====================================
 
 TELEMACHOS proudly presents : 
 
 Part 3 of the PXD trainers  
 
 3D Vector engine 
 The basics of 3D 
 
====================================
_____> The Peroxide Programming Tips <_____
<><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><>
Intoduction

Hiya... I'm Telemachos of Peroxide  a new danish group (yes... we DO
have groups in Denmark too :))) )
Since my last trainer quite a few people has mailed me and asked me to
do trainers on various 3D subjects.
As a result of this I have decided to dedicate my next two trainers
to the realm of 3D graphic.
What we'll be doing in the next two trainers is to build a 3D vector
engine capable of doing most of the effects used in todays demos.
Our engine will have the following features.
Tuturial #3 (this one) :
 Nice 3D object organization  no unnessesary rotations done.
 Depth sorting
 Hidden face removal.
 Solid Fill
 Glenzing
Tuturial #4 (next week or so...) :
 Zshading
 Flat shading according to moving lightsource(s)
 Gouraud Shading according to moving lightsource(s)
 Texturemapping
 Environmentmapping
 Phong Shading (a fake 'cause )
So when you are done with these two tuturials you should be able to
do some nice 3D vector objects.
It might seem that tuturial 4 will be a hard one to get through 
but believe me : We're doing all the preparations in this trainer.
Once our 3D engine is set up all the different shading/fill types are
surprisingly alike :)
******************* ATTENTION ARTISTS!!! *****************************
ARE YOU AN ARTIST ?
DO YOU DRAW VGABITMAPS ?
CAN YOU DO GFX IN ALL RESOLUTIONS  320x200x256 AND VARIOUS SVGAMODES ?
DO YOU WANT TO SEE YOUR WORK IN AMAZING PRODUCTIONS ?
CAN YOU DO GAMEGFX AS WELL AS BACKGROUNDS FOR DEMOS ?
IF YOU MEET THE ABOVE TERMS (or some at least :) ),
THEN DROP ME (TELEMACHOS) A MESSAGE OR MAIL THE GROUP AT :
Peroxide@image.dk
*********************************************************************
If you want to get in contact with me, there are several ways of
doing it :
1) Write me via FIDOnet : 2:235/350.22
2) Email me : tm@image.dk
3) Snail mail me : Kasper Fauerby
Saloparken 226
8300 Odder
Denmark
4) Call me (Voice ! ) : +45 86 54 07 60
Get this serie from the major demorelated FTPsites  currently :
GARBO ARCHIVES (forgot the address) : /pc/programming/
ftp.teeri.oulu.fi : /msdos/programming/docs/
Or grap it from my homepage :
Telemachos' Codin' Corner http://www.image.dk/~tm
FIRST THINGS FIRST!  3D DEFINATIONS AND TRANSLATIONS

Lets define the 3D space where our object is placed. The origin of
the 3D object space is located at the middle of the screen and the
axis is defined as shown below :
\ 
> Xaxis
 \
 \
 \
 \
 \
 \>
 Zaxis (into the screen :) )

V
Yaxis
Ok.. so our object is made from a number of 3D points each defined by
(X,Y,Z) But how do we plot such a 3D point to the screen ?? We must
find some way of translating the 3 coordinated in the 2 coordinates
of the screen.
This is done by calculating the intersection between the vector made
from the 3D point and the eye position and the viewplane.
I won't get into the math involved in this operation  if you'r
interrested go grap a book on vector math and read the bit about
intersection between a line and a plane.
I'll just give you some formulas :
X0 := Xofs + Round(X*(Zeye/(ZeyeZ)));
Y0 := Yofs + Round(Y*(Zeye/(ZeyeZ)));
Set Xofs to 160 and Yofs to 100 to center object space at the center
of the screen.
If you'r unhappy with these formulas (they are a bit slow because of
the Round and all the floating point muls and divs) you can use a
approximation of the formulas :
X0 := Xofs + (x div (zZoff)) shl 8;
Y0 := Yofs + (y div (zZoff)) shl 8;
This will also work allthough not entirely correct.
LETS TALK ABOUT DATASTRUCTURES

