| # 3D Game Design ## Perspective Correct Texture Mapping
> The original version of this document was found at http://www.rhumba.net/milo/3dgames/tmap.htm ### Sample Implementation All of the ideas discussed on this page are being used in the Alpha engine. To see an example of these ideas in a working application, try Poly2.hpp and Poly2.cpp. ### Texture Mapping Fundamentals Texture mapping is the process of copying data (texels) from a source image (texture) to a destination image in such a way that it appears as if the source image is "painted on" a surface in the destination image. The basic algorithm is to iterate over the pixels in the destination image, and for each pixel, calculate which texel in the texture bitmap should be used to color the pixel:
>     BYTE* screen;

>     BYTE* texture;

>     for (int y = 0; y < ymax; y++) {

>        for (int x = 0; x < xmax; x++) {

>           int u = TextureMap_U(x,y);

>           int v = TextureMap_V(x,y);

>           screen[y][x] = texture[v][u];

>        }

>     }
> The details of the functions `TextureMap_U` and `TextureMap_V` determine what sort of texture mapping is being performed. ### Perspective Correct Texture Mapping For first person perspective 3D gaming, we are mainly concerned with "perfect" or "perspective correct" texture mapping and approximations thereof. The basic idea of perspective correct texture mapping is to compute the 3D to 2D projection of the texture image onto the destination image. In order to do this, we must first define the texture in 3-space coordinates, and then apply the appropriate vector transforms. The first part is easy. Let us assume that the source texture is rectangular (for performance reasons, we will later assume that it has dimensions that are powers of 2). Let us also assume that the destination polygon (in 3-space) is also rectangular (this assumption does not always hold, but it is easy to work around). The first step is to compute three vectors which define the placement of the texture in 3-space: P, M, and N. Figure 1: Texture Vectors P, M, and N. As shown in Figure 1, if the upper left hand vertex of the texture polygon is V0, and the remaining vertices are numbered sequentially in clockwise facing order, then the texture vectors can be calculated as follows:
>     P = V0

>     M = V1 - V0    // vector subtraction

>     N = V3 - V0
> Note that these numbers must be scaled appropriately. If your world coordinates are transformed into screen coordinates like this:
>     i =  hscale * x / z

>     j = -vscale * y / z
> Then you need to multiply the `x` components of P, M, and N by `hscale` and the `y` components by `-vscale`. For each polygon, we then compute the following "magic" vectors:
>     // "x" is vector cross product,

>     // "*" is vector-scalar multiplication

>     A = (P x N) * twidth

>     B = (M x P) * theight

>     C = (N x M)
> To complete the mapping, for each pixel compute the following:
>     S = Vector(i, j, 1)

>     a = S * A      // dot product

>     b = S * B

>     c = S * C

>     u = texturewidth  * a / c

>     v = textureheight * b / c

>     screen[j][i] = texture[v][u]
> This gives rise to the following (horizontal) rendering loop:
>     // Once for the entire polygon, compute A, B, and C

>     VECTOR3 A, B, C;

>     CrossProduct(poly.P, poly.N, A);  A = A * twidth;

>     CrossProduct(poly.M, poly.P, B);  B = B * theight;

>     CrossProduct(poly.N, poly.M, C);

>     // For each row of the polygon...

