Neighborhood grid: A novel data structure for fluids animation with GPU computing

This paper introduces a novel and efficient data structure, called neighborhood grid, capable of supporting large number of particle based elements on GPUs (graphics processing units), and is used for optimizing fluid animation with the use or GPU computing. The presented fluid simulation approach is based on SPH (smoothed particle hydrodynamics) and uses a unique algorithm for the neighborhood gathering. The brute force approach to neighborhood gathering of n particles has complexity O(n(2)), since it involves proximity queries of all pairs of fluid particles in order to compute the relevant mutual interactions. Usually, the algorithm is optimized by using spatial data structures which subdivide the environment in cells and then classify the particles among the cells based on their position, which is not efficient when a large number of particles are grouped in the same cell. Instead of using such approach, this work presents a novel and efficient data structure that maintains the particles into another form of proximity data structure, called neighborhood grid. In this structure, each cell contains only one particle and does not directly represent a discrete spatial subdivision. The neighborhood grid does process an approximate spatial neighborhood of the particles, yielding promising results for real time fluid animation, with results that goes up to 9 times speedup, when compared to traditional GPU approaches, and up to 100 times when compared against CPU implementations. (C) 2014 Elsevier Inc. All rights reserved.