A first-person game has to decide, every frame, which walls hide which. A binary space partitioning (BSP) tree does most of that work before the game runs. It cuts the level into convex pieces and stores the cuts in a tree, so that from any viewpoint the renderer can visit the walls in order of distance by asking one question at each branch: which side of this line am I on? John Carmack took the idea from graphics research in 1993, while rescuing the Super Nintendo version of Wolfenstein 3D, and rebuilt Doom’s renderer around it. Doom walked its tree from front to back and never drew the same wall or floor pixel twice. Quake took the tree into three dimensions and added a pre-computed list of what could be seen from where.
Fast facts
- The academic method: “On visible surface generation by a priori tree structures”, Computer Graphics, July 1980; later papers by Bruce Naylor of AT&T Bell Labs.
- 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.”
- In Doom: a two-dimensional tree, built before play by a separate program,
doombsp, and walked front to back. - The cost: walls cannot move sideways during play; “Thats why there are no swinging doors in Doom,” Carmack wrote.
- In Quake: a 3D tree plus the Potentially Visible Set, worked out over “one slow, cathartic weekend” after months of trying.
Building the tree
Take a map of walls seen from above. Pick one wall and extend its line right across the level. Every other wall now lies on one side of that line or the other, and any wall the line crosses is cut into two pieces. Repeat the process on each side, choosing a new splitting line each time, until every remaining region is convex: a shape with no corners pointing inwards, so no wall inside it can hide another wall inside it. Each branch point of the tree stores a splitting line; each leaf stores one convex region and the wall pieces around it.
Fabien Sanglard’s Game Engine Black Book: DOOM works through a small example: a square room with a square pillar in the middle, eight walls in all. Three splits turn it into four convex regions. The splits cut some walls, so the eight walls become twelve pieces, but the tree can now put every piece in order from any point in the room with exactly three side-of-line tests. How good the tree is depends on the choice of splitters. A line that divides the map evenly keeps the tree shallow, and a line that crosses few walls creates few extra pieces.
Walking the tree
There are two ways to use the order the tree gives.
The textbook way is back to front. Hearn and Baker’s Computer Graphics calls the BSP tree “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 in a first-person game: the walls never move, and the player does. At each branch, visit the side the viewer is not on first, then the side they are on; nearer walls are then painted over farther ones. The 1980 paper put the saving plainly. Most visibility methods calculate a distance to every polygon that might cover a pixel, but “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.”
Doom goes the other way, front to back, and that is what made it fast. Its R_RenderBSPNode routine works out which side of the splitting line the player stands on, draws everything on that near side first, and only then considers the far side. The renderer keeps a list of which screen columns are already covered by solid walls. A wall piece found later is clipped against that list, so only its uncovered columns are drawn, and each node stores a bounding box for its far side. The check on that box, R_CheckBBox, returns false when the box is outside the field of view or falls entirely within columns already covered, and the whole of that side of the tree is skipped. Sanglard sums up the result: Doom renders walls and flats “with zero overdraw (each pixel is written exactly once)”. Only the sprites and see-through walls, drawn afterwards from back to front, paint over anything.
How Doom came to use it
Doom’s first renderer did without a tree. Carmack described it as “built out of ‘sectors’ – complex polygonal regions with a common floor / ceiling texture and height”. It “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.” John Romero found a case that broke it 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 conversion of Wolfenstein 3D. By Sanglard’s account, in early April 1993, “with only three weeks remaining to deliver a gold cartridge, the contractor was nowhere to be seen”. Wolfenstein’s raycasting renderer was too slow for the console. Romero recalls that Carmack “had several VHS tapes of math conferences, and compendiums of graphics papers”, and names “Bruce Naylor’s May 1993 AT&T Bell Labs paper”, “Constructing Good Partitioning Trees”, from the proceedings of Graphics Interface ’93: “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.” Romero’s own date for the paper falls after the crisis began in April, so the exact order of events in his account is uncertain. Carmack is clear that the SNES game came first. “I do remember clearly that 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.” He told Computer Gaming World the same in 1996. Carmack and Naylor met later, after Doom had shipped, when Naylor visited id during work on Quake and “gave me copies of a bunch of his papers”.
Doom’s tree
Doom’s tree was never built while the game ran. A separate NeXTSTEP program, doombsp, read the editor’s map and wrote the WAD file, 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 three lumps of the WAD: NODES holds the splitting lines, SEGS the wall pieces the splits produced, and SSECTORS the convex sub-sectors those pieces enclose. doombsp scored every candidate line in a region and preferred splitters that kept the tree balanced, created few new pieces and ran along the map’s axes, which made side tests faster and debugging easier.
All of this was paid for once, when a map was built. Sanglard, rerunning doombsp on a NeXTstation TurboColor, measured 8 seconds for E1M1, a minute for E2M7 and just over ten minutes for the 27 maps of the registered game. The tree is two-dimensional: its splitting lines are seen from above, so each point on the map belongs to exactly one sub-sector with one floor and one ceiling. Carmack spelled out the consequences in 1994. Doom “cannot draw sloping floors, overlapping walkways, or tilted walls”, and because partitioning the map “is a time-consuming task” done ahead of time, “the lines that make up the world cannot have their endpoints adjusted during play. Thats why there are no swinging doors in Doom.” Doors in Doom open by raising a ceiling.
Quake
In Quake the tree went fully three-dimensional. Explaining the engine to Computer Gaming World in 1996, Carmack described the BSP tree as “a software tool to order all of the sectors of a virtual world”. The magazine counted several trees in the new engine: two for the world, “to help determine line of sight and to allow the player to traverse the world”, and 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.” For each region of the level, the map compiler works out which other regions could ever be seen from it. During play the engine takes the set for the player’s current region, ignores everything outside it, and turns the visible polygons into spans, “properly clipped horizontal pieces of the polygons”. Monsters and other moving models were then drawn using a z-buffer, which Computer Gaming World called “a rather ‘old-school’ 3D technique”.
By 1997 the pre-computation itself was the point of comparison. Previewing 3D Realms’ portal-based Prey, PC Gamer described what is really Quake’s visibility data: “no matter where you are in a Quake level if you turn somewhere the engine can say, ‘I’m in this position and facing this direction, so if I look at the BSP tree I know what polygons I have to deal with immediately’”. The price was the one Doom had paid: “because the geometry is predetermined there’s little scope for massive moving walls, explosive areas and radical changes to the level design.”
Released source code
id Software released the source code of doombsp in May 1994, with a note from Carmack: “The source code for the binary space partitioner we used for DOOM is now available”. The source code of Doom itself followed on 23 December 1997, including r_bsp.c, the file that holds R_RenderBSPNode and R_CheckBBox; it is now on GitHub under the GNU General Public License, version 2. The Quake source was released under the same licence on 21 December 1999 (see Quake).
Sources
- Andrew S. Glassner (ed.), An Introduction to Ray Tracing (Academic Press, 1989), references: H. Fuchs, “On visible surface generation by a priori tree structures”, Computer Graphics 14(3), pp. 124–133, July 1980.
- Donald Hearn and M. Pauline Baker, Computer Graphics, C Version, second edition (Prentice Hall), section 13-7, “BSP-Tree Method”: back-to-front painting, fixed objects and a moving viewpoint, splitting polygons crossed by a partitioning plane.
- Fabien Sanglard, Game Engine Black Book: DOOM (2018): section 4.5 (
doombsp, the three data structures); section 4.4 and figure 4.12 (theNODES,SEGSandSSECTORSlumps); section 5.12 (the renderer and zero overdraw; the sector-flooding renderer and Carmack on it; Romero on E1M2 and on Naylor’s paper; the SNES Wolfenstein 3D crisis; Carmack on the SNES game; the worked example and the splitter heuristic;R_RenderBSPNode,R_PointOnSideand thesolidsegsclipping); section 5.12.1 (the 1980 paper and Carmack’s interview for Scarydarkfast, with the footnote that he and Naylor met after Doom shipped); appendix C.2 (doombsprun times); appendix F (thedoombspsource release note, May 1994); appendix G.1 (Carmack’s essay from DOOM: Survivor’s Strategies & Secrets, 1994); the automap’s yellow lines for “changes in ceiling height (e.g. doors)”. - id Software, Doom source code,
linuxdoom-1.10/r_bsp.c, released 23 December 1997, GitHub id-Software/DOOM (GPL-2.0) (web):R_RenderBSPNode,R_CheckBBox(“Returns true if some part of the bbox might be visible”) and thesolidsegstest. https://github.com/id-Software/DOOM - Paul Schuytema, “Quake! Programming Techniques”, Computer Gaming World issue 144, July 1996, p. 103 onward: Carmack on learning BSP trees for the SNES Wolfenstein; the trees in Quake; the PVS and the “slow, cathartic weekend”; spans and the z-buffer.
- Preview of Prey, PC Gamer (UK) issue 46, August 1997: Quake‘s pre-computed visibility and its limits, against 3D Realms’ portals.