Overview
Often in a renderer, it is useful to have a system of local transformations for each object to properly place them in the world and a set of world transformations to properly orient the scene in relation to a camera coordinate system. This simplistic system only requires a transformation matrix for each object and a world transformation matrix for the camera system; however, more complex modeling systems often require objects to move in relation to other objects in a sort of parent-child object-dependent system. For example, if we wanted to model a robot arm we would have each section of the arm be a separate object that has its own set of transformations. Each object's transformations must be composed of its parent object transformations. So the base of the robot is only influenced by transformations that transform it into a world coordinate system, and the first section of the arm has a composed matrix that transforms it into the base coordinate system, and the next section of the arm has a matrix that transforms it into the arms, and so on. The point is that each object in the arm has a "parent" or is dependent on another object for its transformations. Ultimately, for example, the arm must be transformed into the base's system and then into the world, so its composed matrix must be ARM x BASE x WORLD. Each object has its own local coordinate system that must be transformed to fit into it's parent coordinate system. This scheme sets up a hierarchy of dependent objects whose transformation matrices are composed of its own local matrix along with the parent matrix:
OBJECT HIERARCHY: BASE BaseToWorldMatrix Dependent only on world system ARM ArmToBaseMatrix Dependent on Base system (which is dependent on world) HAND HandToArmMatrix Dependent on Arm system (dependent on base and world) COMPOSED MATRICES REQUIRED FOR EACH OBJECT FOR PROPER MODELING: BASE BaseToWorld X World ARM ArmToBase X BaseToWorld X World HAND HandToArm X ArmToBase X BaseToWorld X WorldIt is quite clear that a system of parent-child dependencies has been built up to properly tranform the robot arm. So now if the ArmToBase matrix is altered (as in a rotation) the hand will be rotated along with it as long as these dependencies are constantly updated. This hierarchy forms an object tree, so it is important to note that if the object's matrices that are further up are composed before the lower objects, we need only multiply an object's transformation matrix by its parent matrix to obtain a final matrix for the current object. For example if the robot's object matrices are composed in the following order: BASE, ARM, and then HAND, we will obtain the following matrix compositions:
COMPOSITION OF MATRICES (in this order): BASE ComposedBase = BaseToWorld X World ARM ComposedArm = ArmToBase X ComposedBase HAND ComposedHand = HandToArm X ComposedArmOnce these final composed matrices are found, each object can then merely apply its own final matrix to each of its vertices to properly orient the objects with respect to each other.
So what does all of this mean? Well, now we have a system of composed transformations that are in one final matrix for each object. So, for the BASE, the ComposedBase matrix will move the base around on the floor and finally into its position in world coordinates and then the world transformation will be applied to properly orient it with the camera system. The ComposedArm matrix will rotate the arm about its own local coordinate system rotation point and then move the arm up onto the base's connection in the base coordinate system, and since the ComposedArm matrix includes the base's transformations, the ARM will move along with the BASE.
Possible Implementation
So how can we implement this? Clearly, each object needs a list of its own local transformations, a local transformation matrix composed from its local transformation list, a final composed matrix composed from its local and parent transformation matrices, an index of its parent object that it is dependent on, and an Updated flag that tells if the final composed matrix needs updating (if it has been changed). Also, the world needs its own list of transformations corresponding to the camera system, along with its own final matrix and Update flag. So here are some possible data structures:
What a hierarchically modeled object should contain:
// TRANSFORMATION LIST ELEMENT
typedef struct
{
int Type; // transformation type (rotate, translate, scale)
float x,y,z; // transformation parameters
4x4MatrixType M; // the matrix pertaining to this transformation
} TransformListElementType;
// AN EXAMPLE TRANSFORMATION LIST (array)
TransformListElementType TransList[MAXNUMLOCALTRANS];
int NumTrans; // number of transformations actually used in array
// LOCAL TRANSFORMATION MATRIX COMPOSED FROM TRANSFORMATION LIST MATRICES
4x4MatrixType LocalM;
// FINAL TRANSFORMATION MATRIX COMPOSED FROM LocalM X ParentComposedM
// THIS IS THE ACTUAL MATRIX APPLIED TO THIS OBJECT'S VERTICES
4x4MatrixType ComposedM;
// INDEX OF PARENT OBJECT (-1 means only dependent on World System)
int ParentObj;
// Update FLAG INDICATING WHETHER OR NOT THE FINAL COMPOSED MATRIX
// NEEDS UPDATING (ComposedM)
int Updated;
The world system only requires the transformation list and a local "world" transformation matrix composed from its transformation list.
So now we have the proper data structures in place, each element in the hierarchy is only responsible for its own local transformation matrix; a second pass will be used to update the parent-child final composition matrices. So what happens from start to finish? Each object will have a list of local transformations that will have their own corresponding transformation matrices to maintain. For example, if the first object has the following transformations: Scale 1.1 1.2 1.3, RotateAboutY 1.2, and Translate 100 100 100, each of these will have a corresponding transformation matrix (three matrices total). Each of these matrices will be composed into one final local transformation matrix (LocalM). Each object will have a LocalM (the world will also have its own) that is used to form the final composed matrices (ComposedM). So if an object's transformation list is altered, then so must the list's corresponding matrices, the LocalM, the ComposedM, and the ComposedM's of all objects dependent on this object (further down in the hierarchy). So, for example, in our robot arm example, if the HAND is altered, then only its ComposedM must be rederived, but if the BASE is moved then the BASE, ARM, and HAND's ComposedM must all be rederived since they are all dependent on the BASE further down the hierarchical modeling tree.
How are the transformation list element matrices updated?
Each transformation list element has a transformation type and a set of parameters, so its matrix simply corresponds to this transformation:
Possible transformations: RotateAboutX radians RotateAboutY radians RotateAboutZ radians Scale AlongX AlongY AlongZ Translate AlongX AlongY AlongZOnly the scaling and translation will use all three parameters, the rotations will only require the first (x). If any of these parameters are changed for an object, its corresponding matrix and the locally composed matrix must be updated. These matrices are updated individually only when they are first created (while reading in initial transformations) or when they are altered.
How are the local object and world transformation matrices updated?
First of all, the transformation list element matrices must all be updated. Then the local transformation matrix is simply the composition of all of the matrices in the transformation list. In the above example, we had a list consisting of three transformations: scale, rotate, and then translate, the local matrix will be computed as the composition of these: scale x rotate x translate. Here is an example loop that will update an objects local transformation matrix from the transformation list matrices:
LocalM = IDENTITYMATRIX; for (int i=0; i < NumTrans; i++) LocalM = LocalM x TransList[i].M;
How are final composed transformation matrices updated?
This requires that all of the local matrices (including world's matrix) has been properly updated in the following order: transformation list matrices and then local composition matrices. This one is a little tricky because we must now set up the proper hierarchy of matrix compositions. Each object has a parent object (or the world) that it is dependent on; this is indicated by its ParentObj index. If this value is -1, then it is dependent only on the world transformations, otherwise it indicates which object (starting at 0) it is dependent on. The order in which these final matrices are composed is crucial; the objects higher up on the hierarchy must be processed before the lower ones.
So we must first check for all objects dependent only on the world system (ParentObj = -1), these object's ComposedM's will simply be their LocalM x WorldM. The parent being the world. Subsequent objects are processed in order of dependency; the next objects processed will be dependent on object 0, and so on. Here are two example loops that will update all of the object's ComposedM's:
// FOR OBJECTS DEPENDENT ONLY ON THE WORLD MATRIX (ParentObj=-1) for (int i=0; i < NumObjects; i++) if (Objs[i].ParentObj < 0) Objs[i].ComposedM = Objs[i].LocalM x WorldM; // FOR SUBSEQUENT OBJECTS (NOT DEPENDENT ONLY ON WORLD) for (int ParentObj=0; ParentObj < NumObjects; ParentObj++) for (int i=0; i < NumObjects; i++) if (Objs[i].ParentObj == ParentObj) Objs[i].ComposedM = Objs[i].LocalM x Objs[ParentObj].ComposedM;