This chapter links to the course’s interactive demos and uses MathJax for its formulas. Read it through the course website (or download the file and open it in a browser); a Canvas inline preview will reach neither the demos nor the math. All chapters.

Animation and Interpolation: Keyframes, Easing, Rotations, Skinning, Simulation

Hunger (1974), animated with Burtnyk and Wein's computer keyframe interpolation at Canada's National Research Council, was nominated for an Academy Award. Burtnyk and Wein, Interactive Skeleton Techniques, CACM 1976; Academy Awards, 1975

Everything earlier in the text places, views, builds, dresses and lights a scene at one instant. Animation is the function from time to all of that: positions, orientations, joint angles, vertex positions. Nobody authors that function frame by frame. An animator sets a few keyframes and the computer interpolates, and the whole subject is the question of what to interpolate and how. Positions interpolate along a curve, and the choice between straight hops and a spline is worked on the keyframe demo’s three keys; the curve editor that animators use is a Bézier in time with one constraint worked to the failure that breaks it. Time itself is interpolated by an easing function. Rotations must not be interpolated as matrices or Euler angles, and the chapter shows what goes wrong (a shrinking matrix, a collapsed joint), works the quaternion slerp between two keys, and the squad that removes the corner between three. A skeleton is the scene-graph chain of the scene-graphs chapter driven by angles, solved forward and, for one two-link arm, inverse; its bind matrices are computed with the course library, and skinning attaches a mesh to it with the blend that produces the classic collapsing elbow. The last third is simulation: a spring stepped two ways to show why the order of two lines of code decides whether the motion stays bounded, a particle fountain, a mass-spring cloth with the step-size bound derived and measured, and a bounce.

1 · Keyframes and in-betweening

The keyframe demo has three keys, \(\mathbf{K}_0 = (-2.2, 0.5, 0)\), \(\mathbf{K}_1 = (0, 1.9, -0.6)\), \(\mathbf{K}_2 = (2.2, 0.7, 0)\), at times \(0, \tfrac12, 1\), and one parameter \(t\). Its two modes are the two simplest answers to the question of what lies between.

2 · The curve editor: keys with handles

A production animation curve is one scalar channel per animated number (the \(x\) of a position, one Euler angle, one blend weight) plotted against time, with a key at each keyframe and a pair of Bézier handles at each key. Between two keys the channel is the cubic Bézier curve of the curves chapter in the plane \((\text{time}, \text{value})\), with the key positions as \(\mathbf{P}_0, \mathbf{P}_3\) and the handles as \(\mathbf{P}_1, \mathbf{P}_2\).

Two special tangent modes matter. Flat tangents (handles horizontal) give the ease-in, ease-out of Section 3 at every key and are the default in most tools. Stepped keys hold the previous value until the next key, which is how a light switches or a visibility flag is animated, and how blocking passes are previewed before the in-betweens are smoothed. A channel evaluated by this root-find is expensive compared to a Hermite piece with a known parameter, so exporters bake channels to dense samples or to Hermite tangents before they reach a game engine.

3 · Timing: easing, and the animator’s principles

A path fixes where; a second function fixes when. Real things accelerate from rest and decelerate to a stop, and an object that starts at full speed looks pushed. An easing function \(s(t)\) maps normalized time to normalized progress, and the position at time \(t\) is the path evaluated at \(s(t)\): the same path, retimed. Disney’s animators named this principle slow in and slow out.

The CSS curve is a two-dimensional Bézier \((0,0), (0.42, 0), (0.58, 1), (1, 1)\) read as \(s\) against \(t\), which needs the root-find of Section 2 to evaluate at a given \(t\); it is one channel segment of the curve editor applied to time. Easing composes with everything else in the chapter: a rotation slerped at \(s(t)\), a joint angle keyed at \(s(t)\).

Slow in and slow out is one of twelve principles that Disney’s animators codified for drawn animation and that Lasseter (1987) carried over to computer animation. The ones that are geometry have formulas.

4 · Interpolating rotations: slerp and squad

