The idea of free-direction texture-mapping seems to be new to many few people, so I decided to post this short introduction.

Warning: The level of this discussion is quite introductory, if you know (or guess) what I'm going to talk about, you probably know as much as I do.

First look at the principles. In Doom (and in Wolfenstain) the method used to draw the walls is quite simple. You divide the wall into vertical lines. Then you calculate where the wall should start and where to end on the screen (A and B in my nice ASCII-picture), and where in the texture space the corresponding line should start and end.

[font="Courier New"][color="#000080"]Wall:[nbsp][nbsp][nbsp][nbsp][nbsp][nbsp]Texture:
[nbsp]\[nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp]Y
[nbsp][nbsp]\B[nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp]\/\^\/\/\
[nbsp][nbsp]^\[nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp]/\/./\/\/
[nbsp][nbsp].[nbsp]\[nbsp][nbsp][nbsp][nbsp][nbsp][nbsp]\/\.\/\/\
[nbsp][nbsp].[nbsp]/[nbsp][nbsp][nbsp][nbsp][nbsp][nbsp]/\/./\/\/
[nbsp][nbsp]./[nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp]X
[nbsp][nbsp]/A
[nbsp]/[/color][/font]

Then you simply do a highly optimized loop in which you do all the pixels in the vertical line, pick a color from the texture, put it onto the screen, and move to next position in the texture.

The floor is a bit more complicated. (I understand that Wolfenstain had no floor texturing, am I correct?) This time, the floor segment is mapped to a horizontal line, which is simple enough. However, in texture space that same line may be in any direction, so you'll have a 2D line in the texture, like this:

[font="Courier New"][color="#000080"]Floor:[nbsp][nbsp][nbsp][nbsp][nbsp]Texture:
[nbsp][nbsp][nbsp][nbsp]/\[nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp]Y
[nbsp]A/...>\B[nbsp][nbsp][nbsp][nbsp][nbsp]\/\/\.\/\
/[nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp]\[nbsp][nbsp][nbsp][nbsp][nbsp][nbsp]/\/\.\/\/
[nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp]\/./\/\/\
[nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp]/./\/\/\/
[nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp]X[/color][/font]

This is old and dull. Now for the new and exciting part: suppose we wish to draw a polygon in 3-space that has free orientation. A bit of thought and a simple extension of the above ideas tell us that we should use a free-direction line in the display coordinates as well.

When we map a plane with free orientation to the screen, there is always one direction on the screen, in which the z-coordinate (distance) stays the same. In doom's walls it is vertical, in Doom's floors it is horizontal. But there is one such direction for every plane.

Why is constant z-coordinate important? These lines have the special property that constant movement along them corresponds to constant movement in texture space.

Read the above two paragraphs again until you have understood them, since they are the key thing. The rest is only implementation, following is a short explanation on how I did it.

For each polygon you are about to draw on the screen, do the following. Find the plane equation. From that, derive the "constant-z" direction. (Come on, take a piece of paper and a pen, it is quite easy.)

It helps to make the distinction between two cases here. Either the "constant-z" direction is more horizontal, or it is more vertical. Suppose that it is more horizontal. The constant-z line equation is now something like y = p*x, where -1 <= p >= 1.

[font="Courier New"][color="#000080"][nbsp]----
[nbsp][nbsp][nbsp][nbsp][nbsp]---[nbsp][nbsp][nbsp]Example[nbsp]of[nbsp]a[nbsp]constant-z[nbsp]line
[nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp]----
[nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp]----[/color][/font]

Now, a change in the coordinate system is in order. x is the same x as before, but y is "slanted" by the factor of p. This means that the x-axis will be "slanted" but y-axis will be the same as before.

The next thing is to convert the polygon to this coordinate system. Scan convert it line by line, but along these "slanted" (constant-z) lines.

Suppose that we are about to draw a triangle shown below, and the slanted line is the one shown above. So the path to follow on the is as follows (ASCII art is back again). The path in the texture is also determined.

[font="Courier New"][color="#000080"]On[nbsp]the[nbsp]screen:[nbsp][nbsp][nbsp][nbsp][nbsp]In[nbsp]texture[nbsp](eg.):

[nbsp]\-------[nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp]Y
[nbsp]A...[nbsp][nbsp][nbsp][nbsp]-----/[nbsp][nbsp][nbsp][nbsp][nbsp][nbsp]/./\/\/\/
[nbsp][nbsp][nbsp]\[nbsp]...[nbsp][nbsp][nbsp][nbsp][nbsp]/[nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp]\/./\/\/\
[nbsp][nbsp][nbsp][nbsp]\[nbsp][nbsp][nbsp]..../[nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp]/\/./\/\/
[nbsp][nbsp][nbsp][nbsp][nbsp]\[nbsp][nbsp][nbsp][nbsp][nbsp]/B[nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp]\/\/./\/\
[nbsp][nbsp][nbsp][nbsp][nbsp][nbsp]\[nbsp][nbsp][nbsp]/[nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp]X
[nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp]\[nbsp]/
[nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp]X[/color][/font]

So when you render the triangle, the result would be like this. The numbers are lines of constant Z-value.

[font="Courier New"][color="#000080"][nbsp]22221110[nbsp][nbsp][nbsp]
[nbsp][nbsp]3332221111000
[nbsp][nbsp][nbsp]44333222211
[nbsp][nbsp][nbsp][nbsp]544433332[nbsp][nbsp]
[nbsp][nbsp][nbsp][nbsp][nbsp]5554444[nbsp][nbsp][nbsp]
[nbsp][nbsp][nbsp][nbsp][nbsp][nbsp]66555[nbsp][nbsp][nbsp][nbsp]
[nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp]766[nbsp][nbsp][nbsp][nbsp][nbsp]
[nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp]7[nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][/color][/font]

Note: you should stack the constant-z lines just as shown in the picture.

Implementation notes: this will be a bit slower than DOOM floors, since the algorithm is a bit more complicated. Another thing is that it will not be quite as cache-coherent.

If you are rendering big polygons (and have a large cache), it helps to precalculate the pixels lying on the line, so you need not worry about your Bresenham having to choose right pixels. All you need to do is offset the line to right memory offset.

The inner loop of this machine could look something like this:

There is an error of about 0.5 pixel-lengths, since the pixels lying on the constant-z lines are rounded to nearest pixels.

Another error can also be seen in the above picture, the line marked with 0's has a small "gap" in it, what should we do with it?

Happy programming!