Skip to main content
SpringerLink
Log in

Velocity-based modeling of physical interactions in dense crowds

  • Original Article
  • Published:
The Visual Computer Aims and scope Submit manuscript

Abstract

We present an interactive algorithm to model physics-based interactions in dense crowds. Our approach is capable of modeling both physical forces and interactions between agents and obstacles, while also allowing the agents to anticipate and avoid upcoming collisions during local navigation. We combine velocity-based collision-avoidance algorithms with external physical forces. The overall formulation produces various effects of forces acting on agents and crowds, including balance recovery motion and force propagation through the crowd. We further extend our method to model more complex behaviors involving social and cultural rules. We use finite-state machines to specify a series of behaviors and demonstrate our approach on many complex scenarios. Our algorithm can simulate a few thousand agents at interactive rates and can generate many emergent behaviors.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15
Fig. 16

Similar content being viewed by others

References

  1. AMD: Bullet Physics 2.80. http://bulletphysics.org (2012)

  2. Baraff, D.: An introduction to physically based modeling: rigid body simulation i - unconstrained rigid body dynamics. In: An Introduction to Physically Based Modelling, SIGGRAPH ’97 Course, Notes, p. 97 (1997)

  3. Buckland, M.: Programming game AI by example. Jones & Bartlett Learning (2005)

  4. Curtis, S., Guy, S.J., Zafar, B., Manocha, D.: Virtual tawaf: a case study in simulating the behavior of dense, heterogeneous crowds. In: 1st IEEE Workshop on Modeling, Simulation and Visual Analysis of Large Crowds, pp. 128–135 (2011)

  5. Curtis, S., Manocha, D.: Pedestrian simulation using geometric reasoning in velocity space. In: Proceedings of Pedestrian and Evacuation Dynamics (2012)

  6. Curtis, S., Snape, J., Manocha, D.: Way portals: efficient multi-agent navigation with line-segment goals. In: Proceedings of the ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games. I3D ’12, pp. 15–22. ACM, New York (2012)

  7. Durupinar, F., Pelechano, N., Allbeck, J., Güdükbay, U., Badler, N.: How the ocean personality model affects the perception of crowds. Comput. Graphics Appl. IEEE 31(3), 22–31 (2011)

  8. Guy, S.J., Curtis, S., Lin, M.C., Manocha, D.: Least-effort trajectories lead to emergent crowd behaviors. Phys. Rev. E 85, 016110 (2012)

  9. Guy, S.J., Kim, S., Lin, M.C., Manocha, D.: Simulating heterogeneous crowd behaviors using personality trait theory. In: Symposium on Computer Animation, pp. 43–52. ACM (2011)

  10. Helbing, D., Farkas, I., Vicsek, T.: Simulating dynamical features of escape panic. Nature 407(6803), 487–490 (2000)

    Article  Google Scholar 

  11. Helbing, D., Molnár, P.: Social force model for pedestrian dynamics. Phys. Rev. E 51, 4282–4286 (1995)

    Article  Google Scholar 

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

    Article  Google Scholar 

  13. Karamouzas, I., Overmars, M.: Simulating and evaluating the local behavior of small pedestrian groups. IEEE Trans. Vis. Comput. Graphics 18(3), 394–406 (2012)

  14. Kim, M., Hyun, K., Kim, J., Lee, J.: Synchronized multi-character motion editing. ACM Trans. Graph. 28(3), 79:1–79:9 (2009)

  15. Kim, S., Guy, S.J., Manocha, D.: Velocity-based modeling of physical interactions in multi-agent simulations. In: Eurographics/ACM SIGGRAPH Symposium on Computer Animation. Eurographics Association (2013)

  16. Kim, S., Guy, S.J., Manocha, D., Lin, M.C.: Interactive simulation of dynamic crowd behaviors using general adaptation syndrome theory. Symposium on Interactive 3D Graphics. I3D ’12, pp. 55–62. ACM, New York (2012)

  17. Koshak, N., Fouda, A.: Analyzing pedestrian movement in mataf using gps and gis to support space redesign. In: The 9th International Conference on Design and Decision Support Systems in Architecture and Urban, Planning (2008)

  18. Köster, G., Treml, F., Gödel, M.: Avoiding numerical pitfalls in social force models. Phys. Rev. E 87, 063305 (2013). doi:10.1103/PhysRevE.87.063305

  19. Lee, K.H., Choi, M.G., Hong, Q., Lee, J.: Group behavior from video: a data-driven approach to crowd simulation. In: Symposium on Computer, Animation, pp. 109–118 (2007)

  20. Lemercier, S., Jelic, A., Kulpa, R., Hua, J., Fehrenbach, J., Degond, P., Appert-Rolland, C., Donikian, S., Pettré, J.: Realistic following behaviors for crowd simulation. Comput. Graph. Forum 31(2pt2), 489–498 (2012)

  21. Lerner, A., Chrysanthou, Y., Shamir, A., Cohen-Or, D.: Data driven evaluation of crowds. In: MIG, pp. 75–83 (2009)

  22. Maki, B., McIlroy, W., Fernie, G.: Change-in-support reactions for balance recovery. IEEE Eng. Med. Biol. Mag. 22(2), 20–26 (2003)

    Article  Google Scholar 

  23. Muico, U., Popović, J., Popović, Z.: Composite control of physically simulated characters. ACM Trans. Graph. 30(3) (2011)

  24. Musse, S.R., Thalmann, D.: A model of human crowd behavior: group inter-relationship and collision detection analysis. In: Proc. Workshop of Computer Animation and Simulation of Eurographics’97, pp. 39–51 (1997)

  25. Narain, R., Golas, A., Curtis, S., Lin, M.C.: Aggregate dynamics for dense crowd simulation. ACM Trans. Graph. 28(5), 122:1–122:8 (2009)

  26. Ondřej, J., Pettré, J., Olivier, A.H., Donikian, S.: A synthetic-vision based steering approach for crowd simulation. ACM Trans. Graph. 29(4), 123:1–123:9 (2010)

  27. Pelechano, N., Allbeck, J.M., Badler, N.I.: Controlling individual agents in high-density crowd simulation. In: Symposium on Computer, Animation, pp. 99–108 (2007)

  28. Pettré, J., Ondřej, J., Olivier, A.H., Cretual, A., Donikian, S.: Experiment-based modeling, simulation and validation of interactions between virtual walkers. In: Symposium on Computer Animation, SCA ’09, pp. 189–198. ACM (2009)

  29. Reynolds, C.: Steering behaviors for autonomous characters. In: Game Developers Conference 1999 (1999)

  30. Sakuma, T., Mukai, T., Kuriyama, S.: Psychological model for animating crowded pedestrians: virtual humans and social agents. Comput. Anim. Virtual Worlds 16, 343–351 (2005)

    Article  Google Scholar 

  31. Seyfried, A., Steffen, B., Klingsch, W., Boltes, M.: The fundamental diagram of pedestrian movement revisited. J. Stat. Mech. 2005, P10,002 (2005)

  32. Shao, W., Terzopoulos, D.: Autonomous pedestrians. In: Symposium on Computer, Animation, pp. 19–28 (2005)

  33. Shapiro, A., Pighin, F., Faloutsos, P.: Hybrid control for interactive character animation. In: Pacific Conference on Computer Graphics and Applications, PG ’03, p. 455. IEEE Computer Society, Washington, DC (2003)

  34. Shiratori, T., Coley, B., Cham, R., Hodgins, J.K.: Simulating balance recovery responses to trips based on biomechanical principles. In: Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation (2009)

  35. Shum, H.P.H., Komura, T., Yamazaki, S.: Simulating multiple character interactions with collaborative and adversarial goals. IEEE Trans. Vis. Comput. Graph. 18(5), 741–752 (2012)

    Article  Google Scholar 

  36. Sok, K.W., Yamane, K., Lee, J., Hodgins, J.: Editing dynamic human motions via momentum and force. Symposium on Computer Animation. SCA ’10, pp. 11–20. Eurographics Association, Aire-la-Ville (2010)

  37. Still, G.K.: Proximate and distal causality. http://www.gkstill.com/ExpertWitness/CrowdDisasters.html (2013)

  38. Thalmann, D., Musse, S.: Behavioral animation of crowds. In: Crowd Simulation, pp. 111–168. Springer, London (2013).doi:10.1007/978-1-4471-4450-2_5

  39. Treuille, A., Cooper, S., Popović, Z.: Continuum crowds. In: ACM SIGGRAPH 2006, pp. 1160–1168. ACM (2006)

  40. Ulicny, B., Thalmann, D.: Towards interactive real-time crowd behavior simulation. In: Computer Graphics Forum, vol. 21, pp. 767–775. Wiley Online, Library (2002)

  41. van den Berg, J., Guy, S.J., Lin, M., Manocha, D.: Reciprocal n-body collision avoidance. In: Robotics Research: 14th ISRR (STAR), vol. 70, pp. 3–19 (2011)

  42. Wei, Y., Gang, B., Zuwen, W.: Balance recovery for humanoid robot in the presence of unknown external push. In: International Conference on Mechatronics and Automation, 2009. ICMA 2009, pp. 1928–1933 (2009). doi:10.1109/ICMA.2009.5246563

  43. Yeh, H., Curtis, S., Patil, S., van den Berg, J., Manocha, D., Lin, M.: Composite agents. In: Symposium on Computer, Animation, pp. 39–47 (2008)

  44. Yu, Q., Terzopoulos, D.: A decision network framework for the behavioral animation of virtual humans. In: Symposium on Computer, Animation, pp. 119–128 (2007)

  45. Yu, W., Johansson, A.: Modeling crowd turbulence by many-particle simulations. Phys. Rev. E 76, 046105 (2007)

  46. Zordan, V.B., Majkowska, A., Chiu, B., Fast, M.: Dynamic response for motion capture animation. ACM Trans. Graph. 24(3), 697–701 (2005)

    Article  Google Scholar 

