Evaluating motion graphs for character navigation

ABSTRACT

Realistic and directable humanlike characters are an ongoing goal in animation. Motion graph data structures hold much promise for achieving this goal. However, the quality of the results obtained from a motion graph may not be easy to predict from the input motion segments. This paper introduces the idea of assessing a data structure such as a motion graph for its utility in a particular application. We focus on navigation tasks and define metrics for evaluating expected path quality and coverage for a given environment. One key to evaluating a motion graph for navigation tasks is to first embed it into the environment in a way that captures all possible paths that might result from "playing back" the motion graph within that environment. This paper describes an algorithm for accomplishing this embedding that preserves the flexibility of the original motion graph. We use the metrics defined in this paper to compare motion datasets and to highlight areas where these datasets could be improved.

REFERENCES

• 1: Okan Arikan , D. A. Forsyth, Interactive motion generation from examples, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
• 2: Okan Arikan , David A. Forsyth , James F. O'Brien, Motion synthesis from annotations, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 3: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 4: Min Gyu Choi , Jehee Lee , Sung Yong Shin, Planning biped locomotion using motion capture data and probabilistic roadmaps, ACM Transactions on Graphics (TOG), v.22 n.2, p.182-203, April 2003 [doi>10.1145/636886.636889]
• 5: {DJM04} Drumwright E., Jenkins O. C., Matarić M. J.: Exemplar-based primitives for humanoid movement classification and control. In Proc. IEEE Intl. Conference on Robotics and Automation (2004).
• 6: Bruce Donald , Patrick Xavier , John Canny , John Reif, Kinodynamic motion planning, Journal of the ACM (JACM), v.40 n.5, p.1048-1066, Nov. 1993 [doi>10.1145/174147.174150]
• 7: Michael Gleicher , Hyun Joon Shin , Lucas Kovar , Andrew Jepsen, Snap-together motion: assembling run-time animations, Proceedings of the 2003 symposium on Interactive 3D graphics, April 27-30, 2003, Monterey, California [doi>10.1145/641480.641515]
• 8: Jessica K. Hodgins , James F. O'Brien , Jack Tumblin, Perception of Human Motion With Different Geometric Models, IEEE Transactions on Visualization and Computer Graphics, v.4 n.4, p.307-316, October 1998 [doi>10.1109/2945.765325]
• 9: Jason Harrison , Ronald A. Rensink , Michiel van de Panne, Obscuring length changes during animated motion, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 10: Lucas Kovar , Michael Gleicher, Automated extraction and parameterization of motions in large data sets, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 11: Lucas Kovar , Michael Gleicher , Frédéric Pighin, Motion graphs, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
• 12: Lucas Kovar , John Schreiner , Michael Gleicher, Footskate cleanup for motion capture editing, Proceedings of the 2002 ACM SIGGRAPH/Eurographics symposium on Computer animation, July 21-22, 2002, San Antonio, Texas [doi>10.1145/545261.545277]
• 13: {KL98} Kavraki L. E., Latombe J.-C.: Probabilistic roadmaps for robot path planning. In Proctical Motion Planning In Robotics: Current Approaches and Future Directions, Gupta K., del Pobil A., (Eds.). John Wiley, 1998, pp. 33--53.
• 14: Tae-hoon Kim , Sang Il Park , Sung Yong Shin, Rhythmic-motion synthesis based on motion-beat analysis, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 15: Jean-Claude Latombe, Robot Motion Planning, Kluwer Academic Publishers, Norwell, MA, 1991
• 16: Jehee Lee , Jinxiang Chai , Paul S. A. Reitsma , Jessica K. Hodgins , Nancy S. Pollard, Interactive control of avatars animated with human motion data, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
• 17: {LPO91} Lozano-Pérez T., O'Donnell P. A.: Parallel robot motion planning. In Proc. IEEE Intl. Conference on Robotics and Automation (1991).
• 18: Jed Lengyel , Mark Reichert , Bruce R. Donald , Donald P. Greenberg, Real-time robot motion planning using rasterizing computer graphics hardware, Proceedings of the 17th annual conference on Computer graphics and interactive techniques, p.327-335, September 1990, Dallas, TX, USA
• 19: Yan Li , Tianshu Wang , Heung-Yeung Shum, Motion texture: a two-level statistical model for character motion synthesis, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
• 20: L. M. Tanco , A. Hilton, Realistic synthesis of novel human movements from a database of motion capture examples, Proceedings of the Workshop on Human Motion (HUMO'00), p.137, December 07-08, 2000
• 21: {OHJ00} Oesker M., Hecht H., Jung B.: Psychological evidence for unconscious processing of detail in real-time animation of multiple characters. Journal of Visualization and Computer Animation 11 (2000), 105--112.
• 22: Charles Rose , Michael F. Cohen , Bobby Bodenheimer, Verbs and Adverbs: Multidimensional Motion Interpolation, IEEE Computer Graphics and Applications, v.18 n.5, p.32-40, September 1998 [doi>10.1109/38.708559]
• 23: Paul S. A. Reitsma , Nancy S. Pollard, Perceptual metrics for character animation: sensitivity to errors in ballistic motion, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 24: {RSC01} Rose C. F., Sloan P.-P. J., Cohen M. F.: Animation: Artist-directed inverse-kinematics using radial basis function interpolation. Computer Graphics Forum 20, 3 (2001).
• 25: Peter-Pike J. Sloan , Charles F. Rose, III , Michael F. Cohen, Shape by example, Proceedings of the 2001 symposium on Interactive 3D graphics, p.135-143, March 2001 [doi>10.1145/364338.364382]
• 26: Jing Wang , Bobby Bodenheimer, An evaluation of a cost metric for selecting transitions between motion segments, Proceedings of the 2003 ACM SIGGRAPH/Eurographics symposium on Computer animation, July 26-27, 2003, San Diego, California
• 27: Douglas J. Wiley , James K. Hahn, Interpolation Synthesis of Articulated Figure Motion, IEEE Computer Graphics and Applications, v.17 n.6, p.39-45, November 1997 [doi>10.1109/38.626968]
• 28: Victor Brian Zordan , Jessica K. Hodgins, Motion capture-driven simulations that hit and react, Proceedings of the 2002 ACM SIGGRAPH/Eurographics symposium on Computer animation, July 21-22, 2002, San Antonio, Texas [doi>10.1145/545261.545276]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.7 Three-Dimensional Graphics and Realism