(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 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 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!
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:
Other references and information:
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
12396 hits since 9/22/96, 10:42am