ikd-Tree is an incremental k-d tree designed for robotic applications. The ikd-Tree incrementally updates a k-d tree with new coming points only, leading to much lower computation time than existing static k-d trees. Besides point-wise operations, the ikd-Tree supports several features such as box-wise operations and down-sampling that are practically useful in robotic applications.
Yixi Cai 蔡逸熙: Data structure design and implementation
Wei Xu 徐威: Incorporation into LiDAR-inertial odometry package (FAST_LIO2 Released)
More details please refer to our paper and video~
Related paper available on arxiv:
ikd-Tree: An Incremental K-D Tree for robotic applications
Related video: https://youtu.be/ueOunk03zxA
- We upgraded our ikd-Tree to achieve a more stable and efficient performance. More details are shown as follows:
- Replace the queue and priority queue in STL with our code to avoid memory conflicts.
- Fix some bugs in re-building of the previous version, which may result in information loss during the multi-thread re-building process.
- Add a new parameter
max_distto support ranged search to achieve faster nearest search in robotic applications. - Fix minor bugs to improve the overall performance.
cd ~/catkin_ws/src
git clone [email protected]:hku-mars/ikd-Tree.git
cd ikd-Tree/build
cmake ..
make -j 9Note: To run Example 2 & 3, please download the PCD file (HKU_demo_pointcloud) into${Your own directory}/ikd-Tree/materials
cd ${Your own directory}/ikd-Tree/build
# Example 1. Check the speed of ikd-Tree
./ikd_tree_demo
# Example 2. Searching-points-by-box examples
./ikd_Tree_Search_demo
# Example 3. An aysnc. exmaple for readers' better understanding of the principle of ikd-Tree
./ikd_tree_async_demoExample 2: ikd_tree_Search_demo
| Box Search Result | Radius Search Result |
|---|---|
 |
 |
Points returned from the two search methods are shown in red.
Example 3: ikd_tree_Async_demo
Original Map:
Box Delete Results:
| Points removed from ikd-Tree(red) | Map after box delete |
|---|---|
 |
 |
This example is to demonstrate the asynchronous phenomenon in ikd-Tree. The points are deleted by attaching 'deleted' on the tree nodes (map shown in the ) instead of being removed from the ikd-Tree immediately. They are removed from the tree when rebuilding process is performed. Please refer to our paper for more details about delete and rebuilding.
Thanks Hyungtae Lim 임형태 for providing application examples on point clouds.