Blog

The Force Engine development news and updates.

Upcoming DF Classic Renderer Release

This post concerns the next major test release, the DF Classic Renderer Release. There may be smaller releases in the meantime, such as bug fixes or quality of life improvements.

Classic Renderer

The “Classic Renderer” is the Dos-Dark Forces derived Jedi Engine renderer. This covers the rendering in the 3D view - purely 2D rendering such as UI is basically done except for a few bugs. This renderer involves several key components: walls with overlays (such as switches or signs), flats (floors and ceilings), mask walls (walls with transparent elements such as fences or force fields), sprites and 3D models - with proper light attenuation in different situations.

For a more thorough description of the DOS renderer itself see the work in progress Dark Forces (DOS) Rendering series starting with Dark Forces (DOS) Rendering, Part I. I will probably post Part 2 within a week or so.

DF Classic Renderer Release

The current renderer in the test release is not complete and not fully accurate - there are several issues such as sorting issues with sprites versus walls in a few cases and incorrect sorting with 3D objects versus sprites and walls in general. There are also some issues with wall rendering in some mods - such as “Prelude to Harkov`s Defection” (see the tram/subway). Finally the light falloff is not quite correct (though it is close in many levels), which is probably most obvious in Gromas Mines - the fog effect does not match the original very well in some areas.

As the reverse-engineering of the original DOS renderer nears completion, The Force Engine code is being updated and the code refactored. The ultimate goal of this release is to complete the Classic (DF) Renderer and ensure that it is functionally identical to the Dos version in 320x200. As I have been working, when I identify look-up tables I spend the time to make sure I understand how to accurately re-build the tables - with this knowledge I can remove the tables entirely when appropriate in order to support higher resolutions without sacrificing accuracy.

While refactoring the renderer code I plan on implementing a few non-DOS based features:

  • Widescreen support.
  • “Window-Resolution” option that changes the virtual resolution to match window size and aspect ratio.
  • Improved software renderer performance.
  • [Maybe] Classic Hardware Renderer.

Note that after the gameplay is more complete there will be another big renderer release before the project beta release in November that will feature the “Perspective Renderer”, more hardware support and Outlaws Jedi Engine enhancements (such as slopes, double adjoins, vertical adjoins, etc.). The goal of this release is renderer accuracy so that all levels and mods are rendered correctly and visually match the DOS version at 320x200.

Next Steps

Once the DF Classic Renderer Release is finalized, the next steps are to focus on gameplay elements - fully accurate collision detection and player movement, AI and weapons. These will be broken down into major test releases, in a similar manner as the DF Classic Renderer.

Add Comment

Dark Forces (DOS) Rendering, Part I

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

First Post

This is my first “real” post on this blog. Several years ago there was a project called the “XL Engine” which evolved from DarkXL with lofty ambitions. I personally hit some difficult times but never properly canceled the project, even if I couldn’t get back to it for a long time and didn’t really want to for a long time after that. Fast forward to today, things are much better now with more free time but time moves on and the XL Engine isn’t really necessary anymore - both Daggerfall and Blood have great projects that fill the niche the XL Engine wanted to fill (or close enough).

But the Jedi Engine never had a proper source release or reverse engineering effort. While many considered DarkXL to be a promising effort, it was incomplete and inaccurate in many ways. Ultimately the methods used to reproduce the game could never be 100% faithful in the ways that matter. And so The Force Engine was concieved as a complete re-write, rebuilt from the ground up with the following tenets:

  • Support all Jedi based games - Dark Forces and Outlaws.
  • Source-level accuracy by reverse engineering the original executables.
  • Focus on making sure the core games are completely supported before adding effects on top like dynamic lighting, this means starting with the software renderer just like the originals.
  • Open sourcing the project the moment it goes public.
  • Cross platform support (though admittadly this last area still needs a lot of work before the first release).

While the GitHub repository has been made public, The Force Engine has not been officially announced and no release has been made. It will be some time before that happens (see the Roadmap).

Add Comment