Computer Graphics & Visual Computing (CGVC) 2019

Permanent URI for this collection

Now showing 1 - 1 of 1

Fast and Efficient Nearest Neighbor Search for Particle Simulations
(The Eurographics Association, 2019) Gross, Julian; Köster, Marcel; Krüger, Antonio; Vidal, Franck P. and Tam, Gary K. L. and Roberts, Jonathan C.
One of the fundamental algorithms in particle simulations is the identification and iteration over nearest neighbors of every particle. Well-known examples are SPH or PBD simulations that compute forces and particle-position updates in every simulation step. In order to find nearest neighbors for all particles, hash-based, grid-based or tree-based approaches have been developed in the past. The two most prominent and fastest algorithms use virtual and explicitly allocated uniform grids to achieve high performance on Graphics Processing Units (GPUs). However, they have disadvantages with numerous particle simulation domains, either in terms of run time or memory consumption. We present a novel algorithm that can be applied to large simulation domains that significantly reduces memory consumption using a shared-memory based neighbor search. Furthermore, we achieve high-performance on our evaluation scenarios that often outperforms existing state-of-the-art methods.