In 1993, home computers were too slow to render true 3D game worlds in real-time. To make Doom run smoothly, John Carmack implemented "binary space partitioning" (BSP), a technique from a 1969 academic paper. By splitting the game's map into a tree-like hierarchy of spaces, the engine instantly knew which walls were behind others, allowing it to render only what the player could actually see.
The Hidden Surface Problem on 1990s Hardware
In the early 1990s, personal computers lacked dedicated 3D graphics hardware. All rendering calculations had to run entirely on the central processor, typically an Intel 386 or 486 chip. For a computer game attempting to depict an immersive, three-dimensional environment at acceptable frame rates, the primary bottleneck was visible surface determination. A naive rendering engine would attempt to sort and draw every surface in the environment from furthest to nearest, a method known as the painter's algorithm. On complex levels with hundreds of walls, computing the depth of every polygon and repeatedly overdrawing pixels that would ultimately be hidden by closer objects quickly overwhelmed the processor.
Drawing the same pixel on screen multiple times, known as overdraw, was too computationally expensive for commodity hardware of the era. If the game could not rapidly determine which walls stood in front of others from the player's current vantage point, performance collapsed. To maintain smooth motion, a graphics engine needed a way to instantly identify visible surfaces and skip the hidden geometry entirely, without performing expensive per-polygon sorting calculations on the fly during every single frame.
The Pseudo-3D World Model
The Doom engine solved this challenge in part by constraining the nature of its 3D environment. Rather than building a fully unrestricted three-dimensional world where geometry could exist at arbitrary angles and orientations, the engine treated maps fundamentally as two-dimensional top-down floor plans. Walls were defined as vertical two-dimensional lines with assigned heights, connecting coordinate points called vertices. The spaces enclosed by these boundary lines formed distinct regions known as sectors.
Each sector stored independent numerical values for floor height, ceiling height, textures, and lighting levels. Because the core map data was stored as a flat 2D layout with vertical extrusion, the world had strict architectural rules: no room could be positioned directly on top of another room, and walls were always strictly perpendicular to the floor. This structural limitation dramatically simplified the mathematical geometry of the level, transforming a complex 3D visibility problem into a manageable 2D spatial division task.
Binary Space Partitioning in Practice
To achieve rapid visibility checks, the engine adopted binary space partitioning (BSP). Rather than sorting the environment while the game was running, the spatial analysis was performed beforehand during an offline preprocessing stage. A specialized tool, known as a node builder, analyzed the level's two-dimensional lines and recursively divided the map space into smaller and smaller convex subsectors using partitioning lines.
The resulting data structure was a BSP tree. At the root of the tree was a line that split the entire map into two halves. Each of those halves was split again by subsequent lines, continuing down until the remaining spaces were guaranteed to be convex subsectors where no line segment could obstruct another within the same leaf. Because this computation happened when the level was compiled rather than during gameplay, the computer could bypass expensive dynamic sorting algorithms during live rendering.
Front-to-Back Traversal and Occlusion
When rendering a frame, the engine traversed the precomputed BSP tree starting from the player's current coordinate position. At each decision point in the tree, the engine evaluated which side of the partitioning line the player was standing on. This allowed the renderer to walk the tree in strict front-to-back order relative to the camera, guaranteeing that the closest subsectors were always processed before the ones farther away.
As nearby wall segments were projected onto the screen, the engine recorded which horizontal columns of the display had been filled using a one-dimensional array. Because walls were drawn from closest to furthest, any column that had already been completely covered by a nearer wall was marked as solid. When the renderer later encountered geometry that fell into already-filled columns, it clipped and discarded that geometry immediately. This early rejection eliminated overdraw for walls, ensuring that the engine only spent processing time rendering visible pixels.
Visplanes, Colormaps, and Sprites
While walls were rendered as vertical columns via the BSP traversal, horizontal floors and ceilings required a different pipeline. As the engine drew wall segments, it tracked the upper and lower boundaries of the visible openings into adjacent sectors. These exposed horizontal gaps were grouped into continuous regions known as visplanes, which were subsequently drawn as horizontal spans of floor and ceiling textures.
Dynamic objects, including enemies, items, and projectiles, were not part of the static BSP tree. Instead, they were represented as two-dimensional animated sprites that always rotated to face the player's viewpoint, commonly known as billboards. Sprites were sorted and drawn after the walls and visplanes had been established, clipped against the stored depth and occlusion data. Lighting was simulated efficiently without dynamic light calculations by applying distance-based color lookup tables, known as colormaps, which faded textures toward darker palette entries as distance from the camera increased.
The WAD Architecture and Tooling
A defining technical choice of the Doom engine was the strict separation of executable programming logic from game content. All graphics, sound effects, music, and level geometry were stored in external archive files known as WADs (Where's All the Data). Because level maps were cleanly decoupled from the engine executable, independent developers and enthusiasts could construct their own custom levels and run external node builders to compile BSP trees for user-created maps.
This modular design fostered a widespread community of content creators and led to the development of numerous third-party map editors and BSP compilers. By solving visible surface determination through a combination of 2D map constraints and precomputed spatial partitioning, the engine demonstrated that sophisticated real-time rendering was achievable on general-purpose personal computers, shaping the trajectory of subsequent first-person 3D game engines throughout the 1990s.
Key takeaways
•The Doom engine relied on a pseudo-3D representation where 2D floor plans with vertical height parameters allowed visibility sorting to be solved in two dimensions.
•Binary space partitioning (BSP) divided the map during an offline preprocessing step into a tree structure, eliminating expensive real-time sorting during gameplay.
•Traversing the BSP tree from front to back allowed the engine to use a 1D screen occlusion array to discard hidden walls before drawing them, eliminating costly pixel overdraw.
•Separating map geometry and game data into WAD files allowed external tools to compile custom BSP trees, establishing an enduring modding ecosystem.