BSP draw order

This tank is drawn with no depth buffer and no sorting at runtime.
The draw order was worked out once, when the model was built, and stored as a small tree inside the model.

The problem

Without a z-buffer, polygons simply overwrite each other, so the draw order is the depth test. A fixed order breaks as soon as the camera moves: on the left the hull paints over the turret and the near track. Sorting by distance every frame costs time, and sorting by each face's centre can still get overlapping parts wrong.

How it works

A BSP tree (binary space partition) is built offline:

1. Pick a polygon. Its plane splits space into a front side and a back side.
2. Every other polygon goes to one side. A polygon that crosses the plane is cut in two.
3. Repeat on each side until every polygon sits on a node.

At runtime, for each node: test which side of the plane the camera is on (one dot product). Draw the far side's subtree first, then the node's own polygons, then the near side. That walk is back-to-front for any camera position, with no comparisons between polygons.

What I hit

The splits add up. My tank is 8 boxes, 48 faces. Building the tree with csg.js turned them into 129 polygons on 126 nodes, 13 levels deep. csg.js always splits on the first polygon of each list, with no heuristic. Choosing splitters to cut fewer polygons is where offline tools spent their effort.

The walk visits every node every frame. Here that is 126 side tests, while sorting the 24 visible faces took 80 to 85 comparisons. The tree is not cheaper by count on a model this small. What it buys is no sort at all, a fixed cost per frame, and an order that is correct by construction.

I searched camera angles for cases where the centre-depth sort disagrees with the tree. The worst were around 36° to 54° of orbit at 18° elevation, so the last shot sits there.

My build

csg.js by Evan Wallace: CSG.Node.build and CSG.Plane.splitPolygon, unchanged, only to build the tree once at load. The walk, camera and renderer are my own: a Canvas2D painter with flat shading, no depth test, back faces culled on both sides of the split. The tank is my own low-poly model, not taken from any game.

Trade-offs

• Correct order from any viewpoint, for the static model
• No per-frame sort; one dot product per node
• Works for shapes that pass through each other (barrel in turret, tracks in hull)
• Splits grow the polygon count (48 → 129 here)
• The model must be rigid: moving parts need their own trees
• Every node is visited each frame, even on small models

When to use it

Software renderers, retro-style engines, and any rigid model that has to be drawn without a depth buffer, for example on hardware that can't spare the memory for one.