Fast and Efficient Nearest Neighbor Search for Particle Simulations

Abstract

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.