[ICRA 2024] i-Octree: A Fast, Lightweight, and Dynamic Octree for Proximity Search
Abstract
Establishing the correspondences between newly acquired points and historically accumulated data (i.e., map) through nearest neighbors search is crucial in numerous robotic applications. However, static tree data structures are inadequate to handle large and dynamically growing maps in real-time.
To address this issue, we present the i-Octree, a dynamic octree data structure that supports both fast nearest neighbor search and real-time dynamic updates, such as point insertion, deletion, and on-tree down-sampling. The i-Octree is built upon a leaf-based octree and has two key features: a local spatially continuous storing strategy that allows for fast access to points while minimizing memory usage, and local on-tree updates that significantly reduce computation time compared to existing static or dynamic tree structures. The experiments show that i-Octree surpasses state-of-the-art methods by reducing run-time by over 50% on real-world open datasets.
An example of using i-Octree in odometry. The i-Octree and odometry collaborate to estimate the poses of the 3D data obtained from the range sensors.
i-Octree Design and Implementation
Illustration of locations of a octant's points in memory. (a) scattered locations; (b) continual locations.
Fig. (a) and (b) illustrate insertion of new points (red) out of the range to the i-Octree. In (a), the left yellow cube is the root octant as well as the leaf octant with points (black) in the beginning. After inserting, the root octant becomes the light purple cube. In (b), the purple node is the root octant and it is updated after inserting new octants (dashed black rectangle).
Illustration of box-wise delete. The blue box is the given box, and the numbers 0 to 7 (Morton codes) are the indices of the octants. Octants, with indices 0, 1, 4, and 5 are directly deleted. Octant 7 is also deleted due to having no points.
Randomized Data Experiments
Dynamic data structure comparison over different tree size.
The comparison of time consumption.
Real-world Data Experiments
The Comparison of time consumption on the street_02 sequence.
