new file: 16/PCGPE10/3DROTATE.DOC

[16.git] / 16 / PCGPE10 / TEXTURE.TXT

                            ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿\r
                            ³ Texture Mapping ³\r
                            ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ\r
\r
                 Written for the PC-GPE by Sean Barrett.\r
\r
               ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿\r
               ³      THIS FILE MAY NOT BE DISTRIBUTED     ³\r
               ³ SEPARATE TO THE ENTIRE PC-GPE COLLECTION. ³\r
               ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ\r
\r
\r
-=-=-=-=- -=-=-=-=-=- -=-=-=-=-=- -=-=-=-=-=- -=-=-=-=-=- -=-=-=-=-=-\r
TEXTURE\r
TEXUE  almost everything you need to know to texture map with the PC\r
TXR\r
X\r
-=-=-=-=- -=-=-=-=-=- -=-=-=-=-=- -=-=-=-=-=- -=-=-=-=-=- -=-=-=-=-=-\r
\r
Copyright 1994 Sean Barrett.\r
Not for reproduction (electronic\r
or hardcopy) except for personal use.\r
\r
Contents:\r
\r
  0. warnings\r
  1. terminology and equations\r
  2. the basics\r
      Perfect texture mapping\r
      DOOM essentials\r
      Wraparound textures\r
      Non-rectangular polygons\r
  3. the hazards\r
      going off the texture map\r
      divide by 0\r
      it'll never be fast enough\r
  4. the complexities\r
      handling arbitrarily-angled polygons\r
      lighting\r
      slow 16-bit VGA cards\r
      mipmapping\r
\r
 -=-=-=-=-=-\r
| Note:  I am not providing any references as I simply\r
|        derived the math myself and worked out the various\r
|        techniques for myself (the 32-bit ADC trick was\r
|        pointed out to me in another context by TJC,\r
|        author of the Mars demo) over the last two years\r
|        (since Wolfenstein 3D and Underworld came out).\r
 -=-=-=-=-=-\r
\r
TEXTURE\r
TEXUE\r
TXR   0. Warnings\r
X\r
\r
  I assume a RIGHT-handed 3D coordinate system, with X positive\r
to the right, Y positive disappearing into the screen/distance,\r
and Z positive up.  To adjust this to the typical left-handed\r
3D space, simply swap all the 3D Ys & Zs.\r
\r
  I assume the screen space is positive-X to the right,\r
positive-Y goes down.  Adjust the signs as appropriate for\r
your system.\r
\r
  I will present code and pseudo-code in C.  I also include\r
some relatively tight inner loops written in assembly, but I'm\r
omitting the details of the loop setup.  The inner loops, while\r
usually from real, working code, should generally be taken\r
as examples showing how fast it ought to be possible to run\r
a given task, not as necessarily perfect examples.  I often\r
use 32-bit instructions (sorry 286 programmers) because they\r
can double the performance.  However, I write in real mode,\r
because 16-bit addressing is often convenient for texture maps,\r
and it's straightforward to use segment registers as pointers\r
to texture maps.  The translation to protected mode should not\r
prove problematic, but again, these should more be taken as\r
examples rather than simply being used directly.  I optimize\r
for the 486, but I skip some obvious optimizations.  For example,\r
I write "loop", because it's simpler and more clear.\r
Production code for the 486 should explicitly decrement and\r
then branch.  Similarly, I write "stosb", etc. etc.\r
\r
\r
TEXTURE\r
TEXUE\r
TXR   1. Terminology and Equations\r
X\r
\r
\r
  You really probably don't want to read this section first,\r
but rather refer back to it whenever you feel the need.  So\r
skip up to section 2 and refer back as appropriate.  I could've\r
made this an appendix, but it seems too important to put last.\r
\r
TEX\r
TE   Terms\r
T\r
    texture:  A texture is a pixelmap of colors which is mapped\r
              onto a polygon using "texture mapping".  The size\r
              of the polygon has nothing to do with the size (the\r
              number of pixels) in the texture map.\r
\r
    run:  A run is a row or column of pixels.  Normal texture\r
          mapping routines process one run in an "inner loop".\r
\r
    arbitrarily-angled polygon:  a polygon which isn't a floor,\r
          wall, or ceiling; technically, a polygon which isn't\r
          parallel to the X or Z axes (or X or Y axes in a\r
          Z-is-depth coordinate system).\r
\r
    texture space:\r
    polygon space:\r
    polygon coordinate space:\r
          Since a texture is flat, or two-dimensional, the relation\r
          of the texture to the 3D world can be described with a\r
          special coordinate space known by one of these names.\r
          Because it is only 2D, the space can be characterized with\r
          the location of the texture space in 2D, and two 3D vectors\r
          which represent the axes of the coordinate space.  Sometimes\r
          called "uv" space, because the name of the coordinates are\r
          usually u & v.\r
\r
TEX\r
TE   Notation\r
T\r
\r
    Vectors appear in all caps.\r
    Components of vectors are P = < Px, Py, Pz >.\r
\r
    Certain variables have consistent usage:\r
\r
      x,y,z are coordinates in three-space\r
      i,j are screen coordinates\r
      u,v are coordinates in texture space\r
      a,b,c are "magic coordinates" such that\r
         u = a/c, v = b/c\r
\r
TEX\r
TE   Equations\r
T\r
\r
    Don't let this scare you off!  Go read section 2, and\r
    come back to this when you're ready.\r
\r
    Let P,M, and N be vectors defining the texture space: P is the\r
    origin, and M and N are the vectors for the u&v axes.\r
\r
    Assume these vectors are in _view space_, where view space is\r
    defined as being the space in which the transformation from\r
    3D to 2D is:\r
\r
      (x,y,z) -> (i,j)\r
        i = x / y\r
        j = z / y\r
\r
    In other words, you have to adjust P, M, and N to be relative\r
    to the view, and if you have multiplications in your perspective\r
    computation, you have to multiply the appropriate components of\r
    P, M, and N to compute them.  Note that since typically in 3D\r
    up is positive, and in 2D down is positive, there may be a\r
    multiplication by -1 that needs to go into Py, My, Ny.  Note that\r
    this also assumes that (0,0) in screen space is at the center\r
    of the screen.  Since it's generally not, simply translate\r
    your screen coordinates (i,j) as if they were before applying\r
    the texture mapping math (or if you're funky you can modify\r
    your viewspace to pre-skew them).\r
\r
      For example, if your transforms are:\r
         i = Hscale * x / y + Hcenter\r
         j = -Vscale * z / y + Vcenter\r
\r
      Then you should simply multiply Px, Mx, and Nx by Hscale,\r
      and multiply Py, My, and Mz by -Vscale.  Then just remember\r
      to subtract Hcenter and Vcenter from the i,j values right\r
      before plugging them into the texture mapping equations.\r
\r
    We begin by computing 9 numbers which are constant\r
    for texture mapping the entire polygon (O stands for\r
    Origin, H for Horizontal, and V for vertical; why I use\r
    these names should become clear eventually):\r
\r
         Oa = Nx*Pz - Nz*Px\r
         Ha = Nz*Py - Ny*Pz\r
         Va = Ny*Px - Nx*Py\r
\r
         Ob = Mx*Pz - Mz*Px\r
         Hb = Mz*Py - My*Pz\r
         Vb = My*Px - Mx*Py\r
\r
         Oc = Mz*Nx - Mx*Nz\r
         Hc = My*Nz - Mz*Ny\r
         Vc = Mx*Ny - My*Nx\r
\r
    Ok.  Then, for a given screen location (i,j), the formula\r
    for the texture space (u,v) coordinates corresponding to\r
    it is:\r
\r
         a = Oa + i*Ha + j*Va\r
         b = Ob + i*Hb + j*Vb\r
         c = Oc + i*Hc + j*Hc\r
\r
         u = a/c\r
         v = b/c\r
\r
\r
TEXTURE\r
TEXUE\r
TXR   2.  The Basics\r
X\r
\r
    So you've got your polygon 3D engine running, and\r
