A simple 3D tutorial
An introduction to the concepts
Vectors
I'm assuming the readers know what a vector is, I'm just reviewing the issues to make sure the terminology doesn't confuse anyone. If you are familiar with the concepts, skip the rest of these introductory sections.

A vector is a group of numbers, having the same amount of items as the space has dimensions. A point on a 2D computer screen has two vector components. I'll denote these by (x,y). The vectors in 3D space have a third component, z. This means a 3D vector will have the form (x,y,z). In Allegro, the origin (0,0,0) is in the middle of the screen, x increases to the right, y downwards, and z into the screen.

There are two categories of vectors. The vectors describing where in the 3D space the point or object is are called position vectors. This is the type of vector you are concerned with when you determine the location of vertices, move objects around etc. The other type is direction vector. Imagine you turn your head to see who's behind you. You don't actually move, i.e. your position vector is the same, but you turn, your direction vector changes. The direction vector tells the coordinates of a point in your line of sight relative to yourself. Direction vectors are usually used to determine the if a polygon's back face is towards the viewer. If this is the case, it won't be drawn. The actual difference between position and direction vectors is that the other one is relative to the origin and the other to the object whose direction vector you are calculating.

Dot and cross product
Just as normal numbers have associated operations, vectors have too. Addition means adding the corresponding components, and is a very simple way of determining where the vertices of an object are relative to the origin if you know the objects coordinates. You simply add the position vector of the object relative to the origin and the vector of the vertex relative to the object, and you have the position vector of the vertex.

Dot product is a weird number whose actual value doesn't really tell you that much. It can be used to determine if two vectors are parallel, which is the case if the dot product is zero. It can be used for a fast determination of the length of the vector as well as projections, but you won't usually be needing it.

Cross product is more interesting. If you have two vectors and you find their cross product, it is perpendicular to both of them. To determine the direction of the vector (there are two possibilities), use the so called right-hand rule. If you have cross(a,b), where a and b are the vectors in the picture on the right, the resultant vector's direction is the direction your thumb points if you point your right hand's other fingers in the direction of the arrow. Now this can be used to determine the direction polygons face. Let's call the origin in the picture c. If you have a triangular polygon with corners a, b and c, you can get the vectors you need from (c - a) and (c - b). Then calculate the cross product. If the z component is negative, the polygon is facing away form you and you don't have to draw it. More on this later on when this will actually be used.

Translating vectors using matrices
There's quite a bit on this in the Allegro docs, in the math section. I'll elaborate on this section if I get feedback telling me to.

The example program
The example program which I'm about to explain to you in detail, draws a cube on the screen and spins it around. I'll be using flat shading for the cube. Notice that I will not necessarily be explaining every line and some of the things might be handled in a different order than the order which you see in the .c file. This is to clarify things...

The data structures used to hold the coordinate data
There are several structures used. For the cube, for its six faces and the eight vertices.

typedef struct VTX               /* vertex data */
{
    fixed x, y, z;
} VTX;
This struct is used to represent a vector (x,y,z). This is used internally only, Allegro's functions use vectors of type V3D, so make sure you notice the difference.

typedef struct QUAD              /* four vertices makes a quad */
{
    VTX *vtxlist;
    int v1, v2, v3, v4;          /* these vars define the points in vtxlist
                                     used for this QUAD */
} QUAD;
This is used to determine the six faces of the cube, never mind the ints at this point. Come back here when the points variable is initialised later.

typedef struct SHAPE             /* store position of a shape */
{
    fixed x, y, z;               /* x, y, z position */
    fixed rx, ry, rz;            /* rotations */
    fixed drx, dry, drz;         /* speed of rotation */
} SHAPE;
The information on the actual shape, the cube. The shape is located at (x,y,z) and is rotated by the amount indicated by rx, ry, and rz. The vars dr? indicate the rotation speed of the object. These values are added to r? every cycle.

VTX points[] =                   /* a cube, centered on the origin */
{
   /* vertices of the cube, of type fixed */
   { -32 << 16, -32 << 16, -32 << 16 },
   { -32 << 16,  32 << 16, -32 << 16 },
   {  32 << 16,  32 << 16, -32 << 16 },
   {  32 << 16, -32 << 16, -32 << 16 },
   { -32 << 16, -32 << 16,  32 << 16 },
   { -32 << 16,  32 << 16,  32 << 16 },
   {  32 << 16,  32 << 16,  32 << 16 },
   {  32 << 16, -32 << 16,  32 << 16 },
};
These are the points of the eight vertices of a cube. They are all shifted by 16 since Allegro's type fixed determines the most significant word as the integer part and the least significat one as decimals. Now go back to the QUAD struct. The ints are indexes into this table. The following table is used with this one to determine which vertices go with each face.

