search

koide3 / ndt_omp

Multi-threaded and SSE friendly NDT algorithm
BSD 2-Clause "Simplified" License
743 stars 325 forks source link

difference between DIRECT7 、DIRECT1、and KDTREE #4

Closed chennuo0125-HIT closed 6 years ago

chennuo0125-HIT commented 6 years ago

thank you for your contribution, i don't know what is difference between DIRECT7 、DIRECT1 and KDTREE ？

koide3 commented 6 years ago

For each point in the input cloud, NDT searches the neighbor voxels to calculate the gradient of the matching score. The original NDT implementation in PCL used kdtree-based radius search to find the neighbor voxels. But, the radius search is expensive processing, and it affects the matching speed. DIRECT1 and DIRECT7 directly finds the neighbor voxels by indexing. As illustrated in the figure, DIRECT1 just returns the voxel which contains the point (voxel[x, y]), while DIRECT7 extracts the seven voxels next to the center voxel (voxel[x, y], voxel[x-1, y], voxel[x, y-1], ...).

untitled diagram

The matching result with KDTREE is identical to the original version in PCL, and it is slightly faster thanks to the SSE optimization. DIRECT1 is much faster, but a bit unstable since it refers narrow area compared to KDTREE. DIRECT7 is faster than KDTREE, and it extracts the same voxels as KDREE in most of cases.

chennuo0125-HIT commented 6 years ago

@koide3 thank you for your answer , i get it !

bob-ROS commented 4 years ago

Hey @koide3. I have used your package with great success for my thesis, very impressive implementation. Do you have any paper explaining these settings more in detail?

koide3 commented 4 years ago

Hi @bob-ROS , We've not published some papers about the detail of this implementation. If you need general explanation of the NDT algorithm, this thesis would be helpful.

This implementation was developed as a part of the following work, and I would be glad if you refer to it in case it is appropriate for your paper.