Motion patches: building blocks for virtual environments annotated with motion data

ABSTRACT

Real time animation of human figures in virtual environments is an important problem in the context of computer games and virtual environments. Recently, the use of large collections of captured motion data has increased realism in character animation. However, assuming that the virtual environment is large and complex, the effort of capturing motion data in a physical environment and adapting them to an extended virtual environment is the bottleneck for achieving interactive character animation and control. We present a new technique for allowing our animated characters to navigate through a large virtual environment, which is constructed using a set of building blocks. The building blocks, called motion patches, can be arbitrarily assembled to create novel environments. Each patch is annotated with motion data, which informs what actions are available for animated characters within the block. The versatility and flexibility of our approach are demonstrated through examples in which multiple characters are animated and controlled at interactive rates in large, complex virtual environments.

REFERENCES

• 1: Abaci, T., Cíger, J., and Thalmann, D. 2005. Planning with smart objects. In WSCG (Short Papers), 25--28.
• 2: Okan Arikan , D. A. Forsyth, Interactive motion generation from examples, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
• 3: Okan Arikan , David A. Forsyth , James F. O'Brien, Motion synthesis from annotations, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 4: Okan Arikan , David A. Forsyth , James F. O'Brien, Pushing people around, Proceedings of the 2005 ACM SIGGRAPH/Eurographics symposium on Computer animation, July 29-31, 2005, Los Angeles, California [doi>10.1145/1073368.1073376]
• 5: S. Bandi , D. Thalmann, A Configuration Space Approach for Efficient Animation of Human Figures, Proceedings of the 1997 IEEE Workshop on Motion of Non-Rigid and Articulated Objects (NAM '97), p.38, June 16-July 16, 1997
• 6: Bindiganavale, R., Granieri, J. P., Wei, S., Zhao, X., and Badler, N. I. 1994. Posture interpolation with collision avoidance. In Proceedings of Computer Animation '94, 13--20.
• 7: Stephen Chenney, Flow tiles, Proceedings of the 2004 ACM SIGGRAPH/Eurographics symposium on Computer animation, August 27-29, 2004, Grenoble, France [doi>10.1145/1028523.1028553]
• 8: 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]
• 9: Richard O. Duda , Peter E. Hart , David G. Stork, Pattern Classification (2nd Edition), Wiley-Interscience, 2000
• 10: Keith Grochow , Steven L. Martin , Aaron Hertzmann , Zoran Popović, Style-based inverse kinematics, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 11: Eugene Hsu , Sommer Gentry , Jovan Popović, Example-based control of human motion, Proceedings of the 2004 ACM SIGGRAPH/Eurographics symposium on Computer animation, August 27-29, 2004, Grenoble, France [doi>10.1145/1028523.1028534]
• 12: Jung, M. R., Badler, N. I., and Noma, T. 1994. Animated human agents with motion planning capability for 3d-space postural goals. The Journal of Visualization and Computer Animation 5, 4, 225--246.
• 13: Kalisiak, M., and Van De Panne, M. 2001. A grasp-based motion planning algorithm for character animation. The Journal of Visualization and Computer Animation 12, 3, 117--129.
• 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: Yoshihito Koga , Koichi Kondo , James Kuffner , Jean-Claude Latombe, Planning motions with intentions, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, p.395-408, July 1994 [doi>10.1145/192161.192266]
• 16: 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
• 17: Lucas Kovar , Michael Gleicher , Frédéric Pighin, Motion graphs, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
• 18: Kuffner, J. J., Nishiwaki, K., Kagami, S., Inaba, M., and Inoue, H. 2001. Footstep planning among obstacles for biped robots. In Proc. IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS'01).
• 19: Taesoo Kwon , Sung Yong Shin, Motion modeling for on-line locomotion synthesis, Proceedings of the 2005 ACM SIGGRAPH/Eurographics symposium on Computer animation, July 29-31, 2005, Los Angeles, California [doi>10.1145/1073368.1073373]
• 20: Yu-Chi Lai , Stephen Chenney , ShaoHua Fan, Group motion graphs, Proceedings of the 2005 ACM SIGGRAPH/Eurographics symposium on Computer animation, July 29-31, 2005, Los Angeles, California [doi>10.1145/1073368.1073409]
• 21: Jean-Claude Latombe, Robot Motion Planning, Kluwer Academic Publishers, Norwell, MA, 1991
• 22: Manfred Lau , James J. Kuffner, Behavior planning for character animation, Proceedings of the 2005 ACM SIGGRAPH/Eurographics symposium on Computer animation, July 29-31, 2005, Los Angeles, California [doi>10.1145/1073368.1073408]
• 23: Jehee Lee , Kang Hoon Lee, Precomputing avatar behavior from human motion data, Proceedings of the 2004 ACM SIGGRAPH/Eurographics symposium on Computer animation, August 27-29, 2004, Grenoble, France [doi>10.1145/1028523.1028535]
• 24: Jehee Lee , Sung Yong Shin, A hierarchical approach to interactive motion editing for human-like figures, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.39-48, July 1999 [doi>10.1145/311535.311539]
• 25: 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
• 26: Noser, H., Renault, O., Thalmann, D., and Thalmann, N. M. 1995. Navigation for digital actors based on synthetic vision, memory, and learning. Computer & Graphics 19, 1, 7--19.
• 27: Sang Il Park , Hyun Joon Shin , Tae Hoon Kim , Sung Yong Shin, On-line motion blending for real-time locomotion generation: Research Articles, Computer Animation and Virtual Worlds, v.15 n.3-4, p.125-138, July 2004 [doi>10.1002/cav.v15:3/4]
• 28: Julien Pettré , Jean-Paul Laumond , Thierry Siméon, A 2-stages locomotion planner for digital actors, Proceedings of the 2003 ACM SIGGRAPH/Eurographics symposium on Computer animation, July 26-27, 2003, San Diego, California
• 29: Katherine Pullen , Christoph Bregler, Motion capture assisted animation: texturing and synthesis, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
• 30: P. S. A. Reitsma , N. S. Pollard, Evaluating motion graphs for character navigation, Proceedings of the 2004 ACM SIGGRAPH/Eurographics symposium on Computer animation, August 27-29, 2004, Grenoble, France [doi>10.1145/1028523.1028536]
• 31: Wei Shao , Demetri Terzopoulos, Autonomous pedestrians, Proceedings of the 2005 ACM SIGGRAPH/Eurographics symposium on Computer animation, July 29-31, 2005, Los Angeles, California [doi>10.1145/1073368.1073371]
• 32: Matthew Stone , Doug DeCarlo , Insuk Oh , Christian Rodriguez , Adrian Stere , Alyssa Lees , Chris Bregler, Speaking with hands: creating animated conversational characters from recordings of human performance, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 33: Sung, M., Gleicher, M., and Chenney, S. 2004. Scalable behaviors for crowd simulation. Computer Graphics Forum (Eurographics 2004) 23, 3, 519--528.
• 34: Mankyu Sung , Lucas Kovar , Michael Gleicher, Fast and accurate goal-directed motion synthesis for crowds, Proceedings of the 2005 ACM SIGGRAPH/Eurographics symposium on Computer animation, July 29-31, 2005, Los Angeles, California [doi>10.1145/1073368.1073410]
• 35: Tarjan, R. 1972. Depth first search and linear graph algorithms. SIAM Journal of Computing 1, 146--160.
• 36: Matthew Thorne , David Burke , Michiel van de Panne, Motion doodles: an interface for sketching character motion, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 37: Jing Wang , Bobby Bodenheimer, Computing the duration of motion transitions: an empirical approach, Proceedings of the 2004 ACM SIGGRAPH/Eurographics symposium on Computer animation, August 27-29, 2004, Grenoble, France [doi>10.1145/1028523.1028568]
• 38: Katsu Yamane , James J. Kuffner , Jessica K. Hodgins, Synthesizing animations of human manipulation tasks, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004

INDEX TERMS

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

Keywords:
human motion, interactive character animation, motion capture, path planning, virtual environments