The Mysteries of EX22 (now called ex3d)
Or how to do 3D with Allegro without a 5 year degree course and an expensive book on 3D

  This document is for people who've had a look at ex22 (ex3d) and it's source in the Allegro examples directory (otherwise known as the 'bouncy cubes' demo) and said 'yessss', then 3 days later after looking at the source said 'yessss, but I still don't get it, what does all this actually do?' Read on and most will be revealed...

I recommend downloading the accompanying examples zipfile called mystex22.zip which is very small and contains: mystex22.htm (this file), ex22s.c, ex22b.c and 3dstars.c.

Index:
What you need to know already
(very) Basic 3D
A 'simpler' EX22
The real EX22 step by step
Beyond EX22...


What you need to know already


  Not a lot, you need to know the basics of C, be familiar with setting up the screen etc with Allegro, and C pointers and their types. Very quick pointer explanation, a pointer takes up very little space on it's own, but 'points' to an area of memory where something is stored. A pointer is given a specific type when it is made, for example:
char *mypointer;
is a pointer to some 'char's. Note the '*' is used when declaring a pointer, also a pointer must _not_ be used in your code before it is initialised (loaded with a valid address). Pointers can also point to structures of data (in ex22, there are QUAD, VTX and SHAPE pointers), and if these are arrays of data stored one after the other, the pointer can move through them by incrementing it (mypointer++).



(Back to top)


(very) Basic 3D


  If you intend to do 3D seriously, you do need to spend time studying the subject from either a book or 3D reference, try the zed3d tutorial from the allegro links page.
  You will be pleased to know that you don't need to know much to get started (or understand ex22) as you can use quite a lot of the techniques without knowing how they work. The way I see it, if you can understand 2D, you should be able to grasp 3D, eventually...
  Just as 2D objects have an x and y position (for the sake of this tutorial, I'll assume from the top left of the screen), 3D objects have an extra 'D' (dimension) called z. Also, x, y and z aren't measured in 'pixels' in 3D, they are just 'some unit'. These dimensions (x, y and z) bear no relation to positions on the screen until they are transformed to 2D (x and y) coordinates. So in a 3D system you need some way to translate x, y and z into x and y. If you haven't got it already, get my 3dstars example in the zip at the top of this page. This shows a very simple way of converting a point from 3D to 2D, it assumes that the 'origin' (where x, y and z are all 0) is the middle of the screen. The higher value z is, the further into the screen the points are and the nearer the middle of the screen they are drawn. Very simple example:

2dx = 3dx/3dz;
2dy = 3dy/3dz;

  You should be able to see that the screen x and y (2dx and 2dy) get smaller as z gets bigger (further away). You should also be able to see that it makes sense to have the 2dx and 2dy from the middle of the screen (otherwise points will drift towards the top left corner), so a better example would be:

2dx = (3dx/3dz)+(SCREEN_W/2);
2dy = (3dy/3dz)+(SCREEN_H/2);

  You can do a 3D starfield really easily this way by just decreasing the 3dz value until it gets to 0 (never divide by 0!) then resetting it to a far away distance and decreasing again. The stars will appear to move away from the middle of the screen without you even changing the 3dx and 3dy values! There is the additional bonus of increasing the brightness of the star by just testing 3dz. Obviously there's a lot more to 3D than that, but you should try to understand the 3D starfield before continuing with this tutorial... It's also worth noting that if 3dz is a negative number (less than to 0) it is 'behind' you and it can't be seen.



(Back to top)


A 'simpler' EX22


 Lots of people have remarked that ex22 is too complicated (i don't think it's complicated enough, there are important things missing like a moving camera and proper shading!). I think the problem is you see it's quite a lot of source (for an example) and get bogged down in trying to read it all. This shouldn't be the case, only read the parts you want to learn about and ignore the rest and you should be OK. However, I have stripped down ex22 to remove all the 'complicated' bits :) Here it is, I've rewritten some of it, all it does is take the 3D cube and display it as a wireframe graphic on the screen:

Remember to get the source! It's in the zip at the top of this page, the source includes all the following comments

#include <stdlib.h>
#include <stdio.h>

#include "allegro.h"

#define NUM_VERTICES 8 /* a cube has eight corners */
#define NUM_FACES 6 /* a cube has six faces */
A vertex (plural: vertices) is a point in 3D space (a bit like a star in the starfield example). These are the 'building blocks' of 3D objects.
A face is a collection of 3 or more vertices to make a flat polygon. A cube has six faces (like on a die) each with four corners (and so four vertices per face). Note that a face can share vertices with other faces (there are only eight vertices in this cube!)

OK, what Shawn has done here is decided to define some data types, I've removed the 'SHAPE' one from this example, so we are left with:

typedef struct VTX
{
fixed x, y, z;
} VTX;
This is simply a group of 3 points in 3D space (a vertex).

typedef struct QUAD /* four vertices makes a quad */
{
VTX *vtxlist;
int v1, v2, v3, v4;
} QUAD;
Since a cube's faces have 4 sides, Shawn's defined a QUAD type. The first field is a pointer to a list (or array) of vertices, the next 4 are which vertices in the list that quad is using (this will become clear, trust me :)

VTX points[] = /* a cube, centered on the origin */
{
/* vertices of the cube */
{ -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 },
};
Shawn's made an array of vertices (type VTX), there are 8 (count 'em), one for each corner of the cube. You will see the centre of the cube is 0, 0, 0 (x, y and z) so some points have negative values. Also note that Shawn has put <<16 (shift left 16 bits) instead of using itofix (these are fixed point values, as typedef'd above) which is a bit naughty for an example...:) If you just wanted to display those points on screen, you wouldn't need any more data, but as we're going to show the cubes faces (in wireframe) we need to define some faces...

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 faces list is important, all the faces use the same points array ('points', that's the VTX array shown above the QUAD array), but they use different vertices (obviously). The first face uses point 0 (-32 << 16, -32 << 16, -32 << 16 ), point 3, point 2 and point 1. The order of these points is useful in seeing which way the face is 'facing' (ho!) but that's not used in this simpler example... I'm just going to add here that in this example the actual 'points' member of each QUAD isn't used, the points are translated to output_points and output_points is used instead.

/* somewhere to put translated vertices */
VTX output_points[NUM_VERTICES];
This VTX list will hold the actual screen x and y (pixel) values in fixed format when they've been calculated from the 3D values

/* translate shapes from 3d world space to 2d screen space */
void translate_shapes()
Right, is this where people are confused? In this simpler example the cube is not moved or rotated, but it still has to be translated to 2D coordinates...
I've altered this example to create a textfile called 'points.txt' so you can see how it works by examining that file in a text viewer. You have your 3D in points, and your 2D out points (the z is preserved so you can work out the colour from the distance). The further away a point is, the nearer the centre of the screen it gets. persp_project will take care of adjusting 2dx and 2dy so they are from the top left of the screen... I've subtracted 100 from the z value so the cube isn't 'on top of' the camera (view position, 0, 0, 0).
{
int c;
VTX *inpoint = points;
VTX *outpoint = output_points;

for (c=0;c < NUM_VERTICES;c++) {
persp_project(inpoint->x, inpoint->y, inpoint->z+itofix(100), &outpoint->x, &outpoint->y);
outpoint->z = inpoint->z+itofix(100);
I hope you're up on your pointer indirection! Recap: If you declare a structure, like VTX myvtx; you access it's members by: myvtx.member; If you declare a pointer and point at a structure, like VTX *myvtx = &asinglevtx; You use: myvtx->member;

inpoint++; /* Move 'in' pointer to next 3D vertex */
outpoint++; /* Move 'out' pointer to next 2D vertex */
}
}


/* draw a line (for wireframe display) */
void wire(BITMAP *b, VTX *v1, VTX *v2)
This simply draws a line between two points (the vertices are now 2D so they are really just x,y points on the screen, they could be off the screen (eg. x=10000, y=-23456) but don't worry about that for this example...
The colour is determined by the distance from the screen, you could just replace it with a simple colour value...
{
int col = MID(128, 255 - fixtoi(v1->z+v2->z) / 16, 255);
line(b, fixtoi(v1->x), fixtoi(v1->y), fixtoi(v2->x), fixtoi(v2->y), col);
}


/* draw the shapes calculated by translate_shapes() */
void draw_shapes(BITMAP *b)
I removed the solid drawing methods to leave only wireframe. The VTX pointers (v1 to v4) point to the new 2D coordinates made with the function translate_shapes. The vertices are chosen depending on which are needed by a particular face. This part will probably need most study, it's only doing some quite simple 'looking up' though :)
{
int c;
QUAD *face = faces; /* face now points to first face of cube */
VTX *v1, *v2, *v3, *v4;

for (c=0; c < NUM_FACES; c++) {
/* find the vertices used by the face */
v1 = output_points;
v2 = output_points;
v3 = output_points;
v4 = output_points;

/* Point vertex pointers at correct vertices... */
v1 += face->v1;
v2 += face->v2;
v3 += face->v3;
v4 += face->v4;

/* draw the face */
wire(b, v1, v2); /* First of 4 sides */
wire(b, v2, v3); /* Second */
wire(b, v3, v4); /* Third */
wire(b, v4, v1); /* Fourth, join to close face */

face++; /* Point face at next face of cube */
}
}

int main()
OK, you don't need to see any of the stuff in main, apart from the set_projection_viewport (pretty simple) and the calls to the functions above.
{
blah blah, standard Allegro setup and a few extras...
See EX22S.C for what's in here...
/* set up the viewport for the perspective projection */
set_projection_viewport(0, 0, SCREEN_W, SCREEN_H);
clear(buffer);
translate_shapes();
draw_shapes(buffer);
}



(Back to top)


The real EX22 step by step


  This section will go through the parts of ex22 that are new or different from ex22s, so if you haven't read that section now would be a good time. All the comments from this and the last section are included in the file ex22b.c which is in the zip file linked to at the top of this document.

#define NUM_SHAPES 8 /* number of bouncing cubes */
You can change this to be any number, if you just want 1 cube, change the '8' to a '1'. EX22 isn't very flexible, so it would be better to use it as a learning example then make your own rather than trying to change it into a proper 3D system

typedef struct SHAPE /* store position of a shape */
{
fixed x, y, z; /* x, y, z position */
fixed rx, ry, rz; /* rotations */
fixed dz; /* speed of movement */
fixed drx, dry, drz; /* speed of rotation */
} SHAPE;
This is one of the structures I removed for ex22s, SHAPEs are used to store information about each individual cube, such as it's position in 3D space (x,y,z)
The rotations (rx,ry,rz) are how many degrees it is from each axis (basically, which way the object is pointing). Remember that degrees are from 0 to 255 in the Allegro system, _not_ 0 to 359, you'll find this is true of most 3D systems as it is easier to calculate
The speed of movement and speed of rotation is just how fast the cube is spinning and moving on each axis. Note that Shawn has only allowed movement along the z (into and out of the screen) axis and not included dx and dy members

SHAPE shapes[NUM_SHAPES]; /* a list of shapes */
A simple array of SHAPEs, the number dependent on the NUM_SHAPES define.

QUAD output_faces[NUM_FACES * NUM_SHAPES];
This is new, unlike ex22s, this array is going to store all the sorted faces (more on sorting later...)

enum {
wireframe,
flat,
etc etc etc...
} render_mode = wireframe;
int render_type[] = { blah };
char *mode_desc[] = { blah };
ex22 demonstrates several different rendering modes. It's good to see how it does this as it allows the user to select how things are drawn. I won't go into too much detail, but whenever render_mode is increased it selects the next type of rendering, this can then be passed to a rendering function as render_type[render_mode] and to a describing function (such as textout) as mode_desc[render_mode]

BITMAP *texture;
This bitmap pointer is loaded later, and is used for texture mapping

/* initialise shape positions */
void init_shapes()
For all the shapes (cubes, default is 8). They are initialised with default values. Shawn's using a crazy random number method (again totally disregarding the itofix() function :). You should be able to see each shape has a random 3dx and 3dy value, but always starts 768 units into the screen (3dz). Each shape starts off with no rotation (it is pointing directly into the screen) and a random amount of 'spin' in each axis (drx,dry,drz). The speed dz is also random for each shape so the cubes move in and out at different speeds.
{
int c;

for (c=0; c < NUM_SHAPES; c++) {
shapes[c].x = (random() & 0xFFFFFF) - 0x800000;
shapes[c].y = (random() & 0xFFFFFF) - 0x800000;
shapes[c].z = itofix(768);
shapes[c].rx = 0;
shapes[c].ry = 0;
shapes[c].rz = 0;
shapes[c].dz = (random() & 0xFFFFF) - 0x80000;
shapes[c].drx = (random() & 0x1FFFF) - 0x10000;
shapes[c].dry = (random() & 0x1FFFF) - 0x10000;
shapes[c].drz = (random() & 0x1FFFF) - 0x10000;
}
}

/* update shape positions */
void animate_shapes()
This function is called once every loop and updates (moves and rotates) each shape. First, dz is added to z (the distance to move is added to the z position), a check is made to make sure it doesn't go out of bounds and its direction changed if it does. Then the amount of spin for each axis is added onto the angle of each axis (if an object is only spinning on its x axis it will appear to be 'rolling' toward or away from you, if it's spinning on its y axis it's like looking at a revolving door, on it's z axis is like looking at a spinning top, or a turntable from above). The combination of spinning on all 3 axes gives rise to the sickening display that is ex22:)
{
int c;

for (c=0; c shapes[c].z += shapes[c].dz;

if ((shapes[c].z > itofix(1024)) ||
(shapes[c].z < itofix(192)))
shapes[c].dz = -shapes[c].dz;

shapes[c].rx += shapes[c].drx;
shapes[c].ry += shapes[c].dry;
shapes[c].rz += shapes[c].drz;
}
}

/* translate shapes from 3d world space to 2d screen space */
void translate_shapes()
There was a simple version of this in ex22s, do not attempt to decipher this without understanding ex22s :)
{
int c, d;
MATRIX matrix;
Ooh, a matrix! There is a detailed explanation of what these do in the Allegro documentation, I'm not going to discuss it here as it would just complicate things, it's a need-to-know basis, and we don't need-to-know at this point

VTX *outpoint = output_points;
QUAD *outface = output_faces;

for (c=0; c < NUM_SHAPES; c++) {
/* build a transformation matrix */
get_transformation_matrix(&matrix, itofix(1),
shapes[c].rx, shapes[c].ry, shapes[c].rz,
shapes[c].x, shapes[c].y, shapes[c].z);
To start with, let's just treat matrices and their Allegro functions like magic boxes, we don't need to know how they work, just what to put in them and what they do. The get_tranformation_matrix will just fill the declared matrix with the right data for what we want to do. There is a description of all these functions in the Allegro documentation. This one will set up a matrix to rotate about a point

/* 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);
apply_matrix uses the matrix we setup to change the direction the cube is pointing and store the results in outpoint[?]
persp_project(outpoint[d].x, outpoint[d].y, outpoint[d].z, &outpoint[d].x, &outpoint[d].y);
}

/* output the faces */
for (d=0; d < NUM_FACES; d++) {
outface[d] = faces[d];
outface[d].vtxlist = outpoint;
}

outpoint += NUM_VERTICES;
outface += NUM_FACES;
}
}

/* draw a quad */
void quad(BITMAP *b, VTX *v1, VTX *v2, VTX *v3, VTX *v4, int mode)
Just a different way of drawing a face, like wire, really. There are a few differences, firstly the entire face is drawn in one call, and next it relies on the faces being sorted so the ones furthest away are drawn first (otherwise nasty overlapping occurs)
{
int col;

/* four vertices */
V3D vtx1 = { v1->x, v1->y, v1->z, 0, 0, 0 };
V3D vtx2 = { v2->x, v2->y, v2->z, 31<<16, 0, 0 };
V3D vtx3 = { v3->x, v3->y, v3->z, 31<<16, 31<<16, 0 };
V3D vtx4 = { v4->x, v4->y, v4->z, 0, 31<<16, 0 };
See Allegro docs on 'Polygon rendering', a V3D is a VTX with texture and colour info

/* cull backfaces */
if ((mode != POLYTYPE_ATEX_MASK) && (mode != POLYTYPE_PTEX_MASK) &&
(mode != POLYTYPE_ATEX_MASK_LIT) && (mode != POLYTYPE_PTEX_MASK_LIT) &&
(polygon_z_normal(&vtx1, &vtx2, &vtx3) < 0))
return;
Culling backfaces is the removal of polygons facing away from you. Normally polygons only have 'one side' in 3D, and if you are looking at the other side it is simply not drawn, so this function can simply return without drawing if you are looking at the invisible side of a face

/* set up the vertex color, differently for each rendering mode */
switch (mode) {

case POLYTYPE_FLAT:
etc etc...
Suffice it to say there are a range of different ways to draw your polygons :)
/* draw the quad */
quad3d(b, mode, texture, &vtx1, &vtx2, &vtx3, &vtx4);
quad3d is an Allegro function, see docs, this draws the polygon using the information calculated

/* callback for qsort() */
int quad_cmp(const void *e1, const void *e2)
'qsort' is a routine from stdlib.h which will sort things into order, in this case, faces
{
QUAD *q1 = (QUAD *)e1;
QUAD *q2 = (QUAD *)e2;

fixed d1 = q1->vtxlist[q1->v1].z + q1->vtxlist[q1->v2].z +
q1->vtxlist[q1->v3].z + q1->vtxlist[q1->v4].z;

fixed d2 = q2->vtxlist[q2->v1].z + q2->vtxlist[q2->v2].z +
q2->vtxlist[q2->v3].z + q2->vtxlist[q2->v4].z;

return d2 - d1;
}

/* draw the shapes calculated by translate_shapes() */
void draw_shapes(BITMAP *b)
This isn't much more complicated than ex22s, the faces are sorted with qsort then drawn, you've seen 'wire', 'quad' draws solid faces
{
int c;
QUAD *face = output_faces;
VTX *v1, *v2, *v3, *v4;

/* depth sort */
qsort(output_faces, NUM_FACES * NUM_SHAPES, sizeof(QUAD), quad_cmp);

for (c=0; c < NUM_FACES * NUM_SHAPES; 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 */
if (render_mode == wireframe) {
wire(b, v1, v2);
wire(b, v2, v3);
wire(b, v3, v4);
wire(b, v4, v1);
}
else {
quad(b, v1, v2, v3, v4, render_type[render_mode]);
}

face++;
}
}

The last things in ex22 are colour and light mapping, which you can read about in the Allegro docs, and the 'main' function which just sets things up, creates a bitmap for a texture then loops, allowing you to change the rendering mode

There, that wasn't so difficult, was it? If there is something you don't understand, or are stuck on, please spend some time trying to understand it yourself. I am happy to try and help you, as long as you've had a go at it first. My email is at the end of this document.



(Back to top)


Beyond EX22...


 The most glaring omission from EX22 is that there's no way to change your viewpoint (this is the 'camera'). Fortunately, it's pretty easy to put one in, just look at ex25. You just need to add a get_camera_matrix function and an additional apply_matrix next to the other one for the camera, that's it. You can see this in wire1.c from the tutorial zip, I disabled the movement of the camera as I didn't put any handling of what to do when an object is out of view, but it is still there.

Comments or suggestions on the tutorial? email me: rburrows@bigfoot.com
The Allegro homepage has links to 3D tutorials and a helpful mailing list http://alleg.sourceforge.net
If you got here from my 'C' programming page, you can return to it by clicking here