Build a Game Engine · Animation

Animation: Blending, State Machines & IK

Your character can play one clip at a time. A game needs more: go from idle to walk to run without a visible jolt, strafe diagonally with only forward and sideways clips, reload while running, and keep its feet on the stairs instead of floating above them. The Skeletal Animation module built the machinery (a skeleton, the matrix palette, clip sampling with slerp, the cross-fade). This page covers everything upstream of the palette: how the engine decides which pose to produce each frame (a state machine or motion matching), blends and layers it, and adjusts it with IK before it ever reaches the skin.

Time~80 min LevelSenior PrereqsHelpful, not required: the Skeletal Animation module (the palette, slerp, the cross-fade, additive-as-delta, two-bone IK) and Behavior Trees (decisions drive transitions). StackC++ & Rust

What you'll be able to do by the end

Write an animation state machine whose transitions are timed cross-fades, and implement inertialization, the transition that samples only one clip.
Compute 1D and 2D blend-space weights, including gradient-band weights for samples that don't sit on a grid.
Layer an upper-body action over locomotion with a bone mask, and build and apply additive deltas with quaternions.
Build a motion-matching feature vector, scale it, search a database for the best frame, and explain how often to search and what it costs to author.
Implement FABRIK with the root reset, and combine raycasts, a pelvis drop and two-bone IK into foot IK.

01Where this fits

