You have captured a big pile of motion: an actor in a suit dotted with markers, wandering a studio for an afternoon — a walk here, a turn there, a jog, a stop, a look-around. It is gorgeous, human, real motion. But it is also fixed: each clip plays exactly the path the actor happened to take. Your game needs the character to walk to that door, then turn and jog to this waypoint — a route the actor never performed. How do you get new, controllable motion out of a finite library of old clips, without it ever looking synthetic?

The answer, from two landmark 2002 papers (Kovar, Gleicher & Pighin's Motion Graphs and Arikan & Forsyth's Interactive Motion Generation from Examples), is to stop thinking of the database as a list of clips and start thinking of it as a graph you can walk. Every frame the character ever performed becomes a place you might be; wherever two moments look similar enough, you build a bridge between them; and then synthesising motion becomes finding a path. This page builds that idea from the ground up, works a concrete pose-distance example, and shows how a graph search turns "walk to that door in three seconds" into an answer.

The core idea: motion as a graph

Lay all your captured clips end to end as strips of frames. A motion graph reinterprets those strips: the edges are pieces of original, untouched motion (a run of consecutive frames), and the nodes are the points between pieces where you are allowed to jump from one clip to another. A node is a choice point; an edge is a stretch of guaranteed-real motion you play through until the next choice.

The magic is that every edge is real captured motion. Nothing on an edge was invented — it is exactly what the actor did. The only synthetic moments are the short blended transitions at the nodes, and if we only ever place nodes where two frames genuinely match, even those are imperceptible. We get endless novel routes out of finite footage, all of it still looking human.

A picture of a tiny graph

Below is a toy motion graph. Each labelled node is a frame where clips can meet; the plain arrows are the original clips (walk, jog, turn) playing forward through their frames; the highlighted arrow is a transition edge — a bridge discovered because the frame at its tail looked very like the frame at its head. A character controller lives on this graph: it plays along an edge, and at each node it may continue or take a transition, weaving the short clips into arbitrarily long, varied motion.

Read a route off it: enter the walk, at its end take the highlighted transition into the jog, run the jog, loop back through the turn — you have just produced a walk-then-jog-then-turn performance the actor never recorded in that order. Different constraints pick different walks through the same graph.

Where do transitions come from? A pose-distance metric

A transition is only allowed between two frames that are genuinely alike, so we need to measure how alike two poses are. The workhorse is a pose distance: put the skeleton's joints as 3-D points and compare them. Write frame i as its set of joint positions p^i_1, \dots, p^i_m. A first, simple distance is the sum of squared joint differences:

But raw positions are in world space, so a walk heading north and an identical walk heading east would look far apart just because they sit in different places and face different ways. That is wrong: pose similarity should not care where the character is or which way it faces. So before comparing, we align frame j to frame i with the rigid 2-D transform T_{\theta, x_0, z_0} (a rotation about the vertical axis plus a ground-plane translation) that best matches them, making the metric invariant to global position and heading:

Two refinements matter. First, we compare over a short window of frames rather than a single instant, so the motions match in direction of travel, not just static pose — this is what folds velocity into the metric. Second, the weights w_k let heavy, visually dominant joints (torso, feet) count for more than fingertips. Wherever D(i, j) falls below a threshold \tau, we mint a transition edge between frames i and j and blend across the window.

Worked example: computing a transition

Let us do the arithmetic with a cartoon 3-joint skeleton (hip, foot, hand) to see a threshold create an edge. Take two frames, already root-aligned so we can just subtract coordinates. Positions in metres:

The hip matches exactly; the foot differs by 0.1 m in x so contributes 0.1^2 = 0.01; the hand differs by 0.1 m in z so contributes another 0.01. Summing:

With a threshold of, say, \tau = 0.05\ \text{m}^2, we have D(A,B) = 0.02 < 0.05, so the poses are close enough: create a transition edge from A to B and blend the window around them. Had the foot been planted a stride away — differing by 0.6 m, contributing 0.36 — we would get D = 0.37 \gg \tau and correctly refuse the edge, because splicing there would show an ugly jump. The threshold is the dial that trades graph connectivity against transition quality.

Synthesis is search: finding a three-second walk to a target

Now we have a graph whose walks are all valid motions. To make the character actually do something, we search the graph for the walk that best satisfies the user's request. Constraints come in several flavours:

• Follow a path — the root should trace a sketched curve on the ground.
• Reach a location — arrive near a target point (optionally by a deadline).
• Match a sketch or annotation — "walk, then wave", or a rough drawn trajectory.

Turn the request into a numeric cost — for "reach the door in 3 seconds", the cost of a candidate walk is how far its endpoint lands from the door after 3 \times 30 = 90 frames. Then explore walks of the right length, growing them edge by edge, and keep the cheapest. A naive search branches at every node and explodes, so the papers prune it with branch-and-bound (abandon any partial walk whose best-possible completion already costs more than the best full walk found so far) or frame it as dynamic programming over graph states. Concretely, to hit the door in three seconds you enumerate walks totalling about 90 frames, score each by final distance-to-door, and prune branches that have already wandered too far to recover — returning the walk whose real, blended frames land the character on the doorstep on time.