Texture Mapping Mania by André LaMothe A long time ago in a galaxy far, far away, there were only flat shaded 3D games and engines... Today, if your product doesn't support texture mapping then it's probably going to end up in the bargain bin right next to yet another version of Defender. Not only is texture mapping expected these days, it's possible in real-time. And it can be accomplished totally in software which makes it nice for programmers. Now the bad news...Texture mapping is actually a very complex subject especially when you start talking about perspective correct, Mip-Mapped, light interpolated, alpha channeled, texture mapping. In this article, we are going to cover the most basic form of texture mapping which is referred to as "affine" texture mapping. An affine transformation means that it preserves quantities, thus as one image is mapped onto another and there is a one to one relationship, that is, no warping. In the realm of texture mapping, affine mapping usually means throwing away the 3D information all together and performing a simple 2D mapping. Perspective texture mapping on the other hand, takes the Z coordinate of a 3D polygon definition into consideration hence the perspective warping into consideration that occurs in a 3D space and uses this information to perform the texture mapping in a more visually correct way. Figure 1.0 shows the difference between a affine texture mapped polygon and a perspective correct texture mapped polygon. Notice how the perspective correct image looks more realistic. The problem with perspective correct texture mapping is that it takes 2 divisions per pixel. Of course, you can approximate perspective correct texture mapping with what is referred to as "perspective correct-ed" texture mapping, by only computing the perspective every few pixels and then affine texture mapping (or linearly interpolating) in-between. But again this is only an approximation, and you must affine texture map in the middle. The point is, the ultimate goal is to create a perspective corrected texture mapper with all the toppings. But, you have to start somewhere, and affine texture mapping is a good place since many of the concepts apply to other aspects of 3D rendering such as light interpolation and other sampling type operations. In fact, texture mapping is really nothing more than an application of sampling theory. That's what we're doing, sampling one data set and projecting or mapping it into another. But, enough talk, let's get to it shall we! What's In It For Me? Before we get started on the math and the code, I want to give you an idea of what exactly you're going to get. By the end of this article you'll have all you need including the working source code for an affine texture mapper that can texture map a rectangular bitmap texture that's 64x64 pixels in 256 colors onto a triangular polygon with full texture coordinate support. In addition, I'm going to give you a full working demo that loads in some texture maps and draws thousands of textured triangles a second on the screen. The demo will be in DirectX since the DirectX SDK is readily available and DirectX is the easiest 32 bit platform these days and the one any graphics programmer on the PC should be using. But if you're working on another system then the ideas and concepts are absolutely applicable and the texture mapper is in straight C, so it's totally portable. Getting Down To Specifics Figure 2.0 shows the exact process that we want to implement. We want to texture map a rectangular bitmap that is 64x64 pixels in 256 colors (1 byte per pixel) onto an arbitrary triangle with any coordinates. This means that we need a way to take rotation and scaling of the triangle into consideration. To help design the algorithm, I have labeled a number of points of interest on Figure 2.0. First, you'll see that the destination triangle is made up of 3 vertices, these have been labeled p0, p1, and p2, with coordinates (x0, y0), (x1, y1), and (x2, y2) respectively. In addition, I have labeled the axes around the texture map as U and V, where U is the horizontal axis and V is the vertical axis. Note that both U and V range from (0,0) in the upper left hand corner to (63,63) in the lower right hand corner. What we want to do is come up with 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. Hold on a minute! What's all this about rendering triangles? We'll, the point of texture mapping is to draw or render a triangle with the texture on it, but to draw a textured triangle. I guess we better take a quick look at how to draw an non-textured single color triangle huh? Take a look at Figure 3.0 here you see the various cases of triangles that can possibly exist. There are: Type 1: Flat Top - A triangle with a flat top. Type 2: Flat Bottom - A triangle with a flat top. Type 3: General - A general triangle with neither a flat top or bottom. However, the general triangle is really made up of a triangle with a flat top, and one with a flat bottom. So if we can draw Type 1 and 2 triangles then Type 3 is easy. So let's focus on Type 2, from it you can figure out how to do Type 1 since it's the same as Type 2, just upside down. Interpolate Me Baby! There are a number of ways to draw triangles including tracing the two edges of the triangle with a line drawing algorithm such as Bresenham's or with simple interpolation. I prefer interpolation since it's more straight forward. Let's see how this works. Take a look at Figure 4.0, all we have to do is find the points that make up the integer rasterized version of the triangle. These points are shown in the figure as little dots. Once we find these dots for each scanline the makes up the triangle then drawing the triangle is nothing more than performing a simple memory fill from dot to dot as shown in Figure 4.0. Finding these points is nothing more than interpolating the slope (well almost) of each side of the triangle. The interpolation is done as follows: We know that the height of the triangle is: ``` dy = (y2 - y0); ``` And the difference in X's 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 hand side is: ``` slope_left_side = dy/dx_left_side = (y2 - y0)/(x2 - x0); ``` And, the slope of the right hand side is: ``` slope_right_side = dy/dx_right_side = (y2 - y0)/(x1 - x0); ``` However, we don't exactly want the slope. The slope is the "change in Y per change in X". This means that if we were to move over exactly one pixel in the X direction then the Y would change by the slope. We don't want this, we want the opposite, or dx/dy. This is because we 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); ``` That's it! That's the entire triangle drawing algorithm for a flat bottom Type 2 triangle. Type 1 is similar and I leave up to you. Take a look at Listing 1.0 for a pseudo-code implementation of the triangle drawing algorithm. Listing 1.0 - Pseudo Code Implementation of Triangle Renderer ``` 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 ``` At this point you've seen how interpolation can be used to sample something and draw it. Granted in this case, we didn't actually sample anything more than a single color, but we could of! But the point is that we used the vertical and horizontal deltas for each of the triangle sides to figure out how much to step each vertical scanline step. Hence, the correct X position was what we were interpolating. Get it? It's very important that you understand the idea of interpolating since the entire texture mapping algorithm is based on it, so take you time and work through the example above with some real numbers to get a better feel for it. I always like to try an algorithm with real numbers for just a few iterations, to get a feel for it. Now let's move onto the using interpolation to texture map a one dimensional polygon and then move on to triangles in any orientation or scale. 1-D Interpolations Texture mapping a triangle with a rectangular texture map is nothing more than a lot of interpolating, but there is so much interpolating that it's easy to make a mistake and or write a slow algorithm, so let's take our time and start with the simplest case in 1 dimension. Figure 5.0 illustrates the worlds simplest texture mapper, the texture mapping of a single vertical line. In Figure 5.0 we have a texture map that is exactly one pixel thick and 8 pixels high, we want to map this into a destination polygon that is exactly one pixel thick, but any height. How do we do this? Again sampling comes to the rescue. What we need to do is "sample" the texture map which in this case is a single 1x8 pixel bitmap and map it into the destination polygon which is 1xn pixels where n can range from 1 to infinity. Take a look at Figure 5.0 for the derivation of the following examples. Example 1 As a first example, let's say that our destination polygon is 1x4 pixels. It makes sense that we want to sample the source texture every other pixel, as shown in the figure. Thus, if we select pixels (0,2,4,6) of the source texture and map them into the destination polygon at positions (0,1,2,3) then we are doing pretty good. But how did I arrive (0,2,4,6)? The answer is by using a sampling ratio which is nothing more than a an interpolation factor. Here's the math: In general, ``` sampling_ratio = source_height / destination_height ``` Thus the sampling ratio is, ``` sampling_ratio = 8/4 = 2. ``` Thus, every 1 pixel we move on the destination polygon in the vertical axis, we must move 2 pixels on the source to keep up. That's were the 2 comes from and hence the sampling sequence (0,2,4,6). If you're still with me then you should say wait a minute, we lost information! And indeed we did, we had to throw away half the pixels. This is definitely 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 your sampling (area sampling), so as to get a better approximation, but for games and real-time our technique will do. Now let's see another example of the opposite case. Example 2 In example 1, we saw that the source texture was compressed, that is, the destination was smaller than the source, thus information was lost. The second case of course would be when 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 "chunkyness" 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. Anyway, referring to the second example in Figure 5.0, we see that the source is again 1x8, but this time the destination is 1x14 pixels, yuck! Obviously, we are going to need a fractional sampling ratio, but let's let the math do it: As usual, ``` sampling_ratio = source_height / destination_height; ``` Thus the sampling ratio is, ``` sampling_ratio = 8/14 = 0.57 ``` Hence, every pixel we draw on the destination polygon we should sample it 0.57 units from the last sample point on the source. This gives us 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 ``` And to get the actual sample points, we 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 2 times, or 1/0.57 ~ 2.0. That's what I'm talking about! Multiple Interpolations When I wrote my first affine texture mapper I thought that something must be wrong since it seemed like I was interpolating everything, but the kitchen sink! However, 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 per pixel on a Pentium which translates to a theoretical max of 10 - 20 million textels (textured pixels) per second on a Pentium 100mhz which in reality will be far less than that due to a million reasons such as the caches, memory bandwidth, video card, etc. Now, let's talk about the algorithm in general and then derive the math for it. The idea behind the algorithm is that we 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. So what we need to do first is assign full texture coordinates to the vertices of the destination triangle to give us a frame of reference for the interpolants. Thus we must assign each vertex a (u,v) texture coordinate as shown in Figure 6.0. Therefore, each vertex has a total of 4 data components or it's a 4-D value -- weird huh? Moving on, let's talk about the range of the texture coordinates. Since our source texture map is 64x64 pixels that means that the texture coordinates must range from 0 - 63 for any vertex. This will map or stretch the texture map to each vertex. For example, in Figure 7.0 we see a couple examples: one triangle with 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 we would expect. In the second example in Figure 7.0 we see the same texture mapped onto 2 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 6.0, let's implement the algorithm mathematically. Note that the variable names used in the following analysis are based on Figure 6.0 and the final program, so that you can follow the program code more easily. The left edge interpolants are: ``` dxdyl = (x2 - x0)/(y2 - y0); // the x interpolant for the left hand side dudyl = (u2 - u0)/(y2 - y0); // the u interpolant for the left hand side dvdyl = (v2 - v0)/(y2 - y0); // the v interpolant for the left hand side ``` and similarly the right edge interpolants are, ``` dxdyr = (x1 - x0)/(y2 - y0); // the x interpolant for the right hand side dudyr = (u1 - u0)/(y2 - y0); // the u interpolant for the right hand side dvdyr = (v1 - v0)/(y2 - y0); // the v interpolant for the right hand side ``` Of course, there's a lot of room for optimization in the math, for example, the term (y2 - y0) is common and need only be computed once, furthermore, it's better to compute the reciprocal of (y2 - y0) and then multiply, but you get the idea. Anyway, now that we have the interpolants we are almost ready to rock. The interpolants must be in reference to some starting point, right? This starting is the topmost vertex, vertex 0. Hence, we need to start the algorithm off like this: ``` xl = x0; // the starting point for the left hand side edge x interpolation ul = u0; // the starting point for the left hand side edge u interpolation vl = v0; // the starting point for the left hand side edge v interpolation ``` And for the right hand side, ``` xr = x0; // the starting point for the right hand side edge x interpolation ur = u0; // the starting point for the right hand side edge u interpolation vr = v0; // the starting point for the right hand side edge v interpolation ``` Now we are almost ready to go, we can interpolate down the left hand edge and the right edge with: ``` xl+=dxdyl; ul+=dudyl; vl+=dvdyl; ``` and, ``` xr+=dxdyr; ur+=dudyr; vr+=dvdyr; ``` But at each point on the left and right hand edge of the triangle we still need to perform once more linear interpolation across the scanline! This is the final interpolation and the one that will give us our texture coordinates (ui,vi) which we will use as [row, column] indices into the texture bitmap to obtain the textel. All we need to do is compute the u,v coordinate on the left and right side and then use the dx to compute a linear interpolation factor for each. Here's the math:: ``` dx = (xend - xstart); // the difference or delta dx xstart = xl; // left hand starting point xend = xr; // right hand 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, we have everything we need to interpolate across the scanline at vertical position y from xstart to xend. Here's a code fragment: ``` // initialize u,v interpolants to left and right hand side values ui = 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 ``` 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 final code for the texture mapper is shown in Listing 2.0 and 3.0, the function assumes a specific input data structure and that the texture map is a linear bitmap 64x64 pixels, but other than that, it's nothing more than an implementation of our derivation here along with all the triangle cases, and clipping, so it doens't blow up. In addition, within the source file TMAPSRC.ZIP is a complete DirectX demo of the texture mapper in action -- TMAPDEMO.CPP. It draws random triangles all over the screen in 640x480x256. Listing 2.0 - Header file for Affine texture mapper. ``` // TMAPPER.H - Header file for TMAPPER.CPP, so external programs can link // DEFINES ////////////////////////////////////////////////////////////////// // defines for fixed point math #define FIXP16_SHIFT 16 #define FIXP16_MAG 65536 #define FIXP16_DP_MASK 0x0000ffff #define FIXP16_WP_MASK 0xffff0000 #define FIXP16_ROUND_UP 0x00008000 // defines for texture mapper triangular analysis #define TRI_TYPE_NONE 0 #define TRI_TYPE_FLAT_TOP 1 #define TRI_TYPE_FLAT_BOTTOM 2 #define TRI_TYPE_FLAT_MASK 3 #define TRI_TYPE_GENERAL 4 #define INTERP_LHS 0 #define INTERP_RHS 1 #define MAX_VERTICES_PER_POLY 6 // MACROS /////////////////////////////////////////////////////////////////// #define SIGN(x) ((x) > 0 ? (1) : (-1)) #define SWAP(a,b,temp) {temp = a; a=b; b=temp;} // TYPES /////////////////////////////////////////////////////////////////// // basic types typedef unsigned short USHORT; typedef unsigned short WORD; typedef unsigned char UCHAR; typedef unsigned char BYTE; // CLASSES ///////////////////////////////////////////////////////////////// // general 3D vertex class class VERTEX3D { public: float x,y,z; float u,v,i; float length(void) { return(sqrt(x*x + y*y + z*z)); } }; typedef VERTEX3D *VERTEX3D_PTR; /////////////////////////////////////////////////////////////////////////////// // general integer vertex class class VERTEXI3D { public: int x,y,z; int u,v,i; float length(void) { return(sqrt(x*x + y*y + z*z)); } }; typedef VERTEXI3D *VERTEXI3D_PTR; ///////////////////////////////////////////////////////////////////////////////// // general face class, note that 90% of this stuff isn't used, but it // gives you an idea of what the average 3D engine might keep track of... class FACE3D { public: int state; // the state of the face, visible, clipped, culled etc. int attr; // attributes of face, shading, properties etc. int num_vertices; // numer of points that make up polygon int color; // color of poly if it's flat shaded UCHAR *texture; // pointer to the texture information float nlength; // length of the normal int avg_z; // average z of vertices, used for simple sorting VERTEX3D vlist[MAX_VERTICES_PER_POLY]; // general vertex list VERTEXI3D tlist; // triangle vertex list int int form FACE3D *prev; // pointer to previous face in ADS FACE3D *next; // pointer to next face in ADS }; typedef FACE3D *FACE3D_PTR; ``` Listing 3.0 - Affine texture mapper. ``` // TMAPPER.CPP - The texture mapping function // compile this and link it to the TMAPDEMO.CPP to // make a complete executable // Affine Texture Mapper, for 256 color linear // memory 64x64 pixel texture mapping of 3 vertex polys. // there's an example at the bottom! #include // include important C/C++ stuff #include #include #include #include #include #include #include #include #include "tmapper.h" // include all the header info and classes // GLOBALS ///////////////////////////////////////////////////////////////// // the viewport to clip to, can be smaller than the screen extern int poly_clip_min_x, poly_clip_max_x, poly_clip_min_y, poly_clip_max_y; // FUNCTIONS //////////////////////////////////////////////////////////////// void Draw_Textured_Triangle(void *vface, // ptr to face UCHAR *dest_buffer, // pointer to video buffer int mem_pitch) // bytes per line, 320, 640 etc. { // this function draws a textured triangle FACE3D_PTR face; // working face int v0=0, v1=1, v2=2, temp=0, tri_type = TRI_TYPE_NONE, irestart = INTERP_LHS; int dx,dy,dyl,dyr, // general deltas u,v, du,dv, xi,yi, // the current interpolated x,y ui,vi, // the current interpolated u,v index_x,index_y, // looping vars x,y, // hold general x,y xstart, xend, ystart, yrestart, yend, xl, dxdyl, xr, dxdyr, dudyl, ul, dvdyl, vl, dudyr, ur, dvdyr, vr; int x0,y0,tu0,tv0, // cached vertices x1,y1,tu1,tv1, x2,y2,tu2,tv2; UCHAR *screen_ptr = NULL, *screen_line = NULL, *textmap = NULL; // convert void ptr to face face = (FACE3D_PTR)vface; // extract texture map textmap = face->texture; // first trivial clipping rejection tests if (((face->tlist.y < poly_clip_min_y) && (face->tlist.y < poly_clip_min_y) && (face->tlist.y < poly_clip_min_y)) || ((face->tlist.y > poly_clip_max_y) && (face->tlist.y > poly_clip_max_y) && (face->tlist.y > poly_clip_max_y)) || ((face->tlist.x < poly_clip_min_x) && (face->tlist.x < poly_clip_min_x) && (face->tlist.x < poly_clip_min_x)) || ((face->tlist.x > poly_clip_max_x) && (face->tlist.x > poly_clip_max_x) && (face->tlist.x > poly_clip_max_x))) return; // degenerate triangle if ( ((face->tlist.x==face->tlist.x) && (face->tlist.x==face->tlist.x)) || ((face->tlist.y==face->tlist.y) && (face->tlist.y==face->tlist.y))) return; // sort vertices if (face->tlist[v1].y < face->tlist[v0].y) {SWAP(v0,v1,temp);} if (face->tlist[v2].y < face->tlist[v0].y) {SWAP(v0,v2,temp);} if (face->tlist[v2].y < face->tlist[v1].y) {SWAP(v1,v2,temp);} // now test for trivial flat sided cases if (face->tlist[v0].y==face->tlist[v1].y) { // set triangle type tri_type = TRI_TYPE_FLAT_TOP; // sort vertices left to right if (face->tlist[v1].x < face->tlist[v0].x) {SWAP(v0,v1,temp);} } // end if else // now test for trivial flat sided cases if (face->tlist[v1].y==face->tlist[v2].y) { // set triangle type tri_type = TRI_TYPE_FLAT_BOTTOM; // sort vertices left to right if (face->tlist[v2].x < face->tlist[v1].x) {SWAP(v1,v2,temp);} } // end if else { // must be a general triangle tri_type = TRI_TYPE_GENERAL; } // end else // extract vertices for processing, now that we have order x0 = face->tlist[v0].x; y0 = face->tlist[v0].y; tu0 = face->tlist[v0].u; tv0 = face->tlist[v0].v; x1 = face->tlist[v1].x; y1 = face->tlist[v1].y; tu1 = face->tlist[v1].u; tv1 = face->tlist[v1].v; x2 = face->tlist[v2].x; y2 = face->tlist[v2].y; tu2 = face->tlist[v2].u; tv2 = face->tlist[v2].v; // set interpolation restart value yrestart = y1; // what kind of triangle if (tri_type & TRI_TYPE_FLAT_MASK) { if (tri_type == TRI_TYPE_FLAT_TOP) { // compute all deltas dy = (y2 - y0); dxdyl = ((x2 - x0) << FIXP16_SHIFT)/dy; dudyl = ((tu2 - tu0) << FIXP16_SHIFT)/dy; dvdyl = ((tv2 - tv0) << FIXP16_SHIFT)/dy; dxdyr = ((x2 - x1) << FIXP16_SHIFT)/dy; dudyr = ((tu2 - tu1) << FIXP16_SHIFT)/dy; dvdyr = ((tv2 - tv1) << FIXP16_SHIFT)/dy; // test for y clipping if (y0 < poly_clip_min_y) { // compute overclip dy = (poly_clip_min_y - y0); // computer new LHS starting values xl = dxdyl*dy + (x0 << FIXP16_SHIFT); ul = dudyl*dy + (tu0 << FIXP16_SHIFT); vl = dvdyl*dy + (tv0 << FIXP16_SHIFT); // compute new RHS starting values xr = dxdyr*dy + (x1 << FIXP16_SHIFT); ur = dudyr*dy + (tu1 << FIXP16_SHIFT); vr = dvdyr*dy + (tv1 << FIXP16_SHIFT); // compute new starting y ystart = poly_clip_min_y; } // end if else { // no clipping // set starting values xl = (x0 << FIXP16_SHIFT); xr = (x1 << FIXP16_SHIFT); ul = (tu0 << FIXP16_SHIFT); vl = (tv0 << FIXP16_SHIFT); ur = (tu1 << FIXP16_SHIFT); vr = (tv1 << FIXP16_SHIFT); // set starting y ystart = y0; } // end else } // end if flat top else { // must be flat bottom // compute all deltas dy = (y1 - y0); dxdyl = ((x1 - x0) << FIXP16_SHIFT)/dy; dudyl = ((tu1 - tu0) << FIXP16_SHIFT)/dy; dvdyl = ((tv1 - tv0) << FIXP16_SHIFT)/dy; dxdyr = ((x2 - x0) << FIXP16_SHIFT)/dy; dudyr = ((tu2 - tu0) << FIXP16_SHIFT)/dy; dvdyr = ((tv2 - tv0) << FIXP16_SHIFT)/dy; // test for y clipping if (y0 < poly_clip_min_y) { // compute overclip dy = (poly_clip_min_y - y0); // computer new LHS starting values xl = dxdyl*dy + (x0 << FIXP16_SHIFT); ul = dudyl*dy + (tu0 << FIXP16_SHIFT); vl = dvdyl*dy + (tv0 << FIXP16_SHIFT); // compute new RHS starting values xr = dxdyr*dy + (x0 << FIXP16_SHIFT); ur = dudyr*dy + (tu0 << FIXP16_SHIFT); vr = dvdyr*dy + (tv0 << FIXP16_SHIFT); // compute new starting y ystart = poly_clip_min_y; } // end if else { // no clipping // set starting values xl = (x0 << FIXP16_SHIFT); xr = (x0 << FIXP16_SHIFT); ul = (tu0 << FIXP16_SHIFT); vl = (tv0 << FIXP16_SHIFT); ur = (tu0 << FIXP16_SHIFT); vr = (tv0 << FIXP16_SHIFT); // set starting y ystart = y0; } // end else } // end else flat bottom // test for bottom clip, always if ((yend = y2) > poly_clip_max_y) yend = poly_clip_max_y; // test for horizontal clipping if ((x0 < poly_clip_min_x) || (x0 > poly_clip_max_x) || (x1 < poly_clip_min_x) || (x1 > poly_clip_max_x) || (x2 < poly_clip_min_x) || (x2 > poly_clip_max_x)) { // clip version // point screen ptr to starting line screen_ptr = dest_buffer + (ystart * mem_pitch); for (yi = ystart; yi<=yend; yi++) { // compute span endpoints xstart = ((xl + FIXP16_ROUND_UP) >> FIXP16_SHIFT); xend = ((xr + FIXP16_ROUND_UP) >> FIXP16_SHIFT); // compute starting points for u,v interpolants ui = ul + FIXP16_ROUND_UP; vi = vl + FIXP16_ROUND_UP; // compute u,v interpolants if ((dx = (xend - xstart))>0) { du = (ur - ul)/dx; dv = (vr - vl)/dx; } // end if else { du = (ur - ul); dv = (vr - vl); } // end else /////////////////////////////////////////////////////////////////////// // test for x clipping, LHS if (xstart < poly_clip_min_x) { // compute x overlap dx = poly_clip_min_x - xstart; // slide interpolants over ui+=dx*du; vi+=dx*dv; // reset vars xstart = poly_clip_min_x; } // end if // test for x clipping RHS if (xend > poly_clip_max_x) xend = poly_clip_max_x; /////////////////////////////////////////////////////////////////////// // draw span for (xi=xstart; xi<=xend; xi++) { // write textel screen_ptr[xi] = textmap[(ui >> FIXP16_SHIFT) + ((vi >> FIXP16_SHIFT) << 6)]; // interpolate u,v ui+=du; vi+=dv; } // end for xi // interpolate u,v,x along right and left edge xl+=dxdyl; ul+=dudyl; vl+=dvdyl; xr+=dxdyr; ur+=dudyr; vr+=dvdyr; // advance screen ptr screen_ptr+=mem_pitch; } // end for y } // end if clip else { // non-clip version // point screen ptr to starting line screen_ptr = dest_buffer + (ystart * mem_pitch); for (yi = ystart; yi<=yend; yi++) { // compute span endpoints xstart = ((xl + FIXP16_ROUND_UP) >> FIXP16_SHIFT); xend = ((xr + FIXP16_ROUND_UP) >> FIXP16_SHIFT); // compute starting points for u,v interpolants ui = ul + FIXP16_ROUND_UP; vi = vl + FIXP16_ROUND_UP; // compute u,v interpolants if ((dx = (xend - xstart))>0) { du = (ur - ul)/dx; dv = (vr - vl)/dx; } // end if else { du = (ur - ul); dv = (vr - vl); } // end else // draw span for (xi=xstart; xi<=xend; xi++) { // write textel screen_ptr[xi] = textmap[(ui >> FIXP16_SHIFT) + ((vi >> FIXP16_SHIFT) << 6)]; // interpolate u,v ui+=du; vi+=dv; } // end for xi // interpolate u,v,x along right and left edge xl+=dxdyl; ul+=dudyl; vl+=dvdyl; xr+=dxdyr; ur+=dudyr; vr+=dvdyr; // advance screen ptr screen_ptr+=mem_pitch; } // end for y } // end if non-clipped } // end if else if (tri_type==TRI_TYPE_GENERAL) { // first test for bottom clip, always if ((yend = y2) > poly_clip_max_y) yend = poly_clip_max_y; // pre-test y clipping status if (y1 < poly_clip_min_y) { // compute all deltas // LHS dyl = (y2 - y1); dxdyl = ((x2 - x1) << FIXP16_SHIFT)/dyl; dudyl = ((tu2 - tu1) << FIXP16_SHIFT)/dyl; dvdyl = ((tv2 - tv1) << FIXP16_SHIFT)/dyl; // RHS dyr = (y2 - y0); dxdyr = ((x2 - x0) << FIXP16_SHIFT)/dyr; dudyr = ((tu2 - tu0) << FIXP16_SHIFT)/dyr; dvdyr = ((tv2 - tv0) << FIXP16_SHIFT)/dyr; // compute overclip dyr = (poly_clip_min_y - y0); dyl = (poly_clip_min_y - y1); // computer new LHS starting values xl = dxdyl*dyl + (x1 << FIXP16_SHIFT); ul = dudyl*dyl + (tu1 << FIXP16_SHIFT); vl = dvdyl*dyl + (tv1 << FIXP16_SHIFT); // compute new RHS starting values xr = dxdyr*dyr + (x0 << FIXP16_SHIFT); ur = dudyr*dyr + (tu0 << FIXP16_SHIFT); vr = dvdyr*dyr + (tv0 << FIXP16_SHIFT); // compute new starting y ystart = poly_clip_min_y; // test if we need swap to keep rendering left to right if (dxdyr > dxdyl) { SWAP(dxdyl,dxdyr,temp); SWAP(dudyl,dudyr,temp); SWAP(dvdyl,dvdyr,temp); SWAP(xl,xr,temp); SWAP(ul,ur,temp); SWAP(vl,vr,temp); SWAP(x1,x2,temp); SWAP(y1,y2,temp); SWAP(tu1,tu2,temp); SWAP(tv1,tv2,temp); // set interpolation restart irestart = INTERP_RHS; } // end if } // end if else if (y0 < poly_clip_min_y) { // compute all deltas // LHS dyl = (y1 - y0); dxdyl = ((x1 - x0) << FIXP16_SHIFT)/dyl; dudyl = ((tu1 - tu0) << FIXP16_SHIFT)/dyl; dvdyl = ((tv1 - tv0) << FIXP16_SHIFT)/dyl; // RHS dyr = (y2 - y0); dxdyr = ((x2 - x0) << FIXP16_SHIFT)/dyr; dudyr = ((tu2 - tu0) << FIXP16_SHIFT)/dyr; dvdyr = ((tv2 - tv0) << FIXP16_SHIFT)/dyr; // compute overclip dy = (poly_clip_min_y - y0); // computer new LHS starting values xl = dxdyl*dy + (x0 << FIXP16_SHIFT); ul = dudyl*dy + (tu0 << FIXP16_SHIFT); vl = dvdyl*dy + (tv0 << FIXP16_SHIFT); // compute new RHS starting values xr = dxdyr*dy + (x0 << FIXP16_SHIFT); ur = dudyr*dy + (tu0 << FIXP16_SHIFT); vr = dvdyr*dy + (tv0 << FIXP16_SHIFT); // compute new starting y ystart = poly_clip_min_y; // test if we need swap to keep rendering left to right if (dxdyr < dxdyl) { SWAP(dxdyl,dxdyr,temp); SWAP(dudyl,dudyr,temp); SWAP(dvdyl,dvdyr,temp); SWAP(xl,xr,temp); SWAP(ul,ur,temp); SWAP(vl,vr,temp); SWAP(x1,x2,temp); SWAP(y1,y2,temp); SWAP(tu1,tu2,temp); SWAP(tv1,tv2,temp); // set interpolation restart irestart = INTERP_RHS; } // end if } // end if else { // no initial y clipping // compute all deltas // LHS dyl = (y1 - y0); dxdyl = ((x1 - x0) << FIXP16_SHIFT)/dyl; dudyl = ((tu1 - tu0) << FIXP16_SHIFT)/dyl; dvdyl = ((tv1 - tv0) << FIXP16_SHIFT)/dyl; // RHS dyr = (y2 - y0); dxdyr = ((x2 - x0) << FIXP16_SHIFT)/dyr; dudyr = ((tu2 - tu0) << FIXP16_SHIFT)/dyr; dvdyr = ((tv2 - tv0) << FIXP16_SHIFT)/dyr; // no clipping y // set starting values xl = (x0 << FIXP16_SHIFT); xr = (x0 << FIXP16_SHIFT); ul = (tu0 << FIXP16_SHIFT); vl = (tv0 << FIXP16_SHIFT); ur = (tu0 << FIXP16_SHIFT); vr = (tv0 << FIXP16_SHIFT); // set starting y ystart = y0; // test if we need swap to keep rendering left to right if (dxdyr < dxdyl) { SWAP(dxdyl,dxdyr,temp); SWAP(dudyl,dudyr,temp); SWAP(dvdyl,dvdyr,temp); SWAP(xl,xr,temp); SWAP(ul,ur,temp); SWAP(vl,vr,temp); SWAP(x1,x2,temp); SWAP(y1,y2,temp); SWAP(tu1,tu2,temp); SWAP(tv1,tv2,temp); // set interpolation restart irestart = INTERP_RHS; } // end if } // end else // test for horizontal clipping if ((x0 < poly_clip_min_x) || (x0 > poly_clip_max_x) || (x1 < poly_clip_min_x) || (x1 > poly_clip_max_x) || (x2 < poly_clip_min_x) || (x2 > poly_clip_max_x)) { // clip version // x clipping // point screen ptr to starting line screen_ptr = dest_buffer + (ystart * mem_pitch); for (yi = ystart; yi<=yend; yi++) { // compute span endpoints xstart = ((xl + FIXP16_ROUND_UP) >> FIXP16_SHIFT); xend = ((xr + FIXP16_ROUND_UP) >> FIXP16_SHIFT); // compute starting points for u,v interpolants ui = ul + FIXP16_ROUND_UP; vi = vl + FIXP16_ROUND_UP; // compute u,v interpolants if ((dx = (xend - xstart))>0) { du = (ur - ul)/dx; dv = (vr - vl)/dx; } // end if else { du = (ur - ul); dv = (vr - vl); } // end else /////////////////////////////////////////////////////////////////////// // test for x clipping, LHS if (xstart < poly_clip_min_x) { // compute x overlap dx = poly_clip_min_x - xstart; // slide interpolants over ui+=dx*du; vi+=dx*dv; // set x to left clip edge xstart = poly_clip_min_x; } // end if // test for x clipping RHS if (xend > poly_clip_max_x) xend = poly_clip_max_x; /////////////////////////////////////////////////////////////////////// // draw span for (xi=xstart; xi<=xend; xi++) { // write textel screen_ptr[xi] = textmap[(ui >> FIXP16_SHIFT) + ((vi >> FIXP16_SHIFT) << 6)]; // interpolate u,v ui+=du; vi+=dv; } // end for xi // interpolate u,v,x along right and left edge xl+=dxdyl; ul+=dudyl; vl+=dvdyl; xr+=dxdyr; ur+=dudyr; vr+=dvdyr; // advance screen ptr screen_ptr+=mem_pitch; // test for yi hitting second region, if so change interpolant if (yi==yrestart) { // test interpolation side change flag if (irestart == INTERP_LHS) { // LHS dyl = (y2 - y1); dxdyl = ((x2 - x1) << FIXP16_SHIFT)/dyl; dudyl = ((tu2 - tu1) << FIXP16_SHIFT)/dyl; dvdyl = ((tv2 - tv1) << FIXP16_SHIFT)/dyl; // set starting values xl = (x1 << FIXP16_SHIFT); ul = (tu1 << FIXP16_SHIFT); vl = (tv1 << FIXP16_SHIFT); // interpolate down on LHS to even up xl+=dxdyl; ul+=dudyl; vl+=dvdyl; } // end if else { // RHS dyr = (y1 - y2); dxdyr = ((x1 - x2) << FIXP16_SHIFT)/dyr; dudyr = ((tu1 - tu2) << FIXP16_SHIFT)/dyr; dvdyr = ((tv1 - tv2) << FIXP16_SHIFT)/dyr; // set starting values xr = (x2 << FIXP16_SHIFT); ur = (tu2 << FIXP16_SHIFT); vr = (tv2 << FIXP16_SHIFT); // interpolate down on RHS to even up xr+=dxdyr; ur+=dudyr; vr+=dvdyr; } // end else } // end if } // end for y } // end if else { // no x clipping // point screen ptr to starting line screen_ptr = dest_buffer + (ystart * mem_pitch); for (yi = ystart; yi<=yend; yi++) { // compute span endpoints xstart = ((xl + FIXP16_ROUND_UP) >> FIXP16_SHIFT); xend = ((xr + FIXP16_ROUND_UP) >> FIXP16_SHIFT); // compute starting points for u,v interpolants ui = ul + FIXP16_ROUND_UP; vi = vl + FIXP16_ROUND_UP; // compute u,v interpolants if ((dx = (xend - xstart))>0) { du = (ur - ul)/dx; dv = (vr - vl)/dx; } // end if else { du = (ur - ul); dv = (vr - vl); } // end else // draw span for (xi=xstart; xi<=xend; xi++) { // write textel screen_ptr[xi] = textmap[(ui >> FIXP16_SHIFT) + ((vi >> FIXP16_SHIFT) << 6)]; // interpolate u,v ui+=du; vi+=dv; } // end for xi // interpolate u,v,x along right and left edge xl+=dxdyl; ul+=dudyl; vl+=dvdyl; xr+=dxdyr; ur+=dudyr; vr+=dvdyr; // advance screen ptr screen_ptr+=mem_pitch; // test for yi hitting second region, if so change interpolant if (yi==yrestart) { // test interpolation side change flag if (irestart == INTERP_LHS) { // LHS dyl = (y2 - y1); dxdyl = ((x2 - x1) << FIXP16_SHIFT)/dyl; dudyl = ((tu2 - tu1) << FIXP16_SHIFT)/dyl; dvdyl = ((tv2 - tv1) << FIXP16_SHIFT)/dyl; // set starting values xl = (x1 << FIXP16_SHIFT); ul = (tu1 << FIXP16_SHIFT); vl = (tv1 << FIXP16_SHIFT); // interpolate down on LHS to even up xl+=dxdyl; ul+=dudyl; vl+=dvdyl; } // end if else { // RHS dyr = (y1 - y2); dxdyr = ((x1 - x2) << FIXP16_SHIFT)/dyr; dudyr = ((tu1 - tu2) << FIXP16_SHIFT)/dyr; dvdyr = ((tv1 - tv2) << FIXP16_SHIFT)/dyr; // set starting values xr = (x2 << FIXP16_SHIFT); ur = (tu2 << FIXP16_SHIFT); vr = (tv2 << FIXP16_SHIFT); // interpolate down on RHS to even up xr+=dxdyr; ur+=dudyr; vr+=dvdyr; } // end else } // end if } // end for y } // end else } // end if } // end Draw_Textured_Triangle /******************************* EXAMPLE *********************************** This is the setup: To create a single triangle to be rendered consisting of the 3 points (in CC order I think): (x0,y0,u0,v0) (x1,y1,u1,v1) (x2,y2,u2,v2) 64x64 texture at address texture_buffer in row major form FACE3D face; // the triangle object // set up the vertices face.tlist.x = x0; face.tlist.y = y0; face.tlist.u = u0; face.tlist.v = v0; face.tlist.x = x1; face.tlist.y = y1; face.tlist.u = u1; face.tlist.v = v1; face.tlist.x = x2; face.tlist.y = y2; face.tlist.u = u2; face.tlist.v = v2; // assign the texture to your 64x64 texture map buffer face.texture = texture_buffer; // set the clipping coords of the desired 2D viewport poly_clip_min_x = 0; poly_clip_max_x = 0; poly_clip_min_y = SCREEN_WIDTH-1; poly_clip_max_y = SCREEN_HEIGHT-1 // then draw the triangle to the rendering buffer Draw_Textured_Triangle((void *)&face, double_buffer, memory_pitch); ***************************************************************************/ ``` If you don't want to type the code, you can find it along with the executable within TMAPSRC.ZIP which you can download by clicking on the main menu control to the left. In addition, the demo uses fixed point math even though we used floating point here. I have found that all math should be done using floating point, until final rasterization (as in this case) since the conversion from floating point to integer and visa-versa kills you. Finally, as a test of the texture mapper, I gave it to a friend of mine -- Jarrod Davis and he created a 3D demo by adding the texture mapper to his flat shaded 3D engine, thanks Jarrod. The demo is called BOX2.EXE and is within the TMAPSRC.ZIP archive file as well, so enjoy. Well, that's it for texture mapping. Maybe next time we can talk about lighting those texture mapped polygons... Discuss this article in the forums Date this article was posted to GameDev.net: 11/18/1999 (Note that this date does not necessarily correspond to the date the article was written) See Also: Texture Mapping © 1999-2011 Gamedev.net. All rights reserved. Terms of Use Privacy Policy Comments? Questions? Feedback? Click here!