Source Project - Doom

Introduction

During the course of the glDoom project, it was necessary to take the 2D Doom level data and convert it into 3D polygons for rendering using OpenGL. This process which seems relatively simple on the face of it turned out to be fairly complex. The Doom engine imposed certain rules on the level design but left open some fairly large holes that can cause major problems when trying to devise an algorithm to reliably convert these levels to 3D. Chief among these was the fact that even though a linedef bordered two sectors, it did not have to have sidedefs for either of those sectors. This causes an open sector because not all the linedefs that define the sector can be assigned to that sector. Even though the sector is physically enclosed by the linedefs, we can't logically enclose it with sidedefs. And a sidedef is the only way that a linedef can be assigned to a sector.

Doom level construction

Those of you who aren't familiar with how the Doom engine works are probably wondering what I'm talking about. So I'll give a brief description of how a Doom level is constructed.

The smallest unit for describing a Doom level is the vertex. Each vertex is two coordinates (X and Y) that defines a position in 2D space basically North/South for Y and East/West for X. There is no height above ground included in these vertices. That comes later.

Wall segments in Doom are built from two things, linedefs and sidedefs. The linedef defines a line segment which stretches between two vertices and also has some flags that tell the game engine if the linedef can trigger some action in the game. The second part of the wall segment is the sidedef. Each linedef can have two sidedefs, one for each side of the line. Each sidedef contains the definitions for what textures should be displayed on the upper, middle and lower wall sections for that side of the linedef. The sidedef is also what binds the linedef to a specific sector. "Why is that important?", you ask. Read on.

Since Doom vertices don't have any height or elevation information stored in them, how do we get a 3D level? Well, the height part is spread out over an entire area of the level called a sector. The sector is what determines the height of the floor and ceiling of each area of the level. The sector also defines what textures to use when drawing the floor and ceiling or if it should be sky instead. So, using the X and Y coordinates from the linedef and the Z coordinate from the sector, we can build a 3D representation of the level. Individual sectors can also have line tags that link the sector to linedefs that can trigger game actions like doors, lifts, crushing ceilings, changes in lighting and rising staircases.

If you've noticed that Doom levels always have vertical walls and flat floors and ceilings (no ramps or slanted walls), then you now understand why they cannot be slanted or tilted. A linedef only has two vertices which define position in 2D space. The walls are just extrusions into a third dimension (height) using the associated sector's floor and ceiling height to determine the top and bottom of the wall. Upper walls are the exposed edge of a lower ceiling and lower walls are the exposed edge of higher floor. These are calculated by the differences in the heights between the two sectors that a linedef separates. The two sidedefs of the linedef are what tell us which sector each side of the line belongs to.

We also use the linedefs enclosing a sector to tell us where the floors and ceilings for a sector begin and end. If a linedef is assigned to a different sector than the one that it encloses (for whatever reason), that linedef cannot be properly used to define the sector edges. Nor can we accurately tell where the top and bottom of that wall are. This complicates both the drawing of the floor and ceiling for that sector as well as determining how to draw the walls.

The Doom engine coped with these problems relatively well because it is a span renderer (vertical and horizontal) and only drew the floors and ceilings after all the walls had been drawn. Some of these errors are still visible with the original game engine, though. More so with the walls than with floors and ceilings which are drawn to fill in the gaps between the walls.

Converting it to polygons

Converting Doom levels to 3D polygons takes a little ingenuity but we can get there without too much difficulty. The first thing we will tackle is the creation of walls then we'll step up to creating the floors and ceilings.

But first we need to change the coordinate system. Doom uses Cartesion coordinates for the vertices which is just fine for a plan view of a house (the overhead view) but which won't work well with a 3D renderer. So we need to add a third coordinate to each vertex. The X coordinate of the vertex defning East/West (left/right) position is just fine, we can use that like it is. But the Y coordinate in a 3D coordinate system defines height (up/down) not North/South(into and out of the screen) position. The Z coordinate in a 3D coordinate system defines North/South (into and out of the screen) and is the basis for whether we have a left handed or right handed coordinate system. So we will use the Doom Y coordinate for our Z coordinate and we will use the sector heights as the new Y coordinates. (two per sector)