QUAD faces[] =                   /* group the vertices into polygons */
{
   { points, 0, 3, 2, 1 },
   { points, 4, 5, 6, 7 },
   { points, 0, 1, 5, 4 },
   { points, 2, 3, 7, 6 },
   { points, 0, 4, 7, 3 },
   { points, 1, 2, 6, 5 }
};
This array determines the vertices which each one of the faces consists of. Let's take the first face as an example. The indexes into the points array are 0, 3, 2, 1. The corresponding coordinates are (-32,-32,-32), (32,-32,-32), (32,32,-32) and (-32, 32, -32). This is the one closest to the viewer. You can tell because all the z components are -32. Remember, z grows into the screen, so negative is closer to the viewer.

SHAPE shape;
Last but not least, initialize the instance of the cube.

Initialization
The variables need to have values for the program to work. Some were given values as they were initialized, but the cube needs its parameters set.

void init_shape()
{
    shape.x = 0;
    shape.y = 0;
    shape.z = itofix(256);
    shape.rx = 0;
    shape.ry = 0;
    shape.rz = 0;

    shape.drx = (random() & 0x1FFFF) - 0x10000;
    shape.dry = (random() & 0x1FFFF) - 0x10000;
    shape.drz = (random() & 0x1FFFF) - 0x10000;
}
The cube spins in the middle of the screen 2D-wise, and I found 256 to be a good z value. It will start from the default position, so rx, ry and rz are all zero. Experiment with these and you'll get a feeling of how the stuff works. The rotation speed is determined randomly for each component.

Also, there's some initialization stuff in main(), mainly Allegro initialization etc., but there's also the palette gradient. It is used to determine the colors used for the faces based on their orientation. The color range is a bit weird, but it's a kludge that won't get in the way of understanding how the stuff works.

There's also an important line:

    set_projection_viewport(0, 0, SCREEN_W, SCREEN_H);
This tells Allegro that it should pass values between these in response to a persp_project() call. Essentially, this sets the area on the screen where you want your 3D stuff to be on the screen.

The calculations
The actual loop does three things:

Updates the variables to new values 
Translates the 3D coordinates to 2D screen coordinates 
Draws the polygons on the screen 
The first phase is taken care of by the following function:

void animate_shape()
{
    shape.rx += shape.drx;
    shape.ry += shape.dry;
    shape.rz += shape.drz;
}
This simply increases (or decreases) the various angle components of the cube. These are then translated into 2D coordinates. These 2D coordinates are stored into the following arrays:

VTX output_points[NUM_VERTICES];
QUAD output_faces[NUM_FACES];
The first one will contain the x and y values of the projected vertices, the z value will be used as a temporary variable as well. The latter will be similar to the faces array, but will contain indexes into the output_points list instead of points, which faces uses.

void translate_shape()
{
    int d;
    MATRIX matrix;
    VTX *outpoint = output_points;
    QUAD *outface = output_faces;

    /* build a transformation matrix */
    get_transformation_matrix(&matrix, itofix(1),
                              shape.rx, shape.ry, shape.rz,
                              shape.x, shape.y, shape.z);
The get_transformation_matrix function makes a transformation matrix which rotates a vector by the coordinates specified by the 3rd, 4th and 5th parameters and displaces it by the 6th, 7th and 8th parameters (which are 0, 0 and 256 always in our example). The second parameter could be used to scale the whole cube. Note that the complete translation is done on every pass. This operation does not use the vectors resulting from the last pass, they are generated from the coodinates of the original cube. (The struct points is never altered)

    /* output the vertices */
    for (d=0; d<NUM_VERTICES; d++) {
        apply_matrix(&matrix, points[d].x, points[d].y, points[d].z, &outpoint[d].x, &outpoint[d].y, &outpoint[d].z);
        persp_project(outpoint[d].x, outpoint[d].y, outpoint[d].z, &outpoint[d].x, &outpoint[d].y);
    }
Here, for each vertex, the transformation matrix is first applied to the point to rotate it into the specified angle, and then persp_project is called. It is the heart of the whole function. It takes the 3D coordinates passed to it and, on the data given earlier using set_projection_viewport, it determines where on the screen the specified point should be. The coordinates are saved in outpoint[d].

    /* output the faces */
    for (d=0; d<NUM_FACES; d++) {
        outface[d] = faces[d];
        outface[d].vtxlist = outpoint;
    }
}
This part first copies the faces array into output_faces to keep track of the order of the vertices which belong to each one of the faces, and then substitutes the rotated and projected 2D coordinates into the place of the unrotated 3D coords.

