Doom solved draw order with somebody else's 1980 paper, and paid for it in level architecture

The problem that had to be solved by December 1993 sounds dull and determines everything else: in what order do you draw walls so that near ones hide far ones.

The obvious method is a depth buffer, storing a distance for every point on screen. On machines of that era this meant an extra megabyte of memory and a comparison for every pixel drawn; neither was available. The second method is the painter's algorithm: sort polygons by distance and draw far to near. It requires sorting every frame, and worse, it does not always work: three walls can overlap in a cycle, and no correct order exists for them at all.

Wolfenstein 3D in 1992 sidestepped the problem entirely: the world was a grid of identical cubes and the engine cast one ray per screen column. Ordering on a grid is trivial. But on a grid you cannot place a wall at an angle.

What Carmack took

Doom's levels are arbitrary polygons at arbitrary angles. For those Carmack applied binary space partitioning, described in 1980 in a paper by Henry Fuchs, Zvi Kedem and Bruce Naylor.

The idea takes three sentences. Take a wall and extend its line to infinity: it divides the level into in front and behind. Repeat recursively for each half, splitting any wall that lands on the line. The leaves of the tree are convex regions inside which nothing can occlude anything.

At run time no sorting is needed at all. For any camera position the engine descends the tree, at each node taking first the side the player is on. The order is correct by construction.

Carmack did not make the sort faster. He moved it out of play time and into map compile time.

What the speed cost

The tree is built once, when the level is assembled in the editor, and that takes seconds to minutes. It describes the geometry permanently.

From which follows the thing you recognise about Doom at a glance. A door can rise, a floor can drop, a platform can travel upward — all of that changes heights but not the plan. No wall in Doom rotates or slides horizontally, because that would invalidate the tree, and rebuilding it on the fly is not possible. The game's architectural style, a static plan with vertically moving floors and doors, is not an artistic decision but a direct consequence of a data structure.

To this the engine adds a second economy: it walks the tree from near to far and keeps a list of screen columns already covered. Once a column is closed, everything behind it is skipped without processing. Doom almost never draws the same pixel twice, a rarity for its time.

The general rule

Doom shipped on 10 December 1993 and became the first widely known example of the trade that has defined graphics ever since: move work out of run time and into build time. The same line runs through baked lightmaps, precomputed visibility in Quake, baked global illumination and today's bounding volume hierarchies for ray tracing. It is one bargain repeated.

So the useful question to ask of any handsome effect is not what it costs per frame, but what was computed before the player pressed start. And then a second question, whose answer is usually the real price: what can no longer be moved because of it.