Eva Schiffer

Motion Graphs
by Lucas Kovar, Fred Pighin and Michael Gleicher. SIGGRAPH 2002 

Summary:

This paper discusses a method for constructing complex graphs of motion transitions based on motion capture data and then using them to generate motion based on high level constraints. A special focus is given to path synthesis using these motion graphs.

Problem:

This paper tacked the problem of creating "realistic, controllable motion" that meets high level constraints. The sub-problems of how to find similar poses in the input data, how to create or blend transitions between the nodes in the graph, and how to use the graphs for path synthesis (including higher level constraints about the type of motion desired on parts of the path) are also tackled.

Method:

The basic method presented in this paper was to phrase the problem of constructing the abstract motion graph as a dynamic programming problem based on the similarity of the component motions. Once similar points were identified, the graph could be constructed and then pruned so that strongly connected components are all that remain; allowing for arbitrarily long and stylistically flexible motion to be created. Transitions were formed between the appropriate matching nodes (as found by the dynamic programming problem) and constraints are enforced as a post processing step. 
The method for path synthesis presented in this paper is essentially a graph search which tries to minimize the total error at iteratively further steps along the requested path. 

Key Ideas:

Dynamic programming can be used to find similar motions quickly.
Pruning the graph assures that the problem of motion generation is much easier to solve as a graph search.
A finished motion graph can be used to generate many sorts of motion via graph searches, not just simple motion along a path.

Contributions:

The form of the motion graphs and the strategy of using dynamic programing to identify similar motions are unique to this paper. 

Questions:

How complex do the finished graphs get? How hard is it tune the threshold to form a "good" graph?