WGT Graphics Tutorial #3
Topic: Texture Mapped Polygons
By Chris Egerter
December 8, 1994
Contact me at: chris.egerter@homebase.com
Compuserve: 75242,2411
Introduction
------------
This series of tutorials describes a method of drawing filled polygons
using 3 rendering techniques: Solid, Gouraud shading, and texture mapping.
The code in this tutorial was written in Turbo C++ but can be ported to
other graphics libraries and operating systems. I did not use the
WGT functions in this one, so the wgtgfx.c file contains a few routines
which are needed for the demos. I have decided to explain the method
used for these routines since I had to discover them on my own, and
think you can learn from the code.
1.0 - From Gouraud to Texture
-----------------------------
If you haven't read the previous tutorials, please read them first since
they provide the basic ideas for filling polygons. In the last issue I
mentioned that texture mapping is only slightly different from shading.
This may not seem very obvious to you, so I'll explain.
When we scan converted the Gouraud shaded edges, we kept track of the
starting and ending color on each horizontal line. Texture mapping is
the same, only we need to keep track of X and Y coordinates instead of
a color. In place of a start and end color, we can get a (x,y) coordinate
at each end of the line. Let's modify our point structure to store
coordinates:
typedef struct
{
int x,y;
int sx, sy; /* Source coordinates from the texture image */
} tpoint;
sx and sy is a location on another image, which is associated with a
vertex of the polygon. They are commonly called u and v coordiantes in
graphics texts.
When we converted the polygon into a list of x coordinates, we stored them
into 4 arrays, startx and endx, startcol and endcol. With texture mapping
we need to remove the color array, and replace it with startx,
starty, endx and endy. I've decided to make this into a structure
to keep things a bit cleaner.
struct {
int startx; /* The first X coord */
int endx; /* The last X coord */
int x1; /* First pixel coord out of texture */
int y1;
int x2; /* Last pixel coord out of texture */
int y2;
} texturepoint[200]; /* One for each scan line (320x200x256) */
When the list is created, we will have two screen x coordinates,
two x texture coordinates, and two y texture coordinates.
The gpolyline routine becomes the tpolyline routine, which calculates
the texture coordinates at the ends of each horizontal line. To do this,
we use fixed point math in the same way as the Gouraud routine, only
we step along the x and y at the same time.
void tpolyline (int x1, int y1, int tx1, int ty1, int x2, int y2,
int tx2, int ty2)
/* Calculates the coordinates of a line given two
vertices, (x1,y1) with texture coordinates (tx1, ty1), and
(x2, y2) with texture coordinates (tx2,ty2).
We will use fixed point math to speed things up.
The x coordinate is multiplied by 256 and for each row,
a constant m is added to x. This is a simplified version
of a line algorithm because we only have to store 1 x coordinate
for every y coordinate.
The texture coordinates increase by a step value based on the
number of pixels between the texture coordinates and the distance between
the screen y coordinates.
*/
{
int tmp,y;
long x,m;
long xcoord, xstep; /* X texture coordinate, and step value */
long ycoord, ystep; /* Y texture coordinate, and step value */
if (y2 != y1) /* This isn't a horizontal line */
{
if (y2 < y1) /* Make sure y2 is greater than y1 */
{
tmp = y1; /* Swap the y coordinate */
y1 = y2;
y2 = tmp;
tmp = x1; /* Swap the corresponding x coordinates */
x1 = x2;
x2 = tmp;
tmp = tx1; /* Swap the corresponding x values */
tx1 = tx2;
tx2 = tmp;
tmp = ty1; /* Swap the corresponding y values */
ty1 = ty2;
ty2 = tmp;
}
x = (long)x1<<8; /* Multiply by 256 */
m = ((long)(x2 - x1)<<8) / ((long)(y2 - y1));
/* m is the fractional amount to add to the x coordinate every row.
m is equal to (delta x) / (delta y). In other words, the x coordinate
has to change by (x2 - x1) columns in (y2 - y1) rows. */
xcoord = (long)tx1 << 8; /* Initial x coord in 8.8 fixed point format */
xstep = ((long)(tx2 - tx1) << 8) / ((long)(y2 - y1));
/* Calculate the x step value */
ycoord = (long)ty1 << 8; /* Initial y coord in 8.8 fixed point format */
ystep = ((long)(ty2 - ty1) << 8) / ((long)(y2 - y1));
/* Calculate the y step value */
x += m; /* We ALWAYS skip the first point in every line. This is done */
y1++; /* because we do not want to store the point where two lines
meet, twice. This would result in a single point being drawn. */
for (y = y1; y <= y2; y++) /* Go through each row */
{
if ((y >= 0) & (y < 200)) /* If the coordinate is on the screen */
if (texturepoint[y].startx == -16000) /* Store the first coordinate */
{
texturepoint[y].startx = x >> 8; /* Store the first coordinate */
texturepoint[y].x1 = xcoord >> 8;
texturepoint[y].y1 = ycoord >> 8;
}
else
{
texturepoint[y].endx = x >> 8; /* Store the last coordinate */
texturepoint[y].x2 = xcoord >> 8;
texturepoint[y].y2 = ycoord >> 8;
}
x += m; /* Add our constant to x */
xcoord += xstep; /* Add our x step value to the texture */
ycoord += ystep; /* Add our y step value to the texture */
}
}
}
Next we have the actual texture mapping routine that calls the previous
routine and draws the polygon.
void texturedpoly (tpoint *vertexlist, int numvertex)
/* Draws a textured polygon given an array of vertices. */
{
int i;
tpoint *curpt,*nextpt;
/* Two pointers to a vertex. These are used to connect to vertices
together in when calling the gpolyline routine. */
curpt = vertexlist; /* Set to the first vertex in the array */
nextpt = vertexlist + 1; /* and to the second vertex */
for (i = 0; i < 200; i++)
{
texturepoint[i].startx = -16000; /* Set up our impossible values */
texturepoint[i].endx = -16000;
}
for (i = 1; i < numvertex; i++)
{
tpolyline (curpt->x, curpt->y, curpt->sx, curpt->sy,
nextpt->x, nextpt->y, nextpt->sx, nextpt->sy);
/* Calculate the edge of this line. */
curpt += 1; /* Go to the next line */
nextpt += 1;
}
nextpt = vertexlist; /* Now close the polygon by doing a line between
the first and last vertex. */
tpolyline (curpt->x, curpt->y, curpt->sx, curpt->sy,
nextpt->x, nextpt->y, nextpt->sx, nextpt->sy);
for (i = 0; i < 200; i++) /* Now draw the horizontal line list */
if (texturepoint[i].startx != -16000)
/* Indicates there is a line on this row */
{
if (texturepoint[i].endx == -16000)
texturepoint[i].endx = texturepoint[i].startx;
/* In case there was only one point found on this row */
tmapline (texturepoint[i].startx,
texturepoint[i].x1, texturepoint[i].y1,
texturepoint[i].endx,
texturepoint[i].x2, texturepoint[i].y2,
i);
/* Draw a texture mapped line between the two x coordinates,
on the row i. */
}
}
So far the code is just keeping track of the coordinates for each
horizontal line. The real texture mapping code lies in the tmapline
routine which draws it on the screen.
2.0 Size Restrictions
---------------------
I will now place a restriction on our textures to enable some optimizations.
The texture MUST have a width of 256, and has a maximum height of 256.
The reason for this is you can store an X or Y texture coordinate in half
of a register.
This restriction isn't necessary. I also have code for texture mapping
any size texture, but I feel the speed increase is well worth it and decided
to present this method.
3.0 - TMAPLINE Pseudo-code
--------------------------
Our basic texture mapped line routine looks like this:
Calculate the x step value
Calculate the y step value
Make a coordinate variable equal to the left endpoint's texture coordinate.
For x = x1 to x2
Read a pixel from the texture
Put pixel on screen
Add x step value to the texture coordinate
Add y step value to the texture coordinate
End for
4.0 Calculating the step values
-------------------------------
The tmapline routine needs to step along the x and y coordinate as we draw
the line. To do this, we can calculate a step value similar to the
technique described in the Gouraud shading tutorial.
length = x2 - x1 + 1; /* Calculate the length of this line */
deltax = tmapx2 - tmapx1 + 1; /* Find the delta values */
deltay = tmapy2 - tmapy1 + 1;
xincr = ((long)(deltax) << 8) / (long)length;
yincr = ((long)(deltay) << 8) / (long)length;
Now we have the values which are added to the texture coordinate
for every pixel drawn.
5.0 Assembly Tricks
-------------------
Here's how I would set up the registers to hold the texture coordinates.
This is the key to optimized texture mapping.
EDX is a 32-bit register that will contain the texture coordinates.
Since the x and y coordinates can go up to 256, they use 8 bits each.
As well, we will use 8 bits for the fractional portion of our fixed point
number.
Y whole value Y fraction X whole value X fraction
<--------------.--------------> <--------------.-------------->
1 2 3 4 5 6 7 8 9 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2
As you can see, the register will hold two 8.8 fixed point numbers.
ESI is used the same way, only it holds the step values.
Y whole step Y frac. step X whole step X frac. step
<--------------.--------------> <--------------.-------------->
1 2 3 4 5 6 7 8 9 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2
To add the step values to the texture coordinates, we simply add
ESI to EDX.
The next step is to take the x and y whole value out of EDX and
create a single offset into our texture image. To do this, we have
to remove the fractional portions, multiply the y value by the texture's
width, and add them together.
First copy EDX into another register so we can work with it. I used EBX
because it was the only one left. We want to access the high word of the
register, so we must shift it right.
mov ebx, edx /* Copy EDX into EBX for work */
shr ebx, 16 /* BH now contains the y coordinate */
By shifting it right 16 places, EBX now looks like this:
Y whole value Y fraction
<-----BH-------.------BL------>
1 2 3 4 5 6 7 8 9 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2
Here's the trick. Since our texture image has a width of 256, and the
y is in BH, it is already multiplied by the width! To create an offset,
all we have left to do is add the x value. In other words, we have to put
the x whole value into BL. EBX no longer contains the x value, so we'll
get it from EDX. The x whole value is stored in DH.
mov bl, dh /* Store the x value in BL */
BX is now an offset into the texture image, between 0 and 65535.
To get the pixel from the texture image, we use bx as the offset,
and ds as the segment of the texture. This means the texture MUST be
aligned to a segment. Having a texture fit perfectly within a segment
enables you to have a repeating texture, where the source texture coordinates
are much large than the texture itself. The values will wrap around at
256 and cause the texture to be shown more than once. You will see this
effect in the first demo.
mov al, ds:[bx] /* Get the color from the texture image */
Finally we need to add the step values to the texture coordinates.
add edx, esi /* Advance one pixel */
You can then put the pixel on the visual screen, where the pointer to the
screen is stored in es:di.
6.0 Other optimizations
-----------------------
Another optimization I used is drawing two pixels at once. You can
accomplish this by storing the first pixel in ah, the second in al,
and writing AX to the screen. This method requires a check to see if an odd
pixel needs to be drawn.
7.0 The code
------------
Whew. That was pretty complicated code. The same thing could have been done
easily in C, but several key optimizations would not be possible.
Here is the full texture mapping line routine:
void tmapline (int x1, int tmapx1, int tmapy1, int x2, int tmapx2,
int tmapy2, int y)
/* Draws one scanline of the textured polygon.
Where:
x1 is the first x coordinate
tmapx1 is the x coordinate on the texture relating to (x1,y)
tmapy1 is the y coordinate on the texture relating to (x1,y)
x2 is the second x coordinate
tmapx2 is the x coordinate on the texture relating to (x2,y)
tmapy2 is the y coordinate on the texture relating to (x2,y)
y is the scanline to draw the line on
*/
{
long length;
long deltax, deltay; /* Difference between the x and y coordinates */
unsigned char far * dest; /* Ptr to the screen */
unsigned char far * src; /* Ptr to texture image */
int xincr; /* X offset into texture, amount to increase every pixel */
int yincr; /* Y offset into texture, amount to increase every pixel */
int xpos, ypos; /* Stores fractional part after clipping */
int t; /* Used for swapping */
if (x1 > x2) /* Swap all the coordinates so x1 < x2 */
{
t = x1; x1 = x2; x2 = t;
t = tmapx1; tmapx1 = tmapx2; tmapx2 = t;
t = tmapy1; tmapy1 = tmapy2; tmapy2 = t;
}
length = x2 - x1 + 1; /* Calculate the length of this line */
if (length > 0)
{
deltax = tmapx2 - tmapx1 + 1; /* Find the delta values */
deltay = tmapy2 - tmapy1 + 1;
dest = abuf + y * 320 + x1; /* Make a pointer to the correct place in
video memory */
src = textureimage + tmapy1 * 256 + tmapx1;
/* Make a pointer to the correct place on the texture map
Assumes the image is 256 in width. */
xincr = ((long)(deltax) << 8) / (long)length;
yincr = ((long)(deltay) << 8) / (long)length;
/* Calculate the step value for the x and y coordinates.
For every pixel on the destination, the x coordinate on the texture
will move xincr pixels. */
xpos = tmapx1<<8;
ypos = tmapy1<<8;
asm {
.386
push ds
cld
mov cx, word ptr length /* Set length */
shr cx, 1
les di, dest /* Set destination ptr */
lds si, src /* Set source ptr */
mov dx, word ptr ypos /* Put the y in the low word */
shl edx, 16 /* Move the y to the high word */
mov dx, word ptr xpos /* Put the x in the low word */
mov si, word ptr yincr /* Set up the increments the */
shl esi, 16 /* same way */
mov si, word ptr xincr
/* Now to advance one pixel, we can add edx and esi together to
advance the x and y at the same time, with the fractional
portion automatically carrying at 256. */
cmp cx, 0
je onepixel
}
tlineloop:
;
asm {
mov ebx, edx
shr ebx, 16 /* BH now contains the y coordinate */
mov bl, dh /* Store the x value in BL, */
/* BX is now an offset into the texture image,
between 0 and 65535. */
mov al, ds:[bx] /* Get the color from the texture image */
add edx, esi /* Advance one pixel */
mov ebx, edx /* Repeat the above, and get another pixel */
shr ebx, 16
mov bl, dh
mov ah, ds:[bx]
add edx, esi
stosw /* Store a word to the destination */
dec cx /* Decrease length */
jnz tlineloop /* Repeat for all pixels */
}
onepixel:
asm {
mov cx, word ptr length
and cx, 1
jz tlinedone
mov ebx, edx
shr ebx, 16 /* BH now contains the y coordinate */
mov bl, dh /* Store the x value in BL, */
/* BX is now an offset into the texture image,
between 0 and 65535. */
mov al, ds:[bx] /* Get the color from the texture image */
mov es:[di], al
}
tlinedone:
asm {
pop ds
}
}
}
8.0 - What About Clipping?
--------------------------
Clipping can be performed similar to the way I used in the Gouraud
shaded line routine. I will leave this for you to complete if you require
it.
9.0 - Future Tutorials
----------------------
The next tutorial will discuss using dirty rectangles to speed up your
screen updates. If you have any requests for future topics, feel free to
suggest them to me and I'll see what I can do.
10.0 - Where to get WGT 4.0
---------------------------
You can download my graphics library from two places:
FTP site:
x2ftp.oulu.fi under /pub/msdos/programming/wgt/wgt4.zip
BBS:
Softnet BBS (519)-472-3661
Located in London, Ontario, Canada.
Login name: word up
Password: graphics
The files are located in file area #10.