25. Advanced Character Animation

Chapter 13 built a character: a skeleton of joints, forward and inverse kinematics, a skin attached with linear blend skinning, blend shapes for the face, and motion capture to feed it.
Chapter 14 made it run in a game: clips blended and cross-faded, state machines, blend trees, ragdolls and crowds.
This chapter opens those boxes.

We'll start with the skin.
Chapter 13 showed that linear blend skinning makes elbows thin and twisted wrists collapse, and promised the fix: dual quaternion skinning, which we'll derive and compute here, together with the corrective shapes and smoothing deformers that clean up what is left.
Then we'll go deeper into blending: blend spaces with worked weights, additive and layered animation, root motion, and inertialization, a cheaper and better transition than the cross-fade.
Next comes motion matching, the technique that replaced hand-built state machines in many recent games, with a worked search.
Then full-body inverse kinematics: FABRIK, the Jacobian methods with a worked step, joint limits, feet on uneven ground, heads that look at things, and physically powered ragdolls.
We finish with faces solved from performance capture, crowds, and how animation data is compressed.

All of this is beyond the exam syllabus, but it grows directly out of two syllabus items of area 5, character animation (キャラクタのアニメーション) and real-time animation (リアルタイムアニメーション), and the exam points near the end of section 25.6 tie it back to them.
The math is the quaternion algebra of Linear Algebra chapter 13 and the transformation matrices of this series' chapters 4 and 5; I'll link back instead of re-teaching them.

25.1 Skinning matrices, worked in full

The chain of matrices

Recall the formula of linear blend skinning (LBS, リニアブレンドスキニング) from chapter 13, section 13.8:

𝐯′=∑jwj𝐒j𝐯,𝐒j=𝐖j𝐁j−1,∑jwj=1

Three matrices meet in it, and each comes from a different place:

  • 𝐁j, the bone's world matrix in the bind pose (バインドポーズ), the pose the mesh was modeled in. It never changes, so the engine stores its inverse, the inverse bind matrix (逆バインド行列), in the model file (glTF calls the array inverseBindMatrices).
  • 𝐖j, the bone's world matrix in the current pose, computed every frame by forward kinematics from the animated local transforms: 𝐖j=𝐖parent(j)𝐋j.
  • 𝐒j, the skinning matrix, the product of the two: "undo where the bone was when the mesh was modeled, then do where the bone is now".

Why the inverse bind matrix?
A vertex is stored in model space, not relative to any bone.
If we applied 𝐖j alone, a vertex near the elbow would be moved by the elbow's whole offset from the origin a second time.
𝐁j−1 first expresses the vertex in the bone's own frame, and 𝐖j carries that frame to its new place.
A useful check follows immediately: in the bind pose 𝐖j=𝐁j, so every 𝐒j=𝐈 and the mesh stays exactly where it was modeled, whatever the weights are.

Worked example

Take the two-bone arm of chapter 13 in 2D, with the homogeneous 3 × 3 matrices of chapter 4.
Bone 0 starts at the origin, bone 1 at (2,0), so 𝐁0=𝐈 and 𝐁1=𝐓(2,0).
This time both joints move: the shoulder turns by 30° and the elbow by 90° relative to the upper arm:

𝐖0=𝐑(30°),𝐖1=𝐖0𝐓(2,0)𝐑(90°)

The skinning matrices are 𝐒0=𝐑(30°) and 𝐒1=𝐑(30°)𝐓(2,0)𝐑(90°)𝐓(−2,0).
Read 𝐒1 right to left: move the elbow to the origin, turn by 90°, move it back, then turn the whole arm by 30° about the shoulder.
Multiplied out,

𝐓(2,0)𝐑(90°)𝐓(−2,0)=[0−1210−2001],𝐒1=[−0.5−0.8662.7320.866−0.5−0.732001]

Now skin the vertex on the outside of the elbow, 𝐯=(2,−0.5), with the weights 0.5 and 0.5:

  • 𝐒0𝐯=(2cos30°+0.5sin30°,2sin30°−0.5cos30°)=(1.982,0.567);
  • 𝐒1𝐯=(−0.5⋅2+0.866⋅0.5+2.732,0.866⋅2+0.5⋅0.5−0.732)=(2.165,1.250);
  • blended: 0.5(1.982,0.567)+0.5(2.165,1.250)=(2.074,0.909).

The elbow is now at 𝐖0(2,0)=(1.732,1.0), and the vertex is 0.3422+0.0922=0.354 from it: the same thinning to 0.354 as in chapter 13, because turning the whole arm doesn't change the shape of the bend.

Why the skin shrinks: the blended matrix

Since the blend is linear, we can blend the matrices first and apply the result once:

𝐌=0.5𝐒0+0.5𝐒1=[0.183−0.6831.3660.6830.183−0.366001]

Its upper-left 2 × 2 part has the determinant 0.1832+0.6832=0.5, and it is 0.707𝐑(75°): a rotation by 75°, halfway between 30° and 120°, times a uniform scale of 0.707.
That's a general identity worth remembering:

12(𝐑(α)+𝐑(β))=cosβ−α2𝐑(α+β2)

The average of two rotations points the right way but shrinks by the cosine of half the angle between them: 0.707 at 90°, 0 at 180°.
It's the matrix lerp of chapter 13, section 13.4 again, now hidden inside every skinned vertex near a joint.
So LBS isn't wrong because of the weights; it's wrong because a weighted sum of rigid transforms is not a rigid transform.

In practice

The skinning matrices of a rigid skeleton have the bottom row (0,0,0,1), so the matrix palette is usually uploaded as 3 × 4 matrices: 12 floats per joint instead of 16.
Normals use the blended 3 × 3 parts, which is exact only without scaling; a scaled bone needs the inverse transpose of chapter 5, section 5.4.

25.2 Dual quaternion skinning

The fix for the shrinking is to blend something that stays rigid.
For rotations alone we already know the answer: blend unit quaternions and normalize (nlerp), and the result is always a rotation (Linear Algebra chapter 13, section 13.6).
But a bone turns about its own joint, not about the origin, so its rotation and translation belong together; blending them separately rotates about the wrong center.
Dual quaternions (デュアルクォータニオン, 双対四元数) put rotation and translation into one object that can be blended and normalized like a quaternion.
Kavan, Collins, Žára and O'Sullivan introduced dual quaternion skinning (DQS, デュアルクォータニオンスキニング) in "Skinning with Dual Quaternions" (I3D 2007) and analyzed it fully in "Geometric Skinning with Approximate Dual Quaternion Blending" (ACM Transactions on Graphics, 2008).

Dual numbers

A dual number (双対数) is a+εb, where ε is a new symbol with the single rule

ε2=0,ε≠0

That's all; compare complex numbers, where i2=−1.
Multiplying two dual numbers, the ε2 term simply drops out:

(a+εb)(c+εd)=ac+ε(ad+bc)

For example (2+3ε)(4+5ε)=8+ε(10+12)=8+22ε.

Dual quaternions and rigid transforms

A dual quaternion is the same idea with quaternions as the parts:

q^=qr+εqd

qr is the real part and qd the dual part, each an ordinary quaternion (w,x,y,z); that's 8 numbers.
Products follow the dual number rule with the Hamilton product of Linear Algebra chapter 13:

q^1q^2=qr1qr2+ε(qr1qd2+qd1qr2)

A rigid transform "rotate by the unit quaternion qr, then translate by 𝐭" is the unit dual quaternion

q^=qr+ε12tqr,t=(0,𝐭) (a pure quaternion)

and its product with another unit dual quaternion is the composition of the two transforms, exactly like multiplying matrices.
To apply it to a point 𝐩, we rotate with the real part and read the translation back from the dual part:

𝐩′=qr𝐩qr∗+𝐭,𝐭=vector part of 2qdqr∗

(since 2qdqr∗=tqrqr∗=t for a unit qr).

Blending: dual quaternion linear blending

DQS replaces the blended matrix of LBS by a blended dual quaternion, dual quaternion linear blending (DLB):

b^=∑jwjsjq^j,c^=b^‖br‖

  • The weights are the same skin weights as for LBS; nothing in the rig changes.
  • sj=±1 picks the sign: q and −q are the same rotation (the double cover, Linear Algebra section 13.5), and we take the sign for which qrj⋅qr0≥0, so that all bones of a vertex blend "the short way round", as slerp does.
  • Both parts are divided by the length of the blended real part. Then cr is a unit quaternion, a pure rotation, and the vector part of 2cdcr∗ is a translation: whatever the weights, the vertex is moved by a rigid transform. (A tiny leftover in the scalar part of 2cdcr∗ is simply ignored.)

Worked example: the bent elbow

Same bend as in chapter 13: bone 1 turns by 90° about z around the elbow 𝐜=(2,0,0), bone 0 stays, and the vertex 𝐯=(2,−0.5,0) has the weights 0.5 and 0.5.

Bone 1 as a dual quaternion. The rotation is qr1=(cos45°,0,0,sin45°)=(0.7071,0,0,0.7071).
A rotation about the point 𝐜 is "rotate about the origin, then translate by 𝐭=𝐜−R𝐜": R(2,0,0)=(0,2,0), so 𝐭1=(2,−2,0).
The dual part is 12(0,2,−2,0)(0.7071,0,0,0.7071).
For two quaternions (a,𝐀)(b,𝐁)=(ab−𝐀⋅𝐁,a𝐁+b𝐀+𝐀×𝐁); here 𝐀⋅𝐁=0 and

0.7071(2,−2,0)+(2,−2,0)×(0,0,0.7071)=(1.4142,−1.4142,0)+(−1.4142,−1.4142,0)=(0,−2.8284,0)

so qd1=12(0,0,−2.8284,0)=(0,0,−1.4142,0).
Bone 0 is the identity, qr0=(1,0,0,0) and qd0=0.

Blend. qr0⋅qr1=0.7071≥0, so no sign flip.

br=0.5(1,0,0,0)+0.5(0.7071,0,0,0.7071)=(0.8536,0,0,0.3536),bd=(0,0,−0.7071,0)
‖br‖=0.85362+0.35362=0.8536=0.9239
cr=(0.9239,0,0,0.3827)=(cos22.5°,0,0,sin22.5°),cd=(0,0,−0.7654,0)

The real part is a rotation by 45°, exactly half of the bend.

Translation. Write cr=(w,𝐕) and cd=(e,𝐄). The vector part of 2cdcr∗ works out to 2(w𝐄−e𝐕+𝐕×𝐄).
With w=0.9239, 𝐄=(0,−0.7654,0), e=0 and 𝐕=(0,0,0.3827):

𝐭=2((0,−0.7071,0)+(0.2929,0,0))=(0.5858,−1.4142,0)

And that is 𝐜−R(45°)𝐜=(2−1.4142,0−1.4142,0): the blended transform is a rotation by 45° about the elbow.

The vertex. R(45°)(2,−0.5)=(1.7678,1.0607), plus 𝐭, gives (2.3536,−0.3536), at the distance 0.35362+0.35362=0.5 from the elbow.
LBS put it at (2.25,−0.25), 0.354 from the elbow; DQS keeps the full radius of the tube.

Left: a tube bent by 90 degrees with linear blend skinning, the outside vertex at 2.25, -0.25, 0.354 from the joint. Right: the same bend with dual quaternion skinning, the vertex at 2.354, -0.354, 0.5 from the joint, and a small bulge of 0.044 beyond the straight surface just before the joint; the dotted circle has radius 0.5 around the joint

Worked example: twisting, and the flip

