Construction and Optimal Search of Interpolated Motion Graphs

Alex J. Champandard on August 10, 2007

Siggraph 2007 was underway this week, and the four papers of Character Animation I were covered here (1, 2, 3, 4). This kind of technology is very useful for creating next-generation AI. Over the next few days, you’ll find out about the remaining contributions at this year’s event.

Another paper from Carnegie Mellon Graphics Lab presents techniques for constructing and searching interpolated motion graphs. There are two innovations here:

  • Representing the desired motion as an interpolation of different paths through a motion graph.

  • Using an anytime A* algorithm to search through the graph of possible motion clips.

This approach combines the benefits of the motion graphs for creating natural looking transitions, yet it allows the animation to be constrained physically also.

User path sketched through obstacles.

View or download the movie (MOV, 24 Mb).

Here’s the abstract:

Many compelling applications would become feasible if novice users had the ability to synthesize high quality human motion based only on a simple sketch and 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* search to find a globally optimal solution in this graph that satisfies the user’s specification. 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.

Download the paper (PDF, 4.5 Mb):

Construction and Optimal Search of Interpolated Motion Graphs
Safonova, A. and Hodgins, J. K.
ACM Transactions on Graphics 26(3)

Here’s a quick assessment of the technology based on how easy it would be to use for upcoming games.

Applicability to games: 8/10
This kind of technology is perfect for AAA studios that can afford to capture lots of animations to provide the ability for interpolation. EA uses similar concepts behind this technology on its sports games already.
Usefulness for character AI: 9/10
While it may not always be feasible to motion capture all the AI behaviors, this is certainly one of the best ways to use them in a physically realistic way. This approach also provides a very elegant and logical interface between AI and animation.
Simplicity to implement: 7/10
The interpolation itself is quite easy to implement, but it requires building the motion graph to support it. A* is also straightforward to code up, but the heuristic requires a solid animation background.
A grabbing motion with multiple possible targets.

Interpolation used for grabbing targets.

How do you think this kind of technology can be useful to game AI?

Discussion 0 Comments

If you'd like to add a comment or question on this page, simply log-in to the site. You can create an account from the sign-up page if necessary... It takes less than a minute!