One thing I had to take into account was the fact that each linedef has only 2 vertices. But it could actually need up to 8 depending on where adjoining sectors met. A single sidedef could have both an upper and a lower wall segment. It could also have a middle segment whether it had upper and lower segments or not. For the lower wall, we need 4 vertices to describe the wall. For the upper wall we also need 4 vertices. If we have both, that makes 8 vertices. Even if we have a middle wall, too, we still only need 8 vertices total. So each linedef will need between 0 and 8 vertices.

Now adjoining linedefs can share the vertices on one end of adjoining linedefs if they are the same height and if they are in the same sector(s) or neither of the sectors is movable. If the sidedefs are assigned to different sector(s), and the floor and/or ceiling of the different sectors are at different heights (statically or dynamically) then sharing the vertices is not possible. Since Doom has no moving lines the X and Y Doom level coordinates never change during the game. It is only the heights that can change so that is the only factor which limits vertex sharing. If the floor and ceiling heights match between the sectors and neither sector moves, we can share the vertices because they will never be at different heights. But if either moves, even if they start off at the same height, we cannot share them.

This can cause quite a jump in the number of vertices for a level. But keeping the old 2D vertices is just too impractical.

Building walls

To create a Doom wall, we first remember that all Doom walls are vertical and rectangular. So every wall segment can be drawn with just two triangles. This makes creating the walls almost trivial. To determine which wall segments to create and how to create them, we first have to look at how many sidedefs a linedef has.

A linedef that has only one sidedef does not separate two sectors but is the edge of a single sector. This tells is that there can be no upper or lower wall segments, only a middle wall segment. Also, this wall segment just goes from the floor to the ceiling of the sector the sidedef is assigned to. Fairly simple. My first attempt at
this looked at the static heights of the floor and ceiling and did not create a wall segment with zero height. But this is wrong. The floor or ceiling may move and create a space that isn't there in the static level definition. We still need the wall so we create it anyway. We will adjust the Y coordinates of the vertices while the game engine is running. (NOTE: If there is no texture named for the wall segment, we create it anyway and assign a default texture to it (aastinky or something).
The reason for this is that there must be a wall drawn there. Otherwise the player is looking outside the level.)

A linedef that has two sidedefs is a little more tricky. What we have to look at several factors before creating some of the wall segments. One of the rules for creating upper and lower walls is that we do not create them if the far sector (the sector opposite the sidedef for which we are creating the wall segment) has sky for the ceiling or floor respectively. There are couple of other rules to follow as well.

If the heights of the two sector floors are different we must create a lower wall segment even if no texture is defined for it. If no texture is defined it is a mistake on the part of the level designer. We need to try to fix it if possible. I did this by looking at wall definitions on linedefs that are part of the same "wall" and using the same texture they have. If I couldn't find one that way, I tried to use the upper or lower texture of the same wall segment if there was one. If it is not possible to determine the texture that way, I resorted to using a "default" texture for the wall. One of the other solutions worked 99% of the time though.

The same rule applies to upper segments with respect to the two ceiling heights.

Another rule is that we create wall segments for every place that has a texture definition, even if the sector heights are the same between the two sidedefs. (and even if the sector assignment of both sidedefs is the same) This is because the level designer probably put them there because one or both of the sectors moves up and
down or because the designer wanted a fake wall. (one you can walk through)

The next step, generating texture coordinates for the wall segments, is a little more complicated. OpenGL requires that all textures have dimensions that are powers of 2. They do not have to be square, though. So you can have a texture that is 4 by 1024 since both are powers of 2. 3Dfx threw a wrench in the works by adding two more restrictions. The first is that the ratio between the larger and smaller dimension of a texture could not be more than 8 to 1. The second is that the maximum length of either dimension is 256. Other 3D accelerator chip vendors that support OpenGL do not have this restriction. 3Dfx still does.

I mentioned this because of one the fact that not all of Doom's textures are powers of 2 in both dimensions. They are all multiples of 2 but not powers of 2. You can handle this problem one of two ways. You can pad out or truncate the textures, or you can stretch or compress them so they are a power of 2. Either way, you have to retain the value of the original size of each dimension in order to calculate the texture coordinates properly. I chose to pad out the textures to the next power of 2 in my implementation.

