CS184 AS9: Inverse Kinematics and Mesh Skinning

DUE DATE: Friday April 8, 11:00pm
You may work with a partner for this assignment.


In this assignment we pose and animate a mesh using a skeleton. You'll learn to use inverse kinematics and quaternion interpolation animate a skeleton, and linear blend skinning to animate a mesh attached to that skeleton.

Minimum Specifications

We will provide you with code to load and view a skeleton attached to a mesh. You will then accomplish the following:

  1. Inverse Kinematics: The provided code picks joints based on mouse position, and provides target positions for those joints. Implement an IK algorithm to hit those targets, so you can click and drag to reposition any joint. Let all joints be ball joints without joint limits -- in other words, permit any joint rotation about any axis by default. The IK algorithm should update joint orientations along the chain from that selected joint back to the root joint. (Whether you adjust the root orientation itself is up to you; it will probably be easier to pose the model if you don't.) We suggest one of these algorithms for IK:
    • Cyclic coordinate descent method: Starting from the selected joint and working back toward the root, greedily pick the orientation for that joint which gets you closest to the target at each joint. Repeat as needed/desired.
    • Jacobian transpose method: A cheap variant of the Jacobian psuedo-inverse method, which simply replaces the psuedo-inverse with a transpose. For each free parameter, find how changing that parameter moves your "end effector" joint. (Finite differences OR analytic derivatives are ok for this.) Then move the parameter proportionally to the dot product of that vector and (goal_position - current_position). Do this simultaneously for all parameters. Choose a scale for your parameter movement (a step size) such that you always make progress -- e.g., test that the movement would take you closer to the goal, and if it wouldn't then cut the step size in half and try again. Repeat as needed/desired.
  2. Animation creation: In the provided code, pressing 'a' saves the current pose as a "key frame" of animation in the animation class. Use this feature to create an animation with at least a few key frames. (No new code is required for this task.)
  3. Animation playback: In the provided code, pressing 'p' toggles a playback mode, which works like your as2 animation (x position of the mouse controls the time). You should fill in the Animation::setJoints() function to make the animation actually play back smoothly as the time (frame) variable is adjusted. You should use either slerp (slerp meaning spherical linear interpolation) or normalized lerp (lerp meaning linear interpolation -- see function nlerp in the quat class) to transition between key frames of animation.
  4. Mesh skinning: Position mesh vertices based on the mesh skeleton, using linear blend skinning. Note that the BoneWeight vector in each Vert includes weights and joint-local positions, and the Joint class has a local to world transformation function.

Extra Credit ideas:


To submit this project, all of the following needs to be done by the deadline: Windows Users: The grader should ONLY have to open your .sln file and press F5 to build and run your solution.
*Nix Users: The grader should ONLY have to run make with the appropriate makefile to build your project. Thus, for Mac and Linux make and for solaris gmake.

Note: The submit program retains the directory structure of what you send it. Thus, we recommend making a new directory for your assignment on the server, cd'ing into that directory, copying the whole framework with your code into this directory, and running submit as8 to easily submit the whole project to us.

Group submissions

For this project, groups of two are allowed. If you're working in a group, only one of you should submit the full project results; the other should only submit the README.txt file. Both of you should include your partner's name in the README.txt file.


See the Framework page here. Version 7 of the framework provides code to load a skeleton and its associated mesh.

Implementation Tips

Joint chain illustration

The Skeleton::getChain(joint id) function gives a vector of only the joints you need to get from the root to the given joint id. These are the joints you'll want to update when you do ik. Here are some notes on the joint information in that context:

Orientation of end = j0.orient*j1.orient*j2.orient = j2.l2w
To rotate j2 around j1, update j2.orient
Position of end (in world space) = j2.posn
Skeleton::getChain(j2) = [j2,j1,j0]
Un-rotated bone orientation: (0,1,0)
See Skeleton::updateChainFrames to update chain positions and l2w frames.

Cyclic Coordinate Descent notes

To implement CCD, you'll want to iteratively 'solve' one joint at a time.

To solve a joint i, you want to update the joint's orientation quaternion (orient) by composing (multiplying) it with an additional rotation such that the vector from the joint parent to end effector points in the same direction as the vector from parent to the goal. There's a function to find the quaternion that accomplishes this rotation in the quat class (note that it assume both vectors are nonzero).

But you need to ensure that rotation quaternion is computed in the correct local space so that it rotates orient as expected. You can do this by either first converting all positions to the local space of the joint (chain[i]->worldToLocal()) or by converting the quaternion to the local space of the joint after (chain[i]->l2w.conjugate() * theQuaternionToConvert * chain[i]->l2w). (Note quaternion conjugate() gives an inverse quaternion.)