Heirarchical transformations
Once we start moving beyond simple models in computer graphics we will find it convenient to construct heirarchical models. In a heirarchical model we try to model a complex object made up of various parts that move independently. The most obvious example of this is a graphics model of a person with limbs that can move independently and be repositioned with respect to the person's torso.
The diagram below shows a simple example of a heirarchical model in two dimensions representing something like an industrial robot with a fixed base and an articulated arm that can move relative to the base by bending a pair of joints.
The coordinate frame positioned at 
acts as the object coordinate frame for the entire model. The robot has joints at 
and 
that can be rotated independently: the diagram shows the joint at 
rotated through a positive angle θ and the joint at 
rotated through a negative angle φ.
The diagram shows a secondary frame positioned at 
. We can use that frame to describe the location of the point 
:
If we change the joint angle θ, the point 
will stay at the same coordinates relative to the coordinate frame 
t.
What should we do with the coordinate frame 
t? One approach is to try to express that coordinate frame relative to the world coordinate frame. A second, somewhat more straightforward, approach is to express the 
t coordinate frame relative to the object coordinate frame 
t:
Once we can express the coordinate frame 
t relative to the frame 
t we can express the location of the point 
relative to the frame 
t as
Here B is the transformation matrix that transforms coordinates relative to 
t to coordinates relative to 
t. If we bend the joint at 
we will be moving the point at 
, although that point's coordinates in the 
t frame will not change. What will change instead the B matrix that relates the 
t frame to the 
t frame.
Finally, we will have to relate the 
t frame to the world coordinate frame. As usual, this is done by setting up an appropriate transformation matrix.
In world coordinates our point 
is now expressed
This allows us to move the entire robot around by updating only the A matrix, as well as bending the joint at 
by updating only the B matrix.
A system of bones
Character animation in computer graphics starts with the concept of a skeleton. A skeleton is a collection of bones organized in a heirarchy. The origin bone gives us a point of reference for the skeleton. By moving that origin bone around in the scene we can move the entire figure around.
Each bone in the skeleton can have 0 or more child bones that are positioned relative to that bone via a transformation. In the diagram above, bone 0 is the origin bone. Bone 0 has one child bone, bone 1, that is translated upward and rotated through an angle. Bone 1 in turn has a child bone, bone 2, that is translated and rotated relative to bone 1.
The transformations that we use to position the bones relative to each other form a heirarchical system of transformations that can be used as the basis for a local coordinate system.
Rigid body transformations
All of the transformations that we will use for our system of bones will involve only a translation relative to the origin of the parent bone followed by a rotation. For simplicity we will always combine these two transformations into a single transformation, called a rigid body transformation, or RBT for short.
I have written a C++ class that we will use to represent and work with RBTs:
class RigTForm {
glm::vec3 t_; // translation component
glm::mat4 r_; // rotation component
public:
RigTForm() : t_(0.0f), r_(1.0f) {}
RigTForm(const glm::vec3& t, const glm::mat4& r): t_(t),r_(r) {}
explicit RigTForm(const glm::vec3& t) : t_(t), r_(1.0f) {}
explicit RigTForm(const glm::mat4& r) : t_(0.0f), r_(r) {}
glm::vec3 getTranslation() const {
return t_;
}
glm::mat4 getRotation() const {
return r_;
}
RigTForm& setTranslation(const glm::vec3& t) {
t_ = t;
return *this;
}
RigTForm& setRotation(const glm::mat4& r) {
r_ = r;
return *this;
}
glm::mat4 toMatrix() {
return glm::translate(glm::mat4(1.0f), t_)*r_;
}
};
Attaching flesh to the bones
Since each bone forms its own local bone coordinate frame, we can draw objects relative to that coordinate frame. For example, in the picture below we draw three cylinders over the three bones. Each of the three cylinders has the same coordinates in bone coordinates. Since the bones make three distinct coordinate frames, when we draw the cylinders they will all appear positioned relative to their underlying bone frames.
The obvious problem with this approach is that it leaves gaps at the joints between bones.
Skinning
The skinning technique seeks to overcome the gaps at joints by way of an averaging process. The basic idea is to average together the bone coordinate transformations for both bones on either side of a joint for vertices on the cylinders that are close to the joints.
The result is a more pleasing and realistic image.
Rigging
In the technique called rigging we start with a three dimensional image of a figure that we want to animate. The figure will usually be drawn first via standard 3d modeling software.
The image is then rigged by placing a skeleton in the interior of the image. In the rigging process, we need to assign each of the vertices in the image to an underlying bone, so that the vertex will move along with the bone as we animate the skeleton.
In order to solve the gapping problem at joints, we make it possible to assign vertices to more than one bone. For example, for a vertex near a joint, we can assign the vertex 50% to each of the bones that meet at that joint. Then, when we render the figure, we can compute where each of the bones would want to position that vertex and then just average those positions together using the assigned ratios. The result is that the parts of the figure will track the motion of the bones in a smooth and convincing way without gaps at the joints.
One small technical problem with the rigging process has to do with the fact that the image is drawn before placing the skeleton. This means that the vertices that make up the image will be described in object coordinates, and not in bone coordinates. To make up for this, we compute an offset transformation for each bone as we build the skeleton and rig the figure. The offset transformation translates object coordinates to bone coordinates for each of the vertices assigned to a bone, making it possible for us to represent each of these vertices in bone coordinates. If we subsequently reposition the skeleton, these bone coordinates can then be translated to world coordinates using the coordinate frame attached to the bone in question.
An implementation
To demonstrate the skinning process, I have written a simple demo application. The application constructs a simple cylinder shape and rigs it with a system of three bones arranged as shown below. The bones run down the center of the cylinder.
Once the figure is rigged, we can move the bones to a new orientation
and the vertices will follow, producing the image shown here.
Implementation details
The first thing needed to implement rigging in the example application is a pair of classes that represent bones and skeletons.
class Skeleton;
class Bone
{
private:
RigTForm transform_;
glm::vec3 offset_;
Bone* parent_;
public:
Bone(Bone* parent,const glm::vec3& offset,const RigTForm& transform);
void rotateBy(const glm::mat4& rotation);
void setRotation(const glm::mat4& rotation);
glm::mat4 getModelMatrix() const;
glm::mat4 getBoneMatrix() const;
};
class Skeleton
{
private:
std::map<int,Bone*> bones_;
public:
Skeleton();
~Skeleton();
Bone* addBone(int name,Bone* parent,const glm::vec3& offset,const RigTForm& transform);
Bone* getNamedBone(int name);
};
Each bone contains a rigid body transformation that positions the bone relative to its parent bone, and an offset transformation as described above. Bones can move by using either the rotateBy() or setRotation() functions to order a bone to change its orientation relative to its parent. The getBoneMatrix() function returns a transformation matrix that can be used to map a vertex attached to this bone to a new location in object coordinates when the underlying bone moves.
Each bone has an integer 'name' associated with it that we can use to identify it later in the rigging process.
Here is an updated Extruded class that can generate indices, vertex locations, normals, bone name vectors and bone weight vectors.
class Extruded
{
private:
int numVertices;
int numIndices;
int numSlices;
std::vector<int> indices;
std::vector<glm::vec3> vertices;
std::vector<glm::vec3> normals;
std::vector<glm::ivec3> names;
std::vector<glm::vec3> weights;
protected:
int numSamples;
void init();
virtual glm::vec3 normal(int i,int j) = 0;
virtual glm::ivec3 name(int i,int j) = 0;
virtual glm::vec3 weight(int i,int j) = 0;
virtual glm::vec3 base(int i) = 0;
virtual glm::mat4 T(float t) = 0;
public:
Extruded(int samples,int slices);
int getNumVertices();
int getNumIndices();
std::vector<int> getIndices();
std::vector<glm::vec3> getVertices();
std::vector<glm::vec3> getNormals();
std::vector<glm::ivec3> getBoneNames();
std::vector<glm::vec3> getBoneWeights();
};
We then build an updated Cylinder class on top of this framework. The cylinder now includes methods to generate bone name vectors and bone weight vectors for each vertex:
class Cylinder : public Extruded
{
public:
Cylinder(int samples,float r,float h) : Extruded(samples,48) {
height = h;
radius = r;
init();
}
protected:
virtual glm::vec3 normal(int i,int j) {
return this->base(i);
}
virtual glm::ivec3 name(int i,int j) {
return glm::ivec3(0,1,2);
}
virtual glm::vec3 weight(int i,int j) {
float t = float(j)/48;
float cutOne = 1.0f / 3;
float cutTwo = 2.0f / 3;
float margin = 1.0f / 24;
if(t <= cutOne - margin)
return glm::vec3(1.0,0.0,0.0);
if(t <= cutOne + margin)
return glm::vec3(2.5 - 6*t,-1.5 + 6*t,0.0);
if(t <= cutTwo - margin)
return glm::vec3(0.0,1.0,0.0);
if(t <= cutTwo + margin)
return glm::vec3(0.0,4.5 - 6*t,-3.5 + 6*t);
return glm::vec3(0.0,0.0,1.0);
}
virtual glm::vec3 base(int i) {
float s = ((float) i)/numSamples;
return radius*glm::vec3(cos(-s * 2.0f * 3.14159f), 0, sin(-s * 2.0f * 3.14159f));
}
virtual glm::mat4 T(float t) {
return glm::translate(glm::mat4(1.0),glm::vec3(0,height*t,0));
}
private:
float height;
float radius;
};
To perform vertex position averaging, we modify the vertex shader to compute the needed averages.
#version 430
layout (location = 0) in vec3 vertPos;
layout (location = 1) in vec3 vertNormal;
layout (location = 2) in ivec3 vertNames;
layout (location = 3) in vec3 vertWeights;
out vec3 varyingNormal;
out vec3 varyingLightDir;
out vec3 varyingVertPos;
struct PositionalLight
{ vec4 ambient;
vec4 diffuse;
vec4 specular;
vec3 position;
};
struct Material
{ vec4 ambient;
vec4 diffuse;
vec4 specular;
float shininess;
};
uniform vec4 globalAmbient;
uniform PositionalLight light;
uniform Material material;
uniform mat4 proj_matrix;
uniform mat4 bones[8];
uniform mat4 boneNormals[8];
void main(void)
{
varyingNormal = vec3((vertWeights.x*boneNormals[vertNames.x]+
vertWeights.y*boneNormals[vertNames.y]+
vertWeights.z*boneNormals[vertNames.z]) * vec4(vertNormal, 0.0));
varyingVertPos = ((vertWeights.x*bones[vertNames.x]+
vertWeights.y*bones[vertNames.y]+
vertWeights.z*bones[vertNames.z]) * vec4(vertPos, 1.0)).xyz;
varyingLightDir = light.position - varyingVertPos;
gl_Position = proj_matrix * vec4(varyingVertPos,1.0);
}
Before invoking this shader we will have asked each of the bones for their bone transformation matrices. These will get passed in through the uniform arrays bones. Normal transformation matrices will also get passed in through boneNormals so we can compute an averaged normal at each vertex.
Finally, here is the code for display() function to show how we update the bone angles, get the bone transformation matrices and bone normal matrices, and then pass all of this information to the shader.
void display(GLFWwindow* window, double currentTime) {
glClear(GL_DEPTH_BUFFER_BIT);
glClear(GL_COLOR_BUFFER_BIT);
glUseProgram(renderingProgram);
projLoc = glGetUniformLocation(renderingProgram, "proj_matrix");
mvLoc[0] = glGetUniformLocation(renderingProgram, "bones[0]");
mvLoc[1] = glGetUniformLocation(renderingProgram, "bones[1]");
mvLoc[2] = glGetUniformLocation(renderingProgram, "bones[2]");
nLoc[0] = glGetUniformLocation(renderingProgram, "boneNormals[0]");
nLoc[1] = glGetUniformLocation(renderingProgram, "boneNormals[1]");
nLoc[2] = glGetUniformLocation(renderingProgram, "boneNormals[2]");
vMat = glm::translate(glm::mat4(1.0f), glm::vec3(-cameraX, -cameraY, -cameraZ));
currentLightPos = glm::vec3(lightLoc.x, lightLoc.y, lightLoc.z);
amt += 0.5f;
rMat = glm::rotate(glm::mat4(1.0f), toRadians(amt), glm::vec3(0.0f, 0.0f, 1.0f));
currentLightPos = glm::vec3(rMat * glm::vec4(currentLightPos, 1.0f));
installLights(vMat);
// Now compute and apply new bone angles
timeNow += dir;
int angle = (timeNow / 3) % 50 - 25;
if (timeNow == 150)
dir = -1;
else if (timeNow < 0) {
timeNow = 0;
dir = 1;
}
skeleton.getNamedBone(1)->setRotation(glm::rotate(glm::mat4(1.0f), toRadians(angle), glm::vec3(0.0f, 0.0f, 1.0f)));
skeleton.getNamedBone(2)->setRotation(glm::rotate(glm::mat4(1.0f), toRadians(-angle), glm::vec3(0.0f, 0.0f, 1.0f)));
glm::mat4 bones[3];
glm::mat4 normals[3];
for(int n = 0;n < 3;n++) {
bones[n] = vMat * skeleton.getNamedBone(n)->getBoneMatrix();
glUniformMatrix4fv(mvLoc[n], 1, GL_FALSE, glm::value_ptr(bones[n]));
normals[n] = glm::transpose(glm::inverse(bones[n]));
glUniformMatrix4fv(nLoc[n], 1, GL_FALSE, glm::value_ptr(normals[n]));
}
glUniformMatrix4fv(projLoc, 1, GL_FALSE, glm::value_ptr(pMat));
glBindBuffer(GL_ARRAY_BUFFER, vbo[0]);
glVertexAttribPointer(0, 3, GL_FLOAT, GL_FALSE, 0, 0);
glEnableVertexAttribArray(0);
glBindBuffer(GL_ARRAY_BUFFER, vbo[1]);
glVertexAttribPointer(1, 3, GL_FLOAT, GL_FALSE, 0, 0);
glEnableVertexAttribArray(1);
glBindBuffer(GL_ARRAY_BUFFER, vbo[2]);
glVertexAttribIPointer(2, 3, GL_INT, 0, 0);
glEnableVertexAttribArray(2);
glBindBuffer(GL_ARRAY_BUFFER, vbo[3]);
glVertexAttribPointer(3, 3, GL_FLOAT, GL_FALSE, 0, 0);
glEnableVertexAttribArray(3);
glEnable(GL_CULL_FACE);
glFrontFace(GL_CCW);
glEnable(GL_DEPTH_TEST);
glDepthFunc(GL_LEQUAL);
glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, vbo[4]);
glDrawElements(GL_TRIANGLES, numCylinderIndices, GL_UNSIGNED_INT, 0);
}