Drawing the cube
After (almost) all the math is done, the polygons are drawn. This is accomplished by the function draw_shape() together with a helper function quad().

void draw_shape(BITMAP *b)
{
    int c;
    QUAD *face = output_faces;
    VTX *v1, *v2, *v3, *v4;
    
    for (c=0; c < NUM_FACES; c++) {
        /* find the vertices used by the face */
        v1 = face->vtxlist + face->v1;
        v2 = face->vtxlist + face->v2;
        v3 = face->vtxlist + face->v3;
        v4 = face->vtxlist + face->v4;
        
        /* draw the face */
        quad(b, v1, v2, v3, v4);
        
        face++;
    }
}
This function draws the cube on the BITMAP b passed as a parameter. You can see how the variables v1, v2, v3 and v4 are given values from the vtxlist in output_faces. This list is, as you might remember from translate_shape(), the array output_points. Now, when calling quad(), all the 2D projected vertices' locations are known. Do remember that the 3D z-values are still stored in the array. Once the polygon is drawn, the next face is handled etc.

The actual drawing is done by quad():

void quad(BITMAP *b, VTX *v1, VTX *v2, VTX *v3, VTX *v4)
{
    int col;
    fixed x, y, z;
    
    /* four vertices */
    V3D vtx1 = { v1->x, v1->y, v1->z, 0, 0, 0 };
    V3D vtx2 = { v2->x, v2->y, v2->z, 0, 0, 0 };
    V3D vtx3 = { v3->x, v3->y, v3->z, 0, 0, 0 };
    V3D vtx4 = { v4->x, v4->y, v4->z, 0, 0, 0 };
The internal format VTX has to be converted to Allegro's own V3D points. The 4th and 5th parameters are texture mapping coordinates, but we're using flat shading, so it doesn't matter what you have there. The last one is color, but it will be set later.

    /* use the cross-product to cull backfaces */
    cross_product(v2->x-v1->x, v2->y-v1->y, 0, v3->x-v2->x, v3->y-v2->y, 0, &x, &y, &z);
    if (z < 0)
      return;
Imagine all the six faces of the cube, including the ones you can't see (you can only see three at any time). Now if you go ahead and draw them in a random order, imagine what happens if you've already drawn the tree visible ones, and you still have one face to draw... The result won't be too pleasant (If you didn't get this, comment the above, compile and run). That's why we take the cross product to find the vector perpendicular to the face we are about to draw. If the vector is pointing away from us (z > 0), we don't have to draw it at all!

    /* set up the vertex color */
    col = MID(128, 255 - fixtoi(v1->z+v2->z) / 16, 255);
    vtx1.c = col;
OK, as Shawn said, every silver lining has a cloud, so does this tutorial. Here it is. The color can be deducted from the z-value of the cross product. I made a shameless kludge and experimentally determined the range of colors the above formula for col takes and set up a palette gradient for that interval. The interval is 220-229. The color used by quad3d is the color value of the first vertex, so you'll only have to set that one. I wanted to make the color gradient steep so that you could actually see the colors change as the cube spins. It's tends to cause some pretty jumpy color changes though... Lesson: use proper color gradients.

    /* draw the quad */
    quad3d(b, POLYTYPE_FLAT, NULL, &vtx1, &vtx2, &vtx3, &vtx4);
}
The rest of the code is the main(), and I won't go into explaining it. It's pretty straightforward, so everyone figure it out.

What next
Make sure you understand the stuff in this text. Please mail me if you find errors or come up with questions. Especially if you would like to see more on matrix math or something I didn't even mention. Then try the following things on your own:

Repair the color kludge by setting a broader palette range. A scale from color index 128 to 255 might be nice. 
Make the cube move as well as spin. Give values to shape.r? and modify the shape's coordinates in animate_shape(). 
Change the coordinates in points in animate_shape() as well. Ever seen the morphing objects in some cool demos? 
Check out Shawn's ex22.c. It'll seem a lot simpler now... 
Experiment with get_camera_matrix(). You'll have to apply_matrix() the camera matrix before persp_project(). 


--------------------------------------------------------------------------------


This page by Tero Parvinen, Tero.Parvinen@hut.fi