tmapmania.htm

关于windows游戏编程的一些文章还有相关图形

<P>As usual,</P>
</FONT><FONT FACE="Courier New" SIZE=1><P>sampling_ratio = source_height / destination_height;</P>
</FONT><FONT SIZE=2><P>Thus the sampling ratio is,</P>
</FONT><FONT FACE="Courier New" SIZE=1><P>sampling_ratio = 8/14 = 0.57</P>
</FONT><FONT SIZE=2><P>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): </P>
</FONT><FONT FACE="Courier New" SIZE=1><P>Sample 0: 0.57</P>
<P>Sample 1: 1.14</P>
<P>Sample 2: 1.71</P>
<P>Sample 3: 2.28</P>
<P>Sample 4: 2.85</P>
<P>Sample 5: 3.42</P>
<P>Sample 6: 3.99</P>
<P>Sample 7: 4.56</P>
<P>Sample 8: 5.13</P>
<P>Sample 9: 5.7</P>
<P>Sample 10: 6.27</P>
<P>Sample 11: 6.84 </P>
<P>Sample 12: 7.41</P>
<P>Sample 13: 7.98</P>
</FONT><FONT SIZE=2><P>And to get the actual sample points, we simply truncate the sample points in integer space or take the <I>floor</I> 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!</P>
</FONT><B><FONT SIZE=4><P>Multiple Interpolations</P>
</B></FONT><FONT SIZE=2><P>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. </P>
</FONT><P><IMG SRC="Image52.gif" WIDTH=576 HEIGHT=432></P>
<FONT SIZE=2><P>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.</P>
</FONT><P><IMG SRC="Image53.gif" WIDTH=576 HEIGHT=432></P>
<FONT SIZE=2><P>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. <I>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.</P>
</I><P>The left edge interpolants are:</P>
</FONT><FONT FACE="Courier New" SIZE=1><P>dxdyl&#9;= (x2 - x0)/(y2 - y0); // the x interpolant for the left hand side</P>
<P>dudyl &#9;= (u2 - u0)/(y2 - y0); // the u interpolant for the left hand side</P>
<P>dvdyl &#9;= (v2 - v0)/(y2 - y0); // the v interpolant for the left hand side</P>
</FONT><FONT SIZE=2><P>and similarly the right edge interpolants are,</P>
</FONT><FONT FACE="Courier New" SIZE=1><P>dxdyr&#9;= (x1 - x0)/(y2 - y0); // the x interpolant for the right hand side</P>
<P>dudyr &#9;= (u1 - u0)/(y2 - y0); // the u interpolant for the right hand side</P>
<P>dvdyr &#9;= (v1 - v0)/(y2 - y0); // the v interpolant for the right hand side</P>
</FONT><FONT SIZE=2><P>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:</P>
</FONT><FONT FACE="Courier New" SIZE=1><P>xl = x0; // the starting point for the left hand side edge x interpolation</P>
<P>ul = u0; // the starting point for the left hand side edge u interpolation</P>
<P>vl = v0; // the starting point for the left hand side edge v interpolation</P>
</FONT><FONT SIZE=2><P>And for the right hand side,</P>
</FONT><FONT FACE="Courier New" SIZE=1><P>xr = x0; // the starting point for the right hand side edge x interpolation</P>
<P>ur = u0; // the starting point for the right hand side edge u interpolation</P>
<P>vr = v0; // the starting point for the right hand side edge v interpolation</P>
</FONT><FONT SIZE=2><P>Now we are almost ready to go, we can interpolate down the left hand edge and the right edge with:</P>
</FONT><FONT FACE="Courier New" SIZE=1><P>xl+=dxdyl;</P>
<P>ul+=dudyl;</P>
<P>vl+=dvdyl;</P>
</FONT><FONT SIZE=2><P>and,</P>
</FONT><FONT FACE="Courier New" SIZE=1><P>xr+=dxdyr;</P>
<P>ur+=dudyr;</P>
<P>vr+=dvdyr;</P>
</FONT><FONT SIZE=2><P>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::</P>
</FONT><FONT FACE="Courier New" SIZE=1><P>dx = (xend - xstart); // the difference or delta dx</P>
<P>xstart = xl; &#9;&#9;// left hand starting point</P>
<P>xend = xr; &#9;&#9;// right hand starting point</P>
</FONT><FONT SIZE=2><P>Therefore, the interpolants across each scanline in u,v space are,</P>
</FONT><FONT FACE="Courier New" SIZE=1><P>du = (ul - ur)/dx; </P>
<P>dv = (vl - vr)/dx;</P>
</FONT><FONT SIZE=2><P>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:</P>
</FONT><FONT FACE="Courier New" SIZE=1><P>// initialize u,v interpolants to left and right hand side values</P>
<P>ui = ul;</P>
<P>vi = vl;</P>
<P>// now interpolate from left to right, i.e, in a positive x direction</P>
<P>for (x = xstart; x &lt;= xend; x++)</P>
<P>{</P>
<P>// get texture pixel value</P>
<P>pixel = texture_map[ui][vi];</P>
<P>// plot pixel at x,y</P>
<P>Plot_Pixel(x,y,pixel);</P>
<P>// advance u,v interpolants</P>
<P>ui+=du; </P>
<P>vi+=dv;</P>
<P>} // end for x</P>
</FONT><FONT SIZE=2><P>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. </P>
<P>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, Listing 4.0 is a complete DirectX demo of the texture mapper in action. It draws random triangles all over the screen in 640x480x256. </P>
<B><P>Listing 2.0 - Header file for Affine texture mapper. <U>(production insert tmapper.h)</P>
</U><P>Listing 3.0 - Affine texture mapper.</B> <B><U>(production - insert tmapper.cpp)</P>
</U><P>Listing 4.0 - A complete DirectX demo of the texture mapper.</B> <B><U>(production - insert tmapdemo.cpp)</P>
</B></U><P>If you don't want to type the code, you can find it along with the executable within <B>TMAPSRC.ZIP </B>which you can download from <B><U>(production insert FTP url here). </B></U>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 -- <B>Jarrod Davis</B> and he created a 3D demo by adding the texture mapper to his flat shaded 3D engine, thanks Jarrod. The demo is called <B>BOX2.EXE</B> and is within the <B>TMAPSRC.ZIP</B> archive file as well, so enjoy.</P>
<P>Well, that's it for texture mapping. Maybe next time we can talk about lighting those texture mapped polygons...</P>
<P>&nbsp;</P>
<P>&nbsp;</P></FONT></BODY>
</HTML>