Hacking Doom code for Spino transparent LED POV display

Doom (the original version), is not only one of the best game ever made, but it's also a great example of C code.

Thanks to id Software decision to release the code as open source in 1999, anybody can have a look and modify it.

I had this project of changing the rendering of doom, to add a border effect to the walls, or cel shading. You can check the video at the end of this post to see why I wanted to do this to start with.

This idea of the cel shading algorithm (as described in the Wikipedia page ) is simple: we apply a Sobel filter to both the depth and normal buffers of the rendered frame, that we then superpose to the colors.

(Image from wikipedia)

I used the excellent chocolate-doom port of Doom, since this is the closest to the original I could find, and it compiles nicely.

My goal is to create my own buffers for depth and normals, and hook a function to fill them inside the rendering code, then just before the final blit, to call an other function to perform the Sobel filter and applying to the final image.

Here is what it will looks like:

Before

-- Before. --

After

-- After. --

The difficulty when looking at doom source is that most of the functions have side effects modifying global variables. I have to admit it is a bit ugly, and I suspect that this was an optimization to avoid useless copies into the stack.

Neither the less, the code is easy to follow, as there is almost no abstractions and indirections. Clearly, John Carmack is an adept of the New Jersey style of programming.

I came up with this simplified function call tree for the rendering algorithm:

R_RenderBSPNode
    R_Subsector // For each visible subsector
        R_FindPlane
        R_AddSprites  // Fill the vissprites list
        R_AddLine     // For each wall (front to back)
            R_ClipSolidWallSegment
                R_StoreWallRange(start, stop)
                    R_CheckPlane
                    R_RenderSegLoop
                        R_DrawColumn    // What I am looking for
R_DrawPlanes  // Render ceiling and floor.
R_DrawMasked

What they call 'line' is really a wall surface. The reason it is a 'line' is because from a logical point of view, doom walls are just 2d lines extruded vertically (they never have slopes).

As we would expect, the walls are rendered front to back (function R_AddLine). To prevent rendering on top of previous walls, the code keeps an array of up to 32 ranges ( struct cliprange) of already rendered walls. Since the front to back order is guarantied, there is no need for an actual depth buffer.

In my case, what I am looking for is the function R_DrawColumn, that ultimately renders a column of pixels from a sprite. It is used for both the walls and the sprites.

Before the function is called, some global variables are set:

dc_x:            x position.
dc_yl:           Start y position.
dc_yh:           End y position.
dc_iscale:       Texture scale (i.e: view distance).
rw_normalangle:  Normal of the surface angle.

Those are all I need to maintain the depth and a normal buffers. In R_DrawColum, I add a call to my own function spoom_AddColumn, that fills some pre-allocated buffers:

void spoom_AddColumn(int x, int y1, int y2, int z, int a)
{
    double angle = M_PI * a / ANG180;
    int y;
    for (y = y1; y < y2; y++) {
        depthBuffer[y * WIDTH + x] = (double)z / ((uint64_t)1 << 16);
        normBuffer[0][y * WIDTH + x] = cos(angle);
        normBuffer[1][y * WIDTH + x] = sin(angle);
    }
}

(Note that at the time when doom was release, such unoptimized code would kill the performances of the game. Fortunately this is of no concern for my needs).

Now that my buffers are filled, I just need to process them with a Sobel filter at each frame, and use the result to add the borders on top of the color buffer. I do it in a single function:

// Screen point to the color buffer.
void spoom_Apply(byte *screen)
{
    int i, k;
    gaussianBlur(depthBuffer, tmpBuffers[0]);
    sobel(depthBuffer, tmpBuffers);
    gaussianBlur(normBuffer[0], tmpBuffers[0]);
    sobel(normBuffer[0], tmpBuffers);
    gaussianBlur(normBuffer[1], tmpBuffers[0]);
    sobel(normBuffer[1], tmpBuffers);
    for (i = 0; i < WIDTH * HEIGHT; i++) {
        if (    depthBuffer[i] > 1.0 ||
                normBuffer[0][i] > 0.5 ||
                normBuffer[1][i] > 0.5) {
            screen[i] = 0;
        }
    }
}

The Sobel and Gaussian filters are implemented with a convolution product:

static void convolve(const double *m, const double *kern, double *dst)
{
    int i, j, i2, j2;
    double v;
    for (i = 1; i < HEIGHT - 1; i++)
    for (j = 1; j < WIDTH - 1; j++) {
        v = 0;
        for (i2 = -1; i2 <= 1; i2++)
        for (j2 = -1; j2 <= 1; j2++) {
            v += m[(i + i2) * WIDTH + j + j2] * kern[(i2 + 1) * 3 + j2 + 1];
        }
        dst[i * WIDTH + j] = v;
    }
}
static void gaussianBlur(double *m, double *tmp)
{
    const double kern[] = {
        1. / 16, 1. / 8, 1. / 16,
        1. /  8, 1. / 4, 1. / 8,
        1. / 16, 1. / 8, 1. / 16,
    };
    convolve(m, kern, tmp);
    convolve(tmp, kern, m);
}
static void sobel(double *m, double *tmp[2])
{
    int i;
    const double kernx[] = {-1. / 1,  0. / 1,  1. / 1,
                            -2. / 1,  0. / 1,  2. / 1,
                            -1. / 1,  0. / 1,  1. / 1};
    const double kerny[] = {-1. / 1, -2. / 1, -1. / 1,
                             0. / 1,  0. / 1,  0. / 1,
                             1. / 1,  2. / 1,  1. / 1};
    convolve(m, kernx, tmp[0]);
    convolve(m, kerny, tmp[1]);
    for (i = 0; i < WIDTH * HEIGHT; i++)
        m[i] = sqrt(tmp[0][i] * tmp[0][i] + tmp[1][i] * tmp[1][i]);
}

Finally, here is the final result, of me playing doom on a LED POV display. The walls are much easier to see compared to the unmodified game.