1996, and everything changes
Doom (1993) was a magnificent illusion: a 2D map extruded upward, no rooms above rooms, no looking up. Quake, released by id Software in June 1996: John Carmack on the engine, Michael Abrash on the renderer: was actually 3D: arbitrary geometry, real pitch and roll, polygonal monsters, and it ran in software on a Pentium. It did this not with brute force but with three big precomputation ideas: carve the world (BSP), precompute what can see what (PVS), and precompute the light (lightmaps). The demo above uses the same philosophy at toy scale.
BSP · carve the world before anyone plays it
At compile time, the map's brushes are fed to a tool that recursively splits space with planes until every region is a convex leaf. The result is a binary tree: walk it from any camera position and you get all surfaces in perfect front-to-back order, and point-location ("which leaf am I in?") in a handful of plane tests. Rendering order, collision, and visibility all hang off this one structure.
PVS · never draw what you cannot see
The second tool, vis, spends minutes-to-hours answering one question for every leaf: which other leaves could ever be visible from anywhere inside it? The answers are stored as compressed bitfields. At runtime Quake finds your leaf, reads its Potentially Visible Set, and simply never touches the rest of the map: the corridor behind a wall costs nothing at all. This is why Quake levels are full of twists and door-jambs: every bend is a visibility firewall.
Lightmaps · light, painted in advance
Quake's third precomputation: the light tool traces every light source against every surface and stores the result in coarse per-surface grids: lightmaps, one luxel per 16 texels. At runtime a wall is its texture multiplied by its lightmap, composited once into a surface cache. Torch glow pooling on a floor cost exactly zero per frame. Dynamic events (a rocket's flash) just add a temporary term and re-composite the few surfaces they touch.
The little arena above does precisely this: its lights were traced once at page load and baked into the geometry: what changes per frame is only your muzzle flash.
The software renderer · spans, and a divide every 16 pixels
No GPU. Every pixel of a 320×200 (later 640×480) frame was produced by the CPU. The world pass built a global edge list and emitted non-overlapping horizontal spans: each screen pixel drawn exactly once, zero overdraw. And perspective-correct texture mapping needs a divide per pixel: too slow: so Abrash's inner loop did the true divide every 16th pixel and interpolated linearly between, an error nobody's eye can find.
QuakeWorld · the internet learns to feel instant
Original Quake trusted the server for everything: on a 200 ms modem you pressed forward and walked a fifth of a second later. QuakeWorld (December 1996) added client-side prediction: your machine simulates your own movement immediately, the server stays authoritative, and when its verdict arrives the client reconciles the difference. Every multiplayer shooter since is built on this bargain.
The famous magic number
For the record: the legendary fast inverse square root, with its 0x5F3759DF constant, ships three years later in Quake III Arena's code (its exact authorship is folklore of its own). Quake 1's speed came from the ideas above plus hand-scheduled Pentium assembly: Abrash pairing instructions so the U and V pipes never stalled.