The Art of Demomaking - Issue 14 - Perspective Correct Texture Mapping by (22 November 1999) | Return to The Archives

Introduction

This is going to be the last tutorial about 3D related techniques, so make sure you savour it. This week I will explain in detail how perspective correct texture mapping works, and especially how to make it run very fast if you do some simplifications. I will also briefly tell you about makefiles.

Perspective Correction

Last week, to texture our polygons we used affine texture mapping. This is quick but incorrect, since we assume that we can linearly interpolate our texture coordinates (U,V) in screen space. When we take into account the perspective projection, we realise that U and V cannot be directly computed in screen space. To do things correctly, we need to take into account the Z coordinate. There are two techniques to do this, which we will cover in the following paragraph. Either technique enables us to perfectly compute the (U,V) coordinates at each pixel. By doing this for each pixel inside the polygon, we get what I call perspective perfect texture mapping. This is the ideal way of doing things, but it can be quite slow, since we need one division per pixel to project the screen coordinates into texture space. A simple hack to speed this up is to only compute the perfect texture coordinates every 16 pixels or so. Then we use linear interpolation to find the intermediary values of (U,V). This way you get a huge speed gain, and practically unnoticeable quality loss.

Linear Interpolation Method

The first technique I know of to compute the perfect texture coordinates involves linear interpolation. After what I said in the previous paragraph, you should be wondering how we can get perfect texture mapping with linear interpolation. Well, there is a trick. Although U, V and Z cannot be interpolated linearily in screen space, U/Z, V/Z and 1/Z can be. So when we're scanning along each edge of our polygons, we interpolate these values instead. Then when we need the U and V coordinates, we simply compute then with the following equation:

         (U/Z) / (1/Z) = U/Z * Z = U
         (V/Z) / (1/Z) = V/Z * Z = V

Notice the division that slows things down a lot. The advantage with this technique is that we already have most of the necessary code available. All we need is to change a few entries in the edge table and modify the texel fetching routine, and voila! We have a perspective perfect texture mapper.

Using Magic

The second technique uses the famous 9 magic constants. There's nothing magic about them at all, it's just that a majority of people don't actually understand the formula. I have to confess I can't remember how to derive the following equations, even though I sat down and worked them out a while back. Take my word for it, they do make sense! There is no magic in programming :) Here's the pseudo code to compute those 9 constants:

          //
          // Three vertices defining the polygon
          //
             V1 V2 V3

          //
          // Base of the polygon
          //
             Bp = V1

          //
          // Vectors that define texture space
          //
             Up = V2-V1
             Vp = V3-V1

          //
          // Compute the 9 constants = 3 vectors formed with cross products
          //
             sZ = Up ^ Vp
             sU = Vp ^ Bp
             sV = Bp ^ Up

          //
          // Develop that and we get
          //
             sZ.x = Up[1] * Vp[2] - Vp[1] * Up[2]
             sZ.y = Vp[0] * Up[2] - Up[0] * Vp[2]
             sZ.z = Up[0] * Vp[1] - Vp[0] * Up[1]
             sU.x = Vp[1] * Bp[2] - Bp[1] * Vp[2]
             sU.y = Bp[0] * Vp[2] - Vp[0] * Bp[2]
             sU.z = Vp[0] * Bp[1] - Bp[0] * Vp[1]
             sV.x = Bp[1] * Up[2] - Up[1] * Bp[2]
             sV.y = Up[0] * Bp[2] - Bp[0] * Up[2]
             sV.z = Bp[0] * Up[1] - Up[0] * Bp[1]

Now the question is, what do we do with these constants now? Well, unsurprisingly there is another equation that enables us to derive 1/Z, U/Z and V/Z from these 9 constants, given a vertex in screen space at location (i,j).

             1/Z = sZ.z + sZ.y * j + sZ.x * i
             U/Z = sU.z + sU.y * j + sU.x * i
             V/Z = sV.z + sV.y * j + sV.x * i

Note that i and j are uncentered, so if you need to subtract VCENTRE and HCENTRE from them for the equation to work correctly. Then to compute U and V, we do the same as above. The advantage with this method is that we can instantly compute both U and V for any pixels in the polygon without interpolation. This is slower if you want to do the entire polygon, but in some cases can be quicker. For example, if part of the polygon is occluded by others and we only need to draw a select number of pixels, then this method is ideal.

Constant Depth Optimizations

So far, I've been telling you that perspective correct texture mapping is quite slow. How come Doom could do it on old 386's then? Once again the trick is simplification. In Doom you couldn't look up or down, or tilt the view left or right. This meant that all spans, both horizontal and vertical had constant depth. By taking a quick look at our generic equations again, you'll immediately notice the huge amount of computation this saves.

            //
            // generic main loop
            //
               for (i=startx; i<endx; i++)
               {
                   isz = 1/sz;

                   u = su * isz;
                   v = sv * isz;

                   pixel( i, j ) = texel( u, v );

                   sz += dsz;
                   su += dsu;
                   sv += dsv;
               }

            //
            // constant depth simplified main loop
            //
               du = dsu/sz;
               dv = dsv/sz;
               for (i=startx; i<endx; i++)
               {
                   pixel( i, j ) = texel( u, v );

                   u += du;
                   v += dv;
               }

That's the reason why Doom was so quick. We only need two additions in our loop now. So given the special case where the line has constant depth, we can gain about 10x speed. This an ideal technique to draw horizontal planes, extremely useful for floors or sky's. See this week's demo.

Makefiles

I have to admit I've been holding out on you. There is an easy way to compile programs without having to type all the command line by hand. I probably should have told you earlier, but I'm sure that like me, you managed until with BATCH files. First you need a handy little program called make, which you can find at the DJGPP web site. It's in the archive mak3761b.zip. What make basically does is input a script, also known as makefile, that describes the way your program should be built. It then simply builds it for you. You can specify different types of compilations, like a special build for debugging, and another for release. This is what a minimal makefile looks like:

             CC = gcc

             plane: *.cpp
                    $(CC) *.cpp -o plane.exe -O2 -s -lstdcxx -lpng -lz

             clean:
                    del plane.exe

Type "make plane" and the program will be built for you. Type "make clean" and the executable will be erased. There are so many things you can do with makefiles, just consult the documentation in the archive to find out more.

Final words

This week's demo implements simple perspective correct texture mapping onto a plane. The horizontal lines are at a constant depth, but you should have no trouble extracting the relevant generic code to add to your polygon renderer. You will also find a short makefile to build the demo. It's good practice to use makefiles, so make the effort. I've just starting using them myself, it makes life a whole lot easier ;)
Well, there's no point denying it, this column is slowing coming to an end. And unless something really special comes up, you should get another 2 issues.
You can download this week's demo and source code package right here (142k)
Enjoy,
Alex

Article Series:

> - The Art of Demomaking - Issue 01 - Prologue
> - The Art of Demomaking - Issue 02 - Introduction To Computer Graphics
> - The Art of Demomaking - Issue 03 - Timer Related Issues
> - The Art of Demomaking - Issue 04 - Per Pixel Control
> - The Art of Demomaking - Issue 05 - Filters
> - The Art of Demomaking - Issue 06 - Bitmap Distortion
> - The Art of Demomaking - Issue 07 - Bump Mapping
> - The Art of Demomaking - Issue 08 - Fractal Zooming
> - The Art of Demomaking - Issue 09 - Static Texture Mapping
> - The Art of Demomaking - Issue 10 - Roto-Zooming
> - The Art of Demomaking - Issue 11 - Particle Systems
> - The Art of Demomaking - Issue 12 - Span Based Rendering
> - The Art of Demomaking - Issue 13 - Polygon Engines
> - The Art of Demomaking - Issue 14 - Perspective Correct Texture Mapping
> - The Art of Demomaking - Issue 15 - Music And Synchronization
> - The Art of Demomaking - Issue 16 - The Final Product

Copyright 1999-2008 (C) FLIPCODE.COM and/or the original content author(s). All rights reserved.
Please read our Terms, Conditions, and Privacy information.