Abstract:
Recent crowd simulation algorithms do path planning on complex surfaces by breaking 3D surfaces into a series of 2.5D planes. This allows for path planning on surfaces th...Show MoreMetadata
Abstract:
Recent crowd simulation algorithms do path planning on complex surfaces by breaking 3D surfaces into a series of 2.5D planes. This allows for path planning on surfaces that can be mapped from 3D to 2D without distortion, such as multistory buildings. However, the 2.5D approach does not handle path planning on curved surfaces such as spheres, asteroids, or insect colonies. Additionally, the 2.5D approach does not handle the complexity of dynamic obstacle avoidance when agents can walk on walls or ceilings. We propose novel path planning and obstacle avoidance algorithms that work on surfaces as a whole instead of breaking them into a 2.5D series of planes. Our "whole surfaceâ approach simulates crowds on both multistory structures and highly curved topologies without changing parameters. We validate our work on a suite of 30 different meshes, some with over 100,000 triangles, with crowds of 1,000 agents. Our algorithm always averaged more than 40 FPS with virtually no stalling.
Published in: IEEE Transactions on Visualization and Computer Graphics ( Volume: 20, Issue: 2, February 2014)
References is not available for this document.
Select All
1.
F. Lamarche and S. Donikian, "Crowd of Virtual Humans: A New Approach for Real Time Navigation in Complex and Structured Environments", Computer Graphics Forum, vol. 23, no. 3, pp. 509-518, 2004.
2.
S. Singh, M. Kapadia, B. Hewlett, G. Reinman and P. Faloutsos, "A Modular Framework for Adaptive Agent-Based Steering", Proc. Symp. Interactive 3D Graphics and Games, 2011.
3.
J. Sethian, "Fast Marching Methods", SIAM Rev., vol. 41, pp. 199-235, 1999.
4.
R. Geraerts and M. Overmars, "The Corridor Map Method: A General Framework for Real-Time High-Quality Path Planning", Computer Animation and Virtual Worlds, vol. 18, no. 2, pp. 107-119, 2007.
5.
M. Kallmann, "Navigation Queries from Triangular Meshes", Proc. Third Int'l Conf. Motion in Games, pp. 230-241, 2010.
6.
A. Kamphuis, M. Mooijekind, D. Nieuwenhuisen and M. Overmars, "Automatic Construction of Roadmaps for Path Planning in Games", Proc. Int'l Conf. Computer Games: Artificial Intelligence Design and Education, pp. 285-292, 2004.
7.
J. Pettré, P. Ciechomski, J. Maïm, B. Yersin, J. Laumond and D. Thalmann, "Real-Time Navigating Crowds: Scalable Simulation and Rendering", Proc. Computer Animation and Virtual Worlds, vol. 17, no. 3/4, pp. 445-455, 2006.
8.
D. Hale, "A Growth-Based Approach to the Automatic Generation of Navigation Meshes” dissertation", The Univ. of North Carolina Charlotte, 2012.
9.
S. Curtis, J. Snape and D. Manocha, "Way Portals: Efficient Multi-Agent Navigation with Line-Segment Goals", Proc. ACM SIGGRAPH Symp. Interactive 3D Graphics and Games, pp. 15-22, 2012.
10.
J. Mitchell, D. Mount and C. Papadimitriou, "The Discrete Geodesic Problem", SIAM J. Computing, vol. 16, no. 4, pp. 647-668, 1987.
11.
J. Chen and Y. Han, "Shortest Paths on a Polyhedron", Proc. Sixth Ann. Symp. Computational Geometry, pp. 360-369, 1990.
12.
D. Martínez, L. Velho and P. Carvalho, "Computing Geodesics on Triangular Meshes", Computers and Graphics, vol. 29, no. 5, pp. 667-675, 2005.
13.
R. Kimmel and J. Sethian, "Computing Geodesic Paths on Manifolds", Proc. Nat'l Academy of Sciences of the United States of Am., vol. 95, no. 15, pp. 8431, 1998.
14.
C. Reynolds, "Flocks Herds and Schools: A Distributed Behavioral Model", Proc. ACM SIGGRAPH Computer Graphics, vol. 21, no. 4, pp. 25-34, 1987.
15.
D. Helbing and P. Molnar, "Social Force Model for Pedestrian Dynamics", Physical Rev., vol. 51, no. 5, pp. 4282-4286, 1995.
16.
P. Fiorini and Z. Shiller, "Motion Planning in Dynamic Environments Using Velocity Obstacles", The Int'l J. Robotics Research, vol. 17, no. 7, pp. 760, 1998.
17.
J. Van den Berg, M. Lin and D. Manocha, "Reciprocal Velocity Obstacles for Real-Time Multi-Agent Navigation", Proc. Robotics and Automation Conf., pp. 1928-1935, 2008.
18.
S. Guy, J. Chhugani, S. Curtis, P. Dubey, M. Lin and D. Manocha, "Pledestrians: A Least-Effort Approach to Crowd Simulation", Proc. ACM SIGGRAPH/Eurographics Symp. Computer Animation, pp. 119-128, 2010.
19.
N. Courty and S. Musse, "Fastcrowd: Real-Time Simulation and Interaction with Large Crowds Based on Graphics Hardware", Proc. ACM SIGGRAPH/EuroGraphics Symp. Computer Animation, pp. 177-187, 2004.
20.
R. Narain, A. Golas, S. Curtis and M. Lin, "Aggregate Dynamics for Dense Crowd Simulation", ACM Trans. Graphics, vol. 28, no. 5, pp. 122, 2009.
21.
I. Karamouzas, P. Heil, P. van Beek and M. Overmars, "A Predictive Collision Avoidance Model for Pedestrian Simulation", Proc. Second Int'l Workshop Motion in Games, pp. 41-52, 2009.
22.
S. Singh, M. Kapadia, G. Reinman and P. Faloutsos, "Footstep Navigation for Dynamic Crowds", Computer Animation and Virtual Worlds, vol. 22, no. 2/3, pp. 151-158, 2011.
23.
N. Pelechano, J. Allbeck and N. Badler, "Controlling Individual Agents in High-Density Crowd Simulation", Proc. ACM SIGGRAPH/Eurographics Symp. Computer Animation, pp. 99-108, 2007.
24.
A. Treuille, S. Cooper and Z. Popović, "Continuum Crowds", ACM Trans. Graphics, vol. 25, no. 3, pp. 1160-1168, 2006.
25.
H. Jiang, W. Xu, T. Mao, C. Li, S. Xia and Z. Wang, "Continuum Crowd Simulation in Complex Environments", Computers and Graphics, vol. 34, no. 5, pp. 537-544, 2010.
26.
M. Kapadia, M. Wang, S. Singh, G. Reinman and P. Faloutsos, "Scenario Space: Characterizing Coverage Quality and Failure of Steering Algorithms", Proc. ACM SIGGRAPH/Eurographics Symp. Computer Animation, pp. 53-62, 2011.
27.
M. Kapadia, M. Wang, G. Reinman and P. Faloutsos, "Improved Benchmarking for Steering Algorithms", Proc. Fourth Int'l Conf. Motion in Games, pp. 266-277, 2011.
28.
N. Pelechano, C. Stocker, J. Allbeck and N. Badler, "Being a Part of the Crowd: Towards Validating VR Crowds Using Presence", Proc. Seventh Int'l Joint Conf. Autonomous Agents and Multiagent Systems, pp. 136-142, 2008.
29.
S. Singh, M. Kapadia, P. Faloutsos and G. Reinman, "SteerBench: A Benchmark Suite for Evaluating Steering Behaviors", Computer Animation and Virtual Worlds, vol. 20, no. 5/6, pp. 533-548, 2009.
30.
S. Singh, M. Naik, M. Kapadia, P. Faloutsos and G. Reinman, "Watch Out! A Framework for Evaluating Steering Behaviors", Proc. Conf. Motion in Games, pp. 200-209, 2008.
