“Implicit Integration for Robust Collision-Free Crowd Simulation” by Karamouzas, Sohre, Narain and Guy

  • ©Ioannis Karamouzas, Nick Sohre, Rahul Narain, and Stephen J. Guy

Conference:


Type:


Title:

    Implicit Integration for Robust Collision-Free Crowd Simulation

Session/Category Title: Simulation for Virtual Worlds

Presenter(s)/Author(s):


Moderator(s):


Abstract:


    Large multi-agent systems such as crowds involve inter-agent interactions that are typically anticipatory in nature, depending strongly on both the positions and the velocities of agents. We show how the nonlinear, anticipatory forces seen in multi-agent systems can be made compatible with recent work on energy-based formulations in physics-based animation, and propose a simple and effective optimization-based integration scheme for implicit integration of such systems. We apply this approach to crowd simulation by using a state-of-the-art model derived from a recent analysis of human crowd data, and adapting it to our framework. Our approach provides, for the first time, guaranteed collision-free motion while simultaneously maintaining high-quality collective behavior in a way that is insensitive to simulation parameters such as time step size and crowd density. These benefits are demonstrated through simulation results on various challenging scenarios and validation against real-world crowd data.

References:


    1. David Baraff and Andrew Witkin. 1998. Large Steps in Cloth Simulation. In Proceedings of the 25th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH ’98). ACM, 43–54. 
    2. Sofien Bouaziz, Sebastian Martin, Tiantian Liu, Ladislav Kavan, and Mark Pauly. 2014. Projective Dynamics: Fusing Constraint Projections for Fast Simulation. ACM Transaction on Graphics (2014), 154:1–154:11.
    3. Panayiotis Charalambous and Yiorgos Chrysanthou. 2014. The PAG Crowd: A Graph Based Approach for Efficient Data-Driven Crowd Simulation. Computer Graphics Forum 33, 8 (2014), 95–108. 
    4. Panayiotis Charalambous, Ioannis Karamouzas, Stephen J. Guy, and Yiorgos Chrysanthou. 2014. A Data-Driven Framework for Visual Crowd Analysis. Computer Graphics Forum 33, 7 (2014), 41–50. 
    5. Teófilo Dutra, Ricardo Marques, Joaquim B. Cavalcante-Neto, Creto Augusto Vidal, and Julien Pettré. 2017. Gradient-based steering for vision-based crowd simulation algorithms. Computer Graphics Forum 36, 2 (2017). 
    6. Paolo Fiorini and Zvi Shiller. 1998. Motion Planning in Dynamic Environments using Velocity Obstacles. The International Journal of Robotics Research 17, 7 (1998), 760–772. 
    7. Marco Fratarcangeli, Valentina Tibaldo, and Fabio Pellacini. 2016. Vivace: A Practical Gauss-seidel Method for Stable Soft Body Dynamics. ACM Transaction on Graphics 35, 6 (2016), 214:1–214:9.
    8. Theodore F. Gast, Craig Schroeder, Alexey Stomakhin, Chenfanfu Jiang, and Joseph M. Teran. 2015. Optimization Integrator for Large Time Steps. IEEE Transactions on Visualization and Computer Graphics 21, 10 (2015), 1103–1115. 
    9. Herbert Goldstein. 1980. Classical Mechanics. Addison-Wesley.
    10. Dirk Helbing, Illés Farkas, and Tamas Vicsek. 2000. Simulating dynamical features of escape panic. Nature 407, 6803 (2000), 487–490. 
    11. Dirk Helbing and Péter Molnár. 1995. Social Force Model for Pedestrian Dynamics. Physical Review E 51 (1995), 4282–4286. 
    12. Dirk Helbing, Péter Molnár, Illés J. Farkas, and Kai Bolay. 2001. Self-Organizing Pedestrian Movement. Environment and Planning B: Planning and Design 28, 3 (2001), 361–383. 
    13. Rowan Hughes, Jan Ondřej, and John Dingliana. 2014. Holonomic Collision Avoidance for Virtual Crowds. In ACM SIGGRAPH/Eurographics Symposium on Computer Animation. 103–111.
    14. Rowan Hughes, Jan Ondřej, and John Dingliana. 2015. DAVIS: density-adaptive synthetic-vision based steering for virtual crowds. In Motion in Games. ACM, 79–84. 
    15. Roger L. Hughes. 2002. A continuum theory for the flow of pedestrians. Transportation Research Part B: Methodological 36, 6 (2002), 507–535. 
    16. Eunjung Ju, Myung Geol Choi, Minji Park, Jehee Lee, Kang Hoon Lee, and Shigeo Takahashi. 2010. Morphable crowds. ACM Transactions on Graphics 29 (2010), 140:1–140:10. Issue 6.
    17. Couro Kane, Jerrold E. Marsden, Michael Ortiz, and Matt West. 2000. Variational integrators and the Newmark algorithm for conservative and dissipative mechanical systems. Internat. J. Numer. Methods Engrg. 49, 10 (2000). 
    18. Mubbasir Kapadia, Nuria Pelechano, Jan Allbeck, and Norm Badler. 2015. Virtual crowds: Steps toward behavioral realism. Synthesis Lectures on Visual Computing: Computer Graphics, Animation, Computational Photography, and Imaging 7, 4 (2015), 1–270. 
    19. Mubbasir Kapadia, Shawn Singh, Brian Allen, Glenn Reinman, and Petros Faloutsos. 2009. Steerbug: an interactive framework for specifying and detecting steering behaviors. In ACM SIGGRAPH/Eurographics Symposium on Computer Animation. 209–216. 
    20. Mubbasir Kapadia, Shawn Singh, William Hewlett, Glenn Reinman, and Petros Faloutsos. 2012. Parallelized egocentric fields for autonomous navigation. The Visual Computer 28, 12 (2012), 1209–1227. 
    21. Ioannis Karamouzas, Peter Heil, Pascal van Beek, and Mark H. Overmars. 2009. A Predictive Collision Avoidance Model for Pedestrian Simulation. In Motion in Games. 41–52. 
    22. Ioannis Karamouzas, Brian Skinner, and Stephen J. Guy. 2014. Universal Power Law Governing Pedestrian Interactions. Physical Review Letters 113 (2014), 238701. Issue 23.
    23. Danny M. Kaufman, Rasmus Tamstorf, Breannan Smith, Jean-Marie Aubry, and Eitan Grinspun. 2014. Adaptive Nonlinearity for Collisions in Complex Rod Assemblies. ACM Transactions on Graphics 33, 4 (2014), 123:1–123:12.
    24. Liliya Kharevych, Weiwei Yang, Yiying Tong, Eva Kanso, Jerrold E. Marsden, Peter Schröder, and Matthieu Desbrun. 2006. Geometric, Variational Integrators for Computer Animation. In ACM SIGGRAPH/Eurographics Symposium on Computer Animation. 43–51.
    25. Jongmin Kim, Yeongho Seol, Taesoo Kwon, and Jehee Lee. 2014. Interactive Manipulation of Large-scale Crowd Animation. ACM Transactions on Graphics 33, 4 (2014), 83:1–83:10.
    26. Alon Lerner, Yiorgos Chrysanthou, and Dani Lischinski. 2007. Crowds by example. Computer Graphics Forum 26 (2007), 655–664. 
    27. Alon Lerner, Yiorgos Chrysanthou, Ariel Shamir, and Daniel Cohen-Or. 2010. Context-Dependent Crowd Evaluation. Computer Graphics Forum 29, 7 (2010), 2197–2206. 
    28. Tiantian Liu, Adam W. Bargteil, James F. O’Brien, and Ladislav Kavan. 2013. Fast Simulation of Mass-spring Systems. ACM Transactions on Graphics 32, 6 (2013), 214:1–214:7.
    29. Tiantian Liu, Sofien Bouaziz, and Ladislav Kavan. 2016. Towards Real-time Simulation of Hyperelastic Materials. arXiv preprint arXiv:1604.07378 (2016).
    30. Jerrold E. Marsden and Tudor Ratiu. 1999. Introduction to Mechanics and Symmetry. Springer. 
    31. Sebastian Martin, Bernhard Thomaszewski, Eitan Grinspun, and Markus Gross. 2011. Example-based Elastic Materials. ACM Transactions on Graphics 30, 4 (2011), 72:1–72:8.
    32. Mehdi Moussaïd, Dirk Helbing, and Guy Theraulaz. 2011. How simple rules determine pedestrian behavior and crowd disasters. Proceedings of the National Academy of Sciences 108, 17 (2011), 6884–6888. 
    33. Rahul Narain, Abhinav Golas, Sean Curtis, and Ming C. Lin. 2009. Aggregate Dynamics for Dense Crowd Simulation. ACM Transaction on Graphics 28, 5 (2009), 122:1–122:8.
    34. Rahul Narain, Matthew Overby, and George E. Brown. 2016. ADMM ⊇ Projective Dynamics: Fast Simulation of General Constitutive Models. In ACM SIGGRAPH/Eurographics Symposium on Computer Animation. 21–28.
    35. Jorge Nocedal and Steve J. Wright. 2006. Numerical optimization. Springer.
    36. Aline Normoyle, Maxim Likhachev, and Alla Safonova. 2014. Stochastic Activity Authoring with Direct User Control. In ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games. 31–38. 
    37. Anne-Hélène Olivier, Antoine Marin, Armel Crétual, and Julien Pettré. 2012. Minimal predicted distance: A common metric for collision avoidance during pairwise interactions between walkers. Gait Posture 36, 3 (2012), 399–404. 
    38. Jan Ondřej, Julien Pettré, Anne-Hélène Olivier, and Stéphane Donikian. 2010. A synthetic-vision based steering approach for crowd simulation. ACM Transactions on Graphics 29, 4 (2010), 1–9. 
    39. Nuria Pelechano, Jan M. Allbeck, and Norman I. Badler. 2007. Controlling individual agents in high-density crowd simulation. In ACM SIGGRAPH/Eurographics Symposium on Computer Animation. 99–108.
    40. Stefano Pellegrini, Andrea Ess, Konrad Schindler, and Luc Van Gool. 2009. You’ll never walk alone: Modeling social behavior for multi-target tracking. In IEEE International Conference on Computer Vision. 261–268. 
    41. Julien Pettré, Jan Ondřej, Anne-Hélène Olivier, Armel Crétual, and Stéphane Donikian. 2009. Experiment-based Modeling, Simulation and Validation of Interactions between Virtual Walkers. In ACM SIGGRAPH/Eurographics Symposium on Computer Animation. 189–198.
    42. Craig W. Reynolds. 1987. Flocks, herds, and schools: A distributed behavioral model. Computer Graphics 21, 4 (1987), 24–34. 
    43. Craig W. Reynolds. 1999. Steering Behaviors For Autonomous Characters. In Game Developers Conference. 763–782.
    44. Armin Seyfried, Oliver Passon, Bernhard Steffen, Maik Boltes, Tobias Rupprecht, and Wolfram Klingsch. 2009. New insights into pedestrian flow through bottlenecks. Transportation Science 43, 3 (2009), 395–406. 
    45. Shawn Singh, Mubbasir Kapadia, Billy Hewlett, Glenn Reinman, and Petros Faloutsos. 2011a. A Modular Framework for Adaptive Agent-based Steering. In ACM Symposium on Interactive 3D Graphics and Games. 141–150. 
    46. Shawn Singh, Mubbasir Kapadia, Glenn Reinman, and Petros Faloutsos. 2011b. Footstep navigation for dynamic crowds. Computer Animation and Virtual Worlds 22, 2–3 (2011), 151–158.
    47. Sybren Stuvel, Nadia Magnenat-Thalmann, Daniel Thalmann, A Frank van der Stappen, and Arjan Egges. 2016. Torso Crowds. IEEE Transactions on Visualization and Computer Graphics (2016).
    48. Demetri Terzopoulos, John Platt, Alan Barr, and Kurt Fleischer. 1987. Elastically Deformable Models. In Proceedings of the 14th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH ’87). ACM, 205–214. 
    49. Adrien Treuille, Seth Cooper, and Zoran Popović. 2006. Continuum crowds. ACM Transactions on Graphics 25, 3 (2006), 1160–1168. 
    50. Jur van den Berg, Stephen J. Guy, Ming C. Lin, and Dinesh Manocha. 2011. Reciprocal n-body Collision Avoidance. In International Symposium of Robotics Research. 3–19. 
    51. Jur van den Berg, Ming C. Lin, and Dinesh Manocha. 2008. Reciprocal Velocity Obstacles for real-time multi-agent navigation. In IEEE International Conference on Robotics and Automation. 1928–1935. 
    52. Huamin Wang and Yin Yang. 2016. Descent Methods for Elastic Body Simulation on the GPU. ACM Transaction on Graphics 35, 6 (2016), 212:1–212:10.
    53. Marcel Weiler, Dan Koschier, and Jan Bender. 2016. Projective Fluids. In ACM Motion in Games. 79–84. 
    54. David Wolinski, Ming C. Lin, and Julien Pettré. 2016. WarpDriver: context-aware probabilistic motion prediction for crowd simulation. ACM Transactions on Graphics 35, 6 (2016), 164.
    55. Manqi Zhao and Venkatesh Saligrama. 2009. Anomaly detection with score functions based on nearest neighbor graphs. In Advances in neural information processing systems. 2250–2258.

ACM Digital Library Publication:


Overview Page: