|====================================|
                  |                                    |
                  |   TELEMACHOS proudly presents :    |
                  |                                    |
                  |    Part 4 of the PXD trainers  -   |
                  |                                    |
                  |          3D Vector engine          |
                  |         Differnt poly-fills        |
                  |                                    |
                  |====================================|

         ___---__-->   The Peroxide Programming Tips   <--__---___

<><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><>


Intoduction
-----------

As promised in my last tuturial this one will be on different types of fills
that we can add to our basic 3D engine.
If you have not read my previous tuturial (pxdtut3.zip) I suggest you get a
copy of it as we'll use some code we discussed in it.
This tuturial is about one (two) week late. This is because some work came up -
involving a trip to a danish island with about 60 kids in the age 4-6 years,
arranging a local sailing tournement and eating lots of sweets while drinking
softdrinks and watching video.
So as you see I'm a busy man 8)

But well.. better late than never - here goes :

    - Z-shading : Bad type of flatshading... but I'll tell you anyway...
    - Flat shading according to moving lightsources
    - Gouraud shading according to moving lightsources
    - Texturemapping
    - Environmentmapping / Fake Phong....



Z-SHADING
-----------

This one you can implement in about 2 minutes in the 3D object engine we build
in the last tuturial.
The theory behind Z-shading is that a face usually darkens when moving farther
away from the light.
As we store the center Z-values for all our faces in a variable called Centers
we can easily determine the distance from the light to the center of the face.
Now we convert this Z-value into a value that lies in the colorspan we use for
shades.
As you have probably noticed this means that the lightsource is placed at a
fixed position somewhere outside the screen pointing straight into the screen.

Take a look at this piece of code to see how it could be implemented :


Procedure BadFlatShade(where : word; minZ, maxZ, Num_of_shades : integer);
{********************************************************************}
{**  MinZ, MaxZ : What is the minimum and maximum Z-values of the  **}
{**               faces that is to be drawn ? You COULD set theese **}
{**               values so that minZ is the minimum Z-val of the  **}
{**               entire object and MaxZ the maximum value. However**}
{**               consider the fact that half of the objects faces **}
{**               is removed by hidden face removal. So, if you    **}
{**               want to have bigger diference on the shown faces **}
{**               just set minZ to minimum object Z-value and MaxZ **}
{**               to the Z-value of the CENTER of the object.      **}
{**               Experiment!!                                     **}
{** Num_of_shades : shades used = color 0 to Num_of_shades         **}
{********************************************************************}

var
 taeller : integer;
 X1,Y1,X2,Y2,X3,Y3,X4,Y4 : integer;
 color : byte;
 polynr : integer;
 normal,span : integer;
 shade : real;
begin
 for taeller := 1 to Num_of_faces do
   begin
     polynr := OrderTable[taeller];
     X1 := translated[faces[polynr].P1].X;
     Y1 := translated[faces[polynr].P1].Y;
     X2 := translated[faces[polynr].P2].X;
     Y2 := translated[faces[polynr].P2].Y;
     X3 := translated[faces[polynr].P3].X;
     Y3 := translated[faces[polynr].P3].Y;
     X4 := translated[faces[polynr].P4].X;
     Y4 := translated[faces[polynr].P4].Y;

     {***************** Z-shading *****************}

     span := ABS (minZ-maxZ);   {Z span of object}
     shade := (centers[taeller] div 4 + ABS(minZ)) / span;

     color := Num_of_shades - round(Num_of_shades*shade);

     {*******************************************************}
     {******* HIDDEN FACE REMOVAL - YES, THAT EASY ;) *******}
     {*******************************************************}
     {Z-Comp of normal to 2d-polygon}
     normal := (Y1-Y3)*(X2-X1) - (X1-X3)*(Y2-Y1);
       if (normal < 0) then {pointing towards us}
         Polygon(X1,Y1,X2,Y2,X3,Y3,X4,Y4,color,where);
     {*******************************************************}
     {*******************************************************}
     {*******************************************************}
   end;
end;




NICE FLATSHADING - THE THEORY BEHIND THE LIGHTVECTOR / DOT-PRODUCT
-------------------------------------------------------------------

Now... while the above shown piece of code works quite allright on simple
objects as fx. cubes it will not produce an acceptable shading for more complex
objects.
And the situation with the fixed lightsource is'nt to good either. So we'll
have to find some better way of shading our objects. Remember the facenormals
we discussed in the last tuturial - I told you they could be used for shading
and I did not lie :)

