research-article

Extreme-Density Crowd Simulation: Combining Agents with Smoothed Particle Hydrodynamics

Authors:

Wouter van Toll,

Barbara Solenthaler,

Julien PettréAuthors Info & Claims

MIG '20: Proceedings of the 13th ACM SIGGRAPH Conference on Motion, Interaction and Games

Article No.: 11, Pages 1 - 10

https://doi.org/10.1145/3424636.3426896

Published: 22 November 2020 Publication History

Abstract

In highly dense crowds of humans, collisions between people occur often. It is common to simulate such a crowd as one fluid-like entity (macroscopic), and not as a set of individuals (microscopic, agent-based). Agent-based simulations are preferred for lower densities because they preserve the properties of individual people. However, their collision handling is too simplistic for extreme-density crowds. Therefore, neither paradigm is ideal for all possible densities.

In this paper, we combine agent-based crowd simulation with the concept of Smoothed Particle Hydrodynamics (SPH), a particle-based method that is popular for fluid simulation. Our combination augments the usual agent-collision handling with fluid dynamics when the crowd density is sufficiently high. A novel component of our method is a dynamic rest density per agent, which intuitively controls the crowd density that an agent is willing to accept.

Experiments show that SPH improves agent-based simulation in several ways: better stability at high densities, more intuitive control over the crowd density, and easier replication of wave-propagation effects. Our implementation can simulate tens of thousands of agents in real-time. As such, this work successfully prepares the agent-based paradigm for crowd simulation at all densities.

Supplementary Material

MP4 File (a11-van_toll-video.mp4)

Download
57.34 MB

References

[1]

Jan Bender, Tassilo Kugelstadt, Marcel Weiler, and Dan Koschier. 2019. Volume maps: An implicit boundary representation for SPH. In Motion, Interaction and Games. Article 26, 10 pages.

[2]

Arianna Bottinelli and Jesse L. Silverberg. 2018. Can high-density human collective motion be forecasted by spatiotemporal fluctuations?arXiv:1809.07875 (2018).

[3]

Sean Curtis, Andrew Best, and Dinesh Manocha. 2016. Menge: A modular framework for simulating crowd movement. Collective Dynamics 1, A1 (2016), 1–40.

[4]

Teofilo B. Dutra, Ricardo Marques, Joaquim B. Cavalcante-Neto, Creto A. Vidal, and Julien Pettré. 2017. Gradient-based steering for vision-based crowd simulation algorithms. Comput. Graph. Forum 36, 2 (2017), 337–348.

Digital Library

[5]

Ángel Garcimartín, Daniel R. Parisi, Jose M. Pastor, César Martín-Gómez, and Iker Zuriguel. 2016. Flow of pedestrians through narrow doors with different competitiveness. J. Stat. Mech. Theory Exp.4 (2016), 043402.

[6]

Robert A. Gingold and Joseph J. Monaghan. 1977. Smoothed particle hydrodynamics: theory and application to non-spherical stars. Mon. Not. Roy. Astron. Soc. 181, 11 (1977), 375–389.

[7]

Abhinav Golas, Rahul Narain, and Ming C. Lin. 2014. Continuum modeling of crowd turbulence. Physical Review E 90, 4 (2014), 042816.

[8]

Stephen J. Guy, Jatin Chhugani, Sean Curtis, Pradeep Dubey, Ming Lin, and Dinesh Manocha. 2010. PLEdestrians: A least-effort approach to crowd simulation. In Proc. ACM SIGGRAPH/Eurographics Symp. Computer Animation. 119–128.

[9]

Dirk Helbing, Illés Farkas, and Tamás Vicsek. 2000. Simulating dynamical features of escape panic. Nature 407(2000), 487–490.

[10]

Dirk Helbing and Péter Molnár. 1995. Social force model for pedestrian dynamics. Physical Review E 51, 5 (1995), 4282–4286.

[11]

Omar Hesham and Gabriel Wainer. 2017. Context-sensitive personal space for dense crowd simulation. In Proc. Symp. Simulation for Architecture and Urban Design. Article 19, 8 pages.

[12]

Roger L. Hughes. 2003. The flow of human crowds. Annu. Rev. Fluid Mech. 35, 35 (2003), 169–182.

[13]

Ioannis Karamouzas, Brian Skinner, and Stephen J. Guy. 2014. Universal power law governing pedestrian interactions. Phys. Rev. Lett. 113(2014), 238701:1–5. Issue 23.

[14]

Peter M. Kielar, Daniel H. Biedermann, and André Borrmann. 2016. MomenTUMv2: A modular, extensible, and generic agent-based pedestrian behavior simulation framework. Technical Report TUM-I1643. TU München, Institut für Informatik.

