214
Now that know how to represent all of the transformations with matrices, you can concatenate them
together, saving a load of time and space. This also changes the way you might think about
transformations. Each object defines all of its points with respect to a local coordinate system, with the
origin representing the center of rotation for the object. Each object also has a matrix, which transforms
the points from the local origin to some location in the world. When the object is moved, the matrix can
be manipulated to move the points to a different location in the world.
To understand what is going on here, you need to modify the way you perceive matrix transformations.
Rather than translate or rotate, they actually become maps from one coordinate space to another. The
object is defined in one coordinate space (which is generally called the object's local coordinate space),
and the object's matrix maps all of the points to a new location in another coordinate space, which is
generally the coordinate space for the entire world (generally called the world coordinate space).
A nice feature of matrices is that it's easy to see where the matrix that transforms from object space to
world space is sitting in the world. If you look at the data the right way, you can actually see where the
object axes get mapped into the world space.
Consider four vectors, called n, o, a, and p. The p vector represents the location of the object
coordinate space with relation to the world origin. The n, o, and a vectors represent the orientation of
the i, j, and k vectors, respectively.

Figure 5.23: The n, o, a, and p vectors for a transformation
You can get and set these vectors right in the matrix, as they are sitting there in plain sight: 215
This system of matrix concatenations is how almost all 3D applications perform their transformations.
There are four spaces that points can live in: object space, world space, and two new spaces: view
space and screen space.
View space defines how images on the screen are displayed. Think of it as a camera. If you move the
camera around the scene, the view will change. You see what is in front of the camera (in front is
defined as positive z).

more complex equations are used, especially since there is now the need to make provisions for z-
buffering. While you want x and y to still behave the same way, you don't want to use a value as
arbitrary as scale.
Instead, a better value to use in the calculation of the projection matrix is the horizontal field of view
(fov). The horizontal fov will be hardcoded, and the code chooses a vertical field of view that will keep
the aspect ratio of the screen. This makes sense: You couldn't get away with using the same field of
view for both horizontal and vertical directions unless the screen was square; it would end up looking
vertically squished.
Finally, you also want to scale the z values appropriately. In Chapter 8
, I'll teach you about z-buffering,
but for right now just make note of an important feature: They let you clip out certain values of z-range.
Given the two variables z
near
and z
far
, nothing in front of z
near
will be drawn, nor will anything behind z
far
.
To make the z-buffer work swimmingly on all ranges of z
near
and z
far
, you need to scale the valid z
values to the range of 0.0 to 1.0.
For purposes of continuity, I'll use the same projection matrix definition that Direct3D recommends in
the documentation. First, let's define some values. You initially start with the width and height of the
viewport and the horizontal field of view.


To draw a triangle, for example, you would take its local space points defining its three corners and
multiply them by the transformation matrix. Then you have to remember to divide through by the w
component and voilá! The points are now in screen space and can be filled in using a 2D raster
algorithm. Drawing multiple objects is a snap, too. For each object in the scene all you need to do is
change the world matrix and reconstruct the total transformation matrix.
The matrix4 Structure
Now that all the groundwork has been laid out to handle transformations, let's actually write some code.
The struct is called matrix4, because it represents 4D homogenous transformations. Hypothetically, if
you wanted to just create rotation matrices, you could do so with a class called matrix3. The definition of
matrix4 appears in Listing 5.23
.
Listing 5.23: The matrix4 structure

struct matrix4
{

/**
* we're using m[y][x] as our notation.
*/
union
{
struct
{
float _11, _12, _13, _14;

219
float _21, _22, _23, _24;
float _31, _32, _33, _34;
float _41, _42, _43, _44;
};

point3 structures and matrix4 structures exists to apply a non-projection transformation to a point3
structure. The matrix4*matrix4 operator creates a temporary structure to hold the result, and isn't terribly
fast. Matrix multiplications aren't performed often enough for this to be much of a concern, however.

Warning
If you plan on doing a lot of matrix multiplications per object or even per triangle,
you won't want to use the operator. Use the provided MatMult function; it's faster.
Listing 5.24: Matrix multiplication routines

matrix4 operator*(matrix4 const &a, matrix4 const &b)
{
matrix4 out; // temporary matrix4 for storing result
for(int j = 0; j < 4; j ++) // transform by columns first
for(int i = 0; i < 4; i ++) // then by rows
out.m[i][j] = a.m[i][0] * b.m[0][j] +
a.m[i][1] * b.m[1][j] +
a.m[i][2] * b.m[2][j] +
a.m[i][3] * b.m[3][j];
return out;
};

inline const point4 operator*( const matrix4 &a, const point4 &b)
{
return point4(
b.x*a._11 + b.y*a._21 + b.z*a._31 + b.w*a._41,
b.x*a._12 + b.y*a._22 + b.z*a._32 + b.w*a._42,
b.x*a._13 + b.y*a._23 + b.z*a._33 + b.w*a._43,
b.x*a._14 + b.y*a._24 + b.z*a._34 + b.w*a._44
);
};

The code to create this type of transformation matrix appears in Listing 5.25
.
Listing 5.25: Code to create a translation transformation

void matrix4::ToTranslation( const point3& p )

222
{
MakeIdent();
_41 = p.x;
_42 = p.y;
_43 = p.z;
}

matrix4 matrix4::Translation( const point3& p )
{
matrix4 out;
out.ToTranslation( p );
return out;
} Basic Rotations
The matrices used to rotate around the three principal axes, again, are:

The code to set up Euler rotation matrices appears in Listing 5.26
.
Listing 5.26: Code to create Euler rotation transformations

void matrix4::ToXRot( float theta )


matrix4 matrix4::YRot( float theta )
{
matrix4 out;
out.ToYRot( theta );

224
return out;
}

//==========

void matrix4::ToZRot( float theta )
{
float c = (float) cos(theta);
float s = (float) sin(theta);
MakeIdent();
_11 = c;
_12 = s;
_21 = -s;
_22 = c;
}

matrix4 matrix4::ZRot( float theta )
{
matrix4 out;
out.ToZRot( theta );
return out;
}


Axis-angle rotations fix both of these problems by doing rotations much more intuitively. You provide an
axis that you want to rotate around and an angle amount to rotate around that axis. Simple. The actual
matrix to do it, which appears below, isn't quite as simple, unfortunately. For sanity's sake, just treat it as
a black box. See Real-Time Rendering (Moller and Haines) for a derivation of how this matrix is
constructed.

Code to create an axis-angle matrix transformation appears in Listing 5.27
.
Listing 5.27: Axis-angle matrix transformation code void matrix4::ToAxisAngle( const point3& inAxis, float angle )

226
{
point3 axis = inAxis.Normalized();
float s = (float)sin( angle );
float c = (float)cos( angle );
float x = axis.x, y = axis.y, z = axis.z;

_11 = x*x*(1-c)+c;
_21 = x*y*(1-c)-(z*s);
_31 = x*z*(1-c)+(y*s);
_41 = 0;
_12 = y*x*(1-c)+(z*s);
_22 = y*y*(1-c)+c;
_32 = y*z*(1-c)-(x*s);
_42 = 0;
_13 = z*x*(1-c)-(y*s);
_23 = z*y*(1-c)+(x*s);

vector and the up vector, and if they're the same thing the behavior of the cross product is undefined. In
games like Quake III: Arena, you can look almost straight up, but there is some infinitesimally small
epsilon that prevents you from looking in the exact direction.
Three vectors are passed into the function: a location for the matrix to be, a target to look at, and the up
vector (the third parameter will default to j <0,1,0> so you don't need to always enter it). The
transformation vector for the matrix is simply the location. The a vector is the normalized vector
representing the target minus the location (or a vector that is the direction you want the object to look
in). To find the n vector, simply take the normalized cross product of the up vector and the direction
vector. (This is why they can't be the same vector; the cross product would return garbage.) Finally, you
can get the o vector by taking the cross product of the n and a vectors already found.
I'll show you two versions of this transformation, one to compute the matrix for an object to world
transformation, and one that computes the inverse automatically. Use ObjectLookAt to make object
matrices that look in certain directions, and CameraLookAt to make cameras that look in certain
directions.
Listing 5.28: LookAt matrix generation code

void matrix4::ToObjectLookAt(
const point3& loc,
const point3& lookAt,
const point3& inUp )
{ 228
point3 viewVec = lookAt - loc;
float mag = viewVec.Mag();
viewVec /= mag;

float fDot = inUp * viewVec;
point3 upVec = inUp - fDot * viewVec;

return out;
}

//==========

void matrix4::ToCameraLookAt(
const point3& loc,
const point3& lookAt,
const point3& inUp )
{
point3 viewVec = lookAt - loc;
float mag = viewVec.Mag();
viewVec /= mag;

float fDot = inUp * viewVec;
point3 upVec = inUp - fDot * viewVec;
upVec.Normalize();

point3 rightVec = upVec ^ viewVec;

// The first three columns contain the basis
// vectors used to rotate the view to point
// at the lookat point
_11 = rightVec.x; _12 = upVec.x; _13 = viewVec.x;
_21 = rightVec.y; _22 = upVec.y; _23 = viewVec.y;
_31 = rightVec.z; _32 = upVec.z; _33 = viewVec.z;

// Do the translation values
_41 = - (loc * rightVec);
_42 = - (loc * upVec);

Code to perform inversion appears in Listing 5.29
.

231
Listing 5.29: Matrix inversion code

void matrix4::ToInverse( const matrix4& in )
{

// first transpose the rotation matrix
_11 = in._11;
_12 = in._21;
_13 = in._31;
_21 = in._12;
_22 = in._22;
_23 = in._32;
_31 = in._13;
_32 = in._23;
_33 = in._33;

// fix right column
_14 = 0;
_24 = 0;
_34 = 0;
_44 = 1;

// now get the new translation vector
point3 temp = in.GetLoc();

_41 = -(temp.x * in._11 + temp.y * in._12 + temp.z * in._13);

collision detection. Games generally use bounding boxes or bounding spheres to accomplish this; I'm
going to talk about bounding spheres. They try to simplify complex graphics tasks like occlusion and
collision detection.
The general idea is that instead of performing tests against possibly thousands of polygons in an object,
you can simply hold on to a sphere that approximates the object, and just test against that. Testing a
plane or point against a bounding sphere is a simple process, requiring only a subtraction and a vector
comparison. When the results you need are approximate, using bounding objects can speed things up
nicely. This gives up the ability to get exact results. Fire up just about any game and try to just miss an
object with a shot. Chances are (if you're not playing something with great collision detection like MDK,
Goldeneye, or House of the Dead) you'll hit your target anyway. Most of the time you don't even notice,
so giving up exact results isn't a tremendous loss.
Even if you do need exact results, you can still use bounding objects. They allow you to perform trivial
rejection. An example is in collision detection. Typically, to calculate collision detection exactly is an
expensive process (it can be as bad as O(mn), where m and n are the number of polygons in each

233
object). If you have multiple objects in the scene, you need to perform collision tests between all of
them, a total of O(n
2
) operations where n is the number of objects. This is prohibitive with a large
amount of complex objects. Bounding object tests are much more manageable, typically being O(1) per
test.
To implement bounding spheres, I'll create a structure called bSphere3. It can be constructed from a
location and a list of points (the location of the object, the object's points) or from an explicit location and
radius check. Checking if two spheres intersect is a matter of calling bSphere3::Intersect with both
spheres. It returns true if they intersect each other. This is only a baby step that can be taken towards
good physics, mind you, but baby steps beat doing nothing!
Listing 5.30: Bounding sphere structure

struct bSphere3

{
iter i = begin;
m_loc = loc;
m_radius = 0.f;
float currRad; while( i != end )
{
currRad = (*i).Mag();
if( currRad > m_radius )
{
m_radius = currRad;
}
i++;
}
}

static bool Intersect( bSphere3& a, bSphere3& b )
{
// avoid a square root by squaring both sides of the equation
float magSqrd =
(a.m_radius + b.m_radius) *
(a.m_radius + b.m_radius);
if( (b.m_loc - a.m_loc).MagSquared() > magSqrd )
{
return false;
}

235
return true;
}
};

. I've left out a few routine bits of code to keep the listing
focused.
Listing 5.31: The color4 structure

struct color4

236
{
union {
struct
{
float r, g, b, a; // Red, Green, and Blue color data
};
float c[4];
};

color4(){}

color4( float inR, float inG, float inB, float inA ) :
r( inR ), g( inG ), b( inB ), a( inA )
{
}

color4( const color3& in, float alpha = 1.f )
{
r = in.r;
g = in.g;
b = in.b;
a = alpha;
}


unsigned long MakeDWordSafe()
{
color4 temp = *this;
temp.Sat();
return temp.MakeDWord();
}

// if any of the values are >1, cap them.
void Sat()
{
if( r > 1 )
r = 1.f;

238
if( g > 1 )
g = 1.f;
if( b > 1 )
b = 1.f;
if( a > 1 )
a = 1.f;
if( r < 0.f )
r = 0.f;
if( g < 0.f )
g = 0.f;
if( b < 0.f )
b = 0.f;
if( a < 0.f )
a = 0.f;
}