Dr. Dobb's Journal July 1998
It used to be you could get away with developing flat shaded 3D computer games and engines. But if your software doesn't support texture mapping these days, it will likely end up in the bargain bin. One form of texture mapping is "affine" texture mapping, which is fundamental to many forms of 3D rendering, including light interpolation and other sampling type operations. In this article, I'll present an affine texture mapper that can texture map a 64×64-pixel/256-color rectangular bitmap onto a triangular polygon with full texture coordinate support. In addition, I'll include a demo that loads texture maps and draws thousands of textured triangles a second. Although this demo is in DirectX, the ideas and concepts are applicable to other systems. And since the texture mapper is in straight C, it's totally portable.
Assume you want to texture map a rectangular bitmap that is 64×64 pixels in 256 colors (one byte per pixel) onto an arbitrary triangle with any coordinates. To do so, you need to take rotation and scaling of the triangle into consideration. To design the algorithm that makes this possible, I've labeled a number of points of interest on Figure 1. First, the destination triangle is made up of three vertices -- p0, p1, and p2, with coordinates (x0,y0), (x1,y1), and (x2,y2), respectively. In addition, the axes around the texture map are U and V, where U is the horizontal axis and V is the vertical axis. Both U and V range from (0,0) in the upper left to (63,63) in the lower right. What you want to do is design an algorithm that samples the texture map, so that the sampled pixels can be used to color each pixel of each scanline of the target triangle polygon as it is being rendered.
There are a number of ways to draw triangles, including tracing the edges of the triangle with a line-drawing algorithm (such as Bresenham's) or with simple interpolation. I prefer interpolation since it's more straightforward. Also, the concept of interpolation is important because the texture mapping algorithm is based on it. In Figure 2, all you have to do is find the points (shown as little dots) that make up the integer rasterized version of the triangle. Once you find these dots for each scanline that makes up the triangle, drawing the triangle is nothing more than performing a memory fill from dot to dot. Finding these points simply involves interpolating the slope of each side of the triangle. The interpolation is done as follows:
You know that the height of the triangle is:
dy=(y2-y0);
and the difference in the "x" between the lower-left vertex and the lower-right vertex is:
dx_left_side=(x2-x0); dx_right_side=(x1-x0);
Thus, the slope of the left side is:
slope_left_side=dy/dx_left_side=(y2-y0)/(x2-x0);
And, the slope of the right side is:
slope_right_side=dy/dx_right_side=(y2-y0)/(x1-x0);
However, you don't exactly want the slope. The slope is the "change in Y per change in X." This means that if you were to move over exactly one pixel in the X direction, then the Y would change by the slope. You don't want this. In fact, you want the opposite -- dx/dy -- because you are drawing the triangle scan line by scan line and incrementing Y each time; hence dy=1, which is a constant. Thus:
dx_left_side=1*(x2-x0)/(y2-y0);
and
dx_right_side=1*(x1-x0)/(y2-y0);
Listing One is a pseudocode implementation of the triangle drawing algorithm.
Texture mapping a triangle with a rectangular texture map involves lots of interpolating. Consequently, it's easy to make a mistake or to write a slow algorithm. With this in mind, I'll start with the simplest case in one dimension. Figure 3 illustrates the simplest texture mapper -- the texture mapping of a single vertical line that's one pixel thick and eight pixels high.
What you need to do is "sample" the texture map (in this case, a single 1×8 pixel bitmap) and map it into the destination polygon, which is 1×n pixels, where n can range from one to infinity.
As a first example, assume that your destination polygon is 1×4 pixels. It makes sense that you want to sample the source texture every other pixel, as in Figure 3. Thus, if you select pixels (0,2,4,6) of the source texture and map them into the destination polygon at positions (0,1,2,3), then you are doing pretty good. But how did you arrive at (0,2,4,6)? The answer is by using a sampling ratio, which is nothing more than an interpolation factor. In general, sampling_ratio=source_height/destination_height. Thus, the sampling ratio is sampling_ratio=8/4=2. Thus, every one pixel you move on the destination polygon in the vertical axis, you must move two pixels on the source to keep up. That's where the "two" comes from and hence the sampling sequence (0,2,4,6). Unfortunately, this means you had to throw away half the pixels. This is a problem with sampling on an integer matrix without any averaging. If you were writing a high-end 3D modeler (like 3D Studio MAX), then you would probably average the pixels you're sampling (area sampling) to get a better approximation, but for games and real time, our technique will do.
In the previous example, the source texture was compressed; that is, the destination was smaller than the source and information was lost. On the other hand, there could be the case that the destination is bigger than the source, and there isn't enough information to go around. In this case, the source data must be sampled more than once and replicated. This is where all "chunkiness" comes from when texture mapped polygons get too close to you in a 3D game. There isn't enough texture data so some sample points are sampled many times, creating big blocks. Referring again to the second example in Figure 3, you see that the source is again 1×8, but this time the destination is 1×14 pixels. Obviously, you need a fractional sampling ratio. Again, sampling_ratio=source_height/destination_height;. Thus, the sampling ratio is sampling_ratio=8/14=0.57.
Hence, the sample for every pixel you draw on the destination polygon should be taken 0.57 units from the last sample point on the source. This gives you the following sample point sequence for destination pixels (0,1,2,3,....13):
Sample 0: 0.57 Sample 1: 1.14 Sample 2: 1.71 Sample 3: 2.28 Sample 4: 2.85 Sample 5: 3.42 Sample 6: 3.99 Sample 7: 4.56 Sample 8: 5.13 Sample 9: 5.7 Sample 10: 6.27 Sample 11: 6.84 Sample 12: 7.41 Sample 13: 7.98
To get the actual sample points, you simply truncate the sample points in integer space or take the floor of each value resulting in the sample points (0,1,1,2,2,3,3,4,5,5,6,6,7,7), which sounds about right. Each point got sampled about two times, or 1/0.57.
When I wrote my first affine texture mapper, I thought something must be wrong since it seemed like I was interpolating everything. The truth is, there is really no way around all the various interpolants, and in the end, the inner loop for each pixel can be optimized into around 10 cycles/pixel on a Pentium, which translates to a theoretical maximum of 10- to 20-million textels (textured pixels) per second on a 100-MHz Pentium.
The idea behind the algorithm is that you want to interpolate down the left and right edges of the triangle and draw each scanline strip as we go with the proper texture pixels. What you need to do first is assign full texture coordinates to the vertexes of the destination triangle to give us a frame of reference for the interpolants. Thus you must assign each vertex a (u,v) texture coordinate, as in Figure 4. Therefore, each vertex has a total of four data components -- that is, it's a 4D value. Since the source texture map is 64×64 pixels, the texture coordinates must range from 0-63 for any vertex. This will map or stretch the texture map to each vertex.
Figure 5(a), for example, has the texture coordinates (0,0), (63,0), and (63,63) mapped to vertices 0,1, and 2, respectively. This basically copies half of the texture map to the destination triangle, which is what you would expect. In Figure 5(b), you see the same texture mapped onto two triangles which are adjacent to each other forming a square. In this case, the texture coordinates are selected in such a way that half of the texture map is mapped to one triangle and the rest to the other, hence, a perfect texture wrapping around two triangles. Moreover, this is how you would make a quadrilateral; that is, with two triangles. Now that you have a visual on the problem and know the labeling from Figure 4, let's implement the algorithm mathematically. The variable names used in the following analysis are based on Figure 4 and the final program so that you can follow the program code more easily.
The left edge interpolants are:
dxdyl = (x2-x0)/(y2-y0); // x interpolant for left side dudyl = (u2-u0)/(y2-y0); // u interpolant for left side dvdyl = (v2-v0)/(y2-y0); // v interpolant for left side
Similarly, the right edge interpolants are:
dxdyr = (x1-x0)/(y2-y0); // x interpolant for right side dudyr = (u1-u0)/(y2-y0); // u interpolant for right side dvdyr = (v1-v0)/(y2-y0); // v interpolant for right side
There's a lot of room for optimization. For example, (y2-y0) is common and need only be computed once. Furthermore, it's better to compute the reciprocal of (y2-y0) and then multiply.
The interpolants must be in reference to some starting point. This starting is the top-most vertex, vertex 0. Hence, you need to start the algorithm off in the following manner:
xl = x0; // starting point for left side edge x interpolation ul = u0; // starting point for left side edge u interpolation vl = v0; // starting point for left side edge v interpolation
And for the right side,
xr = x0; // starting point for right side edge x interpolation ur = u0; // starting point for right side edge u interpolation vr = v0; // starting point for right side edge v interpolation
Now you can interpolate down the left and right edges with:
xl+=dxdyl; ul+=dudyl; vl+=dvdyl;
and
xr+=dxdyr; ur+=dudyr; vr+=dvdyr;
At each point on the left and right edge of the triangle, you still need to perform one more linear interpolation across the scanline. This is the final interpolation and the one that will give you the texture coordinates (ui,vi), which you'll use as [row, column] indexes into the texture bitmap to obtain the textel. All you need to do is compute the u,v coordinate on the left and right side, then use the dx to compute a linear interpolation factor for each. Here's the math:
dx = (xend-xstart); // difference or delta dx xstart = xl; // left starting point xend = xr; // right starting point
Therefore, the interpolants across each scanline in u,v space are:
du = (ul-ur)/dx; dv = (vl-vr)/dx;
Then with du,dv, you have everything you need to interpolate across the scanline at vertical position y from xstart to xend; see Listing Two.
That's it. Of course for the outer loop, you would still interpolate xl,ul,vl,xr,ur,vr down the triangle edges for each scanline of the triangle.
The files tmapper.h and tmapper.cpp (available electronically; see "Resource Center," page 3) provide a complete implementation of the texture mapper. The program assumes a specific input data structure and that the texture map is a linear bitmap 64×64 pixels. Other than that, it's nothing more than an implementation of the derivation here, along with all the triangle cases and clipping. In addition, the program tmapdemo.cpp (available electronically) is a complete DirectX demo of the texture mapper that draws random triangles all over the screen in 640×480×256. Finally, BOX2.EXE is a 3D demo written by Jarrod Davis that uses the texture mapper.
DDJ
void Draw_Triangle(float x0,float y0,float x1,float y1,float x2,float y2, int color)
{
// this function rasterizes a triangle with a flat bottom
// compute left side interpolant
float dx_left = (x2 - x0)/(y2 - y0);
// compute right side interpolant
float dx_right = (x1 - x0)/(y2 - y0);
// seed left and right hand interpolators
float x_left = x0;
float x_right = x0;
// enter into rasterization loop
for (int y=y0; y<=y1; y++)
{
// draw the scanline
Draw_Line(x_left, x_right, y, color);
// advance interpolants
x_left+=dx_left;
x_right+=dx_right;
} // end for y
} // end Draw_Triangle
// initialize u,v interpolants to left and right side valuesui = ul;
vi = vl;
// now interpolate from left to right, i.e, in a positive x direction
for (x = xstart; x <= xend; x++)
{
// get texture pixel value
pixel = texture_map[ui][vi];
// plot pixel at x,y
Plot_Pixel(x,y,pixel);
// advance u,v interpolants
ui+=du;
vi+=dv;
} // end for x