PointNeighbors.jl

PointNeighbors.jl is a package for neighborhood search with fixed search radius in 1D, 2D and 3D point clouds.

Features

Several implementations of neighborhood search with fixed search radius
Focus on fast incremental updates to be usable for particle-based simulations with frequent updates
Designed as a "playground" to easily switch between different implementations and data structures
Common API over all implementations
Extensive benchmark suite to study different implementations
GPU compatibility

Implementation	Description	Features	Query	Update	GPU-compatible
`GridNeighborhoodSearch` with `DictionaryCellList`	Grid-based NHS with Julia `Dict` backend	Infinite domain	Fast	Fast	❌
`GridNeighborhoodSearch` with `FullGridCellList`	Grid-based NHS allocating all cells of the domain	Finite domain, but efficient memory layout for densely filled domain.	Faster	Fastest	✅
`PrecomputedNeighborhoodSearch`	Precompute neighbor lists	Best for TLSPH without NHS updates. Not suitable for updates in every time step.	Fastest	Very slow	✅

Benchmarks by Implementation

The following benchmarks were conducted on an Intel Xeon W9-3475X using 36 threads.

Benchmark of a single force computation step of a Weakly Compressible SPH (WCSPH) simulation: WCSPH benchmark by implementation

Benchmark of different neighborhood search update strategies. The benchmark alternates between two perturbed point clouds. In 3D, only about 0.7% of the particles change cells between updates, which is similar to a dam break simulation. This is not relevant for ParallelUpdate, which reinitializes all particles in every update step. Benchmark by update strategy

Benchmarks by Machine

Benchmark of a single force computation step of a Weakly Compressible SPH (WCSPH) simulation with the GridNeighborhoodSearch and FullGridCellList implementation: WCSPH benchmark by machine

Benchmark of a single force computation step of a Total Lagrangian SPH (TLSPH) simulation with the PrecomputedNeighborhoodSearch implementation (TLSPH is looking for neighbors in the initial configuration, so the NHS does not need to be updated): TLSPH benchmark by machine

Deformation gradient performance for a TLSPH simulation with the PrecomputedNeighborhoodSearch implementation: TLSPH deformation gradient benchmark by machine

Packages using PointNeighbors.jl

If you're using PointNeighbors.jl in your package, please feel free to open a PR adding it to this list.

Cite Us

If you use PointNeighbors.jl in your own research or write a paper using results obtained with the help of PointNeighbors.jl, please cite it as

@misc{pointneighbors,
  title={{P}oint{N}eighbors.jl: {N}eighborhood search with fixed search radius in {J}ulia},
  author={Erik Faulhaber and Niklas Neher and Sven Berger and
          Michael Schlottke-Lakemper and Gregor Gassner},
  year={2024},
  howpublished={\url{https://github.com/trixi-framework/PointNeighbors.jl}},
  doi={10.5281/zenodo.12702157}
}