Dark Forces (DOS) Rendering, Part I

16 May 2020

I have been reverse engineering the Dark Forces executable in order to figure out how it works, exactly, so that The Force Engine can truly be “source port” accurate. Figuring out how the AI works, player movement, collision detection, etc. is very important but this series of posts will start with rendering. These posts will talk about how Dark Forces rendering works in DOS and how the “Classic” Software Renderer works in the Force Engine (or will work as more work needs to be done there). Note that I will be showing some code snippets, these are directly from the reverse engineered work and represent what is actually happening in Dark Forces. However I obviously won’t be showing all of the code here and instead just snippets as needed.

Fixed Point

Back when Dark Forces was developed, floating point processors were generally not available. So, like most 3D games of the time such as Doom, they used “fixed point” instead. The concept is pretty simple but I will not go into too much detail here. Basically a fixed number of bits are assigned to store the fractional part of the number and the remainder are used for the sign (1 bit) and integer part. Dark Forces used 16.16 for most of fixed point numbers (or 1.15.16 if you want to call out the sign bit). In this scheme 1.0 = 65536 (0x10000) and 0.5 = 32768 (0x8000), which are the HALF_16 and ONE_16 constants used in the code.

Adding and subtracting works as you would expect (ignoring possible overflow) but multiplication and division can be problematic. In Dark Forces, they essentially upcast the values to 64 bit, do the operation and then use the lower 32 bits of the result. You will see functions such as mul16(), div16(), round16(), floor16(), etc. that handle these details in the explanations.

Camera

The Player has 3D position in the world - an (x, y, z) coordinate where (x,z) represent their position on the floor, as if seen from above (or a map view) and (y) is the height. In Dark Forces negative (y) is going up and positive (y) is going down. To convert to camera coordinates the (x,z) value is left as-is and the (y) value is offset by the eye-height, which is about -5.8 DFU when standing (Dark Forces Units, ~1 foot, though some estimates put it closer to 25cm). For the curious, the exact value is -380108 / 65536.

vec3 camPos = { player.x, player.y - eyeHeight, player.z };

The Player also has pitch, yaw and roll angles in order to orient the view. For Dark Forces only yaw and pitch are used for the camera, though 3D models (3DOs) can be fully oriented using all 3 angles.

From this several values are computed, the equivalent of a matrix:
cosYaw, sinYaw, negSinYaw
xTranslation, zTranslation

Cosine and Sine are computed using a 4096 entry table and with transformations to handle each quadrant and phase shifting one table handles both sine and cosine. Note that the precision is equivalent to a 16k entry table. Translations are computed thusly:

zTranslation = mul16(-camPos.z, cosYaw) + mul16(-camPos.x, negSinYaw);
xTranslation = mul16(-camPos.x, cosYaw) + mul16(-camPos.z, sinYaw);

Sectors & Walls

Drawing starts in the current player sector, processing each sector as they are seen through portals (“adjoins”). Each time a portal is traversed, “window coordinates” are tracked that clip the view to the current portal. To start with, those window coordinates exactly cover the full view. We start by processing these walls - which includes culling, projection and preparing for rendering, which will be the focus of the rest of this post. Details such as merging and sorting, drawing columns, drawing floors and ceilings, traversing portals, drawing sprites and models will be handled in future posts.

Each sector keeps track of the last frame it has been used. By using this, the engine only transforms its vertices and processes its walls - converting them to renderable segments once per frame. The first time a sector is encountered, the first step is to transform all of its vertices from world space to viewspace:

vec2* vtxWS = curSector->verticesWS;
vec2* vtxVS = curSector->verticesVS;
for (s32 w = curSector->vertexCount - 1; w >= 0; w--)
{
vtxVS->x = mul16(vtxWS->x, cosYaw) + mul16(vtxWS->z, sinYaw) + xTranslation;
vtxVS->z = mul16(vtxWS->x, negSinYaw) + mul16(vtxWS->z, cosYaw) + zTranslation;
vtxVS++;
vtxWS++;
}

Note that the vertices are “2D” - the (y) coordinates, which map to the heights on screen, are computed later by projecting the floor and ceiling heights. It is still fair to say that the Jedi Engine, like the Doom Engine, is 3D since the third dimension is accounted for in the varying floor and ceiling heights.

Culling

Next we must loop through every wall in the sector and process them. In Dark Forces this is what the Wall_Process() function is for. Dark Forces uses a 90 degree horizontal field of view. As a result, we can think of the top down, 2D frustum as consisting of two 45 degree right triangles. What this means is that for a given ‘depth’ (z value), the left clipping plane passes through x = -z and the right clipping plane passes through x = +z. Or to put it a different way, given a point (x,z) in viewspace - we know that if x < -z it is outside the left side of the screen and if x > +z it is outside the right side of the screen.

At this point the wall being processed consists of two view space coordinates (x0,z0) and (x1,z1). First Wall_Process() culls the wall if it is completely behind the camera and then culls it if both vertices are outside the left plane or both vertices are outside the right plane.

if (z0 < 0 && z1 < 0)
{
wall->visible = 0;
return;
}
if ((x0 < -z0 && x1 < -z1) || (x0 > z0 && x1 > z1))
{
wall->visible = 0;
return;
}

Next, Wall_Process() determines if the wall is front facing. That is if the camera is looking at the front or back of the wall. We can determine which side of a wall we are on by taking the cross-product. However, the original programmer didn’t quite finish simplifying the equation, so did something equivalent but slightly more complicated. This actually simplifies to a cross-product, so it is mathematically equivalent and gets the job done.

s32 dz = z1 - z0;
s32 dx = x1 - x0;
s32 side = mul16(z0, dx) - mul16(x0, dz);
if (side < 0)
{
wall->visible = 0;
return;
}

Clipping

Now things get a little more complicated. I won’t post the code, there is a lot of it, but the next phase of the function is clipping the wall the view frustum and to the near plane. There are still a few interesting things to point out, though. First, whenever a wall changes in Dark Forces (i.e. the vertices are moved, such as in the case of rotating doors or moving sectors) - its length in texels is computed and stored. Dark Forces uses a consistent texel density - 8 texels per DFU. To put it simply:

wall->texelLength = mul16( length(x0, z0, x1, z1), intToFixed16(8) );
length in texels = length of wall * 8.0

Anyway when clipping lengthInTexels must be tracked, in addition to the starting texel offset after clipping (which is 0 if no clipping is required).

Projection

Once the wall is clipped to the view frustum, it is finally time to project it into screenspace. Note that we still don’t care about the wall height or camera pitch. For now we are still focusing on the x coodinates. First I will show the code and then explain it since it is pretty simple:

x0_screen = div16( mul16(x0, focalLength), z0 ) + halfWidth;
x1_screen = div16( mul16(x1, focalLength), z1 ) + halfWidth;
x0_pixel = round16(x0_screen);
x1_pixel = round16(x1_screen);

halfWidth is half of the width of the screen in pixels.
focalLength controls the horizontal field of view - it is basically tan(FOV/2) * halfWidth. Since FOV = 90, tan(45) = 1, so focalLength is actually the same value as halfWidth. But Dark Forces stores them as two seperate variables.

Finally round16() rounds the fixed point number and then converts it to an integer. Basically if the fractional part is less than 0.5, it rounds down otherwise it rounds up. The code is actually really simple:

s32 round16(s32 x) { return (x + HALF_16) >> 16; }

More Culling

Once the wall is projected, Dark Forces tries culling it again just to be sure.

First Backface culling. Since we know the orientation of the walls, we know that if x0 > x1 then we are looking at the backside of the wall:
if (x0_pixel > x1_pixel)
{
wall->visible = 0;
return;
}
Next we check if the wall is outside of the screen. Since we know the order of the x values, we can just see if the minimum value is to the right or the maximum value is to the left:
if (x0pixel > s_maxScreenX || x1pixel < s_minScreenX)
{
wall->visible = 0;
return;
}

Finally Dark Forces has a limit of 384 potentially visible walls. Fortunately each sector is only processed once and culled walls don’t count, so this limit isn’t as severe as it seems. Also note that only potentially visible sectors are processed in this way, so any invisible sector also doesn’t count towards this limit.
if (s_nextWall == MAX_SEG)
{
errorMessage(5, 20, "Wall_Process : Maximum processed walls exceeded!");
return;
}

Wall Segments

The walls themselves aren’t directly used for rendering. Instead processed walls are converted into “WallSegments.” The remainder of Wall_Process() handles creating a new segment which will be merged, clipped and sorted later during rendering.

Most elements are fairly straight forward, so I will just show the code:
wallSeg->srcWall = wall;
wallSeg->wallX0_raw = x0_pixel;
wallSeg->wallX1_raw = x1_pixel;
wallSeg->z0 = z0;
wallSeg->z1 = z1;
wallSeg->uCoord0 = curU;
wallSeg->wallX0 = x0_pixel;
wallSeg->wallX1 = x1_pixel;
wallSeg->x0View = x0;

Like I said, this is mostly straight forward. As WallSegments are processed, they are merged and clipped against existing segments and against the current window (or portal). This means that the projected (x) values are clamped during this process. To compute proper per-column depth (z) and texture coordinates, we have to keep around the ‘raw’ - or unclipped version of the coordinate (or no additional clipping anyway).

Next, remember in the clipping section when I mentioned we have to keep track of the starting ‘u’ texture coordinate after clipping? That is stored in uCoord0. If the renderer didn’t track this then the texture would swim as the wall went off screen. Finally we also save the view space x coordinate, this will be useful later for calculating per-column depth and u coordinate.

In the next step we have to compute two more values used to compute per-column depth (z) and texture coodinates - the slope of the wall and the texture scaling factor. We only have 16 bits of fractional precision available and we have to deal with purely horizontal or vertical walls (when viewed from top down) - so this complicates this part.

dx = x1 - x0;
dz = z1 - z0;
s32 slope, den;
if (abs(dx) > abs(dz))
{
slope = div16(dz, dx);
den = dx;
}
else
{
slope = div16(dx, dz);
den = dz;
}
wallSeg->slope = slope;
wallSeg->uScale = div16(texelLengthRem, den);

abs(x) = Absolute Value of x
Notice that we compute abs(dx) and abs(dz) (where dx = x1 - x0 and dz = z1 - z0) and use the larger value as the denominator in the slope. How does that help us? Let’s assume that abs(dx) > abs(dz):

Assume we want to compute the depth (z) at any point (x) along the WallSegment. We know that z(x0) = z0 and z(x1) = z1. So:
z(x) = z0 + (x - x0)*dx/dz => z(x) = z0 + (x - x0)*slope

Adding the WallSegment

So we have created a WallSegment, ready to be rendered. What next? First we have a list of “source segements” - again only computed once per frame for each potentially visible sector. So this segment is simply added to that list:

WallSegment* wallSeg = &s_wallSegListSrc[s_nextWall];
s_nextWall++;

Conclusion

Now we leave the Wall_Process() and continue to draw the wall. In Part 2 I will go over the merge/sort/clip process so we can start drawing the visible parts of the WallSegments!

Add Comment