A Neighborhood Grid Data Structure for Massive 3D Crowd Simulation on GPU

Mark Joselli, Erick Baptista Passos, Marcelo Zamith, Esteban Walter Gonzalez Clua, Anselmo Montenegro, Bruno Feijo
MediaLab, UFF, Niteroi, Brazil
VIII Brazilian Symposium on Games and Digital Entertainment (SBGAMES), 2009


   title={A Neighborhood Grid Data Structure for Massive 3D Crowd Simulation on GPU},

   author={Joselli, M. and Passos, E.B. and Zamith, M. and Clua, E. and Montenegro, A. and Feij{‘o}, B.},

   booktitle={VIII Brazilian Symposium on Games and Digital Entertainment},





Download Download (PDF)   View View   Source Source   



Simulation and visualization of emergent crowd in real-time is a computationally intensive task. This intensity mostly comes from the O(n2) complexity of the traversal algorithm, necessary for the proximity queries of all pair of entities in order to compute the relevant mutual interactions. Previous works reduced this complexity by considerably factors, using adequate data structures for spatial subdivision and parallel computing on modern graphic hardware, achieving interactive frame rates in real-time simulations. However, the performance of existent proposals are heavily affected by the maximum density of the spatial subdivision cells, which is usually high, yet leading to algorithms that are not optimal. In this paper we extend previous neighborhood data structure, which is called neighborhood grid, and a simulation architecture that provides for extremely low parallel complexity. Also, we implement a representative flocking boids case-study from which we run benchmarks with simulation and rendering of up to 1 million boids at interactive frame-rates. We remark that this work can achieve a minimum speeup of 2.94 when compared to traditional spatial subdivision methods with a similar visual experience and with lesser use of memory.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: