Article

Fast and accurate goal-directed motion synthesis for crowds

Authors:

Michael GleicherAuthors Info & Claims

SCA '05: Proceedings of the 2005 ACM SIGGRAPH/Eurographics symposium on Computer animation

Pages 291 - 300

https://doi.org/10.1145/1073368.1073410

Published: 29 July 2005 Publication History

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]

{AF02} Arikan O., Forsyth D. A.: Interactive motion generation from examples. ACM Transactions on Graphics 21, 3 (2002), 483--490.

Digital Library

[2]

{AFO03} Arikan O., Forsyth D. A., O'Brien J. F.: Motion synthesis from annotations. ACM Transactions on Graphics 22, 3 (2003), 402--408.

Digital Library

[3]

{BC89} Bruderlin A., Calvert T.: Goal-directed, dynamic animation of human walking. In Proc. of ACM SIGGRAPH 1989 (July 1989), Annual Conference Series, ACM SIGGRAPH, pp. 233--242.

Digital Library

[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]

{BMTT90} Boulic R., Magnenat-Thalmann N., Thalmann D.: A global walking model with real-time kinematic personification. Visual Computer 6, 6 (1990), 344--358.

Digital Library

[6]

{BUT04} Boulic R., Ulicny B., Thalmann D.: Versatile walk engine. Journal of Game Development 1, 1 (2004).

[7]

{BW95} Bruderlin A., Williams L.: Motion signal processing. In Proc. of ACM SIGGRAPH 95 (Aug. 1995). Annual Conference Series, ACM SIGGRAPH, pp. 97--104.

Digital Library

[8]

{CLS03} Choi M. G., Lee J., Shin S. Y.: Planning biped locomotion using motion capture data and probabilistic roadmaps. ACM Transactions on Graphics 22, 2 (2003), 182--203.

Digital Library

[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]

{GR96} Guo S., Roberge J.: A high-level control mechanism for human locomotion based on parametric frame space interpolation. In Proc. of Eurographics Workshop on Computer Animation and Simulation '96 (Aug. 1996), pp. 95--107.

Digital Library

[11]

{GSKJ03} Gleicher M., Shin H. J., Kovar L., Jepsen A.: Snap-together motion: assembling run-time animations. In Proc. of the 2003 Symposium on Interactive 3D graphics (2003), pp. 181--188.

Digital Library

[12]

{HFV00} Helbing D., Farkas I., Vicsek T.: Simulating dynamics feature of escape panic. In Nature (2000), pp. 487--490.

[13]

{HGP04} Hsu E., Gentry S., Popović J.: Example-based control of human motion. In Proc. of the 2004 ACM SIGGRAPH/Eurographics Symposium on Computer Animation (2004), pp. 69--77.

Digital Library

[14]

{HM95} Helbing D., Molnar P.: Social force model for pedestrian dynamics. In Physical Review (May 1995), pp. 4282--4286.

[15]

{KGP02} Kovar L., Gleicher M. Pighin F.: Motion graphs. ACM Transactions on Graphics 21, 3 (2002), 473--482.

Digital Library

[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]

{KPS03} Kim T., Park S., Shin S.: Rhythmic-motion synthesis base on motion-beat analysis. ACM Transactions on Graphics 22, 3 (2003), 392--401.

Digital Library

[19]

{LCR*02} Lee J., Chai J., Reitsma P., Hodgins J., Pollard N.: Interactive control of avatars animated with human motion data. ACM Transactions on Graphics 21, 3 (2002), 491--500.

Digital Library

[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]

{LL04} Lee J., Lee K. H.: Precomputing avatar behavior from human motion data. In Proc. of the 2004, ACM SIGGRAPH/Eurographics Symposium on Computer Animation (2004). pp. 79--87.

Digital Library

[23]

{MT01} Musse S. R., Thalmann D.: Hierarchical model for real time simulation of virtaul human crowds. In IEEE Transaction on Visualization and Computer Graphics (2001), pp. 152--164.

Digital Library

[24]

