Implementing a Scene Hierarchy

A matrix stack simplifies the construction of hierarchical models, in which complicated objects are constructed from a series of simpler objects.

A scene, or transform, hierarchy is usually represented by a tree data structure. Each node in the tree data structure contains a matrix. A particular matrix represents the change in coordinate systems from the node's parent to the node. For example, if you were modeling a human arm, you might implement the following hierarchy.

In the preceding hierarchy, the Body matrix places the body in the world. The UpperArm matrix contains the rotation of the shoulder, the LowerArm matrix contains the rotation of the elbow, and the Hand matrix contains the rotation of the wrist. To determine where the hand is relative to the world, you would simply multiply all the matrices from Body down through Hand together.

The previous hierarchy is overly simplistic, since each node has only one child. However, if you begin to model the hand in more detail, you will probably want to add fingers and a thumb. Each digit could be added to the hierarchy as children of Hand.

Now, if you traverse the complete graph of the arm in depth-first order (traversing as far down a single path as possible before moving on to the next alternative path) to draw the scene, you would perform a sequence of segmented rendering. For example, in order to render the hand and fingers you would implement the following pattern.

1. Push the Hand matrix onto the matrix stack.
2. Draw the hand.
3. Push the Finger 1 matrix onto the matrix stack.
4. Draw the first finger.
5. Pop the Finger 1 matrix off of the stack.
6. Push the Finger 2 matrix onto the matrix stack.
7. Draw the second finger.
8. Pop the Finger 2 matrix off of the stack.
9. Push the Finger 3 matrix onto the matrix stack. You would continue in this manner until all of the fingers and thumb have been rendered.

After you have completed rendering the fingers, you would pop the Hand matrix off of the stack.

You can follow this basic process in code with the following examples. When you encounter a node during the depth-first search of the tree data structure, push the matrix onto the top of the matrix stack.

MatrixStack->Push();
MatrixStack->MultMatrix(pNode->matrix);

When you are finished with a node, pop the matrix off of the top of the matrix stack.

MatrixStack->Pop();

In this way, the matrix on the top of the stack will always represent the world-transform of the current node. Therefore, before drawing each node, you should set the Direct3D matrix.

pD3DDevice->SetTransform(D3DTRANSFORMSTATE_WORLD, *MatrixStack->GetTop());

For more information on the specific methods that you can perform on a Direct3DX matrix stack, see the ID3DXMatrixStack reference topic.