>     for (int j = poly.top; j < poly.bottom; j++) {

>        // Find the screen location and horizontal boundaries

>        BYTE* srow = screen + screen_pitch * j;

>        int start = poly.row_at(j).left;

>        int end   = poly.row_at(j).right;

>        double a, b, c;

>        int    u, v;

>        // For each pixel in the row...

>        for (int i = start; i < end; i++) {

>           // Compute dot products and divisions

>           VECTOR3 S = VECTOR3(i,j,1);

>           a = DotProduct(S, A);

>           b = DotProduct(S, B);

>           c = DotProduct(S, C);

>           u = twidth  * a/c;

>           v = theight * b/c;

>           // Perform the texture lookup and screen write

>           srow[i] = texture[v][u];

>        }

>     }
> This code will perform perspective correct texture mapping on any set of (convex) polygons, seen from any position and any angle: it is the basis for a true 3D 6 degree of freedom renderer. But it isn't very fast. NOTE You may see people on the net espouse using triangular polygons for texture mapping "because the polygon gradients are constant across the entire triangle, and you only need one divide per triangle." This is called "linear texture mapping," and it will not work as a substitute for perspective texture mapping. ### Picking Up Speed The above code is not very efficient. There are nine multiplies, six adds, and two divides per pixel. At 640x480 resolution those operations will have to be repeated over 300,000 times per frame! Let's try to speed things up a bit. We'll start by pulling everything out of the loop that doesn't need to be there. Most of the variables do not change each time through the loop, so they can be computed once and reused. Also, we're dividing by `c` twice; no need for that:
>     for (int j = poly.top; j < poly.bottom; j++) {

>        BYTE* srow = screen + screen_pitch * j;

>        int start = poly.row_at(j).left;

>        int end   = poly.row_at(j).right;

>        double a = start*A.x + j*A.y + A.z;

>        double b = start*A.x + j*B.y + B.z;

>        double c = start*A.x + j*C.y + C.z;

>        for (int i = start; i < end; i++) {

>           double cinv = 1/c;

>           int u = tw * a * cinv;

>           int v = tw * b * cinv;

>           srow[i] = texture[v][u];

>           a += A.x;

>           b += B.x;

>           c += C.x;

>        }

>     }
> This code is a bit better, but still requires at least one floating point divide per pixel. This is simply still too slow for real time rendering. Even if we ignore every other instruction in the entire program 307,200 divides at 39 clocks per divide means the best we can hope for is 11 frames per second on a Pentium 133. The rest of this page (and about half the trick to 3D rendering engines) is devoted to making the above code go faster by eliminating or reducing the impact of those divides. ### "Floor" Mapping There is one important case where those costly divides per pixel can be eliminated from the inner loop: when the `c` term does not vary over the course of the span. From the code above, this is obviously true whenever `C.x` is zero. This situation is called "spans of constant z", because every pixel on the span is at the same z distance from the viewer. This is always true for flat "floor" and "ceiling" polygons, as long as the viewer doesn't tilt his head to one side or the other. Spans of constant z also occur for all vertical "wall" polygons, as long as the viewer doesn't look up or down, and the spans are drawn vertically instead of horizontally. Note that no head tipping or tilting, and all vertical walls and all horizontal floors are precisely the restrictions that are placed on the Doom universe. In Doom, all spans are of constant z, and so only one divide is necessary per span. Which is why Doom runs so much faster than Quake. NOTE Duke Nukem 3D and Dark Forces also employ almost the same restrictions. In both these games, walls are always vertical, the player can not tip his head to the left or right, and the view angle can not be adjusted up or down. Both of these games use a modified head tilt which actually performs a 2D translation instead of a 3D rotation. ### Bilinear Interpolation Another, more general way to reduce the impact of per pixel divides is called "bilinear interpolation." This technique breaks each horizontal span into 8 or 16 pixel sub-spans, computes accurate texture coordinates at the beginning and end of each sub-span, and uses linear interpolation in between.
>     for (int j = poly.top; j < poly.bottom; j++) {

>        BYTE* srow = screen + screen_pitch * j;

>        int start = poly.row_at(j).left;

>        int end   = poly.row_at(j).right;

>        double a = start*A.x + j*A.y + A.z;

>        double b = start*A.x + j*B.y + B.z;

>        double c = start*A.x + j*C.y + C.z;

>        // compute u and v at the start and

>        // end of a sub-span:

>        double u0 = tw * a/c;

>        double v0 = tw * b/c;

>        a += A.x * 16.0;

>        b += B.x * 16.0;

>        c += C.x * 16.0;

>        int count = end-start;

>        while (count) {

>           double u1 = tw * a/c;

>           double v1 = tw * b/c;

>           // compute linear increment for u and v:

>           double du = (u1 - u0)/16;

>           double dv = (v1 - v0)/16;

>           int run = (count>16) ? 16 : count;

>           // perform bilinear interpolation

>           // across sub-span:

>           for (int i = 0; i < run; i++) {

>              int u = (int) u0;

>              int v = (int) v0;

>              srow[i] = texture[v][u];

>              u0 += du;

>              v0 += dv;

>           }

>           // update polygon gradients for

>           // next sub-span:

>           u0 = u1;

>           v0 = v1;

>           a += A.x * 16.0;

>           b += B.x * 16.0;

>           c += C.x * 16.0;

>        }

>     }
In effect, bilinear interpolation treats every polygon as a floor, sixteen pixels at a time. For the most part, bilinear interpolation produces a result that is indistinguishable from true "perfect" mapping. The only visible distortion occurs when mapping large polygons seen at sharp angles to the viewer (sometimes called the "rubber sheet" effect). The distortion is caused by approximating a hyperbolic curve with a series of straight line segments, and it makes the surface look "pinched" at regular intervals. Figure 2: Distortion with Bilinear Interpolation. This distortion can be reduced or eliminated by checking the viewing angle and using shorter spans only on the distorted polygons. Alternatively, the span length can be reduced for all polygons (definitely slowing down the renderer) whenever the viewer is stationary. One final alternative is to design the game so that the viewer will rarely see polygons at sharp angles. ### Advanced Optimization What we have looked at so far is the basic algorithm and a bit of the math behind texture mapped rendering. Really getting a perspective correct texture mapper to run at a decent frame rate requires tuning the performance of many aspects of the above code. More than just coding up a tight inner loop in assembly language, optimizing a renderer means studying the performance of the entire algorithm and making sure that no part of it slows down the entire works. That's what we're going to look at next. ### Acknowledgements Thanks and credit to Sean Barrett and Mark Feldman for publishing most of this info first. Sean worked on the original PC Game Programmer's Encyclopedia, and was a programmer on Origin's System Shock. Mark is the current maintainer of the PC Game Programmer's Encyclopedia, which should be released real soon now, right Mark? back to milo's home page | e-mail milod@netcom.com This page is designed and implemented by John DiCamillo Copyright © 1995-1997 John DiCamillo. All rights reserved. Hosted by Rhumba Networks - http://www.rhumba.net