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!

[size="5"]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.

[size="5"]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:

[bquote]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.[/bquote]

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.Type 2: Flat Bottom - A triangle with a flat top.

Type 3: General - A general triangle with neither a flat top or bottom.[/bquote]

[size="5"]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);`

`dx_left_side = (x2 - x0);`

dx_right_side = (x1 - x0);

`slope_left_side = dy/dx_left_side = (y2 - y0)/(x2 - x0);`

`slope_right_side = dy/dx_right_side = (y2 - y0)/(x1 - x0);`

`dx_left_side = 1 * (x2 - x0)/(y2 - y0);`

`dx_right_side = 1 * (x1 - x0)/(y2 - y0);`

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

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.

[size="5"]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.

[size="3"] 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`

`sampling_ratio = 8/4 = 2.`

[size="3"] 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;`

`sampling_ratio = 8/14 = 0.57`

`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

[size="5"]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

`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

`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

`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

`xl+=dxdyl;`

ul+=dudyl;

vl+=dvdyl;

`xr+=dxdyr;`

ur+=dudyr;

vr+=dvdyr;

`dx = (xend - xstart); // the difference or delta dx`

xstart = xl; // left hand starting point

xend = xr; // right hand starting point

`du = (ul - ur)/dx; `

dv = (vl - vr)/dx;

`// 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

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[3]; // 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;

`// 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[0].y < poly_clip_min_y) &&

(face->tlist[1].y < poly_clip_min_y) &&

(face->tlist[2].y < poly_clip_min_y)) ||

((face->tlist[0].y > poly_clip_max_y) &&

(face->tlist[1].y > poly_clip_max_y) &&

(face->tlist[2].y > poly_clip_max_y)) ||

((face->tlist[0].x < poly_clip_min_x) &&

(face->tlist[1].x < poly_clip_min_x) &&

(face->tlist[2].x < poly_clip_min_x)) ||

((face->tlist[0].x > poly_clip_max_x) &&

(face->tlist[1].x > poly_clip_max_x) &&

(face->tlist[2].x > poly_clip_max_x)))

return;

// degenerate triangle

if ( ((face->tlist[0].x==face->tlist[1].x) && (face->tlist[1].x==face->tlist[2].x)) ||

((face->tlist[0].y==face->tlist[1].y) && (face->tlist[1].y==face->tlist[2].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[0].x = x0;

face.tlist[0].y = y0;

face.tlist[0].u = u0;

face.tlist[0].v = v0;

face.tlist[1].x = x1;

face.tlist[1].y = y1;

face.tlist[1].u = u1;

face.tlist[1].v = v1;

face.tlist[2].x = x2;

face.tlist[2].y = y2;

face.tlist[2].u = u2;

face.tlist[2].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);

***************************************************************************/

Well, that's it for texture mapping. Maybe next time we can talk about lighting those texture mapped polygons...