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.

• Doom’s software renderer draws the level walls front to back.

• Quake’s software renderer also traverses the BSP front to back but only starts to actually draw polygons after all potentially visible surfaces have been visited.

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.

• Thief: The Dark Project drew the world back to front instead. The game did go all-in on BSPs and they split and clipped dynamic objects to sort correctly against the static BSP map.

Even object polygons were sorted using their own BSP trees!

BSP being made

This became clear while implementing a BSP builder:

• Building a BSP is more difficult than a bounding volume hierarchy (BVH).

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):

• A kd-tree is an axis-aligned BSP tree.

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:

BSP on the GPU

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

• You can traverse a BSP in parallel on the GPU if you really want to. And even save the result to an index buffer and reuse it across frames.

• Painter’s algorithm is not a good fit for the GPU because you may have to render the scene a couple of polys at a time to get the correct image.

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.

• You’ll want to store node bounding boxes in the BSP tree for frustum culling.

• You can store geometry in leaf nodes or in inner nodes of the tree. This gives different flavors of a BSP tree.

• Quake stored polygons in inner nodes, Thief in leaves.

  Details on how Quake reduced splits by storing geometry in nodes. (Click to expand)

  Let’s say you want to draw a whole BSP tree front to back. If all your polygons are in leaves of the tree, then you can do a depth-first recursion in the tree where you always visit first the child closer to camera. When you get to a leaf, you draw the submesh stored in that leaf.

  This is simple but produces a lot of polygon splits at tree build time. When you store polygons in inner nodes, less splits are needed but the rendering logic gets more complicated. Michael Abrash explains:

  Getting proper front-to-back drawing order is a little more complicated with polygons on nodes. As we walk the BSP tree front-to-back, in each leaf we mark the polygons that are at least partially in that leaf, and then after we’ve recursed and processed everything in front of a node, we then process all the marked polygons on that node, after which we recurse to process the polygons behind the node.

  So leaves “mark” polygons and nodes draw them. One thing missing from the above explanation is how they deal with the case where some node’s “back” subtree marks poly to be visible but it isn’t drawn by its direct parent. See r_bsp.c how they first recurse to left subtree, draw marked polys, and then the right subtree. According to my experiments, this is a non-issue and all marked polygons are eventually drawn higher up the tree. But it would be nice to know how exactly does the BSP builder guarantee it.

  And you can’t avoid splits even then. Another quote from the Black Book:

  [–] strict BSP order requires that polygons be split so that every polygon falls entirely within a single leaf. This can be stretched by putting polygons on nodes, allowing for larger polygons on average, but even then, polygons still need to be split so that every polygon falls within the bounding volume for the node on which it lies.

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

• A BSP-tree used for collision detection shouldn’t store clipped polygons but references to the original input polys instead. This should be more robust, as a ray never “slips between the cracks,” if you will.

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:

• To be pedantic, a BSP traversal gives you the correct visibility order which is distinct from simple depth sorting which you could also call a “back to front” order.

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.