Fast and accurate goal-directed motion synthesis for crowds

ABSTRACT

This paper presents a highly efficient motion synthesis algorithm that is well suited for animating large numbers of characters. Given constraints that require characters to be in specific poses, positions, and orientations in specified time intervals, our algorithm, synthesizes motions that exactly satisfy these constraints while avoiding inter-character collisions and collisions with the environment. We represent the space of possible actions with a motion graph and use search algorithms to generate motion. To provide a good initial guess for the search, we employ a fast path planner based on probabilistic roadmaps to navigate characters through complex environments. Also, unlike existing algorithms, our search process allows for smooth, continual adjustments to position, orientation, and timing. This allows us both to satisfy constraints precisely and to generate motion much faster than would otherwise be possible.

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: A. Bruderlin , T. W. Calvert, Goal-directed, dynamic animation of human walking, Proceedings of the 16th annual conference on Computer graphics and interactive techniques, p.233-242, July 1989
• 4: {BC97} Bouvier E., Cohen E.: From crowd simulation to airbag deployment: particle system, a new paradigm of simulation. Journal of Electronic imaging (1997), 94--107.
• 5: 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]
• 6: {BUT04} Boulic R., Ulicny B., Thalmann D.: Versatile walk engine. Journal of Game Development 1, 1 (2004).
• 7: 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]
• 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: {FBT99} Farenc N., Boulic R.. Thalman D.: An informed environment dedicated to the simulation virtual humans in urban context. In Proc. of EUROGRAPHICS 1999 (1999). Annual Conference Series. pp. 309--318.
• 10: Shang Guo , James Robergé, A high-level control mechanism for human locomotion based on parametric frame space interpolation, Proceedings of the Eurographics workshop on Computer animation and simulation '96, p.95-107, December 1996, Poitiers, France
• 11: 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]
• 12: {HFV00} Helbing D., Farkas I., Vicsek T.: Simulating dynamics feature of escape panic. In Nature (2000), pp. 487--490.
• 13: 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]
• 14: {HM95} Helbing D., Molnar P.: Social force model for pedestrian dynamics. In Physical Review (May 1995), pp. 4282--4286.
• 15: Lucas Kovar , Michael Gleicher , Frédéric Pighin, Motion graphs, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
• 16: {KL94} Kavraki L., Latombe J. C.: Randomized pre-processing of configuration space for fast path planning. In Proc. IEEE Int. Conf. on Robotics and Automation (1994), pp. 2138--2145.
• 17: {KL00} Kuffner J., Lavalle S.: Rrt-connect: An efficient approach to single-query path planning. In Proc. IEEE Int. Conf. on Robotics and Automation (2000), pp. 995--1001.
• 18: 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
• 19: 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
• 20: {LK99} Lavalle S., Ku J.: Randomized kinodynamic planning. In Proc. IEEE Int. Conf. on Robotics and Automation (1999), pp. 473--479.
• 21: {LK00} Lavalle S., Kuffner J.: Rapidly-exploring random trees: Progress and prospects. In In Workshop on the Algorithmic Foundations of Robotics. (2000), pp. 293--308.
• 22: 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]
• 23: Soraia Raupp Musse , Daniel Thalmann, Hierarchical Model for Real Time Simulation of Virtual Human Crowds, IEEE Transactions on Visualization and Computer Graphics, v.7 n.2, p.152-164, April 2001 [doi>10.1109/2945.928167]
• 24: 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
• 25: Sang Il Park , Hyun Joon Shin , Sung Yong Shin, On-line locomotion generation based on motion blending, Proceedings of the 2002 ACM SIGGRAPH/Eurographics symposium on Computer animation, July 21-22, 2002, San Antonio, Texas [doi>10.1145/545261.545279]
• 26: 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]
• 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: 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]
• 29: {SCG04} Sung M., Chenney S., Gleicher M.: Scalable behaviors for crowd simulation. In Computer Graphics Forum (EUROGRAPHICS '04) (2004), vol. 23, pp. 519--528.
• 30: Arno Schödl , Irfan A. Essa, Controlled animation of video sprites, Proceedings of the 2002 ACM SIGGRAPH/Eurographics symposium on Computer animation, July 21-22, 2002, San Antonio, Texas [doi>10.1145/545261.545281]
• 31: Harold C. Sun , Dimitris N. Metaxas, Automating gait generation, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.261-270, August 2001 [doi>10.1145/383259.383288]
• 32: {UT02} Ulicny B., Thalmann D.: Towards interactive real-time crowd behavior simulation. Computer Graphics Forum (Nov. 2002), 767--775.
• 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]

INDEX TERMS

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