Fast and Efficient Nearest Neighbor Search for Particle Simulations
No Thumbnail Available
Date
2019
Journal Title
Journal ISSN
Volume Title
Publisher
The Eurographics Association
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.
Description
@inproceedings{10.2312:cgvc.20191258,
booktitle = {Computer Graphics and Visual Computing (CGVC)},
editor = {Vidal, Franck P. and Tam, Gary K. L. and Roberts, Jonathan C.},
title = {{Fast and Efficient Nearest Neighbor Search for Particle Simulations}},
author = {Gross, Julian and Köster, Marcel and Krüger, Antonio},
year = {2019},
publisher = {The Eurographics Association},
ISBN = {978-3-03868-096-3},
DOI = {10.2312/cgvc.20191258}
}