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:
- 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.
- 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.)
- 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.
- 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:
- A copy of your code, including the whole framework, the compiles on the platform you developed on.
- A README.txt containing: Your name, SID, Login and a description of the platform your code compiles on.
- ONE image of your mesh posed like a
little teapot (one hand on hip, other arm out and bent to
mimick a spout).
- 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:
- A separate page for this assignment.
- 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.