BSP Trees
3D rendering optimisation
A BSP tree sorts a level's walls in advance so the renderer can draw them in order from any viewpoint. John Carmack learned it from Bruce Naylor's papers in April 1993 while squeezing Wolfenstein 3D onto the SNES, rebuilt Doom around it, and took it into 3D with the PVS for Quake.
A binary space partitioning tree cuts a level into convex pieces in advance, so that at run time the renderer can walk the tree from any viewpoint and draw the walls in order without measuring a single depth. John Carmack learned the method in April 1993 while squeezing Wolfenstein 3D onto the Super Nintendo, then rebuilt Doom’s renderer around it; Quake took the tree into three dimensions and added the pre-computed visibility set that made a true 3D engine run on a Pentium.
Fast facts
- The academic method: a tree built by splitting space with planes, traversed back to front like the painter’s algorithm; the standard textbook treatment names Bruce Naylor’s papers.
- How it reached games: Carmack, in 1996: “I actually had DOOM up and running before I knew about BSP trees… I learned about them when I was doing WOLFENSTEIN for the Super Nintendo, because I had to make it go a lot faster.”
- The paper: Naylor’s “Constructing Good Partitioning Trees”, Graphics Interface ’93, in Carmack’s collection according to John Romero.
- In Doom: built offline by
doombsp, which took ten seconds for E1M1 and eleven minutes for the full registered game on a NeXTstation TurboColor. - In Quake: a 3D tree plus the Potentially Visible Set, worked out over “one slow, cathartic weekend” after months of trying.
What the tree does
Hearn and Baker’s Computer Graphics describes the method as “an efficient method for determining object visibility by painting surfaces onto the screen from back to front, as in the painter’s algorithm”, one that “is particularly useful when the view reference point changes, but the objects in a scene are at fixed positions.” That is the situation a first-person game is in: the walls never move, the player does. Naylor’s thesis put the saving plainly. Most visibility methods calculate a distance from the eye to every polygon that might cover a pixel; “Our approach eliminates these distance calculations entirely. Rather, it transforms the polygonal data base (splitting polygons when necessary) into a binary tree which can be traversed at image generation time to yield a visible priority z value for each polygon.”
The build is recursive. Pick a wall and extend its line across the level; everything falls on one side or the other, and any wall the line crosses is cut in two. Repeat on each side until every remaining region is convex. Each node of the tree is a splitting line, each leaf a convex piece of floor. To draw a frame, start at the root, ask which side of the line the camera is on, and recurse into the far side first, then the near side. The walls come out in order from any position, and the only work per node is one side-of-line test.
How Doom came to use it
Doom’s first renderer did without a tree. Carmack has described it as “built out of ‘sectors’ – complex polygonal regions with a common floor / ceiling texture and height”, which “started in the view sector and recursively flowed into the adjoining sectors, but because they could all be complex polygons it was a lot of record keeping to know what parts you had already visited or were in the stack somewhere. It worked, and simple areas were fast, but it slowed down precipitously with complexity.” Romero found the failure case while building E1M2 “around April 1993”: a set of circular stairs that made the sector-list code “take a really long amount of time to execute”.
The fix came from an emergency elsewhere. id Software had subcontracted the Super Nintendo port of Wolfenstein 3D, and in early April 1993, by Fabien Sanglard’s account, “with only three weeks remaining to deliver a gold cartridge, the contractor was nowhere to be seen.” The SNES could not run Wolfenstein’s raycaster fast enough. Romero recalls that Carmack “had several VHS tapes of math conferences, and compendiums of graphics papers from conferences because game books were a rare thing back then”, and that “Bruce Naylor’s May 1993 AT&T Bell Labs paper was titled ‘Constructing Good Partitioning Trees’ and was published in the proceedings of Graphics Interface ’93. John had this book in his collection. Bruce’s explanation of BSPs was mostly to cull backfaces from 3D models, but the algorithm seemed like the right direction, so John adapted it for Wolfenstein 3D.”
Carmack said the same to Computer Gaming World in July 1996 — “I learned about them when I was doing WOLFENSTEIN for the Super Nintendo, because I had to make it go a lot faster” — and later to Sanglard: “I first used BSP for the SNES version of Wolfenstein, which was a gentle introduction with everything being axial and easier to visualize, which gave me more confidence I would be able to make it work when I went back to working on Doom.” Naylor himself “came down and visited here and gave me copies of a bunch of his papers.”
Building the tree
Doom’s tree was never built at run time. A separate tool, doombsp, read the editor’s map and wrote the WAD, adding “three data structures… A binary space-partitioned version of the map expressed a node tree to speed up rendering. A blockmap accelerated collision detection. Finally, a reject table accelerated A.I. processing.” The tree lives in the NODES, SEGS and SSECTORS lumps — the split lines, the wall fragments the splits produced, and the convex sub-sectors those fragments enclose. The cost of the pre-computation was paid once, on the NeXT: “running doombsp on E1M1 took 10s. On E1M2, it took 30s. On E2M7, it took a full minute. The first nine maps of the shareware took 3m26s to process. The full twenty seven maps of the registered version required 11 minutes.”
Quake
Doom’s tree was two-dimensional — its split lines were vertical planes, and its levels had no room above another. Explaining Quake to Computer Gaming World in 1996, Carmack described the tree as “a software tool to order all of the sectors of a virtual world”, and the magazine counted how many the new engine used: two for the world, “to help determine line of sight and to allow the player to traverse the world”, plus one for “each movable object… (objects like ammo boxes, but not animated beasties)”. “It’s esoteric, technical stuff,” Carmack admitted. “A lot of people said that we couldn’t use BSPs for a general 3D engine, but we think they’re wrong.”
The tree alone was not enough in three dimensions. “With levels averaging around 10,000 sectors, having to consider extra sectors becomes very inefficient, even with the help of a BSP tree. That problem occupied Carmack for several months, and then during one slow, cathartic weekend, he solved it. Using the world BSP data, Carmack devised a routine that pre-calculated the Potentially Visible Set (PVS) of sectors.” From each leaf, the compiler works out which other leaves could ever be seen; at run time the engine rejects everything outside the current leaf’s set before the tree is walked at all.
By 1997 the pre-computation itself was the point of comparison. Previewing 3D Realms’ Prey and its portal engine, PC Gamer summarised id’s approach — “It stores these in a BSP tree, so no matter where you are in a Quake level… I know what polygons I have to deal with immediately” — and its limit: “because the geometry is predetermined there’s little scope for massive moving walls, explosive areas and radical changes to the level design.”