Behavior planning for character animation

ABSTRACT

This paper explores a behavior planning approach to automatically generate realistic motions for animated characters. Motion clips are abstracted as high-level behaviors and associated with a behavior finite-state machine (FSM) that defines the movement capabilities of a virtual character. During runtime, motion is generated automatically by a planning algorithm that performs a global search of the FSM and computes a sequence of behaviors for the character to reach a user-designated goal position. Our technique can generate interesting animations using a relatively small amount of data, making it attractive for resource-limited game platforms. It also scales efficiently to large motion databases, because the search performance is primarily dependent on the complexity of the behavior FSM rather than on the amount of data. Heuristic cost functions that the planner uses to evaluate candidate motions provide a flexible framework from which an animator can control character preferences for certain types of behavior. We show results of synthesized animations involving up to one hundred human and animal characters planning simultaneously in both static and dynamic environments.

REFERENCES

• 1: Okan Arikan , D. A. Forsyth, Interactive motion generation from examples, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
• 2: O. Burchan Bayazit , Jyh-Ming Lien , Nancy M. Amato, Roadmap-Based Flocking for Complex Environments, Proceedings of the 10th Pacific Conference on Computer Graphics and Applications, p.104, October 09-11, 2002
• 3: Jernej Barbič , Alla Safonova , Jia-Yu Pan , Christos Faloutsos , Jessica K. Hodgins , Nancy S. Pollard, Segmenting motion capture data into distinct behaviors, Proceedings of the 2004 conference on Graphics interface, p.185-194, May 17-19, 2004, London, Ontario, Canada
• 4: Armin Bruderlin , Lance Williams, Motion signal processing, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.97-104, September 1995 [doi>10.1145/218380.218421]
• 5: 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]
• 6: Anthony C. Fang , Nancy S. Pollard, Efficient synthesis of physically valid human motion, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 7: {FvdPT01} Faloutsos P., Van De Panne M., Terzopoulos D.: The virtual stuntman: dynamic characters with a repertoire of autonomous motor skills. Computers and Graphics 25, 6 (2001), 933--953.
• 8: Michael Gleicher, Retargetting motion to new characters, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.33-42, July 1998 [doi>10.1145/280814.280820]
• 9: Michael Gleicher , Hyun Joon Shin , Lucas Kovar , Andrew Jepsen, Snap-together motion: assembling run-time animations, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 10: Jared Go , Thuc Vu , James J. Kuffner, Autonomous behaviors for interactive vehicle animations, Proceedings of the 2004 ACM SIGGRAPH/Eurographics symposium on Computer animation, August 27-29, 2004, Grenoble, France [doi>10.1145/1028523.1028525]
• 11: {HNR68} Hart P., Nilsson N., Rafael B.: A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. Sys. Sci. and Cyb. 4 (1968), 100--107.
• 12: Jessica K. Hodgins , Wayne L. Wooten , David C. Brogan , James F. O'Brien, Animating human athletics, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.71-78, September 1995 [doi>10.1145/218380.218414]
• 13: Lucas Kovar , Michael Gleicher , Frédéric Pighin, Motion graphs, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
• 14: 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]
• 15: {KvdP01} Kalisiak M., Van De Panne M.: A grasp-based motion planning algorithm for character animation. J. Visualization and Computer Animation 12, 3 (2001), 117--129.
• 16: {LaV} LaValle S. M.: Planning Algorithms. Cambridge University Press (also available at http://msl.cs.uiuc.edu/planning/). To be published in 2006.
• 17: 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
• 18: 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]
• 19: {LP02} Liu C. K., Popovic Z.: Animating human athletics. In Proc. ACM SIGGRAPH 2002 (Annual Conference Series) (2002).
• 20: 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]
• 21: {MBC01} Mizuguchi M., Buchanan J., Calvert T.: Data driven motion transitions for interactive games. Eurographics 2001 Short Presentations (September 2001).
• 22: Alberto Menache , Alberto Manache, Understanding Motion Capture for Computer Animation and Video Games, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1999
• 23: Katherine Pullen , Christoph Bregler, Motion capture assisted animation: texturing and synthesis, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
• 24: Ken Perlin , Athomas Goldberg, Improv: a system for scripting interactive actors in virtual worlds, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.205-216, August 1996 [doi>10.1145/237170.237258]
• 25: 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
• 26: Zoran Popović , Andrew Witkin, Physically based motion transformation, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.11-20, July 1999 [doi>10.1145/311535.311536]
• 27: 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]
• 28: Craig W. Reynolds, Flocks, herds and schools: A distributed behavioral model, Proceedings of the 14th annual conference on Computer graphics and interactive techniques, p.25-34, August 1987
• 29: 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]
• 30: Alla Safonova , Jessica K. Hodgins , Nancy S. Pollard, Synthesizing physically realistic human motion in low-dimensional, behavior-specific spaces, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 31: {SYN01} Shiller Z., Yamane K., Nakamura Y.: Planning motion patterns of human figures using a multi-layered grid and the dynamics filter. In Proceedings of the IEEE International Conference on Robotics and Automation (2001), pp. 1--8.
• 32: 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]
• 33: Andrew Witkin , Zoran Popovic, Motion warping, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.105-108, September 1995 [doi>10.1145/218380.218422]
• 34: 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