Assignment 2: Hierarchical Modeling and SSD

Programming Assignment 2: Hierarchical Modeling and SSD
In this assignment, you will construct a hierarchical character model that can be interactively controlled
with a user interface. Hierarchical models may include humanoid characters (such as people, robots, or
aliens), animals (such as dogs, cats, or spiders), mechanical devices (watches, tricycles), and so on. You will
implement skeletal subspace deformation, a simple method for attaching a “skin” to a hierarchical skeleton
which naturally deforms when we manipulate the skeleton’s joint angles.
1. Getting Started
2. Summary of Requirements
3. Hierarchical Modeling
4. Skeletal Subspace Deformation
5. Extra Credit
6. Submission Instructions
1 Getting Started
The sample solution is included in the starter code under the sample solution folder.
• For Athena/Linux, the executable is sample solution/athena/a2.
• For Mac OS, the executable is sample solution/mac/a0.
• For Windows, the executable is sample solution/windows/a2.exe.
You may need to change the permissions to be able to run it (type chmod u+x sample solution/athena/a2
at the Athena prompt).
Download the starter code from Stellar, build the executable with cmake and make, and run the resulting
executable on one of the test models: (a2 data/Model1). A window will pop up. It will be mostly empty,
and will eventually contain a rendering of your character. Overlayed on top are a list of articulation variables
or simply joints. By manipulating one of the sliders, you will be able to change the pose of your characters.
You can change the camera view using mouse control just like in previous assignments: the left button
rotates, the middle button moves, and the right button zooms. You can press a to toggle drawing of the
coordinate axes.
The sample solution (See above for solution naming convention corresponding to your OS) shows a
completed version of the homework, including loading and displaying a skeleton, loading a mesh that is
bound to the skeleton, and deforming the skeleton and mesh based on joint angles. You can press a and s
to toggle drawing of the coordinate axes and skeleton, respectively.
1
2 Summary of Requirements
2.1 Hierarchical Model
For part one of this assignment, you are required to correctly load, display, and manipulate a hierarchical
skeleton. Your implementation must be able to correctly parse any of the provided skeleton files (*.skel),
construct a scene graph data structure, and use a matrix stack in conjunction with simple sphere and cylinder
primitives to render the skeleton. Finally, you will write the code to set join transforms based on joint angles
passed in from the user interface.
2.2 Skeletal Subspace Deformation
For the second part of this assignment, you will implement skeletal subspace deformation to attach a “skin”
to your skeleton. SSD will allow you to pose true characters, not just skeletons. This part first requires you
to adapt your assignment 0 code to parse a mesh without normals and generate them at display time. You
will also need to write yet another parser to load attachment weights, which specify, for each vertex, the
importance of each bone. Finally, you will implement the actual SSD algorithm which requires applying a
number of operations to your skeletal hierarchy.
2.3 Artifact
The artifact for this assignment will be very easy to create: simply take a screenshot of one of the character
models and submit it in PNG JPEG format. The starter code already has a button that lets you take
screenshots. Please take a few minutes to pose your character interestingly and choose a reasonable camera
position. A straightforward extension would be to load multiple characters and pose them interacting
together in an interesting way. You may also want to add a floor by drawing a flattened cube.
3 Hierarchical Modeling
In previous assignments, we addressed the task of generating static geometric models. As we’ve seen, this
approach works quite well for generating objects such as spheres, teapots, wineglasses, statues, and so on.
However, this approach is limited when applied to generating characters that need to be posed and animated. For instance, in a video game, a model of a human should be able to interact with the environment
realistically by moving its limbs to imitate walking or running.
One approach to creating these animations is to individually manipulate vertices and control points.
Doing so quickly becomes tedious. A better approach is to define a hierarchy such as a skeleton for a human
figure and few control parameters such as joint angles of the skeleton. By manipulating these parameters,
sometimes called articulation variables or joints, a user can pose the hierarchical shapes more easily. Furthermore, the surface of the object can also be computed as a function of the same articulation variables.
An example of a skeleton hierarchy for a human character is shown below.
2
Each node in the hierarchy is associated with a transformation, which defines its local coordinate frame
relative to its parent. These transformations will typically have translational and rotational components.
Typically, the rotational components are controlled by articulation variables given by the user. We can
determine the global coordinate frame of a node (that is, a coordinate system relative to the world) by
multiplying the local transformations down the tree.
The global coordinate frames of each node can be used to generate a character model by using them
to transform geometric models for each node. For instance, the torso of the character can be drawn in the
coordinate frame of the pelvis, and the thighs of the character can be drawn in the coordinate frame of the
hips. Make sure you understand what these global coordinate frames mean; in what space is the input? In
what space is the output?
In your code, your model will be drawn in this manner. By placing, say, a cylinder in the coordinate
frame of the left hip, you can draw a simple thigh for your character. Doing this for all nodes in the hierarchy
will result in simple stick figures, such as the ones shown below.
3.1 Matrix Stack (5% of grade)
Your first task is to implement a matrix stack. A matrix stack keeps track of the current transformation
(encoded in a matrix) that is applied to geometry when it is rendered. It is stored in a stack to allow you
to keep track of a hierarchy of coordinate frames that are defined relative to one another - e.g., the foot’s
coordinate frame is defined relative to the leg’s coordinate frame.
In your implementation, if no current transformation is applied to the stack, then it should return the
identity. Each matrix transformation pushed to the stack should be multiplied by the previous transformation. This puts you in the correct coordinate space with respect to its parent. The interface for the matrix
stack has been defined for you in MatrixStack.h. The implementation in MatrixStack.cpp is currently
empty and must be filled in. We recommend you simply use an std::vector for the stack, but you may use
any data structure you wish.
3
When rendering, you will be pushing and popping matrices onto and o↵ the stack. Before drawing an
object using the VertexRecorder class, or the drawSphere() and drawCylinder() functions, you must
update the transformation uniform variables. The camera class has a helper function for that:
void Camera::SetUniforms(GLuint program, Matrix4f M = Matrix4f::identity());
The starter code’s SkeletalModel class comes equipped with an instance of MatrixStack called m matrixStack.
To set the current stack for subsequent draw calls, call camera.SetUniforms(program, m matrixStack.top()).
To reset the model matrix to identity, call the method without second argument: camera.SetUniforms(program).
3.2 Hierarchical Skeletons (35% of grade)
3.2.1 File Input
Your next task is to parse a skeleton that has been pre-built for you. The starter code automatically calls
the method loadSkeleton with the right filename in SkeletalModel.cpp. The skeleton file format (.skel)
is very straightforward. It contains a number of lines of text, each with 4 fields separated by a space. The
first three fields are floating point numbers giving the joint’s translation relative to its parent joint. The
final field is the index of its parent (where a joint’s index is the zero-based order it occurs in the .skel file),
hence forming a directed acyclic graph (DAG). The root node contains !1 as its parent and its translation
is its global position in the world.
Each line of the .skel file refers to a joint, which you should load as a pointer to a new instance of the
Joint class. You can initialize a new joint by calling
Joint * joint = new Joint;
Because joint is a pointer, note that we must initialize it with the new keyword to allocate space in
memory for this object that will persist after the function ends. (If you try to create a pointer to a local
variable, the pointer will become invalid when the local variable goes out of scope, and attempting to access
it will cause a crash.) Also note that when dealing with a pointer to an object, you must access the member
variables of the object with the arrow operator - instead of . (e.g. joint-transform, which reflects the
fact that there is a memory lookup involved).
Your implementation of loadSkeleton must create a hierarchy of Joints, where each Joint maintains
a list of pointers to Joints that are its children. You must also populate a list of Joints m joints in the
SkeletalModel and set m rootJoint to point to the root Joint.
3.2.2 Drawing Stick Figures
To ensure that your skeleton was loaded correctly, we will draw simple stick figures like the ones above.
Joints We will first draw a sphere at each joint to see the general shape of the skeleton. The starter code
calls SkeletalModel::drawJoints. Your task is to create a recursive function that you should call from
drawJoints that traverses the joint hierarchy starting at the root and uses your matrix stack to draw a
sphere at each joint. We provide the helper function drawSphere( 0.025f, 12, 12 )) to draw a sphere
of reasonable size. Remember to update the transformation uniform variables using the camera class before
drawing.
Bones A stick figure without bones is not very interesting. In order to draw bones, we will draw cylinders
between each pair of joints in the method SkeletalModel::drawSkeleton. As with joints, it is up to you
to define a separate recursive function that will traverse the joint hierarchy. At each joint, you should draw
a cylinder between the joint and the joint’s parent (unless it is the root node).
4
When drawing a bone, you should first determine the length of the bone. This will allow you to draw a
cylinder of the correct length by calling drawCylinder(6, 0.02f, <length). A 6-sided cylinder with radius 0.02 should look good enough. Before calling the draw function, you must call Camera::SetUniforms()
with a model matrix that moves the cylinder to the position of the parent joint, and rotates it into the direction of the child joint. As with drawing the spheres to visualize the joints, you should verify the correctness
of your implementation with the sample solution.
3.3 User Interface (5% of grade)
Whenever a joint rotation slider is dragged, the application calls setJointTransform, passing in the index
of the joint to be updated and the Euler rotation angles set by the user. You should implement this function
to set rotation component of the joint’s transformation matrix appropriately.
4 Skeletal Subspace Deformation
Hierarchical skeletons allowed you to render and pose vaguely human-looking stick figures in 3D. In this
section, we will use Skeletal Subspace Deformation to attach a mesh that naturally deforms with the skeleton.
In the approach used to render the skeleton, body parts (spheres and cubes) were drawn in the coordinate
system of exactly one joint. This method, however, can generate some undesirable artifacts. Observe the
vertices near a joint.
This is a cross-sectional view of a skeleton with a mesh attached to each node. Notice how the two meshes
collide with each other as the skeleton bends. Our stick figures hide this artifact by drawing spheres at each
joint. However, it is only a quick fix for the fact that the aforementioned approach rigidly attaches vertices of
the character model to individual nodes of the hierarchy. This is an unrealistic assumption for more organic
characters (such as humans and animals) because skin is not rigidly attached to bones. It instead deforms
smoothly according to configuration of the bones, as shown below.
5
This result was achieved using skeletal subspace deformation, which positions individual vertices as a
weighted average of transformations associated with nearby nodes in the hierarchy. For example, a vertex
near the elbow of the model is positioned by averaging the transformations associated with the shoulder and
elbow joints. Vertices near the middle of the bone (far from a joint) are a↵ected by only one joint - they
move rigidly, as they did in the previous setup.
More generally, we can assign each vertex a set of attachment weights which describes how closely it
follows the movement of each joint. A vertex with a weight of one for a given joint will follow that joint
rigidly, as it did in the previous setup. A vertex with a weight of zero for a joint is completely una↵ected
by that joint. Vertices in between are blended - we compute their position as if they were rigidly attached
to each joint, then average these positions according to the weights we’ve assigned them.
In the previous section, a vertex was defined in the local coordinates of a given joint - you probably used
the drawCylinder() function, then transformed the entire object via a translation to the joint’s location.
Now, however, vertices don’t belong to a single joint, so we can’t define vertices in the local coordinate frame
of the joint they belong to. Instead, we define the mesh for the entire body, and keep track of the bind pose
- the pose of each joint in the body such that the bones match up with the locations of the vertices in the
mesh. Imagine taking the skin of a character, then fitting a skeleton inside that skin. The skeleton which
matches up with the skin’s position is in the character’s bind pose.
Let’s say that p is the position of a vertex in a character’s coordinate frame in the bind pose. Say that
p is a↵ected by joint 1 and joint 2. Let’s also say that the bind pose transformation of joint 1 (the transformation which takes us from the local coordinate frame of joint 1 before the character has been animated to
the character’s coordinate frame) is B1. Finally, the transformation from joint 1’s local coordinate frame to
the character’s coordinate frame after animation is T1. Then the position of our vertex after transformation,
if that vertex were rigidly attached to joint 1, would be T1B1!1p. Notice that we have to first transform
the point into the local coordinate system of the joint (B1!1p) before transforming it (remember, p is in the
character’s bind pose coordinate system). Similarly, the bind transformation of joint 2 is described by B2,
and T2 describes the transformation from the unanimated local coordinate frame of joint 2 to the animated
character coordinate frame. Then the vertex’s position, if it were rigidly attached to joint 2, would be
T2B2!1p. However, say that the given vertex is near the connection of two bones corresponding to joint 1 and
joint 2, and we want it to be attached to both joints. We assign each joint a weight according to how much
influence that joint should have on the vertex. Weights will usually range between 0 and 1 for each joint, and
the weights for all joints will usually sum to 1. We want it tied to joint 1 with a weight of w, so it is tied to
joint 2 with a weight of (1!w). Then we compute the final position of the vertex as wT1B1!1p+(1!w)T2B2!1p.
Note that since we usually only have one bind pose for a character, the inverse bind transformations
B!1
i need to be computed only once. On the other hand, since we want to animate the character using our
user interface, the animation transforms Ti need to be recomputed every time the joint angles change. This
implies that the vertex positions will also need to be updated whenever the skeleton changes. (Although
recomputing Ti is relatively cheap on a character with few joints, updating the entire mesh can be quite
expensive. Modern games typically perform SSD on many vertices in parallel using the graphics card’s vertex
shader. You can implement this for extra credit (see end of handout).
4.1 File Input: Bind Pose Mesh (5% of grade)
To get started, we will first need to adapt your code from assignment 0 to load the bind pose vertices from
an OBJ file. The starter code automatically calls Mesh::load with the appropriate filename. The only
di↵erence between this part and assignment 0 is that the meshes we provide for you do not include normals.
Instead, we will generate them on-the-fly when we render. Your code should populate the bindVertices
and faces fields of the mesh. Notice that our Mesh struct comes with two copies of vertices: the bind pose
6
and the current pose. We will render from the current pose vertices, which are generated by transformations
of the bind pose vertices. The starter code makes the initial copy for you.
4.2 Mesh Rendering (5% of grade)
Next, we will verify the correctness of your mesh loader by rendering the mesh. The starter code calls
Mesh::draw automatically with the right filename. Be sure to render from m mesh.currentVertices and
not m mesh.bindVertices.
Unlike meshes from previous assignments, these meshes do not provide any per-vertex normals since
they were not computed analytically. Instead, we will generate a single normal for each triangle on-the-fly
inside the rendering loop by taking the cross product of the edges. Don’t forget to normalize your normals.
Note how your model appears “faceted”: the lighting is discontinuous between neighboring faces because
the normals change abruptly.
4.3 File Input: Attachment Weights (5% of grade)
The last thing we must load are the attachment weights. The starter code calls Mesh::loadAttachments
automatically with the right filename. The attachment file format (.attach) is straightforward. It contains
a number of lines of text, one per vertex in your mesh. Each line contains as many fields as there are joints,
minus one, separated by spaces. Each field is a floating point number that indicates how strongly the vertex
is attached to the (i+ 1)-th joint. The weight for the 0th joint, the root, is assumed to be zero.
Your code should populate the attachments field of the mesh. We recommend the starter code’s data
structure, where m mesh.attachments is a vector< vector< float . The inner vector contains one
weight per joint, and the outer vector has size equal to the number of vertices.
4.4 Implementing SSD (40% of grade)
Finally, we will implement SSD as described above. We will first compute all the transformations necessary
for blending the weights and then use them to update the vertices of the mesh.
4.4.1 Computing Transforms
As we describe above, we must compute the bind pose world to joint transformations (once) and the animated
pose joint to world transformations (every time the skeleton is changed). The starter code automatically
calls computeBindWorldToJointTransforms and updateCurrentJointToWorldTransforms at the appropriate points in the code.
computeBindWorldtoJointTransforms should set the bindWorldToJointTransform matrix of each Joint.You
should use a recursive algorithm similar to the one you used for rendering the skeleton. Be careful with the
order of matrix multiplications. Think carefully about which space is the input and which space is the output.
updateCurrentJointToWorldTransforms is called whenever the skeleton changes. Your implementation
should update the currentJointToWorldTransform matrix of each Joint, and will be very similar to your
implementation of computeBindWorldtoJointTransforms. But once again, be careful about which spaces
you’re mapping between. One convenient method for debugging is that if your skeleton did not change
(i.e.,you did not touch any sliders), the bind world to joint transform for any Joint should be the inverse of
the current joint to world tranform.
7
4.4.2 Deforming the mesh
For the final part of your assignment, you will deform the mesh according to the skeleton and the attachment
weights. Since you’ve populated all the appropriate data structures, your implementation should be straightforward. The starter code calls SkeletalModel::updateMesh whenever the sliders change. Your code should
update the current position of each vertex in m mesh.currentVertices according to the current pose of the
skeleton by blending together transformations of your bind pose vertex positions in m mesh.bindVertices.
If you implemented SSD correctly, your solution should match the sample solution. Feel free to change
the appearance of your characters and extend your code to pose multiple characters together to make an
interesting scene.
5 Extra Credit
As with the previous assignment, the extra credits for this assignment will also be ranked easy, medium, and
hard. These categorizations are only meant as a rough guideline for how much they’ll be worth. The actual
value will depend on the quality of your implementation, e.g., a poorly-implemented medium may be worth
less than a well-implemented easy. We will make sure that you get the credit that you deserve.
5.1 Easy
• Generalize the code to handle multiple characters by storing multiple skeletons, meshes, and attachment
weights. Optionally, you can reuse data between instances of the same character.
• Employ OpenGL texture mapping to render parts of your model more interestingly. The OpenGL Red
Book covers this topic in Chapter 9, and it provides plenty of sample code which you are free to use.
• This assignment uses per-face normals which lead to a faceted appearance. For smoother shading,
compute per-vertex normals. You can do this by setting a vertex normal to the average normal of the
neighboring faces.
• Simulate the appearance of a shadow or reflection of your model on a floor using OpenGL. While
performing these operations in general is quite complicated, it is relatively easy when you are just
assuming that a plane is receiving the shadows. The OpenGL Red Book describes one way to do this
in Chapter 14.
• For your SSD implementation, use pseudo-colors to display your vertex weights. For example, assign
a color with a distinct hue to each joint, and color each vertex in the model according to the assigned
weights by computing the corresponding weighted average of joint colors.
• There are numerous other tricks that you might try to make your model look more interesting. Feel
free to implement extensions that are not listed here, and we’ll give you an appropriate amount of
extra credit.
5.2 Medium
• Implement SSD using the vertex shader. You should store the bind pose in a vertex bu↵er, and
define a set of uniform variables for the joint transformations. For each frame, upload the latest joint
transforms, and compute the transformed vertex positions and normals in the shader.
• Embed the control points of a generalized cylinder’s sweep curve in the character hierarchy. If you
have implemented SSD and your code from the previous assignment is modular, this should be quite
straightforward. This is an alternative way to provide smooth skins for body parts like arms and legs.
8
However, note that this technique is less general than SSD because it can only handles non-branching
hierarchies.
• Build your own model out of generalized cylinders and surfaces of revolution, and pose it using SSD.
• Implement intuitive manipulation of articulation variables through the model display. For instance, if
the elbow joint is active, the user should be able to click on the arm and drag it to set the angle (rather
than using the slider). For an example of such an interface, give Maya a try.
• Implement a method of animating your character by using interpolating splines to control articulation
variables. This method of animation is known as keyframing. You may either allow input from a text
file, or for additional credit, you may implement some sort of interface that allows users to interactively
modify the curves.
5.3 Hard
• Implement pose space deformation. This method is an alternative to skeletal subspace deformation
which often gives higher-quality results.
• Implement inverse kinematics, which solves for articulation variables given certain positional constraints. For instance, you can drag the model’s hand and the elbow will naturally extend. Your code
should allow interactive manipulation of your model through the drawing window.
• Implement mesh-based inverse kinematics, which allows a model to be posed without any underlying
skeleton.
6 Submission Instructions
As with the previous assignment, you are to write a README.{txt,pdf} that answers the following questions:
• How do you compile and run your code? Provide instructions for Athena Linux.
• Did you collaborate with anyone in the class? If so, let us know who you talked to and what sort of
help you gave or received.
• Were there any references (books, papers, websites, etc.) that you found particularly helpful for
completing your assignment? Please provide a list.
• Are there any known problems with your code? If so, please provide a list and, if possible, describe
what you think the cause is and how you might fix them if you had more time or motivation. This
is very important, as we’re much more likely to assign partial credit if you help us understand what’s
going on.
• Did you do any of the extra credit? If so, let us know how to use the additional features. If there was
a substantial amount of work involved, describe what how you did it.
• Got any comments about this assignment that you’d like to share?
Submit your assignment as a single archive (.tar.gz or .zip) on Stellar. It should contain:
• Your source code.
• A compiled executable named a2.
• Any additional files (OBJs, textures) that are necessary.
• The README file.
• Your artifact(s) in PNG or JPEG format.
9