|====================================| | | | 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...) : - Z-shading - Flat shading according to moving lightsource(s) - Gouraud Shading according to moving lightsource(s) - Texturemapping - Environment-mapping - Phong Shading (a fake 'cause ) So when you are done with these two tuturials you should be able to to 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 VGA-BITMAPS ? CAN YOU DO GFX IN ALL RESOLUTIONS - 320x200x256 AND VARIOUS SVGA-MODES ? DO YOU WANT TO SEE YOUR WORK IN AMAZING PRODUCTIONS ? CAN YOU DO GAME-GFX 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 FIDO-net : 2:235/350.22 2) E-mail 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 demo-related FTP-sites - 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 : \ | -----------------------------> X-axis | \ | \ | \ | \ | \ | \> | Z-axis (into the screen :) ) | V Y-axis 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/(Zeye-Z))); Y0 := Yofs + Round(Y*(Zeye/(Zeye-Z))); 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 (z-Zoff)) shl 8; Y0 := Yofs + (y div (z-Zoff)) shl 8; This will also work allthough not entirely correct. LETS TALK ABOUT DATA-STRUCTURES -------------------------------- 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 Z-axis : (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 X-axis : Xrotated = X Yrotated = Cos (A)*Y - Sin (A)*Z Zrotated = Sin (A)*Y + Cos (A)*Z rotation around Y-axis : 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 X-coords 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 y-lines 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 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 Z-value 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 face-numbers belonging to a centervalue. To do the actual sorting we'll use a simple bubble-sort. 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 bubble-sort - not to fast but what the heck :) } {Faces with the HIGHEST Z-val 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.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) 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 sample program. 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.