Every frame, something has to decide what pose the character is in before the GPU can deform its mesh. The Skeletal Animation module ends with a pipeline: a per-joint local pose (each joint's rotation and offset relative to its parent) → walk the hierarchy to globals → build the matrix palette → skin the vertices. Everything in this module produces or modifies that local pose, then hands it to the same matrix palette, the array of per-joint matrices the vertex shader uses. The full per-frame pipeline:

pose source (state machine or motion matching) → layer blends → IK adjusts → globals → palette → skin

Each stage reuses the skeletal module's primitives: the local-space per-joint cross-fade (slerp rotations, lerp translation/scale), additive-as-delta, and the two-bone analytic IK. This module goes deeper on what that one previewed rather than re-deriving it.

Worked example

One frame for a soldier on a staircase: the state machine is 0.075 s into a 0.25 s walk-to-run cross-fade, so its pose is 30% run. A reload layer overrides the 24 upper-body joints of a 65-joint skeleton. Foot IK lowers the pelvis 15 cm so the downhill foot reaches its step, then bends both legs to plant the feet. Only then are the 65 globals computed, the 65 palette matrices built, and the mesh skinned.

02The state machine

The player pushes the stick from rest to full, and the character has to go from idle to walk to run without a jolt at each change. An is the standard hand-authored model (state machines inside Unreal's AnimGraph, Unity's Animator Controllers)^[1]^[2]^[3]. Each state produces one pose (a clip or a blend tree). Each transition is {toState, condition, blendDuration}. A transition is a timed cross-fade between the source state's pose and the destination's, with weight clamp(elapsed / blendDuration, 0, 1) in the simplest (linear) case: the local-space cross-fade from Skeletal Animation, driven by time instead of a slider.

Worked example

A walk-to-run transition with a 0.2 s blend at 60 fps lasts 12 frames, with the weight climbing by 1 ÷ 12 = 0.083 each frame. If the knee sits at 20° in the walk and 45° in the run at that moment, the cross-fade moves it about 2° a frame. A hard cut moves it the whole 25° between two frames, which reads as a pop. For those 12 frames the cross-fade samples both the walk and the run; inertialization samples only the run.

A transition is not an instant switch, and inertialization is the cheaper alternative

A hard cut (weight jumps 0→1) pops: joint angles jump between two frames. Blend in local space per joint, then recompute globals; blending global matrices gives non-rigid, shrinking in-betweens (the LBS failure). A dual-pose cross-fade evaluates both states during the transition (double cost). A production alternative, offered by Unreal as a transition blend mode^[2], is inertialization (Bollo, Gears of War 4): switch to the destination immediately, record the offset from the source pose, and decay that offset to zero over the transition, so only one pose graph is evaluated^[4]. Blend durations are authored per transition; fast reactions use shorter blends than locomotion changes.

The widget runs a three-state machine driven by one speed input. Its blend lasts 0.4 s, slower than most games use, so the fade is easy to watch:

The three states (idle, walk, run) with the active one highlighted, a blend-weight bar, and a stick figure playing the blended gait. Drag Speed up and down, then tick hard cut and do it again. Speed above 20 selects walk and above 65 selects run. Raise speed to cross thresholds (idle → walk → run); the transition plays as a cross-fade (the weight bar fills over the blend duration) and the figure's gait sweeps smoothly. Enable hard cut and the figure pops at each change, the instant-switch artifact the blend exists to hide.

An animation state machine (transitions are timed cross-fades)

struct Transition { int toState; ConditionFn condition; float blendDuration; };
struct State { PoseSource source; std::vector<Transition> transitions; };  // source = clip or blend tree

Pose StateMachine::evaluate(float dt, const Params& params) {
    if (targetState < 0)                                  // idle: check transitions in priority order
        for (auto& transition : states[currentState].transitions)
            if (transition.condition(params)) {
                targetState = transition.toState; elapsed = 0;
                activeBlendDuration = transition.blendDuration; break;
            }

    Pose from = states[currentState].source.sample(dt, params);  // local-space pose
    if (targetState < 0) return from;

    Pose to = states[targetState].source.sample(dt, params);  // both states run mid-transition
    elapsed += dt;
    float weight = clamp(elapsed / activeBlendDuration, 0.0f, 1.0f);
    Pose blended = crossFade(from, to, weight);          // per-joint slerp/lerp, LOCAL space
    if (weight >= 1.0f) { currentState = targetState; targetState = -1; }  // done
    return blended;
}

struct Transition { to_state: usize, condition: fn(&Params) -> bool, blend_duration: f32 }
struct State { source: PoseSource, transitions: Vec<Transition> }   // source = clip or blend tree

fn evaluate(&mut self, dt: f32, params: &Params) -> Pose {
    if self.target.is_none() {                          // idle: check transitions in priority order
        for transition in &self.states[self.current].transitions {
            if (transition.condition)(params) {
                self.target = Some(transition.to_state); self.elapsed = 0.0;
                self.active_blend_duration = transition.blend_duration; break;
            }
        }
    }
    let from = self.states[self.current].source.sample(dt, params);  // local-space pose
    let Some(target) = self.target else { return from };
    let to = self.states[target].source.sample(dt, params);  // both states run mid-transition
    self.elapsed += dt;
    let weight = (self.elapsed / self.active_blend_duration).clamp(0.0, 1.0);
    let blended = cross_fade(&from, &to, weight);          // per-joint slerp/lerp, LOCAL space
    if weight >= 1.0 { self.current = target; self.target = None; }  // done
    blended
}

Inertialization: one pose instead of two

A cross-fade samples both clips for the whole blend, and in a real graph each "clip" can be a blend tree of its own, so a busy transition roughly doubles the animation cost. Inertialization switches to the new clip at once and hides the jump with an offset: on the switch frame, record how far the new clip's pose is from the pose on screen, add that offset to the new clip, and shrink it to zero over the next few frames^[4]. After the switch frame, only the destination is sampled. Bollo's original presentation shrinks the offset along a polynomial over a fixed time; Holden's version, used below, decays it with a critically damped spring instead, which has no fixed end time and makes the code a few lines^[5]. Unreal offers inertialization as a blend mode on state-machine transitions^[2].

Worked example

From the listing's output: at t = 0.50 s the walk clip has the knee at 20.0° and the run clip at 37.4°. A hard cut shows 37.4° on that frame, a 17.4° jump. The inertializer shows 20.0° (run plus an offset of −17.4°), then 30.5° at 0.55 s and 50.2° at 0.60 s as the offset decays with an 80 ms halflife, and it's within 1.2° of the run clip by 0.80 s. The 0.25 s cross-fade also starts at 20.0°, but it samples both clips until 0.75 s.

One knee angle over time: the two dashed curves are the walk and run clips, the solid line is what the character shows, and a purple line marks each switch (every 1.5 s, or press switch clip). Compare the three modes and watch the readout. A hard cut jumps straight onto the other clip, and the break in the curve reads the full gap between them. A cross-fade starts where the old clip was and bends onto the new one over 0.25 s, sampling 2 clips while it does. Inertialize keeps the curve continuous, settles within 1° of the new clip in under 0.4 s, and after the switch frame samples only 1 clip. When the clips cross at the switch but move at different speeds, the offset starts near zero and still swings out a few degrees and back: that swing is the old clip's velocity being carried through. Press switch twice in quick succession: the inertializer adds the new offset to the one still decaying, so it stays smooth.

Inertialization for one channel, against a hard cut and a cross-fade (complete program)

// Inertialization for one animation channel (a knee angle), compared with a
// hard cut and a cross-fade. The offset decays on a critically damped spring.
#include <cmath>
#include <cstdio>
#include <numbers>

constexpr float kPi = std::numbers::pi_v<float>;

// Halflife sets how fast the offset dies away (smaller is faster). It is named after a
// simple damper's time to halve the gap; a spring carrying velocity is only roughly there.
float halflifeToDamping(float halflife) { return (4.0f * std::numbers::ln2_v<float>) / (halflife + 1e-5f); }

// Move an offset and its velocity toward zero with a critically damped spring,
// solved exactly for the step dt, so it is stable at any frame rate.
void decaySpring(float& offset, float& offsetVelocity, float halflife, float dt) {
    // Closed form: offset(t) = e^(-decayRate t) * (offset + linearTerm * t).
    float decayRate = halflifeToDamping(halflife) / 2.0f;
    float linearTerm = offsetVelocity + offset * decayRate;
    float decay = std::exp(-decayRate * dt);
    offset = decay * (offset + linearTerm * dt);
    offsetVelocity = decay * (offsetVelocity - linearTerm * decayRate * dt);
}

struct Inertializer {
    float offset = 0.0f;
    float offsetVelocity = 0.0f;

    // At the switch, record how far the new clip is from what is on screen.
    // Adding the old offset lets a switch interrupt a switch still in progress.
    void transition(float sourceValue, float sourceVelocity, float destValue, float destVelocity) {
        offset = (sourceValue + offset) - destValue;
        offsetVelocity = (sourceVelocity + offsetVelocity) - destVelocity;
    }

    // Each frame: show the destination plus the offset, then shrink the offset.
    // Only the destination clip is sampled.
    float update(float destValue, float halflife, float dt) {
        float shown = destValue + offset;
        decaySpring(offset, offsetVelocity, halflife, dt);
        return shown;
    }
};

// Two clips' knee angle in degrees, and its rate of change in degrees per second.
float walkKnee(float time) { return 20.0f + 15.0f * std::sin(2.0f * kPi * 1.0f * time); }
float walkKneeVelocity(float time) { return 15.0f * 2.0f * kPi * 1.0f * std::cos(2.0f * kPi * 1.0f * time); }
float runKnee(float time) { return 45.0f + 30.0f * std::sin(2.0f * kPi * 1.6f * time + 1.0f); }
float runKneeVelocity(float time) { return 30.0f * 2.0f * kPi * 1.6f * std::cos(2.0f * kPi * 1.6f * time + 1.0f); }

int main() {
    const float dt = 1.0f / 60.0f;
    const int switchFrame = 30;                 // walk until t = 0.5 s, then run
    const float crossFadeTime = 0.25f, halflife = 0.08f;
    Inertializer inertializer;

    std::printf("    t   walk    run   cut  cross  inert\n");
    for (int frame = 24; frame <= 60; ++frame) {
        float time = frame * dt;
        float walk = walkKnee(time), run = runKnee(time);
        bool running = frame >= switchFrame;
        if (frame == switchFrame)
            inertializer.transition(walk, walkKneeVelocity(time), run, runKneeVelocity(time));

        float hardCut = running ? run : walk;
        // Cross-fade: both clips are sampled for the whole blend.
        float weight = running ? std::fmin(1.0f, (time - switchFrame * dt) / crossFadeTime) : 0.0f;
        float crossFade = walk + (run - walk) * weight;
        float inertial = running ? inertializer.update(run, halflife, dt) : walk;

        if (frame % 3 == 0)
            std::printf("%5.2f %6.1f %6.1f %5.1f %6.1f %6.1f\n", time, walk, run, hardCut, crossFade, inertial);
    }
}

// Inertialization for one animation channel (a knee angle), compared with a
// hard cut and a cross-fade. The offset decays on a critically damped spring.
use std::f32::consts::{LN_2, PI};

// Halflife sets how fast the offset dies away (smaller is faster). It is named after a
// simple damper's time to halve the gap; a spring carrying velocity is only roughly there.
fn halflife_to_damping(halflife: f32) -> f32 { (4.0 * LN_2) / (halflife + 1e-5) }

// Move an offset and its velocity toward zero with a critically damped spring,
// solved exactly for the step dt, so it is stable at any frame rate.
fn decay_spring(offset: &mut f32, offset_velocity: &mut f32, halflife: f32, dt: f32) {
    // Closed form: offset(t) = e^(-decay_rate t) * (offset + linear_term * t).
    let decay_rate = halflife_to_damping(halflife) / 2.0;
    let linear_term = *offset_velocity + *offset * decay_rate;
    let decay = (-decay_rate * dt).exp();
    *offset = decay * (*offset + linear_term * dt);
    *offset_velocity = decay * (*offset_velocity - linear_term * decay_rate * dt);
}

#[derive(Default)]
struct Inertializer { offset: f32, offset_velocity: f32 }

impl Inertializer {
    // At the switch, record how far the new clip is from what is on screen.
    // Adding the old offset lets a switch interrupt a switch still in progress.
    fn transition(&mut self, source_value: f32, source_velocity: f32, dest_value: f32, dest_velocity: f32) {
        self.offset = (source_value + self.offset) - dest_value;
        self.offset_velocity = (source_velocity + self.offset_velocity) - dest_velocity;
    }

    // Each frame: show the destination plus the offset, then shrink the offset.
    // Only the destination clip is sampled.
    fn update(&mut self, dest_value: f32, halflife: f32, dt: f32) -> f32 {
        let shown = dest_value + self.offset;
        decay_spring(&mut self.offset, &mut self.offset_velocity, halflife, dt);
        shown
    }
}

// Two clips' knee angle in degrees, and its rate of change in degrees per second.
fn walk_knee(time: f32) -> f32 { 20.0 + 15.0 * (2.0 * PI * 1.0 * time).sin() }
fn walk_knee_velocity(time: f32) -> f32 { 15.0 * 2.0 * PI * 1.0 * (2.0 * PI * 1.0 * time).cos() }
fn run_knee(time: f32) -> f32 { 45.0 + 30.0 * (2.0 * PI * 1.6 * time + 1.0).sin() }
fn run_knee_velocity(time: f32) -> f32 { 30.0 * 2.0 * PI * 1.6 * (2.0 * PI * 1.6 * time + 1.0).cos() }

fn main() {
    let dt = 1.0_f32 / 60.0;
    let switch_frame = 30; // walk until t = 0.5 s, then run
    let (cross_fade_time, halflife) = (0.25_f32, 0.08_f32);
    let mut inertializer = Inertializer::default();

    println!("    t   walk    run   cut  cross  inert");
    for frame in 24..=60 {
        let time = frame as f32 * dt;
        let (walk, run) = (walk_knee(time), run_knee(time));
        let running = frame >= switch_frame;
        if frame == switch_frame {
            inertializer.transition(walk, walk_knee_velocity(time), run, run_knee_velocity(time));
        }

        let hard_cut = if running { run } else { walk };
        // Cross-fade: both clips are sampled for the whole blend.
        let weight = if running { ((time - switch_frame as f32 * dt) / cross_fade_time).min(1.0) } else { 0.0 };
        let cross_fade = walk + (run - walk) * weight;
        let inertial = if running { inertializer.update(run, halflife, dt) } else { walk };

        if frame % 3 == 0 {
            println!("{time:5.2} {walk:6.1} {run:6.1} {hard_cut:5.1} {cross_fade:6.1} {inertial:6.1}");
        }
    }
}

A real implementation runs this per joint: the rotation offset is a quaternion (the difference between the two rotations) decayed toward the identity, the rotation that does nothing, and the translation offset is a vector, each with its own velocity. Velocity matters at the switch: the offset starts with the difference in velocity as well as position, so the knee keeps the speed it had on the old clip through the switch instead of snapping to the new clip's speed. Unreal also has an experimental dead blending node^[6], a variant that extrapolates the old pose forward from its velocity and blends from that into the new clip, so at the switch it needs only the current pose and its velocity^[7].

03Blend spaces

The character can move at any speed between a walk and a sprint, and in any direction, but you only have a handful of clips. A state's pose is often a , which mixes several clips by runtime parameters, rather than a single clip. A 1D blend places a parameter (speed) on a line of sorted samples (idle, walk, run); find the two bracketing samples and blend by the normalized fraction. A 2D blend mixes by two parameters (e.g. forward speed × strafe speed) and needs a real 2D weighting scheme^[1]^[3].

Worked example

A 1D speed blend has idle at 0, walk at 1.4 and run at 4.0 m/s. At 2.0 m/s the bracketing samples are walk and run, and the fraction is (2.0 − 1.4) ÷ (4.0 − 1.4) = 0.23, so the pose is 77% walk and 23% run.

2D blending is not two 1D blends

With the usual locomotion samples, which don't fill a grid (idle in the middle, one clip per direction), a 2D blend can't be built from two independent 1D blends: mixing an X blend with a Y blend is exact on the axes, but off them (a diagonal strafe) it keeps too much idle and bends the motion toward the nearer axis. Unity's freeform 2D blend types use Gradient Band Interpolation (Johansen): each sample's influence is min over j of [1 − (p−p_i)·(p_j−p_i) / |p_j−p_i|²], clamped at zero and normalized. It needs no triangulation, and each sample's influence reaches exactly to its neighbors however unevenly they're spaced^[8]. Barycentric (triangulation) is a valid alternative but needs a mesh of the samples and extrapolates badly outside the hull. Directional locomotion uses Johansen's polar variant (angle + magnitude), because in Cartesian space a walk sample's influence can reach out to speeds beyond the run samples in that direction^[8]. Whichever scheme, it only computes weights; the blend itself is still the local-space per-joint one.

Worked example

Take the widget's five samples (idle at the center, forward, back, left and right one unit out) and a query at (0.6, 0.3), right and slightly back. For the right sample, the band against idle is 1 − 0.4 = 0.6, and its bands against the other samples are larger, so its raw weight is 0.6. Idle comes out at 0.4 and back at 0.3; forward and left come out at 0. Normalized, that's 46% right, 31% idle and 23% back, and the blended motion points exactly where the query does. Two 1D blends give 40% right, 50% idle and 10% back, and their motion points 13° off.

The widget computes both schemes for a point you can drag:

Five sample clips, each drawn as a disc sized by its weight, and a query point that orbits on its own until you drag it. Drag it off the axes, then switch to two 1D blends. The gradient-band weights and the blended motion (solid arrow) update live against the requested motion (dashed). Switch to two 1D blends and, off the axes, the solid arrow bends toward the nearer axis and idle keeps too much weight: at (0.6, 0.3) it is off by 13°. Neither scheme reaches the corners with only these five samples; that takes diagonal clips.

04Layered animation

A soldier sprints for cover and reloads on the way. Real characters do two things at once: run and reload. Layered animation stacks poses with a bone mask selecting which joints a layer affects. An upper-body layer (aim, reload) plays over a lower-body locomotion layer; the mask is what stops them fighting over the spine and hips.

Besides its pose, a layer has a weight, a mask and a blending type. The mask gives each joint a weight from 0 to 1, which multiplies the layer's weight. Unity's layers take a mask and a blending type, Override or Additive^[9]. Unreal's Layered Blend per Bone node picks joints with a branch filter: name a bone, and it and everything below it in the hierarchy get the layer, optionally tapered over a few bones by a blend depth so the spine bends gradually instead of at one joint^[6].

Override layers vs additive layers

An override layer replaces the masked joints' pose (up to the layer weight). An additive layer adds a pose difference, a delta from a reference pose (the additive-as-delta rule), composed on top of any base: one aim-offset or lean or recoil delta works over walk, run, and crouch without authoring every combination. A layer is one or the other, and additive is not "playing clip B over clip A"^[1].

For rotations the delta is a quaternion. With q⁻¹ meaning the inverse rotation, the open-source ozz-animation library builds an additive clip as delta = reference⁻¹ · pose for every joint and key, and applies it as base · delta, scaling the delta by the layer weight by interpolating it from the identity rotation (no rotation) first^[10].

In words: the delta is the extra rotation that turns the reference pose into the additive pose, and applying it turns the base pose by that same extra amount, measured in the joint's own frame. Engines differ on which side the delta multiplies; what matters is using the same convention to build the delta and to apply it.

Worked example

On a 65-joint skeleton, an upper-body mask selects the 24 joints from the spine up. A reload layer at weight 1 replaces those 24 joints' rotations with the reload clip's, and the legs keep running. An additive lean authored as +10° of spine bend from its reference pose then adds 10° to whatever the spine is doing, in the run, the reload, or both. The listing below runs the same idea on six joints: with the upper-body mask, the aim pose sets the arm to 85° while the thigh and shin keep the run's 35° and −60°; with no mask, the legs snap to the aim clip's standing 0° and −5°; and a +12° lean takes the spine from 8° to 20° in the run and from 2° to 14° in the aim.

Left is the base layer, a run cycle; right is the result with an aim pose layered on top, its bones colored amber where the aim layer drives them. Switch masks, drag the weight, then turn on the lean. With spine and up the arm aims while the legs keep running. With no mask the aim clip, authored standing still, takes the legs too and the runner skates with straight legs. Tapered gives the spine a third of the aim, the chest two thirds and the arm all of it, so the bend spreads over the torso. The additive lean adds 12° to the spine and 3° to the chest on top of whatever the layers produced.

Masked override and additive layers per joint, with quaternions (complete program)

// Layering poses per joint in local space: an override layer replaces the
// masked joints, an additive layer adds a delta measured from a reference pose.
// Rotations only; translations and scales blend the same way with lerp.
#include <cmath>
#include <cstdio>
#include <numbers>
#include <vector>

struct Quat { float w, x, y, z; };

Quat multiply(Quat a, Quat b) {
    return {a.w * b.w - a.x * b.x - a.y * b.y - a.z * b.z,
            a.w * b.x + a.x * b.w + a.y * b.z - a.z * b.y,
            a.w * b.y - a.x * b.z + a.y * b.w + a.z * b.x,
            a.w * b.z + a.x * b.y - a.y * b.x + a.z * b.w};
}
Quat conjugate(Quat rotation) { return {rotation.w, -rotation.x, -rotation.y, -rotation.z}; }   // the inverse, for a unit quaternion

// Normalized lerp: cheap, and close to slerp for the small angles between poses.
Quat nlerp(Quat a, Quat b, float weight) {
    float dot = a.w * b.w + a.x * b.x + a.y * b.y + a.z * b.z;
    float sign = dot < 0.0f ? -1.0f : 1.0f;              // q and -q are the same rotation: take the short way
    Quat blended{a.w + (sign * b.w - a.w) * weight, a.x + (sign * b.x - a.x) * weight,
                 a.y + (sign * b.y - a.y) * weight, a.z + (sign * b.z - a.z) * weight};
    float length = std::sqrt(blended.w * blended.w + blended.x * blended.x +
                             blended.y * blended.y + blended.z * blended.z);
    return {blended.w / length, blended.x / length, blended.y / length, blended.z / length};
}

// Every joint in this example bends about the x axis, so one angle describes it.
Quat bendX(float degrees) {
    float half = degrees * std::numbers::pi_v<float> / 360.0f;
    return {std::cos(half), std::sin(half), 0.0f, 0.0f};
}
float angleX(Quat rotation) { return 2.0f * std::atan2(rotation.x, rotation.w) * 180.0f / std::numbers::pi_v<float>; }

using Pose = std::vector<Quat>;           // one local rotation per joint
using Mask = std::vector<float>;          // one weight per joint, 0..1

// Override: each joint moves toward the layer's rotation by weight * mask.
Pose overrideLayer(const Pose& base, const Pose& layer, const Mask& mask, float weight) {
    Pose result(base.size());
    for (size_t joint = 0; joint < base.size(); ++joint)
        result[joint] = nlerp(base[joint], layer[joint], weight * mask[joint]);
    return result;
}

// Additive: the delta is what the additive clip changes relative to its own
// reference pose. Scaled by weight * mask, it is applied on top of any base.
Pose additiveLayer(const Pose& base, const Pose& additive, const Pose& reference,
                   const Mask& mask, float weight) {
    const Quat identity{1.0f, 0.0f, 0.0f, 0.0f};
    Pose result(base.size());
    for (size_t joint = 0; joint < base.size(); ++joint) {
        Quat delta = multiply(conjugate(reference[joint]), additive[joint]);
        result[joint] = multiply(base[joint], nlerp(identity, delta, weight * mask[joint]));
    }
    return result;
}

const char* kJointNames[] = {"pelvis", "spine", "chest", "arm", "thigh", "shin"};

void printPose(const char* label, const Pose& pose) {
    std::printf("%-22s", label);
    for (const Quat& rotation : pose) std::printf("%7.1f", angleX(rotation));
    std::printf("\n");
}

int main() {
    // One frame of a run, an aiming pose, and a lean authored against a neutral stance.
    Pose run       = {bendX(5),  bendX(8),  bendX(4),  bendX(-40), bendX(35), bendX(-60)};
    Pose aim       = {bendX(0),  bendX(2),  bendX(6),  bendX(85),  bendX(0),  bendX(-5)};
    Pose leanClip  = {bendX(0),  bendX(12), bendX(3),  bendX(0),   bendX(0),  bendX(0)};
    Pose neutral   = {bendX(0),  bendX(0),  bendX(0),  bendX(0),   bendX(0),  bendX(0)};
    Mask upperBody = {0.0f, 1.0f, 1.0f, 1.0f, 0.0f, 0.0f};   // spine and everything above it
    Mask everything(6, 1.0f);

    std::printf("%-22s", "joint (degrees)");
    for (const char* name : kJointNames) std::printf("%7s", name);
    std::printf("\n");
    printPose("run (base)", run);
    printPose("aim, upper-body mask", overrideLayer(run, aim, upperBody, 1.0f));
    printPose("aim, no mask", overrideLayer(run, aim, everything, 1.0f));
    printPose("aim at weight 0.5", overrideLayer(run, aim, upperBody, 0.5f));
    printPose("run + lean", additiveLayer(run, leanClip, neutral, everything, 1.0f));
    printPose("aim + lean", additiveLayer(overrideLayer(run, aim, upperBody, 1.0f),
                                          leanClip, neutral, everything, 1.0f));
}

// Layering poses per joint in local space: an override layer replaces the
// masked joints, an additive layer adds a delta measured from a reference pose.
// Rotations only; translations and scales blend the same way with lerp.
use std::f32::consts::PI;

#[derive(Clone, Copy)]
struct Quat { w: f32, x: f32, y: f32, z: f32 }

fn multiply(a: Quat, b: Quat) -> Quat {
    Quat {
        w: a.w * b.w - a.x * b.x - a.y * b.y - a.z * b.z,
        x: a.w * b.x + a.x * b.w + a.y * b.z - a.z * b.y,
        y: a.w * b.y - a.x * b.z + a.y * b.w + a.z * b.x,
        z: a.w * b.z + a.x * b.y - a.y * b.x + a.z * b.w,
    }
}
fn conjugate(rotation: Quat) -> Quat { Quat { w: rotation.w, x: -rotation.x, y: -rotation.y, z: -rotation.z } } // the inverse, for a unit quaternion

// Normalized lerp: cheap, and close to slerp for the small angles between poses.
fn nlerp(a: Quat, b: Quat, weight: f32) -> Quat {
    let dot = a.w * b.w + a.x * b.x + a.y * b.y + a.z * b.z;
    let sign = if dot < 0.0 { -1.0 } else { 1.0 }; // q and -q are the same rotation: take the short way
    let blended = Quat {
        w: a.w + (sign * b.w - a.w) * weight, x: a.x + (sign * b.x - a.x) * weight,
        y: a.y + (sign * b.y - a.y) * weight, z: a.z + (sign * b.z - a.z) * weight,
    };
    let length = (blended.w * blended.w + blended.x * blended.x +
                  blended.y * blended.y + blended.z * blended.z).sqrt();
    Quat { w: blended.w / length, x: blended.x / length, y: blended.y / length, z: blended.z / length }
}

// Every joint in this example bends about the x axis, so one angle describes it.
fn bend_x(degrees: f32) -> Quat {
    let half = degrees * PI / 360.0;
    Quat { w: half.cos(), x: half.sin(), y: 0.0, z: 0.0 }
}
fn angle_x(rotation: Quat) -> f32 { 2.0 * rotation.x.atan2(rotation.w) * 180.0 / PI }

type Pose = Vec<Quat>; // one local rotation per joint
type Mask = Vec<f32>;  // one weight per joint, 0..1

// Override: each joint moves toward the layer's rotation by weight * mask.
fn override_layer(base: &Pose, layer: &Pose, mask: &Mask, weight: f32) -> Pose {
    (0..base.len()).map(|joint| nlerp(base[joint], layer[joint], weight * mask[joint])).collect()
}

// Additive: the delta is what the additive clip changes relative to its own
// reference pose. Scaled by weight * mask, it is applied on top of any base.
fn additive_layer(base: &Pose, additive: &Pose, reference: &Pose, mask: &Mask, weight: f32) -> Pose {
    let identity = Quat { w: 1.0, x: 0.0, y: 0.0, z: 0.0 };
    (0..base.len())
        .map(|joint| {
            let delta = multiply(conjugate(reference[joint]), additive[joint]);
            multiply(base[joint], nlerp(identity, delta, weight * mask[joint]))
        })
        .collect()
}

const JOINT_NAMES: [&str; 6] = ["pelvis", "spine", "chest", "arm", "thigh", "shin"];

fn print_pose(label: &str, pose: &Pose) {
    print!("{label:<22}");
    for rotation in pose { print!("{:7.1}", angle_x(*rotation)); }
    println!();
}

fn main() {
    // One frame of a run, an aiming pose, and a lean authored against a neutral stance.
    let run: Pose       = [5.0, 8.0, 4.0, -40.0, 35.0, -60.0].map(bend_x).to_vec();
    let aim: Pose       = [0.0, 2.0, 6.0, 85.0, 0.0, -5.0].map(bend_x).to_vec();
    let lean_clip: Pose = [0.0, 12.0, 3.0, 0.0, 0.0, 0.0].map(bend_x).to_vec();
    let neutral: Pose   = [0.0; 6].map(bend_x).to_vec();
    let upper_body: Mask = vec![0.0, 1.0, 1.0, 1.0, 0.0, 0.0]; // spine and everything above it
    let everything: Mask = vec![1.0; 6];

    print!("{:<22}", "joint (degrees)");
    for name in JOINT_NAMES { print!("{name:>7}"); }
    println!();
    print_pose("run (base)", &run);
    print_pose("aim, upper-body mask", &override_layer(&run, &aim, &upper_body, 1.0));
    print_pose("aim, no mask", &override_layer(&run, &aim, &everything, 1.0));
    print_pose("aim at weight 0.5", &override_layer(&run, &aim, &upper_body, 0.5));
    print_pose("run + lean", &additive_layer(&run, &lean_clip, &neutral, &everything, 1.0));
    print_pose("aim + lean", &additive_layer(&override_layer(&run, &aim, &upper_body, 1.0),
                                             &lean_clip, &neutral, &everything, 1.0));
}

05Motion matching

Hand-authoring a state and a tuned transition for every start, stop, turn and foot plant gets expensive as the move set grows. (Büttner and Clavet at Ubisoft, shipped in For Honor) is a data-driven alternative to a hand-built state machine^[11]^[12]. Instead of authoring states and transitions, you keep a database of mocap frames, each tagged with a feature vector (the future trajectory, plus foot positions/velocities and hip velocity). Each search builds a query vector from the desired trajectory plus the current pose, finds the nearest database frame by a weighted cost, and blends to it (For Honor cross-faded; later systems often use inertialization).

Holden and colleagues' paper on Learned Motion Matching spells out a concrete version, the one the authors say is used in several AAA game productions^[12]. Every frame of the database gets a feature vector of 27 numbers, all measured relative to the character: where its root will be on the ground 20, 40 and 60 frames ahead at 60 Hz (6 numbers), which way it will face then (6), its two feet's positions (6) and velocities (6), and its hip velocity (3). Because metres, unit directions and velocities have very different ranges, each feature is divided by its standard deviation over the database before distances are taken. Every few frames, or when the stick moves sharply, the game builds a query in the same format (the trajectory part from a spring-damper prediction of the stick, the pose part from the frame playing now) and searches for the frame with the smallest squared distance. If that beats the frame already playing, playback jumps there and an inertialization blend hides the jump^[12].

Worked example

Twenty minutes of mocap at 60 frames a second is 72,000 frames. With 27 numbers per frame, a brute-force search compares the query against 72,000 × 27 ≈ 1.9 million numbers. That's why searches run every few frames rather than every frame, and why production systems add an acceleration structure. The Learned Motion Matching paper names a KD-tree (citing Clavet's talk) among the options and itself uses bounding boxes around runs of 16 and 64 consecutive frames, skipping any box whose nearest point is already farther than the best match so far^[12].

