> For the complete documentation index, see [llms.txt](https://isubasinghe.gitbook.io/isithas-wiki/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://isubasinghe.gitbook.io/isithas-wiki/computer_science/data_structures/octree.md).

# Octree

## Basic idea

An octree recursively partitions three-dimensional space into eight octants. Points or objects are stored in leaves, while internal nodes summarize a spatial region. Octrees support spatial search, collision detection, ray tracing, adaptive meshes, and hierarchical N-body algorithms such as Barnes–Hut.

## Key formulas

* Each internal node has at most $2^3=8$ children; the two-dimensional analogue is a quadtree.
* Child index around centre $(c\_x,c\_y,c\_z)$: $\[x\geq c\_x]+2\[y\geq c\_y]+4\[z\geq c\_z]$.
* A balanced tree has height $O(\log n)$; an unbalanced tree can have height $O(n)$.
* For weighted points, store total mass $M=\sum\_i m\_i$ and centre of mass $\mathbf{c}=M^{-1}\sum\_i m\_i\mathbf{x}\_i$ at each node.
* Fixed maximum depth bounds memory and traversal cost but controls spatial resolution.

## Resources

<https://en.wikipedia.org/wiki/Octree>