[15]

Sujeong Kim, Stephen J. Guy, Karl Hillesland, Basim Zafar, Adnan Abdul-Aziz Gutub, and Dinesh Manocha. 2015. Velocity-based modeling of physical interactions in dense crowds. The Visual Computer 31(2015), 541–555. Issue 5.

Digital Library

[16]

Dan Koschier, Jan Bender, Barbara Solenthaler, and Matthias Teschner. 2019. Smoothed Particle Hydrodynamics techniques for the physics based simulation of fluids and solids. In Eurographics 2019 Tutorials.

[17]

Leon B. Lucy. 1977. A numerical approach to the testing of the fission hypothesis. The Astronomical Journal 82, 12 (1977), 1013–1024.

[18]

Bertrand Maury, Aude Roudneff-Chupin, and Filippo Santambrogio. 2010. A macroscopic crowd motion model of gradient flow type. Math. Mod. Meth. Appl. S. 20, 10 (2010), 1787–1821.

[19]

Matthias Müller, David Charypar, and Markus Gross. 2003. Particle-based fluid simulation for interactive applications. In Proc. ACM SIGGRAPH/Eurographics Symp. Computer Animation. 154–159.

[20]

Rahul Narain, Abhinav Golas, Sean Curtis, and Ming C. Lin. 2009. Aggregate dynamics for dense crowd simulation. ACM Trans. Graph. 28(2009), 1–8. Issue 5.

Digital Library

[21]

Nuria Pelechano, Jan M. Allbeck, and Norman I. Badler. 2007. Controlling individual agents in high-density crowd simulation. In Proc. ACM SIGGRAPH/Eurographics Symp. Computer Animation. 99–108.

[22]

Nuria Pelechano, Jan M. Allbeck, Mubbasir Kapadia, and Norman I. Badler. 2016. Simulating Heterogeneous Crowds with Interactive Behaviors. CRC Press.

Digital Library

[23]

Kalle Sjöström. 2011. Computational fluid dynamics in 2D game environments. Master’s thesis. Umeå University.

[24]

Sybren A. Stüvel, Nadia Magnenat-Thalmann, Daniel Thalmann, and A. Frank van der Stappen. 2016. Torso crowds. IEEE Trans. Vis. Comput. Graphics 23, 7 (2016), 1823–1837.

Digital Library

[25]

Weerawat Tantisiriwat, Arisara Sumleeon, and Pizzanu Kanongchaiyos. 2007. A crowd simulation using individual-knowledge-merge based path construction and Smoothed Particle Hydrodynamics. In Proc. 15th Int. Conf. in Central Europe on Computer Graphics, Visualization and Computer Vision. 261–268.

[26]

Daniel Thalmann and Soraia R. Musse. 2013. Crowd Simulation (2ed.). Springer.

[27]

Wouter tollvan Toll, Fabien Grzeskowiak, Axel López, Javad Amirian, Florian Berton, Julien Bruneau, Beatriz Daniel, Alberto Jovane, and Julien Pettré. 2020. Generalized microscopic crowd simulation using costs in velocity space. In Proc. ACM SIGGRAPH Symp. Interactive 3D Graphics and Games. 10 pages.

[28]

Wouter tollvan Toll, Norman Jaklin, and Roland Geraerts. 2015. Towards believable crowds: A generic multi-level framework for agent navigation. In ASCI.OPEN.

[29]

Adrien Treuille, Seth Cooper, and Zoran Popović. 2006. Continuum crowds. ACM Trans. Graph. 25(2006), 1160–1168. Issue 3.

Digital Library

[30]

Jur P. van den Berg, Stephen J. Guy, Ming C. Lin, and Dinesh Manocha. 2011. Reciprocal n-body collision avoidance. In Proc. Int. Symp. Robotics Research. 3–19.

[31]

Christin Vetter, Lars Oetting, Christian Ulrich, and Thomas Rung. 2011. SPH simulations of pedestrian crowds. In Proc. 6th Int. Spheric Workshop. 261–268.

[32]

Tomer Weiss, Chenfanfu Jiang, Alan Litteneker, and Demetri Terzopoulos. 2017. Position-based multi-agent dynamics for real-time crowd simulation. In Proc. 10th Int. Conf. Motion in Games. 10:1–10:8.

[33]

Yufei Yuan, Bernat Goñi-Ros, Ha H. Bui, Winnie Daamen, Hai L. Vu, and Serge P. Hoogendoorn. 2020. Macroscopic pedestrian flow simulation using Smoothed Particle Hydrodynamics. Transp. Res. Part C Emerg. Technol. 111 (2020), 334 – 351.

