Doom and BSP rendering

Context: 1993, a budget of a couple of million cycles

The target hardware is an Intel 386/486: no graphics accelerator, no hardware z-buffer, a slow FPU or none at all (the 486SX has none whatsoever). At 35 FPS a frame gets on the order of two to three million cycles for the entire render. "Honest" 3D with per-pixel depth sorting (a z-buffer) or floating point does not fit into that. Wolfenstein 3D (1992) had already shown "3D" through raycasting, but at the cost of hard constraints: walls on a uniform grid, all the same height, no slanted walls. Carmack needed more — arbitrary wall angles, rooms of different heights, stairs, windows. The answer was not to squeeze the hardware but to change the statement of the problem and move the heavy part into level compilation.

Doom's world: a 2D plan with heights

To understand the renderer you need to know what a level is made of (this lives in the WAD):

• vertices — points on the 2D plan.
• linedefs — segments between vertices (a wall or a boundary between sectors).
• sidedefs — a "side" of a line: which textures (upper/lower/middle) and which sector it belongs to.
• sectors — regions with a floor height, a ceiling height, textures and lighting. Height is the only "third coordinate".
• segs — pieces of linedefs after the BSP has cut them up; these are what the engine draws.

The main consequence of two-dimensionality: a point (x, y) on the plan belongs to exactly one sector — which means the map cannot have two floors stacked above one another in the same place. That is the 2.5D constraint: the world looks volumetric (thanks to heights and projection), but geometrically it is flat, and so the visibility problem reduces to a two-dimensional one. "No room over room" is not a bug but the very "can't" that makes the algorithm cheap.

Why this is not raycasting

A common confusion: "Doom casts a ray for each column and looks for a wall". That is Wolfenstein 3D: one ray per screen column, traced across a uniform grid (DDA) to the first wall → distance → column height. The grid and the single height are consequences of raycasting itself.

Doom works the other way round: it doesn't ask "what is in this column?", it takes the actual wall segments and projects them onto the screen as vertical trapezoids, clipping away what is hidden as it goes. The "who to draw first" order comes from the BSP, not from a ray. That is exactly what lifts Wolf3D's restrictions: walls at any angle, sectors of different heights, portals (openings between sectors of different heights — windows, steps).

Projection: where the 1/z comes from

The camera sits at the origin looking along an axis. A point on a wall at perpendicular distance z (depth along the view) and world height h above eye level. The projection plane (the screen) stands at distance d_proj. By similar triangles (a shared angle at the camera): the ratio of screen height to d_proj equals the ratio of world height to z. d_proj itself is set by the horizontal field of view and the screen width W:

In Doom the horizontal FOV is 90° and the screen is 320 pixels → d_proj = 160/tan(45°) = 160. It is convenient to introduce scale — how many screen pixels one unit of world height covers at a given depth z:

Then the screen vertical coordinate of a world height h_world (relative to the eye height viewz), and the full wall height on screen:

There is your "1/distance": column height is inversely proportional to z.

Plug in numbers. A wall of height h_wall = z_ceil − z_floor = 128 units at depth z = 256 → scale = 160/256 = 0.625 → h_screen = 128 · 0.625 = 80 px. Step back to z = 512 and the same wall is half as tall, 40 px. All the "depth" comes from one division by z.

From a column to a whole wall. One seg is a segment with its two ends at different depths z₁, z₂, so it has two scales: d_proj/z₁ and d_proj/z₂. The engine steps scale linearly across screen columns between the seg's edges (which is correct: scale ∝ 1/z, and 1/z for a flat wall is linear in screen space) — where the wall is nearer the columns are taller, where it is farther they are shorter. That is how vertical columns add up into the trapezoid of an angled wall, and the perspective unfolding of the horizontal texture is a direct consequence of the same 1/z step.

And a subtle point about the textures themselves: within one column the vertical sampling is affine (the whole column is one horizontal point of a vertical wall, i.e. one z), so frac += iscale suffices. Across columns z changes — and the horizontal direction requires that same 1/z correction from the scale step above.

BSP: construction (offline)

A BSP (Binary Space Partitioning) is built by a node builder when the level is compiled. The recursion: pick a splitting line (usually along one of the segs); segs in front of it go into one branch, those behind into the other, and those crossing the line get cut in two (important: a split really does create new segs). The recursion ends when a branch holds a convex set of segs — a subsector: inside a convex region walls cannot occlude one another ambiguously, so they can be drawn in any internal order. An internal tree node stores the splitting line (a point p and a direction (dx, dy)) and each child's bbox.

Don't confuse sector and subsector. A sector is a gameplay unit (its own floor/ceiling height, lighting, a "lava/teleport" type); a subsector is a rendering unit (a convex BSP leaf). A non-convex sector gets cut by the tree into several subsectors, so a level usually has more subsectors than sectors. The player "stands in a sector", but the engine walks and draws "by subsector".

Choosing the splitter is a compromise: the "luckier" the line, the fewer splits (fewer new segs, less memory) and the more balanced the tree (shallower traversal). These two goals conflict, and the optimal BSP (minimum splits / minimum nodes) is NP-hard, so node builders use greedy heuristics (for example, minimize the number of splits while penalizing imbalance).

BSP: traversal (runtime, front to back)

Given the camera position, the tree is walked so that segs come out strictly from near to far:

render_bsp(node):
    if node is subsector:
        draw_segs(node)              # a convex leaf — internal order doesn't matter
        return
    side = point_side(view, node.partition)   # which side the camera is on (sign below)
    render_bsp(node.child[side])              # the NEAR side first
    if bbox_visible(node.child[1 - side]):    # the far side — only if not yet occluded
        render_bsp(node.child[1 - side])

The side test is the sign of a 2D cross product (the signed area): for a splitter with point p and direction (dx, dy) and a camera at v

s > 0 means the camera is on one side, s < 0 the other. We descend into the near branch first → near walls come out before far ones. Since leaves are convex and the splitting planes are consistent, this order matches true depth for any camera position (the proof is in the deep end).

Clipping the occluded: why the traversal is linear

Front-to-back only pays off together with cheap rejection of what is already covered. Doom keeps two structures of screen coverage:

• solidsegs — a list of horizontal column ranges already fully covered by solid walls. A new seg is first clipped against them; if its range is already fully covered it is discarded instantly, without being drawn.
• ceilingclip[x] / floorclip[x] — for each column x, the current upper and lower boundary of pixels still free. A solid wall writes the columns and squeezes the window "to zero"; a portal (an opening) merely raises the floor or lowers the ceiling, leaving a slit for the far walls beyond it.

So every screen pixel is written at most once (no overdraw — critical, fill rate was the bottleneck), and as soon as solidsegs covers the whole screen the BSP traversal can be cut short. The result: O(n) in the number of segs, with no sorting and no per-pixel depth.

🕹 Games to play — and what to notice

One question — "how do you draw 3D on a CPU with no GPU" — with five different answers under different constraints, from a grid of rays to real 3D. For each: how it was done and what to play to see it with your hands (ordered simple to complex).

# the texture column in fixed-point 16.16
frac = texturemid + (y0 - centery) * iscale
for y in y0 .. y1:
    pix[y] = src[ (frac >> 16) & mask ]   # the integer part as an index
    frac += iscale                          # step through the texture, no float