BSP Lessons

March 7th, 2023

Nobody talks about binary space partitioning (BSP) trees anymore but they used to be a big deal in computer graphics. Here are some BSP lessons I recently learned.

BSP in the 90s

BSP trees were used to accelerate software rendering and collision detection.

What’s pretty wild about Quake is that all potentially visible triangles are rasterized but only the frontmost ones are “scanned out” i.e. shaded and written to screen. So when a door is blocking a view to a room, all polys behind the door are transformed, projected, and converted into horizontal spans. Finally, the last per-scanline depth sorting step discards those occluded spans. The Potentially Visible Set (PVS) is doing the heavy lifting here.

See Michael Abrash’s Black Book’s section “Drawing the World” for more details.

Even object polygons were sorted using their own BSP trees!

BSP being made

This became clear while implementing a BSP builder:

You need to (a) pick the splitting planes carefully and (b) actually go and split the polygons. Pretty tricky code even if you know how. Memory management is also more difficult than when building a BVH because splits can produce new polygons. In a BVH you just partition a static array so storage for all nodes of the tree can be allocated at the start.

And the obvious (in hindsight):

Usually kd-trees are not presented from this point of view because it isn’t very useful. You end up having to split so many polygons, I mean, take a look at what happens:

The green surface in the middle represents a single leaf. All those tiny sliver triangles around its boundaries were generated by axis-aligned splits and weren’t present in the input mesh. What a mess.

BSP on the GPU

It’s hard to find good use for BSPs in an hardware accelerated renderer.

Well yeah, you can bake a traversal into an index buffer like in the above link but that only works if you don’t need to switch textures or shader uniforms. If you’re interested in just rendering Quake BSPs on modern hardware then you can use only the PVS part like in this demo or just render the whole map at once like the Xbox 360 port of Quake 2 did.

BSP in your code

And then some implementation details I learned from Abrash’s Black Book mentioned earlier.

From Christer Ericson’s Realtime Collision Detection’s BSP chapter:

And if you’ve wondered why PlayStation 1 games had often sorting issues, well it had no z-buffer and used “ordering tables” instead, and that’s not enough:

So rendering polygons in BSP traversal order always gives the correct image but for example sorting by polygon’s average camera space Z coordinate does not.

Thanks to mankeli for the Quake BSP discussions and pointing me to the sdlquake source port.