Interpolating a rotation matrix entry by entry does not give a rotation. Halfway between the identity and \(R_y(90^\circ)\), entry by entry, is \(\tfrac12\bigl(I + R_y(90^\circ)\bigr)\), whose \(xz\) block is \(\begin{pmatrix} 0.5 & 0.5 \\ -0.5 & 0.5 \end{pmatrix}\): a rotation by \(45^\circ\) times a scale of \(0.707\), with determinant \(0.5\). An object interpolated that way shrinks by 29 % at the midpoint and recovers. Halfway between the identity and a \(180^\circ\) rotation the matrix is zero and the object vanishes. Interpolating Euler angles keeps the rotation valid but not the path: with three angles changing at once the object swings along a curve that depends on the axis order, and near gimbal lock it spins.

node -e "import('./lib/core/xform.js').then(x=>{
  const q=x.quatFromAxisAngle(0,1,0,30);
  console.log(q.map(c=>+c.toFixed(4)));})"

Games often use normalized lerp anyway, because it needs no trigonometry and its speed error is invisible over the small arcs between consecutive keyframes; slerp is the reference. Through several orientation keys, slerping each pair in turn has the same defect as the polyline of Section 1: the angular velocity jumps at every key. The fix is the quaternion analog of the Catmull–Rom spline.

5 · Interpolating transforms

A node’s local transform in the scene-graph chain is the TRS product of the affine chapter, and the rule for animating it follows from Section 4: never interpolate the matrix. Interpolate the three parts separately, translation and scale by a curve, rotation by slerp or squad, and rebuild \(T\,R\,S\) at each frame. An animation file (glTF, FBX) stores exactly those three channels per node, each with its own keyframes and interpolation mode (glTF offers step, linear, and cubic Hermite with explicit tangents, the export form of Section 2), and the matrix is never stored at all. A matrix that must be interpolated (from a tool that only exported matrices) is first decomposed into TRS, which is the read-back of the affine chapter and which fails, as noted there, if the matrix has shear.

The same rule applies to a camera: interpolate the eye position and the look-at target, or the eye and a quaternion, and rebuild the view matrix; and to a dolly, where the field of view is one more scalar channel. Everything that is a matrix is rebuilt from things that are not.

6 · Skeletons: forward and inverse kinematics

A character’s skeleton is a scene graph whose nodes are joints and whose local transforms are rotations about those joints; the arm of the scene-graph chapter, base, arm and hand, is a three-joint skeleton. Forward kinematics is the composite rule: set the joint angles, multiply down the chain, and the hand lands where it lands. Keyframing the angles and interpolating them with slerp is how most character animation is authored.

Inverse kinematics asks the other question: where must the joints be for the hand to reach a given point? For a chain of many joints the answer is not unique and is found numerically (cyclic coordinate descent, which rotates one joint at a time to point the end effector at the target and sweeps the chain repeatedly; or the Jacobian method, which linearizes the end-effector position in the joint angles and takes a pseudo-inverse step toward the target). For two links in a plane it is a triangle, and the law of cosines solves it.

Which solution an animator wants is a constraint the solver cannot know (a human elbow bends one way); real IK systems take a preferred bend direction, joint limits, and a pole target that fixes the plane of the elbow. IK is what keeps feet planted on uneven ground and hands on door handles while the rest of the body is keyframed.

7 · The bind pose and skinning

A skeleton moves; a mesh must follow it. The mesh is modeled once, in a bind pose (arms out, the T-pose), with the skeleton laid inside it; every bone’s world matrix in that pose is recorded, and thereafter each vertex is carried by the bones it is attached to. Attaching each vertex rigidly to one bone tears the mesh at every joint, so vertices near a joint are attached to several bones with weights, and their position is the blend of where each bone would carry them.