The widget and the listing below shrink this to root motion only: how the character travels across the ground, with no skeleton. Nine synthetic clips (idle, walk, run, turns at two speeds, a start and a stop) are generated as ground trajectories at 60 Hz. Each frame's feature vector has 13 numbers: the same 6 numbers of future position and 6 of future facing as above, plus the current speed. That leaves 1,380 frames that can be matched, since the last second of each clip has no full second of future to describe.

Top-down: the character walks the grid, the amber rings are the query (where the wanted motion would take it 1/3, 2/3 and 1 s from now), and the green dots are where the playing frame's own motion goes. On a wide screen the side panel shows which clip and frame are playing. Let the auto stick run, then drop the search rate to 1 a second and set the stick by hand. When the green dots sit on the amber rings, the playing frame already does what's wanted. After the stick changes, the character keeps playing the old clip until the next search, so at 1 search a second it can keep running straight for up to a second after you ask for a turn. Ask for 3 m/s turning right at 30°/s and no clip matches exactly: the search settles on the run turning right, the closest frame by the scaled distance. This widget searches only on its schedule; a production system also searches when the stick changes sharply.

Motion matching search: features, per-group scaling, brute force with early out (complete program)

// Motion matching, the search step: describe every database frame with a
// feature vector, scale each feature group by its spread so none dominates,
// then find the frame closest to a query. Root motion only, no skeleton.
#include <array>
#include <cmath>
#include <cstdio>
#include <limits>
#include <numbers>
#include <string>
#include <vector>

