Hierarchical Transformations Part 8: Matrix Transformation Tutorial
Table of Contents
 Introduction
 Math Prerequisites
 Importance of Correct Transformations
 What a Matrix Represents
 Matrix Multiplication
 Transforming a Vector by a Matrix
 Object Space Transformations
 Camera Transformations
 Inverse Transformations
 Hierarchical Transformations
 Precision
 Conclusion
Hierarchical Transformations
I must confess, MechWarrior ][ is the game that inspired me to
grind out all of this matrix code. I found it so realistic, being
able to move in so many different coordinate systems (I wonder if the
casual user realizes this? :) I had been wanting to implement all
this in my code for quite some time, and playing MW2 was the event
that pushed me over the edge.
Another thing that this game showed me was the usefulness of
hierarchical transformations. If you are lost in my terminology, let
me explain what I mean by hierarchical transformations.
Apart from being a great spelling bee word, a hierarchy is an
organazation of things into levels. In a very general sense, the
things higher up in a hierarchy have control over the lower things.
This applies to business, government, and our favorite subject, matrix
transformations.
As far as matrix transformations are concerned, consider an arm as
an example of a hierarchical object. The topmost object in the arm
hierarchy is the bicep or upper arm, followed by the forearm, the
hand, and the fingers. Each of these 'objects' has an origin, the
bicep has the shoulder, the forearm has the elbow, the hand has the
wrist, and the fingers have the knuckles.
Here is where the hierarchical part comes into play, remember what
I said earlier about higher things on a hierarchy being able to
control the lower things? Well, move your bicep up in the air by
pivoting your shoulder. Surprise! Your forearm, hand and fingers
moved with your bicep. Now move your forearm by bending your elbow.
Notice that your hand and fingers moved, but your bicep did not. This
is because your forearm is lower in the hierarchy than your bicep, and
therefore has no control over it.
Here is an interesting question. How on earth do you
mathematically represent this hierarchy of objects in a correct
manner? More importantly, how can you do it quickly? Using matrices,
you can correctly transform a hierarchy of objects in no more time
than it takes to transform nonhierarchical objects.
Alright, its time for a little side trip into the dreaded land of
data structures. While it is coding hell for the beginner, the land
of data structures is the playground of any experienced programmer.
Data structures are easy, its the implementation that kills most
people. Most people with little experience in data structures and
data relationship immediately try to swat a fly with an elephant gun
by applying every data structure in the book to a simple problem.
"How about if I make an array of stacks containing doubly linked lists
of AVL trees, would that work?" Well, I'm not one to say it would
not. However, I have found that the simplest solution to a problem is
generally the best.
In this case, the simplest solution to creating a hierarchical
object data structure is to have parent objects keep track of their
children only.
typedef struct object
{
(other stuff here)
...
object **children;
int numchildren;
} object;
The **children member of the struct above allows you to dynamically
allocate enough memory for the children of each object. For example,
if we were making an instance of this struct for a hand, we would
allocate an array of five pointers for **children. These pointers
would be set to the addresses of the object structs which contain the
children of the hand, namely the fingers.
Now that we have discussed how to implement the hierarchy data
structures, lets move on to cover how to perform the actual
hierarchical transformations. First, if you will recall, our system
of matrix transformations handles incremental rotation and
translation; that is, objects are transformed according to some change
in position and change in angles of rotation. This feature lends
itself well to hierarchical transformation.
If you were to transform two objects by the same matrix, what
would be the result? The two objects would have the same orientation
relative to each other before and after the transformation. This
property of matrix transformation is key to hierarchical
transformations. Consider the arm example again. Keeping your elbow
and wrist stiff, extend your arm in front of you and raise and lower
it by rotating your arm at the shoulder. Your arm will stay straight,
it appears that all objects (bicep, forearm, hand, fingers) are
behaving as one object.
If this were the extent of a hierarchy's usefulness, we could
simply transform each child object using the matrix of its parent.
But we want each child object to be able to move on its own too; that
is, we want to be able to bend the elbow, wrist, and fingers while we
raise and lower our shoulders, using the arm example again. Here is
where the incremental rotation comes in handy. Consider the matrix of
a parent object as a starting point. The orientation of a child can
then be expressed in terms of this parent orientation plus some
rotation and translation increment. This increment can be expressed
in terms of an object matrix.
Actually, we already calculate this matrix in our code; in my code
its the omatrix member of the object struct. This matrix contains the
orientation of the object, and we can easily express this orientation
in terms of an increment to the orientation of a parent object. To do
this, simply understand that when you rotate the forearm 5 degrees,
you are putting a 5 degree bend in your arm between the forearm and
the bicep. Likewise, translating the forearm or hand would move it
relative to its parent according to the displacement vector specified.
Of course, the initial position of the object's origin must be given
as a displacement from the origin of the parent object if you are
going to use this system of object hierarchy.
Here is where the big advantages of this method come into play.
According to what we have already said, the transformation formula for
a child in an object hierarcy would be
[O] = [O] * [T] * [X] * [Y] * [Z] * parent.[O] * parent.parent.[O] ...
[E] = [O] * [C]
where parent.[O] is the object space matrix of the parent to this
object, parent.parent.[O] is the object space matrix of the parent's
parent, etc.
We can shorten this definition to
[E] = [O] * [T] * [X] * [Y] * [Z] * parent.[O] * ... * [C]
Since [E] = [O] * [C], we can substitute parent.[E] = parent.[O] *
[C]. Then, our transformation formula becomes
[E] = [O] * [T] * [X] * [Y] * [Z] * parent.[E]
Which is the same number of matrix multiplies as our original
transformation formula!
Now back to data structures for a second, so we can make some
pseudo code illustrating this point. In my rendering engine, I keep a
list of objects to be rendered. Using this method of hierarchy, only
the parent object in the hierarchy should be in this list. This is
because all objects in the object list are rendered using the camera
matrix, whereas all children must be rendered using the eyespace
matrix of their parent (which contains the parent object space matrix
and the camera matrix). Therefore, in a call to transform or render
an object, you should make sure that the object will transform and
render its children. here is some pseudocode
void transformobject(object *obj, float cmatrix[4][4])
{
(do transformations on this object)
...
for (count = 0; count < obj>numchildren; count++)
transformobject(obj>children[count], obj>ematrix);
}
void renderobject(object *obj)
{
(render the object however you like)
...
for (count = 0; count < obj>numchildren; count++)
renderobject(obj>children[count]);
}
