Now it's finally time to enter the dark, mysterious world of 3d graphic programming. There are enormous amounts of information available on this subject. Through the years I've gone through many files and some books on 3d demo and game programming and in this part I'm going to present the basic math and algorithms that 3d computer graphics are built upon.
3d graphics is simply an extension of 2d graphics. Because of that I'll begin with:
In 2d, a point is represented by a X and a Y -coordinate, written (X,Y). Origo is the point where both the X and Y coordinate is 0, (0,0). For simplicity, imagine origo beeing the middle of the screen.
[picture of screen]
Physical origo is, as you know, at the upper left corner of the screen. To move the origo to the middle of the screen, just add half the height of the screen to the y-coordinates and half the width of the screen to the x-coordinates of all points you wish to draw.
This effect, or transformation, is called translation. That means moving.
where (bx,by) is the coordinates of the point before the movement. Addx is the distance you wish to move the point in the x-direction and addy is the distance to move the point in the y-direction. (tx,ty) is the coordinates of the moved (translated) point.
To ROTATE a point some angle around any arbitrary point requires pretty messy math and we don't have time for that. But to rotate a point around ORIGO is much simpler.
where (bx,by) are the base coordinates (coordinates before rotation) and (rx,ry) are the rotated coordinates. The mathematical functions sin and cos wants the angle in radians, but we are used to count angles in degrees. One revolution in a circle is 360 degrees and it is 2*PI radians. This information tells us that:
So in the rotation formula above, the angle variable should be (DEGREES/360)*2*PI. If you know ANY math you know that PI is 3.14... ;-) This is like made for precalculating. Put it in the arrays sinus & cosinus like this:
for(i=0;i<360;i++)
{
sinus[i] = sin(2*PI*i/360);
cosinus[i] = cos(2*PI*i/360);
}
This is much faster than the sin(2*PI*angle/360) calculations.
Instead of using a 360 degree circle we could use a 256 degree circle. Because a byte can have 256 different values, we could use a byte to hold the angle. Just change the precalculations to:
for(i=0;i<256;i++)
{
sinus[i] = sin(2*PI*i/256);
cosinus[i] = cos(2*PI*i/256);
}
This way a quarter of a circle (right angle) becomes 64 "degrees". A half revolution is 128 "degrees" and an entire revolution is 256 "degrees". Familiar numbers to a computer freak 8^}.
The old problem with rotating around an arbitrary point isn't really that hard to solve. Just combine two transformations. First translate all points so that the point you want to be in the center of rotation ends up in origo. Then perform a rotation around origo and finally translate all points back the same distance as the first translation (just change the sign of the movement). Now the points have been rotated around the arbitrary point.
(bx,by,bz) is the point before movement and (tx,ty,tz) is the moved point.
ROTATION IN 3D is the very heart of 3d demo and game programming. It's really not just one 3d-rotation it's more like three 2d-rotations. First around the X-axis, then around the Y-axis and at last the Z-axis.
Angle_x, angle_y, angle_z are the angles to rotate the point around respective axis. bx,by,bz are the coordinates of the point before rotation (base coordinates). rx,ry,rz are the coordinates rotated once and rrx,rry,rrz are the coordinates rotated twice. When the rotation is done, all coordinates have been rotated twice. You may notice that rotation around the Z-axis is the same as rotating in 2d, which is natural because the z-axis points right into the screen.
Before actually beginning to draw the points to the screen, there is one little problem left. The screen is 2-dimensional and our virtual world is 3-dimensional. It has been proven there are problems that no computer ever will be able to solve. Fortunatly this is not one of them. . . To project a 3-dimesional world onto a 2-dimensional screen we use perspective projection. In reality things further away looks smaller. That could mean that the z-coordinate should be in the denominator, and that is also the case.
where (X,Y,Z) are the 3d coordinates and (SX,SY) are the 2d screen coordinates. DIST is the distance from the eye to the screen. For simplicity and speed of calculation I chose DIST = 256.
[picture of eye-screen-object]
With the formula above the object will appear on the screen where the straight line between the eye and the object intersects with the screen.
Now we know enough to put a 3d demo together, but it would be slow. To make the demo faster we have to use some optimizations. The first optimization would be to put the sin & cos values in precalculated arrays as I described in the 2d case. The sin & cos calculations would still be slow because they are real numbers. It is possible to use integers instead. That's called fixed point math.
Fixed point math is a way to represent floating point numbers with integers. You simply use some of the bits for the whole part of the number and some bits for the fractional part.
Ex
00001001 11000000 /------/ /-------/ whole, fractional partIn this example there are 8 bits for the whole part and 8 bits for the fractional part. That means that the whole part is whole part is 00001001 = 9 and the fractional part is 11000000 = 1/2 + 1/4 = 3/4 = 0.75 This gives that the fixed point number is 9.75.
The values of the bits in a 16 bit fixed point number with 8 bits fractional part
b15 b14 b13 b12 b11 b10 bit9 bit8 bit7 bit6 bit5 bit4 bit3 bit2 bit1 bit0 128 64 32 16 8 4 2 1 1/2 1/4 1/8 1/16 1/32 1/64 1/128 1/256
The largest number representable with 8 bits whole part is 255 (+ 1 if all the fractional bits are set too) and the smallest number with 8 bits fractional part is 1/256 = 0.0039. When using fixed point math you have to think about how big and how small numbers they are going to represent. In 386 assembler there are 32-bits registers but if 16 bits are enough, use only 16 bits because it's faster.
Ex. Let's use 4 bits fractional part, 12 bits whole part. We want to assign the fixed point integer fp1 the value 3.5.
fp1 = 3.5 * 2^4 = 3.5 * 16 = 56 = 000000000011 1000 real value: 3 + 1/2 = 3.5And assign fp2 the value 2.5.
fp2 = 2.5 * 16 = 40 = 000000000010 1000 real value: 2 + 1/2 = 2.5 Now let fp3 = fp1 + fp2 = 56 + 40 = 96 = 000000000110 0000 real value: 6 + 0 = 6.fp3 is now 96. To get the actual value shift fp3 right 4 bits.
Ex: fp3 = (fp1 * fp2) >> fracbits; /* fp3 = fp1*fp2 */ result = fp3 >> fracbits;
Ex: fp3 = (fp1 << fracbits)/fp2; /* fp3 = fp1/fp2 */ result = fp3 >> fracbits;
In assembler, when multiplying two 16 bit integers, the result is in dx:ax = 32 bits. That means that you can multiply two big 16-bit numbers and still not lose any bits, very good. It means that we can represent the sin & cos tables as 16-bit fixed point integers. As you know, sin & cos values vary between -1 and 1 so it's enough to use 2 bits for the whole part and we can use 14 bits for the fractional part, heavy...
I calculated the fixed point sin & cos tables with 14 bits shift like this:
for(i=0;i<256;i++)
{
sinus[i] = sin(2*PI*i/256)*16384;
cosinus[i] = cos(2*PI*i/256)*16384;
}
16384 is 2^14 and PI is 3.1415927.
Now we can put a 3d demo together. I've done a little demo using a rotating cube with 8 sprites at the corners of the cube. I have hidden all the fixed point math and rotation stuff in the rot.asm file. It only contains one callable funtion, rotatepoints. Rotatepoints takes 4 parameters: angle_x, angle_y, angle_z and NUM_OF POINTS. The three first are the angles to rotate the points around the respective axis. The last parameter NO_OF_POINTS tells how many points that shall be rotated. Where are the points that shall be rotated? You may ask. Well, they are in the global arrays: bx,by,bz. It's really bad programming style to use global arrays but it's faster and simpler and that's what counts. bx,by,bz contains the base coordinates, they never change. Rotatepoints uses 8 more global arrays: rx,ry,rz, sx,sy and addx,addy,addz. rx,ry,rz is where the rotated coordinates are stored and sx,sy are where the perspective projected screen coordinates are stored. Addx, addy and addz is the distance that the rotated coordinates will be translated (moved) away from origo in the respective direction. If addx, addy and addz are 0 the points will be centered around the middle of the screen.
All you have to do is put the base coordinates in bx,by,bz and call rotatepoints. Then the rotated coordinates will automatically be put in rx,ry,rz and the screen coordinates will be put in sx,sy. Why are rx,ry,rz necessary? Well, to make it look right on the screen you have to draw the sprites that are furthest away first, and the closest sprites last (painters algorithm). The rz coordinates are necessary to find out how far away into the screen the points are. Actually we're not ready yet. To be able to draw the sprites in right order we have to sort sx and sy with respect to rz.
Ex:
before: rz = 3,1,2 sx = 1,2,3 sy = 4,5,6sort rz and let sx & sy change along with rz
after: rz = 1,2,3 sx = 2,3,1 sy = 5,6,4
There are many sorting algorithms, the simplest is the bubblesort algorithm. I've chosen a faster sorting algorithm called quicksort. The disadvantage with quicksort is that it is recursive. Recursive means that it calls itself. My quicksort assumes that rz, sx & sy are global. Quicksort always have at least two parameters: lower boundary and upper boundary. The boundaries is the interval in the array that will be sorted. If lower boundary, lb, is 0 and ub is 5. Then the 6 first numbers in the array will be sorted. Quicksort takes the first number in the interval that will be sorted inserts it at it's "right" place. Then quicksort calls it self twice. Once with the interval below the "sorted" number and once with the interval above the "sorted" number. Quicksort continues this until the interval is only one number big (ub -lb) <= 1; Then it's done and all numbers are sorted. This may sound strange but it's one of the most effective sorting algorithms. My version of quicksort is written in assembler, to understand it it's easier to look at the c-code. in C it would look something like this:
void qsort3d(int lb,int ub)
{
int a,down,up,hold,indexA;
indexA=lb; /* set the index of a to lower boundary */
a=rz[indexA]; /* a = the first number in the interval to be sorted */
down=lb; /* let down point at the beginning of the interval */
up=ub; /* let up point at the end of the interval */
while(down<up;)
{
while((rz[down]<=a)&&(down<=ub)) down++; /* inc down until rz[down]>a; */
while((rz[up]>a;)&&(up>=lb)) up--; /* dec up until rz[up]<=a */
if(up>down;)
{
hold=rz[down]; /* if up > down xchange rz[down] & rz[up] */
rz[down]=rz[up];
rz[up]=hold;
hold=sx[down]; /* xchange sx[down] & sx[up] */
sx[down]=sx[up];
sx[up]=hold;
hold=sy[down]; /* and xchange sy[down] & sy[up] the same way */
sy[down]=sy[up];
sy[up]=hold;
}
}
hold=rz[indexA]; /* xchange rz[indexA] and rz[up] */
rz[indexA]=rz[up];
rz[up]=hold;
hold=sx[indexA]; /* exchange sx and sy */
sx[indexA]=sx[up];
sx[up]=hold;
hold=sy[indexA]; /* the same way */
sy[indexA]=sy[up];
sy[up]=hold;
indexA=up;
/* recursive calls to qsort3d with smaller intervals */
if(indexA-1-lb>0;) qsort3d(lb,indexA-1);/* if smaller intervals > 1 element*/
if(ub-indexA-1>0;) qsort3d(indexA+1,ub);/* sort the smaller intervals too */
}
Now we must be ready to make a 3d demo or?
YES it's about time.
All the ingredients for a pretty fast 3d-demo are here.
Now it's up to you too cook'em.
There are of course more optimizations to do but I've done the most obvious
optimizations for you.
What you can begin with is to make some nice data structures. These global data structures that I've made now really sux and must be improved when we move on to drawing filled polygons with shading and eliminate hidden planes.
Rotatepoints and qsort3d uses these global arrays:
Iv'e split the demo into these files:
demo4 and d4morf are two different demos but they use the same functions (and they have the same global arrays)
Next time we'll continue this journey into 3d space with drawing solid polygons and hidden surface elimination.
download abedemo4.zip
1996-02-11 Abe of Space s-mail: Albert Veli Spisringsg. 9 724 76 Väster;ås; SWEDENmail:dat94avi@bilbo.mdh.se.