To refresh your memory I'll just show you the formulas again :

        Xnormal=(P2.Y-P1.Y)(P1.Z-P3.Z)-(P2.Z-P1.Z)(P1.Y-P3.Y)
        Ynormal=(P2.Z-P1.Z)(P1.X-P3.X)-(P2.X-P1.X)(P1.Z-P3.Z)
        Znormal=(P2.X-P1.X)(P1.Y-P3.Y)-(P2.Y-P1.Y)(P1.X-P3.X)

Now, if we define the lightsource as a vector also :

        LightVect  : RealPointT;

then the direction of the lightsource can be set by defining LightVect.X,
LightVect.Y and LightVect.Z

Now, the amount of light that shines on an object is determined by the angle
between the lightsource and the facenormal. Take a look at this picture..

                normal
                  |         / <-- the lightsource
                  |       /
                  |_ A  /
                  |  \/
                  | /
                  |
        ---------------------  <-- a face in the object


If the light shines directly on the face a maximum amount of light should be
shown, and the angle A would be 0 degree.
The greater the angle, the darker shade.

Now is the time for another new term - UNITVECTOR. A unitvector is simply a
vector with the length 1. Any vector can easily be made a unitvector by
dividing all three vectorcomponents by the entire vector length.
The length of a vector is calculated by :

    length = SQRT(X*X + Y*Y + Z*Z);

Obviously it's WAY to slow to :

1) Calculate the facenormal.
2) Calculate the length of the normal (SQRT is SLOOOW)
3) Divide all three components by length

So what we'll do is to calculate the facenormals and make them unitvectors ONE
time when setting up the object. Then we rotate these unitvectors for each
frame. This is of cause not entirely true. If we made our facenormals unit-
vectors during setup we would have to store all vectorcomponents as reals.
And then our rotation routine could not handle them. So we store the unit-
vectors as fx. 8.8 fixed point values. As all vectorcomponents range from 0
to 1 we could easily store them as 1.15 fixed point values... but if we store
them as 8.8 it'll make environmentmapping easier... :)
As with the object itself, store the original normalvectors in a buffer and
rotate the buffer into another buffer from which you do all the calculations
on the rotated normals - this way you'll not lose precision during rotation.

Now, if we define both the facenormal and the lightvector as UNITVECTORS
we can use a new formula called the dot-product to calculate the angle between
them. Actually the dot-product returns the cosinus values of the angle - but
this is PERFECT!
As cos ranges from 0 to 1 and being 1 at 0 degrees and 0 at 90 degrees we can
just multiply the cosinus value by the numbers of shades we want in our object.

The dot-product :

dot := (Normal.X*Lightvect.X) + (Normal.Y*Lightvect.Y) + (Normal.Z*Lightvect.Z);


Now go implement this in your engine.... It COULD look like this :


Procedure NiceFlatShade(where : word; Num_of_shades : integer);
var
 taeller : integer;
 X1,Y1,X2,Y2,X3,Y3,X4,Y4 : integer;
 color : byte;
 polynr : integer;
 normal : integer;
 shade : real;
 Nx,Ny,Nz : real;
 dot : real;

begin
 for taeller := 1 to Num_of_faces do
   begin
     polynr := order[taeller];
     X1 := translated[faces[polynr].P1].X;
     Y1 := translated[faces[polynr].P1].Y;
     X2 := translated[faces[polynr].P2].X;
     Y2 := translated[faces[polynr].P2].Y;
     X3 := translated[faces[polynr].P3].X;
     Y3 := translated[faces[polynr].P3].Y;
     X4 := translated[faces[polynr].P4].X;
     Y4 := translated[faces[polynr].P4].Y;


     {*******************************************************}
     {******* HIDDEN FACE REMOVAL - YES, THAT EASY ;) *******}
     {*******************************************************}
     {Z-Comp of normal to 2d-polygon}
     normal := (Y1-Y3)*(X2-X1) - (X1-X3)*(Y2-Y1);
       if (normal < 0) then {pointing towards us}
         begin
           {************************************************************}
           {**   LAMBERTS FLATSHADING ACCORDING TO MOVING LIGHTSOURCE **}
           {************************************************************}

          Nx := RotNormals[polynr].X / 256;
          Ny := RotNormals[polynr].Y / 256;
          Nz := RotNormals[polynr].Z / 256;
          dot := (Nx*Lightvect.X) + (Ny*Lightvect.Y) + (Nz*Lightvect.Z);
          if (dot > 1) or (dot < 0) then dot := 0;
          color := Round(dot * Num_of_shades);
          Polygon(X1,Y1,X2,Y2,X3,Y3,X4,Y4,color,where);
         end;
     {*******************************************************}
     {*******************************************************}
     {*******************************************************}
   end;
end;



GOURAUD SHADING
----------------

After Flatshading comes Gouraud shading. Gouraud shading is the first shading
type which does not have a constant color for a face in the object.
First thing to say is, that gouraud shading is based on linear interpolation
of colorvalues/lightintensities.
We still draw the polygon scanline pr scanline, but now we need more than just
two X-values to draw the line. We also needs two colors per line. Namely the
starting color and the ending color. When we draw our horizontal line, we use
fixed point math to step through the colorspan the line consist of.
Take a look at this gouraud line drawer :


PROCEDURE GouraudHorline(xbeg,xend,y:integer; c1,c2:byte;where : word);
var coloradd : integer;
begin
 if (Xend-Xbeg) <> 0 then
 coloradd := ((c2-c1) shl 8) div (Xend-Xbeg);

 asm
  mov bx,[xbeg]
  mov cx,[Xend]

  inc cx
  sub cx,bx             { length of line in cx }
  mov es,Where          { segment to draw in   }
  mov ax,[y]            { Ypos of the line     }
  shl ax,6
  mov di,ax
  shl ax,2
  add di,ax             { y*320 in di (offset) }
  add di,bx             { add x-begin }

  xor ax,ax
  mov al,[C1]
  shl ax,8              {colorstart fixed-p 8.8 }

 @again:
  mov es:[di],ah        {ah = real value of fixed-p color (ah = ax shr 8 ) }
  inc di
  dec cx
  add ax,[coloradd]
  cmp cx,0
  jne @again
 end;
end;


Thats all well and good.....  but how do we calculate C1 and C2 for each
horizontal line ?
Well.. for a start we'll calculate the color for each of the 4 points in our
polygon. This is done in a way similar to the way we calculated the face color
in flat shading - by calculating the dot-product of the lightvector and the
POINT-normal.
Now, as you all know, one can't calculate a normal to a point. It has to be a
plane. So we'll have to think of our own way of defining the term POINT-normal.
It has been decided that the normal to a point is calculated by taking the
average of the FACE-normals in which the point is included.
You could calculate the 4 normals pr. face each frame - or you could calculate
them once during setup and then rotate them like the face normals.
Suit yourself.
Remember!  The POINT-normals has to be unitvectors. The fact that the
FACE-normals are unitvectors does NOT mean that the calculated POINT-normals
will be too.
So, you'll have to make them unitvectors for each frame.
All this means that the solution with the POINT-normals being rotated is
probably the best/fastest :)

When you got the 4 color values for the 4 points of the polygon you scan the
edges as with the normal polygon routine I showed you in the last tut.
But as you scan along the edges you shade them at the same time - much like
the GouraudHorLine procedure.... the difference is just that the line you
shade is'nt horizontal. In the end, you'll have two variables filled with the
info needed to draw our gouraud shaded polygon :

    polygon[1..200,1..2] :  the X-values to draw the lines between
    color[1..200,1..2]   :  the starting and ending colors for each HorLine

I'll just show you the new ScanPolySide procedure :


Procedure ScanPolySide(x1,y1,x2,y2:integer;c1,c2 : byte);
  { This scans the side of a polygon and updates the poly variable }
  {updates the colors variable for gouraud shading}
VAR temp:integer;
    xfixed,xinc,x:integer;
    loop1:integer;
    dcol : integer;
    color : integer;
BEGIN
  if y1=y2 then exit;
  if y2<y1 then
   BEGIN
     temp:=y2;
     y2:=y1;
     y1:=temp;
     temp:=x2;
     x2:=x1;
     x1:=temp;
     temp := c2;
     c2 := c1;
     c1 := temp;
   END;          {make sure y1 is top and y2 bottom}

  dcol := ((c2-c1) shl 8) div (Y2-Y1);    {colorstep pr. y-line}
  color := c1 shl 8;                      {starting color in fixed-p}

  xinc:=((x2-x1) shl 7) div (y2-y1);      {xinc in fixed point}
  xfixed:=x1 shl 7;
  for loop1:=y1 to y2 do BEGIN
    if (loop1>(ytopclip)) and (loop1<(ybotclip)) then
      BEGIN
        x := xfixed shr 7;
        if (x<polygon[loop1,1]) then
         begin
           polygon[loop1,1]:=x;
           colors[loop1,1] := color shr 8;
         end;
        if (x>polygon[loop1,2]) then
         begin
           polygon[loop1,2]:=x;
           colors[loop1,2] := color shr 8;
         end;
      END;
    xfixed:=xfixed+xinc;
    color := color + dcol;
  END;