Cited By

Dang HGaudou BVerstaevel N(2024)A literature review of dense crowd simulationSimulation Modelling Practice and Theory10.1016/j.simpat.2024.102955134(102955)Online publication date: Jul-2024
https://doi.org/10.1016/j.simpat.2024.102955
Zhao RRahman AWei BLi CMa YCai YHan L(2024)A Literature Review of Contacting Force Measurement Methods for Pedestrian CrowdsHeliyon10.1016/j.heliyon.2024.e39755(e39755)Online publication date: Oct-2024
https://doi.org/10.1016/j.heliyon.2024.e39755
Allcock RSiebers P(2024)Crowd Health Encoding, for Crowd Simulations Using the Smoothed Particle Hydrodynamics Computational MethodAdvances in Social Simulation10.1007/978-3-031-57785-7_3(21-33)Online publication date: 21-Jul-2024
https://doi.org/10.1007/978-3-031-57785-7_3
Show More Cited By

Recommendations

Numerical simulation of interfacial flows by smoothed particle hydrodynamics

An implementation of the smoothed particle hydrodynamics (SPH) method is presented to treat two-dimensional interfacial flows, that is, flow fields with different fluids separated by sharp interfaces. Test cases are presented to show that the present ...
Smoothed particle hydrodynamics and finite volume modelling of incompressible fluid flow

Fundamentals of two different numerical approaches to the fluid flow modelling are presented. The smoothed particle hydrodynamics (SPH) is a meshless approach, while the finite volume (FV) method is defined on a grid. Within SPH, the computational grid ...
Pairwise Force Smoothed Particle Hydrodynamics model for multiphase flow

We present a novel formulation of the Pairwise Force Smoothed Particle Hydrodynamics (PF-SPH) model and use it to simulate two- and three-phase flows in bounded domains. In the PF-SPH model, the Navier-Stokes equations are discretized with the Smoothed ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

MIG '20: Proceedings of the 13th ACM SIGGRAPH Conference on Motion, Interaction and Games

October 2020

190 pages

ISBN:9781450381710

DOI:10.1145/3424636

Copyright © 2020 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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 November 2020

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed limited

Conference

MIG '20

Sponsor:

SIGGRAPH

MIG '20: Motion, Interaction and Games

October 16 - 18, 2020

SC, Virtual Event, USA

Acceptance Rates

Overall Acceptance Rate -9 of -9 submissions, 100%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
160
Total Downloads

Downloads (Last 12 months)44
Downloads (Last 6 weeks)7

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Dang HGaudou BVerstaevel N(2024)A literature review of dense crowd simulationSimulation Modelling Practice and Theory10.1016/j.simpat.2024.102955134(102955)Online publication date: Jul-2024
https://doi.org/10.1016/j.simpat.2024.102955
Zhao RRahman AWei BLi CMa YCai YHan L(2024)A Literature Review of Contacting Force Measurement Methods for Pedestrian CrowdsHeliyon10.1016/j.heliyon.2024.e39755(e39755)Online publication date: Oct-2024
https://doi.org/10.1016/j.heliyon.2024.e39755
Allcock RSiebers P(2024)Crowd Health Encoding, for Crowd Simulations Using the Smoothed Particle Hydrodynamics Computational MethodAdvances in Social Simulation10.1007/978-3-031-57785-7_3(21-33)Online publication date: 21-Jul-2024
https://doi.org/10.1007/978-3-031-57785-7_3
Serena LMarzolla MD’Angelo GFerretti S(2023)A review of multilevel modeling and simulation for human mobility and behaviorSimulation Modelling Practice and Theory10.1016/j.simpat.2023.102780127(102780)Online publication date: Sep-2023
https://doi.org/10.1016/j.simpat.2023.102780
Brugière ANguyen-Ngoc DDrogoul A(2022)Handling multiple levels in agent-based models of complex socio-environmental systems: A comprehensive reviewFrontiers in Applied Mathematics and Statistics10.3389/fams.2022.10203538Online publication date: 1-Dec-2022
https://doi.org/10.3389/fams.2022.1020353
Cabrero‐Daniel BMarques RHoyet LPettré JBlat J(2022)Dynamic Combination of Crowd Steering Policies Based on ContextComputer Graphics Forum10.1111/cgf.1446941:2(209-219)Online publication date: 24-May-2022
https://doi.org/10.1111/cgf.14469

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.

HTML Format

View this article in HTML Format.

Media

Figures

Other

Tables

View Table of Contents