Texture Mapping Howto --------------------------------------------------------------------------- WARNING: this document contains hazardous information and should be used with great caution! Also the code contained herein is of the c/c++ breed. Definitions: (u, v) coordinates: the (x, y) coordinates of a texture interpolation: (x2 - x1) / (y2 - y1) or (y2 - y1) / (x2 - x1). X and y don't have to be points, they could be colors. screen space: flat 2d space (3d space projected onto the sceen. scanline: a horizontal line, joining two opposite edges of a triangle. Affine Texture Mapping: Affine texture mapping is the easiest method to map a texture onto a triangle (or any polygon for that matter). I want to focus on texture mapping triangles because they are easier to render and squares don't cut it in 3d. I also want to use floating point numbers so it's easier to understand what's going on. Each vertex of the triangle has a (x, y, z), a (u, v), a (sx, sy, sz), and a (su, sv): struct vertex { float x, y, z; // (x, y, z) coords. in 3d space float u, v; // (u, v) texture coordinates float sx, sy, sz; // (x, y, z) projected into screen space float su, sv; // (u, v) projected texture coords. }; Each triangle has a pointer to a texture and of course 3 vertices: struct triangle { vertex v[3]; unsigned char* tPtr; }; To render our triangle, we draw it top-down, left-right, interpolating (sx, sy) and (u, v). We won't need sz, su, and sv until perspective texture mapping. void DrawAffineTriangle(const triangle& tri) { // Affine texture map a triangle // if there are any bugs in here don't get pissed, just email me :) int top = 0; // index to top vertex int a, b; // other 2 vertices // interpolants float dx_A, // change in sx with respect to sy dx_B, du_A, // change in u with respect to sy du_B, dv_A, // change in v with respect to sy dv_B; for(int i = 1; i < 3; i++) { // find top vertex if(tri.v[i].sy < tri.v[top].sy) top = i; } a = top + 1; b = top - 1; if(a > 2) a = 0; if(b < 0) b = 2; int y = int(tri.v[top].sy); float x1 = tri.v[top].sx; float x2 = x1; float u1 = tri.v[top].u; float u2 = u1; float v1 = tri.v[top].v; float v2 = v1; int height_A = int(tri.v[a].sy - tri.v[top].sy); int height_B = int(tri.v[b].sy - tri.v[top].sy); if(height_A) { // avoid divide by zero // calculate the interpolants dx_A = (tri.v[a].sx - tri.v[top].sx) / height_A; du_A = (tri.v[a].u - tri.v[top].u) / height_A; dv_A = (tri.v[a].v - tri.v[top].v) / height_A; } if(height_B) { // avoid divide by zero // calculate the interpolants dx_B = (tri.v[b].sx - tri.v[top].sx) / height_B; du_B = (tri.v[b].u - tri.v[top].u) / height_B; dv_B = (tri.v[b].v - tri.v[top].v) / height_B; } // start drawing for(int i = 2; i > 0;) { while(height_A && height_B) { DrawAffineScanline(x1, x2, u1, u2, v1, v2, y, tri.tPtr); y++; height_A--; height_B--; x1 += dx_A; // add the interpolants x2 += dx_B; u1 += du_A; u2 += du_B; v1 += dv_A; v2 += dv_B; } if(!height_A) { // new edge int na = a + 1; if(na > 2) na = 0; height_A = int(tri.v[na].sy - tri.v[a].sy); if(height_A) { // avoid divide by zero // recalculate the interpolants for the new edge dx_A = (tri.v[na].sx - tri.v[a].sx) / height_A; du_A = (tri.v[na].u - tri.v[a].u) / height_A; dv_A = (tri.v[na].v - tri.v[a].v) / height_A; } x1 = tri.v[a].sx; u1 = tri.v[a].u; v1 = tri.v[a].v; i--; // one less vertex a = na; } // end if if(!height_B) { // new edge int nb = b - 1; if(nb < 0) nb = 2; height_B = int(tri.v[nb].sy - tri.v[b].sy); if(height_B) { // avoid divide by zero // recalculate the interpolants for the new edge dx_B = (tri.v[nb].sx - tri.v[b].sx) / height_B; du_B = (tri.v[nb].u - tri.v[b].u) / height_B; dv_B = (tri.v[nb].v - tri.v[b].v) / height_B; } x2 = tri.v[b].sx; u2 = tri.v[b].u; v2 = tri.v[b].v; i--; // one less vertex b = nb; } // end if } // end for loop } // end function This next function is to draw a scanline: DrawAffineScanline(float x1, float x2, float u1, float u2, float v1, float v2, int y, unsigned char* tPtr) { // we are assuming the texture is 64 units wide, it can be any // size though. if(x2 < x1) { // swap coordinates so we // can draw left-to-right float tmp = x1; x1 = x2; x2 = tmp; tmp = u1; u1 = u2; u2 = tmp; tmp = v1; v1 = v2; v2 = tmp; } float width = x2 - x1; float du, dv; // more interpolants int u, v; if(width) { // avoid divide by zero du = (u2 - u1) / width; dv = (v2 - v1) / width; } // draw the scanline for(int x = int(x1); x < int(x2); x++) { u = int(u1); v = int(v1); screen[y * 320 + x] = tPtr[v * 64 + u]; u1 += du; v1 += dv; } } // end function That's it, you got yourself an affine texture mapped triangle. Affine Mapping is very fast but it has two flaws, it warps when using triangles and doesn't exactly look right with large triangles at sharp angles. It doesn't warp if you use squares, but you can't use squares very well to make complex 3d objects. To fix this problem, you have to take the z axis into account when texture mapping. Notice in affine mapping sz, su, and sv wasn't used. Now we are going to use them in Perspective Correct Texture Mapping. Perspective Correct Texture Mapping: Perspective Correct Texture Mapping is how the world really looks, none of this fake texture mapping. The problem is that it is pretty slow relative to affine mapping. Fortunately, it can be speeded up a lot. Ok, when we project 3d space onto screen space, we divide (x, y) and (u, v) by z: sx = x / z; sy = y / z; su = u / z; sv = v / z; We get these new coordinates (sx, sy) and (su, sv). Notice (su, sv), before we didn't project the (u, v) coordinates into screen space. We also need to project the z coordinate into screen space to give us sz = 1 / z Now since (sx, sy, sz) and (su, sv) are in screen space they are linear! We can just interpolate these values along the edges and across scanlines. But we need the original (u, v) coordinates, not the (su, sv) coordinates. That's were interpolating sz comes in. To get (u, v), we divide su by sz and sv by sz: u = (su / sz) = (u / z) / (1 / z) v = (sv / sz) = (v / z) / (1 / z) The DrawPerspective function is nearly the same as the DrawAffineTriangle function except you need to interpolate (su, sv) and sz instead of just (u, v): void DrawPerspectiveTriangle(const triangle& tri) { // Perspective texture map a triangle int top = 0; // index to top vertex int a, b; // other 2 vertices // interpolants float dx_A, // change in sx with respect to sy dx_B, du_A, // change in su with respect to sy du_B, dv_A, // change in sv with respect to sy dv_B, dz_A, // change in sz with respect to sy dz_B; for(int i = 1; i < 3; i++) { // find top vertex if(tri.v[i].sy < tri.v[top].sy) top = i; } a = top + 1; b = top - 1; if(a > 2) a = 0; if(b < 0) b = 2; int y = int(tri.v[top].sy); // all of the interpolants float x1 = tri.v[top].sx; // start at the top vertex float x2 = x1; float u1 = tri.v[top].su; float u2 = u1; float v1 = tri.v[top].sv; float v2 = v1; float z1 = tri.v[top].sz; float z2 = z1; int height_A = int(tri.v[a].sy - tri.v[top].sy); int height_B = int(tri.v[b].sy - tri.v[top].sy); if(height_A) { // avoid divide by zero // calculate the interpolants dx_A = (tri.v[a].sx - tri.v[top].sx) / height_A; du_A = (tri.v[a].su - tri.v[top].su) / height_A; dv_A = (tri.v[a].sv - tri.v[top].sv) / height_A; dz_A = (tri.v[a].sz - tri.v[top].sz) / height_A; } if(height_B) { // avoid divide by zero // calculate the interpolants dx_B = (tri.v[b].sx - tri.v[top].sx) / height_B; du_B = (tri.v[b].su - tri.v[top].su) / height_B; dv_B = (tri.v[b].sv - tri.v[top].sv) / height_B; dz_B = (tri.v[b].sz - tri.v[top].sz) / height_B; } // start drawing for(int i = 2; i > 0;) { while(height_A && height_B) { DrawPerspectiveScanline(x1, x2, u1, u2, v1, v2, z1, z2, y, tri.tPtr); y++; height_A--; height_B--; x1 += dx_A; // add the interpolants x2 += dx_B; u1 += du_A; u2 += du_B; v1 += dv_A; v2 += dv_B; z1 += dz_A; z2 += dz_B; } if(!height_A) { // new edge int na = a + 1; // next vertex if(na > 2) na = 0; height_A = int(tri.v[na].sy - tri.v[a].sy); if(height_A) { // avoid divide by zero // recalculate the interpolants for the new edge dx_A = (tri.v[na].sx - tri.v[a].sx) / height_A; du_A = (tri.v[na].su - tri.v[a].su) / height_A; dv_A = (tri.v[na].sv - tri.v[a].sv) / height_A; dz_A = (tri.v[na].sz - tri.v[a].sz) / height_A; } x1 = tri.v[a].sx; u1 = tri.v[a].su; v1 = tri.v[a].sv; z1 = tri.v[a].sz; i--; // one less vertex a = na; } // end if if(!height_B) { // new edge int nb = b - 1; // next vertex if(nb < 0) nb = 2; height_B = int(tri.v[nb].sy - tri.v[b].sy); if(height_B) { // avoid divide by zero // recalculate the interpolants for the new edge dx_B = (tri.v[nb].sx - tri.v[b].sx) / height_B; du_B = (tri.v[nb].su - tri.v[b].su) / height_B; dv_B = (tri.v[nb].sv - tri.v[b].sv) / height_B; dz_B = (tri.v[nb].sz - tri.v[b].sz) / height_B; } x2 = tri.v[b].sx; u2 = tri.v[b].su; v2 = tri.v[b].sv; z2 = tri.v[b].sz; i--; // one less vertex b = nb; } // end if } // end for loop } // end function And here is the perspective scanline function: DrawPerspectiveScanline(float x1, float x2, float u1, float u2, float v1, float v2, float z1, float z2, int y, unsigned char* tPtr) { // remember that x1, x2, u1, u2, v1, v2, z1, and z2 are projected // coordinates. // we are assuming the texture is 64 units wide, it can be any // size though. if(x2 < x1) { // swap coordinates so we // can draw left-to-right float tmp = x1; x1 = x2; x2 = tmp; tmp = u1; u1 = u2; u2 = tmp; tmp = v1; v1 = v2; v2 = tmp; tmp = z1; z1 = z2; z2 = tmp; } float width = x2 - x1; float du, dv, dz; // more interpolants int u, v; if(width) { // avoid divide by zero du = (u2 - u1) / width; dv = (v2 - v1) / width; dz = (z2 - z1) / width; } // draw the scanline for(int x = int(x1); x < int(x2); x++) { u = int(u1 / z1); // u = (u / z) / (1 / z) v = int(v1 / z1); // v = (v / z) / (1 / z) screen[y * 320 + x] = tPtr[v * 64 + u]; u1 += du; v1 += dv; z1 += dz; } } // end function Now you have a perspective correct texture mapped triangle! Afterthoughts The code above is to get the basic idea across, and is not a good way to rasterize polygons. It will produce "grainy" artifacts along with wobbly textures. Actually you can notice some of these things in a lot of current game engines, but I really suggest getting Chris Hecker's articles in Game Developer magazine to see what goes into a perfect rasterizer. It is a five article series in all: * April/May 1995 Perspective Texture Mapping Part I: Foundations * June/July 1995 Part II: Rasterization * August/Sept 1995 Part III: Endpoints and Mapping * Dec 1995/Jan 1996 Part IV: Approximations * April/Map 1996 Part V: It's About Time It's around \$8 an issue, but I think it's worth it and you can order back issues from Game Developer. It is the best information I found on texture mapping by far. Other references and information: * Pcgpe (Pc game programming encyclopedia) has a document on texture mapping. I thought it was hard to understand and had some bugs in it. * Milo's Home Page A pretty cool page on 3d programming, check it out. I want to thank Mark Feldman for pointing out some bugs in my code. He has also written a new document on texture mapping for Win95GPE (which isn't expected to be out until early '97). Fortunately, you can check it out HERE . Go to the Win95GPE Home Page and you'll find it. It discusses many different methods of texture mapping. I would like to hear some feed back so why don't you email me? Last modified or fixed: 2/2/97, 4:06pm 5301 hits since 9/22/96, 10:42am