First you have to figure out what power of two is the next one. This is relatively easy to do. In 'C' it works like this.

int FixDimension(int dim)
   {
    int power, maxpower = 1024

    if (cl_3Dfx)
       {
        maxpower = 256
       }
    for (power = 1 power <= max_power power *= 2)
       {
        if (power >= dim)
           {
            return power
           }
       }
    return power // we truncate to 256 for 3Dfx
   }

byte *tex_PadWidth(int width, int height, int newwidth, byte *data, int Bpt)
   {
    // Bpp is bytes per texel not bits per texel
    int          y
    static byte *tempbuff = 0

    tempbuff = (byte *)realloc(tempbuff, newwidth*height*Bpt)
    for (y = 0 y < height y++)
       {
        memcpy(&tempbuff[y*newwidth], &data[y*width*Bpp], width*Bpt)
        memcpy(&tempbuff[(y*newwidth)+width], &data[y*width*Bpt], (newwidth-width)*Bpt)
       }
    return tempbuff
   }

byte *tex_PadHeight(int width, int height, int newheight, byte *data, int Bpt)
   {
    int          x
    static byte *tempbuff = 0

    tempbuff = (byte *)realloc(tempbuff, width*newheight*Bpt)
    memcpy(tempbuff, data, width*height*Bpt)
    for (x = height x < newheight x++)
       {
        memcpy(&tempbuff[x*width*Bpt], &data[((x-height)*width)*Bpt], width*Bpt)
       }
    return tempbuff
   }

The next thing we have to take into account when trying to come up with texture coordinates is the issue of pegging. There are two pegging flags in each sidedef. Lower unpegged and upper unpegged. These two flags can reverse the way a texture is drawn.

Some textures are drawn from the bottom up and some are drawn from the top down. A lower texture is normally drawn from the top down. An upper texture is normally drawn from the bottom up. A middle texture is normally drawn from the top down. "What effect does this have on texture coordinates", you ask. Quite a bit actually. Read on.

A normal middle texture in Doom is drawn from the top down. This means that the top of the wall texture is aligned with the top of the wall and is drawn down the wall (repeating the texture if necessary) until it reaches the bottom of the wall. If all you are doing it writing out texels in a vertical span, you just start at the top and keep drawing the same vertical span until you get to the bottom of the wall. But with a 3D renderer, you have to specify texture coordinates.

OpenGL expects texture coordinates on a rectangle to be 0,1 at the top left corner, 0,0 at the bottom left corner, 1,0 at the bottom right corner and 1,1 at the top right corner. The first texture coordinate is the horizontal. The second is the vertical.

For the horizontal coordinate, the value goes from 0 to 1 as you go from right to left with 0 being the left edge of the texture and 1 being the right edge of the texture. (not the polygon but the texture)

For the vertical coordinate, the value goes from 0 to 1 as you go from bottom to top with 0 being the bottom edge of the texture and 1 being the top edge of the texture. (not the polygon)

In Doom, the coordinate system was a 1 to 1 correspondence with texture dimensions (thankfully). So if you had a wall segment that was 128 high and 256 wide and you wanted to map a 128 by 128 texture onto it. The bottom left coordinate would be 0,0. The top left would be 0,1. The bottom right would be 2,0. And the top right would be 2,1. This is because the polygon is twice as wide as the texture so the texture will fit twice within the width of the wall.

Consider, though if the wall segment was 128 high and 64 wide and we wanted to map the same 128 by 128 texture onto it. Now, instead of 2,0 for the bottom right and 2,1 for the top right, we would have .5,0 for the bottom right and .5,1 for the to right. This is because only half the texture fits on the wall. Setting the left side of the coordinate to .5 and the right side to 1.0 would also work. We would then see the other half of the texture mapped to the wall.

But here we have 2 modifiers to our rule. The first is pegging which means we have to alter the way we calculate the texture coordinates if the wall isn't an exact multiple of the texture's vertical dimension. The second is called the "offset".