Now the candy wrapper of chapter 13: bone 1 twists by φ about the x axis (the bone's own axis), and we follow the vertex (2,0,0.5) on the ring at the joint, weights 0.5 and 0.5.
The twist axis passes through the origin, so there is no translation, and qr1=(cosφ2,sinφ2,0,0).

  • φ=90°: br=(0.8536,0.3536,0,0), normalized (0.9239,0.3827,0,0), a twist of 45°. The vertex goes to (2,−0.3536,0.3536), radius 0.5. LBS: radius 0.5cos45°=0.354.
  • φ=170°: qr1=(0.0872,0.9962,0,0), dot with qr0 positive; the blend is a twist of 85°, radius 0.5. LBS: 0.5cos85°=0.044, nearly collapsed.
  • φ=190°: qr1=(−0.0872,0.9962,0,0), and now the dot product is negative, so −qr1=(0.0872,−0.9962,0,0) is used: the same rotation, described as a twist of −170°. The blend is a twist of −85°.

The radius is always 0.5: no candy wrapper.
But between 170° and 190° the ring at the joint jumps from +85° to −85°, a sudden turn of 170° for a smooth 20° change of the bone.
That's the flipping artifact Kavan and colleagues describe: DQS always blends the short way round, and at 180° the short way switches sides (at exactly 180° the dot product is 0 and rounding decides).
LBS has its own version: its ring passes through radius 0 at 180°.
Real rigs avoid such large twists on one joint anyway, with twist bones that share the rotation.

Left: radius of the ring at the joint against the twist of bone 1; DQS stays at 0.5, LBS follows 0.5 times the absolute cosine of half the twist, 0.354 at 90 degrees and 0.044 at 190 degrees. Right: the twist of the ring with DQS, half the bone&

Bulging

In the bent tube, vertices a little before the joint have a small weight on bone 1 and are turned by a small angle about the elbow, which swings them outward.
With the weights of chapter 13 (fading from 0 at x=1.5 to 1 at x=2.5), the outside sticks out to y=−0.544, 0.044 beyond the upper arm's surface at y=−0.5: a bulge (膨らみ) of about 9 % of the radius, where LBS collapses inward.
It is usually accepted or fixed with a corrective shape (section 25.3); some DCC tools also blend LBS and DQS per vertex (Maya's skin cluster, for example, offers "Classic Linear", "Dual Quaternion" and a weight-blended mix).

In code

Here are DLB and the two worked examples in C++, with Quat, rotate and conjugate from the Linear Algebra series' linalg.hh:

#include <cmath>
#include <cstdio>
#include <initializer_list>
#include "linalg.hh"

// Unit dual quaternion: real = rotation, dual = 0.5 * translation * rotation.
struct DualQuat {
  Quat real, dual;
};

Quat scaled(Quat q, float s) { return {s * q.w, s * q.x, s * q.y, s * q.z}; }
Quat added(Quat a, Quat b) { return {a.w + b.w, a.x + b.x, a.y + b.y, a.z + b.z}; }
float dot(Quat a, Quat b) { return a.w * b.w + a.x * b.x + a.y * b.y + a.z * b.z; }

// Rigid transform "rotate by r, then translate by t" as a dual quaternion.
DualQuat fromRigid(Quat r, Vec3 t) {
  return {r, scaled(Quat{0.0f, t.x, t.y, t.z} * r, 0.5f)};
}

// Apply a unit dual quaternion to a point: p' = r p r* + t, t = vector part of 2 * dual * real*.
Vec3 transformPoint(const DualQuat &q, Vec3 p) {
  Quat t = q.dual * conjugate(q.real);
  return rotate(q.real, p) + Vec3{2.0f * t.x, 2.0f * t.y, 2.0f * t.z};
}

// Dual quaternion linear blending (DLB): weighted sum on the short side of bone 0, then normalize.
DualQuat blend(const DualQuat *dq, const float *w, int n) {
  DualQuat b{{0, 0, 0, 0}, {0, 0, 0, 0}};
  for (int i = 0; i < n; ++i) {
    float s = dot(dq[i].real, dq[0].real) < 0.0f ? -w[i] : w[i]; // q and -q are the same rotation
    b.real = added(b.real, scaled(dq[i].real, s));
    b.dual = added(b.dual, scaled(dq[i].dual, s));
  }
  float len = std::sqrt(dot(b.real, b.real));
  return {scaled(b.real, 1.0f / len), scaled(b.dual, 1.0f / len)};
}

// Rotation by angle about axis through the point c, as rotation + translation.
DualQuat rotationAbout(Vec3 axis, float angle, Vec3 c) {
  Quat r = Quat::fromAxisAngle(axis, angle);
  return fromRigid(r, c - rotate(r, c));
}

int main() {
  const float deg = 3.14159265f / 180.0f;
  const float w[2] = {0.5f, 0.5f};
  Vec3 elbow{2, 0, 0};

  // Bend: bone 1 turns 90 degrees about z at the elbow; vertex on the outside of the elbow.
  DualQuat bend[2] = {fromRigid(Quat{}, {0, 0, 0}), rotationAbout({0, 0, 1}, 90 * deg, elbow)};
  Vec3 v{2, -0.5f, 0};
  Vec3 lbs = 0.5f * v + 0.5f * transformPoint(bend[1], v);
  Vec3 dqs = transformPoint(blend(bend, w, 2), v);
  printf("bend  LBS (%.4f, %.4f) r = %.4f\n", lbs.x, lbs.y, distance(lbs, elbow));
  printf("bend  DQS (%.4f, %.4f) r = %.4f\n", dqs.x, dqs.y, distance(dqs, elbow));

  // Twist: bone 1 twists about x by 90, 170 and 190 degrees; vertex on the ring at the joint.
  Vec3 u{2, 0, 0.5f};
  for (float phi : {90.0f, 170.0f, 190.0f}) {
    DualQuat twist[2] = {fromRigid(Quat{}, {0, 0, 0}), rotationAbout({1, 0, 0}, phi * deg, elbow)};
    Vec3 l = 0.5f * u + 0.5f * transformPoint(twist[1], u);
    DualQuat b = blend(twist, w, 2);
    Vec3 d = transformPoint(b, u);
    float ringTwist = 2.0f * std::atan2(b.real.x, b.real.w) / deg;
    printf("twist %3.0f: LBS r = %.4f, DQS r = %.4f, DQS ring twist %.1f deg\n", phi,
           std::hypot(l.y, l.z), std::hypot(d.y, d.z), ringTwist);
  }
  return 0;
}

bend  LBS (2.2500, -0.2500) r = 0.3536
bend  DQS (2.3536, -0.3536) r = 0.5000
twist  90: LBS r = 0.3536, DQS r = 0.5000, DQS ring twist 45.0 deg
twist 170: LBS r = 0.0436, DQS r = 0.5000, DQS ring twist 85.0 deg
twist 190: LBS r = 0.0436, DQS r = 0.5000, DQS ring twist -85.0 deg

On the GPU

The engine uploads two float4 per joint instead of a 3 × 4 matrix: 8 floats instead of 12.
In the vertex shader, the rotation of a point by a unit quaternion (𝐮,w) is written without building a matrix, as 𝐩+2𝐮×(𝐮×𝐩+w𝐩).
The quaternions are stored as (x,y,z,w) here, with w in the fourth component, the order glTF uses too:

struct DualQuatPalette {
  float4 real[64]; // rotation (x, y, z, w) of every joint
  float4 dual[64]; // dual part (x, y, z, w) of every joint
};
ConstantBuffer<DualQuatPalette> dqPalette;

// Dual quaternion skinning of one position with four joint indices and weights (summing to 1).
float3 skinPositionDQ(float3 position, uint4 joints, float4 weights) {
  float4 r0 = dqPalette.real[joints.x];
  float4 br = float4(0.0, 0.0, 0.0, 0.0);
  float4 bd = float4(0.0, 0.0, 0.0, 0.0);
  for (int k = 0; k < 4; ++k) {
    float4 r = dqPalette.real[joints[k]];
    float w = dot(r, r0) < 0.0 ? -weights[k] : weights[k]; // blend the short way round
    br += w * r;
    bd += w * dqPalette.dual[joints[k]];
  }
  float len = length(br);
  br /= len;
  bd /= len;
  float3 p = position + 2.0 * cross(br.xyz, cross(br.xyz, position) + br.w * position);
  float3 t = 2.0 * (br.w * bd.xyz - bd.w * br.xyz + cross(br.xyz, bd.xyz));
  return p + t;
}
layout(set = 0, binding = 1) uniform DualQuatPalette {
  vec4 dqReal[64]; // rotation (x, y, z, w) of every joint
  vec4 dqDual[64]; // dual part (x, y, z, w) of every joint
};

// Dual quaternion skinning of one position with four joint indices and weights (summing to 1).
vec3 skinPositionDQ(vec3 position, uvec4 joints, vec4 weights) {
  vec4 r0 = dqReal[joints.x];
  vec4 br = vec4(0.0);
  vec4 bd = vec4(0.0);
  for (int k = 0; k < 4; ++k) {
    vec4 r = dqReal[joints[k]];
    float w = dot(r, r0) < 0.0 ? -weights[k] : weights[k]; // blend the short way round
    br += w * r;
    bd += w * dqDual[joints[k]];
  }
  float len = length(br);
  br /= len;
  bd /= len;
  vec3 p = position + 2.0 * cross(br.xyz, cross(br.xyz, position) + br.w * position);
  vec3 t = 2.0 * (br.w * bd.xyz - bd.w * br.xyz + cross(br.xyz, bd.xyz));
  return p + t;
}
struct DualQuatPalette {
  float4 real[64]; // rotation (x, y, z, w) of every joint
  float4 dual[64]; // dual part (x, y, z, w) of every joint
};
ConstantBuffer<DualQuatPalette> dqPalette;

// Dual quaternion skinning of one position with four joint indices and weights (summing to 1).
float3 skinPositionDQ(float3 position, uint4 joints, float4 weights) {
  float4 r0 = dqPalette.real[joints.x];
  float4 br = float4(0.0, 0.0, 0.0, 0.0);
  float4 bd = float4(0.0, 0.0, 0.0, 0.0);
  for (int k = 0; k < 4; ++k) {
    float4 r = dqPalette.real[joints[k]];
    float w = dot(r, r0) < 0.0 ? -weights[k] : weights[k]; // blend the short way round
    br += w * r;
    bd += w * dqPalette.dual[joints[k]];
  }
  float len = length(br);
  br /= len;
  bd /= len;
  float3 p = position + 2.0 * cross(br.xyz, cross(br.xyz, position) + br.w * position);
  float3 t = 2.0 * (br.w * bd.xyz - bd.w * br.xyz + cross(br.xyz, bd.xyz));
  return p + t;
}

Normals are rotated by the blended real part alone.
Kavan and colleagues report that DQS costs only a few more shader instructions than LBS.
Its limitation is in the name: a dual quaternion can only describe rotation and translation, so bones that scale (a cartoon squash, a bulging muscle) need extra work, for example applying the scale in a separate pass before the dual quaternion blend.

25.3 Corrective shapes, pose-space deformation and delta mush

No skinning formula knows anatomy (creases inside an elbow, a bunching shoulder, a kneecap), so film and high-end game rigs add shapes on top.

Pose-driven corrective blend shapes

A corrective blend shape (補正ブレンドシェイプ) is a blend shape (chapter 13, section 13.5) whose weight is not animated by hand but driven by the pose, typically by a joint angle:

w(θ)=clamp(θ−θ0θ1−θ0,0,1)

The deltas are added before skinning, in the bind pose, so the skinning carries them along with the bones:

𝐯′=∑jwj𝐒j(𝐯+∑kwk(𝜽)𝐝k)

Added after skinning, a delta modeled for the arm pointing sideways would point the wrong way as soon as the arm moves.

Worked example. At the 90° bend of section 25.2, LBS put the outside vertex at (2.25,−0.25), and the artist wants it on the round elbow at (2.3536,−0.3536) (where DQS put it).
For this vertex LBS applies the blended matrix with the linear part 𝐀=[0.5−0.50.50.5], so a bind-space delta 𝐝 moves the result by 𝐀𝐝.
We need 𝐀𝐝=(2.3536−2.25,−0.3536+0.25)=(0.1036,−0.1036), and

𝐝=𝐀−1(0.1036,−0.1036)=[11−11][0.1036−0.1036]=(0,−0.2071)

In the bind pose the corrective pushes the vertex 0.2071 further outward (down, away from the bone), and the shrinking blend brings it back to the right radius.
With the driver θ0=30°, θ1=90°, the shape is off below 30°, at weight 0.5 at 60°, and full at 90°.
In production the delta is sculpted, not solved: the artist poses the arm at 90°, sculpts the elbow until it looks right, and the tool computes the bind-space delta exactly like this, per vertex (an "inverted" or "pre-skinning" corrective).

Pose-space deformation

An angle driver works for a hinge, but a shoulder's correctives depend on three rotation axes at once.
Pose-space deformation (PSD, ポーズスペースデフォメーション; Lewis, Cordner and Fong, SIGGRAPH 2000) treats correctives as scattered data interpolation in the space of poses: the artist sculpts corrections at a few example poses, and between them the correction is interpolated with radial basis functions (RBF, 放射基底関数).
An RBF interpolant is a sum of bumps centered on the examples,

f(𝜽)=∑iaiϕ(‖𝜽−𝜽i‖),ϕ(r)=e−(r/σ)2

with the coefficients ai chosen so that f passes exactly through the example values: one linear equation per example.

Worked example with one angle and two examples: the rest pose θ=0° (corrective weight 0) and the sculpted pose θ=90° (weight 1), with σ=60°.
The bump between the two examples is ϕ(90°)=e−2.25=0.1054, so

[10.10540.10541][a0a1]=[01]⇒a1=11−0.10542=1.0112,a0=−0.1054a1=−0.1066

At 45° both bumps are e−0.5625=0.5698: f=0.5698(−0.1066+1.0112)=0.515.
At 120°: f=−0.1066e−4+1.0112e−0.25=−0.0020+0.7875=0.786.

The corrective weight against the elbow angle: a linear driver from 30 to 90 degrees, and the Gaussian RBF through the example poses 0 and 90 degrees, 0.515 at 45 degrees and 0.786 at 120 degrees, falling back towards 0 beyond 90

The RBF curve is smooth and passes through both examples, but notice what happens beyond 90°: Gaussian bumps fade with distance, so the correction falls back towards 0 as the elbow bends further, which is usually wrong.
That's the classic trap of RBF interpolation: outside the examples it returns to zero.
Rigs avoid it by sculpting another example at the extreme pose (say 140°), or by adding a linear term to the interpolant.
The same machinery works in many dimensions (all three shoulder angles, or a quaternion distance) and with whole vertex deltas instead of a weight; PSD solvers and RBF nodes are standard tools in DCC rigging at the time of writing.

Delta mush

Delta mush (デルタマッシュ), developed at Rhythm & Hues and presented by Mancewicz and colleagues at DigiPro 2014, cleans up a deformation automatically:

  1. In the bind pose, smooth the mesh (a few iterations of moving each vertex towards the average of its neighbors, 𝐯←𝐯+λ(𝐯¯−𝐯)), and store each vertex's delta from its smoothed position, expressed in a local frame of the smoothed surface (tangent, bitangent, normal).
  2. At runtime, deform the mesh with any cheap skinning, even rigid binding, smooth the deformed mesh the same way, and add the stored deltas back, rotated into the local frames of the smoothed deformed surface.

The smoothing removes the kinks and collapses of the crude skinning; the deltas put the modeled detail (wrinkles, buttons, muscles) back: a stored delta of 0.3 along the normal, on a smoothed surface point at (5,2) whose frame has turned by 30°, lands at (5,2)+0.3(−sin30°,cos30°)=(4.85,2.26).
The smoothing costs time every frame, so games often use delta mush offline instead, to bake better LBS weights.

25.4 Blending animation in depth

Chapter 14, section 14.8 listed blending, cross-fades, state machines and blend trees.

What a pose is, and how to blend it

A pose is one local transform per joint, usually stored as translation, rotation quaternion and scale (TRS), relative to the parent.
Blending two poses with the weight α is done per joint, in local space:

  • translations and scales: linear interpolation;
  • rotations: nlerp (normalized lerp, with the sign check) or slerp; most engines use nlerp, because blend weights change every frame anyway and nlerp is cheaper and commutative for many inputs (a weighted sum of several quaternions, then one normalization).

In local space each joint blends only its own rotation, and FK afterwards builds a valid skeleton with the bone lengths intact; blended world matrices would shrink (section 25.1).

1D blend spaces and synchronization

A blend space (ブレンドスペース) places clips at points of a parameter space, and the current parameter value picks the weights.
In 1D, along speed: idle at 0 m/s, walk at 1.5 m/s, run at 4.5 m/s.
At 2.0 m/s, between walk and run:

wrun=2.0−1.54.5−1.5=16,wwalk=56

But a walk cycle lasts 1.2 s and a run cycle 0.8 s; blended frame by frame, the feet would soon be out of step (left foot down in one clip, right foot in the other).
The fix is synchronization (同期) by normalized time (phase): both clips play the same fraction of their cycle, and the blended cycle lasts

T=56⋅1.2+16⋅0.8=1.1333 s

so the walk plays at 1.2/1.1333=1.059 times its speed and the run at 0.8/1.1333=0.706 times.
Clips are marked with sync markers (foot-down events) so the phases line up even when the clips don't start on the same foot.

A detail that bites: the root speed is not exactly 2.0 now.
The stride per cycle is 1.5⋅1.2=1.8 m for the walk and 4.5⋅0.8=3.6 m for the run; blended, 56⋅1.8+16⋅3.6=2.1 m per 1.1333 s, which is 1.853 m/s.
Either the weight is solved for the exact speed (wrun=0.2308 here), or the playback rate is raised by 2.0/1.853=1.079, or the stride is adjusted with IK (stride warping).

2D blend spaces with triangles

Locomotion depends on two numbers, the velocity sideways and forward in the character's frame.
A 2D blend space scatters clips over that plane: idle at the center, walks at 1.5 m/s and runs at 4.5 m/s in four directions.
To blend at any point, the samples are triangulated (for example with a Delaunay triangulation), and the query point gets the barycentric coordinates (重心座標) of its triangle as weights, exactly the edge-function areas of chapter 6, section 6.9.
Unreal Engine's blend spaces, for example, use triangulation by default at the time of writing.

Worked example. The query 𝐩=(1.0,2.5) (forward at 2.5 m/s, drifting right at 1.0 m/s) lies in the triangle run F (0,4.5), walk F (0,1.5), run R (4.5,0).
The triangle's area is 12⋅3⋅4.5=6.75.
Each weight is the area of the small triangle opposite its vertex, divided by 6.75:

  • run F: triangle 𝐩, walk F, run R, area 3.0, weight 3.0/6.75=0.444;
  • walk F: triangle run F, 𝐩, run R, area 2.25, weight 0.333;
  • run R: triangle run F, walk F, 𝐩, area 1.5, weight 0.222.

Check: 0.444(0,4.5)+0.333(0,1.5)+0.222(4.5,0)=(1.0,2.5), and the weights add up to 1.
Only three clips are evaluated, and the weights change continuously from one triangle to the next.

A 2D blend space with nine samples, idle, walks at 1.5 and runs at 4.5 m/s in four directions, triangulated; the query 1.0, 2.5 lies in the triangle run F, walk F, run R with the weights 0.444, 0.333 and 0.222

Thin triangles make weights change abruptly, so animators add samples (diagonal walks) where needed.

Additive animation

An additive animation (加算アニメーション) stores a difference from a reference pose instead of a pose: breathing, a flinch, a recoil, leaning into a turn.
For each joint,

qadd=qref−1qpose,q=qbaseslerp(qid,qadd,w)

where qid=(1,0,0,0) is no rotation, so the weight w scales the difference (translations simply add the weighted difference).
Worked example. A flinch bends a spine joint 12° forward about x relative to its reference.
Played with the weight 0.5 on top of a run whose spine is at 20° about x, the result is 20°+0.5⋅12°=26° about x.
Because the difference adds on top of whatever plays underneath, one flinch works on idle, walk and run alike; with several additive layers the order matters, because rotations about different axes don't commute.

Layered and masked blending

Layered blending (レイヤーブレンド) plays different animations on different parts of the body: the legs run while the upper body aims or reloads.
A bone mask (ボーンマスク) gives each joint a weight for the upper layer, often ramped up the spine so the twist is spread out: for example 0.25, 0.5 and 0.75 on three spine joints and 1 from the chest up.
A spine joint with the mask 0.5, at 0° in the run and 40° in the aim pose, gets slerp at 0.5: 20°.

Root motion

The root (ルート) joint of chapter 13 carries the character's motion through the world.
With root motion (ルートモーション) the clip's root displacement is extracted each frame and applied to the character's movement component, so the feet stay planted exactly as captured.
Worked example. The walk clip moves its root 1.8 m forward per 1.2 s cycle, 1.5 m/s; at 60 fps that's 1.8/72=0.025 m per frame along the clip's forward axis +z.
The character faces 30° about y, so the displacement in the world is 𝐑y(30°)(0,0,0.025)=(0.025sin30°,0,0.025cos30°)=(0.0125,0,0.0217) m.
The alternative is in-place animation moved by gameplay code; when the two disagree, the feet slide: code at 2.0 m/s with a walk animated at 1.5 m/s slides 0.5 m every second, unless the playback rate (×1.33) or the stride is adjusted.
Games often use root motion for attacks and climbing, where the exact path matters, and code-driven motion for responsive running.

Transitions: cross-fade vs inertialization

A cross-fade (クロスフェード) from clip A to clip B over 0.2 to 0.3 s evaluates both clips during the whole transition and blends them.
That doubles the cost while it lasts, and the blend can show artifacts of its own (both clips' foot contacts mixed).
Inertialization (慣性化) switches to the new clip immediately and hides the jump with an offset that decays to zero.
David Bollo described it for Gears of War 4 (2016) in talks at SIGGRAPH 2017 and GDC 2018.
At the switch, for each joint (and each channel), record the offset x0=old−new and its rate of change v0; then add to the new clip an offset x(t) that starts at x0 with velocity v0 and reaches 0 with zero velocity and acceleration after the blend time T.
Six conditions call for a polynomial of degree five; with the normalized time s=t/T, V=v0T and zero starting acceleration,

x(s)=x0+Vs−(10x0+6V)s3+(15x0+8V)s4−(6x0+3V)s5

If v0 points away from zero (the offset is still growing), it's set to 0 first, so the curve doesn't overshoot.
Bollo's version also chooses a starting acceleration and can shorten T, both to prevent overshoot; keeping the acceleration at zero makes the numbers simpler here.
With V=0 this is x0(1−10s3+15s4−6s5), the quintic "smootherstep" relative of chapter 13's smoothstep.

Worked example. At the switch, an elbow is at 30° and moving at −45°/s in the old clip, and at 10° moving at +15°/s in the new one.
The offset is x0=20°, its velocity v0=−60°/s (already shrinking, so it's kept), T=0.3 s, V=−18°:

x(s)=20−18s−92s3+156s4−66s5

Check: x(1)=20−18−92+156−66=0.
At t=0.15 s (s=0.5): 20−9−11.5+9.75−2.0625=7.19°, so the elbow shows 10+15⋅0.15+7.19=19.44°.

Joint angle against time around a switch at t equals 0: the old clip falling from 30 degrees, the new clip rising from 10 degrees, a 0.3 s cross-fade, and the inertialized curve that continues the old motion smoothly and reaches the new clip at 0.3 s, 19.44 degrees at 0.15 s

The inertialized curve leaves the old motion with exactly its velocity and lands on the new clip smoothly, and only one clip is evaluated.
For rotations the offset is a quaternion (the rotation from the new pose to the old one), decayed through its axis–angle form.
Unreal Engine, for example, has an inertialization node at the time of writing, and many games now use it for most transitions; it is also what makes motion matching (section 25.5) practical.

State machines, revisited

The state machines of chapter 14 organize all this: each state holds a blend space or blend tree, each transition a condition and a blend method, and big graphs nest sub-state machines.
Their weakness is scale: hundreds of clips need thousands of hand-tuned transitions, the problem motion matching attacks.

25.5 Motion matching

From motion graphs to motion matching

The motion graphs of chapter 13, section 13.9 (Kovar, Gleicher and Pighin, 2002) precompute where one clip can jump into another.
Motion matching (モーションマッチング) drops the precomputation: it keeps a large database of unedited motion capture (minutes of a performer walking, turning, starting and stopping in every combination) and, every few frames at runtime, searches it for the frame that best continues the current pose towards what the player wants.
Simon Clavet of Ubisoft Montreal presented it at GDC 2016 ("Motion Matching and The Road to Next-Gen Animation"), and it shipped in For Honor; since then many games and engines have adopted it.

Features

Each frame of the database gets a feature vector (特徴ベクトル) describing what matters for choosing it, in the character's local frame:

  • trajectory features: where the root will be (and which way it will face) a little into the future, for example at 0.33, 0.67 and 1.0 s;
  • pose features: positions and velocities of a few key joints, typically the feet and the hips, so the next frame continues the current motion without a jump.

At runtime the query is built the same way: the pose features from the character's current pose, the trajectory features from the player's stick input, predicted forward (often with a spring like those of chapter 14).
Features in different units (meters, meters per second) must be made comparable: each one is normalized by subtracting its mean over the database and dividing by its standard deviation, and then weighted to set priorities (more weight on the trajectory for responsiveness, more on the pose for smoothness).

Search: a worked example

A small example with six numbers per frame: the root's future position (x,z) at 0.5 s and at 1.0 s, and the forward offsets zL,zR of the left and right foot.
Standard deviations: 0.5 m for the trajectory numbers, 0.2 m for the feet; all weights 1.
The player pushes the stick forward and to the right, and the current pose has the left foot ahead:

𝐪=(0.3,0.7,0.9,1.2,0.15,−0.10)

Four candidate frames:

frame traj. 0.5 s traj. 1.0 s feet trajectory cost pose cost total
A: walk straight (0, 0.75) (0, 1.5) (0.12, −0.12) 3.970 0.033 4.003
B: walk turning right, other foot (0.25, 0.7) (0.85, 1.25) (−0.10, 0.14) 0.030 3.003 3.033
C: walk turning right (0.3, 0.65) (0.95, 1.1) (0.18, −0.05) 0.060 0.085 0.145
D: run turning right (0.6, 1.4) (1.8, 2.6) (0.2, −0.2) 13.400 0.313 13.713

Each cost is the sum of squared normalized differences.
For C: the trajectory differences divided by 0.5 are (0,−0.1,0.1,−0.2), squared and summed 0.06; the foot differences divided by 0.2 are (0.15,0.25), giving 0.0225+0.0625=0.085.
For B the trajectory is even closer (0.03), but its feet are in the opposite phase: (−0.250.2)2+(0.240.2)2=1.5625+1.44=3.003.
Jumping to B would swap the feet in one frame; the pose features prevent that.
C wins, and the character transitions to it, usually with inertialization.

Top-down view in the character&

Cost and speed

Real feature vectors have 20 to 30 numbers.
Thirty minutes of capture at 30 frames per second is 30⋅60⋅30=54,000 frames; with 27 floats each, a brute-force search touches 54,000⋅27=1.46 million numbers (5.8 MB), several times per second, per character.
That's affordable for the player but not for a crowd, so implementations add acceleration structures (k-d trees, bounding-box hierarchies over the features), search only every 0.1 s or so, and skip the search while the current continuation is good enough.
The capture must cover every motion the player can ask for, and tags exclude frames that don't fit the situation.

Learned motion matching and learned controllers

Learned motion matching (Holden, Kanoun, Perepichka and Popa, SIGGRAPH 2020) replaces the database with small neural networks that do the same job: one predicts the next features (the "stepper"), one does the search's work (the "projector"), and one rebuilds the full pose from the features (the "decompressor"), at a fraction of the memory.
Earlier, phase-functioned neural networks (Holden, Komura and Saito, SIGGRAPH 2017) generated locomotion directly from the user's input and the terrain.
Controllers trained with reinforcement learning can also drive simulated characters with joint torques to imitate captured clips (for example DeepMimic, Peng and colleagues, 2018), physically valid motion that reacts to pushes.
Chapter 29 covers neural networks in rendering.

25.6 Full-body inverse kinematics

Chapter 13 solved IK analytically for two links and iteratively with CCD, and showed the Jacobian.
Here are the methods used for longer chains and whole bodies.

FABRIK

FABRIK (Forward And Backward Reaching Inverse Kinematics; Aristidou and Lasenby, Graphical Models, 2011) works on joint positions, not angles.
It keeps the bone lengths by placing each joint on the line towards its neighbor, at the right distance, in two passes:

  1. Reachability: if the target is farther from the root than the sum of the bone lengths, stretch the chain straight towards it and stop.
  2. Backward pass: put the end effector on the target; then, from the end towards the root, move each joint onto the line from its (already moved) child to its current position, at the bone length from the child. The root ends up displaced.
  3. Forward pass: put the root back where it belongs; then, from the root towards the end, move each joint onto the line from its (already moved) parent to its current position, at the bone length.
  4. Repeat until the end effector is close enough to the target.

Worked example on chapter 13's arm: l1=3, l2=2, straight along x (joints at (0,0), (3,0), (5,0)), target (2,3), at the distance 13=3.606<5: reachable.

  • Backward: the hand goes to (2,3). The elbow moves towards its old position (3,0): the direction (1,−3) has length 10=3.162, so the elbow goes to (2,3)+2(1,−3)3.162=(2.632,1.103). The root would follow to (−0.135,−0.056), 0.146 away from where it must be.
  • Forward: the root is put back at (0,0). The elbow goes towards (2.632,1.103), whose length is 2.854: 3(2.632,1.103)2.854=(2.767,1.159). The hand goes from there towards (2,3): the direction (−0.767,1.841) has length 1.994, so the hand lands at (2.767,1.159)+2(−0.767,1.841)1.994=(1.998,3.005).

FABRIK on the arm with l1 = 3 and l2 = 2: the start pose with the target at 2, 3; the backward pass with the hand on the target, the elbow at 2.632, 1.103 and the root detached by 0.146; the forward pass with the root back, the elbow at 2.767, 1.159 and an error of 0.0056

After one iteration the error is 0.0056, after two below 0.0001; CCD needed four sweeps to reach 0.012 on the same problem (chapter 13, section 13.7).
FABRIK's moves are cheap (one normalization per joint, no trigonometry), the bending spreads over the whole chain, and several end effectors (two hands on a rifle) are handled by running the passes per branch and averaging at shared joints.
Angles are read off the final positions: θ1=atan2(1.159,2.767)=22.73°, against the exact 22.62°.

Jacobian methods

The Jacobian 𝐉 of chapter 13 links small joint changes to small end-effector moves, Δ𝐩≈𝐉Δ𝜽.
To move the effector by the error 𝐞=𝐩target−𝐩, there are three classic choices (Samuel Buss's 2004 notes "Introduction to Inverse Kinematics with Jacobian Transpose, Pseudoinverse and Damped Least Squares methods" are the standard tutorial):

  • Jacobian transpose (ヤコビ行列の転置法): Δ𝜽=α𝐉⊤𝐞. No inversion at all; 𝐉⊤𝐞 is the direction in which the error falls fastest, and a good step size is α=𝐞⋅𝐉𝐉⊤𝐞‖𝐉𝐉⊤𝐞‖2.
  • Pseudo-inverse (擬似逆行列): Δ𝜽=𝐉+𝐞, with 𝐉+=𝐉⊤(𝐉𝐉⊤)−1 for a chain with more joints than target coordinates (the smallest joint change that achieves 𝐞 in the linear model); for a square 𝐉 it's simply 𝐉−1.
  • Damped least squares (DLS, 減衰最小二乗法; Wampler and, independently, Nakamura and Hanafusa, 1986): Δ𝜽=𝐉⊤(𝐉𝐉⊤+λ2𝐈)−1𝐞. The damping λ trades accuracy for stability: it minimizes ‖𝐉Δ𝜽−𝐞‖2+λ2‖Δ𝜽‖2, so it never asks for huge joint changes.

Worked example. Chapter 13's FK pose, θ1=30°, θ2=45°, hand at (3.116,3.432), with

𝐉=[−3.432−1.9323.1160.518],det𝐉=4.243

The target is (2.5,3.8), so 𝐞=(−0.616,0.368), a distance of 0.717.

  • Transpose: 𝐉⊤𝐞=(3.260,1.380) and α=0.0404, so Δ𝜽=(0.1317,0.0558) rad =(7.55°,3.20°).
  • Pseudo-inverse (here 𝐉−1): Δ𝜽=(5.30°,8.85°).
  • DLS with λ=1: Δ𝜽=(6.34°,5.36°).

Running FK with the new angles, the hand misses the target by 0.035, 0.070 and 0.041.
The pseudo-inverse step is exact for the linear model (it predicts (2.5,3.8) exactly), but the arm moves on arcs, not straight lines, so every method needs a few more iterations; with small errors near the end, all three converge.

The arm in chapter 13&

The difference shows near a singular pose (特異姿勢).
Bend the elbow only 5° (θ1=0, hand at (4.992,0.174), det𝐉=6sin5°=0.523) and ask for a hand 0.3 further along x, just out of reach.
The inverse answers with Δ𝜽=(65.5°,−164.1°): the arm whips around and the hand lands at (1.12,0.73).
DLS with λ=1 answers (0.49°,−1.58°), a small, harmless step.
That's why solvers damp, and why λ is often raised automatically as det𝐉 gets small.

Joint limits and other constraints

Iterative solvers enforce the joint limits (可動域) after every step: clamp a hinge angle (a step that asks a knee for 160° gets 150°), project a ball joint's bone back into its allowed cone, and in FABRIK move each joint back into its allowed region relative to its parent during the pass.
A hinge also needs its bending plane: FABRIK alone happily bends a knee backwards if that's closer, which is what the pole vector of chapter 13 or a "mirror into the correct half-plane" rule fixes (the practical assignment shows it).

Foot placement

Animations are captured on flat floors.
On stairs and slopes, foot IK (フットIK) keeps the feet on the real ground:

  1. Cast a ray down from each foot's animated position to find the ground height (and normal).
  2. If a foot must go down (a hole, a lower step), the leg can't reach while the pelvis stays at its animated height, so lower the pelvis by the largest downward offset.
  3. Solve each leg as a two-bone IK chain (chapter 13's law of cosines) from the lowered hip to its ground point, with a pole vector so the knee points forward.
  4. Rotate each foot to match the ground normal, and smooth all offsets over time so steps don't pop.

Worked example. Thigh and shin are 0.45 m each.
In the animation the hip is at (0,0.85) and the feet at (±0.15,0), at the distance 0.152+0.852=0.863; the knee bend is arccos0.745−0.4050.405=arccos0.840=32.9°.
The ground under the back foot has a dip of −0.10, and under the front foot a step of +0.15.
Lower the pelvis by 0.10 to (0,0.75).
The back foot's target (−0.15,−0.10) is again 0.863 away, so its knee keeps 32.9°.
The front foot's target (0.15,0.15) is 0.0225+0.36=0.618 away: cosθ=0.3825−0.4050.405=−0.056, a knee bend of 93.2°.

Foot placement: the animated pose with the hip at 0.85 and both feet at ground level, and the pose after foot IK with the pelvis lowered by 0.10, the back foot in a dip of minus 0.10 with the knee at 32.9 degrees and the front foot on a step of plus 0.15 with the knee at 93.2 degrees

Look-at

A head that turns towards a point of interest is a small IK problem of its own.
The rotation from the head's forward direction 𝐟 to the target direction 𝐝 has the axis 𝐟×𝐝 (normalized) and the angle arccos(𝐟⋅𝐝), an axis–angle rotation (Linear Algebra chapter 13, section 13.2) built from a cross and a dot product.
With 𝐟=(0,0,1) and a target 60° to the side, 𝐝=(sin60°,0,cos60°)=(0.866,0,0.5): 𝐟×𝐝=(0,0.866,0), so the axis is +y, the angle arccos0.5=60°, and q=(cos30°,0,sin30°,0).
Turning only the head looks robotic, so the rotation is distributed, for example 20 % to the spine, 30 % to the neck and 50 % to the head (12°, 18°, 30°, each a slerp from the identity), and clamped to a comfortable cone, beyond which the body should turn instead.

A full-body solver combines such goals (hands on a ledge, feet on the ground, the head on a target, the center of mass over the feet) in one FABRIK-like or damped Jacobian solve over the whole skeleton.

Ragdolls and powered ragdolls

A ragdoll (ラグドール, chapter 14) is the skeleton turned into rigid bodies with joint constraints; it falls convincingly but has no will of its own.
Games blend into a ragdoll when a character is knocked down, and back with a get-up clip that matches the ragdoll's final pose.
A powered ragdoll (also active ragdoll, パワードラグドール) adds a motor at each joint that tries to follow the animation.
The simplest motor is a PD controller (PD制御), a spring towards the target angle plus a damper:

τ=kp(θtarget−θ)−kdω

Worked example. An elbow with the moment of inertia I=0.5 kg·m², kp=200 N·m/rad, kd=20 N·m·s/rad, lags its animated angle by 0.3 rad while turning at 1 rad/s: τ=200⋅0.3−20⋅1=40 N·m, an angular acceleration of 40/0.5=80 rad/s².
These gains are no accident: kd=2kpI=2100=20 is critical damping, the same c=2km as for the spring of chapter 14, section 14.2: the joint reaches its target fast without oscillating.
High gains follow the animation closely, low gains go limp; a hit reaction lowers the gains of the hit limb for a moment, so the physics pushes it and the animation pulls it back.
How a physics engine solves the joint constraints and motors is chapter 26.

Exam points

Beyond the syllabus, but these sharpen two syllabus items of area 5, character animation and real-time animation (chapters 13 and 14):

  • LBS blends matrices, and a weighted sum of rotations is a rotation times a shrink (0.707 at 90°, 0 at 180°): thin bends, candy wrapper. DQS blends rigid transforms as dual quaternions with the same weights, so every vertex moves rigidly: no collapse, but a slight bulge at bends and a flip past 180° of twist.
  • The skinning matrix is 𝐖j𝐁j−1: the identity in the bind pose.
  • Blend in local space, per joint, with slerp or nlerp; 2D blend spaces use barycentric weights of three samples; synchronized clips share a normalized phase.
  • Cross-fade evaluates two clips; inertialization evaluates one and decays the offset.
  • IK: FABRIK moves positions along lines; Jacobian methods move angles (transpose, pseudo-inverse, damped least squares, the last one stable near singular poses).

25.7 Facial animation in depth

FACS-based rigs and combination shapes

Chapter 13 introduced the Facial Action Coding System (FACS) and its action units (アクションユニット, AU), and FACS-based rigs with roughly one blend shape per AU.
Real faces don't add up linearly, though: a smile (AU12) with the jaw dropped (AU26) stretches the lips differently than the two shapes summed.
So rigs add combination shapes (コンビネーションシェイプ), sculpted corrections for pairs or triples of AUs, whose weight is the product of the weights involved.
With AU12 at 0.8 and AU26 at 0.5, the combination shape gets 0.8⋅0.5=0.4: zero when either is off, full when both are full.
A film-quality face rig can have hundreds of base and combination shapes, plus correctives for the eyelids sliding over the eyeball and the lips sticking together.

Solving blend shape weights from capture

Performance capture records the face as moving points: markers, or features tracked in video, or a dense reconstructed mesh.
To drive a rig, the capture must be turned into blend shape weights: blend shape solving (ブレンドシェイプのソルブ).
Stack the displacements of the tracked points from the neutral face into a vector 𝐝, and put each shape's displacements of the same points into a column of a matrix 𝐁; then find the weights 𝐰 that reproduce 𝐝 best in the least squares sense:

min𝐰‖𝐁𝐰−𝐝‖2⇒𝐁⊤𝐁𝐰=𝐁⊤𝐝

(the normal equations), usually with the extra conditions 0≤wk≤1 and a small penalty that keeps the weights sparse, because a face rig has more shapes than the capture can tell apart.

Worked example with two shapes and three measured numbers: the mouth corner's height, the mouth corner's sideways position and the chin's height.
Smile: (0.40,0.30,0.10); jaw drop: (−0.20,0,−0.80); measured 𝐝=(0.17,0.20,−0.41).

𝐁⊤𝐁=[0.26−0.16−0.160.68],𝐁⊤𝐝=[0.0870.294]

With the determinant 0.26⋅0.68−0.162=0.1512,

wsmile=0.68⋅0.087+0.16⋅0.2940.1512=0.702,wjaw=0.16⋅0.087+0.26⋅0.2940.1512=0.598

The rebuilt displacements (0.161,0.211,−0.408) miss the measurement by only 0.014: the capture was a 70 % smile with the jaw 60 % open, plus a little noise that no combination of the shapes can explain, which is exactly what least squares throws away.

At the time of writing, consumer devices do this solve in real time: Apple's ARKit face tracking, for example, outputs named coefficients from 0 (neutral) to 1 (maximum), such as jawOpen and eyeBlinkLeft, ready to drive a rig with matching shapes.

Performance capture

In film and AAA games, performance capture (パフォーマンスキャプチャ) records body, face and voice together, the face with a head-mounted camera.
The footage is tracked, solved onto the actor's own digital double first, retargeted to the character through shared AU names or learned mappings, and polished by animators (eyes, lip contacts for p, b and m).

25.8 Crowds and animation compression

Crowd animation LOD

Chapter 14 introduced crowds and animation LOD.
A typical tier list for a stadium or a battle:

  • near: full skeleton, blending, IK;
  • middle: fewer bones, updates at 15 to 30 Hz, no IK;
  • far: no skeleton: vertex animation textures (VAT, 頂点アニメーションテクスチャ) store the skinned vertex positions of each frame in a texture row, read by the vertex shader by vertex index and time;
  • farthest: impostors, the billboards of chapter 12 with a flipbook of animation frames.

A VAT for a 2,000-vertex character and a 60-frame cycle, with positions as four 16-bit floats (8 bytes), is 2,000⋅60⋅8=960,000 bytes, under 1 MB, and with GPU instancing thousands of copies play it at different phases for almost nothing.

Animation compression

Raw, a clip stores per joint and frame a translation (3 floats), a rotation (4) and a scale (3): 40 bytes; 60 joints at 30 fps make 2,400 bytes per frame and 4.32 MB per minute.
Animation compression (アニメーション圧縮) works in layers:

  • Remove constant tracks. Most joints never scale, and only the root translates. Keeping 60 rotations (16 bytes each) plus one root translation (12 bytes) gives 972 bytes per frame, 2.5 times smaller, with no loss at all.
  • Keyframe reduction (キーフレーム削減). Remove keys that interpolation between the remaining keys reproduces within a tolerance. A channel with the samples 0, 1.02, 1.98, 3.01, 4.0 at frames 0 to 4 is within 0.02 of the straight line through the first and last, so with a tolerance of 0.05 only two keys remain. Curve fitting with splines (chapter 8) goes further.
  • Quantization (量子化). Store values with fewer bits, inside the range each track actually uses.

The classic trick for rotations is smallest three (最小3成分): a unit quaternion satisfies w2+x2+y2+z2=1, so one component can be dropped and rebuilt.
Drop the one with the largest magnitude (2 bits say which), and flip the whole quaternion if it's negative (q and −q are the same rotation); the other three then lie in [−12,12], which 10 bits each cover in steps of 1.41421023=0.00138.
That's 32 bits per rotation instead of 128.

Worked example. q=(0.9659,0,0,0.2588), 30° about z.
Drop w. The code for z is round(0.2588+0.70711.4142⋅1023)=round(698.72)=699, which decodes to 0.2592; x and y (0) become code 512, which decodes to 0.0007, because no code sits exactly on 0.
Rebuilt: w=1−0.00072−0.00072−0.25922=0.9658, and the decoded rotation differs from the original by 0.12°.
With rotations at 4 bytes and the root translation as three 16-bit values, a frame needs 60⋅4+6=246 bytes, 9.8 times smaller than the raw 2,400.

Errors add up along the chain (0.05° at the hip moves a foot 1 m below by 1000⋅0.05⋅π180=0.87 mm), so good compressors measure the error at the ends of the chains and give each track just enough bits.

25.9 Summary

  • Skinning matrices are 𝐖j𝐁j−1, the identity in the bind pose. LBS averages them, and the average of two rotations is a rotation times cosβ−α2: thin bends and candy wrappers.
  • Dual quaternions qr+ε12tqr (ε2=0) encode rigid transforms. DQS blends them with the LBS weights (sign-checked) and normalizes, so each vertex moves rigidly: the 90° elbow keeps radius 0.5 (LBS 0.354). It bulges slightly at bends, flips past 180° of twist and doesn't handle scale directly.
  • Corrective shapes are driven by joint angles and added before skinning; pose-space deformation interpolates sculpted corrections with RBFs (which fall back to zero away from the examples); delta mush smooths a crude deformation and restores the detail.
  • Poses blend per joint in local space; blend spaces interpolate weights (1D with phase sync, 2D barycentric in a triangulation); additive layers add differences, masks limit layers to body parts, root motion moves the character with the clip.
  • Inertialization switches clips instantly and decays the offset with a quintic, evaluating one clip instead of two.
  • Motion matching searches a motion-capture database for the frame whose normalized, weighted features (future trajectory, foot positions and velocities) best match the query; learned motion matching compresses it into networks.
  • FABRIK solves IK with positions in backward and forward passes; Jacobian transpose, pseudo-inverse and damped least squares solve it with angles, DLS staying stable near singular poses; joint limits, foot placement and look-at build on them.
  • Powered ragdolls drive physics joints towards the animation with PD controllers (critical damping kd=2kpI).
  • Faces: FACS shapes plus combination shapes, with weights solved from capture by bounded least squares.
  • Crowds use fewer bones, lower update rates, vertex animation textures and impostors; compression removes constant tracks, reduces keys and quantizes (smallest three: 32 bits per rotation).

25.10 Key terms

English 日本語
bind pose, inverse bind matrix バインドポーズ、逆バインド行列
skinning matrix, matrix palette スキニング行列、行列パレット
linear blend skinning (LBS) リニアブレンドスキニング
dual number 双対数
dual quaternion デュアルクォータニオン(双対四元数)
dual quaternion skinning (DQS) デュアルクォータニオンスキニング
dual quaternion linear blending (DLB) デュアルクォータニオン線型ブレンド(DLB)
flipping artifact, bulge 反転アーティファクト、膨らみ
twist bone ツイストボーン
corrective blend shape 補正ブレンドシェイプ
pose-space deformation (PSD) ポーズスペースデフォメーション(PSD)
radial basis function (RBF) 放射基底関数(RBF)
delta mush デルタマッシュ
pose ポーズ
blend space ブレンドスペース
synchronization, normalized time 同期、正規化時間
barycentric coordinates 重心座標
additive animation 加算アニメーション
layered blending, bone mask レイヤーブレンド、ボーンマスク
root motion ルートモーション
cross-fade クロスフェード
inertialization 慣性化(イナーシャライゼーション)
motion matching モーションマッチング
feature vector 特徴ベクトル
learned motion matching 学習型モーションマッチング
FABRIK FABRIK
Jacobian transpose ヤコビ行列の転置法
pseudo-inverse 擬似逆行列
damped least squares (DLS) 減衰最小二乗法
singular pose 特異姿勢
joint limit 可動域
foot IK, foot placement フットIK、足の接地
look-at ルックアット
ragdoll, powered ragdoll ラグドール、パワードラグドール(アクティブラグドール)
PD controller PD制御
action unit, combination shape アクションユニット、コンビネーションシェイプ
blend shape solving ブレンドシェイプのソルブ
performance capture パフォーマンスキャプチャ
vertex animation texture (VAT) 頂点アニメーションテクスチャ(VAT)
animation compression アニメーション圧縮
keyframe reduction キーフレーム削減
quantization, smallest three 量子化、最小3成分

25.11 Challenges

  1. ★ The elbow of section 25.2 bends by 60° instead of 90° (bone 1 turns about z around (2,0); the vertex (2,−0.5) has the weights 0.5 and 0.5). Compute the LBS position and its distance from the elbow, then the DQS position (a rotation by half the bend about the elbow), and check that the LBS distance is 0.5cos30°.
  2. ★ In the 2D blend space of section 25.4, compute the weights for the queries (0.5,3.0) and (0.6,0.6), and check that each set reproduces its query. Then compute the 1D weights for 3.5 m/s between walk (1.5 m/s, cycle 1.2 s) and run (4.5 m/s, cycle 0.8 s) and the length of the synchronized cycle.
  3. ★★ An inertialization starts with the offset x0=−12°, the offset velocity v0=30°/s and T=0.25 s. Write x(s), check x(1)=0, and compute x(0.5). Then redo it with v0=−30°/s, and explain why that velocity is set to 0 first.
  4. ★★ An arm with l1=4 and l2=3 lies straight along x, and the target is (3,5). Do one FABRIK iteration by hand (backward and forward pass) and give the remaining error. Compare the elbow with the two analytic solutions of chapter 13's law of cosines: which one does FABRIK approach, and why?
  5. ★★★ Two bones rotate about the same axis through the same point, by 0 and by φ. Show that DLB with the weight w on the second gives a rotation about that same axis and point, by the angle 2atan2(wsinφ2,1−w+wcosφ2). Evaluate it for φ=90° and w=0.25, compare with slerp, and explain where the bulge of section 25.2 comes from.

Multiple choice

Q1 ★ Which of the following statements about dual quaternion skinning is correct?

A It blends the entries of the bones' skinning matrices with the weights, exactly like linear blend skinning but with 8 numbers per bone.
B It needs a different set of skin weights from linear blend skinning, so the weights must be painted again.
C A joint twisted by 180° about the bone's axis collapses the skin onto the bone, just as with linear blend skinning.
D It handles non-uniform scaling of bones directly, because a unit dual quaternion can describe any affine transform.
E It blends the bones' rigid transforms as dual quaternions and normalizes the result, so each vertex is moved by a rigid transform; this avoids the candy-wrapper collapse but can make the skin bulge slightly at bent joints.

Q2 ★ Which of the following statements about animation blending and motion matching is correct?

A In a triangulated 2D blend space, every sample clip contributes to the pose with a nonzero weight.
B Inertialization evaluates both the old and the new clip for the whole length of the transition, like a cross-fade.
C Motion matching needs a hand-built state machine with a transition for every pair of clips.
D Motion matching searches a database of animation frames for the frame whose feature vector, for example future trajectory points and foot positions, is closest to a query built from the current pose and the player's input.
E An additive animation stores absolute joint rotations, so it can only be played on its own.

Q3 ★★ Which of the following statements about inverse kinematics is correct?

A FABRIK computes the joint angles with the Jacobian matrix in every iteration.
B Damped least squares adds λ2𝐈 to 𝐉𝐉⊤ before inverting, which keeps the steps small near singular poses such as a fully stretched arm, at the cost of slower convergence.
C The pseudo-inverse step always leaves a smaller error after one step than the Jacobian transpose step, whatever the target.
D CCD moves all joints of the chain at the same time along the gradient of the error.
E Foot placement raises the pelvis to the height of the highest foot target, so that both legs can reach the ground.

25.12 Practical assignment

Put a leg on a stair step, skin its knee and smooth the transition, all with ruler, compass, protractor and calculator.
You need graph paper (1 unit = 1 cm), a ruler, a compass, a protractor, a pencil, two colored pens and a calculator.

The leg has a thigh l1=4 and a shin l2=4.
The hip is fixed at H=(0,7.5), and in the bind pose the leg hangs straight down: knee K0=(0,3.5), ankle (0,−0.5).
The character faces +x, so the knee must bend forward (towards +x).
The foot must go onto a step at F=(2,1.5).

  1. Reach. Measure and compute the distance from H to F, and check that it's less than l1+l2.
  2. FABRIK by construction, two iterations. Backward pass: put the ankle on F, draw the line from F to the current knee, and mark the new knee with the compass at 4 from F on that line. Forward pass: draw the line from H to the new knee, mark the knee at 4 from H, then the ankle at 4 from the knee towards F. Measure the remaining distance from the ankle to F. Repeat once. Use the first pen.
  3. Joint limit. Look at where your knee ended up. If it points backwards (towards −x), reflect it across the line HF (the knee that the pole vector of chapter 13 would choose). Then compute both analytic knee positions with the law of cosines and compare.
  4. Skin the knee. A vertex sits on the front of the knee in the bind pose, at (0.5,3.5), with the weights 0.5 (thigh) and 0.5 (shin). Measure the angles by which the thigh and the shin have turned from pointing straight down. Rigid copy 1: turn the vertex about H by the thigh's angle. Rigid copy 2: move it with the shin (turn it about K0 by the shin's angle, then move K0 to the new knee). LBS is the midpoint of the two copies; DQS (with equal weights, both copies agree on where K0 goes) turns the vertex about K0 by the average of the two angles and moves K0 to the new knee. Mark both with the second pen and measure their distances from the knee.
  5. Inertialize the knee. In the animation that was playing, the knee was bent 20° and holding still; the IK result is your knee bend from step 3. Take x0=20°−θIK, v0=0 and T=0.2 s, compute the knee bend θIK+x(s) at s=0,0.25,0.5,0.75,1, and plot the five points against time.

How to check yourself:

  • Step 1: ‖F−H‖=40=6.325<8.
  • Step 2: every bone you drew must measure exactly 4. The error after the first iteration is about 0.31 and after the second about 0.03, so it shrinks roughly tenfold per iteration. Starting from the straight leg, FABRIK bends this knee backwards, to about (−1.3,3.7).
  • Step 3: cosθ=40−16−1632=0.25, a knee bend of 75.5°; the two analytic knees are at about (3.32,5.28) and (−1.32,3.72). Your reflected knee must be close to the first one, and each analytic knee must be 4 from H and 4 from F.
  • Step 4: the thigh turns by about 56.2° and the shin by about −19.3° (a difference of 75.5°, the knee bend). The DQS vertex must be 0.5 from the knee, near (3.80,5.43); the LBS vertex about 0.5cos75.5°2=0.395 from it, near (3.70,5.40).
  • Step 5: the factors 1−10s3+15s4−6s5 are 1, 0.896, 0.5, 0.104 and 0, so the knee goes 20°, 25.8°, 47.8°, 69.8°, 75.5°: exactly halfway at s=0.5, with flat starts and ends, and never beyond 75.5°.


コメント(0)

まだコメントはありません。