high performance computing on graphics processing units: hgpu.org

Simulation and visualization of particles in real-time can be a computationally intensive task. This intensity comes from diverse factories, being one of them is the O(n^2) complexity of the traversal algorithm, necessary for the proximity queries of all pair of particles that decide the need to compute collisions. 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 apply a novel data structure, which is called neighborhood grid, and a simulation architecture that provides for extremely low parallel complexity. Also, we compared this work with the traditional spatial hashing achieving a speedup up to 9.5 with a similar visual experience and with lesser use of memory.