constexpr int kFps = 60;
constexpr int kFutureFrames[3] = {20, 40, 60};   // 1/3, 2/3 and 1 s ahead
constexpr int kFeatureCount = 13;               // 6 trajectory positions, 6 facings, 1 speed
using Features = std::array<float, kFeatureCount>;
constexpr float kRadiansPerDegree = std::numbers::pi_v<float> / 180.0f;

// A clip's root motion, one sample per frame. Facing is the direction
// (sin yaw, cos yaw) on the ground; a positive turn rate turns right.
struct Clip { std::string name; std::vector<float> x, z, yaw, speed; };

template <class SpeedFn, class TurnFn>
Clip makeClip(std::string name, float seconds, SpeedFn speedAt, TurnFn turnDegreesAt) {
    Clip clip{std::move(name), {}, {}, {}, {}};
    float x = 0, z = 0, yaw = 0;
    for (int frame = 0; frame < static_cast<int>(seconds * kFps); ++frame) {
        float time = static_cast<float>(frame) / kFps, speed = speedAt(time);
        clip.x.push_back(x); clip.z.push_back(z); clip.yaw.push_back(yaw); clip.speed.push_back(speed);
        yaw += turnDegreesAt(time) * kRadiansPerDegree / kFps;
        x += std::sin(yaw) * speed / kFps;
        z += std::cos(yaw) * speed / kFps;
    }
    return clip;
}

