PointCloudLibrary / pcl

Point Cloud Library (PCL)
https://pointclouds.org/
Other
9.64k stars 4.59k forks source link

Faster octree nearestKSearch #6037

Closed mvieth closed 1 month ago

mvieth commented 1 month ago

Inspired by the logic in organized.h: always keep point_candidates sorted, inserting new entries at the correct places. This avoids repeated calls to std::sort and having more than k entries in point_candidates.

Benchmarks: NormalEstimation (without OpenMP) with octree: NormalEstimation Old New
k=50, cloud=milk 2607 ms 1842 ms
k=50, cloud=mug 2043 ms 1505 ms
k=100, cloud=milk 5650 ms 3075 ms
k=100, cloud=mug 3824 ms 2436 ms
Calling nearestKSearch on every (valid) point of a cloud: Search Old New
k=1, cloud1 818 ms 509 ms
k=1, cloud2 791 ms 613 ms
k=1, cloud3 773 ms 744 ms
k=5, cloud1 914 ms 637 ms
k=5, cloud2 950 ms 780 ms
k=5, cloud3 1083 ms 1033 ms
larshg commented 1 month ago

Nice improvements!