This paper extends Motion Graphs by allowing exact control over position, orientation and time at points in a path. Since the original paper required that all motion be generated directly from paths along the graph itself, it could not guarantee that, given a path defined by constraints, that the ending positions/orientations be exactly as specified (or even close). Besides the obvious problem that the resulting motion may not be good enough, this property also requires their system to exhaustively search the graph.

In order to acheive their goals for a given section of the path defined by two constraints, they first sample the world, construct a graph from the samples and then use Dijkstra's algorithm to construct a reasonable approximation to a path from one end to the other that avoids obstacles (including other actors).

This path is then used in a greedy search along the motion graph from one pose to another, forming a chain of poses from the starting point to some point near the end. A similar chain is formed from the end point back to the start. Since the first chain contains the correct starting pose in the correct position and orientation, and ditto for the ending pose of the second chain, all they do is search along the chains for a matching pose in each. They then replace clips so that that pose is more closely aligned between the motions and smooth out any discrepancy with a displacement map.