Computer Science Department
School of Computer Science, Carnegie Mellon University


Construction and Optimal Search of
Interpolated Motion Graphs

Alla Safonova, Jessica K. Hodgins

January 2007


Keywords: Motion capture, motion graph, motion planning, human animation

Many compelling applications would immediately become feasible if novice users had the ability to synthesize high quality human motion based only on a simple sketch or a few easily specified constraints. We approach this problem by representing the desired motion as an interpolation of two time-scaled paths through a motion graph. The graph is constructed to support interpolation and pruned for efficient search. We use an anytime version of A to find a globally optimal solution in this graph that satisfies the user”Ēs specification. This solution is not subject to local minima and avoids the inefficient motions that are sometimes seen with locally optimal search algorithms and traditional motion graphs. Our approach retains the natural transitions of motion graphs and the ability to synthesize physically realistic variations provided by interpolation. We demonstrate the power of this approach by synthesizing optimal or near optimal motions that include a variety of behaviors in a single motion.

27 pages

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by