zhujun3753 / i-octree Goto Github PK

[ICRA2024] Implementation of A Fast, Lightweight, and Dynamic Octree for Proximity Search

Home Page: https://sites.google.com/view/I-Octree

License: GNU General Public License v2.0

CMake 1.06% C++ 89.53% Python 9.18% Shell 0.23%

i-octree's Introduction

i-Octree: A Fast, Lightweight, and Dynamic Octree for Proximity Search(Accepted by ICRA 2024)

i-Octree is 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.

Features

Dynamically insert points to the tree.
Delete points inside given axis-aligned bounding boxes.
Fast k-nearest neighbors search.
Fast radius neighbors search.
Fully templated for maximal flexibility to support arbitrary point representations & containers.

News 📰

[2024.03.16] - Feature Enhancement

Enhanced the implementation of the i-Octree with new functionalities and updated the Python bindings accordingly.

Python Bindings Test

1. Requirement

To compile, we require Eigen, C++17, and torch.

2. Run

git clone [email protected]:zhujun3753/i-octee.git

cd octree_map
# Update the `CMAKE_PREFIX_PATH` variable in `CMakeLists.txt` to reflect your own path settings.!!!!
bash build.sh

cd ..
python demo.py

3. Results

==============================
This is a debug print in OctreeMap C++!
==============================
num: 100
attr_n: 6
after filter num: 95
octree_feature.get_size(): 85
tensor([0.5879, 0.8644, 0.9247, 0.9912, 0.9457, 0.2752, 0.5103, 0.7180, 0.9304])
tensor([0.5879, 0.8644, 0.9247, 0.9912, 0.9457, 0.2752, 0.5103, 0.7180, 0.9304])

Run Randomized Data Experiments

1. Build

git clone [email protected]:zhujun3753/i-octee.git

# For Comparison
cd i-octree
git clone [email protected]:hku-mars/ikd-Tree.git

# Build & Run
bash run.sh

# Plot Results
python plot_time.py

2. Results

Attribution

If you use the implementation or ideas from the corresponding paper in your academic work, it would be nice if you cite the corresponding paper:

@misc{zhu2023ioctree,
      title={i-Octree: A Fast, Lightweight, and Dynamic Octree for Proximity Search}, 
      author={Jun Zhu and Hongyi Li and Shengjie Wang and Zhepeng Wang and Tao Zhang},
      year={2023},
      eprint={2309.08315},
      archivePrefix={arXiv},
      primaryClass={cs.RO}
}

Acknowledgement

Thanks to Jens Behley for open-sourcing his excellent work octree.

This project uses "ikd-Tree" by Cai, Yixi for comparison purposes. The code from "ikd-Tree" is licensed under the GPL-2.0. You can find the original project and its source code here.

License

The source code of i-Octree is released under GPLv2 license. For commercial use, please contact Mr. Jun ZHU ([email protected]) or Dr. Tao ZHANG ([email protected]).

i-octree's People

Contributors

Stargazers

Watchers

i-octree's Issues

Examples of the functions

Is there any example of your functions?
How to use the lib to implement the functions like,
Fast k-nearest neighbors search.
Fast radius neighbors search.

Slow than KDTree in scipy.spatial

I test a sample by the following code,

from scipy.spatial import KDTree
from octree_map import OctreeMap
import torch,time
pts = torch.randint(0,1000,size=(805285,3)).float()
qury_pts = torch.randint(0,1000,size=(10000,3)).float()
OctreeMap.add_pts_with_attr_cpu(pts)
t1 = time.time()
data2 = OctreeMap.nearest_search(pts, qury_pts)
print('ioctree',time.time()-t1)

tree_gloabl = KDTree(pts, compact_nodes=False)
t2 = time.time()
min_dis, min_nnIDx = tree_gloabl.query(qury_pts, 11, workers=-1)
print('scipy',time.time()-t2)

while fix the interface in octree_map.hpp

	torch::Tensor nearest_search(torch::Tensor pts_attr, torch::Tensor query_pts)
	{
		if(octree_feature.size()<1)
		{
			std::cout<<"Empty octree!\n";
			return torch::empty(0);;
		}
		int num = query_pts.size(0);
		auto pts_attr_acces = pts_attr.accessor<float,2>();
		auto query_pts_acces = query_pts.accessor<float,2>();
		if(pts_attr.size(1)<3)
		{
			std::cout<<"Must be 3D pts!\n";
			return torch::empty(0);;
		}
		int attr_n = octree_feature.get_attr_n();
		torch::Tensor data_tensor = torch::zeros({num, 11, attr_n}, torch::dtype(torch::kFloat32));
		auto data_tensor_acces = data_tensor.accessor<float,3>();
		for(int i=0; i<num; i++)
		{
			std::vector<float> query;
			for(int j=0; j<3; j++)
				query.push_back(query_pts_acces[i][j]);
			std::vector<std::vector<float>> resultIndices;
			std::vector<float> distances;
			octree_feature.knnNeighbors_eigen(query, 11, resultIndices, distances);
			if(distances.size()>0)
			{
				for(int n=0; n<11;n++){
					for(int j=0; j<attr_n; j++)
					{
						data_tensor_acces[i][n][j] = resultIndices[n][j];
					}
				}
			}
		}
		return data_tensor;
	}

Then I got,

num: 805285
attr_n: 0
after filter num: 804958
octree_feature.get_size(): 804958
ioctree 0.14931321144104004
scipy 0.017796754837036133

This means ioctree is much slower than scipy.KDTree, is that right?