TreeNSearch
TreeNSearch is a C++ library for fast computation of neighbor lists in point clouds that implements the method described in our paper Fast Octree Neighborhood Search for SPH Simulations. TreeNSearch can be used for any type of point clouds, not just particle data from fluid simulations. What makes TreeNSearch faster than previous methods is that it employs an adaptive acceleration structure that can utilize the CPU more efficiently. Demonstrations using TreeNSearch are computed with the popular fluid simulation software SPlisHSPlasH.
All the internal stages of TreeNSearch are available in two versions, one using scalar instructions and another using AVX2 SIMD instructions. Both implementations are 100% interchangeable. This makes TreeNSearch a great learning material for SIMD implementation of complex data structures and algorithms.
Main features:
- Supports both fixed search radius and variable per-point search radius.
- Multiple point sets with arbitrary active/inactive searches between them.
- Very fast approximate reordering of arbitrary user data related to the points according to a space-filling Z curve to improve the cache efficiency.
Paper: Fast Octree Neighborhood Search for SPH Simulations
Experiments video: Video
License: MIT
