search

jlblancoc / nanoflann

nanoflann: a C++11 header-only library for Nearest Neighbor (NN) search with KD-trees
Other
2.22k stars 488 forks source link

Performance issues with RKNNResultSet #218

Closed kya8 closed 10 months ago

kya8 commented 10 months ago

First of all thank you again for adding RKNN support to nanoflann.

I've been playing with the new nanoflann::RKNNResultSet, and there seems to be a performance issue with it. Specifically, RKNNResultSet::addPoint() returns immediately if the point is out of maximumSearchDistanceSquared, leaving the dists and indices lists (and therefore the return value of worstDist()) unchanged.

Does this make branch culling inefficient, especially for small maximumSearchDistanceSquared and large capacity? If I'm not mistaken, the tree could loop over most of the points without updating the RKNNResultSet when maximumSearchDistanceSquared is small, until it finally hits some points within that radius. Only after dists is full, the return value of worstDist() will allow for branch culling. However it takes really long for dists to become full, since before that it's essentially a brute-force radius search. This is even slower than regular KNN search.

I was experimenting with R=0.2, K=16 for computing normals on a real-world point cloud with approx. 4 million points, using multiple threads. The computation (not including tree construction) took 218 seconds with the new nanoflann::RKNNResultSet. With my custom RKNN ResultSet implemented as described in https://github.com/jlblancoc/nanoflann/issues/216 (i.e. setting dists[capacity - 1] to the max radius), it took 0.55 seconds. The final results were identical.

jlblancoc commented 10 months ago

Oh, it makes sense... thanks for checking it. I formerly tried by adding a new method to the result sets to return whether it should accept more points or not but finally discarded that solution and went to the published one which seemed simpler, but without a proper benchmarking to detect what you found.

If you could open a pull request with the change I would be more than glad to merge it. Please, feel free of also updating the CHANGELOG.md including the fix, and your name (unless you need privacy for work reason or whatever!).

jlblancoc commented 10 months ago

My tests (with smaller point clouds) show an improvement far from your dramatic results, but an improvement indeed. So I'll make a new release with your contribution in case your case is applicable to others. Thanks again!