C++ library for fast computation of neighbor lists in point clouds.
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. TreeNSearch is used in 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:
Paper: Fast Octree Neighborhood Search for SPH Simulations
Experiments video: Video
License: MIT
You can use CMake to build this project. Follow these steps to integrate the TreeNSearch library into another CMake project:
TreeNSearch
folder into the folder structure of your project. There is no need to include tests
nor the top level CMakeLists.txt
file.TreeNSearch/include
to the include directories.TreeNSearch
.Simplest example for TreeNSearch: one point set, all the points have the same search radius.
// Data types. (Unintiallized for illustration purposes)
float search_radius;
std::vector<std::array<float, 3>> points;
// TreeNSearch default set up
tns::TreeNSearch nsearch;
nsearch.set_search_radius(search_radius);
const int set_0 = nsearch.add_point_set(points[0].data(), points.size());
nsearch.set_active_search(set_0, set_0); // points in set_0 search for neighbors in set_0
// TreeNSearch execution
nsearch.run();
// Typical use: traverse the neighbors of point i
const tns::NeighborList neighborlist = nsearch.get_neighborlist(set_0, set_0, i);
for (int loc_j = 0; loc_j < neighborlist.size(); loc_j++) {
const int j = neighborlist[loc_j];
// ...
}
To execute the neighborhood search again after points have moved, simply use nsearch.run()
again and the next traversals will be updated.
If the number of points or the pointer to the point coordinate changes, use nsearch.resize_point_set(set_id, points_ptr, n_points)
.
Important: Points are not included in their own neighbor list.
It is also possible to work with more sets and arbitrary searches between them:
const int set_0 = nsearch.add_point_set(points_0[0].data(), points_0.size());
const int set_1 = nsearch.add_point_set(points_1[0].data(), points_1.size());
nsearch.set_active_search(set_0, set_0); // Points in set_0 search for neighbors in set_0
nsearch.set_active_search(set_0, set_1); // Points in set_0 search for neighbors in set_1
In the above example, points in set_1
do not search for neighbors in set_1
.
To work with variable per-point search radius, we can simply include a pointer search radii array in the point set declaration:
// Data types. (Unintiallized for illustration purposes)
float search_radius;
std::vector<std::array<float, 3>> points;
std::vector<float> radii;
// TreeNSearch default set up for variable search radii
tns::TreeNSearch nsearch;
const int set_0 = nsearch.add_point_set(points[0].data(), radii.data(), points.size());
nsearch.set_symmetric_search(); // Optional: i is in the neighbor list of j if j is neighbor of i
Warning: It is not possible to have sets with variable search radii and sets with fixed search radii at the same time. If a single point set has variable search radii, all sets must be declared as such.
In SPH simulations typically point data is kept approximately sorted to improve performance due to better cache utilization. An explicit sort is often done every few time steps. TreeNSearch can take advantage of its internal data structure to provide a very fast approximate sort. You can sort any data as follows:
// Data types. (Unintiallized for illustration purposes)
std::vector<std::array<float, 3>> points;
std::vector<double> density;
std::vector<uint32_t> indices;
// Sorting
nsearch.prepare_zsort();
nsearch.apply_zsort(set_id, points[0].data(), 3);
nsearch.apply_zsort(set_id, density.data(), 1);
nsearch.apply_zsort(set_id, indices.data(), 1);
TreeNSearch offers the possibility to traverse a neighbor list by using a templated callback function, replacing the following code
const tns::NeighborList neighborlist = nsearch.get_neighborlist(set_i, set_j, i);
for (int loc_j = 0; loc_j < neighborlist.size(); loc_j++) {
const int j = neighborlist[loc_j];
// ...
}
with this one
nsearch.for_each_neighbor(set_i, set_j, i,
[&](const int j) {
// ...
}
);
Both versions should have identical runtime performance assuming the compiler inlines the templated callback function.
Even though most applications will not suffer from these limitations, we are currently working on handling those extreme cases.
float
internally, which is faster than double
for the neighborhood search problem.
While faster, it has the downside that it will misclassify points as neighbors when they are at approximately search radius distance.
As consequence, there might be some points found as neighbors by TreeNSearch that would be not classified as neighbor in later processing if carried out in double
precision.
The misclasification tolerance is the machine precision value of float
, ~5.96e-08.