Octree
- Also called: sparse voxel octree
- Category: Sensing › 3D maps & reconstruction
- Tags: mapping, data-structures, 3d-perception, occupancy-mapping, point-clouds
A tree data structure that recursively splits 3D space into eight cubes, allocating fine cells only where there is data, for compact maps and fast spatial queries.
Definition
An octree is a tree in which every node represents a cube of space and can have up to eight children, one for each octant obtained by halving the cube along all three axes. The root covers the whole volume; each level down halves the cell size. Branches are only subdivided where something of interest is present, such as measured surface points, so large empty or unobserved regions stay as single coarse nodes. Octrees were described for solid modelling by Donald Meagher in the early 1980s and are now standard in graphics, point cloud processing and robot mapping.
The main appeal is memory. A dense voxel grid at fine resolution over a large building needs storage for every cell, while an octree's storage grows roughly with the observed surface area. It also gives multi-resolution access: a planner can query coarse cells for a quick check and descend for detail. In OctoMap, a widely used library by Hornung and colleagues, each leaf holds a probabilistic occupancy value in log-odds form, updated from range measurements, so the map distinguishes occupied, free and unknown space. Children with the same state are pruned back into their parent to save memory.
Octrees trade some speed for this compactness: reaching a leaf means walking down the tree, which is slower than indexing a flat array. Alternatives such as voxel hashing and the VDB structure offer faster access in some workloads. Octrees are also used to accelerate nearest-neighbour search and collision checking on point clouds, and in recent neural mapping systems they organise sparse voxels that store learned features, growing incrementally as new depth frames arrive.
Why it matters
Robots need 3D maps that cover large areas at useful resolution without exhausting memory. Octrees make this practical, and they are the basis of common occupancy mapping and collision-checking tools used in manipulation and aerial navigation.
Key applications
- Probabilistic 3D occupancy mapping with OctoMap
- Collision checking for manipulators and drones
- Nearest-neighbour and radius search on point clouds
- Sparse voxel structures for neural implicit and dense mapping
- Point cloud compression and level-of-detail rendering
In practice
A team building a 3D map for a drone flying through a warehouse feeds depth camera or lidar point clouds, with poses from their odometry, into OctoMap at a few centimetres' resolution. Each ray marks the cells it passes through as more likely free and the cell at its end as more likely occupied. The planner queries the octree for occupancy along candidate paths, treating unknown space as an obstacle. On a manipulator, MoveIt can take the same kind of octree from a depth sensor to keep the arm's planning scene up to date. Engineers tune resolution, sensor range and the hit and miss probabilities to balance detail, memory and how quickly moving objects are cleared.
Common misconceptions
- An octree is the same as a voxel grid — a voxel grid stores every cell, while an octree subdivides only where needed and merges uniform regions
- Octrees are always faster than flat grids — they save memory, but each lookup walks the tree, so dense or hashed grids can be quicker for some queries
- Empty space in an octree means free space — in occupancy octrees, unobserved space is unknown, which planners should usually treat differently from free
Who should know this
- Mapping and SLAM engineers
- Motion planning and collision-checking developers
- Drone autonomy engineers working in 3D environments
- Developers of neural and dense mapping systems
Related technologies
- OctoMap
- Voxel Hashing
- OpenVDB
- Point Cloud Library (PCL)
- MoveIt
Related terms
Related projects
- LingBot-Map: Streaming 3D reconstruction from one camera: pose and depth for every frame, live
- Cartographer: Google's real-time 2D and 3D SLAM system for multi-platform robotics
- OpenDroneMap: Open-source photogrammetry toolkit that turns drone images into maps and 3D models
- RTAB-Map: Versatile graph-based SLAM supporting RGB-D, stereo, and LiDAR with real-time operation
- LeGO-LOAM: Classic lightweight, ground-optimized lidar odometry and mapping baseline (IROS 2018)
- GLIM: GPU-accelerated 3D lidar SLAM framework for any range sensor, from AIST
Videos
- Using Octrees and A* for Efficient Pathfinding: git-amend