“A synthetic-vision based steering approach for crowd simulation” by Ondřej, Pettre, Olivier and Donikian

  • ©Jan Ondřej, Julien Pettre, Anne-Hélène Olivier, and Stéphane Donikian




    A synthetic-vision based steering approach for crowd simulation



    In the everyday exercise of controlling their locomotion, humans rely on their optic flow of the perceived environment to achieve collision-free navigation. In crowds, in spite of the complexity of the environment made of numerous obstacles, humans demonstrate remarkable capacities in avoiding collisions. Cognitive science work on human locomotion states that relatively succinct information is extracted from the optic flow to achieve safe locomotion. In this paper, we explore a novel vision-based approach of collision avoidance between walkers that fits the requirements of interactive crowd simulation. By simulating humans based on cognitive science results, we detect future collisions as well as the level of danger from visual stimuli. The motor-response is twofold: a reorientation strategy prevents future collision, whereas a deceleration strategy prevents imminent collisions. Several examples of our simulation results show that the emergence of self-organized patterns of walkers is reinforced using our approach. The emergent phenomena are visually appealing. More importantly, they improve the overall efficiency of the walkers’ traffic and avoid improbable locking situations.


    1. Chaumette, F., and Hutchinson, S. 2006. Visual servo control, part i: Basic approaches and part ii: Advanced approaches. IEEE Robotics and Automation Magazine 13(4), 82–90.Google ScholarCross Ref
    2. Chenney, S. 2004. Flow tiles. In Proc. 2004 ACM SIGGRAPH/Eurographics Symposium on Computer Animation (SCA ’04), Eurographics Association, Aire-la-Ville, Switzerland, Switzerland, 233–242. Google ScholarDigital Library
    3. Cutting, J. E., Vishton, P. M., and Braren, P. A. 1995. How we avoid collisions with stationary and moving objects. Psychological Review 102(4) (October), 627–651.Google ScholarCross Ref
    4. Gayle, R., Moss, W., Lin, M. C., and Manocha, D. 2009. Multi-robot coordination using generalized social potential fields. In Proc. IEEE International Conference on Robotics and Automation (ICRA ’09), 106–113. Google ScholarDigital Library
    5. Guy, S. J., Chhugani, J., Kim, C., Satish, N., Lin, M., Manocha, D., and Dubey, P. 2009. Clearpath: highly parallel collision avoidance for multi-agent simulation. In Proc. 2009 ACM SIGGRAPH/Eurographics Symposium on Computer Animation (SCA ’09), ACM, New York, NY, USA, 177–187. Google ScholarDigital Library
    6. Halperin, C., Anjyo, K., Cioroba, M., Kanyuk, P., Regelous, S., Yoshida, T., and Salvati, M. 2009. Crowd animation: Tools, techniques, and production examples. In SIGGRAPH Asia ’09: ACM SIGGRAPH Asia 2009 Courses, ACM, New York, NY, USA, 1.Google Scholar
    7. Heigeas, L., Luciani, A., Thollot, J., and Castagné, N. 2003. A physically-based particle model of emergent crowd behaviors. In Graphicon 2003.Google Scholar
    8. Helbing, D., and Molnar, P. 1995. Social force model for pedestrian dynamics. Physical Review E 51, 4282.Google ScholarCross Ref
    9. Hughes, R. L. 2003. The flow of human crowds. Annual Review of Fluid Mechanics 35, 169–182.Google ScholarCross Ref
    10. Kapadia, M., Singh, S., Hewlett, W., and Faloutsos, P. 2009. Egocentric affordance fields in pedestrian steering. In Proc. 2009 Symposium on Interactive 3D graphics and games (I3D ’09), ACM, New York, NY, USA, 215–223. Google ScholarDigital Library
    11. Karamouzas, I., Heil, P., van Beek, P., and Overmars, M. H. 2009. A predictive collision avoidance model for pedestrian simulation. In Motion in Games, 41–52. Google ScholarDigital Library
    12. Kuffner, J. J., J., and Latombe, J. C. 1999. Fast synthetic vision, memory, and learning models for virtual humans. In Proc. Computer Animation, 118–127. Google ScholarDigital Library
    13. Lamarche, F., and Donikian, S. 2004. Crowds of virtual humans: a new approach for real time navigation in complex and structured environments. Eurographics’04: Computer Graphics Forum 23, 3 (September), 509–518.Google ScholarCross Ref
    14. Loscos, C., Marchal, D., and Meyer, A. 2003. Intuitive crowd behaviour in dense urban environments using local laws. Theory and Practice of Computer Graphics (TPCG’03). Google ScholarDigital Library
    15. Massive. http://www.massivesoftware.com.Google Scholar
    16. Narain, R., Golas, A., Curtis, S., and Lin, M. 2009. Aggregate dynamics for dense crowd simulation. In SIGGRAPH Asia ’09: ACM SIGGRAPH Asia 2009 papers. Google ScholarDigital Library
    17. Noser, H., Renault, O., Thalmann, D., and Thalmann, N. M. 1995. Navigation for digital actors based on synthetic vision, memory, and learning. Computers & Graphics 19, 1, 7–19. Computer Graphics Lab., Swiss Federal Inst. of Technol., Lausanne, Switzerland.Google Scholar
    18. Paris, S., Donikian, S., and Bonvalet, N. 2006. Environmental abstraction and path planning techniques for realistic crowd simulation. CASA 2006: Computer Animation and Virtual Worlds 17, 3–4, 335. Google ScholarDigital Library
    19. Paris, S., Pettré, J., and Donikian, S. 2007. Pedestrian reactive navigation for crowd simulation: a predictive approach. Eurographics’07: Computer Graphics Forum 26, (3), 665–674.Google ScholarCross Ref
    20. Pelechano, N., Allbeck, J. M., and Badler, N. I. 2007. Controlling individual agents in high-density crowd simulation. In SCA ’07: Proceedings of the 2007 ACM SIGGRAPH/Eurographics symposium on Computer animation, 99–108. Google ScholarDigital Library
    21. Pelechano, N., Allbeck, J., and Badler., N. I. 2008. Virtual Crowds: Methods, Simulation, and Control. Morgan & Claypool Publishers. (Series Editor: Brian Barsky). Google ScholarDigital Library
    22. Peters, C., and O’Sullivan, C. 2003. Bottom-up visual attention for virtual human animation. In International Conference on Computer Animation and Social Agents (CASA’03), 111–117. Google ScholarDigital Library
    23. Pettré, J., Ciechomski, P. d. H., Maïm, J., Yersin, B., Laumond, J.-P., and Thalmann, D. 2006. Real-time navigating crowds: scalable simulation and rendering. Computer Animation and Virtual Worlds 17, 3–4, 445–455. Google ScholarDigital Library
    24. Pettré, J., Ondřej, J., Olivier, A.-H., Cretual, A., and Donikian, S. 2009. Experiment-based modeling, simulation and validation of interactions between virtual walkers. In Proc. 2009 ACM SIGGRAPH/Eurographics Symposium on Computer Animation (SCA ’09), ACM, New York, NY, USA, 189–198. Google ScholarDigital Library
    25. Reynolds, C. W. 1987. Flocks, herds and schools: A distributed behavioral model. In SIGGRAPH ’87: Proceedings of the 14th annual conference on Computer graphics and interactive techniques, ACM, New York, NY, USA, 25–34. Google ScholarDigital Library
    26. Reynolds, C. W. 1999. Steering behaviors for autonomous characters. In Game Developers Conference 1999.Google Scholar
    27. Schadschneider, A. 2001. Cellular automaton approach to pedestrian dynamicstheory. In In Pedestrian and Evacuation Dynamics, 75–85.Google Scholar
    28. Shao, W., and Terzopoulos, D. 2005. Autonomous pedestrians. In Proc. 2005 ACM SIGGRAPH/Eurographics symposium on Computer animation (SCA ’05), ACM Press, New York, NY, USA, 19–28. Google ScholarDigital Library
    29. Silva, A. R. D., Lages, W. S., and Chaimowicz, L. 2009. Boids that see: Using self-occlusion for simulating large groups on gpus. Comput. Entertain. 7, 4, 1–20. Google ScholarDigital Library
    30. Sud, A., Andersen, E., Curtis, S., Lin, M., and Manocha, D. 2007. Real-time path planning for virtual agents in dynamic environments. Proc. IEEE VR 2007, 91–98.Google Scholar
    31. Thalmann, D., and Raupp Musse, S. 2007. Crowd Simulation. Springer, London. Google ScholarDigital Library
    32. Thalmann, D., Kermel, L., Opdyke, W., and Regelous, S. 2005. Crowd and group animation. In SIGGRAPH ’05: ACM SIGGRAPH 2005 Courses, ACM, New York, NY, USA, 1. Google ScholarDigital Library
    33. Tresilian, J. R. 1994. Perceptual and motor processes in interceptive timing. Human Movement Science 13, 335–373.Google ScholarCross Ref
    34. Treuille, A., Cooper, S., and Popović, Z. 2006. Continuum crowds. ACM Transactions on Graphics (SIGGRAPH 2006) 25, (3). Google ScholarDigital Library
    35. Tu, X., and Terzopoulos, D. 1994. Artificial fishes: physics, locomotion, perception, behavior. In SIGGRAPH ’94: Proceedings of the 21st annual conference on Computer graphics and interactive techniques, ACM, New York, NY, USA, 43–50. Google ScholarDigital Library
    36. van den Berg, J., Patil, S., Sewall, J., Manocha, D., and Lin, M. 2008. Interactive navigation of individual agents in crowded environments. Symposium on Interactive 3D Graphics and Games (I3D 2008). Google ScholarDigital Library
    37. Warren, W. H., and Fajen, B. R. 2004. Optic Flow and Beyond. Kluwer (Editors: L. M. Vaina, S. A. Beardsley, and S. Rushton), ch. From optic flow to laws of control, 307–337. Google ScholarDigital Library

ACM Digital Library Publication: