Module 3 · The 3D revolution (1993–1999)

Quake: real 3D — BSP, PVS and baked light

Three years after Doom, id moved to real 3D: arbitrary geometry, free look, perspective-correct textures. The price of honesty is paid in advance: visibility and lighting are baked by the map compiler, leaving the runtime cheap drawing.

deep~22 min

The gist in 30 seconds

Doom was 2.5D: a 2D BSP over lines, sectors with heights, no room over a room and no looking up. Quake (1996) is real 3D: arbitrary polygons, free look (camera pitch up and down), perspective-correct textures. To make that fly on a Pentium, id moved the expensive parts into offline map compilation with three tools: QBSP builds the 3D BSP and the portals, VIS computes the PVS (for every convex cell, a bit list of "what can be seen from here at all"), and LIGHT bakes static lighting into lightmaps. At runtime: take the camera's cell, read its PVS → draw only what is potentially visible; hide the perspective division 1/z under integer work (once every 16 pixels). Honest 3D, paid for up front.

Real 3D versus Doom's 2.5D

Doom and Quake both rest on a BSP — but in a different number of dimensions, and that changes everything.

—	Doom (1993)	Quake (1996)
BSP	2D: splitting lines in the plan	3D: splitting planes in the volume
Geometry	sectors with floor/ceiling heights	arbitrary convex brushes
Room over room	impossible	possible
Looking around	no camera pitch (vertical autoaim)	free look up and down + movement in 3D
Textures	vertical stretch, no perspective correction	perspective-correct UVs
Lighting	brightness per sector	baked lightmaps (a texture of light)

The data structure is the same — a binary space partitioning tree — but in 3D it cuts the volume with arbitrary planes into convex cells (the tree's leaves). One room usually fragments into several convex cells. The BSP here works on three fronts: draw order, collision and visibility storage (PVS).

PVS — precomputed visibility

Quake's main idea: visibility isn't computed in the frame, it is compiled in advance. Between adjacent cells QBSP automatically places portals — "windows" through which one cell can see another. These portals exist only during compilation. The VIS tool runs a region-visibility algorithm over them (Seth Teller, 1992; Carmack implemented it in 1996) and stores, for each cell, a bit vector: which cells are potentially visible from at least some point inside it. That is the PVS — the Potentially Visible Set (plus an analogous PAS for sound).

At runtime the engine takes the leaf the camera is in, reads its PVS bitmask and draws only the flagged cells. Instead of walking the whole map, one lookup: out of a bit vector as long as the map's leaf count (hundreds to thousands), a tight cell has a handful to a few dozen bits set. After that come ordinary frustum culling (what is in view) and the BSP order.

Baked light: lightmaps

The LIGHT tool casts rays from all the map's light sources offline and writes the result into a lightmap — a separate low-resolution texture of light (roughly one sample per large block of surface; lightmaps are packed into atlases such as 128×128 covering many surfaces). At runtime a pixel = base_texture × lightmap. This decouples detail from lighting: geometry and pattern live in a hi-res texture, light in a lo-res lightmap.

To avoid repeating the multiply every frame, Quake caches the result in a surface cache: assemble a lit surface once and reuse it while it stays in frame. LIGHT's -extra flag takes 4 samples per texel and averages them — softer shadow edges. The price of baking is that light is static: you can't move a lamp or a wall (a few dynamic lights — muzzle flashes — were layered on separately and cheaply).

Perspective-correct textures and the division trick

Honest 3D demands perspective correction: interpolating u,v linearly in screen space along a receding polygon warps the texture. The correct approach is interpolating u/z and 1/z (which are linear in screen coordinates) and then dividing:

u = \frac{interp (u / z)}{interp (1 / z)}

The problem: a division on a Pentium (FDIV) takes up to ~39 cycles, which is unaffordable per pixel. Michael Abrash's solution: compute exact u,v once every 16 pixels and interpolate linearly in between (the error over such a span is invisible). And the main trick is overlap: the FDIV for the next 16-pixel span is launched at the start of the current one; while the FPU spends 30+ cycles dividing, the integer U/V pipes draw the current 16 pixels. The division comes out "free" — hidden under the drawing, ~7.5 cycles per pixel.

A bridge to Mode 7. Remember the SNES's per-line perspective? There the depth is constant along a line → one 1/z division per line. In Quake a polygon recedes and z changes along a span → the division is needed periodically (every 16 pixels). Mode 7 is the degenerate case of "N = the whole line width".

Deep end · theory: why the PVS is "potentially" and why that is safeskippable

Region visibility through portals

VIS solves not "is a point visible from a point" but "is a cell visible from any point of another cell". A line of sight has to pass through a sequence of portals; the problem reduces to whether a straight line exists that pierces every portal in the chain (via separating/clipping planes between portal edges). If even one such line exists, the target cell goes into the PVS.

Conservativeness

The PVS is conservative: it may flag extra cells (ones not actually visible from the current point or angle) — that only costs extra draws. But it never misses a genuinely visible cell — otherwise holes would appear in the world. Exact per-pixel visibility would depend on camera position and angle and would cost per-pixel work in the frame — precisely what precomputation eliminates. So a coarse-but-safe per-region approximation is stored instead of an exact per-point one.

Perspective correction: where the warping comes from

A screen coordinate ∝ x/z. Interpolating u linearly across the screen implicitly assumes z is constant — on a receding polygon that makes the texture "swim". What is linear in screen space is u/z and 1/z; those get interpolated, and the division at the end recovers the true u. The span length between exact divisions is an "error vs cost" compromise: Quake's 16 pixels are chosen so the error is invisible while the FDIV just keeps up with drawing the span.

Deep end · engineering: the map compiler and the runtime pipelineskippable

Three tools, in sequence: QBSP (the BSP tree + the .prt portals) → VIS (the PVS from the portals; on 1996 maps this could take hours) → LIGHT (ray-traced light into lightmaps). A map is a "compiled binary" of a level.
The runtime culling cascade: PVS (coarse, precomputed) → frustum cull (by field of view, in the frame) → BSP order (back-to-front / front-to-back with an edge list). Each layer removes its share.
Surface cache: a lit surface (texture × lightmap) is assembled once and cached; redraws take the ready result. Memory traded against computation.
Abrash's inner texturing loop: the next span's FDIV overlaps the integer drawing of the current one on the Pentium's paired pipes → ~7.5 cycles/pixel (that is for the 16-pixel spans on the ASM path; the default C path of the shipping build divides every 8 pixels). This doubled the frame rate over a naive version.
Software rendering first. Quake shipped with a software rasterizer; GLQuake/VQuake (hardware acceleration) came later. A hardware GPU removed the manual FDIV trick, but PVS, BSP and lightmaps stayed (under GL the surface cache is no longer needed — texture and lightmap are combined on the fly).

Analogy

Quake is a museum prepared before opening day. The halls are laid out in advance (BSP cells); each hall has a plaque listing which other halls can be seen from it through the doorways (the PVS); the lighting has been arranged and "baked" into the walls (lightmaps). The runtime visitor simply walks in and reads the ready plaque "from here you can see halls 3, 7, 12", recomputing neither visibility nor light on the way. All the heavy work was done before the first player arrived.

Why it matters

Quake is the canonical example of "move the expensive part offline". The line between what to precompute at map compile time and what to compute in the frame is exactly the budget choice that still decides whether an engine flies: baked GI versus realtime GI, static lightmaps versus dynamic shadows. To understand Quake is to understand that precomputation is not a hack but an architectural decision.

🔁 Beyond games — where this transfers

Quake gives you two powerful moves: "compute it in advance, at runtime just select" (PVS, lightmaps) and a spatial index (the BSP), plus amortizing an expensive operation (a division every 16 pixels).

Systems / databases: the PVS is a materialized view / precomputed index: the expensive answer is computed offline and the runtime is a lookup. The BSP is a spatial index, kin to the k-d tree, BVH and R-tree: partition space so you don't scan everything. Conservative visibility = "better extra than missing" (as in a compiler's alias analysis).

ML / AI: "bake offline, serve cheap" is precomputed embeddings / a feature store (heavy features computed ahead of time, inference is a lookup) and ANN indexes (HNSW/IVF) — a spatial index over embeddings, the same BSP-over-a-world: partition the space so you don't do a full scan. The KV cache is a surface cache for a transformer: the computed prefix state gets reused. A division every 16 pixels = chunking / gradient accumulation: amortize the expensive operation along an axis.

Performance: a lightmap is memoization of an expensive computation into a texture; the surface cache is reuse across frames. "Don't compute in the hot loop what doesn't change".

The principle: decide in advance everything that is invariant at runtime; let the runtime merely select from what was precomputed and amortize what it has to compute.

🔧 Run it and poke at it — on your home machine

What to play is below (🕹). Here — get inside the engine through the console:

🔧 Poke at it (debug) ~30 min, a source port

Install QuakeSpasm/Ironwail and open the console (~). r_speeds 1 gives you counters of drawn surfaces and edges. Now r_novis 1 — you have turned the PVS off: the engine starts drawing everything in the frustum, the counters spike and the frame rate drops; r_novis 0 brings it back. Then r_fullbright 1 (needs developer 1 / cheats) — you have turned the lightmaps off: the atmospheric lighting vanishes and the world goes flat.

🧪 Test it (QA eyes) ~15 min

Look for the consequences of precomputation: a "room over a room" (impossible in Doom); where the PVS "leaks" (sometimes you can see farther than needed — conservativeness); hard edges in baked shadows; the staticness of the light (firing gives a dynamic highlight over a static picture). The artifact checklist of a precompute engine.

Checklist: saw r_speeds jump with r_novis 1; turned the light off with r_fullbright; found a room over a room and judged where the PVS leaks.

🕹 Games to play — and what to notice

From the 2.5D predecessor to real 3D and what grew on top of it. For each: what is inside and what to play or type into the console.

Doom 1993 · 2.5D, the contrast

A 2D BSP, sectors with heights, no camera pitch and no rooms over rooms. The same precomputation technique, but in the plane — an excellent contrast to Quake.

🎮 Play: in Doom, try to find a room directly above another — there isn't one; vertical shooting runs on autoaim. That is the 2.5D ceiling. The full analysis is in the Doom and BSP lesson.

Quake — the PVS live 1996 · r_novis

From the camera's cell, only its PVS gets drawn. You can switch that off and see the cost.

🎮 Play: in QuakeSpasm type r_speeds 1, then r_novis 1 — the surface counter jumps several times over and the frame rate falls: the engine draws the whole potentially-in-frame world with no visibility culling. r_novis 0 and the PVS starts cutting again. You are literally toggling precomputed visibility.

Quake — the freedom of 3D full 3D look + room over room

Arbitrary geometry and full freedom of view — what Doom couldn't do.

🎮 Play: in Quake, find a balcony above a hall (a room over a room — impossible in Doom) and look straight up and straight down. Free camera pitch plus perspective-correct walls at any angle = real 3D, not pseudo.

Quake — baked light r_fullbright

All the "atmosphere" of the levels is static lightmaps over the textures.

🎮 Play: with developer 1, type r_fullbright 1 — the shadows and light gradients vanish and the world becomes uniformly bright and flat. Toggle it on and off and you'll see how much mood a single baked layer of light carries.

Half-Life / Quake II the engine's descendants

GoldSrc (Half-Life) and Quake II stand on the same BSP+PVS+lightmap, adding colored light and more dynamism. The architecture of visibility and baked lighting survived to the end of the 1990s almost unchanged.

🎮 Watch: Half-Life has the same BSP tree and PVS; developer 1 and the equivalent of r_speeds will show the same culling mechanics. Compare HL's colored light with Quake's monochrome lightmaps.

Connections

foundation

Doom and BSP — a 2D BSP, sectors and a column rasterizer; Quake generalizes the same partitioning idea to full 3D.

contrast

SNES Mode 7 — pseudo-3D from a single layer: the 1/z division once per line (constant depth). Quake divides per pixel or span, because depth changes along a polygon.

Overview · Module 3 — the rest of the 3D era's lessons: the rasterization pipeline, cameras, client-side prediction (QuakeWorld).

Questions worth asking

If the PVS already says what is visible, why also do frustum culling and a BSP traversal?

They cut different things. The PVS is coarse, precomputed and per region: "what is visible from at least some point of the cell", looking all 360°. Frustum culling happens in the frame, by the current field of view: it removes what is behind you and outside the angle. The BSP supplies the draw order and doubles for collision. It is a cascade: a cheap coarse filter (PVS) → an exact per-frame one (frustum) → sorting (BSP). Each removes its share — which is why there are three of them, not one.

Why is the PVS "potentially" visible rather than "definitely"?

Exact visibility depends on the specific position and angle of the camera — it would have to be recomputed in the frame, which is exactly what precomputation eliminates. So visibility is stored from a whole cell and conservatively: the PVS may flag extra cells (extra draws are tolerable) but never misses something genuinely visible (a miss = a hole in the world). A safe over-approximation per region instead of an expensive exact one per point.

Doom uses a BSP too — what is the fundamental difference from Quake?

Dimensionality. Doom's BSP is 2D (it cuts the plan with lines); "3D" is imitated with per-sector floor and ceiling heights → no rooms over rooms, no camera pitch, textures stretched without perspective. Quake's BSP is 3D (it cuts the volume with arbitrary planes) → real volumes, free look up and down, perspective-correct textures. One data structure, but going from lines to planes changes the class of what is possible.

Why bake light if Doom already changed sector brightness "dynamically"?

Doom's per-sector brightness is one scalar over a flat region, essentially free. Quake's light is a gradient across a surface (soft shadows, falloff from lamps), and 1996 hardware could not compute that per pixel at runtime. Baking moves the computation offline in exchange for staticness: you can't move a lamp or a wall. A few dynamic lights (flashes) were added as a cheap additive layer over the baked result. The same baked-vs-realtime GI trade-off is alive today.

Why do perspective correction every 16 pixels rather than per pixel or once per span?

Per pixel, the division (FDIV, ~39 cycles) kills the speed. Once per long span, the affine error grows with the length and the depth range and the texture "swims". 16 pixels is the sweet spot: the error is invisible, the loop unrolls nicely, and the FDIV for the next 16 finishes exactly in parallel with the integer drawing of the current ones (the Pentium's paired pipes) → the division is effectively free. Mode 7 gets away with "once per line" only because depth is constant along a line.