node -e "
import('./lib/core/xform.js').then(x=>{
const M_A=x.makeTRS(0,0,0,0,0,30,1,1,1), T_B=x.makeTRS(1,0,0,0,0,0,1,1,1);
const M_B=x.matMul(M_A,x.matMul(T_B,x.makeTRS(0,0,0,0,0,45,1,1,1)));
const K_B=x.matMul(M_B,x.invertTRS(T_B));          // the skinning matrix of bone B
const v=[1.5,0.1,0];
const vA=x.applyMat4(M_A,v).slice(0,3), vB=x.applyMat4(K_B,v).slice(0,3);
console.log('under A', vA.map(c=>+c.toFixed(3)));
console.log('under B', vB.map(c=>+c.toFixed(3)));
console.log('blend  ', vA.map((c,i)=>+(0.5*c+0.5*vB[i]).toFixed(3)));})"

under A [ 1.249, 0.837, 0 ]
under B [ 0.899, 1.009, 0 ]
blend   [ 1.074, 0.923, 0 ]

The fix is the fix of Section 4: blend rotations as rotations. Dual quaternion skinning (Kavan and others, 2007) represents each bone’s rigid transform as a dual quaternion, blends those, and normalizes; the joint keeps its volume and twists cleanly. Linear blending survives because it is cheaper and because a well-placed extra bone hides most of the damage. Facial animation uses a different mechanism, blend shapes: whole-mesh vertex offsets keyed by weights, which is the same weighted-sum formula applied to positions rather than matrices. Skinned normals need the inverse-transpose rule of the illumination chapter applied to the blended matrix, or they lean.

8 · Simulation: stepping a spring

Not everything is keyed. Cloth, hair, water, debris and ragdolls are simulated: a state, a force law, and a rule for advancing the state by one frame’s \(\Delta t\). The simplest case already shows the one decision that matters. A unit mass on a unit spring obeys \(x'' = -x\); from \(x = 1\) at rest the exact motion is \(x = \cos t\), forever.

Semi-implicit Euler is symplectic: it conserves a slightly perturbed energy exactly, so the oscillation neither grows nor decays over any number of steps, which is why every game physics engine uses it or its relative, Verlet integration. It is not unconditionally stable, and the next section works its limit. Stiffer systems need implicit methods (Baraff and Witkin, 1998, made cloth practical by solving a linear system per step so that any \(\Delta t\) is stable) or smaller steps; a frame’s \(\Delta t\) is usually split into several fixed substeps so the simulation does not depend on the frame rate.

9 · Particles and cloth

A particle system (Reeves, 1983) is many copies of the spring integrator with no spring: each particle has a position, a velocity, an age, and forces of gravity and drag; particles are emitted with random initial velocities, stepped, and killed when they die or leave the scene. Smoke, sparks, rain, fountains and the debris of an explosion are particle systems with a sprite or a small mesh drawn at each particle.

Connect the particles with springs and the system is a mass-spring cloth: a grid of masses with structural springs along the grid edges, shear springs across each cell, and bend springs skipping a vertex, each exerting \(\mathbf{f} = k_s(|\mathbf{d}| - L)\hat{\mathbf{d}} + k_d(\mathbf{v}_{\text{rel}}\cdot\hat{\mathbf{d}})\hat{\mathbf{d}}\) on its endpoints. Stiff springs are the whole difficulty.

10 · Collisions

A simulated object that reaches a surface must be stopped. Detection is the intersection problem of the ray-tracing chapter (a particle’s step is a short ray, tested against the scene, with a bounding-volume hierarchy for many objects); the response is two corrections.

Rigid bodies add rotation to this (the impulse acts at the contact point and changes angular velocity too), and resting contact, where a stack of boxes must neither jitter nor sink, is the hard part of every physics engine and is handled by solving all the contact constraints of a frame together. Cloth self-collision, where a fold must not pass through itself, is the corresponding hard part of cloth.

11 · Motion capture, retargeting, and blend trees

Keyframing a walk by hand is slow, and motion capture records one instead: markers on a performer, tracked by cameras at 120 or more frames per second, solved into joint angles on a skeleton that matches the performer. The result is a dense set of keys, one per frame, on every channel; it is edited by the same curve editor, usually after a filtering pass, and it must be retargeted to the character’s skeleton, whose bone lengths and proportions differ. Retargeting copies joint rotations, not positions (a longer thigh at the same angle reaches farther), and then uses inverse kinematics to repair the contacts that the copy breaks: feet that slide or sink because the character’s legs are shorter than the performer’s.

