Texture Mapping
Trying to make your real-time 3D animations look real? This discussion of texture mapping, along with the example diceroll.exe, might do the trick.
Any image can be applied to the face of a polygon and then rotated in three dimensions - like gluing a picture onto a block of wood. In computer graphics this process is called 'texture mapping'. The image is the texture, and it's mapped onto the surface of the polygon. The procedure for doing this is simpler than many books would have you believe. The key concept is proportion.
Imagine a point somewhere along a line segment. Now rotate the line so that it tilts toward you and appears to get shorter. The distance the point is from the end of the line also appears to get shorter. Ignoring the effects of perspective, this apparent distance is a fixed proportion of the apparent length of the line no matter how it's tilted.
Now imagine that the line is the edge of a polygon that has been rotated and tilted in three dimensions, as shown by the line SR in the diagram below, and that the point G is a pixel that you want to display on the screen. What color is it?
Rotated and tilted polygon Unrotated texture map
to be displayed
P
/ \ h
/ \ pixel p ____________________ q
/ \ colors | / |
/ \ <-------- | / |
S / \ | / |
\ \ | / |
G \--------------\ H | / |
\ \ | / |
\ \ | D / |
\ \ Q | / |
\ / | / |
\ / | / |
\ / | / |
\ / |___/________________|
\/ s g r
R
To determine the color of the pixel to display, we must find the corresponding pixel in the texture map and use its color. In the diagram, the corresponding pixel is g. This is the same proportional distance along the edge sr as the pixel we want to display (G) is along its edge SR. Here's an equation that represents this:
R - G r - g
------- = -------
R - S r - s
The coordinates of points (and the ends of line segments) can be broken down into their x and y components. The coordinates of point R are Rx and Ry, the coordinates of point s are sx and sy, and so forth. Now we can write equations using known values to calculate gx and gy. We'll start by calculating gx.
Rx - Gx rx - gx
--------- = ---------
Rx - Sx rx - sx
Rewriting this in computer-friendly notation:
(Rx-Gx) / (Rx-Sx) = (rx-gx) / (rx-sx)
Doing a little algebra:
(Rx-Gx) / (Rx-Sx) * (rx-sx) = (rx-gx)
gx = -(Rx-Gx) / (Rx-Sx) * (rx-sx) + rx
gx = (Gx-Rx) / (Rx-Sx) * (rx-sx) + rx
gx = (Gx-Rx) / (Sx-Rx) * (sx-rx) + rx
The same method is used to calculate gy:
(Ry-Gy) / (Ry-Sy) = (ry-gy) / (ry-sy)
gy = (Gy-Ry) / (Sy-Ry) * (sy-ry) + ry
With values for gx and gy, we can look up the color in the texture map and use it to plot the pixel at Gx,Gy in our 3D image.
We now know how to find the colors of any pixels along the edges of a polygon, but what about the pixels in the middle? If you need more edges, just slice up the polygon. For example, the point on the opposite edge from G is H. The corresponding point in the texture map (h) can be found like before:
hx = (Hx-Qx) / (Px-Qx) * (px-qx) + qx
hy = (Hy-Qy) / (Py-Qy) * (py-qy) + qy
Now all the pixels along the line between G and H can be displayed just like is was another edge. Horizontal slices (raster scan lines) are used to efficiently plot the pixels in the middle of the polygon.
That's all there is to it! The rest is just refining and optimizing this basic idea.
Refining & Optimizing
Since we're doing real-time graphics, we're obsessed with speed. If we need to run through the above calculations for every pixel, we're going to need a supercomputer. Fortunately the calculations can be streamlined quite a bit. Once you know where a pixel is in the texture map, it's easy to find the next pixel.
Suppose we're plotting pixels along the line between G and H, then we need to look up the colors of the pixels along the line between g and h in the texture map. If we know the distance on the texture map that corresponds to the distance between pixels plotted for the 3D image, we can simply add it and step through the texture map. This is a considerable savings in calculations and in time.
Let D be the distance between the points g and h.
D = Sqrt( (hx-gx)^2 + (hy-gy)^2 )
Let d be the amount to step in the texture map for each horizontal pixel plotted in the rotated and tilted polygon.
d / D = 1 / (H-G)
d = D / (H-G)
Let dx be the x component of the step d, and dy be the y component.
dx / d = (hx-gx) / D
dx = d * (hx-gx) / D
Substituting for d, and using the x components for H and G:
dx = D / (H-G) * (hx-gx) / D = (hx-gx) / (Hx-Gx)
Fortunately the D's, which require a square-root calculation, divide out.
The calculation for the y component is similar:
dy = d * (hy-gy) / D
dy = D / (H-G) * (hy-gy) / D = (hy-gy) / (Hx-Gx)
Now we have dx and dy for stepping through the texture map. There's just one little problem: Some of these calculations can give divide-by-zero errors. For instance when Hx = Gx:
/ (Hx-Gx):
If Hx = Gx, the plotted horizontal line would only be one pixel long. However if we don't plot this pixel, it not only solves the divide-by-zero problem, but also solves another problem where pixels are plotted twice for polygons that are side by side. We shouldn't plot pixels on the right or bottom edges of a polygon. Normally it doesn't matter if pixels are plotted on top of each other, it's just redundant, but if a polygon is semitransparent, (such as a colored lens) the overlapping pixels will be noticeable.
/ (Sy-Ry) and / (Py-Qy):
We don't plot horizontal lines from (or to) horizontal edges. Thus this divide-by-zero problem never occurs.
/ (Sx-Rx):
If Sx = Rx, the edge RS of the rotated 3D polygon is straight up and down. This problem is solved by replacing (Gx-Rx) / (Sx-Rx) with (Gy-Ry) / (Sy-Ry). The two equations are equal since they are ratios of the corresponding sides of similar triangles, as shown in this diagram:
S
/|
/ |
/ |
/ |
/ |
/ |
/ | Sy-Ry
G / |
/| |
/ | |
/ | Gy-Ry |
/ | |
/________|_______________|
R Gx-Rx
|<--------- Sx-Rx ------->|
/ (Px-Qx):
This is solved the same way as above by replacing (Hx-Qx) / (Px-Qx) with (Hy-Qy) / (Py-Qy).
The Code
Here's a sketch of a routine to apply these calculations. This simplified version only works for the part of the polygon between the points S and Q.
for Y:= Sy to Qy-1 do For all the horizontal scan lines...
Gx:= Table(Y,0) Look up x coordinates of line to plot
Hx:= Table(Y,1) (Table is generated by the routine BuildLine
which slices the polygon into horiz. lines)
Gy:= Y The plotted line will be horizontal
Hy:= Y
Cg:= (Gy-Ry) / (Sy-Ry) Relative position of line to plot from
Ch:= (Hy-Qy) / (Py-Qy) the end points of the edges RS and PQ
gx:= Cg * (sx-rx) + rx Points in the texture map corresponding to
gy:= Cg * (sy-ry) + ry the left end of the line to plot
hx:= Ch * (px-qx) + qx Points on the right end
hy:= Ch * (py-qy) + qy
if Gx <> Hx then Plotted (horizontal) line has length > 0
dx:= (hx-gx) / (Hx-Gx) Amount to move in texture map for each pixel
dy:= (hy-gy) / (Hx-Gx) plotted on the display
x:= gx Initialize coordinates for starting location
y:= gy in the texture map
for X:= Gx to Hx-1 do Step one pixel at a time horizontally
Color:= Texture(x,y) Get color from texture map
Screen(X, Y, Color) Plot this color along the horizontal line
x:= x + dx Get coordinates of next pixel in texture map
y:= y + dy
Note that the innermost loop has very few calculations, and thus is fast.
Conclusion
This should get you started. The details are in the source code of the accompanying program, diceroll.xpl. At least give it a spin (by running the .exe).
Diceroll is written in a dialect of Pascal called XPL0. You can see how it's compiled by looking at diceroll.asm. Complete details about the XPL0 language, including the compiler, are available at: http://www.idcomm.com/personal/lorenblaney
You'll probably want to extend the ideas introduced here. The 'polygon' we've been talking about is actually just a square (which forms the face of the die). Triangles are usually used instead (because they're always flat), and the texture image is usually mapped over many triangles rather than a single polygon. You'll probably also want to add a lighting model, using a color remapping table, to provide shadows and highlights.
Boreal
aka: Loren Blaney
loren_blaney@idcomm.com