Now for the keyword of 3D programming  DATA STRUCTURES !!
In 3D it is VERY important that you think about how to structure your
data so that a minimum of calculations has to be done.
First problem is how to store your 3D object.
The easiest way is to store it an array of polygons, each polygon
consisting of 4 3D points. But it is also the way ONE SHOULD NEVER!!
store 3D objects.
Lets have a look at a simple cube. A cube consists of 6 sides right ?
And each side consist of 4 points. That sums up to 24 points to be
rotated using the above mentioned data structure.
But as we all know there is only 8 corners in a cube  ie. there is
only 8 DIFFERENT points in a cube.
So what we do is to store all the different points in one array  and
then introduce another variable  we could call it faces  to store
information about which points appears in which faces.
This way we only rotates ONE THIRD of the points we rotate using the
first methode.
The goal in 3D is never do do unnessesary calculations. Only rotate
each point ONCE, only draw each pixel on the screen ONCE and so on.
Now some words about precision.
As we are using a pretty low resolution (320X200) a fairly big amount
of rounding is performed when rotation / projecting a 3D point.
If you store your 3D object in a single variable and rotates the
object into the very same variable the object will in time be distorted
from the roundings. So my advice is to store the original 3D object
in ONE variable and then rotate this BASEOBJECT into a buffer from
which you then perform all the calculations on the rotated 3D object.
This way each rotation starts out with a "fresh" 3D object and the
distortion will be minimal.
For an idea of a 3D data structure check out the sample program
supplied with this text.
NOTE!!
This is only meant as an idea of a data structure. Modify it to match
your needs.
OK  NOW I WANT TO ROTATE THE POINTS

Having an object defined by 3D coords is no fun if it just stands
still on the screen. So we want to rotate it around the different
axes.
For this there is 3 formulas  one for each axis. Please note that
the formulas presented here is the standard rotation formulas given
by vector math books. Numerous optimizations has been made to these
routines making rotation a little faster but I won't get into that
in this text. For now the important thing is to make the points
rotate correctly :)
Before we throw ourselves into the formulas one more important note
has to be made. One has to bear in mind that the sequence in which
the point is rotated around the different axes DOES matter. To rotate
the point 5 degrees around the X axis and then 5 degrees around the
Y axis is NOT the same as rotating it about the Y axis and then the
X axis!! Think about it!
So, it has been decided that one rotates around the axes in the
following order : X, Y and then Z.
Ok... now it's time for the formulas :
rotation around Zaxis : (rotating the point X,Y,Z A degrees)
Xrotated = Cos (A)*X  Sin (A)*Y
Yrotated = Sin (A)*X + Cos (A)*Y
Zrotated = Z
rotation around Xaxis :
Xrotated = X
Yrotated = Cos (A)*Y  Sin (A)*Z
Zrotated = Sin (A)*Y + Cos (A)*Z
rotation around Yaxis :
Xrotated = Cos (A)*X  Sin (A)*Z
Yrotated = Y
Zrotated = Sin (A)*X + Cos (A)*Z
OK... these are the formulas  check out the sample program for an
idea of how to combine them in a pretty fast way.
I just grapped the rotation routine from an Asphyxia tuturial
by Denthor.
His routine is a straight implemention of the above mentioned
formulas  in fixed point assembler. Thanx Denthor.
OK.. lets sum things up.
By now we have learned to
 rotate a 3D point around all 3 axis
 Translate a 3D point into 2D screen coordinates
This is allmost enough to get you started coding a 3D object engine.
With this information you could easily code a wirefram engine  as a
matter of fact I suggest you do just that! By coding a simple 3D
engine you really learn the next stuff faster :)
BACK SO SOON ???  POLYGON DRAWING

