pcl icon indicating copy to clipboard operation
pcl copied to clipboard

CropHull::applyFilter3D speedup using AABB tree

Open yasamoka opened this issue 3 years ago • 0 comments

This pull request provides a tested AABB tree implementation using CGAL (Computational Geometry Algorithms Library).

This implementation is used to speed up CropHull::applyFilter3D which shoots rays into a scene and checks for intersections with the triangle mesh. On top of that, the function is also parallelized by setting the number of threads using CropHull::setNumberOfThreads.

A quick benchmark showing the difference in performance is provided below.

CPU: Intel Core i5 6300HQ RAM: 16GB DDR4-2133 (dual channel) Laptop: Dell XPS 15 9550

Mesh: David (Michelangelo) mesh (https://commons.wikimedia.org/wiki/File:David_(Michelangelo).stl) Input cloud size: 10,000 points (randomly generated) Number of threads: 4 (only applicable for new implementation)

The mesh is simplified using CGAL's surface mesh simplification. The numbers for the AABB tree implementation include tree construction time which is automatically performed the first time applyFilter3D is called (if tree construction is not called explicitly first).

Implementation # Triangles Time Speedup
Default 10,000 5779 ms
AABB tree + OMP 10,000 34.3 ms 168.48x
Default 100,000 58549 ms
AABB tree + OMP 100,000 160 ms 365.93x

For simpler geometry, the speedup is lower but should still be respectable.

I have added a new module (aabb_tree) to the documentation. Please let me know if there are any improvements I could add there.

I would also appreciate feedback regarding the modifications to the CMake scripts that were required to make this work.

Thank you very much!

yasamoka avatar Jun 18 '22 00:06 yasamoka