// Everything is measured in the character's own frame (x right, z forward),
// so a left turn looks the same wherever the character stands.
Features featuresAt(const Clip& clip, int frame) {
    Features features{};
    float cosYaw = std::cos(clip.yaw[frame]), sinYaw = std::sin(clip.yaw[frame]);
    for (int k = 0; k < 3; ++k) {
        int future = frame + kFutureFrames[k];
        float dx = clip.x[future] - clip.x[frame], dz = clip.z[future] - clip.z[frame];
        features[2 * k]     = dx * cosYaw - dz * sinYaw;           // to the right
        features[2 * k + 1] = dx * sinYaw + dz * cosYaw;           // ahead
        float turned = clip.yaw[future] - clip.yaw[frame];
        features[6 + 2 * k]     = std::sin(turned);                // future facing, local
        features[6 + 2 * k + 1] = std::cos(turned);
    }
    features[12] = clip.speed[frame];
    return features;
}

constexpr int groupOf(int feature) { return feature < 6 ? 0 : feature < 12 ? 1 : 2; }

struct Database {
    std::vector<Features> rows;
    std::vector<int> clipOf, frameOf;
    std::array<float, 3> groupScale{};          // 1 / standard deviation of each feature group

    explicit Database(const std::vector<Clip>& clips) {
        for (int clipIndex = 0; clipIndex < static_cast<int>(clips.size()); ++clipIndex)
            // Only frames with a full second of future can be described, so the last 60 can't be matched.
            for (int frame = 0; frame + kFutureFrames[2] < static_cast<int>(clips[clipIndex].x.size()); ++frame) {
                rows.push_back(featuresAt(clips[clipIndex], frame));
                clipOf.push_back(clipIndex); frameOf.push_back(frame);
            }
        // Metres, unit vectors and m/s have different spreads; without scaling, the
        // positions (up to 4 m) would swamp the facings (at most 2 apart).
        std::array<double, kFeatureCount> mean{};
        for (const Features& row : rows) for (int d = 0; d < kFeatureCount; ++d) mean[d] += row[d] / static_cast<double>(rows.size());
        std::array<double, 3> variance{}, count{};
        for (const Features& row : rows)
            for (int d = 0; d < kFeatureCount; ++d) {
                variance[groupOf(d)] += (row[d] - mean[d]) * (row[d] - mean[d]);
                count[groupOf(d)] += 1;
            }
        for (int group = 0; group < 3; ++group)
            groupScale[group] = static_cast<float>(1.0 / std::sqrt(variance[group] / count[group]));
    }

    // Brute force: one scaled squared distance per frame.
    int search(const Features& query, float& bestCost) const {
        int best = -1;
        bestCost = std::numeric_limits<float>::max();
        for (int row = 0; row < static_cast<int>(rows.size()); ++row) {
            float cost = 0;
            for (int d = 0; d < kFeatureCount; ++d) {
                float difference = (query[d] - rows[row][d]) * groupScale[groupOf(d)];
                cost += difference * difference;
                if (cost >= bestCost) break;                         // can't win: stop early
            }
            if (cost < bestCost) { bestCost = cost; best = row; }
        }
        return best;
    }
};

// A query from desired motion: where the character would be over the next second
// if it held this speed and turn rate. Games predict this from the stick with a spring.
Features queryFor(float speed, float turnDegreesPerSecond) {
    Clip prediction = makeClip("query", 1.1f, [=](float) { return speed; },
                               [=](float) { return turnDegreesPerSecond; });
    return featuresAt(prediction, 0);
}

int main() {
    auto constant = [](float value) { return [=](float) { return value; }; };
    std::vector<Clip> clips = {
        makeClip("idle", 2, constant(0.0f), constant(0.0f)),
        makeClip("walk", 4, constant(1.4f), constant(0.0f)),
        makeClip("run", 4, constant(4.0f), constant(0.0f)),
        makeClip("walk_turn_right", 4, constant(1.4f), constant(60.0f)),
        makeClip("walk_turn_left", 4, constant(1.4f), constant(-60.0f)),
        makeClip("run_turn_right", 4, constant(4.0f), constant(45.0f)),
        makeClip("run_turn_left", 4, constant(4.0f), constant(-45.0f)),
        makeClip("start", 3, [](float seconds) { return 1.4f * std::fmin(1.0f, seconds); }, constant(0.0f)),
        makeClip("stop", 3, [](float seconds) { return 1.4f * std::fmin(1.0f, std::fmax(0.0f, 2.0f - seconds)); }, constant(0.0f)),
    };
    Database database(clips);
    std::printf("%zu matchable frames x %d features = %zu multiply-adds per full search\n",
                database.rows.size(), kFeatureCount, database.rows.size() * kFeatureCount);

    float cost = 0;
    int known = 700;                                               // a query copied from the database finds itself
    int found = database.search(database.rows[known], cost);
    std::printf("row %d -> row %d, cost %.3f\n", known, found, cost);

    const float wishes[][2] = {{1.4f, 0}, {4.0f, 0}, {1.4f, -60}, {3.0f, 30}, {0.0f, 0}};
    for (const auto& wish : wishes) {
        int row = database.search(queryFor(wish[0], wish[1]), cost);
        std::printf("want %.1f m/s turning %+4.0f deg/s -> %-15s frame %3d, cost %.3f\n", wish[0], wish[1],
                    clips[database.clipOf[row]].name.c_str(), database.frameOf[row], cost);
    }
}

// Motion matching, the search step: describe every database frame with a
// feature vector, scale each feature group by its spread so none dominates,
// then find the frame closest to a query. Root motion only, no skeleton.
const FPS: usize = 60;
const FUTURE_FRAMES: [usize; 3] = [20, 40, 60]; // 1/3, 2/3 and 1 s ahead
const FEATURE_COUNT: usize = 13;                // 6 trajectory positions, 6 facings, 1 speed
type Features = [f32; FEATURE_COUNT];

// A clip's root motion, one sample per frame. Facing is the direction
// (sin yaw, cos yaw) on the ground; a positive turn rate turns right.
struct Clip { name: String, x: Vec<f32>, z: Vec<f32>, yaw: Vec<f32>, speed: Vec<f32> }

fn make_clip(name: &str, seconds: f32, speed_at: impl Fn(f32) -> f32, turn_degrees_at: impl Fn(f32) -> f32) -> Clip {
    let mut clip = Clip { name: name.to_string(), x: vec![], z: vec![], yaw: vec![], speed: vec![] };
    let (mut x, mut z, mut yaw) = (0.0_f32, 0.0_f32, 0.0_f32);
    for frame in 0..(seconds * FPS as f32) as usize {
        let time = frame as f32 / FPS as f32;
        let speed = speed_at(time);
        clip.x.push(x); clip.z.push(z); clip.yaw.push(yaw); clip.speed.push(speed);
        yaw += turn_degrees_at(time).to_radians() / FPS as f32;
        x += yaw.sin() * speed / FPS as f32;
        z += yaw.cos() * speed / FPS as f32;
    }
    clip
}

// Everything is measured in the character's own frame (x right, z forward),
// so a left turn looks the same wherever the character stands.
fn features_at(clip: &Clip, frame: usize) -> Features {
    let mut features = [0.0; FEATURE_COUNT];
    let (cos_yaw, sin_yaw) = (clip.yaw[frame].cos(), clip.yaw[frame].sin());
    for (k, &ahead) in FUTURE_FRAMES.iter().enumerate() {
        let future = frame + ahead;
        let (dx, dz) = (clip.x[future] - clip.x[frame], clip.z[future] - clip.z[frame]);
        features[2 * k] = dx * cos_yaw - dz * sin_yaw;         // to the right
        features[2 * k + 1] = dx * sin_yaw + dz * cos_yaw;     // ahead
        let turned = clip.yaw[future] - clip.yaw[frame];
        features[6 + 2 * k] = turned.sin();                    // future facing, local
        features[6 + 2 * k + 1] = turned.cos();
    }
    features[12] = clip.speed[frame];
    features
}

const fn group_of(feature: usize) -> usize { if feature < 6 { 0 } else if feature < 12 { 1 } else { 2 } }

struct Database { rows: Vec<Features>, clip_of: Vec<usize>, frame_of: Vec<usize>, group_scale: [f32; 3] }

impl Database {
    fn new(clips: &[Clip]) -> Database {
        let (mut rows, mut clip_of, mut frame_of) = (vec![], vec![], vec![]);
        for (clip_index, clip) in clips.iter().enumerate() {
            // Only frames with a full second of future can be described, so the last 60 can't be matched.
            for frame in 0..clip.x.len().saturating_sub(FUTURE_FRAMES[2]) {
                rows.push(features_at(clip, frame));
                clip_of.push(clip_index); frame_of.push(frame);
            }
        }
        // Metres, unit vectors and m/s have different spreads; without scaling, the
        // positions (up to 4 m) would swamp the facings (at most 2 apart).
        let mut mean = [0.0_f64; FEATURE_COUNT];
        for row in &rows { for d in 0..FEATURE_COUNT { mean[d] += row[d] as f64 / rows.len() as f64; } }
        let (mut variance, mut count) = ([0.0_f64; 3], [0.0_f64; 3]);
        for row in &rows {
            for d in 0..FEATURE_COUNT {
                variance[group_of(d)] += (row[d] as f64 - mean[d]).powi(2);
                count[group_of(d)] += 1.0;
            }
        }
        let group_scale = [0, 1, 2].map(|group| (1.0 / (variance[group] / count[group]).sqrt()) as f32);
        Database { rows, clip_of, frame_of, group_scale }
    }

    // Brute force: one scaled squared distance per frame.
    fn search(&self, query: &Features) -> (usize, f32) {
        let (mut best, mut best_cost) = (usize::MAX, f32::MAX);
        for (row_index, row) in self.rows.iter().enumerate() {
            let mut cost = 0.0;
            for d in 0..FEATURE_COUNT {
                let difference = (query[d] - row[d]) * self.group_scale[group_of(d)];
                cost += difference * difference;
                if cost >= best_cost { break; }                     // can't win: stop early
            }
            if cost < best_cost { best_cost = cost; best = row_index; }
        }
        (best, best_cost)
    }
}

// A query from desired motion: where the character would be over the next second
// if it held this speed and turn rate. Games predict this from the stick with a spring.
fn query_for(speed: f32, turn_degrees_per_second: f32) -> Features {
    let prediction = make_clip("query", 1.1, |_| speed, |_| turn_degrees_per_second);
    features_at(&prediction, 0)
}

fn main() {
    let constant = |value: f32| move |_: f32| value;
    let clips = vec![
        make_clip("idle", 2.0, constant(0.0), constant(0.0)),
        make_clip("walk", 4.0, constant(1.4), constant(0.0)),
        make_clip("run", 4.0, constant(4.0), constant(0.0)),
        make_clip("walk_turn_right", 4.0, constant(1.4), constant(60.0)),
        make_clip("walk_turn_left", 4.0, constant(1.4), constant(-60.0)),
        make_clip("run_turn_right", 4.0, constant(4.0), constant(45.0)),
        make_clip("run_turn_left", 4.0, constant(4.0), constant(-45.0)),
        make_clip("start", 3.0, |seconds| 1.4 * seconds.min(1.0), constant(0.0)),
        make_clip("stop", 3.0, |seconds| 1.4 * (2.0 - seconds).clamp(0.0, 1.0), constant(0.0)),
    ];
    let database = Database::new(&clips);
    println!("{} matchable frames x {} features = {} multiply-adds per full search",
             database.rows.len(), FEATURE_COUNT, database.rows.len() * FEATURE_COUNT);

    let known = 700; // a query copied from the database finds itself
    let (found, cost) = database.search(&database.rows[known]);
    println!("row {known} -> row {found}, cost {cost:.3}");

    let wishes = [(1.4, 0.0), (4.0, 0.0), (1.4, -60.0), (3.0, 30.0), (0.0, 0.0)];
    for (speed, turn) in wishes {
        let (row, cost) = database.search(&query_for(speed, turn));
        println!("want {speed:.1} m/s turning {turn:+4.0} deg/s -> {:<15} frame {:3}, cost {cost:.3}",
                 clips[database.clip_of[row]].name, database.frame_of[row]);
    }
}

The output shows the parts working: a query copied from row 700 finds row 700 at cost 0; wishes that match a clip exactly find it at cost 0 (at frame 0, since every frame of a constant clip looks the same); and 3 m/s turning right at 30°/s, which no clip covers, lands in the run turning right at cost 4.2. The early out stops summing a row as soon as its partial cost passes the best so far, the same trick the bounding-box search relies on.

What's intentionally missing

The listing keeps only the search. A production matcher also has:

pose features (foot positions and velocities, hip velocity) read from the skeleton, so a jump lands on a frame whose legs match the ones on screen;
a query trajectory predicted from the stick by a spring, instead of a fixed speed and turn rate;
per-group weights on top of the scaling, tuned by hand;
an acceleration structure (bounding boxes or a KD-tree) instead of a full scan;
tags or database ranges that limit the search to the gait or action the game asks for;
an inertialization blend on every jump, and a search whenever the stick changes sharply.

Not free, and it didn't kill the state machine

