20 Rendering: BSP Traversal

This tour covers BSP traversal in the renderer, showing how the engine processes walls in front-to-back order through segment management and BSP tree traversal.

Next, we’ll look at how the renderer prepares for BSP traversal by resetting its segment tracking state.

// R_ClearClipSegs and R_ClearDrawSegs reset their respective segment lists before rendering.
// R_RenderBSPNode performs recursive traversal of the BSP tree.
File: linuxdoom-1.10/r_bsp.h (lines 59–64)

// drawsegs stores wall segments waiting to be rendered, with ds_p tracking the current position in the array.
File: linuxdoom-1.10/r_bsp.c (lines 53–54)

// Resets ds_p to clear all wall segments.
File: linuxdoom-1.10/r_bsp.c (lines 68–71)

// Sets up boundary values in solidsegs to mark the edges of the view area.
File: linuxdoom-1.10/r_bsp.c (lines 243–251)

// `NF_SUBSECTOR` is a bit mask used to identify subsector leaf nodes in the BSP tree.
File: linuxdoom-1.10/doomdata.h (lines 177–178)

// The NF_SUBSECTOR bit in bspnum indicates this is a leaf node containing geometry to render.
File: linuxdoom-1.10/r_bsp.c (lines 552–561)

// Traverses the BSP tree by first processing the subtree containing the viewpoint,
// then optionally the back subtree if visible.
File: linuxdoom-1.10/r_bsp.c (lines 567–578)

Next we’ll look at three global flags in r_segs.c - segtextured, markfloor, and markceiling - which control wall segment and plane processing.

// These flags track whether wall segments have visible textures and whether
// floor/ceiling planes need to be marked for rendering.
File: linuxdoom-1.10/r_segs.c (lines 45–50)

The segtextured flag controls texture calculations. When true, the renderer computes the view angle and texture column offset to determine which slice of the wall texture to draw.

// When `segtextured` is true, the code computes the texture column by combining
// view angles, adjusting for distance, and converting to integer pixel coordinates.
File: linuxdoom-1.10/r_segs.c (lines 262–267)

The markfloor flag determines if floor plane spans should be added to the rendering queue. When true, R_CheckPlane registers floor spans for later drawing.

// When `markfloor` is true, `R_CheckPlane` updates the floor plane spans from `rw_x` to `rw_stopx-1`.
File: linuxdoom-1.10/r_segs.c (lines 711–712)

The markceiling flag(708) controls whether ceiling planes are processed. When true, R_CheckPlane(709) adds the ceiling plane to the rendering queue.

// When `markceiling` is true, `R_CheckPlane` updates the ceiling plane span from `rw_x` to `rw_stopx-1`.
File: linuxdoom-1.10/r_segs.c (lines 708–709)

And that’s it! You now understand how DOOM’s renderer traverses the BSP tree to process walls, floors, and ceilings in the correct back-to-front order.