One level, one 386, and a renderer with no sort step anywhere in it. A Doom frame is assembled from two compile-time arrays, drawseg_t drawsegs[MAXDRAWSEGS] and visplane_t visplanes[MAXVISPLANES], filled by a walk over a tree that was computed before the level ever ran [1][2].

The tree is the celebrated part. The part that shaped the maps is the second half of that sentence: both arrays have a ceiling, and the ceiling is enforced by I_Error, so a level that exceeds it does not lose detail, it stops.

The wall

Painter’s order is the obvious answer to drawing a 3D world: sort the surfaces back to front, draw them one over another, and let the nearer ones overwrite the farther ones. It is correct, and it costs a sort of everything visible, every frame, at thirty five frames a second. On the hardware Doom was built for, that is not affordable.

So the renderer could not start a frame by asking which polygons were visible, because answering that question was the expensive part. It could not sort its way to a correct picture either, since sorting is the thing being avoided. The geometry gave it nothing to lean on: a Doom map is 2D, linedefs with sidedefs and sectors for floors and ceilings, and when the BSP splits a linedef the pieces become segs [1].

The wall, then, is ordering. Visibility had to be known before the frame began, from data prepared when the level was built, and the storage for that answer had to be a fixed block of memory.

The move

Split the map once, off the frame budget.

The level is clipped recursively with splitters until every leaf is convex, and each leaf is a subsector_t holding a sector and a slice of segs [1]. The viewpoint sits in one leaf of that partition at a time, and each node on the way down is a decision about which side of a line it is on. Walking from the root, the renderer only descends branches the tree says can be shown, so whole regions of the map are skipped rather than tested [1].

The alternative that lost is a per-frame sort, which is where the wall came from. The second decision is arithmetic: the projection does not use floating point. It runs on fixed_t, an integer carrying a fractional part.

#define FRACBITS 16
#define FRACUNIT (1<<FRACBITS)
typedef int fixed_t;

Sixteen fractional bits, so the maths is integer arithmetic end to end [3].

The drawing unit follows. Doom does not draw polygons; it emits vertical columns, and the height of each column comes from that fixed-point projection. A wall in view becomes a run of columns, and a floor becomes two per-column heights in a visplane [1].

The structures

A leaf holds no geometry, only a reference into a flat array:

typedef struct subsector_s {
    sector_t* sector;
    short numlines;
    short firstline;
} subsector_t;

One pointer and two shorts. firstline and numlines name a contiguous slice of the global seg array, so leaves can be stored compactly and nothing is duplicated between them [1].

The segs in those slices are the split edges:

typedef struct {
    vertex_t* v1;
    vertex_t* v2;
    fixed_t offset;
    angle_t angle;
    side_t* sidedef;
    line_t* linedef;
    sector_t* frontsector;
    sector_t* backsector;
} seg_t;

Both endpoints, an offset and an angle, the sidedef it belongs to, the linedef it was cut from, and the two sectors on either side [1]. The sector pair travels on the seg rather than being looked up at draw time.

Two more structures do the drawing work, and neither is a polygon in any recognisable sense.

A drawseg_t caches a projected wall so that sprites and masked textures can be clipped against it later. It carries x1, x2, scale1, scale2, scalestep, silhouette, bsilheight, tsilheight, plus three clip arrays [1]. The wall is remembered in screen space, after projection, in the form the next passes need.

A visplane_t holds height, picnum, lightlevel, minx, maxx, top[SCREENWIDTH], bottom[SCREENWIDTH] [1]. A floor or a ceiling is not a polygon either. It is a texture, a light level, and two arrays of per-column heights, one screen column at a time.

The budgets

Both arrays are sized at compile time. R_ClearDrawSegs sets ds_p = drawsegs, putting the write pointer back at the front of the buffer, so 256 is a per-frame budget rather than a per-level one [1]. The visplanes are a plain visplane_t visplanes[MAXVISPLANES] [2].

ResourceDeclaredCeilingMessage when exceeded
Drawsegs#define MAXDRAWSEGS 256256 per frameR_DrawPlanes: drawsegs overflow (%i)
Visplanes#define MAXVISPLANES 128128R_DrawPlanes: visplane overflow (%i)
A new visplane lookupR_FindPlane128R_FindPlane: no more visplanes

The enforcement is three calls, all fatal:

r_plane.c:246   I_Error ("R_FindPlane: no more visplanes");
r_plane.c:377   I_Error ("R_DrawPlanes: drawsegs overflow (%i)", ...);
r_plane.c:381   I_Error ("R_DrawPlanes: visplane overflow (%i)", ...);

All three live in r_plane.c, which is the plane pass, including the one about drawsegs, which is a wall structure [2].

There is no partial rendering path here. A renderer that expects to run out of room keeps a fallback: it drops a frame, or it draws less detail. Doom’s answer is to name the resource and abort.

The shadow

The bill went to level design.

128 visplanes is 128 floor and ceiling surfaces that can be visible in one frame, each carrying its own height, texture and light level [1]. A mapper who wanted one more lit patch of floor, one more step in a staircase descending into view, one more texture change in a corridor that turns, was spending from a budget with nothing to raise. When the count runs out, R_FindPlane does not return a degraded surface: it prints no more visplanes and the game ends [2]. The same for 256 drawsegs, since a sightline down a long hall is a count of wall segments, and a level that puts one more segment in view crashes. That is why utilities to count visplanes existed.

The tradeoff is legible in one comparison. A modern renderer treats its budget as elastic: it drops a frame, or lowers a detail setting, and the player sees a hitch rather than a message. Doom treated its budget as a specification, enforced at runtime, and pushed the compliance work upstream into the map. In exchange, the frame path works inside two arrays of known size, and the only code that handles running out of room is three I_Error calls.

References

[1] id Software, DOOM, linuxdoom-1.10/r_defs.h for subsector_t, seg_t, drawseg_t, visplane_t, #define MAXDRAWSEGS 256 and drawseg_t drawsegs[MAXDRAWSEGS]; r_bsp.c for ds_p = drawsegs in R_ClearDrawSegs. https://github.com/id-Software/DOOM/blob/master/linuxdoom-1.10/r_defs.h

[2] id Software, linuxdoom-1.10/r_plane.c for #define MAXVISPLANES 128, visplane_t visplanes[MAXVISPLANES], and the I_Error calls at lines 246, 377 and 381. https://github.com/id-Software/DOOM/blob/master/linuxdoom-1.10/r_plane.c

[3] id Software, linuxdoom-1.10/m_fixed.h for #define FRACBITS 16, #define FRACUNIT (1<<FRACBITS) and typedef int fixed_t. https://github.com/id-Software/DOOM/blob/master/linuxdoom-1.10/m_fixed.h