2. Bone hierarchy and skinning

We know how to process a mesh. Still we are not any closer to skeletal animation. We are missing the model skeleton. The example code in Sample2.zip builds upon the previous code to support skinning information.

2.1. Design

2.1.1. Descriptions

In drawing courses, the first thing taught to students for drawing a character is anatomy. To correctly draw a character in a pose, students must know how the body is composed (how the skeleton is made, where the muscles go, how the skin drapes the muscles and the skeleton). Computer graphics are no exception.

A 3D model of a character consists of a skeleton and a skin. The skeleton describes the underlying structure of the model: it helps modelling any pose for a given 3D character. The skin is represented by a polygonal mesh. Below you see below an outline for a gorilla (that's all my drawing capabilities permit ;) ): the skeleton is black and the skin is grey.

The skeleton is a hierarchic set of bones. The bones are represented by matrices. What does that mean? All bones are defined with a joint at the origin, this is called bone space. The associated matrix of a bone scales, rotates and translates the bone to connect it to its immediate parent. This is a local transform matrix since the bone is placed relative to its immediate parent. To place all the bones of a skeleton in character space we must combine the bone local matrix with its parent combined matrix:

Combined_Matrix_bone = Local_Matrix_bone * Combined_Matrix_parent

This combined matrix will be used to display our vertebrate model. There still is one problem: how do we link the polygonal mesh to the underlying skeleton?

The brute polygonal mesh (like the one we extracted in sample1) is said to be in bind space. To combine the skeleton with the mesh in bone space, we use another set of matrices called skin offset transform matrices. These matrices displace the mesh vertices to conform it to the bones. To display the boned mesh into character space, we combine the skin offset matrix of each bone with its corresponding combined matrix:

Final_Matrix_bone = Skin_Offset_bone * Combined_Matrix_bone

This means we first displace the mesh from bind space to bone space, and then we transform the skinned mesh from bone space to character space. Now the mesh is draped around the bones in character space simply by multiplying each vertex by its corresponding bone final matrix.

There still is one problem. When bones are making an angle the mesh may show ungainly angles or gaps (see drawing below).

We need to weight each vertex to define the influence of each bone Final Matrix. Thus the final vertex position in character space is defined by:

Vertex_dest = SUM ( Vertex_source * Underlying_Bone_Final_Matrix * Underlying_Bone_Weight[Vertex_source])

Where shall we find the information in the X file format? Microsoft uses two different blocks:

• Frame: this block describes the bone. It names the bone. It contains one FrameTransformMatrix block describing the bone local matrix and other Frame blocks defining all the children bones. The frame also references the mesh it applies to either by name or by declaration of a Mesh Block. The children of a frame inherit the mesh reference if they do not define their own.
• SkinWeight: this block contains the bone name, the skin offset matrix, the list of vertices to apply this matrix on and the list of weights for these vertices. We find this block within the Mesh block.

Now let's look at the functionalities we need this time:

• Extract the bone hierarchy with all its related matrices.

• Concatenate the meshes and update the bone references
• Calculate the character space matrices
• Display the skinned model.

2.1.2. Code Design

If we look closely at the way matrices are combined, we won't be able to rely on the glMultMatrix function: The glMultMatrix function multiplies the current Matrix on top of the stack with the matrix passed as a parameter:

Top_of_Stack = Top_of_Stack * Parameter Matrix

We need to combine matrices the other way around:

Top_of_Stack = Parameter Matrix * Top_of_Stack

Since matrix multiplication is not commutative ( A*B != B*A), we need our own matrix class with overloaded multiplication operators for Matrix multiplication (for calculating Bone combined matrices) and scalar multiplication (for weighting the final transformation matrix).

We need a Bone class to store the local transform matrix, the skin offset matrix, the list of vertices the bone is linked to and their associated weights, and pointers to the children bones. The Model stores a pointer to the first bone of the hierarchy.

Now let's draw our model. We first want an ObjectBone class. This class holds and does all the matrix calculations (Combined and final transform matrices). It references a bone from the Model to get the Local Transform Matrix and the Skin Offset Matrix. The Object3D class evolves to store a reference to a hierarchical list of ObjectBones strictly replicating the Model-Bone structure.

Thus whenever we need to update the skinned mesh, we call the update function from Object3D that will calculate all the matrices in the hierarchical set of ObjectBone before multiplying each of the final matrices by the Model Mesh to get the final skinned mesh.

That's all for the design.

2.2. Implementation

I will not discuss the Matrix class implementation. This is pretty standard and any quick search on the web will give you all you need to know about matrices operations. There are also existing implementations of Matrix classes like the [WML] library you can reuse.

2.2.1. Parsing the file (file sample2.zip)

The modified X File loading class is in files ToolBox\IOModel_x.h and cpp.

We must modify our Frame processing function. This function gets a pointer to a model Bone as a parameter. You will understand when you look at the pseudo-code:

In the Bone processing loop, if the recognised block name is Frame, we recursively call this processing function with the current bone as a parameter.

Processing the FrameTransformMatrix block is simple. We just read in the 16 values into the bone Local Transform matrix.

Processing the SkinWeight block is a little bit trickier since we need to map the SkinWeight data to the bone class. Let's look at the pseudo-code:

To retrieve the correct bone object, we use the IsName method from the bone object. This method checks first if the bone is the one searched for. If not, then it processes all the children bones. If no bones are found, the method returns null.

When we have finished loading the model, we map the mesh to the bones. We propagate the mesh name of a bone to all its children without mesh names. This step is important for when we concatenate the meshes.

2.2.2. Concatenating Meshes

When we concatenate the meshes, we must update the mesh reference and the vertex indices in each bone class. The pseudo-code for the private method UpdateBoneIndices of the Model Class is:

When we load multiple meshes, each subsequent mesh has a special variable initiated which is the sum of the previous meshes vertices number (see 1.2.3). This variable is used to update the bone vertices index list to keep the link between the bone and the concatenated mesh.

2.2.3. Displaying the result

We are now left with the last part of our implementation. When we initialise an instance of Object3D with our loaded Model, we replicate the Model Bone hierarchy into a corresponding ObjectBone hierarchy. This is the task of the private Object3D method ReplicateSkeletton. This method takes a Model Bone pointer as a parameter and returns an ObjectBone:

Whoa! What is that transform matrix? This matrix variable within the Object Bone class is used to hold a local transform matrix before any matrix calculation. We will come back to that matrix in the 3^rd chapter on animations. Suffice to say it is just a copy of the local transform matrix.

Once the skeleton is replicated, we clear the skinned mesh in Object3D then we call our Update method. This method is modified to calculate all the matrices before skinning the mesh. This calculation is done by the function CalcAttitude with two parameters: the current ObjectBone and its immediate parent:

It's pretty straight forward code.

Eventually we call the SkinMesh method to recursively process each ObjectBone to transform each bone vertex by the Final Matrix and the bone weight list.

The character is ready to display. Note that we put the Update method in the idle function: this means that our skinned mesh is calculated back at each call of our Idle function.

Animating the model