BSP-Tree Painter's Algorithm - Sixth 3D
Table of Contents
1. The problem: painter's algorithm with a bad sort key
This engine is a software renderer without a Z-buffer. Visibility is decided the painter's way: draw far things first, near things last, and let later paint overwrite earlier paint. That requires sorting all polygons by depth — and the cheap way to sort is a single key per polygon: its average Z.
Average Z works until two polygons' depth ranges overlap: a floor tile that extends under a piece of furniture, a wall seen through a doorway. Then polygon A is partly nearer and partly farther than polygon B, and no single key can order them correctly. Whichever one sorts second overdraws the other across its whole surface — the farther polygon visibly wins in places where it should lose. The result is flicker or stable wrongness, depending on sort stability.
Figure 1: The depth-range overlap that defeats average-Z sorting. The overlap region has no correct global order.
Z-buffers solve this per-pixel. Without one, you need an order that is provably correct per polygon fragment — which is what a BSP tree delivers.
2. The idea: partition space, split what straddles
Binary Space Partitioning divides the world with planes. Pick a polygon's plane as the partition plane. Every other polygon is then:
- coplanar — lies exactly on the plane: store it in this node,
- in front — entirely on the normal's side: recurse into the front subtree,
- behind — entirely on the other side: recurse into the back subtree,
- spanning — crosses the plane: split it in two along the intersection line and send each fragment to its own side.
Figure 2: A polygon crossing the partition plane is cut into a front and a back fragment. Each fragment then lies entirely in one half-space.
The splitting is the key move. After it, every fragment lies entirely on one side of its node's plane, so for any viewer position a strict back-to-front order exists — the property average-Z sorting could not guarantee. Interpenetrating geometry is handled for free: penetration always means some polygon straddles some plane, and the split resolves exactly that case.
Build-time cost: the tree is computed once when geometry changes, not
per frame. Splitting can increase the polygon count (the House demo's
BSP build is logged with -De3d.bsp.debug).
3. Per frame: back-to-front from the viewer
Rendering does not re-sort the geometry. Instead the tree is traversed from the current camera position: at each node, the half-space that does not contain the viewer is farther away, so its contents come first. Recursion yields a complete back-to-front fragment sequence in O(fragments).
Figure 3: Traversal from the viewer position assigns each fragment a rank. Ranks feed the aggregator's comparator; unranked shapes keep average-Z behavior.
In Sixth 3D the traversal emits ranks, not paint calls: each
fragment receives setBspRank(slot, rank) with 0 = farthest. The
render aggregator's comparator then orders two ranked shapes by rank
and falls back to average Z for everything else. This slots into the
existing triple-buffered pipeline (ranks are stored per slot, so a
paint pass reading an older slot sees that frame's ranks) and keeps
non-BSP shapes — markers, lines, overlays — on the old Z-sort path.
Consequence for scene authors: put all interpenetrating static
geometry into one BspCompositeShape. Fragments in the same tree are
guaranteed correct relative order; shapes outside it still sort by Z
exactly as before.
4. How it plugs into the engine
BspCompositeShape keeps the polygons you add as the editable source
of truth. When the render list is (re)built after a structural edit:
- every
SolidPolygon(including those inside nested composites, which are flattened) is fan-triangulated; - the triangles are compiled into the splitting
BspTree— the sameBspTreeclass the CSG system uses; - split fragments that came back as quads are re-triangulated, since fragments within one node are coplanar and their mutual order never matters;
- fragments become the render list — plain, or wrapped as
LightmappedTrianglewhen lightmapping is enabled (GI lightmaps live on BSP fragments; see Global illumination).
Then every frame, BspCompositeShape.transform() runs the traversal
and assigns ranks. Because ranks are pure functions of viewer position
and tree, this is safe to run while parallel transform chunk tasks are
still in flight.
5. Limitations
- Dynamic geometry is expensive: moving a polygon means rebuilding (or expensively updating) the tree. BSP ordering suits static level geometry; moving objects stay on the Z-sort path.
- Polygon count grows with splits; deeper trees cost memory and traversal time.
- Nested composites are flattened at build time assuming identity transforms — animate transforms above the BSP composite, not inside it.
- Split fragments lose backface culling — the correct painter order makes this cosmetically irrelevant, at a small overdraw cost.
- Frustum culling applies to the composite as a whole; individual nested composites are no longer culled separately.
- Classic historical note: Doom (1993) shipped exactly this technique — a BSP-compiled level drawn far-to-near with no depth buffer.