{PLS03} Pettré J., Laumond J.-P., Siméon T.: A 2-stages locomotion planner for digital actors. In SCA '03: Proc. of the 2003 ACM SIGGRAPH/Eurographics Symposium on Computer Animation (2003), pp. 258--264.

Digital Library

[25]

{PSS02} Park S. I., Shin H. J., Shin S. Y.: On-line locomotion generation based on motion blending. In Proc. of the 2002 ACM SIGGRAPH/Eurographics Symposium on Computer Animation (2002), pp. 105--111.

Digital Library

[26]

{PSS04} Park S. I., Shin H. J., Shin S. Y.: Online motion blending for real-time locomotion generation. In Computer Animation and Virtual Worlds 15 (2004), pp. 125--138.

Digital Library

[27]

{RCB98} Rose C., Cohen M., Bodenheimer B.: Verbs and adverbs: Multidimensional motion interpolation. IEEE Computer Graphics and Application 18, 5 (1998), 32--40.

Digital Library

[28]

{RP04} Reitsma P. S. A., Pollard N. S.: Evaluating motion graphs for character navigation. In Proc. of the 2004 ACM SIGGRAPH/Eurographics Symposium on Computer Animation (2004), pp. 89--98.

Digital Library

[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]

{SE02} Schödl A., Essa I.: Controlled animation of video sprites. In Proc. of the 2002 ACM SIGGRAPH/Eurographics Symposium on Computer Animation (2002), pp. 121--127.

Digital Library

[31]

{SM01} Sun H. C., Metaxas D.: Automating gait generation. In Proc. of ACM SIGGRAPH 2001 (July 2001), Annual Conference Series, ACM SIGGRAPH, pp. 261--270.

Digital Library

[32]

{UT02} Ulicny B., Thalmann D.: Towards interactive real-time crowd behavior simulation. Computer Graphics Forum (Nov. 2002), 767--775.

[33]

{WP95} Witkin A., Popović Z.: Motion warping. In Proc. of ACM SIGGRAPH 95 (Aug. 1995), Annual Conference Series. ACM SIGGRAPH, pp. 105--108.

Digital Library

Cited By

Gomez-Nogales GPrieto-Martin MRomero CComino-Trinidad MRamon-Prieto POlivier AHoyet LOtaduy MPettre JCasas D(2024)Resolving Collisions in Dense 3D Crowd AnimationsACM Transactions on Graphics10.1145/368726643:5(1-14)Online publication date: 6-Sep-2024
https://dl.acm.org/doi/10.1145/3687266
Zhou YLai PYu JXiong YYang HCai JKankanhalli MPrabhakaran BBoll SSubramanian RZheng LSingh VCesar PXie LXu D(2024)Hydrodynamics-Informed Neural Network for Simulating Dense Crowd Motion PatternsProceedings of the 32nd ACM International Conference on Multimedia10.1145/3664647.3681277(4553-4561)Online publication date: 28-Oct-2024
https://dl.acm.org/doi/10.1145/3664647.3681277
Lu DZhang GJia X(2024)Stochastic Optimal Intervention for Robot-Assisted Crowd EvacuationIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2023.332542425:5(3812-3827)Online publication date: May-2024
https://doi.org/10.1109/TITS.2023.3325424
Show More Cited By

Index Terms

Fast and accurate goal-directed motion synthesis for crowds
1. Computing methodologies
  1. Artificial intelligence
    1. Computer vision
      1. Image and video acquisition
        3D imaging
  2. Computer graphics
    1. Animation

Recommendations

A vision based system for goal-directed obstacle avoidance
RoboCup 2004

We present a complete system for obstacle avoidance for a mobile robot. It was used in the RoboCup 2003 obstacle avoidance challenge in the Sony Four Legged League. The system enables the robot to detect unknown obstacles and reliably avoid them while ...
Motion synthesis
Synthesis of kinematically constrained full-body motion from stochastic motion model
Abstract
Humanoid robots are expected not only to understand human behaviors but also to perform human-like actions in order to be integrated into our daily lives. Learning by imitation is a powerful framework that can allow robots to generate the same ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

SCA '05: Proceedings of the 2005 ACM SIGGRAPH/Eurographics symposium on Computer animation

July 2005

366 pages

