Motion Graph for Character Animation: Design Considerations
Animating human character has become an active research area in computer graphics. It is really important for development of virtual environment applications such as computer games and virtual reality. One of the popular methods to animate the character is by using motion graph. Since motion graph is the main focus of this research, we investigate the preliminary work of motion graph and discuss about the main components of motion graph like distance metrics and motion transition. These two components will be taken into consideration during the process of development of motion graph. In this paper, we will also present a general framework and future plan of this study.
motion graph; distance metrics; motion synthesis; character animation; motion transition
For many years, character animation has become one of the active research areas in computer graphics, and it had been used widely in film and games industries. In this paper the word character refers the human body with the articulated joints in a hierarchical form. Nowadays, motion capture is a popular method to animate the character. It can generate a believable motion in shorter time with less computation time compared to traditional methods like kinematics.
Although the result of animation that is produced from motion capture is good, there are some reasons that we need to reuse and edit the motion capture data. The main reason is the cost of software and the equipment for motion capture system are very expensive . In addition, the motion capture records all the movements according to the actor’s movements. If we want to use a slightly different action from the original action, we need to do the editing process for motion data. We also need to edit the data if we want to create the impossible or difficult actions. Sometimes, in some motion like repetitive motions; the real motion cannot be perfect. If we want to use exact cyclic motions we need to alter and edit the data. The interaction with the other motion such as clothing also can be one of the reasons we need to reuse and alter the data . The reusability of motion capture data means that the animator can create required motions by reusing motion data repeatedly and editing the motion data.
Generally, motion editing can be defined as a process to produce a new motion by changing or combining a number of motions. Motion transition, motion blending and motion interpolation are parts of motion editing operation that need at least two motions as inputs. In contrast, joint repositioning, retargeting, smoothing and style manipulation only need one motion as an input.
Motion blending allows the animator to change the simple motion to complex motion and creates longer motion duration. Motion blending is used for many reasons such as in creating a transition process for two motions that are very widely used in computer game development. A transition is usually used only for changing from one motion to another motion and it is used for a certain transition length. During a transition process, two motion clips will be combined by eliminating the discontinuity at the boundary between two motions. There are many factors that must be considered in motion transition, but the main factor is how to make a realistic and natural transition.
One of the common ways to reuse and editing motion capture data is known as the Motion Graph. In this paper, we focus on several components that need to be considered for creating the character animation using motion graph. Discussion of this paper is as follows: Section 2 explains the overview for motion graph. Section 3 discusses several main components in motion graph such as distance metrics and motion transition. Section 4 provides the general framework for motion graph, followed by Section 5 that concludes this paper and state a future research direction.
In this section, we will give the overview and investigate the preliminary work of motion graph and discusses several main components in motion graph.
A. Motion Graph
The basic idea of motion graph is to seamlessly connect a motion in a database using a transition . The graph structure called a motion graph will be produced. In the motion graph, edges correspond to motion clips and nodes represent as points that connect the clips (see 1).
The development of motion graph is inspired by the work of video textures, which is used to maintain the original motion sequences and played back in non repetitive streams . Motion graph is a very popular technique to animate the character for real-time applications and off-line sketch-based motion synthesis [9-12].
Based on the annotated bibliography paper that had been published by Gleicher, there are three research work that marked as the first original “motion graph” in computer graphics community . These three approaches are proposed by Kovar et al. , Arikan and Forsyth , and Lee et al. . These three approaches share the same basic idea that is develop a graph from motion database and search the graph to generate a motion that follows the user objective. However, they used a different technique for some places such as on the technique to create transition, search the graph and the distance metrics.
In previous work, we can see that many researchers combine motion graphs and interpolation techniques [16-20]. These techniques divide motions into similar behaviour and then group similar segments to create interpolation and smooth transitions. Sang et al  divide motion into short segments and arranged them into nodes in graph and blend them to create locomotion in real-time. Taesoo and Sung  construct automated motion graph for locomotion. Treuille et al. used a simple graph structure to generate real-time character animation . They create near-optimal controllers to guide the virtual character based on the user goal by using a low-dimensional basis representation.
For testing and evaluation process, there are several approaches that have been proposed by previous researchers to check the performance of their propose technique. As stated by , the evaluation process of motion graph can be classified into two categories. The first category is to evaluate the motion graph based on the individual transitions. It also can be evaluated by analyzing the resulting animation. There is a number of studies that depends on human input to measure the quality of synthesized motions [7, 8]. The statistical models also are used by [9, 10] to evaluate the quality of motions. Reitsma et al. introduced a method of evaluating a data structured especially motion graphs .
III. Distance Metrics
Normally, to create transition between very different motions is very difficult. On the other hand, if two motions are similar or nearly similar, a transition is easily to generate using simple interpolation method. For that reason, the motions are need to be compare by using a good motion similarity technique before the transition can be generated. This motion similarity technique can be refer as distance metrics.
Distance metrics is one of the important components that had been used by many researchers in motion editing [1, 3, 12, 13]. In motion graph, distance metrics are used to detect the similar frames for choosing the transition points. From this transition points, the transition can be created between the motion clips. Point clouds, metrics based on joint angles and principle components are the main types of distance metrics in motion graph .
A. Distance Metrics based on Joint-Angles
Since the motion data are represented by the joint angle of a skeleton, calculation using this method is easier than other distance metrics method. However, using this distance metrics method, we need to set a weight as a measure. Lee et al. and Arikan et al. are some of the researchers that used this distance metrics [3, 4]. The following formula shows how Lee et al. calculates the differences of joint angles .
= distance between frame i and frame j
= weighted differences of joint angles
= weighted differences of joint velocities
= weights velocity differences with respect to position differences
The weighted differences of joint angles can be expressed as follows:
= the root joint position of the character at frame i
= the root joint position of the character at frame j
= the orientation of joint k at frame i
= angle that k joint rotates from the orientation of frame i to the orientation of frame j
= quaternion that represents the orientation of the k joint at frame i.
B. Distance Metrics based on Point-Clouds
In point-clouds distance metrics, two frames of motion and its neighbouring frames will be converted into point clouds form. The distance between these two point clouds can be measured by applying the sum of squared Euclidean distance between the corresponding points in the two point clouds. In order to solve the problem of finding the point clouds coordinate systems, the minimal weighted sum of squared distances will be calculated . The distance metrics equation can be defined as:
= kth point in the point clouds for frame Mi and M′j,
= kth point in the point clouds for frame Mi and M′j,
k = joint index
= rigid transformation composed of a rotation by θ degrees about the y (vertical) axis followed by a translation of (x0, z0) in the floor plane.
= the frame weight
Based on the evaluation process that had been done by Basten et al for these three main distance metrics: joint-angle, point clouds and principal component, there are several advantages and disadvantages for these distance metrics  (See Table I). The comparison criteria that they used to evaluate these distance metrics are path deviation and foot skating. Table II shows the types of distance metrics and transition methods that had been used by several researchers in their motion graph method.
TABLE I. Advantages and disadvantages of distance metrics 
Based on joint angles
* Good for path planning in highly constrained areas
* Least path deviation
* Least foot skating
* Path deviation is highest
* Slowest search
* The graph is faster
* No need to set a weight
* Lower path deviation than point-cloud
* Slightly slower
TABLE II. Distance metrics and transition method
Comparison Method/Distance Metrics
Based on joint angles and velocities
cuts and adding displacement maps
Based on joint angles velocities + Joint Accelerations
cuts and adding displacement maps
Point cloud + joint position, joint velocities, joint acclerations
Joint angles + dynamics-based
IV. Creating Transitions
In motion graph, after the distance metric is measured to find poses that are similar, this metric will be applied in the database to find all the possible transitions. If the metric is below some threshold, the transition can be created. There are many types of transition method in the motion graph. By making jump cuts and adding displacement maps, Arikan et al. and Lee et al. are able to create a transition in their motion graph method  . Kovar et al. using a simple linear blending to generate a transition between the frames .
As stated by Wang and Bodenheimer, blending is one of the ways for creating transition . It can be referred to as a temporary blend that used to change from one motion to other motion. During the process of motion transition from one motion to another, motion blend will be started in a certain transition length. The length of motion blend is determined depending on the blended motions. They also stated that linear blending is a common technique for creating transitions. Linear interpolating and linear blending are suitable to be used for the application that need the efficiency and speed which has low computational weight.
However, there are some drawbacks using this method. It is still hard and need a significant manual labor for generating a good transition using blending . It is still critical to determine the blend length and transition points in the clips. To solve this problem, Wang developed the geodesic distance method and the velocity method for determining an optimal blend length for motion transitions . These methods can be used for many different types of motion. The geodesic distance method is suitable for locomotion motions such as walking and running. On the other hand, velocity method is used for unpredictable motions such as dancing and boxing.
V. General Framework
In this section we discuss about a general framework for animating the character using motion graph (see 2). Most of the decisions for designing the framework are based on the previous works of numerous researchers. For each motion clip in the motion database, we will use more than 100 motion clips which contained with one walk cycle. For the process of locating transition points, most of previous works use a point-cloud method to compare and find the similar frames in the motion clip. With a slight modification of point cloud method, we will adapt this approach in our motion graph. The simple linear blending will be used to create a faster transition which is important for creating a controllable motion graph. Since the blending transition can produce the artifacts such as foot-skate, we will solve this problem with suitable foot-skate cleanup method.
VI. Conclusions and Future Works
In this paper we investigate the preliminary work of motion graph and compare the motion graph components like distance metrics and transition methods. These two components are part of the issues that we need to consider during the process of development of motion graph. Distance metrics will be our future direction.
The author wishes to convey their innermost gratitude and appreciation to Malaysian Ministry of Science, Technology and Innovation (MOSTI) under ScienceFund grant (01-01-06-SF0387) for providing financial support of this research.
 Kovar, L., et al., Motion graphs. ACM Trans. Graph., 2002. 21(3): p. 473-482.
 Michael, G., Animation from observation: Motion capture and motion editing. SIGGRAPH Comput. Graph., 2000. 33(4): p. 51-54.
 Arikan, O. and D.A. Forsyth, Interactive motion generation from examples. ACM Trans. Graph., 2002. 21(3): p. 483-490.
 Lee, J., et al., Interactive control of avatars animated with human motion data, in Proceedings of the 29th annual conference on Computer graphics and interactive techniques. 2002, ACM: San Antonio, Texas.
 Treuille, A., Y. Lee, and Z. Popovi, Near-optimal character animation with continuous control. ACM Trans. Graph., 2007. 26(3): p. 7.
 Matsunaga, M., Zordan, V.B., A Dynamics-based Comparison Metric for Motion Graphs. Computer Graphics International (CGI) 2007., 2007.
 S. A. Reitsma, P. and N. S. Pollard, Perceptual metrics for character animation: sensitivity to errors in ballistic motion. ACM Trans. Graph., 2003. 22(3): p. 537-542.
 Wang, J. and B. Bodenheimer, Computing the duration of motion transitions: an empirical approach, in Proceedings of the 2004 ACM SIGGRAPH/Eurographics symposium on Computer animation. 2004, Eurographics Association: Grenoble, France.
 Wang, J. and B. Bodenheimer, An evaluation of a cost metric for selecting transitions between motion segments, in Proceedings of the 2003 ACM SIGGRAPH/Eurographics symposium on Computer animation. 2003, Eurographics Association: San Diego, California.
 Liu, R., et al., A data-driven approach to quantifying natural human motion. ACM Trans. Graph., 2005. 24(3): p. 1090-1097.
 Reitsma, P.S.A. and N.S. Pollard, Evaluating motion graphs for character navigation, in Proceedings of the 2004 ACM SIGGRAPH/Eurographics symposium on Computer animation. 2004, Eurographics Association: Grenoble, France.
 Heck, R. and M. Gleicher, Parametric motion graphs, in Proceedings of the 2007 symposium on Interactive 3D graphics and games. 2007, ACM: Seattle, Washington.
 Leslie, I., A. Okan, and F. David, Quick transitions with cached multi-way blends, in Proceedings of the 2007 symposium on Interactive 3D graphics and games. 2007, ACM: Seattle, Washington.
 Basten, B.J.H.v. and A. Egges, Evaluating distance metrics for animation blending, in Proceedings of the 4th International Conference on Foundations of Digital Games. 2009, ACM: Orlando, Florida.
 Matsunaga, M., Zordan, and V.B. A Dynamics-based Comparison Metric for Motion Graph. in Computer Graphics International (CGI). 2007.
 Lee, J. and S.Y. Shin, General Construction of Time-Domain Filters for Orientation Data. IEEE Transactions on Visualization and Computer Graphics, 2002. 8(2): p. 119-128.
 Jing, W., Synthesizing and evaluating data-driven motion transitions. 2005, Vanderbilt University. p. 114.
 Kovar, L., J. Schreiner, and M. Gleicher, Footskate cleanup for motion capture editing, in Proceedings of the 2002 ACM SIGGRAPH/Eurographics symposium on Computer animation. 2002, ACM: San Antonio, Texas.