📄 tmapmania.htm
字号:
<HTML>
<HEAD>
<META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=windows-1252">
<META NAME="Generator" CONTENT="Microsoft Word 97">
<TITLE>Texture Mapping Mania</TITLE>
<META NAME="Template" CONTENT="C:\PROGRAM FILES\MICROSOFT OFFICE\OFFICE\html.dot">
</HEAD>
<BODY LINK="#0000ff" VLINK="#800080">
<B><FONT SIZE=5><P>Texture Mapping Mania</P>
</B></FONT><FONT SIZE=2><P>by Andre' LaMothe</P>
<P> </P>
<P> </P>
<P>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 <I>Defender.</I> 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. </P>
</FONT><P><IMG SRC="Image47.gif" WIDTH=576 HEIGHT=432><FONT SIZE=2>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. </P>
<P>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.</P>
<P>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! </P>
</FONT><B><FONT SIZE=4><P>What's In It For Me?</P>
</B></FONT><FONT SIZE=2><P>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.</P>
</FONT><P><IMG SRC="Image48.gif" WIDTH=576 HEIGHT=432></P>
<B><FONT SIZE=4><P>Getting Down To Specifics </P>
</B></FONT><FONT SIZE=2><P>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.</P>
</FONT><P><IMG SRC="Image49.gif" WIDTH=576 HEIGHT=432></P>
<FONT SIZE=2><P>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:</P>
<P>Type 1: Flat Top 		- A triangle with a flat top.</P>
<P>Type 2: Flat Bottom 	- A triangle with a flat top.</P>
<P>Type 3: General 		- A general triangle with neither a flat top or bottom.</P>
<P> </P>
<P>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.</P>
</FONT><P><IMG SRC="Image50.gif" WIDTH=576 HEIGHT=432></P>
<B><FONT SIZE=4><P>Interpolate Me Baby!</P>
</B></FONT><FONT SIZE=2><P>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.</P>
<P>Finding these points is nothing more than interpolating the slope (well almost) of each side of the triangle. The interpolation is done as follows:</P>
<P>We know that the height of the triangle is:</P>
</FONT><FONT FACE="Courier New" SIZE=1><P>dy = (y2 - y0) ; </P>
</FONT><FONT SIZE=2><P>And the difference in X's between the lower left vertex and the lower right vertex is:</P>
</FONT><FONT FACE="Courier New" SIZE=1><P>dx_left_side 	= (x2 - x0); </P>
<P>dx_right_side 	= (x1 - x0); </P>
</FONT><FONT SIZE=2><P>Thus, the slope of the left hand side is:</P>
</FONT><FONT FACE="Courier New" SIZE=1><P>slope_left_side = dy/dx_left_side = (y2 - y0)/(x2 - x0);</P>
</FONT><FONT SIZE=2><P>And, the slope of the right hand side is:</P>
</FONT><FONT FACE="Courier New" SIZE=1><P>slope_right_side = dy/dx_right_side = (y2 - y0)/(x1 - x0);</P>
</FONT><FONT SIZE=2><P>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:</P>
</FONT><FONT FACE="Courier New" SIZE=1><P>dx_left_side = 1 * (x2 - x0)/(y2 - y0);</P>
</FONT><FONT SIZE=2><P>and,</P>
</FONT><FONT FACE="Courier New" SIZE=1><P>dx_right_side = 1 * (x1 - x0)/(y2 - y0);</P>
</FONT><FONT SIZE=2><P>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.</P>
<P>Listing 1.0 - Pseudo Code Implementation of Triangle Renderer</P>
</FONT><FONT FACE="Courier New" SIZE=1><P>void Draw_Triangle(float x0,float y0,float x1,float y1,float x2,float y2, int color)</P>
<P>{</P>
<P>// this function rasterizes a triangle with a flat bottom</P>
<P>// compute left side interpolant</P>
<P>float dx_left = (x2 - x0)/(y2 - y0);</P>
<P>// compute right side interpolant</P>
<P>float dx_right = (x1 - x0)/(y2 - y0);</P>
<P>// seed left and right hand interpolators</P>
<P>float x_left = x0; </P>
<P>float x_right = x0;</P>
<P>// enter into rasterization loop</P>
<P>for (int y=y0; y<=y1; y++)</P>
<P>{</P>
<P>// draw the scanline</P>
<P>Draw_Line(x_left, x_right, y, color); </P>
<P>// advance interpolants</P>
<P>x_left+=dx_left;</P>
<P>x_right+=dx_right;</P>
<P>} // end for y</P>
<P>} // end Draw_Triangle</P>
</FONT><FONT SIZE=2><P>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? </P>
<P>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.</P>
</FONT><P><IMG SRC="Image51.gif" WIDTH=576 HEIGHT=432></P>
<B><FONT SIZE=4><P>1-D Interpolations</P>
</B></FONT><FONT SIZE=2><P>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. </P>
<P>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. </P>
<B><P>Example 1</P>
</B><P>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 <I>sampling ratio</I> which is nothing more than a an interpolation factor. Here's the math:</P>
<P>In general,</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/4 = 2.</P>
</FONT><FONT SIZE=2><P>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.</P>
<B><P>Example 2</P>
</B><P>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:</P>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -