Efficient Implementation of Smoothed Particle Hydrodynamics (SPH) with Plane Sweep Algorithm (Communications in Computational Physics, 2018)
Neighbour search (NS) is the core of any implementations of smoothed particlehydrodynamics (SPH). In this paper, we present an efficient $\mathcal{O}$($N$log$N$) neighboursearch method based on the plane sweep (PW) algorithm with $N$ being the number ofSPH particles. The resulting method, dubbed the PWNS method, is totally independentof grids (i.e., purely meshfree) and capable of treating variable smoothing length,arbitrary particle distribution and heterogenous kernels. Several state-of-the-art datastructures and algorithms, e.g., the segment tree and the Morton code, are optimizedand implemented. By simply allowing multiple lines to sweep the SPH particles simultaneouslyfrom different initial positions, a parallelization of the PWNS method withsatisfactory speedup and load-balancing can be easily achieved. That is, the PWNSSPH solver has a great potential for large scale fluid dynamics simulations.