ISBN:1595931988

DOI:10.1145/1073368

Conference Chairs:
Demetri Terzopoulos
New York University, USA
,
Victor Brian Zordan
University of California at Riverside, USA
,
Program Chairs:
Ken Anjyo
OLM Digital, Inc., Japan
,
Petros Faloutsos
University of California at Los Angeles, USA

Copyright © 2005 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques
EUROGRAPHICS: The European Association for Computer Graphics

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 29 July 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SCA05

Sponsor:

SIGGRAPH
EUROGRAPHICS

SCA05: Symposium on Computer Animation

July 29 - 31, 2005

California, Los Angeles

Acceptance Rates

Overall Acceptance Rate 183 of 487 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

93
Total Citations
View Citations
850
Total Downloads

Downloads (Last 12 months)6
Downloads (Last 6 weeks)0

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Gomez-Nogales GPrieto-Martin MRomero CComino-Trinidad MRamon-Prieto POlivier AHoyet LOtaduy MPettre JCasas D(2024)Resolving Collisions in Dense 3D Crowd AnimationsACM Transactions on Graphics10.1145/368726643:5(1-14)Online publication date: 6-Sep-2024
https://dl.acm.org/doi/10.1145/3687266
Zhou YLai PYu JXiong YYang HCai JKankanhalli MPrabhakaran BBoll SSubramanian RZheng LSingh VCesar PXie LXu D(2024)Hydrodynamics-Informed Neural Network for Simulating Dense Crowd Motion PatternsProceedings of the 32nd ACM International Conference on Multimedia10.1145/3664647.3681277(4553-4561)Online publication date: 28-Oct-2024
https://dl.acm.org/doi/10.1145/3664647.3681277
Lu DZhang GJia X(2024)Stochastic Optimal Intervention for Robot-Assisted Crowd EvacuationIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2023.332542425:5(3812-3827)Online publication date: May-2024
https://doi.org/10.1109/TITS.2023.3325424
Tang KZhang JShen YLi CHe G(2024)KDPM: Knowledge‐driven dynamic perception model for evacuation scene simulationComputer Animation and Virtual Worlds10.1002/cav.227935:3Online publication date: 29-May-2024
https://doi.org/10.1002/cav.2279
Starke PStarke SKomura TSteinicke F(2023)Motion In-Betweening with Phase ManifoldsProceedings of the ACM on Computer Graphics and Interactive Techniques10.1145/36069216:3(1-17)Online publication date: 24-Aug-2023
https://dl.acm.org/doi/10.1145/3606921
Chai LLiu YLiu WHan GHe S(2022)CrowdGAN: Identity-Free Interactive Crowd Video Generation and BeyondIEEE Transactions on Pattern Analysis and Machine Intelligence10.1109/TPAMI.2020.304337244:6(2856-2871)Online publication date: 1-Jun-2022
https://doi.org/10.1109/TPAMI.2020.3043372
Musse SCassol VThalmann D(2021)A history of crowd simulation: the past, evolution, and new perspectivesThe Visual Computer10.1007/s00371-021-02252-wOnline publication date: 5-Aug-2021
https://doi.org/10.1007/s00371-021-02252-w
Sun LZhai JQin W(2019)Crowd Navigation in an Unknown and Dynamic Environment Based on Deep Reinforcement LearningIEEE Access10.1109/ACCESS.2019.29334927(109544-109554)Online publication date: 2019
https://doi.org/10.1109/ACCESS.2019.2933492
Schaumann DKapadia MDavis PO'Mahony APfautz J(2019)Modeling Social and Spatial Behavior in Built Environments: Current Methods and Future DirectionsSocial‐Behavioral Modeling for Complex Systems10.1002/9781119485001.ch29(673-695)Online publication date: 29-Mar-2019
https://doi.org/10.1002/9781119485001.ch29
Zhang GLu DLv LYu HLiu H(2018)Knowledge-Based Crowd Motion for the Unfamiliar EnvironmentIEEE Access10.1109/ACCESS.2018.28824356(72581-72593)Online publication date: 2018
https://doi.org/10.1109/ACCESS.2018.2882435
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten