The Visplane Problem

When Wolfenstein 3D was released in 1992, it was a technological marvel, but it was geometrically simple. All walls were 90 degrees. All floors were flat. It was essentially a 2D grid ray-casted into 3D. For his next engine, Doom, John Carmack wanted more. He wanted walls at any angle. He wanted varying floor heights (stairs). He wanted brightness differences.

But this introduced a massive problem: Visibility. In a complex 3D world, how do you know which wall is in front of which?

• Painter’s Algorithm: Draw back-to-front. Too slow (lots of overdraw).
• Z-Buffer: Check depth per pixel. Too slow for 1993 hardware (and required too much RAM).

Carmack found the answer in a 1980 academic paper: Binary Space Partitioning (BSP).

The Tree of Walls

The core idea of the Doom engine is that the map is static. The walls don’t move. Because they are static, we can pre-calculate their relationship to each other.

A tool called the “Node Builder” (like BSP or Zennode) takes the level data and slices it.

1. Pick a wall (a partition line).
2. Everything on the “front” side goes into Child A.
3. Everything on the “back” side goes into Child B.
4. If a wall crosses the line, split the wall in two.
5. Repeat recursively until you are left with convex bucket of space called a Subsector.

This creates a binary tree. The beauty of this tree is that if you traverse it relative to the player’s position, you can get a list of all walls sorted perfectly from Front-to-Back (or Back-to-Front).

Rendering: Zero Overdraw

Doom renders Front-to-Back. This seems counter-intuitive (usually you draw background first), but it’s the key to speed.

The engine maintains a simple array representing the horizontal columns of the screen (0 to 319).

1. Walk the BSP tree to find the closest subsector.
2. Draw the visible parts of the walls in that subsector.
3. Mark those screen columns as “filled”.
4. Move to the next subsector.
5. If we try to draw a wall in a column that is already “filled”, skip it.

This means the engine never calculates a pixel that isn’t seen. It stops exactly when the screen is full.

Code Concept: Walking the BSP

The traversal is a simple recursive function. The genius is deciding which child to visit first.

// Pseudo-code for Doom BSP Traversal
struct Node {
    int x, y, dx, dy; // Partition line
    Node* frontChild;
    Node* backChild;
};

void R_RenderBSPNode(Node* node) {
    // 1. Determine which side of the partition line the camera is on
    // This is a simple 2D dot product check
    bool isFront = CheckPointOnSide(camera_x, camera_y, node);
    
    if (isFront) {
        // If we are in front, we see the front child first
        R_RenderBSPNode(node->frontChild);
        R_RenderBSPNode(node->backChild);
    } else {
        // If we are behind, we see the back child first
        R_RenderBSPNode(node->backChild);
        R_RenderBSPNode(node->frontChild);
    }
}

Note: In the actual engine, the recursion stops when it hits a “Subsector” (leaf), which contains the actual wall segments (Segs) to draw.

The Hall of Mirrors Effect

This BSP structure explains the famous “Hall of Mirrors” glitch. If the player manages to “noclip” outside the map, the BSP traversal breaks. The engine is in a “void” space that isn’t in any subsector. It doesn’t know what to draw. Since the “filled columns” array never gets set, the engine assumes nothing has been drawn. It doesn’t clear the screen (for performance). So the previous frame’s pixels remain, and whatever new pixels are drawn get smeared over them endlessly.

Limits of the BSP

The BSP system is why Doom maps couldn’t have “room over room” (multistory buildings). The 2D partition lines work on a flat plane. It’s also why Doom levels were static. You couldn’t rotate a wall because that would invalidate the entire pre-calculated tree. Moving doors/lifts were handled as special “sectors” that changed height but didn’t move horizontally.

Despite these limits, the BSP tree was the breakthrough that allowed PC gaming to jump from the grid-world of Wolfenstein to the organic, complex architecture of Doom, running at 35 FPS on a 486.