Octree
Divide a one-meter cube into millimeter voxels and you get about a billion cells. Put a coffee mug inside and its surface passes through roughly one in ten thousand of them. The rest is air, and a dense voxel grid pays for every one of those empty cells.
An octree describes space the way you would describe it out loud: coarsely where nothing happens, finely where something does. Split the cube into eight smaller cubes, split again only the ones that contain something, and stop wherever a region is uniform. The result stores a surface at millimeter detail in a small fraction of the memory, answers “what is at this point?” in a handful of steps, and lets a ray cross empty space in long strides. It sits under real-time NeRF renderers, robot occupancy maps, point-cloud libraries and point-cloud compression.
1. Recursive Subdivision
Start with an axis-aligned cube of side \(L\) that encloses everything you care about: the root. A node is either a leaf, or it has exactly eight children, the octants you get by halving the cube along \(x\), \(y\) and \(z\). A node at depth \(d\), counting the root as depth 0, has side
\[s_d = \frac{L}{2^d},\]
so a tree of depth \(D\) resolves detail down to \(L/2^D\). Ten levels take a 1 m cube to cells just under 1 mm.
Each child is named by three bits: \(b_x = 1\) if it lies in the upper half along \(x\), and likewise \(b_y\) and \(b_z\). Packing them into an octant index, and moving from the parent’s center \(\mathbf{c}\) and side \(s\) to the child’s center, gives
\[i = b_x + 2\,b_y + 4\,b_z \in \{0, \dots, 7\}, \qquad \mathbf{c}_{\text{child}} = \mathbf{c} + \frac{s}{4}\,\big(2b_x - 1,\; 2b_y - 1,\; 2b_z - 1\big).\]
To find which child holds a point \(\mathbf{p}\), compare it with the parent’s center: \(b_x = 1\) if \(p_x \ge c_x\), and the same for \(y\) and \(z\).
What makes a leaf a leaf depends on what the tree stores. A region octree stores space itself, such as occupancy or a signed distance, and stops splitting when a cell is uniform (entirely empty or entirely full) or reaches the maximum depth. An octree over points stores samples instead: each leaf holds a bucket of points and splits once the bucket is too full or the cell reaches a minimum size. The tree machinery is the same; only the stopping rule changes.
Figure 1 shows the 2D version, a quadtree with four children per node, refined only where a circle passes. Away from the curve the squares stay large, whether empty or full; along it they shrink to the finest level.
2. Why It Saves Memory
A dense grid of depth \(D\) has \(8^D\) cells, because every level splits every cell into eight. Let \(S_d\) be the number of depth-\(d\) cells that a surface passes through. A surface is two-dimensional, so \(S_d\) grows like its area \(A\) divided by the cell area \(s_d^2\):
\[S_d \approx 1.5\,\frac{A}{s_d^2} \;\propto\; 4^d.\]
The factor 1.5 is how many cells a flat patch of area \(s_d^2\) cuts through, averaged over orientations: a patch with unit normal \(\mathbf{n}\) crosses about \(|n_x| + |n_y| + |n_z|\) cells, which averages 1.5. Only those \(S_d\) cells get split, and each split creates eight children, so a tree of depth \(D\) has
\[N_D = 1 + 8\sum_{d=0}^{D-1} S_d\]
nodes: the root, plus eight children for every cell that gets split. That grows like \(4^D\) while the dense grid grows like \(8^D\), so every extra level doubles the octree’s advantage.
For a concrete case, put a ball of radius 40 cm at the center of a 1 m cube and refine every cell its surface passes through. Counting exactly:
| depth \(D\) | 4 | 6 | 8 | 10 |
|---|---|---|---|---|
| cell size | 62.5 mm | 15.6 mm | 3.9 mm | 0.98 mm |
| dense grid cells \(8^D\) | 4,096 | 262,144 | 16.8 million | 1.07 billion |
| surface cells \(S_D\) | 776 | 12,368 | 197,624 | 3.16 million |
| octree nodes \(N_D\) | 2,313 | 32,969 | 527,689 | 8.43 million |
| dense ÷ octree | 1.8× | 8.0× | 31.8× | 127× |
At depth 10 the dense grid needs 1 GiB even at one byte per voxel. The octree, at a generous 8 bytes per node, needs about 64 MiB. The surface count also matches the area estimate above to within 0.01%.
Two caveats keep this honest. The saving comes from the surface being thin: a volume that varies everywhere, such as fog or the inside of a CT scan, gains little, and the pointers can cost more than a flat array would. And a pointer-based tree scatters its nodes through memory, so each step down risks a cache miss. Practical implementations store each node’s eight children side by side and keep one pointer plus an 8-bit mask saying which children exist, which is how sparse voxel octrees are laid out on the GPU.
3. Finding Things: Lookup, Neighbors and Rays
Lookup is a walk from the root. At each node, compare the query point with the center to get the three bits, step into that child, and repeat until you reach a leaf. That costs at most \(D\) steps, one per level, and often fewer, because a large uniform leaf ends the walk early. Insertion is the same walk, creating children on the way down.
Nearest Neighbors
Nearest-neighbor and radius queries use the boxes to rule out whole subtrees. The distance from a query point \(\mathbf{p}\) to a cube with center \(\mathbf{c}\) and half-side \(h\) is
\[\operatorname{dist}(\mathbf{p}, \text{box})^2 = \sum_{k \in \{x, y, z\}} \max\big(0,\; |p_k - c_k| - h\big)^2,\]
which is zero when the point is inside. Visit children in order of this distance and skip any child whose box is already farther than the best point found so far, since everything inside it is at least that far too. Most subtrees are discarded without ever being opened.
Ray Casting
Rendering, and the free-space updates in section 5, need the cells a ray passes through. Write the ray as the points \(\mathbf{o} + t\,\mathbf{d}\) for \(t \ge 0\), where \(\mathbf{o}\) is its origin, \(\mathbf{d}\) its direction and \(t\) how far along it you are, and write the box’s lowest and highest corners as \(\mathbf{b}^{\min}\) and \(\mathbf{b}^{\max}\). For each axis \(k \in \{x, y, z\}\), the slab test computes the two values of \(t\) at which the ray crosses the pair of faces perpendicular to that axis,
\[t_k^{1} = \frac{b_k^{\min} - o_k}{d_k}, \qquad t_k^{2} = \frac{b_k^{\max} - o_k}{d_k},\]
then keeps the latest entry and the earliest exit:
\[t_{\text{near}} = \max_k \min\big(t_k^1, t_k^2\big), \qquad t_{\text{far}} = \min_k \max\big(t_k^1, t_k^2\big).\]
The ray hits the box if \(t_{\text{near}} \le t_{\text{far}}\) and \(t_{\text{far}} \ge 0\). An octree traversal applies this test to the root, then to the children the ray actually crosses, in front-to-back order, and stops at the first occupied leaf. The payoff is empty-space skipping: a large empty node is crossed in a single step. A ray that walks voxel by voxel through a \(1024^3\) grid can visit up to 3,070 cells; in an octree, a ray through open space touches a few big nodes and only descends near surfaces.
4. Morton Codes: An Octree Without Pointers
The octant bits along a root-to-leaf path can be read straight off a cell’s integer coordinates. At depth \(D\), give each cell coordinates \(x, y, z \in \{0, \dots, 2^D - 1\}\). The most significant bit of \(x\) says which half the cell is in along \(x\) at the first split, the next bit decides the second split, and so on. Interleaving the bits of the three coordinates therefore spells out the whole path, three bits per level:
\[m = \sum_{k=0}^{D-1} \big(x_k + 2\,y_k + 4\,z_k\big)\, 8^{k},\]
where \(x_k\) is bit \(k\) of \(x\). This is the Morton code, or Z-order index, and each of its base-8 digits is exactly the octant index \(i\) from section 1.
Take \(D = 3\), an \(8 \times 8 \times 8\) grid, and the cell \((x, y, z) = (5, 3, 6)\), which is \((101, 011, 110)\) in binary. Reading the bits from the most significant end, one level at a time:
| level | \(x\) bit | \(y\) bit | \(z\) bit | octant \(x + 2y + 4z\) |
|---|---|---|---|---|
| 1 | 1 | 0 | 1 | 5 |
| 2 | 0 | 1 | 1 | 6 |
| 3 | 1 | 1 | 0 | 3 |
So the path from the root is octant 5, then 6, then 3, and the code is \(m = 5 \cdot 64 + 6 \cdot 8 + 3 = 371\), or 101 110 011 in binary. Following the same path with the child-center formula from section 1, starting from a unit cube, lands on \((0.6875, 0.4375, 0.8125)\), which is exactly the center of cell \((5, 3, 6)\) at side 1/8.
Two properties make Morton codes useful. Truncating a code gives an ancestor: dropping the last three bits of 371 gives 46, the depth-2 node containing the cell, and dropping six gives 5, its depth-1 octant. And sorting cells by code lists them in depth-first order of the tree, so every subtree occupies one contiguous run of the sorted array. A linear octree is exactly that, a sorted array of codes, with parent–child relations recovered by bit shifts instead of stored pointers. GPUs build octrees and bounding-volume hierarchies this way, starting from a single parallel sort.
The price is locality at the seams. Cells that touch in space can sit far apart in the order when they straddle the boundary between large octants: cells 3 and 9 in Figure 2 share an edge, yet six codes separate them. Neighbor search in a linear octree therefore computes the neighbors’ codes with bit arithmetic instead of assuming that nearby codes mean nearby cells.
5. A Worked Example: Occupancy Mapping with OctoMap
A robot mapping a room with a depth camera never knows for sure whether a cell is occupied; it accumulates evidence. OctoMap, the octree mapping library that ROS and MoveIt use for 3D occupancy, keeps that evidence in each leaf as the log-odds \(l\) of the probability \(p\) that the cell is occupied,
\[l = \log\frac{p}{1 - p},\]
which turns each Bayesian update into an addition. Every depth measurement is a ray from the sensor: the cell at its endpoint receives a hit, and the cells it passed through on the way receive a miss. With OctoMap’s default sensor model, \(p_{\text{hit}} = 0.7\) and \(p_{\text{miss}} = 0.4\), the increments are
\[l_{\text{hit}} = \log\tfrac{0.7}{0.3} = +0.847, \qquad l_{\text{miss}} = \log\tfrac{0.4}{0.6} = -0.405,\]
and a cell counts as occupied while \(l > 0\), that is, while \(p > 0.5\).
Why the Values Are Clamped
Left alone, the sums grow without bound. A wall seen 100 times reaches \(l = 84.7\); if part of it then moves, say a door swings open, it takes 209 contradicting observations before the map agrees. OctoMap therefore clamps every leaf to \([l_{\min}, l_{\max}] = [-2, 3.5]\), which is \(p \in [0.12, 0.97]\). Here is one cell seen occupied six times, after which the door opens and the cell is seen free again and again:
| after | log-odds \(l\) | \(p\)(occupied) |
|---|---|---|
| 1 hit | 0.847 | 0.700 |
| 2 hits | 1.695 | 0.845 |
| 4 hits | 3.389 | 0.967 |
| 5 hits | 3.500 (clamped) | 0.971 |
| 6 hits | 3.500 (clamped) | 0.971 |
| then 1 miss | 3.095 | 0.957 |
| then 4 misses | 1.878 | 0.867 |
| then 8 misses | 0.256 | 0.564 |
| then 9 misses | −0.149 | 0.463 |
The sixth hit changes nothing, because the cell is already pinned at \(l_{\max}\). From there, nine misses flip it to free instead of 209.
Pruning
Clamping has a second benefit: it makes compression possible. Once the leaves of a stable region are all pinned at the same bound, eight siblings often hold identical values, and OctoMap prunes them, deleting the children and storing the value once in the parent. A large empty room ends up as a few big free nodes instead of millions of small leaves, and nothing is lost, because the children were identical. If a later measurement disagrees with part of a pruned node, the node is expanded again before the update.
6. Where Octrees Show Up
- Rendering. Sparse voxel octrees store geometry and color for real-time ray casting. PlenOctrees made NeRF render in real time by baking the trained radiance field into an octree whose leaves hold density and spherical-harmonic color, and Octree-GS arranges 3D Gaussian splats in octree levels so that distant regions draw coarser detail.
- Robotics. OctoMap-style maps back collision checking in motion planners such as MoveIt and next-best-view planning for scanning. A grasp planner uses one to rule out gripper poses that would hit the scene before it scores the contacts themselves, as in Friction Cone and Antipodal Grasps.
- Point clouds. PCL’s octree module handles radius and nearest-neighbor search, voxel-centroid downsampling and change detection between scans, and the MPEG G-PCC standard compresses point-cloud geometry by coding each node’s 8-bit child-occupancy mask.
- Learning. O-CNN runs convolutions only on the octants a shape’s surface occupies, so memory follows the surface instead of the bounding volume.
Octree or Something Else?
An octree is not the only way to avoid paying for empty space, and it is not always the best.
- A dense grid wins when the volume is small or busy everywhere: lookup is one array index and there are no pointers to chase.
- Spatial hashing, as in voxel hashing for real-time 3D reconstruction, stores only occupied blocks with constant-time average lookup, but it has no hierarchy, so it cannot answer coarse queries or skip empty space in big strides.
- A k-d tree splits at data-dependent planes, which adapts better to uneven point sets and is often faster for nearest-neighbor search, but its cells do not line up with a voxel grid, so it fits occupancy and volumes poorly.
- A bounding-volume hierarchy partitions objects rather than space, which suits ray tracing triangle meshes better than voxel data.
The octree’s niche is the middle ground: spatially organized data, mostly empty, needed at several resolutions at once.
Intuitively: Twenty Questions in 3D
Finding a spot in a room with an octree is a game of twenty questions in which every round asks three at once: left or right, front or back, up or down. Each round narrows the region to one of eight, so ten rounds, thirty yes-or-no answers, pin a point to a millimeter-sized cell of a one-meter cube, out of about a billion possibilities.
What makes it cheap is that you are allowed to stop early. Ask about the empty corner of the room and the answer after the first round is “nothing here, all the way down.” Only where something interesting sits do you keep asking. An octree is that conversation written down: short answers for empty space, long ones only where the detail lives.