you'd like to start adding a bit of texture to your\r
flat- or Gouraud-shaded polygons.  Well, it will make\r
it look a lot cooler.  But let's point out the\r
disadvantages of texture mapping right away:\r
\r
      Slower\r
      Sometimes hard to see polygon edges\r
\r
    Each of these has certain ramifications on the\r
overall approach you want to take with your code,\r
which we'll come back to later, in sections 3 and 4.\r
\r
    Practical advice: Don't try to get your riproaringly\r
fast texture mapper running first.  Get a very simple,\r
slow, "perfect" texture mapper working first, as described\r
in the first subsection below.  This will allow you to make\r
sure you've gotten the equations right.  Realize that I\r
can't present the equations appropriate to every scenario,\r
since there are simply too many spaces people can work\r
in.  I've chosen to present the math from an extremely\r
simple coordinate space which keeps the texture mapping\r
relatively simple.  You'll have to work out the correct\r
transformations to make it work right, and a slow but\r
correct texture mapping routine may help you tweak the\r
code as necessary to achieve this.  Use very simple\r
polygons to start your testing; centered and facing the\r
viewer should be your very first one (if done correctly,\r
this will simply scale the texture).\r
\r
TEX\r
TE   Perfect Texture Mapping\r
T\r
\r
    To start with, we'll do slow but exact "perfect" texture\r
mapping of a square tile with a simple texture map mapped onto\r
it.  The polygon is defined in three-space using four points,\r
and the texture map is 256x256 pixels.  Note that this is all\r
talking about using floating point, so those of you working in\r
C or Pascal are fine.  Those in assembly should realize that\r
you have to do a bit of extra work to use fixed point, or you\r
can beat out the floating point by hand if you want.\r
\r
    First we have to "map" the texture onto the polygon.\r
We have to define how the square texture map corresponds\r
to the square polygon.  This is relatively simple.  Let\r
one corner of the polygon be the origin (location <0,0>)\r
of the texture map.  Let each of the other corners\r
correspond to corners just off the edge of the texture\r
map (locations <256, 0>, <256, 256>, and <0, 256>).\r
\r
    We'd like to use the equations in section 1, which\r
require vectors P, M, and N, where P is the origin,\r
and M & N are the axes for u&v (which are _roughly_\r
the coordinates in the texture map, but see below).\r
In other words, P, M and N tells us where the texture\r
lies relative to the polygon.  P is the coordinate in\r
three-space where the origin of the texture is.  M\r
tells us which way the "horizontal" dimension of the\r
texture lies in three-space, and N the "vertical".\r
\r
    Suppose the polygon has four vertices V[0], V[1],\r
V[2], and V[3] (all four of these are vectors).  Then,\r
P is simply V[0].  M is a vector going from the origin\r
to the corner <256, 0>, so M is a vector from V[0] to\r
V[1], so M = V[1] - V[0].  N is a vector from the origin\r
to the corner <0, 256>, so N is V[3] - v[0].\r
\r
    P = V[0]\r
    M = V[1] - V[0]    { note these are vector subtractions }\r
    N = V[3] - V[0]\r
\r
    Again, remember that we need P, M, and N in the viewspace\r
discussed with the equation, so make sure you've transformed\r
the Vs appropriately, or you can compute P, M, and N in world\r
or object space and transform them into viewspace.\r
\r
    Compute the 9 magic numbers (vectors O, H, and V) as described\r
in section 1.  Now, take your 3D polygon and process it as normal.\r
Scan convert it so that you have a collection of rows of pixels\r
to process.\r
\r
    Now, iterate across each row.  For each pixel in the polygon\r
whose screen coordinates are <i,j>, apply the rest of the math\r
described in section 1; that is, compute a, b, and c, and from\r
them compute <u,v>.\r
\r
    I said before that <u,v> are basically the texture map\r
coordinates.  What they are in truth are the coordinates in texture\r
map space.  Because of the way we defined texture map space,\r
we'll actually find that u and v both run from 0..1, not 0..256.\r
This is an advantage for descriptive purposes because u and v\r
are always 0 to 1, regardless of the size of the texture map.\r
\r
    So, to convert u&v to pixelmap coordinates, multiply them\r
