Overview
An Octree organizes points, volumes, or objects in a hierarchy of 3D boxes, refining crowded or detailed areas.
CoreSource checked
Octree
Indexes 3D space by recursively subdividing regions into eight octants.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Data Structures
- Difficulty
- Intermediate
- Family
- Spatial Index
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 0
- Relationships
- 1
- Code example
- Ready
- Visualization
- Ready
Core Concepts
3D subdivisionoctantspatial querytree hierarchy
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(log n)
Average
O(log n) average query
Worst
O(n)
Space
O(n)
When to Use
- Use when 3D objects or points need spatial culling or neighborhood queries.
- Use when 3D collision detection is a central requirement.
When Not to Use
- Avoid when the data is mostly flat enough for a 2D index.
- Avoid when a simpler array, map, or list already meets the access pattern.
What It Does
- Partitions 3D space
- Stores objects by octant
- Accelerates spatial queries
Use Cases
- 3D collision detection
- Voxel worlds
- Point cloud indexing
Inputs
- 3D points or objects
- Bounding volume
- Capacity threshold
Outputs
- Hierarchical 3D spatial index
Pseudocode
- 1.Create a root 3D bounds
- 2.Insert objects into child octants when possible
- 3.Split crowded nodes into eight children
- 4.Query overlapping octants recursively
Canonical Example
- Input
- point cloud in a cube
- Output
- dense octant subdivides
- Explanation
- Queries visit only boxes that overlap the requested 3D region.
Implementation Notes
- Use broad bounds and maximum depth to avoid infinite subdivision from identical points.
- Keep update operations small and test invariants after insertions and deletions.
- Keep a tiny example with known output beside the implementation.
- Test updates and queries as sequences, not only one operation at a time.
Common Pitfalls
- Rebuilding too often for moving objects can dominate runtime.
- The advertised performance depends on maintaining the structure's invariants.
- Not defining boundary, empty, or degenerate inputs before implementation.
- Incorrect updates can leave stale pointers, counts, balance metadata, or cached summaries.
Interactive Mechanism Walkthrough
Graph Frontier & Edge RelaxationShow a cube subdividing into eight smaller cubes around dense 3D points.
Step 1 of 4: Create a root 3D bounds
data-structureNotes
Loose octrees are often used for moving objects that cross cell boundaries.
Sources (1)
What each reference supports for this entry.
Handbook of Data Structures and Applications
BookData-structures reference for octrees, three-dimensional recursive subdivision, and spatial lookup.
Explore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageGeneralizesQuadtree
Octrees generalize quadtree-style recursive spatial subdivision from two dimensions to three.
Related Algorithms
Tags
Data StructureTreeSpatial IndexSpatial Data Structure