Hierarchical Transformations Part 8: Matrix Transformation Tutorial

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 non-hierarchical 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]);

}

Hierarchical Transformations Part 8: Matrix Transformation Tutorial

Table of Contents

Hierarchical Transformations