OK.. I guess you have now coded a wireframe engine (not so hard ehh ?)
and you want more. Lets face it  your demo won't win The Party if
it's only running wireframe 3D graphics.
But we're going to change that  now is the time for solid objects!!
(WEE!!)
To draw a solid face we need to code a good polygon routine.
We'll code it in a way so that all the nice shadings in the next
tuturial will be really easy to implement  I'll tell you how right
now!
What is a polygon ?? In demos most polygons are triangles but today
we'll draw four sided polygons because I'm gonna use a simple square
box for my sample code. Don't worry though  I'll tell you how to do
triangles too.
So we got our four points and we want to fill the shape with some
color.
But how ?? Well... we draw polygons scanline per scanline.
Ie. a polygon is a bunch of horizontal lines.
So the first thing we'll need is a horizontal line drawer :
Procedure HorLine(Xbegin,Xend,Ypos: integer; color: byte; where: word);
Assembler;
asm
mov cx,[Xend]
inc cx
sub cx,[Xbegin] {cx = length of line  used for counter }
{note, I assume that Xbegin < Xend 
the poly routine}
{will take care of that...}
mov ax,[ypos]
shl ax,8
mov di,ax
shr ax,2
add di,ax
add di,[Xbegin] {di = Ypos * 320 + Xbegin  offset for our line}
mov es,[where] {where to draw..}
mov al,[color]
rep stosb {I draw byte by byte  slower than drawing a word}
{at a time but it is because of the changes we are}
{going to make to this routine when
glenzing/gouraud/texturemapping}
end;
OK.. now we just have to find out what the Xcoords for each
scanline is.
We define a variable to hold that information for us :
polygon : Array[0..199,1..2] of byte;
This variable can hold the endpoints of a horizontal line for each of
the 200 ylines on the VGA screen.
Now we want to fill this buffer out with the correct information.
For each of the four sides (three if it were a triangle) we scan
along the edge of the polygon and updates the polygon variable like
this :
Procedure ScanPolySide(X1,Y1,X2,Y2 : integer);
var
DeltaX : integer;
temp : integer;
Xposfixed,Xpos : integer;
counter : integer;
begin
if Y2=Y1 then exit; {exit if side is a horizontal line }
if (Y2<Y1) then {make sure Y1 is top point}
begin
temp := Y1;
Y1 := Y2;
Y2 := temp;
temp := X1;
X1 := X2;
X2 := temp; {switch the points if Y1 is not top..}
end;
DeltaX := ((X2X1) shl 7) div (Y2Y1);
{DeltaX in 9.7 fixed point math}
Xposfixed := X1 shl 7; {Xpos in 9.7 fixed point math }
for counter := Y1 to Y2 do
begin
Xpos := XposFixed shr 7;
if (Xpos < polygon[counter,1]) then polygon[counter,1] := Xpos;
if (Xpos > polygon[counter,2]) then polygon[counter,2] := Xpos;
Xposfixed := XposFixed + DeltaX;
end;
end;
Now... run this procedure on each side of the poly, and the variable
'polygon' is set up and ready for our friend Mr. Horline.
So..
Procedure Polygon(X1,Y1,X2,Y2,X3,Y3,X4,Y4: integer;
color : byte; where : word);
var
counter : integer;
Ymin, Ymax : integer;
polygon : Array[0..199,1..2] of integer;
begin
Ymin := Y1;
Ymax := Y1;
if (Y2 < Ymin) then Ymin := Y2;
if (Y2 > Ymax) then Ymax := Y2;
if (Y3 < Ymin) then Ymin := Y3;
if (Y3 > Ymax) then Ymax := Y3;
if (Y4 < Ymin) then Ymin := Y4;
if (Y4 > Ymax) then Ymax := Y4;
{what is Ymin and Ymax in this polygon ?}
for counter := 0 to 199 do
begin
polygon[counter,1] := 32000;
polygon[counter,2] := 32000;
end;
{we have to initialize our variable 'polygon' to some extreme values}
ScanPolySide(X1,Y1,X2,Y2);
ScanPolySide(X2,Y2,X3,Y3);
ScanPolySide(X3,Y3,X4,Y4);
ScanPolySide(X4,Y4,X1,Y1); {all four sides scanned}
for counter := Ymin to Ymax do
Horline(polygon[counter,1],polygon[counter,2],counter,color,where);
end;
Well... that was pretty easy... Now we can do solid sides in our 3D
cube. Try it out before continuing :)
WHAT  SOMETHING IS WRONG ??  DEPTH SORTING :

YES  I know. You have some problems getting your cube look right when
having different colors for each face. This is because of the random
order we draw the faces in.
We have to find some way of depth sorting them. We sort the faces by
their center point. The Z component of their center point, that is.
So for each frame we have to calculate the center Zvalue for each
face in the object.
To find the center Z value we add the Z values from the 4 points
making the face and divide this value by 4 (if we are talking
triangles obviously we'll divide by 3)
Only that we don't divide at all! If we don't divide by the number of
points we'll NOT end up with the center Z value. We'll end up with a
value that is 4 times to big. But as ALL the calculated Z values will
be 4 times to big they will still sort corectly.
We'll store the values in a variable called
centers : Array[1..Num_of_faces] of integer;
But when we start sorting this table we'll mess up which center that
belongs to which face. To solve this problem we'll introduce another
variable called
OrderTable : Array[1..Num_of_faces] of integer;
This table will store the correct sequence for drawing the faces.
Ie. it'll store the facenumbers belonging to a centervalue.
To do the actual sorting we'll use a simple bubblesort.
This is a pretty simple sorting algoritm which will work for us
as long we are not talking sorting hundreds of faces.
If you are rendering LOTS of faces I suggest you use a quicksort
routine instead.
The idea is to scan through the centers variable and compare the
entries two and two. If the value at position+1 is higher than the
value at position we switch the two values and updates the ordertable
variable.
We then reset the scan and start over. We continue doing this until
we reach the end of 'centers' without having to switch any values.
Procedure Sort_faces;
{Just a simple bubblesort  not to fast but what the heck :) }
{Faces with the HIGHEST Zval is placed first in Order[] }
VAR
counter : integer;
position : integer;
tempval : integer;
BEGIN
for counter:=1 to Num_of_faces do BEGIN
OrderTable[counter]:=counter;
END;
{we resets the ordertable so that it matches the
unsorted 'centers' variable}
position := 1;
repeat
if (centers[position] < centers[position+1]) then
BEGIN
tempval := Centers[position+1];
Centers[position+1] := centers[position];
centers[position] := tempval;
tempval := OrderTable[position+1];
OrderTable[position+1] := OrderTable[position];
OrderTable[position] := tempval;
position:=1;
END;
inc(position);
until (position = Num_of_faces);
END;
Now when doing the faces we draw them in the order specified in
OrderTable.
Go ahead... try it out...
HIDDEN FACE REMOVAL

Fire up your 3D engine and take a look at the rotating cube.
Looks cool ehh ?? Nice work... YOU did that ;)
But try and count the faces visible at a time. How many faces do you
see at one time ? Only about half of them ????
ARGH!! We are drawing half an object that is never seen ???
This won't do. Right now it does not matter much as drawing a polygon
is fairly fast  but next week when we start texturemapping or
shading the faces it will slow things down.
So  we'll just have to remove the faces we do not see.
This is fortunately VERY!! easy.
To be able to perform this operation it is important that you have
defined your faces in a clockwise direction. Ie. all faces should be
defined as :
P1 P2

 
 
 
 
 

P4 P3
Ok... now I'll introduce a new formula to you  the cross product.
The cross product is a formula that returns the normal to a plane :
Xnormal=(P2.YP1.Y)(P1.ZP3.Z)(P2.ZP1.Z)(P1.YP3.Y)
Ynormal=(P2.ZP1.Z)(P1.XP3.X)(P2.XP1.X)(P1.ZP3.Z)
Znormal=(P2.XP1.X)(P1.YP3.Y)(P2.YP1.Y)(P1.XP3.X)
Well... for now we are only interrested in the Z normal.
If the Z normal is negative it means that the normal points towards
us  ie. we draw the face.
If not we discard it.
One more important note to make is that because the Znormal does not
involve any Z components of the points we can use it on the PROJECTED
2D values.
Now go implement this in your 3D engine  if you are having trouble
take a look at the <a href="pxdtut3.zip">sample program</a>.
Next week we'll see how we use this normal (the hole 3D normal though)
for shading...
ONE LAST THING  GLENZING THE POLYGON

OK.. now we have done a 3D object engine that handles 3D objects
correct  showing only what HAS to be shown.
That done I think you are ready for another kind of fill  that
TOTALLY ignores ALL we have learned about sorting and hidden face
removal... SIGH, thats life :)
The effect is called glenzing and the idea is to make the object look
like it is made from colored glass. This effect is done by setting
the correct pallette. I don't think there is any way of calculating
this pallette so you'll have to experiment.
Now when drawing your faces you do not draw the polygon in one color.
For each pixel you grap the background color and add it to the face
color.
This is of course a little slower than doing single colored polygons
but not much. You'll have to change your horizontal line drawer to do
this  check the sample program if you experiment any trouble.
When glenzing you should obviously NOT remove the faces pointing away
from you as they can be seen through the glass sides.
Sorting is useless.... the result will look the same with or without
sorting.
In my opinion glenzing is not a cool effect  but well... it can't
hurt to know how to do it :)
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 :=)
As mentioned earlier my next tuturial will be on different types of
shading  using this 3D object engine as a base...
But after that ??
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.
Keep on coding...
Telemachos  May '97.