END;



Now... that was'nt too hard ehh ??
Put this new ScanPolySide into your polygon routine and change the call to
HorLine to GouraudHorLine with the parameters :

      GouraudHorline(polygon[loop,1],polygon[loop,2],loop,
                     colors[loop,1], colors[loop,2]);

That should do the trick - a nice Gouraud shaded polygon.
Check out the sample program if you have any trouble coding this effect.



TEXTUREMAPPING
---------------

Now, the first thing I would like to say in this section is that the texture
mapping we'll do here differs ALOT from the one I wrote about in tuturial 1.
The difference is that while the texturemapping in tuturial 1 had correct
perspective this type won't.
The reason we could do perspectively correct texturemapping in tut 1 was that
all the polygons we mapped had constant Z-values for each VERTICAL scanline.
That means that all the perspective calculations only needs to be calculated
ONCE pr scanline. We could do the same thing with  polygons with constant
Z-values for each HORIZONTAL scanline.
But the polygon we're mapping today is often rotated so there is NO constant
Z-values. Therefor heavy calculation is needed for each pixel in the polygon
to calculate the u,v coordinate in the texture.

So, what we'll do is called a linear texturemapping. It works fine on the kind
of objects that is seen in demos 'cause they often move to fast for the viewer
to see the perspective errors.

We'll use the same polygon drawing routine as for all the other fills. The only
diffence lies in the ScanPolySide and in the horizontal line drawer -
U probably allready guessed that :)

When calling the TextureMappedPolygon routine we assign 4 texture coordinates
- one to each point in the polygon. We call these coordinates :

  U1,V2, U2, ... , V4

When scanning the four sides in the polygon we also store two texture
coordinates for each horizontal line. The implemention of this is VERY much
like the one in gouraud shading - only with one more value to increment.
Check out the sample program if you have any trouble.

Now for the TextureMappedHorline routine ;)
It has to scan through the texturemap while drawing the horizontal line. It is
quite easy to do, using fixed point math :


PROCEDURE TextureMapHorline(xbeg,xend,y,u1,v1,u2,v2:integer;source,dest : word);
var
  DeltaX : integer;
  DeltaY : integer;

begin
  If (Xend-Xbeg) <> 0 then
   begin
     DeltaX := ((u2-u1) shl 7) div (Xend-Xbeg);
     DeltaY := ((v2-v1) shl 7) div (Xend-Xbeg);  { 9.7 fixed-p}
     DeltaX := DeltaX + DeltaX;
     DeltaY := DeltaY + DeltaY;                  {now 8.8 fixed-p :)  }
   end
    else
   begin
    DeltaX := 0;
    DeltaY := 0;
   end;
asm
  push ds
  mov ax, [source]
  mov ds,ax

  mov bx,[xbeg]
  mov cx,[Xend]
  inc cx
  sub cx,bx            {cx =  length of line}

  mov es,dest
  mov ax,[y]
  shl ax,6
  mov di,ax
  shl ax,2
  add di,ax
  add di,bx           {es:[di] start of line}

  mov ah,byte[v1]   {8.8 fixed-p value of YTexturePos - for easy ofs calc}
  mov al,byte[u1]
  mov si,ax         {si = starting offset in texture }
  mov dh,al         {8.8 fixed-p value of XTexturePos - for easy ofs calc}

@again:
  movsb               {draw byte}
  add ax,[DeltaY]     {advance in texturemap}
  add dx,[DeltaX]     {advance in texturemap}

  mov bh,ah           {bh = Ypos * 256 }
  mov bl,dh           {bl = Xpos_fixed / 256  = Xpos_real}
  mov si,bx           {BX = Ypos_real * 256 + Xpos_real = offset}

  dec cx
  cmp cx,0
  jne @again          {are we finished ??  }

  pop ds
end;
end;


As you see our Texture has to be placed in a 256X256 orientated coordinate
system. This does not mean that the texture HAS to be 256X256, but it must be
stored with 256 bytes pr line.
This means you probably has to rewrite your image loader a little - and if you
normally use a virtuel screen with the size 320X200 you have to allocate a
little more memory. 320X200 = 64000 bytes while 256X256 = 64Kb... NOT the
same :)



ENVIRONMENT MAPPING / PHONG SHADING
------------------------------------