The search often runs only a few times a second rather than every frame (O3DE's implementation, for one^[13]); between searches the chosen clip simply plays, and a blend smooths each jump. It's not authoring-free: someone has to capture and curate a large, clean mocap database, shot from a scripted "dance card" of walks, plants, and strafes at a spread of angles. The nearest-neighbor search has real cost, usually cut with KD-trees or similar structures^[13]. And it does not replace state machines everywhere: in For Honor the game logic still ran as a simple timed state machine, which requested motion from the matcher^[11]. Feature-vector contents vary by engine; there is no single canonical schema.

06IK in depth

The animation was authored on flat ground, but the character is on a staircase, reaching for a ledge, or looking at the player. Forward kinematics gives positions from angles; finds the angles to reach a target. Two-bone IK (covered in Skeletal Animation) is analytic and exact^[14]: the law of cosines gives the knee or elbow angle from the two bone lengths and the distance to the target, and a pole vector picks which way the joint points. General chains use iterative solvers:

FABRIK (Aristidou & Lasenby): a forward pass (end effector → root) and a backward pass (root → end effector), each placing joints on a line at the original bone lengths. In the authors' benchmarks it needed fewer iterations and less time than CCD and Jacobian methods^[15].
CCD (cyclic coordinate descent): rotate one joint at a time, end → root, to aim the end effector at the target; iterate. Simple and cheap per step, but each joint is solved in isolation, so it can stall in local minima and produce unnatural poses^[16]^[15].
Jacobian methods: linearize end-effector motion against joint angles and step (transpose, pseudo-inverse, or damped least squares); smooth, handles many DOF, but costlier per iteration and unstable near singular poses unless damped.

Iterative solvers are approximate, clamp on unreachable, and FABRIK must reset the root

Unlike two-bone, FABRIK and CCD converge over iterations (more iterations: closer, but more cost) and can't reach an unreachable target; clamp to max reach (FABRIK stretches the chain straight at the target in one pass). FABRIK's backward pass must reset the root to its anchor; skip it and the whole chain drifts off. Foot IK is a combination: raycast down per foot, lower the pelvis so the lower foot can reach its ground point, run two-bone leg IK to plant each foot, and aim the ankle to the surface normal^[17]. Then interpolate the offsets over time; applied instantly, the legs snap every time the ground height changes. Look-at distributes rotation across spine joints with limits (no 180° head snaps). IK runs after the pose is produced and before the palette is built, adjusting that pose (usually with a blend weight) rather than generating one.

FABRIK (forward + backward passes; the backward pass resets the root)

// positions[0] = root (anchored); positions[n-1] = end effector.
// boneLengths[i] is the distance from joint i to joint i+1, captured at bind time.
void solveFABRIK(std::vector<vec3>& positions, const std::vector<float>& boneLengths,
                 vec3 target, int maxIterations = 10, float tolerance = 1e-3f) {
    const size_t n = positions.size(); const vec3 root = positions[0];
    float reach = 0; for (float boneLength : boneLengths) reach += boneLength;
    if (length(target - root) > reach) {                 // UNREACHABLE: stretch straight (1 pass)
        for (size_t i = 0; i + 1 < n; ++i)
            positions[i+1] = positions[i] + normalize(target - positions[i]) * boneLengths[i];
        return;
    }
    for (int iteration = 0; iteration < maxIterations; ++iteration) {
        if (length(positions[n-1] - target) < tolerance) break;   // converged
        positions[n-1] = target;                        // FORWARD: end effector onto target, then inward
        for (int i = (int)n-2; i >= 0; --i)       // keep each joint on the line to its child, at bone length
            positions[i] = positions[i+1] + normalize(positions[i] - positions[i+1]) * boneLengths[i];
        positions[0] = root;                            // BACKWARD: reset the root (critical!), then outward
        for (size_t i = 0; i + 1 < n; ++i)
            positions[i+1] = positions[i] + normalize(positions[i+1] - positions[i]) * boneLengths[i];
    }
}

// positions[0] = root (anchored); positions[n-1] = end effector.
// bone_lengths[i] is the distance from joint i to joint i+1, captured at bind time.
fn solve_fabrik(positions: &mut [Vec3], bone_lengths: &[f32], target: Vec3,
                max_iterations: u32, tolerance: f32) {
    let n = positions.len(); let root = positions[0];
    let reach: f32 = bone_lengths.iter().sum();
    if (target - root).length() > reach {                // UNREACHABLE: stretch straight (1 pass)
        for i in 0..n - 1 {
            positions[i + 1] = positions[i] + (target - positions[i]).normalize() * bone_lengths[i];
        }
        return;
    }
    for _iteration in 0..max_iterations {
        if (positions[n - 1] - target).length() < tolerance { break; }   // converged
        positions[n - 1] = target;                      // FORWARD: end effector onto target, then inward
        for i in (0..n - 1).rev() {                 // keep each joint on the line to its child, at bone length
            positions[i] = positions[i + 1] + (positions[i] - positions[i + 1]).normalize() * bone_lengths[i];
        }
        positions[0] = root;                            // BACKWARD: reset the root (critical!), then outward
        for i in 0..n - 1 {
            positions[i + 1] = positions[i] + (positions[i + 1] - positions[i]).normalize() * bone_lengths[i];
        }
    }
}

Worked example

Two 1 m bones lie along x, from a root at (0, 0), and the target is (0.5, 1.2), 1.3 m away and within reach. The forward pass puts the tip on the target, pulls the middle joint to (0.885, 0.277), and drags the root to (−0.07, −0.02), off its anchor. The backward pass puts the root back at (0, 0) and pushes outward: the middle joint lands at (0.954, 0.299) and the tip at (0.504, 1.192), 9.3 mm short. A second iteration brings the miss to 0.2 mm. Skip the root reset and the next forward pass starts from the dragged root, and the arm walks away from the shoulder.

The widget runs that loop on a five-bone chain:

A six-joint chain anchored at the white root, with its maximum reach drawn as a faint circle. The target starts outside that circle, so the chain loads stretched straight at it; drag the target inside, then out again. The chain runs FABRIK (forward then backward passes) to reach it, one iteration every 0.12 s, and the readout counts iterations for the current target and the end-to-target distance. A target well inside the circle typically settles within a pixel in a few iterations. Pull the target out of range and the chain stretches straight at it in a single pass, with the distance stuck above zero: the unreachable case, clamped to max reach.

07Combining it all

Each stage above is easy to get right on its own; the bugs appear when they run in the wrong order, such as IK before layering, which lets the reload layer overwrite the planted arm. The full per-frame animation pipeline, end to end:

A state machine or motion matching produces a base local pose.
Layers blend on top (masked override + additive deltas).
IK adjusts the result (foot plant, look-at, hand reach), modifying the pose.
Recompute globals from the local pose (walk the hierarchy).
Build the matrix palette and skin in the vertex shader (the Skeletal Animation module).

Every stage here is upstream of the palette; the skeletal module is where it all lands. The behavior tree (or other AI) sits one level up again: it sets the parameters and conditions that drive the state machine's transitions.

Wrong answers, and why: a transition pop is a missing cross-fade (not clip length; and you blend local TRS, never global matrices); FABRIK is iterative/approximate with a root-reset in the backward pass (it isn't exact, and you clamp unreachable targets rather than stretch bones); inertialization samples only the destination; and feature scaling balances the groups rather than speeding up the search.

08Pitfalls

Hard-cut transitionsPop. A transition is a timed cross-fade (or inertialization).

Blending global matricesNon-rigid in-betweens. Blend local TRS, then recompute globals.

2D blend as two 1D blendsWrong off the axes. Use a real 2D scheme (gradient band).

Inertialization without velocityRecord only the position gap and the joint's speed snaps to the new clip's at the switch, a visible kink. Record the velocity difference too.

Layer without a maskUpper and lower body fight. Mask which joints a layer drives.

Mismatched additive conventionsBuild and apply the delta on the same side: reference⁻¹ · pose with base · delta, or pose · reference⁻¹ with delta · base. Mix them and the lean turns about the wrong axis.

Unscaled featuresMetres swamp unit vectors in the distance. Divide each feature group by its standard deviation.

Matching the clip's last secondA frame without a full future can't be described. Leave it out of the search.

"Motion matching needs no authoring"It needs a curated mocap database and tuned costs; game logic can stay a state machine.

FABRIK without the root resetThe chain drifts off its anchor. Reset the root in the backward pass.

Instant foot IKLegs snap on every step change. Raycast + pelvis drop + leg IK, interpolated over time.

"FABRIK is exact"It's iterative; it clamps on unreachable. Two-bone is the exact one.

09What's next

That's the upstream half of character animation: decide the pose (state machine or motion matching), blend and layer it, and adjust it with IK, all feeding the matrix palette. The series continues with Physics Simulation; the full map is on the series hub.

Jason Gregory. Game Engine Architecture, 3rd ed., "Animation Systems." gameenginebook.com. Clips, blend trees, layered/additive blending, and the action state machine.
Epic Games. "State Machines" and "Transition Rules" (Unreal Engine). dev.epicgames.com; transition rules. States with their own AnimGraph layer; transition blend settings; Standard Blend, Inertialization, and Custom blend logic.
Unity Technologies. "State machine basics" and "2D Blending." docs.unity3d.com; 2D blending. States and transitions that define how long the blend between states takes; the Simple Directional, Freeform Directional, and Freeform Cartesian 2D blend types.
David Bollo. "Inertialization: High-Performance Animation Transitions in Gears of War." GDC 2018. gdcvault.com. Handling transitions as a decaying offset applied to the destination pose instead of evaluating two pose graphs (Gears of War 4).
Daniel Holden. "Spring-It-On: The Game Developer's Spring-Roll-Call." 2021. theorangeduck.com. Critically damped springs parameterized by halflife, and inertialization as a spring-decayed offset (the listing's transition and decaySpring).
Epic Games. "Animation Blueprint Blend Nodes in Unreal Engine." dev.epicgames.com. Layered Blend per Bone with branch filters and blend depth; Apply Additive; Inertialization and Dead Blending nodes.
Daniel Holden. "Dead Blending." 2023. theorangeduck.com. Extrapolate the source clip past the switch and cross-fade from it; needs only the current pose and its velocity.
Rune Skovbo Johansen. Automated Semi-Procedural Animation for Character Locomotion (MSc thesis, 2009), §6.3 Gradient Band Interpolation. runevision.com. The gradient band weight formula behind Unity's freeform 2D blend types; the Cartesian and polar variants; why other scattered-data schemes fall short.
Unity Technologies. "Animation Layers." docs.unity3d.com. A layer's mask picks the body parts it drives; its blending type is Override or Additive.
Guillaume Blanc. ozz-animation, additive_animation_builder.cc and blending_job.cc. github.com. Additive rotation delta built as Conjugate(reference) * value and applied as output * nlerp(identity, delta, weight).
Simon Clavet. "Motion Matching and The Road to Next-Gen Animation." GDC 2016 (Ubisoft, For Honor). gdcvault.com. Runtime search for the frame matching the current pose and desired future trajectory; game logic kept as a simple timed state machine that requests motion.
Daniel Holden, Oussama Kanoun, Maksym Perepichka, Tiberiu Popa. "Learned Motion Matching." ACM Transactions on Graphics 39(4), SIGGRAPH 2020. doi.org/10.1145/3386569.3392440. §2.2: motion matching first presented by Büttner and Clavet and developed for For Honor; §3: the 27-number locomotion feature vector, scaling by standard deviation, searching every N frames, jumping only to a cheaper frame with inertialization; Appendix B: bounding boxes over 16 and 64 frames.
O3DE. "Motion Matching in O3DE, a Data-Driven Animation Technique." docs.o3de.org. A concrete feature schema, KD-tree search, and a search that runs a few times per second.
Daniel Holden. "Simple Two Joint IK." theorangeduck.com. The analytic two-bone IK (law of cosines + bend axis) this module recaps.
Andreas Aristidou and Joan Lasenby. "FABRIK: A fast, iterative solver for the Inverse Kinematics problem." Graphical Models 73(5), 2011. andreasaristidou.com. The forward (end effector inward) and backward (root outward) point-on-line passes; benchmarks against CCD and Jacobian methods; unreachable targets handled in one pass.
Ryan Juckett. "Cyclic Coordinate Descent in 2D." ryanjuckett.com. CCD: iterate joints end to root, rotating each to aim the end effector at the target; its local-minimum failure case.
Guillaume Blanc. ozz-animation "foot_ik" sample. guillaumeblanc.github.io. Raycast per leg, lower the character so the lowest ankle reaches its target, two-bone leg IK, then aim each ankle to the floor normal.

01Where this fits

02The state machine

Inertialization: one pose instead of two

03Blend spaces

04Layered animation

05Motion matching

06IK in depth

07Combining it all

08Pitfalls

09What's next

See also