Rahul Narain
ABSTRACT
Large dense crowds show aggregate behavior with reduced individual freedom of movement. We present a novel, scalable approach for simulating such crowds, using a dual representation both as discrete agents and as a single continuous system. In the continuous setting, we introduce a novel variational constraint called unilateral incompressibility, to model the large-scale behavior of the crowd, and accelerate inter-agent collision avoidance in dense scenarios. This approach makes it possible to simulate very large, dense crowds composed of up to a hundred thousand agents at near-interactive rates on desktop computers.
Supplemental Material
- Batty, C., Bertails, F., and Bridson, R. 2007. A fast variational framework for accurate solid-fluid coupling. ACM Trans. Graph. 26, 3, 100. Google Scholar
Digital Library
- Bayazit, O. B., Lien, J.-M., and Amato, N. M. 2002. Better group behaviors in complex environments with global roadmaps. Proc. 8th Intl. Conf. Artificial Life, 362--370. Google ScholarDigital Library
- Bridson, R., and Müller-Fischer, M. 2007. Fluid simulation. In ACM SIGGRAPH 2007 courses, 1--81. Google ScholarDigital Library
- Chenney, S. 2004. Flow tiles. Proc. ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 233--242. Google ScholarDigital Library
- Cordeiro, O. C., Braun, A., Silveria, C. B., Musse, S. R., and Cavalheiro, G. G. 2005. Concurrency on social forces simulation model. First Intl. Workshop on Crowd Simulation.Google Scholar
- Dostál, Z., and Schöberl, J. 2005. Minimizing quadratic functions subject to bound constraints with the rate of convergence and finite termination. Comput. Optim. Appl. 30, 1, 23--43. Google ScholarDigital Library
- Feurtey, F. 2000. Simulating the Collision Avoidance Behavior of Pedestrians. Master's thesis, University of Tokyo, School of Engineering.Google Scholar
- Fiorini, P., and Shiller, Z. 1998. Motion planning in dynamic environments using velocity obstacles. Intl. J. on Robotics Research 17, 7, 760--772.Google ScholarCross Ref
- Funge, J., TU, X., and Terzopoulos, D. 1999. Cognitive modeling: Knowledge, reasoning and planning for intelligent characters. Proc. of ACM SIGGRAPH, 29--38. Google ScholarDigital Library
- Gayle, R., Moss, W., Lin, M. C., and Manocha, D. 2009. Multi-robot coordination using generalized social potential fields. Proc. IEEE Conf. Robotics and Automation. Google ScholarDigital Library
- Guy, S., Chhugani, J., Kim, C., Satish, N., Lin, M. C., Manocha, D., and Dubey, P. 2009. Clearpath: Highly parallel collision avoidance for multi-agent simulation. Proc. ACM SIGGRAPH/Eurographics Symposium on Computer Animation. Google ScholarDigital Library
- Harlow, F. H. 1963. The particle-in-cell method for numerical simulation of problems in fluid dynamics. In Proc. Symp. Appl. Math., vol. 15.Google Scholar
- Heigeas, L., Luciani, A., Thollot, J., and Castagné, N. 2003. A physically-based particle model of emergent crowd behaviors. Proc. Graphikon '03 2.Google Scholar
- Helbing, D., and Molnár, P. 1995. Social force model for pedestrian dynamics. Physical Review E 51 (May), 4282.Google ScholarCross Ref
- Helbing, D., Buzna, L., Johansson, A., and Werner, T. 2005. Self-organized pedestrian crowd dynamics: Experiments, simulations, and design solutions. Transportation Sci. 39, 1--24. Google ScholarDigital Library
- Hughes, R. L. 2003. The flow of human crowds. Annu. Rev. Fluid Mech. 35, 169--182.Google ScholarCross Ref
- Kamphuis, A., and Overmars, M. 2004. Finding paths for coherent groups using clearance. Proc. of ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 19--28. Google ScholarDigital Library
- Kerr, W., and Spears, D. 2005. Robotic simulation of gases for a surveillance task. Proc. IEEE/RSJ Int. Conf. Intelligent Robots and Systems (Aug.), 2905--2910.Google Scholar
- Lakoba, T. I., Kaup, D. J., and Finkelstein, N. M. 2005. Modifications of the Helbing-Molnar-Farkas-Vicsek social force model for pedestrian evolution. SIMULATION 81, 339. Google ScholarDigital Library
- Lamarche, F., and Donikian, S. 2004. Crowd of virtual humans: a new approach for real-time navigation in complex and structured environments. Computer Graphics Forum 23, 3, 509--518.Google ScholarCross Ref
- Lin, M. C., Guy, S., Narain, R., Sewall, J., Patil, S., Chhugani, J., Golas, A., den Berg, J. V., Curtis, S., Wilkie, D., Merrell, P., Kim, C., Satish, N., Dubey, P., and Manocha, D. 2009. Interactive modeling, simulation and control of large-scale crowds and traffic. Proc. Workshop on Motion in Games (Springer-Verlag Lecture Notes in Computer Science Series). Google ScholarDigital Library
- Loscos, C., Marchal, D., and Meyer, A. 2003. Intuitive crowd behaviour in dense urban environments using local laws. In Theory and Practice of Computer Graphics, 122--129. Google ScholarDigital Library
- McAdams, A., Selle, A., Ward, K., Sifakis, E., and Teran, J. 2009. Detail preserving continuum simulation of straight hair. ACM Trans. Graph. 28, 3, 62. Google ScholarDigital Library
- Metoyer, R. A., and Hodgins, J. K. 2003. Reactive pedestrian path following from examples. In Proc. 16th Int. Conf. Computer Animation and Social Agents, 149. Google ScholarDigital Library
- Musse, S. R., and Thalmann, D. 1997. A model of human crowd behavior: Group inter-relationship and collision detection analysis. Computer Animation and Simulation, 39--51.Google Scholar
- Paris, S., Pettre, J., and Donikian, S. 2007. Pedestrian reactive navigation for crowd simulation: a predictive approach. Computer Graphics Forum 26, 3 (September), 665--674.Google ScholarCross Ref
- Pelechano, N., O'Brien, K., Silverman, B., and Badler, N. 2005. Crowd simulation incorporating agent psychological models, roles and communication. First Intl. Workshop on Crowd Simulation.Google Scholar
- Pelechano, N., Allbeck, J. M., and Badler, N. I. 2008. Virtual Crowds: Methods, Simulation and Control. Morgan and Claypool Publishers.Google ScholarDigital Library
- Pettré, J., Laumond, J.-P., and Thalmann, D. 2005. A navigation graph for real-time crowd animation on multilayered and uneven terrain. First Intl. Workshop on Crowd Simulation, 81--90.Google Scholar
- Pettré, J., Kallmann, M., and Lin, M. C. 2008. Motion planning and autonomy for virtual humans. In ACM SIGGRAPH 2008 classes, 1--31. Google ScholarDigital Library
- Pimenta, K., Michael, N., Mesquita, R., Pereira, G., and Kumar, V. 2008. Control of swarms based on hydrodynamic models. Proc. IEEE Int. Conf. Robotics and Automation (May), 1948--1953.Google Scholar
- Reynolds, C. W. 1987. Flocks, herds and schools: A distributed behavioral model. ACM SIGGRAPH 21, 25--34. Google ScholarDigital Library
- Reynolds, C. W. 1999. Steering behaviors for autonomous characters. Game Developers Conference 1999.Google Scholar
- Schreckenberg, M., and Sharma, S. D. 2001. Pedestrian and Evacuation Dynamics. Springer.Google Scholar
- Shao, W., and Terzopoulos, D. 2007. Autonomous pedestrians. Graph. Models 69, 5--6, 246--274. Google ScholarDigital Library
- Shimizu, M., Ishiguro, A., Kawakatsu, T., Masubuchi, Y., and Doi, M. 2003. Coherent swarming from local interaction by exploiting molecular dynamics and Stokesian dynamics methods. Proc. IEEE/RSJ Int. Conf. Intelligent Robots and Systems 2 (Oct.), 1614--1619 vol. 2.Google Scholar
- Sifakis, E., Shinar, T., Irving, G., and Fedkiw, R. 2008. Globally coupled impulse-based collision handling for cloth simulation. In ACM SIGGRAPH/Eurographics Symposium on Computer Animation. Google ScholarDigital Library
- Sud, A., Gayle, R., Andersen, E., Guy, S., Lin, M., and Manocha, D. 2007. Real-time navigation of independent agents using adaptive roadmaps. In Proc. ACM Symp. Virtual Reality Software and Technology, 99--106. Google ScholarDigital Library
- Sud, A., Andersen, E., Curtis, S., Lin, M., and Manocha, D. 2008. Real-time path planning in dynamic virtual environments using multi-agent navigation graphs. IEEE Trans. Visualization and Computer Graphics 14, 3, 526--538. Google ScholarDigital Library
- Sugiyama, Y., Nakayama, A., and Hasebe, K. 2001. 2-dimensional optimal velocity models for granular flows. In Pedestrian and Evacuation Dynamics, 155--160.Google Scholar
- Sung, M., Gleicher, M., and Chenney, S. 2004. Scalable behaviors for crowd simulation. Computer Graphics Forum 23, 3 (Sept), 519--528.Google ScholarCross Ref
- Thalmann, D., O'Sullivan, C., Ciechomski, P., and Dobbyn, S. 2006. Populating Virtual Environments with Crowds. Eurographics 2006 Tutorial Notes.Google Scholar
- Treuille, A., Cooper, S., and Popovic, Z. 2006. Continuum crowds. ACM Trans. Graph. 25, 3, 1160--1168. Google ScholarDigital Library
- van den Berg, J., Lin, M. C., and Manocha, D. 2008. Reciprocal velocity obstacles for real-time multi-agent navigation. Proc. IEEE Conf. Robotics and Automation, 1928--1935.Google Scholar
- van den Berg, J., Patil, S., Seawall, J., Manocha, D., and Lin, M. C. 2008. Interactive navigation of individual agents in crowded environments. Proc. ACM Symposium on Interactive 3D Graphics and Games, 139--147. Google ScholarDigital Library
- van den Berg, J., Guy, S. J., Lin, M. C., and Manocha, D. 2009. Reciprocal n-body collision avoidance. Proc. Intl. Symposium on Robotics Research.Google Scholar
- Yeh, H., Curtis, S., Patil, S., van den Berg, J., Manocha, D., and Lin, M. C. 2008. Composite agents. Proc. ACM SIGGRAPH/Eurographics Symposium on Computer Animation. Google ScholarDigital Library
- Zhu, Y., and Bridson, R. 2005. Animating sand as a fluid. In Proc. ACM SIGGRAPH, 965--972. Google ScholarDigital Library
Index Terms
- Aggregate dynamics for dense crowd simulation
Recommendations
Aggregate dynamics for dense crowd simulation
Large dense crowds show aggregate behavior with reduced individual freedom of movement. We present a novel, scalable approach for simulating such crowds, using a dual representation both as discrete agents and as a single continuous system. In the ...
Divergence-Free SPH Fluid Simulation Using Density Constraint Condition
In this paper, a novel, incompressible fluid simulation framework based on the divergence-free Smoothed Particle Hydrodynamics model is presented. The novel SPH model combines a system of non-linear density constraint conditions and the divergence-free ...
The hierarchical behavior model for crowd simulation
VRCAI '09: Proceedings of the 8th International Conference on Virtual Reality Continuum and its Applications in IndustryWe present a hierarchical behavior model to simulate realistic crowd behaviors. This model is composed of two parts. One is the low density behavior module, emphasizing the autonomy and diversity of the behaviors. The other is high density behavior ...
Comments