What is environement mapping ? Well.. environment mapping is an effect where
an image is reflected on a shiny surface.
The implementation is a straight texturemap - the only thing there is to
environment mapping is calculating the 4 texturecoordinates needed for our
polygon drawer. In ordinary texturemapping we allways set these to the corners
of the image. This is not the case in environmentmapping.

How DO we calculate the coordinated then ?? Well... it's allmost TOO easy.
We simply use the POINT-normals again. As we have stored these in 8.8 fixed
point we know all vectorcomponents ranges from -256 to 256.
We just use the X and Y vectorcomponents for U and V TextureCoodinates needed
for the point, so the only problem is to translate the value so it lies in the
range 0 to 256.
The solution is simple - divide the values by 2 and add 128 to the result.
Voila! U and V coordinates for the Texturemapping routine is found..


What about this phong shading then ?
Well.. for a start I'll just briefly explain the working of REAL phong shading.
As with all other types of shading the light-intensity is calculated by the
dot-product. In Flatshading we did ONE dot-calculation to find the color.
In gouraud we did FOUR dot-calculations to find the color at each of the 4
points.
In Phong shading you do a dot-calculation ON EVERY SINGLE PIXEL IN THE POLYGON!
Ie. the light-intensity is calculated PRECISELY for every single pixel.
So for each pixel we have to

           1) Calculate the Normal to the point by making a plane of the
              neighbour pixels.
           2) Make this normal a unitvector
           3) Take the dot-product of the lightsource and the normal
           4) Plot the pixel.

Well.. this don't sound like real time to me :)
Numerous approximations to this routine has been made, but the easiest one is
to simple do an environmentmap of a Phong-map.
A phong map is simply a picture of a lightsource that we calculate. By using
the environment mapping methode discussed above it is possible to do something
that looks pretty much as phong shading.
Check the sample program for the routine for calculating such a map. This is
BTW not mine - took it somewhere but can't remember where.. Thank you whoever
you are :)




MULTIPLY LIGHTSOURCES
-----------------------

Oh yeah.. before I forget. I think I promised to tell you how to implement
multiple moving lightsources. And I'm not a man who breaks my word :)

First thing first : multiple lightsources. This is incredibly easy to implement.
Instead of just having ONE lightvector you make an array with as many as you
wish.
When calculating the color you just add the lightintensities for all the
lightsources together before multiplying with the number of shades. Of cause
you has to make sure the intensity does not get bigger than 1.

As for moving lightsources - as the routines just use the lightvector in
color-calculation you can freely move it around by assigning new values to it
for each frame. Just remember to make it a unitvector.



OPTIMIZATIONS
--------------

Now you got all the formulas you need to make nice fills/shadings.
But it is up to you to optimize them. The goal of this tuturial is to make
clear code that is easy to understand - in a tuturial I think that is more
important than some highly optimized assembler code being thrown at you.
Some people has mailed me telling me that my code was unoptimized... that I
needed lots of stuff... like clipping, and more direct camera control.
That is correct - but as mentioned before... this is not meant to be an
example of my coding skills :)
I have left many things out for the sake of easy understanding.

So now you know HOW and WHY the things work... it is then up to you to optimize
them - to make that engine that is just a LITTLE bit faster than everyone
elses..
To see if you can beat Karl/Noone :)

I suggest the following optimizations :

1) Clipping : easy in the normal polygon routine. In Gouraud and texturemap
              you'll have to calculate new starting u,v / color values..

2) Speed    : More assembler, draw two bytes at a time, use another polygon
              drawer. Rotate the point-normals instead of calculating them.

3) Triangles : Make triangle versions of ALL the drawing routines.. often
               used in more complex 3d meshes.


LAST REMARKS
-------------

Well, that's about all for now.
Hope you found this doc useful - and BTW : If you DO make anything public using
these techniques please mention me in your greets or where ever you se fit.
I DO love to see my name in a greeting :=)


This completes to 3D tuturial serie. Hope I explained it well enough for you
to get the grasp of it :)
I myself is very pleased with these last two tuturials as I think they
assembles all the most nessesary 3D theory in only two textfiles. Also they
give the reader examples and explenations of things that I myself has never
seen. Fx. gouraud and environmentmapping. I have never seen any good docs on
these subjects - somehow people allways stopped writing tuturials when reaching
these subjects.

But what now ??
If you have any good ideas for a subject you wish to see a tuturial on please
mail me. If I like the idea (and know anything about it :)  ) I'll write a
tut on it.
In near future I might write a small tuturial on how to use interrups for
various programming problems. But, well.. after that I don't know.



Keep on coding...

  Telemachos - June '97.