octree

octree

Imagine, someday, you lose your wallet.
You remember having it until you came back home by driving.
You will therefore search for your wallet around your car, you won't search the whole universe to find your wallet, logic no ?
That's the principle of an Octree data structure.

Installation

go get -u github.com/louis030195/octree

Usage

package main

import (
    octree "github.com/louis030195/octree/pkg"
    "github.com/louis030195/protometry/api/volume"
    "log"
)

func main() {
	o := octree.NewOctree(volume.NewBoxMinMax(1, 1, 1, 4, 4, 4))
	myObj := octree.NewObjectCube(0, 2, 2, 3, 0.5)
	ok := o.Insert(*myObj)
	log.Printf("%v", ok) // true
	colliders := o.GetColliding(*volume.NewBoxMinMax(0, 0, 0, 0.9, 2.9, 0.9))
	log.Printf("%v", colliders)              // some objects
	log.Printf("%v", o.Move(myObj, 2, 2, 3)) // Success
	log.Printf("%v", o.Move(myObj, 2, 2, 8)) // Failure: outside tree !
}

Benchmark

make bench

Roadmap

• More test coverage
• Better benchmarks
• Possible optimisations
  • Linear implementation
  • Looseness
  • Less copies, unnecessary operations
  • Parallelization of a few steps

References

• Github storpipfugl/pykdtree: Fast kd-tree implementation in Python
• Github Rust rust-octree
• Github JS sparse-octree
• Github Distributed adaptive octree construction, 2:1 balancing & partitioning based on space filling curves
• Github UnityOctree
• Book: Real-Time Collision Detection - Christer Ericson
• AN OVERVIEW OF QUADTREES, OCTREES, AND RELATED HIERARCHICAL DATA STRUCTURES
• Efficient Sparse Voxel Octrees
• An Efficient Parametric Algorithm for Octree Traversal
• O-CNN: Octree-based Convolutional Neural Networks for 3D ShapeAnalysis
• Behley, J.; Steinhage, V.; Cremers, A. B. Efficient Radius Neighbor Search in Three-Dimensional Point Clouds. In 2015 IEEE International Conference on Robotics and Automation (ICRA); 2015; pp 3625–3630.
• scipy.spatial.cKDTree — SciPy Reference Guide
• Milinda Fernando, David Neilsen, Hyun Lim, Eric Hirschmann, Hari Sundar, ”Massively Parallel Simulations of Binary Black Hole Intermediate-Mass-Ratio Inspirals” SIAM Journal on Scientific Computing 2019. Paper
• Milinda Fernando, David Neilsen, Hari Sundar, ”A scalable framework for Adaptive Computational General Relativity on Heterogeneous Clusters”, (ACM International Conference on Supercomputing, ICS’19)
• Milinda Fernando, Dmitry Duplyakin, and Hari Sundar. 2017. ”Machine and Application Aware Partitioning for Adaptive Mesh Refinement Applications”. In Proceedings of the 26th International Symposium on High-Performance Parallel and Distributed Computing (HPDC ’17). ACM, New York, NY, USA, 231-242. Paper