*****************************************************************************
                           Texture Mapping Tutorial
                 by Tumblin / Bodies In Motion  (Terry Sznober)
*****************************************************************************

Hi everybody!  I'm going to explain to you how I do texture mapping.  You
will need the Watcom C/C++ 10.0 compiler (I have not tried it on any other
yet).  Okay, lets get started.


                              FIXEDPOINT MATH

First of all you will need to know a little bit about fixed point math.
When it comes right down to it, its simply using an integer to store a
floating point number by shifting the value so many bits to the left so
that the high-order part (the left half) is the whole number and the low-
order part (the right half) is the decimal.  Here is an example:

Say you wanted to store the value of PI in a variable in floating point.
You would say:

float float_value = 3.14159265;

Now, to do the same thing in fixedpoint, you would multiply the number by
a certain number that is a power of two.  So you would then say:

int fixed_value = (int)(3.14159265 * 65535.0); // notice the typecast

Now fixed_value will be in 16.16 form, which means the high-order 16 bits
will hold the 3, and the low-order 16 bits will hold the .14159265 portion.

Remember, when using the flat memory model in Watcom C, and int is 32-bits.
So to turn a regular int value to a fixedpoint value, just shift it left by
16 bits, like this:

int fixed_value = number << 16;

To turn a fixedpoint value back to an integer, you say:

int int_value = fixed_value >> 16;

But now you have lost the fractional portion, so if you need the fractional
part, convert it from fixedpoint to floating point, like this:

float float_value = (float)fixed_value / 65535.0;

Have a look at the file FIXED32.H for some code on fixedpoint.


                               TEXTURE MAPPING

The general idea behind the way I do texture mapping goes like this:
- initialize the left/right edge arrays
- scan each edge of the polygon while recording the source texture coordinates
  along the way
- then for each scanline, as you travel across from left to right, you
  simultaneousy trace an arbitrarily angled line in the source bitmap and
  grab the color of the pixel at the current texture coordinates, then draw
  it.

Its really pretty easy.  Lets see...

First you initialize the left/right edges.  You have these arrays that are
as tall as the screen (for each horizontal scanline) and they keep track of
the left edge's x screen coordinate, and the right edge's x screen coordinate
, as well as the left edge's (x,y) source texture coordinates, and the right
edge's (x,y) source texture coordinates.  Basically you want to initilize
them to their extremes.  This means that you start by setting the left edge's
x coordinate to the highest value you can set it to (320 in this case, I'm
talking about mode 13h, where we're using 320x200 in 256 colors).  And
similarly, you set the right edge's coordinate to the lowest value it can be
(0).  You see, they are criss-crossed, meaning they are backwards.  This will
help us later on so that we will know which scanline is supposed to be drawn
and which isn't.

Next you scan each edge of the polygon and update these left/right edge arrays
I've been talking about.  Lets talk about how that part works.


                               SCANNING EDGES


You give the edge scanning routine the starting (x,y) source texture
coordinate, along with the ending (x,y) destination screen coordinate.  The
first thing you do is make sure that they are going from top to bottom.  So
if the (y) components are out of order, then you swap the source (x,y) AND
destination (x,y) pairs with each other so that the starting (x,y) pair is
higher than the ending (x,y) pair.

Next you have to calculate the slopes of the destination horizontal scanline,
and the source diagonal line that you are about to trace.  Actually they are
not really slopes, but values that will be used for doing interpolation.

                                INTERPOLATION

Interpolation is a way to take a value from A to B in a given number of steps.
This is also known as tweening.  Here's an example:

Say we wan to a path to go from the left (*) to the right (*):

          *                                          *
        (x=11)                                     (x=54)

And we want to do it in 4 steps, for example.  Then we want the pattern:

          *         *          *          *         *
        (x=11)    (x=21)     (x=32)     (x=43)    (x=54)

So what we need is something that we can use to tell us when to draw the (*).
Here is some code:
---------------

int start = 11;
int end = 54;
int steps = 4;
int i;
float x = start; // notice that this is float, not int
int y = 100; // lets assume center of the screen :)
float m = ( end - start) / steps; // this will evaluate to 10.75

for(i=start; i<=end; i++)
{
  DrawPoint( (int)x, y ); // notice the type casting
  x += m; // interpolation magic... easy, isn't it?
}

---------------

So now that you have an idea of what interpolation is, we can apply it to
tracing lines.  We need three of these interpolation values.  One for the
destination x coordinates, one for the source x texture coordinates, and
one for the source y texture coordinates.  Here is some pseudo code for how
you would set them up:

// slope of destination x coordinates
mdx = ( width of destination line ) / ( height of destination line );

// slope of source x coordinates
msx = ( width of source line ) / ( height of destination line );

// slope of source y coordinates
msy = ( height of source line ) / ( height of destination line );

You will notice that each are divided by the same value.  This is because we
have to draw a specific number of pixels.  Everything else is interpolated
appropriately, so no need to worry.  Think of it this way:  if you had this
interpolation value, whatever that is, and initilized a counter value to the
specified starting value, by the time you add it the calculated number of
times to the counter, you will arrive at the specified ending value.  Just
think of your fraction rules:

                          (width of dest.)
mdx * (height of dest.) = ----------------- * (height of dest.) = ...
                          (height of dest.)

... = (width of dest)

Now when you add the starting value to the width of dest, you get the
ending value.

So you see, it works!  Just be careful that you don't try dividing by 0 !!!

Cool, now we know what interpolation is all about.  So the next step is to
initialize the starting destination x coordinate, and the starting source
(x,y) texture coordinates.  Then you go through a loop from the highest
destination y coordinate to the lowest destination y coordinate and record
the source (x,y) texture coordinates into our edge arrays as we go.

Just repeat the above procedure for each edge of the triangle (or multi-sided
polygon).


                          BACK TO TEXTURE MAPPING

We now have those eldge and right edge arrays filled up with all the data we
will need to finish off the texture mapping.  The next step is to figure out
the y coordinates of the highest scanline and the lowest scanline of the
textured triangle.  You might be thinking "well, don't we just use the
coordinates that we passed in and use the highest one?".  Well, that might
work, but what happens if the highest y coordinate is higher than the top of
the screen?

                                 Y-CLIPPING

The solution to this is to clip the polygon.  I do this at this stage of the
polygon drawing pipeline.  What we will need to do is use the 3 y coordinates
that we passed into the texture mapping function and then keep track of what
the highest and lowest y coordinates are.  We could use two variangles like
ymin and ymax, which is what I did in my code.  Now, once you find those two
numbers, you clip them.  If the ymin (highest y coordinate) is less than the
top of the screen (or top of the clipping area, if you want), then you simply
assign 0 to ymin.  Similarly, if the ymax (lowest y coordinate) is lower
than the bottom of the screen, then assign 199 to ymax.


                         TEXTURE FILLING THE SCANLINES

Okay, here it comes, the loop where the actual drawing is done.  You now do
a for loop from ymin to ymax and texture fill each scanline.  Now, for each
scanline you get the destination x screen coordinates from the arrays we've
been maintaining, and make sure that the the left x is less than the right x.

                             INTERPOLATION AGAIN

Yes, it is now time to do some more fancy interpolation.  This time we will
need two interpolation values to trace a line across the source bitmap that
we are trying to texture on the horizontal scanline on the screen.  Find the
values for msx (interpolation value for the source x texture coordinate), and
msy (interpolation value for the source y coordinate), like this:

           (right edge's source x) - (left edge's source x)
msx = ----------------------------------------------------------
      (right edge's destination x) - (left edge's destination x)

           (right edge's source y) - (left edge's source y)
msy = ----------------------------------------------------------
      (right edge's destination y) - (left edge's destination y)

NOTE: make sure that the denominators in the above fractions are not zero, or
else!

Now you use two new variables that will keep track of your source (x,y)
texture coordinates. Set the x to the left edge's source x corrdinate, and
set the y to the left edge's source y coordinate.  Why the left edge?
Because we are drawing to the screen from left to right, but it doesn't matter
which direction we trace the source line.  Next we have the clip the x
coordinate, because we could potentially be drawing out the left edge of the
screen, or even out the right edge of the screen!

                                 X-CLIPPING

So if the left edge's x coordinate is past the left edge of the screen (or
left clipping boundary), do the following.  Find the amount that it passes
the left edge of the screen by subtracting the x coordinate in question from
the x coordinate of the left clipping boundary (zero if its the left edge of
the screen).  Now you simply set the starting x coordinate that we will begin
drawing with to the left clipping boundary.  But what about the line that we
are tracing through the source bitmap... won't we have to skip drawing some
of this stuff to keep things balanced?  Yes you do!  But with the algorithm
I am teaching you its a piece of cake!  All you have to do is multiply the
source (x,y) coordinates by the number of pixels that you clipped off the
left edge (earlier in this paragraph).  So it would look something like this:

sx += msx * clipped_amount; // where sx is the source x texture coordinate
sy += msy * clipped_amount; // where sy is the source y texture coordinate

Okay, we clipped the left edge of the horizontal scanline that we are about
to texture fill, but what about the right side?  Well, guess what?!  Its even
easier to clip the right edge than it is the left edge!  All you do is set
your right edge's destination screen x coordinate to the right clipping
boundary.

                         DRAWING THE TEXTURED SCANLINE

Get psyched, because we are about to pull off some  texture mapping magic!!!
For optimization purposes, what I did in my code was create a variable that
is a pointer to screen memory, and I assigned to it the memory address of
the first pixel that we we will draw in the horizontal scanline.  Then you go
through the inner loop of the texture mapper, like this:

for(i = x start coordinate; i < x end coordinate; i++)
{
...
}

Now, inside this inner loop I de-reference this screen pointer and assign
that pixel's color by doing a lookup in the texture's bitmap array, like this:

*ptr = bitmap[ (sy>>16) * width + (sx>>16)]; // notice the >>16

Notice that I shift the sx and sy variables by 16 bits to the right.  Remember
we are keeping them as fixedpoint because we use them for interpolation (we
keep adding a fractional number to them).  Which comes to the next tidbit of
the inner texture mapping loop.  All thats left to do is add the msx to the
source x texture coordinate and add the msy to the source y texture
coordinate.  You finally also advance the screen pointer by 1 pixel.  So
to summarize, the inner loop would look something like this:

for(i = x start coordinate; i < x end coordinate; i++)
{
  *ptr = bitmap[ (sy>>16) * width + (sx>>16)]; // notice the >>16
  sx += msx;
  sy += msy;
  ptr++;
}

For optimization, instead of multiplying by the width, try shifting left by
a certain number of bits.  This will only work right if the width of your
texture bitmap is a power of two.



                                CONCLUSION

Well, that wraps things up.  All it takes to do this texture mapping is two
functions and some fancy interpolation.  Check out the demo, it has a picture
of yours truly.  If you are still unclear on something in the code, email me
and I will try to help you understand what I am doing.

Oh, and if you ever use this in your demo, say hi in the greetings!
See you all at NAID '96.

Tumblin  (tumblin@mis.nb.ca)