A game character does not play one clip; it blends several. A blend tree takes a set of clips (idle, walk, run) and a parameter (speed) and interpolates between the two nearest clips’ poses, joint by joint, with slerp on the rotations and a shared phase so that the feet of the walk and the run land together. Transitions between states (standing to walking, walking to jumping) cross-fade over a fraction of a second by the same blend with a time-varying weight. Every joint angle that reaches the skinning stage of Section 7 is, in a running game, the output of such a blend, and a layer of IK on top of it keeps the hands and feet where the world requires.

12 · Rigid bodies in an engine

A rigid body is a node of the scene graph (the scene-graphs chapter) whose transform is written by a physics engine instead of by an animator. Its state is a position, an orientation kept as a unit quaternion (the rotation chapter), a linear velocity and an angular velocity; its properties are a mass, the way that mass is spread through the body (its inertia), and a collider: a simple shape such as a box, a sphere, a capsule or a convex hull that stands in for the rendered mesh. Every fixed step the engine adds the forces, advances the velocities and positions as in Section 8, finds the contacts, and corrects the velocities so that nothing interpenetrates, then writes the result back into the node’s transform.

Finding contacts has two phases. The broad phase discards pairs that cannot touch by testing their bounding boxes, kept sorted along an axis or in a tree of boxes: the bounding-volume hierarchy of the ray-tracing chapter, asked which boxes overlap a box rather than which a ray enters. The narrow phase computes the contact points, the contact normal and the overlap depth for the pairs that remain, with exact tests for simple shapes. The response of Section 10 then acts at each contact point; applied off the center of mass it changes the angular velocity as well, which is why a box landing on a corner starts to spin. Baraff’s SIGGRAPH 1989 paper on non-penetrating rigid bodies treated resting contact, the case of a stack of boxes that must neither sink nor jitter, by solving for all the contact forces of a frame together; real-time engines approximate that with many solver iterations and by putting bodies that have stopped moving to sleep.

13 · Cloth in practice

Section 9 showed why stiff springs need tiny steps. Real-time cloth avoids the problem by replacing each spring with a distance constraint and moving the particles to satisfy it directly: predict where every particle would go under gravity and wind, push particles out of obstacles, project each link back toward its rest length, and read the velocities off the moves (position-based dynamics, and its stiffness-aware form XPBD). A constraint cloth cannot explode; too few substeps only make it stretchy. Many short substeps per frame beat many solver passes in one long step. Film uses the other answer of Section 9, implicit integration (Baraff and Witkin, SIGGRAPH 1998), which stays stable at large steps at the price of a linear solve.

14 · Hair and fur

A texture colors a surface; fur and hair stand off it. Kajiya and Kay (SIGGRAPH 1989, “Rendering Fur with Three Dimensional Textures”) filled a thin volume over the surface with texels, small 3D textures storing fur density, hair direction and a lighting frame, and ray traced a furry teddy bear through them. The real-time descendant (Lengyel, Praun, Finkelstein and Hoppe, I3D 2001) slices that volume into shells: copies of the surface pushed outward, each carrying an ordinary 2D texture that is opaque where a hair crosses its height, plus fins at the silhouette so the edge view does not show the layers (the texture-mapping chapter).

A hair has no single normal, so Kajiya and Kay lit it by its tangent: diffuse light is brightest when the light crosses the hair and vanishes along it, and the highlight is a band where the light and the eye make mirror angles with the strand. That is why fur glows at its edges. Hair that moves is simulated as strands, chains of particles joined by links and rooted on the scalp. A few thousand guide hairs are simulated and many more children are drawn between them; each step, gravity and wind move the particles, the links restore each hair’s length, and particles inside the head are pushed back out. Follow the leader (Müller, Kim and Chentanez, VRIPHYS 2012) restores length by moving each particle to exactly one link from its parent, root to tip, so the hair never stretches. Film simulates every strand: Merida in Pixar’s Brave (2012) has about 111,700 hairs in more than 1,500 curls, simulated with a solver the team built for her.

15 · Exercises