CS184 AS9: Inverse Kinematics and Mesh Skinning

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

Aim

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:

• Implement multiple IK algorithms: For example, do both the suggested methods and compare the results. Or try comparing J^T to the "proper" Jacobian pseudoinverse method.
• Add more functionality to the IK interface: For example, try adding the ability to freeze joints, or to do IK on chains that don't just start at the root. Or add the ability to specify orientation of the ik target, in addition to position.
• Add joint limits or penalties: Get the ik solver to detect and avoid some unnatural poses (for example, prevent the knees from bending the wrong way)
• Support more file formats: Try loading and using for example a Doom3 md5mesh file
• Add more robust animation support: A number of features could be added to the animation system. For example: animation saving/loading; the ability to animate root position; an interface to set the timing of keyframes, so it's not a constant-speed playthrough; the ability to delete key frames; etc.
• Better skinning: Try a skinning method like dual quaternion blending, which tries to avoid some of the artifacts of linear blend skinning.
• Make a procedural animation with your IK: for example make a character walk in a user-controlled direction by using IK to place the feet.
• Implement skinning on the GPU

Submission

To submit this project, all of the following needs to be done by the deadline:

• Submit using the submit as9 command on the INST machines:
  1. A copy of your code, including the whole framework, the compiles on the platform you developed on.
  2. A README.txt containing: Your name, SID, Login and a description of the platform your code compiles on.
  3. ONE image of your mesh posed like a little teapot (one hand on hip, other arm out and bent to mimick a spout).
  4. ONE animated GIF of your the animation you have created for your mesh. NOTE: please try to keep the animation short and try to make the file at least under 10 mb. If needed/wanted, you can shrink the size of the gif with imagemagick by using, for example:
     convert file.gif -resize XX% halffile.gif (where XX is whatever percent you want)
• Put on your class instructional website:
  1. A separate page for this assignment.
  2. On this page, the images you are turning in.

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.

Framework

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

Implementation Tips

• Much of your code will likely go in the following functions: Skeleton::inverseKinematics, Skeleton::updateSkin and Animation::setJoints
• Pay careful attention to how the Joints are defined: each joint has an "orient" variable which specifies how the bone connecting it to its parent was rotated to get from its parent frame to itself.
• There are some useful functions in the new quaternion class "quat," which was added to algebra3.h. Like a function to generate a rotation from one direction to another, and a normalized lerp function, etc. Note that angles for quat::axisAngle and quat::angle are in radians.
• Each orientation is represented by two identical quaternions, q and -q. When interpolating quaternions, people usually take care to interpolate to the closest of these two quaternions, to avoid adding extra rotation to their animation. You can use the quat::getNearest function to get the closest quaternion.
  For a smarter algorithm and a more detailed explanation of this concept, you may want to watch this video on quaternion double cover.
• Remember that quaternions must be normalized to represent rotations. So for example if you perturb the quaternion to compute the Jacobian, normalize it before using it! You'll probably want to re-normalize during IK in general for either method, to avoid stability issues.
• For notes on the Jacobian methods of IK, see Niels Joubert's IK notes. He explains the psuedo-inverse method; the transpose method is identical except it uses the transpose instead of the pseudo-inverse.
• lerp is short for "linear interpolation"

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.)

Errata

• The quat::angle() function is incorrect; it should say 2*acos(a) instead of using atan2. It and quat::axis() have been removed from the latest version of the framework.