Introduction to BSP Trees

---

What BSP Is

Binary Space Partitioning (BSP) is a technique that recursively divides space using planes to organize world geometry into a tree structure. In 3D engines, each plane splits space into two regions: front and back.

A BSP tree is usually built offline by tools (commonly called a BSP compiler). The input is a set of polygons representing the level geometry. The compiler repeatedly selects a polygon plane and splits the geometry into two sets until the space is fully partitioned.

Because the tree is precomputed, BSP worlds are generally static and not easily modified at runtime.

Where BSP Is Used

BSP was widely used in many classic engines and games, including:

• Doom-based engines
• Unreal Engine
• Quake 1, 2, 3
• Half-Life (GoldSrc)
• LithTech-based games
• Many other FPS engines of the 1990s–2000s

It became popular because it allowed efficient rendering and spatial queries on hardware that lacked modern GPU features.

Building a BSP Tree

The BSP compiler builds the tree by:

1. Selecting a splitter polygon.
2. Dividing the remaining polygons into: polygons in front of the plane polygons behind the plane polygons intersecting the plane (these are split).
3. Recursively repeating the process for each subset.

The result is a hierarchical tree where each node represents a spatial partition.

Splitter Selection

Choosing the correct splitter affects performance. A good splitter should:

• Keep the tree balanced
• Minimize polygon splits
• Avoid generating too many nodes

A common heuristic score:

Score = w1 * |front - back| + w2 * splits + w3 * coplanar

The splitter with the lowest score is selected.

BSP Rendering

Classic BSP rendering uses tree traversal based on camera position.

The renderer determines whether the camera is in front of or behind the current node’s plane and traverses the tree accordingly. This ensures polygons are drawn in the correct order.

Two traversal orders exist:

Back-to-Front Rendering

Polygons are drawn from farthest to nearest.

Advantages:

• Works without a Z-buffer
• Handles transparency naturally

Front-to-Back Rendering

Polygons are drawn nearest first.

Advantages:

• Reduces overdraw
• Allows early termination when the screen is fully filled.

Node BSP vs Leaf BSP

Node BSP

Geometry is stored directly in tree nodes.

Uses:

• rendering
• collision detection (in Solid BSP variants)

Limitations:

• trees can become deep
• slower traversal for large scenes

Leaf BSP (Used by Quake Engines)

In Leaf BSP:

• nodes store splitting planes
• geometry is stored in leafs
• leaves represent convex regions of space

Advantages:

• shallower trees
• faster traversal
• easier visibility determination.

PVS (Potentially Visible Set)

To avoid rendering the entire world, BSP engines often compute a PVS during compilation. 

PVS can also be used to:

• determine which entities are sent to clients in multiplayer
• determine which sounds or events monsters can detect.

For each leaf, the PVS stores which other leaves may be visible from it.

Example:

From leaf	Visible leaves
A	        A, C
B	        B, C
C	        A, B, C

At runtime:

1. Determine the current leaf containing the camera.
2. Render only leaves listed in its PVS.

This dramatically reduces rendering work in complex maps.

PVS Compression

Large maps may contain thousands of leaves, making PVS data large.

A common solution is Zero Run Length Encoding (ZRLE):

• non-zero values are stored normally
• sequences of zeroes are encoded as (0, count)

This works well because most leaves cannot see most of the map.

Additional Optimizations

Frustum Culling

Bounding volumes (sphere or box) are stored for nodes or leaves and tested against the camera view frustum.

Invisible nodes are skipped during rendering.

Portals

Portals define visibility between regions (e.g., doors between rooms). Closed portals block visibility regardless of PVS.

BSP for Collision Detection

A Solid BSP variant marks certain partitions as solid space.

Collision detection works by traversing the tree to determine whether a point or ray enters a solid region. This reduces the number of polygons that must be tested.

When BSP Works Best

BSP is most effective for:

• indoor environments
• static geometry
• corridor-style levels

It performs poorly for:

• large open worlds
• destructible environments
• dynamically changing geometry.

---

Tags: mapping, level design