Overview
Doom looked 3D but ran on hardware that couldn’t do 3D. BSP trees made it possible by pre-computing spatial relationships during level compilation. The algorithm recursively divided space into regions, creating a tree structure that told the engine exactly what to draw and in what order—no wasted pixels, no z-fighting.
Fast facts
- Origin: Computer science (1969).
- Gaming use: Doom (1993).
- Purpose: Visibility determination.
- Compile time: Pre-calculated.
How BSP works
| Step | Process |
|---|
| 1 | Choose splitting plane |
| 2 | Divide space in two |
| 3 | Recurse on each half |
| 4 | Build tree structure |
Doom implementation
| Use | Benefit |
|---|
| Wall rendering | Back-to-front order |
| Collision detection | Efficient spatial queries |
| AI pathfinding | Navigation assistance |
Compile-time calculation
| Advantage | Trade-off |
|---|
| No runtime cost | Level must compile |
| Optimal ordering | Static geometry only |
| Consistent speed | Map changes need rebuild |
Visibility benefits
| Problem solved | Method |
|---|
| Overdraw | Render visible only |
| Sorting | Automatic ordering |
| Occlusion | Behind walls skipped |
Quake evolution
| Enhancement | Purpose |
|---|
| PVS | Potentially Visible Set |
| Portals | Room connectivity |
| Lightmaps | Pre-calculated lighting |
Legacy
| Use | Application |
|---|
| Collision detection | Spatial queries |
| AI navigation | Pathfinding |
| CSG operations | Level building |
Modern alternatives
| Technique | Use case |
|---|
| Octrees | Dynamic scenes |
| BVH | Ray tracing |
| GPU culling | Hardware acceleration |
See also