Planning biped locomotion using motion capture data and probabilistic roadmaps

ABSTRACT

Typical high-level directives for locomotion of human-like characters are useful for interactive games and simulations as well as for off-line production animation. In this paper, we present a new scheme for planning natural-looking locomotion of a biped figure to facilitate rapid motion prototyping and task-level motion generation. Given start and goal positions in a virtual environment, our scheme gives a sequence of motions to move from the start to the goal using a set of live-captured motion clips. Based on a novel combination of probabilistic path planning and hierarchical displacement mapping, our scheme consists of three parts: roadmap construction, roadmap search, and motion generation. We randomly sample a set of valid footholds of the biped figure from the environment to construct a directed graph, called a roadmap, that guides the locomotion of the figure. Every edge of the roadmap is associated with a live-captured motion clip. Augmenting the roadmap with a posture transition graph, we traverse it to obtain the sequence of input motion clips and that of target footprints. We finally adapt the motion sequence to the constraints specified by the footprint sequence to generate a desired locomotion.

REFERENCES

• 1: Okan Arikan , D. A. Forsyth, Interactive motion generation from examples, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
• 2: Badler, N. I., Bindiganavale, R., Granieri, J. P., Wei, S., and Zhao, X. 1994. Posture interpolation with collision avoidance. In Proceedings of the Conference on Computer Animation '94. 13--20.
• 3: Bandi, S. and Thalmann, D. 1998. Space discretization for efficient human navigation. Comput. Graph. Forum 17, 3, 195--206.
• 4: Jérô Barraquand , Lydia Kavraki , Jean-Claude Latombe , Rajeev Motwani , Tsai-Yen Li , Prabhakar Raghavan, A random sampling scheme for path planning, International Journal of Robotics Research, v.16 n.6, p.759-774, Dec. 1997 [doi>10.1177/027836499701600604]
• 5: Jérîme Barraquand , Jean-Claude Latombe, Robot motion planning: a distributed representation approach, International Journal of Robotics Research, v.10 n.6, p.628-649, Dec. 1991 [doi>10.1177/027836499101000604]
• 6: Ronan Boulic , Nadia Magnenat-Thalmann , Daniel Thalmann, A global human walking model with real-time kinematic personification, The Visual Computer: International Journal of Computer Graphics, v.6 n.6, p.344-358, Dec. 1990 [doi>10.1007/BF01901021]
• 7: Bowden, R. 2000. Learning statistical models of human motion. In Proceedings of the IEEE Workshop on Human Modeling, Analysis and Synthesis, CVPR2000.
• 8: Brand, M. and Hertzmann, A. 2000. Style machines. Comput. Graph. 34, 183--192.
• 9: A. Bruderlin , T. W. Calvert, Goal-directed, dynamic animation of human walking, ACM SIGGRAPH Computer Graphics, v.23 n.3, p.233-242, July 1989
• 10: Bruderlin, A. and Williams, L. 1995. Motion signal processing. Comput. Graph. 29, 97--104.
• 11: Shih-kai Chung , James K. Hahn, Animation of Human Walking in Virtual Environments, Proceedings of the Computer Animation, p.4, May 26-28, 1999
• 12: Michael F. Cohen, Interactive spacetime control for animation, ACM SIGGRAPH Computer Graphics, v.26 n.2, p.293-302, July 1992
• 13: Dijkstra, E. W. 1959. A note on two problems in connection with graphs. Numerische Mathematik 1, 269--271.
• 14: Gleicher, M. 1998. Retargetting motion to new characters. Comput. Graph. 32, 33--42.
• 15: Michael Gleicher, Motion path editing, Proceedings of the 2001 symposium on Interactive 3D graphics, p.195-202, March 2001 [doi>10.1145/364338.364400]
• 16: Gottschalk, S., Lin, M. C., and Manocha, D. 1996. OBBtree: A hierarchical structure for rapid interference detection. Comput. Graph. 30, 171--180.
• 17: Hodgins, J. K. and Pollard, N. S. 1997. Adapting simulated behaviors for new characters. Comput. Graph. 31, 153--162.
• 18: Hodgins, J. K., Wooten, W. L., Brogan, D. C., and O'Brien, J. F. 1995. Animating human athletics. Comput. Graph. 29, 75--78.
• 19: Yong K. Hwang , Narendra Ahuja, Gross motion planning—a survey, ACM Computing Surveys (CSUR), v.24 n.3, p.219-291, Sept. 1992 [doi>10.1145/136035.136037]
• 20: Kalisiak, M. and van de Panne, M. 2000. A grasp-based motion planning algorithm for character animation. In Proceedings of CAS '2000---Eurographics Workshop on Simulation and Animation. 43--58.
• 21: Kavraki, L., Kolountzakis, M., and Latombe, J.-C. 1996a. Analysis of probabilistic roadmaps for path planning. In Proceedings of the IEEE International Conference on Robotics and Automation. 3020--3025.
• 22: Kavraki, L., Svestka, P., Latombe, J.-C., and Overmars, M. H. 1996b. Probabilistic roadmaps for path planning in high dimensional configuration space. IEEE Trans. Robotics and Automation 12, 4, 566--580.
• 23: Kavraki, L. and Latombe, J.-C. 1994. Randomized preprocessing of configuration space for fast path planning. In Proceedings of the IEEE International Conference on Robotics and Automation. 2138--2145.
• 24: Lydia E. Kavraki , Jean-Claude Latombe , Rajeev Motwani , Prabhakar Raghavan, Randomized query processing in robot path planning, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.353-362, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225159]
• 25: Kindel, R., Hsu, D., Latombe, J.-C., and Rock, S. 2000. Kinodynamic motion planning amidst moving obstacles. In Proceedings of the IEEE International Conference on Robotics and Automation. 537--543.
• 26: Ko, H. and Badler, N. I. 1996. Animating human locomotion with inverse dynamics. IEEE Comput. Graph. Appl. 16, 2, 50--29.
• 27: Ko, H. and Cremer, J. 1995. VRLOCO: Real-time human locomotion from positional input streams. Presence: Teleoperations and Virtual Environments 5, 4, 1--15.
• 28: Koga, Y., Kondo, K., Kuffner, J., and Latombe, J.-C. 1994. Planning motions with intentions. Comput. Graph. 28, 395--408.
• 29: Korein, J. U. and Badler, N. I. 1982. Techniques for generating the goal-directed motion of articulated structures. IEEE Comput. Graph. Automation 2, 9, 71--81.
• 30: Lucas Kovar , Michael Gleicher , Frédéric Pighin, Motion graphs, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
• 31: James J. Kuffner , Jr , Jean-Claude Latombe, Fast Synthetic Vision, Memory, and Learning Models for Virtual Humans, Proceedings of the Computer Animation, p.118, May 26-28, 1999
• 32: Alexis Lamouret , Michiel van de Panne, Motion synthesis by example, Proceedings of the Eurographics workshop on Computer animation and simulation '96, p.199-212, December 1996, Poitiers, France
• 33: Laszlo, J., van de Panne, M., and Fiume, E. 1996. Limit cycle control and its application to the animation of balancing and walking. Comput. Graph. 30, 155--162.
• 34: Jean-Claude Latombe, Robot Motion Planning, Kluwer Academic Publishers, Norwell, MA, 1991
• 35: 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
• 36: Lee, J. and Shin, S. Y. 1999. A hierarchical approach to interactive motion editing for human-like figures. Comput. Graph. 33, 395--408.
• 37: Jehee Lee , Sung Yong Shin, A coordinate-invariant approach to multiresolution motion analysis, Graphical Models, v.63 n.2, p.87-105, March 2001 [doi>10.1006/gmod.2001.0548]
• 38: J. Lee , S. Y. Shin, General Construction of Time-Domain Filters for Orientation Data, IEEE Transactions on Visualization and Computer Graphics, v.8 n.2, p.119-128, April 2002 [doi>10.1109/2945.998665]
• 39: 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
• 40: Lin, M. C. and Manocha, D. 1995. Fast interference detection between geometric models. Vis. Comput. 11, 10, 542--561.
• 41: Marti, J. and Bunn, C. 1994. Automated path planning for simulation. In Proceedings of the Conference on AI, Simulation and Planning, AIS94.
• 42: Brian Mirtich , John Canny, Impulse-based simulation of rigid bodies, Proceedings of the 1995 symposium on Interactive 3D graphics, p.181-ff., April 09-12, 1995, Monterey, California, United States [doi>10.1145/199404.199436]
• 43: 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
• 44: Multon, F., France, L., Cani, M.-P., and Debunne, G. 1999. Computer animation of human walking: a survey. J. Vis. Comput. Animation 10, 3, 39--54.
• 45: Noser, H., Pandzic, I. S., Capin, T. K., Thalmann, N. M., and Thalmann, D. 1996. Playing games through the virtual life network. In Proceedings of the Conference on Alife '96.
• 46: Noser, H., Renault, O., Thalmann, D., and Thalmann, N. M. 1995. Navigation for digital actors based on synthetic vision, memory, and learning. Comput. Graph. 19, 1, 7--19.
• 47: Mark H. Overmars , Petr Švestka, A probabilistic learning approach to motion planning, Proceedings of the workshop on Algorithmic foundations of robotics, p.19-37, May 1995, San Francisco, California, United States
• 48: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 49: Katherine Pullen , Christoph Bregler, Motion capture assisted animation: texturing and synthesis, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
• 50: Marc H. Raibert , Jessica K. Hodgins, Animation of dynamic legged locomotion, ACM SIGGRAPH Computer Graphics, v.25 n.4, p.349-358, July 1991
• 51: Reich, B. D., Ko, H., Becket, W., and Badler, N. I. 1994. Terrain reasoning for human locomotion. In Proceedings of the Conference on Computer Animation '94. 77--82.
• 52: Craig W. Reynolds, Flocks, herds and schools: A distributed behavioral model, ACM SIGGRAPH Computer Graphics, v.21 n.4, p.25-34, July 1987
• 53: 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]
• 54: Rose, C., Guenter, B., Bodenheimer, B., and Cohen, M. F. 1996. Efficient generation of motion transitions using spacetime constraints. Comput. Graph. 30, 147--154.
• 55: Arno Schödl , Richard Szeliski , David H. Salesin , Irfan Essa, Video textures, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.489-498, July 2000 [doi>10.1145/344779.345012]
• 56: Ken Shoemake, Animating rotation with quaternion curves, ACM SIGGRAPH Computer Graphics, v.19 n.3, p.245-254, Jul. 1985
• 57: Sun, H. C. and Metaxas, D. N. 2001. Automating gait generation. Comput. Graph. 35, 261--269.
• 58: Svestka, P. and Overmars, M. H. 1998. Coordinated path planning for multiple robots. Robotics and Autonomous Systems 23, 4, 125--152.
• 59: Torkos, N. and van de Panne, M. 1998. Footprint-based quadruped motion synthesis. In Proceedings of Graphics Interface '98. 151--160.
• 60: Tu, X. and Terzopoulos, D. 1994. Artificial fishes: Physics, locomotion, perception, behavior. Comput. Graph. 28, 43--50.
• 61: Unuma, M., Anjyo, K., and Takeuchi, R. 1995. Fourier principles for emotion-based human figure animation. Comput. Graph. 29, 91--96.
• 62: van de Panne, M. 1997. From footprints to animation. Comput. Graph. Forum 16, 4, 211--223.
• 63: Witkin, A. and Popović, Z. 1995. Motion warping. Comput. Graph. 29, 105--108.

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems
  G.3 PROBABILITY AND STATISTICS

General Terms:
Algorithms, Experimentation, Theory

Keywords:
Biped locomotion, human navigation, motion editing and adaptation, probabilistic path planning