both by 256.  Now, use them as indices into the texture map,\r
output the value found there, and voila, you've texture mapped!\r
\r
The loop should look something like this:\r
\r
[ loop #1 ]\r
    for every j which is a row in the polygon\r
      screen = 0xA0000000 + 320*j\r
      for i = start_x to end_x for this row\r
        a = Oa + (Ha * i) + (Va * j)\r
        b = Ob + (Hb * i) + (Vb * j)\r
        c = Oc + (Hc * i) + (Vc * j)\r
        u = 256 * a / c\r
        v = 256 * b / c\r
        screen[i] = texture_map[v][u]\r
      endfor\r
    endfor\r
\r
    Once you've got that working, congratulations!  You're\r
done dealing with the annoying messy part, which is getting\r
those 9 magic numbers computed right.  The rest of this is\r
just hard grunt work and trickery trying to make the code\r
faster.\r
\r
    From here on in, I'm only going to look at the inner\r
loop, that is, a single run (row or column), and let the\r
rest of the runs be understood.\r
\r
TEX\r
TE   Prepare to meet thy DOOM\r
T\r
\r
    This subsection is concerned with vastly speeding\r
up texture mapping by restricting the mapper to walls,\r
floors and ceilings, or what is commonly called\r
DOOM-style texture mapping, although it of course predates\r
DOOM (e.g. Ultima Underworld [*], Legends of Valour).\r
\r
[*  Yes, Underworld allowed you to tilt the view,\r
but it distorted badly.  Underworld essentially used\r
DOOM-style tmapping, and tried to just use that on\r
arbitrarily-angled polygons.  I can't even begin to\r
guess what Underworld II was doing for the same thing.]\r
\r
    To begin with, let's take loop #1 and get as much\r
stuff out of the inner loop as we can, so we can see\r
what's going on.  Note that I'm not going to do low-level\r
optimizations, just mathematical optimizations; I assume\r
you understand that array walks can be turned into\r
pointer walks, etc.\r
\r
[ loop #2 ]\r
      a = Oa + Va*j\r
      b = Ob + Vb*j\r
      c = Oc + Vc*j\r
\r
      a += start_x * Ha\r
      b += start_x * Hb\r
      c += start_x * Hc\r
\r
      for i = start_x to end_x\r
        u = 256 * a / c\r
        v = 256 * b / c\r
        screen[i] = texture_map[v][u]\r
        a += Ha\r
        b += Hb\r
        c += Hc\r
      endfor\r
\r
    With fixed point math, the multiplies by 256\r
are really just shifts.  Furthermore, they can be\r
"premultiplied" into a and b (and Ha and Hb) outside\r
the loop.\r
\r
    Ok, so what do we have left?  Three integer adds,\r
a texture map lookup, and two extremely expensive fixed-point\r
divides.  How can we get rid of the divides?\r
\r
    This is the big question in texture mapping, and most\r
answers to it are _approximate_.  They give results that\r
are not quite the same as the above loop, but are difficult\r
for the eye to tell the difference.\r
\r
    However, before we delve into these, there's a very\r
special case in which we can get rid of the divides.\r
\r
    We can move the divide by c out of the loop without\r
changing the results IFF c is constant for the duration\r
of the loop.  This is true if Hc is 0.  It turns out that\r
Hc is 0 if all the points on the run of pixels are the same\r
depth from the viewer, that is, they lie on a line of\r
so-called "constant Z" (I would call it "constant Y" in\r
my coordinate system).\r
\r
    The requirement that a horizontal line of pixels be the\r
same depth turns out to be met by ceilings and floors.\r
For ceilings and floors, Hc is 0, and so the loop can be\r
adjusted to:\r
\r
[ loop #3 ]\r
      __setup from loop #2__\r
      u = 256 * a / c\r
      v = 256 * b / c\r
      du = 256 * Ha / c\r
      dv = 256 * Hb / c\r
      for i = start_x to end_x\r
        screen[i] = texture_map[v][u]\r
        u += du\r
        v += dv\r
     endfor\r
\r
    Now _that_ can be a very fast loop, although adjusting\r
the u&v values so they can be used as indices has been\r
glossed over.  I'll give some sample assembly in the next\r
section and make it all explicit.\r
\r
    First, though, let's look at walls.  Walls are almost\r
identical to floors and ceilings.  However, with walls,\r
Vc is 0, instead of Hc.  This means that to write a loop\r
in which c is constant, we have to walk down columns instead\r
of across rows.  This affects scan-conversion, of course.\r
\r
    The other thing about walls is that with floors, since\r
you can rotate about the vertical axis (Z axis for me, Y axis\r
for most of you), the horizontal runs on the floors cut\r
across the texture at arbitrary angles.  Since you're\r
bound to not tilt your head up or down, and since the\r
polygons themselves aren't tilted, you generally find\r
that for walls, Va is 0 as well.  In other words, as you\r
walk down a column of a wall texture, both a & c are constant,\r
so u is constant; you generally only change one coordinate,\r
v, in the texture map.  This means the inner loop only needs\r
to update one variable, and can be made to run _very_ fast.\r
\r
    The only thing missing from this discussion for creating\r
a DOOM clone is how to do transparent walls, how to do\r
lighting things, and how to make it fast enough.  These will\r
be discussed in section 4, although the some of the speed\r
issue is addressed by the inner loops in the next subsection,\r
and the rest of the speed issue is discussed in general terms\r
in section 3.\r
\r
TEX\r
TE   ...wrapped around your finger...\r
T\r
\r
    So far, we've only looked at texture mapping a single\r
polygon.  Of course, it's obvious how to texture map\r
a lot of polygons--just lather, rinse, repeat.  But it\r
may seem sort of wasteful to go through all the 3D math\r
and all over and over again if we just want to have one\r
long wall with the same texture repeating over and over\r
again--like linoleum tiles or wallpaper.\r
\r
    Well, we don't have to.  Let's think about this\r
idea of a "texture map space" some more.  We defined\r
it as being a coordinate system "superimposed" on\r
the polygon that told us where the texture goes.\r
However, when we implemented it, we simply used the\r
polygon itself (in essence) as the coordinate space.\r
\r
    To see this, make a polygon which is a rectangle,\r
perhaps four times as long as it is tall.  When it\r
is drawn, you will see the texture is distorted,\r
stretched out to four times its length in one dimension.\r
Suppose we wanted it to repeat four times instead?\r
\r
    The first step is to look at what the definition\r
of the texture map space means.  The texture map space\r
shows how the physical pixelmap itself goes onto the\r
polygon.  To get a repeating texture map, our first\r
step is to just get one of the copies right.  If\r
we set up our P,M, & N so that the M only goes one\r
quarter of the way along the long edge of the\r
rectangle, we'll map the texture onto just that\r
quarter of the rectangle.\r
\r
     Here's a picture to explain it:\r
\r
              Polygon A-B-C-D                    Texture map\r
\r
   A          E                                  u=0     u=1\r
    o--------o-___________          B        v=0  11112222\r
    |111112222            ---------o              11112222\r
    |111112222                     |              33334444\r
    |111112222                     |              33334444\r
    |333334444                     |         v=1\r
    |333334444                     |\r
    |333334444 ___________---------o\r
    o--------o-                     C\r
   D          F\r
\r
    So, we used to map (u,v)=(0,0) to A, (u,v)=(1,0) to B, and\r
(u,v) = (0,1) to D.  This stretched the texture map out to\r
fill the entire polygon map.\r
\r
    Now, instead, we map (u,v)=(1,0) to E.  In other words,\r
let P = A, M = E-A, and N = D-A.  In this new coordinate\r
space, we will map the texture onto the first quarter of\r
the polygon.\r
\r
    What about the rest of the polygon?  Well, it simply\r
turns out that for the first quarter 0 <= u <= 1.  For\r
the rest, 1 <= u <= 4.\r
\r
    To make the texture wrap around, all we have to do is\r
ignore the integer part of u, and look at the fractional part.\r
Thus, as u goes from 1 to 2, we lookup in the texture map using\r
the fractional part of u, or (u-1).\r
\r
    This is all very simple, and the upshot is that, once\r
you define P, M, and N correctly, you simply have to mask\r
your fixed-point u&v values; this is why we generally use\r
texture maps whose sides are powers of two, so that we can\r
mask to stay within the texture map.  (Also because they\r
fit conveniently into segments this way, and also so that\r
the multiply to convert u&v values from 0..1 to indices\r
is just a shift.)\r
\r
    I'm assuming that's a sufficient explanation of the\r
idea for you to get it all setup.  So here's the assembly\r
inner loops I promised.  I'm not going to bother giving\r
the ultra-fast vertical wall-drawing case, just the\r
horizontal floor/ceiling-drawing case.\r
\r
    Note that a mask of 255 (i.e. for a 256x256 texture)\r
can be gotten for free; however, no program that I'm\r
aware of uses texture maps that large, since they\r
simply require too much storage, and they can cache very\r
poorly in the internal cache.\r
\r
    First, here's your basic floor/ceiling texture mapper,\r
in C, with wraparound, and explicitly using fixed point\r
math--but no setup.\r
\r
[ loop #4 ]\r
    mask = 127, 63, 31, 15, whatever.\r
    for (i=0; i < len; ++i) {\r
      temp = table[(v >> 16) & mask][(u >> 16) & mask];\r
      u += du;\r
      v += dv;\r
    }\r
\r
    Now, here's an assembly one.  This one avoids the\r
shifts and does both masks at the same time, and uses\r
16 bits of "fractional" precision and however many bits\r
are needed for the coordinates.  Note that I assume\r
that the texture, even if it is 64x64, still has each\r
row starting 256 bytes apart.  This just requires some\r
creative storage approaches, and is crucial for a fast\r
inner loop, since no shifting&masking is required to\r
assemble the index.\r
\r
       mov  al,mask\r
       mov  ah,mask\r
       mov  mask2,ax      ; setup mask to do both at the same time\r
\r
loop5  and  bx,mask2      ; mask both coordinates\r
       mov  al,[bx]       ; fetch from the texture map\r
       stosb\r
       add  dx,ha_low     ; update fraction part of u\r
       adc  bl,ha_hi      ; update index part of u\r
       add  si,hb_low     ;   these are constant for the loop\r
       adc  bh,hb_hi      ;   they should be on the stack\r
       loop loop5         ;   so that ds is free for the texture map\r
\r
    This code is decent, but nowhere near as fast as it can be.\r
The main trick to improving performance is to use 32 bit adds\r
instead of two adds.  The problem with this is that extra operations\r
are required to setup the indexing into the texture map.  Through\r
the use of the ADC trick, these can be minimized.  In the following\r
code, bl and bh are unchanged.  However, the top half of EBX now\r
contains what used to be in si, and the other values have been\r
moved into registers.  ESI contains hb_low in the top half, and\r
ha_hi in the low 8 bits.  This means that ADC EBX,ESI achieves\r
the result of two of the additions above.  Also, we start using\r
BP, so we move our variables into the data segment and the texture\r
map into FS.\r
\r
loop6  and  bx,mask2\r
       mov  al,fs:[bx]\r
       stosb\r
       add  dx,bp          ; update fractional part of u\r
       adc  ebx,esi        ; update u (BL) and frac. part of v (EBX)\r
       adc  bh,ch          ; update index part of v\r
       dec  cl\r
       jnz  loop6\r
\r
    This is a bit faster, although it has one bug.  It's\r
possible for the addition into BL to overflow into BH.  It might\r
not seem to be, since BL is masked every iteration back down to\r
stay in 0..127, 0..63, or whatever.  However, if the step is\r
negative, then BL will be decremented each iteration, and may\r
"underflow" and subtract one from BH.  To handle this, you need\r
a seperate version of the loop for those cases.\r
\r
    If you're not doing wraparound textures, you can speed the\r
loop up a bit more by removing the and.  You can run entirely\r
from registers except for the texture map lookup.  Additionally,\r
unrolling the loop once cuts down on loop overhead, and is crucial\r
if you're writing straight to the VGA, since it doubles your\r
throughput to a 16-bit VGA card.\r
\r
    Here's a very fast no-wraparound texture mapper.  It uses\r
the ADC trick twice.  Note that the carry flag is maintained\r
around the loop every iteration; unfortunately the 'and' required\r
for wraparound textures clears the carry flag (uselessly).  EBX\r
and EDX contain u & v in their bottom 8 bits, and contain the\r
fractional parts of v & u in their top bits (note they keep the\r
_other_ coordinate's fractional parts).  You have to have prepped\r
the carry flag first; if you can't figure this technique out, don't\r
sweat it, or look to see if someone else has a more clear discussion\r
of how to do fast fixed-point walks using 32-bit registers.\r
\r
    This loop is longer because it does two pixels at a time.\r
\r
loop7   mov  al,[bx]       ; get first sample\r
        adc  edx,esi       ; update v-high and u-low\r
        adc  ebx,ebp       ; update u-high and v-low\r
        mov  bh,dl         ; move v-high into tmap lookup register\r
        mov  ah,[bx]       ; get second sample\r
        adc  edx,esi\r
        adc  ebx,ebp\r
        mov  bh,dl\r
        mov  es:[di],ax    ; output both pixels\r
        inc  di            ; add 2 to di without disturbing carry\r
        inc  di\r
        dec  cx\r
        jnz  loop7\r
\r
    I went ahead and 486-optimized the stosw/loop at the end to make\r
cycle-counting easier.  All of these instructions are single cycle\r
instructions, except the branch, and the segment-override.  So you're\r
looking at roughly 15 cycles for every two pixels.  Your caching\r
behavior on the reads and writes will determine the actual speed.\r
It can be unrolled another time to further reduce the loop overhead;\r
the core operations are 9 instructions (10 cycles) for every two\r
pixels.  Note the "inc di/inc di", which protects the carry flag.\r
If you unroll it again, four "inc di"s will be required.  Unroll it\r
another time, and you're better off saving the carry flag, adding,\r
and restoring, for example "adc ax,ax/add di,8/shr ax,1", rather\r
than 8 "inc di"s.\r
\r
TEX\r
TE   Lost My Shape (trying to act casual)\r
T\r
\r
    Non-rectangular polygons are trivial under this system.\r
Some approaches require you to specify the (u,v) coordinates\r
for each of the vertices of the polygon.  With this technique,\r
you instead specify the 3D coordinates for three of the\r
"vertices" of the texture map.  So the easiest way of handling\r
a texture of a complex polygon is simply to use a square\r
texture which is larger than the polygon.  For example:\r
\r
   P1                       P2\r
     x    B  _______  C    x\r
           /         \\r
         /             \\r
     A /                 \\r
       \                 / D\r
         \             /\r
           \ _______ /\r
     x    F           E\r
   P3\r
\r
    Now, we simply define the texture map such that P is P1,\r
M is P2-P1, and N is P3-P1.  Then, if our texture looks like\r
this:\r
\r
     u=0        u=1\r
      ------------\r
 v=0 |..XXoooooo..\r
     |.XXXXoooooo.\r
     |XXXXXXoooooo\r
     |.XXXXXXoooo.\r
 v=1 |..XXXXXXoo..\r
\r
    Then the regions marked by '.' in the texture map will\r
simply never be displayed anywhere on the polygon.\r
\r
    Wraparound textures can still be used as per normal,\r
and concave polygons require no special handling either.\r
\r
    Also, you can get special effects by having M and N not\r
be perpendicular to each other.\r
\r
TEXTURE\r
TEXUE\r
TXR   3.  The Hazards\r
X\r
\r
    This sections discusses some of the pitfalls and\r
things-aren't-quite-as-simple-as-they-sounded issues\r
that come up while texture mapping.  All of the\r
information is, to some extent, important, whether\r
you've encountered this problem or not.\r
\r
TEX\r
TE   Cl-cl-cl-close to the Edge\r
T\r
\r
    At some time when you're texture mapping, you'll\r
discover (perhaps from the screen, perhaps from a\r
debugger) that your U & V values aren't within the\r
0..1 range; they'll be just outside it.\r
\r
    This is one of these "argh" problems.  It is\r
possible through very very careful definition of\r
scan-conversion operations to avoid it, but you're\r
likely to encounter it.\r
\r
    If you use wraparound textures, you may not ever\r
notice it, however, since when it happens, the\r
texture will simply wraparound and display an\r
appropriate pixel.\r
\r
    If not, you may get a black pixel, or just\r
garbage.  It'll only happen at the edges of your\r
polygon.\r
\r
    The reason this happens is because your scan-conversion\r
algorithm may generate pixels "in the polygon" whose\r
pixel-centers (or corners, depending on how you've\r
defined it) are just outside the texture--that is,\r
they're outside the polygon itself.\r
\r
    The right solution to this is to fix your scan-converter.\r
If your texture mapper computes u&v coordinates based on\r
the top-left corner of the pixel (as the one I've defined\r
so far has), make sure your scan-converter only generates\r
pixels whose top-left corner is really within the polygon.\r
If you do this, you may need to make a minor change to my\r
definition of M & N, but I'm not going to discuss this\r
further, since you probably won't do this.\r
\r
    A second option is to define P, M, and N such that the\r
texture map space is slightly bigger than the polygon; that\r
is, so that if you go just off the edge of the polygon,\r
you'll still be within the texture map.\r
\r
    This is a pain since you end up having to transform extra\r
3D points to do it.\r
\r
    The third, and probably most common solution, is to always\r
use wraparound textures, which hide the problem, but prevent\r
you from using textures that have one edge that highly contrasts\r
with another.\r
\r
    The fourth, and probably second most common solution,\r
and the one that turns out to be a real pain, is to "clamp"\r
the u&v values to be within the texture all the time.\r
\r
    Naively, you just put this in your inner loop:\r
\r
      if (u < 0) u = 0; else if (u > 1) u = 1;\r
      if (v < 0) v = 0; else if (v > 1) v = 1;\r
\r
    Of course, you don't really do this, since it'd slow\r
you down far too much.  You can do this outside the loop,\r
clamping your starting location for each run.  However,\r
you can't, under this system, clamp the ending value\r
easily.\r
\r
    Remember that in the loop we update u and v with\r
(essentially) Ha/c and Hb/c.  These are constant\r
across the entire run, but not constant across the\r
entire polygon, because c has different values for\r
different runs.\r
\r
    We can compute du and dv in a different way to\r
allow for clamping.  What we do is we explicitly compute\r
(a,b,c) at (start_x, j) as we did before, but we also\r
compute (a,b,c) at (end_x, j).  From these we compute\r
(u,v) at start_x & at end_x.  Next we clamp both sets\r
of u & v.  Then we compute du and dv with\r
\r
    du = (u2 - u1) / (end_x - start_x - 1)\r
    dv = (v2 - v1) / (end_x - start_x - 1)\r
\r
    This is slightly more expensive than the old way,\r
because we have to compute u2 and v2, which requires\r
extra divides.  However, for methods that explicitly\r
calculate u&v sets and then compute deltas (and we'll\r
see some in section 4), this is the way to go.\r
\r
    One final thing you can do is interpolate the (a,b,c)\r
triple from the vertices as you scan convert.  This will\r
guarantee that all (a,b,c) triples computed will lie be\r
within the polygon, and no clamping will be necessary\r
(but deltas must still be computed as above).  However,\r
you have to make sure the (a,b,c) values you compute at\r
the vertices are clamped themselves, which is not too hard\r
by a bit more complicated than clamping (u,v) values.\r
\r
TEX\r
TE   Out of This Domain -- Zero's Paradox\r
T\r
\r
    Divides by zero are ugly.  We programmers don't\r
like them.  If this were an ideal world (a quick\r
nod to mathematicians and some physicists), the\r
texture mapping equations would be divide-by-zero-free.\r
\r
    Unfortunately, it's a repercussion of the exact\r
same problem as above that you can bump into them.\r
\r
    Remember above, I noted that it's possible to\r
get (u,v) pairs with a value just outside of the\r
0..1 range, because a pixel we're texture mapping\r
isn't even in the polygon?\r
\r
    Well, even worse, it's possible for this pixel,\r
which isn't in the polygon, to be along the horizon\r
line (vanishing point) for the polygon.  If this\r
happens, your Y value (sorry, Z for most of you)\r
would be infinite if you tried to compute the 3D\r
coordinates from the screen coordinates; and in\r
the (u,v) computation, you end up with a 0 value\r
for c.  Since u = a/c, blammo, divide by 0.\r
\r
    Well, the solution is simple.  Test if c is 0,\r
and if it is, don't divide.  But what _should_ you do?\r
\r
    Well, let's look at an "even worse" case.  Suppose\r
the pixel is so far off the polygon it's across the\r
horizon line.  In this case, we'll end up with c having\r
the "wrong" sign, and while our divide won't fault on\r
us, our u&v values will be bogus.\r
\r
    What do we do then?\r
\r
    We can't clamp our a&b&c values very easily.\r
Fortunately, it turns out we don't have to.  If\r
this happens, it means the edge of the polygon\r
must be very close to the horizon, or the viewer\r
must be very, very flat to the polygon (if you know\r
what I mean).  If so, the viewer can't really tell\r
what should be "right" for the polygon, so if we\r
screw up the u&v values, it really doesn't matter.\r
\r
    So the answer is, don't worry if c gets the\r
wrong sign, and if c comes out to be 0, use any\r
value for u&v that you like--(0,0) makes an obvious\r
choice.\r
\r
    I've never had a serious problem with this, but\r
it is possible that this could actually give you some\r
pretty ugly results, if, say, two corners of a polygon\r
both "blew up", and you treated them both as being\r
(0,0).  It can also cause problems with wraparound\r
polygons not repeating the right amount.\r
\r
TEX\r
TE   Do the Dog\r
T\r
\r
    Most polygon 3D graphics engines probably use\r
the painter's algorithm for hidden surface removal.\r
You somehow figure out what order to paint the polygons\r
in (depth sort, BSP trees, whatever), and then paint\r
them back-to-front.  The nearer polygons obscure the\r
farther ones, and voila!, you're done.\r
\r
    This works great, especially in a space combat\r
simulator, where it's rare that you paint lots of pixels.\r
\r
    You can texture map this way, too.  For example,\r
Wing Commander II doesn't texture map, but it does\r
real time rotation, which involves essentially the\r
same inner loop.  Wing Commander II is fast--until\r
a lot of ships are on the screen close to you, at which\r
point it bogs down a bit.\r
\r
    If you care about not slowing down too much in the above\r
case, or you want to do an "indoor" renderer with lots of\r
hidden surfaces, you'll find that with texture mapping,\r
you can ill-afford to use the painter's algorithm.\r
\r
    You pay a noticeable cost for every pixel you texture\r
map.  If you end up hiding 80% of your surfaces (i.e. there\r
are five "layers" everywhere on the screen), you end up\r
"wasting" 80% of the time you spend on texture mapping.\r
\r
    To prevent this, you have to use more complex methods\r
of hidden surface removal.  These will probably slow you down\r
somewhat, but you should make up for it with the gain in texture\r
mapping.\r
\r
    The essential idea is to only texture map each screen pixel once.\r
To do this, you do some sort of "front-to-back" painting, where\r
you draw the nearest surface first.  Any pixel touched by this\r
surface should never be considered for drawing again.\r
\r
    There are many ways to do this.  You can process a single\r
scanline or column at a time and use ray-casting or just\r
"scanline processing", then resolve the overlap between the\r
runs with whatever method is appropriate.  You can stay\r
polygonal and maintain "2D clipping" information (a data\r
structure which tracks which pixels have been drawn so far).\r
\r
    Beyond getting a fast inner loop for texture mapping,\r
getting a fast hidden-surface-removal technique (and a fast\r
depth-sorting technique if appropriate) is probably the\r
next most crucial thing for your frame rate.\r
\r
    But the details are beyond the scope of this article.\r
\r
    Note that if you attempt to use a Z-buffer, you will\r
still end up paying all of the costs of texture mapping for\r
every forward-facing polygon (or at least 50% of them if\r
you get really tricky; if you get really, really tricky,\r
the sky's the limit.)  I strongly doubt that any PC game\r
now out, or that will come out in the next year, will\r
render full-screen texture mapping through a Z-buffer.\r
(Superimposing a rendered image on a Z-buffered background\r
is a different issue and is no doubt done all the time.)\r
\r
\r
TEXTURE\r
TEXUE\r
TXR   4.  The Complexities\r
X\r
\r
    In this section we will discuss lots of miscellaneous\r
topics.  We'll look at some more optimizations, such as\r
considerations for dealing with slow VGA cards, and how to\r
texture map arbitrarily-angled polygons without doing two\r
divides per pixel.  We'll talk about a technique that lets\r
you use textures with high-frequency components, and one way\r
to integrate lighting into texture-mapping.\r
\r
TEX\r
TE   Arbitrarily-Angled Polygons\r
T\r
\r
    First suggestion: Don't.  Set up your world to\r
have all (or mostly) walls and floors.  Supporting\r
arbitrarily-angled polygons is going to slow you\r
down, no matter what.\r
\r
    The original texture mapping loop, which supported\r
arbitrarily-angled polygons, required two divides per\r
pixel.  We don't have to go that slow, but we'll never\r
go as fast as DOOM-style rendering can go.  (However,\r
as you start to use more sophisticated lighting algorithms\r
in your inner loop, the cost of handling arbitrarily-\r
angled polygons may start to become less important.)\r
\r
    There is one way to texture map such polygons\r
"perfectly" without two divides per pixel, and a\r
host of ways to do it "imperfectly".  I'll discuss\r
several of these ways in varying amounts of detail.\r
Your best bet is to implement them all and see\r
which ones you can get to run the fastest but still\r
look good.  You might find that one is faster for\r
some cases but not for others.  You could actually\r
have an engine which uses all the methods, depending\r
on the polygon it's considering and perhaps a "detail"\r
setting which controls how accurate the approximations\r
are.\r
\r
    The "perfect" texture mapping algorithm is\r
described in another article, "Free-direction texture\r
mapping".  I'll summarize the basic idea and the\r
main flaw.  The basic idea is this.  For ceilings\r
and walls, we were able to walk along a line on\r
the screen for which the step in the "c" parameter\r
was 0; this was a line of "constant Z" on the\r
polygon.\r
\r
    It turns out that every polygon has lines of\r
"constant Z"--however, they can be at any angle,\r
not necessarily vertical or horizontal.\r
\r
    What this means, though, is that if you walk\r
along those lines instead of walking along a horizontal\r
or vertical, you do not need a divide to compute your\r
texture map coordinates, just deltas.\r
\r
    The details can be found in the other article.\r
The slope of the line to walk on the screen is something\r
like Hc/Vc.\r
\r
    Note, however, that the "DOOM" approach was _just_\r
an optimization for a special case.  The wall & ceiling\r
renderers produce exactly the same results as a\r
perfect texture mapper, for the polygons that they\r
handle (ignoring rounding errors and fixed-point precision\r
effects).  This is not true for the "free-direction"\r
texture mapper.  While there is a line across the\r
screen for which the polygon has constant Z,\r
you cannot walk exactly along that line, since you\r
must step by pixels.  The end result is that while\r
in the texture map space, you move by even steps,\r
in the screen space, you move with ragged jumps.\r
With perfect texture mapping, you always sample\r
from the texture map from the position corresponding\r
to the top-left/center of each pixel.  With the\r
free-direction mapper, you sample from a "random"\r
location within the pixel, depending on how you're\r
stepping across the screen.  This "random" displacement\r
is extremely systematic, and leads to a systematic\r
distortion of the texture.  I find it visually\r
unacceptable with high-contrast textures, compared to\r
perfect texture mapping, but you should try it and decide\r
for yourself.  The technically inclined should note that\r
this is simply the normal "floor" renderer with an extra\r
2D skew, and that while 2D skews are trivial, they are\r
non-exact and suffer from the flaw described above.\r
\r
    The only other alternative for arbitrarily-angled\r
polygons is to use some kind of approximation.  We\r
can characterize u and v as functions of i (the horizontal\r
screen position; or use 'j' if you wish to draw columns);\r
for instance, u = a / c, where a = q + i*Ha, c = p + i*Hc.\r
So we can say  u(i) = (q + i*Ha) / (r + i*Hc).\r
\r
    Now, instead of computing u(i) exactly for each i,\r
as we've done until now, we can instead compute some\r
function u'(i) which is approximately equal to u(i) and\r
which can be computed much faster.\r
\r
    There are two straightforward functions which we\r
can compute very fast.  One is the simple linear\r
function we used for DOOM-style mapping, u'(x) = r + x*s.\r
Since the function we're approximating is curved (a\r
hyperbola), a curved function is another possibility,\r
such as u'(x) = r + x*s + x^2*t.  (SGI's Reality Engine\r
apparently uses a cubic polynomial.)\r
\r
    If you try both of these approximations on a very\r
large polygon at a sharp angle, you will find that\r
they're not very good, and still cause visible\r
curvature.  They are, of course, only approximations.\r
The approximations can be improved with a simple\r
speed/quality trade-off through subdivision.  The\r
idea of subdivision is that the approximation is\r
always of high quality for a small enough region,\r
so you can simply subdivide each region until the\r
subregions are small enough to have the desired\r
quality.\r
\r
    There are two ways to subdivide.  One simple way\r
is to subdivide the entire polygon into smaller\r
polygons.  This should be done on the fly, not\r
ahead of time, because only polygons that are at\r
"bad" angles need a lot of subdivision.  After\r
dividing a polygon into multiple smaller ones,\r
render each one seperately.  Use the original\r
P, M, and N values for all of the new polygons\r
to make the texture remain where it should be\r
after subdivision.\r
\r
    The (probably) better way to subdivide is to\r
subdivide runs instead of polygons, and so I'll\r
discuss this in more detail.  The essential thing\r
is that to do an approximation, you evaluate the\r
original function at two or more locations and\r
then fit your approximate function to the computed\r
values.  One advantage of run subdivision is that\r
you can share points that you evaluated for one\r
subrun with those of the next.\r
\r
    First lets turn back to the two approximations\r
under consideration.  The first is what is called\r
"bilinear texture mapping", because the function\r
is linear and we're tracking two ("bi") values.\r
To use this method, we compute the function at\r
both endpoints: u1 = u(start_x), u2 = u(end_x).\r
Then we compute our start and step values.  To\r
keep things simple, I'm going to assume the approximation\r
function u'(x) is defined from 0..end_x-start_x, not\r
from start_x..end_x.\r
\r
    So, the linear function u'(x) = r + s*x, where\r
u'(0) = u1 and u'(end_x - start_x) = u2 is met by\r
letting r = u1, s = (u2 - u1) / (end_x - startx).\r
\r
    Now, suppose our run goes from x = 10 to x = 70.\r
If we evaluate u(10), u(20), u(30), u(40),... u(70),\r
then we can have six seperate sections of bilinear\r
texture mapping.\r
\r
    For a quadratic, there are several ways to compute\r
it.  One way is to compute an additional sample in the\r
middle; u3 = u((start_x + end_x)/2).  Then we can\r
fit u1,u2, and u3 to u'(x) = r + s*x + t*x^2 with:\r
\r
   len = (end_x - start_x)\r
   k   = u1 + u2 - u3*2\r
   r   = u1\r
   s   = (u2 - u1 - 2*k)/len\r
   t   = 2*k / len^2\r
\r
    Note that to use this in code, you cannot simply\r
use a loop like this:\r
\r
   r += s;\r
   s += t;\r
\r
    because the r,s, and t values aren't correct\r
for discrete advancement.  To make them correct,\r
do this during the setup code:\r
\r
    R = r\r
    S = s + t\r
    T = 2*t\r
\r
    Then the loop of (...use R..., R += S, S += T) will work correctly.\r
\r
    The biquadratic loop will be slower than the linear\r
loop, but will look better with fewer subdivisions.  You\r
can share one of the endpoints from one biquadratic\r
section to the next.  Note, though, that you require twice\r
as many calculations of u&v values for the same number of\r
subdivisions with a biquadratic vs. a bilinear.\r
\r
    Another thing to do is to choose how to subdivide the run\r
more carefully.  If you simply divide it in half or into quarters,\r
you'll discover that some of the subruns come out looking better\r
than others.  So there are some things you can do to improve the\r
subdivision system.  Another thing you can do is to try to make\r
most of your subruns have lengths which are powers of two.  This\r
will let you use shifts instead of divides when computing r,s, and\r
t, which cuts down on your overhead, which lets you use more\r
subdivisions and get the same speed.\r
\r
    Note something very important.  Subdivision increases the\r
overhead per run; biquadratic and other things increase the\r
cost of the inner loop.  Before you go crazy trying to optimize\r
your arbitrarily-angled polygon renderer, make sure you're\r
rendering some "typical" scenes.  The "right" answer is going\r
to depend on whether you have lots of very shorts runs or\r
fewer, longer runs.  If you optimize based on a simple test\r
case, you may end up suboptimal on the final code.\r
\r
    You probably still want to have both a column-based and a\r
row-based renderer, and use whichever one the polygon is\r
"closer to" (e.g. if Hc is closer to 0 than Vc, use the row-based).\r
Note that the free-direction renderer looks its worst (to me)\r
for very small rotations, i.e. when Hc or Vc are very close to 0.\r
Since in these cases not much subdivision is needed, even if you\r
choose to use a free-direction mapper as your primary renderer,\r
you might still want to have "almost wall" and "almost floor"\r
renderers as well.\r
\r
    Finally, there is one more approximation method you can use,\r
which is faster than any of the ones discussed so far, but is\r
simply totally and utterly wrong.  This is the approach used\r
by Michael Abrash in his graphics column in Dr. Dobbs.  While\r
it's quite wrong, it works on polygons which are entirely\r
constant Y (sorry, Z), and can be a noticeable speedup.\r
\r
    What you do is 2D (instead of 3D) interpolation.  You mark\r
each vertex with its coordinates in the texture map.  Then when\r
you scan convert, you interpolate these values between vertices\r
on the edges of your runs.  Thus, scan conversion will generate\r
runs with (u,v) values for the left and right end.  Now simply\r
compute (du,dv) by subtracting and dividing by the length (no\r
clamping will be necessary), and use your fast bilinear inner\r
loop.  When combined with 3D polygon subdivision, this approach\r
can actually be useful.\r
\r
  A cheat:\r
\r
    When the player is moving, set your internal quality\r
settings a little lower.  When the player stops, switch\r
back to the normal quality; if the player pauses the game,\r
render one frame in normal quality.\r
\r
    If done right, you can get a small boost to your fps\r
without anyone being able to tell that you did it.  You\r
may have to use normal quality if the player is only\r
moving very slowly, as well.\r
\r
    Note that while this may sound like an utterly cheap\r
trick just to improve the on-paper fps number, it's actually\r
quite related to the "progressive refinement" approach used\r
by some real VR systems (which, when the viewer isn't moving,\r
reuse information from the previous frame to allow them to\r
draw successive frames with more detail).\r
\r
    There are a number of ways of improving this cheat\r
intelligently.  If the player is moving parallel to a polygon,\r
that polygon will tend to be "stably" texture mapped (similar\r
mapping from frame to frame).  If there is any distortion from\r
your approximation, this will be visible to the player.  So\r
this means a rule of thumb is to only cheat (draw with\r
above-average distortion) on polygons that are not facing\r
parallel to the direction of motion of the player.\r
\r
TEX\r
TE   Light My Fire\r
T\r
\r
    If you're texture mapping, it's generally a good idea\r
to light your polygons.  If you don't light them, then it\r
may be difficult to see the edge between two walls which\r
have the same texture (for instance, check out the "warehouse"\r
section of registered DOOM, which is sometimes confusing\r
when a near crate looks the same color as a far crate).\r
\r
    Lighting is actually pretty straightforward, although\r
you take a speed hit in your inner loop.  I'm not going\r
to worry about actual lighting models and such; see other\r
articles for discussion on how to do light-sourced polygons.\r
\r
    Instead I'm going to assume you've computed the lighting\r
already.  We'll start with "flat-run" shading, wherein an\r
entire run has the same intensity of light falling on it.\r
\r
    DOOM uses flat-run shading.  A given polygon has a certain\r
amount of light hitting it, which is the same for the entire\r
polygon.  In addition, each run of the polygon is sort-of\r
lit by the player.  Since runs are always at a constant\r
depth, you can use constant lighting across the run and\r
still change the brightness with distance from the player\r
(DOOM uses something that resembles black fog, technically).\r
\r
    So the only real issue is _how_ you actually get the\r
lighting to affect the texture.  Several approaches are\r
possible, but the only one that I think anyone actually uses\r
is with a lighting table.\r
\r
    The lighting table is a 2D array.  You use the light\r
intensity as one index, and the pixelmap color as the\r
other index.  You lookup in the table, and this gives\r
you your final output color to display.  (With two\r
tables, you can do simple dithering.)  So the only thing\r
you have to do is precompute this table.\r
\r
    Basically, your inner loop would look something like this:\r
\r
  ...compute light...\r
  for (i=start_x; i <= end_x; ++i) {\r
    color = texture[v >> 16][u >> 16];\r
    output = light_table[light][color];\r
    screen[i] = output;\r
    u += du;\r
    v += dv;\r
  }\r
\r
    The next thing to consider is to Gouraud shade your\r
texture map.  To do this, you need to compute the light\r
intensity at the left and right edge of the run; look\r
elsewhere for more details on Gouraud shading.\r
\r
    Once you've got that, you just do something like this:\r
\r
  z = light1 << 16;\r
  dz = ((light2 - light1) << 16) / (end_x - start_x);\r
  for (i=start_x; i <= end_x; ++i) {\r
    color = texture[v >> 16][u >> 16];\r
    output = light_table[z >> 16][color];\r
    screen[i] = color;\r
    u += du;\r
    v += dv;\r
    z += dz;\r
  }\r
\r
    Note that you shouldn't really do this as I've written the\r
code.  light1 and light2 should be calculated with 16 bits of extra\r
precision in the first place, rather than having to be shifted\r
left when computing z.  I just did it that way so the code\r
would be self-contained.\r
\r
    I'm going to attempt to give a reasonably fast assembly\r
version of this.  However, there's a big problem with doing\r
it fast.  The 80x86 only has one register that you can\r
address the individual bytes in, and also use for indexing--BX.\r
This means that it's a real pain to make our inner loop alternate\r
texture map lookup and lighting fetch--whereas it's almost\r
trivial on a 680x0.  I avoid this somewhat by processing two\r
pixels at a time; first doing two texture map lookups, then\r
doing two lighting lookups.\r
\r
     Here's a flat-shading inner loop.  I'm doing this code off the\r
top of my head, so it may have bugs, but it's trying to show\r
at least one way you might try to do this.  Since I use BP,\r
I put variables in the FS segment, which means DS points\r
to the texture, GS to the lighting table.\r
\r
        mov  ch,fs:light\r
        adc  ax,ax\r
loop8   shr  ax,1          ; restore carry\r
        mov  cl,[bx]       ; get first sample, setting up cx for color lookup\r
        adc  edx,esi       ; update v-high and u-low\r
        adc  ebx,ebp       ; update u-high and v-low\r
        mov  bh,dl         ; move v-high into tmap lookup register\r
        mov  ah,[bx]       ; get second sample, save it in ah\r
        adc  edx,esi\r
        adc  ebx,ebp\r
        mov  dh,bl         ; save value of bl\r
        mov  bx,cx         ; use bx to address color map\r
        mov  al,gs:[bx]    ; lookup color for pixel 1\r
        mov  bl,ah         ; switch to pixel 2\r
        mov  ah,gs:[bx]    ; lookup color for pixel 2\r
        mov  es:[di],ax    ; output both pixels\r
        mov  bl,dh         ; restore bl from dh\r
        mov  bh,dl\r
        adc  ax,ax         ; save carry so we can do CMP\r
        add  di,2\r
        cmp  di,fs:last_di ; rather than having to decrement cx\r
        jne  loop8\r
\r
    For a Gouraud shading inner loop, we can now have three\r
different numbers u, v, and z, which we're all adding at every\r
step.  To do this, we use THREE adc, and we have to shuffle\r
around which high-bits correspond to which low-bits in a\r
complex way.  I'll leave you to figure this out for yourself,\r
but here's an attempt at the inner loop.\r
\r
loop9   shr  ax,1          ; restore carry\r
        mov  al,fs:[bx]    ; get first sample\r
        mov  ah,cl         ; save away current z-high into AH\r
                           ; this makes AX a value we want to lookup\r
        adc  edx,esi       ; update v-high and u-low\r
        adc  ebx,ebp       ; update u-high and z-low\r
        adc  ecx,z_v_inc   ; update z-high and v-low\r
        mov  bh,dl         ; move v-high into tmap lookup register\r
        mov  ch,fs:[bx]    ; get second sample, save it in ch\r
        mov  dh,bl         ; save value of bl\r
        mov  bx,ax\r
        mov  al,gs:[bx]    ; lookup first color value\r
        mov  bl,ch\r
        mov  bh,cl\r
        mov  ah,gs:[bx]    ; lookup second color value\r
        mov  es:[di],ax    ; output both pixels\r
        mov  bl,dh         ; restore bl from dh\r
        adc  edx,esi\r
        adc  ebx,ebp\r
        adc  ecx,z_v_inc\r
        mov  bh,dl\r
        adc  ax,ax         ; save carry\r
        add  di,2\r
        cmp  di,last_di    ; rather than having to decrement cx\r
        jne  loop9\r
\r
    Notice that both of these loops are significantly slower\r
than the original loop.  I'm not personally aware of any\r
generally faster way to do this sort of thing (but the code\r
can be tweaked to be faster).  The one exception is\r
that for flat-run shading, you could precompute the entire\r
texture with the right lighting.  This would require a lot\r
of storage, of course, but if you view it as a cache, it\r
would let you get some reuse of information from frame to\r
frame, since polygons tend to be lit the same from frame to\r
frame.\r
\r
    Finally, here's a brief discussion of transparency.\r
There are two ways to get transparency effects.  The first\r
one is slower, but more flexible.  You use _another_ lookup\r
table.  You have to paint the texture that is transparent\r
after you've drawn things behind it.  Then, in the inner\r
loop, you fetch the texture value (and light it) to draw.\r
Then you fetch the pixel that's currently in that location.\r
Lookup in a "transparency" table with those two values as\r
indices, and write out the result.  The idea is that you\r
do this: table[new][old].  If new is a normal, opaque,\r
color, then table[new][old] == new, for every value of old.\r
If new is a special "color" which is supposed to be transparent,\r
then table[new][old] == old, for every value of old.  This causes\r
old to show through.  In addition, you can have translucency\r
effects, where table[new][old] gives a mixture of the colors\r
of old and new.  This will let you do effects like the\r
translucent ghosts in the Ultima Underworlds.\r
\r
    However, the above approach is extremely slow, since you\r
have to load the value from the pixel map and do the extra\r
table lookup.  But it works for arbitrary polygons.   DOOM\r
only allows transparency on walls, not on ceilings and floors.\r
Remember we noticed that the special thing about walls is\r
that u is constant as you draw a column from a wall; you\r
are walking down a column in the texture map at the same\r
time you are drawing a column on screen.  What this means\r
is that you can use a data structure which encodes where\r
the transparency in each column of the texture map is, and\r
use that _outside_ the inner loop to handle transparency.\r
For example, your data structure tells you that you have\r
a run of 8 opaque pixels, then 3 transparent pixels, then\r
5 more opaque ones.  You scale 8, 3, and 5 by the rate at\r
which you're walking over the textures, and simply treat\r
this as two seperate opaque runs.\r
\r
    The details of this method depend on exactly how you're\r
doing your hidden surface removal, and since it doesn't\r
generalize to floors&ceilings, much less to arbitrarily\r
angled polygons, I don't think going into further detail\r
will be very useful (I've never bothered writing such a\r
thing, but I'm pretty sure that's all there is to it).\r
\r
\r
TEX\r
TE   The Postman Always Rings Twice\r
T\r
\r
    If you're going to write to a slow 16-bit VGA card, you\r
should try your darndest to always write 2 pixels at a time.\r
\r
    For texture mapping, your best bet is to build your screen\r
in a buffer in RAM, and then copy it to the VGA all at once.\r
You can do this in Mode 13h or in Mode X or Y, as your heart\r
desires.  You should definitely do this if you're painting\r
pixels more than once while drawing.\r
\r
    If, however, you wish to get a speedup by not paying\r
for the extra copy, you might like to write directly to the\r
VGA card from your inner loop.\r
\r
    You might not think this is very interesting.  If the\r
write to the screen buffer in regular RAM is fast, how much\r
can you gain by doing both steps at once, instead of splitting\r
them in two?\r
\r
    The reason it is interesting is because the VGA, while\r
slow to accept multiple writes, will let you continue doing\r
processing after a single write.  What this means is that\r
if you overlap your texture mapping computation with your\r
write to the VGA, you can as much as double your speed on\r
a slow VGA card.  For example, the fastest I can blast my\r
slow VGA card is 45 fps.  I can texture map floor-style directly\r
to it at 30 fps.  If I texture map to a memory buffer,\r
this is still somewhat slow, more than just the difference\r
between the 30 and 45 fps figures.  Thus, my total rate if\r
I write to an offscreen buffer drops as low as 20 fps, depending\r
on exactly what I do in the texture map inner loop.\r
\r
    Ok, so, now suppose you've decided it might be a speedup\r
to write directly to the VGA.  There are two problems.  First\r
of all, if you're in mode X or Y, it's very difficult to\r
write two bytes at a time, which is necessary for this\r
approach to be a win.  Second of all, even in mode 13h, it's\r
difficult to write two bytes at a time when you're drawing\r
a column of pixels.\r
\r
    I have no answer here.  I expect people to stick to\r
offscreen buffers, or to simply process columns at a time\r
and write (at excruciatingly slow rates on some cards) to\r
the VGA only one byte at a time.\r
\r
    One option is to set up a page flipping mode 13h (which\r
is possible on some VGA cards), and to paint two independent\r
but adjacent columns at the same time, so that you can write\r
a word at a time.  I have a very simple demo that does the\r
latter, but it's not for the faint of heart, and I don't\r
think it's a win once you have a lot of small polygons.\r
\r
    Another answer is to have a DOOM-style "low-detail"\r
mode which computes one pixel, duplicates it, and always\r
writes both pixels at the same time.\r
\r
    A final answer is just to ignore the market of people\r
with slow VGA cards.  I wouldn't be surprised if this\r
approach was commonplace in a year or two.  But if you do\r
so with commercial software, please put a notice of this\r
requirement on the box.\r
\r
TEX\r
TE   Mipmapping (or is it Mip-Mapping?)\r
T\r
\r
    Mipmapping is a very straightforward technique that\r
can be used to significantly improve the quality of your\r
textures, so much so that textures that you could not\r
otherwise use because they look ugly become usable.\r
\r
    The problem that mipmapping addresses is as follows.\r
When a texture is far in the distance, such that its\r
on-screen size in pixels is significantly smaller than\r
its actual size as a texture, only a small number of\r
pixels will actually be visible.  If the texture contains\r
areas with lots of rapidly varying high contrast data,\r
the texture may look ugly, and, most importantly,\r
moire artifacts will occur.  (To see this in DOOM, try\r
shrinking the screen to the smallest setting and going\r
outside in shareware DOOM.  Many of the buildings will\r
show moire patterns.  In registered DOOM, there is\r
a black-and-blue ceiling pattern which has very bad\r
artifacts if it is brightly lit.  Go to the mission\r
with the gigantic round acid pool near the beginning.\r
Cheat to get light amplification goggles (or maybe\r
invulnerability), and you'll see it.)\r
\r
    Mipmapping reduces these artifacts by precomputing\r
some "anti-aliased" textures and using them when the\r
textures are in the distance.\r
\r
    The basic idea is to substitute a texture map half as\r
big when the polygon is so small that only every other\r
pixel is being drawn anyway.  This texture map contains\r
one pixel for every 2x2 square in the original, and is\r
the color average of those pixels.\r
\r
    For a 64x64 texture map, you'd have the original\r
map, a 32x32 map, a 16x16 map, an 8x8 map, etc.\r
\r
    The mipmaps will smear out colors and lose details.\r
You can best test them by forcing them to be displayed\r
while they're still close to you; once they appear to\r
be working, set them up as described above.\r
\r
    Mipmapping causes a somewhat ugly effect when you\r
see the textures switch from one mipmap to the next.\r
However, especially for some textures, it is far less\r
ugly than the effect you would get without them.\r
\r
    For example, a fine white-and-black checkerboard\r
pattern (perhaps with some overlaid text) would look\r
very ugly without mipmapping, as you would see random\r
collections of white and black pixels (which isn't too\r
bad), and you would see curving moire patterns (which\r
is).  With mipmapping, at a certain distance the whole\r
polygon would turn grey.\r
\r
    I do not believe any existing games for the PC\r
use mipmapping.  However, examining the data file\r
for the Amiga demo version of Legends of Valour showed\r
smaller copies of textures, which made it look like\r
mipmapping was being used.\r
\r
    Mipmapping requires 33% extra storage for the\r
extra texture maps (25% for the first, 25% of 25%\r
for the second, etc.).\r
\r
    This may also be a good idea for 2D bitmaps which\r
are scaled (e.g. critters in Underworld & DOOM, or\r
ships in Wing Commander II--although none of those\r
appeared to use it.)\r
\r
    SGI's Reality Engine does mipmapping.  Actually,\r
it does a texturemap lookup on two of the mipmaps,\r
the "closer" one and the "farther" one, and uses\r
a weighted average between them depending on which\r
size is closer to correct.  (The RE also does\r
anti-aliasing, which helps even more.)\r
\r
\r
TEXTURE\r
TEXUE\r
TXR    Where Do We Go From Here?\r
X\r
\r
    The above discussion mostly covers what is basically\r
the state of the art of texture mapping on the PC.  Hopefully\r
in the future every game will be at least as fast as the\r
inner loops in this article allow.\r
\r
    As long as people want full-screen images, it'll\r
be a while before we have enough computational power\r
to do more than that.  But if we did have more power,\r
what else could we do with it?\r
\r
    o  Better lighting\r
      o  Colored lighting (requires complex lookup tables)\r
      o  Phong shading (interpolation of normals--one sqrt() per pixel!)\r
    o  Higher resolution (640x400, or 640x400 and anti-alias to 320x200)\r
    o  A lot more polygons\r
    o  Bump mapping (can be done today with huge amounts of precomputation)\r
    o  Curved surfaces\r