Octree Search

Octree search extends quadtree ideas to three dimensional space. It recursively partitions space into eight octants, enabling efficient spatial queries over 3D points or volumes.

It is commonly used in graphics, physics simulation, and spatial indexing.

Problem

Given a set of 3D points and a query axis aligned bounding box (AABB), find all points inside the box:

x_1 \le x \le x_2,\quad y_1 \le y \le y_2,\quad z_1 \le z \le z_2

Structure

Each node represents a cubic region and has up to eight children:

octant	region
000	x low, y low, z low
001	x low, y low, z high
010	x low, y high, z low
011	x low, y high, z high
100	x high, y low, z low
101	x high, y low, z high
110	x high, y high, z low
111	x high, y high, z high

Each node stores:

field	meaning
boundary	3D box region
points	points in leaf
children	eight octants

Algorithm

Search prunes nodes whose bounding boxes do not intersect the query box.

octree_search(node, Q, result):
    if node is null:
        return

    if not intersects(node.boundary, Q):
        return

    if node is leaf:
        for p in node.points:
            if p inside Q:
                add p to result
        return

    for child in node.children:
        octree_search(child, Q, result)

Example

Points:

point
(1,1,1)
(2,3,4)
(5,5,5)
(7,8,9)

Query box:

[1,1,1] \to [4,4,4]

Matches:

point	inside
(1,1,1)	yes
(2,3,4)	yes
(5,5,5)	no
(7,8,9)	no

Correctness

Each node covers a disjoint axis aligned region of 3D space. If a node’s region does not intersect the query box, none of its children can intersect it, so pruning is safe.

Leaf nodes contain explicit point lists, and every point belongs to exactly one leaf region at the deepest level. Therefore all candidate points are checked, and only those inside the query box are returned.

Complexity

Let $n$ be number of points and $k$ number of results.

case	time
average query	$O(\log n + k)$
worst case	$O(n)$

Space complexity:

O(n)

When to Use

Octrees are useful when:

working in 3D space (graphics, physics, simulations)
spatial partitioning is needed for collision detection
volumetric queries or visibility tests are required
data is static or moderately dynamic

Compared to k-d trees, octrees partition space uniformly rather than by median splits. Compared to R trees, octrees are simpler but less flexible for arbitrary volumes.

Implementation

class Node:
    def __init__(self, boundary):
        self.boundary = boundary
        self.points = []
        self.children = []

def intersects(a, b):
    return not (
        a[3] < b[0] or a[0] > b[3] or
        a[4] < b[1] or a[1] > b[4] or
        a[5] < b[2] or a[2] > b[5]
    )

def inside(p, Q):
    return (
        Q[0] <= p[0] <= Q[3] and
        Q[1] <= p[1] <= Q[4] and
        Q[2] <= p[2] <= Q[5]
    )

def octree_search(node, Q, result):
    if node is None:
        return

    if not intersects(node.boundary, Q):
        return

    if len(node.children) == 0:
        for p in node.points:
            if inside(p, Q):
                result.append(p)
        return

    for child in node.children:
        octree_search(child, Q, result)

type Point3 struct {
	X, Y, Z float64
}

type Box struct {
	X1, Y1, Z1 float64
	X2, Y2, Z2 float64
}

type Node struct {
	Boundary Box
	Points   []Point3
	Children []*Node
}

func intersects(a, b Box) bool {
	return !(a.X2 < b.X1 || a.X1 > b.X2 ||
		a.Y2 < b.Y1 || a.Y1 > b.Y2 ||
		a.Z2 < b.Z1 || a.Z1 > b.Z2)
}

func inside(p Point3, Q Box) bool {
	return p.X >= Q.X1 && p.X <= Q.X2 &&
		p.Y >= Q.Y1 && p.Y <= Q.Y2 &&
		p.Z >= Q.Z1 && p.Z <= Q.Z2
}

func OctreeSearch(node *Node, Q Box, res *[]Point3) {
	if node == nil {
		return
	}

	if !intersects(node.Boundary, Q) {
		return
	}

	if len(node.Children) == 0 {
		for _, p := range node.Points {
			if inside(p, Q) {
				*res = append(*res, p)
			}
		}
		return
	}

	for _, child := range node.Children {
		OctreeSearch(child, Q, res)
	}
}