
Allegro contains some 3d helper functions for manipulating vectors,
constructing and using transformation matrices, and doing perspective
projections from 3d space onto the screen. It is not, and never will be, a
fully fledged 3d library (my goal is to supply generic support routines,
not shrinkwrapped graphics code :) but these functions may be useful for
developing your own 3d code.
Allegro uses a righthanded coordinate system, i.e. if you point the thumb
of your right hand along the x axis, and the index finger along the y axis,
your middle finger points in the direction of the z axis. This also means,
for any rotation, if you point the thumb of your right hand along the axis
of rotation, then the fingers curl in the positive direction of rotation.
All the 3d math functions are available in two versions: one which uses
fixed point arithmetic, and another which uses floating point. The syntax
for these is identical, but the floating point functions and structures are
postfixed with '_f', eg. the fixed point function cross_product() has a
floating point equivalent cross_product_f(). If you are programming in C++,
Allegro also overloads these functions for use with the 'fix' class.
3d transformations are accomplished by the use of a modelling matrix. This
is a 4x4 array of numbers that can be multiplied with a 3d point to produce
a different 3d point. By putting the right values into the matrix, it can be
made to do various operations like translation, rotation, and scaling. The
clever bit is that you can multiply two matrices together to produce a third
matrix, and this will have the same effect on points as applying the
original two matrices one after the other. For example, if you have one
matrix that rotates a point and another that shifts it sideways, you can
combine them to produce a matrix that will do the rotation and the shift in
a single step. You can build up extremely complex transformations in this
way, while only ever having to multiply each point by a single matrix.
Allegro actually cheats in the way it implements the matrix structure.
Rotation and scaling of a 3d point can be done with a simple 3x3 matrix, but
in order to translate it and project it onto the screen, the matrix must be
extended to 4x4, and the point extended into 4d space by the addition of an
extra coordinate, w=1. This is a bad thing in terms of efficiency, but
fortunately an optimisation is possible. Given the 4x4 matrix:
( a, b, c, d )
( e, f, g, h )
( i, j, k, l )
( m, n, o, p )
a pattern can be observed in which parts of it do what. The top left 3x3
grid implements rotation and scaling. The three values in the top right
column (d, h, and l) implement translation, and as long as the matrix is
only used for affine transformations, m, n and o will always be zero and p
will always be 1. If you don't know what affine means, read Foley & Van
Damme: basically it covers scaling, translation, and rotation, but not
projection. Since Allegro uses a separate function for projection, the
matrix functions only need to support affine transformations, which means
that there is no need to store the bottom row of the matrix. Allegro
implicitly assumes that it contains (0,0,0,1), and optimises the matrix
manipulation functions accordingly.
Matrices are stored in the structures:
typedef struct MATRIX  fixed point matrix structure
{
fixed v[3][3];  3x3 scaling and rotation component
fixed t[3];  x/y/z translation component
} MATRIX;
typedef struct MATRIX_f  floating point matrix structure
{
float v[3][3];  3x3 scaling and rotation component
float t[3];  x/y/z translation component
} MATRIX_f
extern MATRIX identity_matrix;
extern MATRIX_f identity_matrix_f;
Global variables containing the 'do nothing' identity matrix. Multiplying
by the identity matrix has no effect.
void get_translation_matrix(MATRIX *m, fixed x, fixed y, fixed z);
void get_translation_matrix_f(MATRIX_f *m, float x, float y, float z);
Constructs a translation matrix, storing it in m. When applied to the
point (px, py, pz), this matrix will produce the point (px+x, py+y,
pz+z). In other words, it moves things sideways.
void get_scaling_matrix(MATRIX *m, fixed x, fixed y, fixed z);
void get_scaling_matrix_f(MATRIX_f *m, float x, float y, float z);
Constructs a scaling matrix, storing it in m. When applied to the point
(px, py, pz), this matrix will produce the point (px*x, py*y, pz*z). In
other words, it stretches or shrinks things.
void get_x_rotate_matrix(MATRIX *m, fixed r);
void get_x_rotate_matrix_f(MATRIX_f *m, float r);
Construct X axis rotation matrices, storing them in m. When applied to a
point, these matrices will rotate it about the X axis by the specified
angle (given in binary, 256 degrees to a circle format).
void get_y_rotate_matrix(MATRIX *m, fixed r);
void get_y_rotate_matrix_f(MATRIX_f *m, float r);
Construct Y axis rotation matrices, storing them in m. When applied to a
point, these matrices will rotate it about the Y axis by the specified
angle (given in binary, 256 degrees to a circle format).
void get_z_rotate_matrix(MATRIX *m, fixed r);
void get_z_rotate_matrix_f(MATRIX_f *m, float r);
Construct Z axis rotation matrices, storing them in m. When applied to a
point, these matrices will rotate it about the Z axis by the specified
angle (given in binary, 256 degrees to a circle format).
void get_rotation_matrix(MATRIX *m, fixed x, fixed y, fixed z);
void get_rotation_matrix_f(MATRIX_f *m, float x, float y, float z);
Constructs a transformation matrix which will rotate points around all
three axis by the specified amounts (given in binary, 256 degrees to a
circle format).
void get_align_matrix(MATRIX *m, fixed xfront, yfront, zfront,
fixed xup, fixed yup, fixed zup);
Rotates a matrix so that it is aligned along the specified coordinate
vectors (they need not be normalized or perpendicular, but the up and
front must not be equal). A front vector of 1,0,0 and up vector of 0,1,0
will return the identity matrix.
void get_align_matrix_f(MATRIX *m, float xfront, yfront, zfront,
float xup, yup, zup);
Floating point version of get_align_matrix().
void get_vector_rotation_matrix(MATRIX *m, fixed x, y, z, fixed a);
void get_vector_rotation_matrix_f(MATRIX_f *m, float x, y, z, float a);
Constructs a transformation matrix which will rotate points around the
specified x,y,z vector by the specified angle (given in binary, 256
degrees to a circle format).
void get_transformation_matrix(MATRIX *m, fixed scale,
fixed xrot, yrot, zrot, x, y, z);
Constructs a transformation matrix which will rotate points around all
three axis by the specified amounts (given in binary, 256 degrees to a
circle format), scale the result by the specified amount (pass 1 for no
change of scale), and then translate to the requested x, y, z position.
void get_transformation_matrix_f(MATRIX_f *m, float scale,
float xrot, yrot, zrot, x, y, z);
Floating point version of get_transformation_matrix().
void get_camera_matrix(MATRIX *m, fixed x, y, z, xfront, yfront, zfront,
fixed xup, yup, zup, fov, aspect);
Constructs a camera matrix for translating worldspace objects into a
normalised view space, ready for the perspective projection. The x, y,
and z parameters specify the camera position, xfront, yfront, and zfront
are the 'in front' vector specifying which way the camera is facing (this
can be any length: normalisation is not required), and xup, yup, and zup
are the 'up' direction vector. The fov parameter specifies the field of
view (ie. width of the camera focus) in binary, 256 degrees to the circle
format. For typical projections, a field of view in the region 3248 will
work well. Finally, the aspect ratio is used to scale the Y dimensions of
the image relative to the X axis, so you can use it to adjust the
proportions of the output image (set it to 1 for no scaling).
void get_camera_matrix_f(MATRIX_f *m, float x, y, z, xfront, yfront, zfront,
float xup, yup, zup, fov, aspect);
Floating point version of get_camera_matrix().
void qtranslate_matrix(MATRIX *m, fixed x, fixed y, fixed z);
void qtranslate_matrix_f(MATRIX_f *m, float x, float y, float z);
Optimised routine for translating an already generated matrix: this
simply adds in the translation offset, so there is no need to build two
temporary matrices and then multiply them together.
void qscale_matrix(MATRIX *m, fixed scale);
void qscale_matrix_f(MATRIX_f *m, float scale);
Optimised routine for scaling an already generated matrix: this simply
adds in the scale factor, so there is no need to build two temporary
matrices and then multiply them together.
void matrix_mul(const MATRIX *m1, *m2, MATRIX *out);
void matrix_mul_f(const MATRIX_f *m1, *m2, MATRIX_f *out);
Multiplies two matrices, storing the result in out (this may be a
duplicate of one of the input matrices, but it is faster when the inputs
and output are all different). The resulting matrix will have the same
effect as the combination of m1 and m2, ie. when applied to a point p, (p
* out) = ((p * m1) * m2). Any number of transformations can be
concatenated in this way. Note that matrix multiplication is not
commutative, ie. matrix_mul(m1, m2) != matrix_mul(m2, m1).
fixed vector_length(fixed x, fixed y, fixed z);
float vector_length_f(float x, float y, float z);
Calculates the length of the vector (x, y, z), using that good 'ole
Pythagoras theorem.
void normalize_vector(fixed *x, fixed *y, fixed *z);
void normalize_vector_f(float *x, float *y, float *z);
Converts the vector (*x, *y, *z) to a unit vector. This points in the
same direction as the original vector, but has a length of one.
fixed dot_product(fixed x1, y1, z1, x2, y2, z2);
float dot_product_f(float x1, y1, z1, x2, y2, z2);
Calculates the dot product (x1, y1, z1) . (x2, y2, z2), returning the
result.
void cross_product(fixed x1, y1, z1, x2, y2, z2, *xout, *yout, *zout);
void cross_product_f(float x1, y1, z1, x2, y2, z2, *xout, *yout, *zout);
Calculates the cross product (x1, y1, z1) x (x2, y2, z2), storing the
result in (*xout, *yout, *zout). The cross product is perpendicular to
both of the input vectors, so it can be used to generate polygon normals.
fixed polygon_z_normal(const V3D *v1, *v2, *v3);
float polygon_z_normal_f(const V3D_f *v1, *v2, *v3);
Finds the Z component of the normal vector to the specified three
vertices (which must be part of a convex polygon). This is used mainly in
backface culling. The backfaces of closed polyhedra are never visible
to the viewer, therefore they never need to be drawn. This can cull on
average half the polygons from a scene. If the normal is negative the
polygon can safely be culled. If it is zero, the polygon is perpendicular
to the screen.
void apply_matrix(const MATRIX *m, fixed x, y, z, *xout, *yout, *zout);
void apply_matrix_f(const MATRIX_f *m, float x, y, z, *xout, *yout, *zout);
Multiplies the point (x, y, z) by the transformation matrix m, storing
the result in (*xout, *yout, *zout).
void set_projection_viewport(int x, int y, int w, int h);
Sets the viewport used to scale the output of the persp_project()
function. Pass the dimensions of the screen area you want to draw onto,
which will typically be 0, 0, SCREEN_W, and SCREEN_H.
void persp_project(fixed x, y, z, *xout, *yout);
void persp_project_f(float x, y, z, *xout, *yout);
Projects the 3d point (x, y, z) into 2d screen space, storing the result
in (*xout, *yout) and using the scaling parameters previously set by
calling set_projection_viewport(). This function projects from the
normalized viewing pyramid, which has a camera at the origin and facing
along the positive z axis. The x axis runs left/right, y runs up/down,
and z increases with depth into the screen. The camera has a 90 degree
field of view, ie. points on the planes x=z and x=z will map onto the
left and right edges of the screen, and the planes y=z and y=z map to
the top and bottom of the screen. If you want a different field of view
or camera location, you should transform all your objects with an
appropriate viewing matrix, eg. to get the effect of panning the camera
10 degrees to the left, rotate all your objects 10 degrees to the right.
