CMSC 491/691: Computer Animation

Assignment 1
Interpolating Keyframes
Initial submission February 10, 2016
Due February 23, 2016

Before you start

You will be doing your work this semester in a class git repository. Before you get started on any of the assignments, you should fetch yourself a copy of your personal repository following these directions. Your personal class respoitory on the UMBC GL/Linux systems is /afs/umbc.edu/users/a/d/adamb/pub/491/your-user-name.git

To make sure you do not have last-minute problems, you must commit and push something to your repository by Wednesday, February 10th. This be anything from an update to the readme to the completed project.

The Assignment

For this assignment, you must write a C or C++ program that will interpolate keyframed positions and orientations. There are basically 4 exercises to the assignment: Catmull-Rom interpolation of positions, Catmull-Rom interpolation of quaternions that represent orientation, Gaussian quadrature of arc-length, and arc length parameterization of piecewise cubics. Your program will take a set of keyframed positions and orientations and will output interpolated (and key) frames. The interpolation will use cubic Catmull-Rom splines and between each pair of key-frames the interpolation will be re-parameterized to achieve constant velocity.

You can run my program here:

~adamb/public/Interpolate/interpolate input.keys output.keys

Input/Output

The input file will have the format

nkeys
t x y z qx qy qz w

t is an integer, the time of the frame.
x, y, z, give the 3D position.
qx, qy, qz give the imaginary parts of the quaternion that represents orientation.
w is the real part of the quaternion.

The output file has the same format.

More details

I wrote 6 functions, evalPoly, evalTangent, integrate, subdivide, maptime, and main. I also created a class for a keyframe that stores the position, orientation, and time. My program is less than 200 lines of code and took less than 4 hours to write. evalPoly evaluates the catmull-rom polynomial interpolant for both the position and orientation at an arbitrary time. evalTangent does the same thing for the tangent (first derivative of the position). integrate integrates the magnitude of the tangent over some interval (see the book). subdivide checks whether the current estimates are good and otherwise subdivides (see the book). maptime takes a frame number and maps it to an arc-length parameterized value. main is the main program and does i/o and calls the other functions.

Catmull-Rom Interpolation of Positions

I found this document (especially the last formula) helpful. I set tau to 0.5. For boundary conditions I used: if we assume the keys used in interpolation are k0, k1, k2, k3. If k0 would be outisde the input, k0 = k1. Similary if k3 is outside the interval k3=k2.

Catmull-Rom Interpolation of Quaternions

This is *not* way more complicated. Instead of interpolating quaternions using spherical linear interpolation (slerp) as in the book, simply use linear quaternian interpolation (qlerp). Apply the same interpolation weights as you did for positions to each component of the quaternion and re-normalize. See the paper for a proof that this is "good enough."

Gaussian Quadrature

I used the 10 point rule in the book.

  double x[5] = {.1488743389, .4333953941, .6794095682, .8650633666, .9739065285};
  double w[5] = {.2955242247, .2692667193, .2190863625, .1494513491, .0666713443};

I basically used the algorithm in the book, I started the subdivision with each pair of keframes (i.e. the interval was the time between to keyframes). I created a table that maps from frame indices to arclengths. This was pretty straightforward.

arc-length reparameterization

This was considerably harder, conceptually, than anything else. But, it is less than 20 lines, and the most important pieces are just three lines. The input is a frame number (and the keyframes and tabulated arc length integrals), the goal is, given a frame number, find an interpolation value that when passed to evalPoly will give constant velocity interpolation between this pair of keyframes. This might involve some algebra. Let f be the frame we wish to interpolate at. Let f0 and f1 be the keyframes such that f0 < f < f1. Let s0 and s1 be the arclengths at the keyframes (I recorded arclengths per interval so s0 was 0.0). Then the arclength that corresponds to f is

s0 + (s1-s0) * (f-f0) / (f1-f0)

Now let i be the entry in the arclength table such that s[i] < s < s[i+1]. Let u[i] and u[i+1] be the coorresponding parameter values. Then we want to return

u[i] + (u[i+1]-u[i]) * (s-s[i]) / (s[i+1]-s[i])

Extra Credit

Ease-in/Ease-out, details coming. Use any of the methods discussed in class or in the book to ease-in/ease-out for up to 10 extra points.

Other people's code

Feel free to use the code I provide and look at the code in the book (somewhat helpful). The only other things I found useful was the formula in the link above and the wikipedia page on Bezier curves that I looked at to derive the formulas for a and b above.

What to turn in

Turn in this assignment electronically by pushing your source code to your class git repository by 1:00 AM on the day of the deadline. Do your development in the proj1 directory so we can find it. Be sure the Makefile will build your project when we run 'make' (or edit it so it will). Also include a README.txt file telling us about your assignment. Do not forget to tell us what (if any) help did you receive from books, web sites or people other than the instructor and TA.

Check in along the way with useful checkin messages. We will be looking at your development process, so a complete and perfectly working ray tracer submitted in a single checkin one minute before the deadline will NOT get full credit. Do be sure to check in all of your source code, Makefile, README, and updated .gitignore file, but no build files, log files, generated images, zip files, libraries, or other non-code content.

To make sure you have the submission process working, you must do at least one commit and push by the friday before the deadline.