Download references

Acknowledgments

This work was supported by NSF awards 1000579, 1117127, 1305286, Intel, AMD, and a grant from the Boeing Company. We also thank the Center of Research Excellence in Hajj and Omrah (HajjCoRE) for its support through the collaboration project titled “Simulate the movement of individual in large-scale crowds during Tawaf”.

Author information

Authors and Affiliations

  1. University of North Carolina at Chapel Hill, Chapel Hill, USA

    Sujeong Kim & Dinesh Manocha

  2. University of Minnesota, Minneapolis, USA

    Stephen J. Guy

  3. Advanced Micro Devices, Sunnyvale, USA

    Karl Hillesland

  4. Hajj Research Institute, Umm Al-Qura University, Mecca, Saudi Arabia

    Basim Zafar

  5. The Custodian of the Two Holy Mosques Institute of the Hajj & Omrah Research, Umm Al-Qura University, Mecca, Saudi Arabia

    Adnan Abdul-Aziz Gutub

Authors
  1. Sujeong Kim
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Stephen J. Guy
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Karl Hillesland
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Basim Zafar
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Adnan Abdul-Aziz Gutub
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Dinesh Manocha
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Sujeong Kim.

Additional information

A preliminary version of this paper appeared in [15].

Electronic supplementary material

Below is the link to the electronic supplementary material.

Supplementary material 1 (mp4 23814 KB)

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Kim, S., Guy, S.J., Hillesland, K. et al. Velocity-based modeling of physical interactions in dense crowds. Vis Comput 31, 541–555 (2015). https://doi.org/10.1007/s00371-014-0946-1

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00371-014-0946-1

Keywords

Search

Navigation