Home

Awesome

ikd-Tree

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.

What does ikd-Tree support?

User Manual

Developers

Related paper

If you are using any code of this repo in your research, please cite at least one of the articles as following:

@article{cai2021ikd,
  title={ikd-Tree: An Incremental KD Tree for Robotic Applications},
  author={Cai, Yixi and Xu, Wei and Zhang, Fu},
  journal={arXiv preprint arXiv:2102.10808},
  year={2021}
}
@article{xu2022fast,
  title={Fast-lio2: Fast direct lidar-inertial odometry},
  author={Xu, Wei and Cai, Yixi and He, Dongjiao and Lin, Jiarong and Zhang, Fu},
  journal={IEEE Transactions on Robotics},
  year={2022},
  publisher={IEEE}
}

Build & Run demo

1. How to build this project

cd ~/catkin_ws/src
git clone git@github.com:hku-mars/ikd-Tree.git
cd ikd-Tree/build
cmake ..
make -j 9

2. Run our examples

Note: 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_demo

Example 2: ikd_tree_Search_demo

Box Search ResultRadius Search Result

Points returned from the two search methods are shown in red.

Example 3: ikd_tree_Async_demo

Original Map:

<img src="materials/imgs/HKU_campus.png" style="zoom:50%;" />

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.

Acknowledgments

License

The source code of ikd-Tree is released under GPLv2 license. For commercial use, please contact Mr. Yixi CAI (yixicai@connect.hku.hk) or Dr. Fu ZHANG (fuzhang@hku.hk).