As an example of unpegging the middle texture, lets use a wall that is 96 units high with a texture that is 128 texels high. With the middle texture "pegged" (lower_unpegged == 0), the top left coordinate of the wall is 0,1. The bottom left coordinate is (128-96)/128 of the texture or 0,0.25 (one fourth of the way up). But with the middle texture "unpegged" we now start with a bottom left texture coordinate of 0,0 and we have to calculate the top coordinate based on what fraction of the texture fits on the wall. In this case we come up with 96/128 or .75, so our top left coordinate is 0,0.75.

There is one little problem with this though. Remember that we had to pad some of the textures out to the next power of 2. This isn't really a problem when it's in the horizontal plane since we only pad the right side and all textures are drawn left to right. But it does present a problem when we calculate vertical texture coordinates on textures that have been padded. Hmmm. How do we handle that?

The solution. Remember we kept the original dimensions of the texture (just for this purpose). So what we have to do is calculate where in the "logical" texture the actual texture starts. If we have a texture height of 96 padded out to 128, then the bottom of the real texture starts at .25 in the logical texture. So if our original texture height was 96 and we padded it to 128, we have to add .25 to all of our vertical texture calculations. We also calculate the primary part of the texture coordinate using the padded size of the texture not the original size. This is because we will be adding or pad_offset back to the result.

For example, we have a wall that is 64 high. We have a texture that was 96 high but padded to 128. It is unpegged so we draw it from the bottom up. In the original texture coordinates, the bottom coordinate would be 0.0 and the top would be .666. But we had to pad it on the bottom of the texture. So our bottom texture coordinate is 0.0 (normal) plus the pad_offset of .25 which yields 0.25. Our upper coordinate is 64/128 which is .5 plus the pad_offset of .25 which yields an upper coordinate of 0.75. Now we are displaying the texture from .25 to .75 of the logical texture or 64 texels, the height of the wall. Remember that the real texture actually starts at 32 texels up in the logical texture. And we want to display from texel 0 up to texel 63 of the real texture. So adding the 32 texel padding to 0 and 63 we display the logical texels from 32 to 95 which corresponds to .25 through .75 of the texture.

Fortunately, we don't have to go through this for horizontal coordinates.

We do have to deal with one other thing for calculating wall texture coordinates, though. The vertical length of a wall is easy to calculate, we just subtract the floor height from the ceiling height. But we have to use the distance formula to calculate the length of a wall.

typedef struct
   {
    float x, y, z
   }vert3d

float tex_GetFlatDistance(vert3d *v1, vert3d *v2)
   {
    return sqrt(((v1->x-v2->x)*(v1->x-v2->x))+((v1->z-v2->z)*(v1->z-v2->z)))
   }

We still haven't looked at offsets, though. We have to deal with two different types of offsets vertical and horizontal. And they can be positive or negative. What these offsets do is indicate how many texels the texture is offset one way or the other. The vertical offset adjusts the texture up and down while the horizontal offset adjusts the texture left and right. The way we calculate these as texture offsets is to first find out what percent of the texture the adjustment represents. We then add that percentage to the final texture coordinate we calculate.

If the horizontal offset is 16 and the texture is 64 wide, the offset factor is .25. If the offset is -16 then the factor would be -.25. To map this texture to a wall 64 wide, our horizontal coordinates would ordinarily go from 0 to 1 but we have to add the offset factor to that. So for the horizontal offset of 16 our final horizontal coordinates would be 0.25 and 1.25. One more thing. If the texture offset is negative we keep subtracting it from 1 until we have a positive offset. So a negative offset of -.25 yields an offset of .75 with final coordinates for our example of .75 and 1.75.

But what about when the floors move?

Once the player starts playing the game, we are going to have to fix some of the vertex and texture coordinates we calculated for the static level. Since we animate the moving floors and ceilings we update all the vertical coordinates when they move and only when they move. Also we retain the height of each wall segment in the data structure for the wall and calculate the height of each wall just before we draw it. If the wall height has changed, we have to recalculate the vertical texture coordinates of the wall texture. We never have to recalculate the horizontal coordinates of the walls since they never change size horizontally.

More later...

Making Floors and Ceilings

Creating Textures

Handling Sprites

Doom's Other 2D Elements

Using glOrtho

The Menu System

Background Screens

Splitting them up

Why a 3D BSP?