Game Dev Mechanics: Octrees — How It Works

In 3D games, thousands of objects coexist in vast three-dimensional spaces. Every frame, the engine must answer questions like: Which enemies are close enough to hear the player? What objects might collide with this projectile? Which lights affect this particular surface? Brute-force checking every object against every other object is an $O(n^2)$ disaster. Octrees are a spatial data structure that partitions 3D space hierarchically, enabling these queries to run in $O(\log n)$ time.

From Quadtrees to Octrees

If you are familiar with quadtrees (the 2D spatial partitioning structure that divides a plane into four quadrants), octrees will feel like a natural extension. Where a quadtree splits a 2D rectangle into four children along two axes (x and y), an octree splits a 3D box (axis-aligned bounding box, or AABB) into eight children along three axes (x, y, and z). The name comes from the Latin octo, meaning eight.

Each internal node in an octree represents a cubic or rectangular region of 3D space. When a node accumulates more objects than its capacity allows, it subdivides into eight equally sized child nodes, one for each octant. This recursive subdivision continues until a maximum depth is reached or nodes remain under capacity.

The Octree Structure

An octree node consists of:

• Bounds: An axis-aligned bounding box defined by a center point $(c_x, c_y, c_z)$ and a half-size $h$
• Children: Either null (leaf node) or an array of 8 child nodes
• Data: Points or object references stored at leaf nodes
• Depth: The current level in the tree hierarchy

The eight octants are defined by the signs of the offset from the center:

$$\text{octant}(i) = \left( c_x + s_x \cdot \frac{h}{2},\; c_y + s_y \cdot \frac{h}{2},\; c_z + s_z \cdot \frac{h}{2} \right)$$

where $s_x, s_y, s_z \in \{-1, +1\}$ and $i \in \{0, 1, \ldots, 7\}$. A common convention maps the three sign bits directly to the octant index:

$$i = (s_x > 0\;?\;1 : 0) \;|\; (s_y > 0\;?\;2 : 0) \;|\; (s_z > 0\;?\;4 : 0)$$

This bit-packing trick means determining which octant a point falls into requires only three comparisons and three bitwise OR operations, fast enough for real-time use.

Insertion Algorithm

Inserting a point into an octree follows a simple recursive pattern:

• If the point is outside this node's bounds, reject it.
• If this node is a leaf and has room, store the point here.
• If this node is a leaf but full, subdivide into 8 children, redistribute existing points, then insert the new point into the appropriate child.
• If this node is already internal (has children), recurse into the child whose bounds contain the point.

class OctreeNode {
  constructor(centerX, centerY, centerZ, halfSize, depth = 0) {
    this.cx = centerX;
    this.cy = centerY;
    this.cz = centerZ;
    this.halfSize = halfSize;
    this.depth = depth;
    this.points = [];
    this.children = null; // null means leaf node
  }

  insert(px, py, pz, data) {
    // Reject if outside bounds
    if (!this.containsPoint(px, py, pz)) return false;

    // Leaf node with room, or at max depth
    if (!this.children) {
      if (this.points.length < MAX_CAPACITY || this.depth >= MAX_DEPTH) {
        this.points.push({ x: px, y: py, z: pz, data: data });
        return true;
      }
      // Full leaf: subdivide
      this.subdivide();
      for (const p of this.points) {
        for (const child of this.children) {
          if (child.insert(p.x, p.y, p.z, p.data)) break;
        }
      }
      this.points = [];
    }

    // Insert into the appropriate child
    for (const child of this.children) {
      if (child.insert(px, py, pz, data)) return true;
    }
    return false;
  }

  containsPoint(px, py, pz) {
    return px >= this.cx - this.halfSize
        && px <= this.cx + this.halfSize
        && py >= this.cy - this.halfSize
        && py <= this.cy + this.halfSize
        && pz >= this.cz - this.halfSize
        && pz <= this.cz + this.halfSize;
  }

  subdivide() {
    const h = this.halfSize / 2;
    this.children = [];
    for (let i = 0; i < 8; i++) {
      const ox = (i & 1) ? h : -h;
      const oy = (i & 2) ? h : -h;
      const oz = (i & 4) ? h : -h;
      this.children.push(
        new OctreeNode(this.cx + ox, this.cy + oy, this.cz + oz, h, this.depth + 1)
      );
    }
  }
}

Subdivision only happens when needed. Sparse regions of space remain as large leaf nodes, while dense clusters trigger recursive subdivision. This adaptive resolution is what makes octrees efficient.

Range Queries

The primary advantage of an octree is fast spatial queries. The most common type is the range query: given a search region (typically a sphere or AABB), find all points within that region.

For a spherical query with center $\mathbf{q}$ and radius $r$, we test each octree node's AABB for intersection with the sphere. If a node's AABB does not intersect the sphere, we skip the entire subtree, potentially eliminating thousands of points from consideration in a single test.

The AABB-sphere intersection test finds the closest point on the box to the sphere center, then checks whether the squared distance is within the squared radius:

$$d^2 = \sum_{i \in \{x,y,z\}} \left( \max\left(0,\; |q_i - c_i| - h\right) \right)^2$$

$$\text{intersects} = (d^2 \leq r^2)$$

Using squared distances avoids an expensive square root operation, a common optimization in game math.

queryRange(qx, qy, qz, radius, results) {
  // Find the closest point on this AABB to the query center
  const clampX = Math.max(this.cx - this.halfSize, Math.min(qx, this.cx + this.halfSize));
  const clampY = Math.max(this.cy - this.halfSize, Math.min(qy, this.cy + this.halfSize));
  const clampZ = Math.max(this.cz - this.halfSize, Math.min(qz, this.cz + this.halfSize));

  const dx = clampX - qx;
  const dy = clampY - qy;
  const dz = clampZ - qz;

  // If the closest point on the AABB is outside the sphere, skip subtree
  if (dx * dx + dy * dy + dz * dz > radius * radius) return;

  if (!this.children) {
    // Leaf: check individual points
    for (const p of this.points) {
      const px = p.x - qx, py = p.y - qy, pz = p.z - qz;
      if (px * px + py * py + pz * pz <= radius * radius) {
        results.push(p);
      }
    }
  } else {
    // Internal: recurse into children
    for (const child of this.children) {
      child.queryRange(qx, qy, qz, radius, results);
    }
  }
}

Performance Analysis

Octrees benefit from aggressive subtree pruning. Consider querying for all points within a small sphere in a space containing $n$ points:

• Brute force: $O(n)$, checks every single point
• Octree query: $O(\log n + k)$, traverses $O(\log n)$ tree levels, then checks $k$ candidates in relevant leaves

For a balanced octree with maximum depth $d$ and node capacity $c$:

$$n_{\text{max}} = c \cdot 8^d$$

A depth-6 octree with capacity 8 can efficiently manage over 2 million objects. At each tree level during a query, we eliminate on average 7 out of 8 octants, rapidly narrowing the search space. This branching factor of 8 is what gives the octree its logarithmic query time in three dimensions.

Real-World Applications

Broad-Phase Collision Detection

Game engines like Unreal Engine and Godot use octrees or similar spatial acceleration structures for broad-phase collision detection. Before running expensive narrow-phase tests like GJK or SAT on precise geometry, the engine queries the octree to retrieve only those objects whose bounding volumes are close enough to potentially overlap. This turns an $O(n^2)$ pairwise test into something far more manageable.

Frustum Culling Integration

Octrees integrate naturally with frustum culling. Rather than testing every object against the six planes of the camera frustum, the engine tests octree nodes hierarchically. If a node's AABB is entirely outside the frustum, all its descendants and their objects are skipped immediately. If a node is entirely inside, all its objects are rendered without further per-object testing. Only nodes that partially intersect the frustum require recursive descent.

Sparse Voxel Octrees (SVO)

Games like Teardown and rendering research from NVIDIA's VXGI (Voxel Global Illumination) use sparse voxel octrees, where each leaf represents a voxel of material data. Empty regions of space consume no memory at all, making SVOs far more memory-efficient than dense 3D grids for complex environments with large amounts of open air.

Ray Tracing Acceleration

In ray tracing pipelines, octrees accelerate ray-object intersection tests. A ray traverses the octree, and the algorithm only tests intersection with objects in the nodes that the ray actually passes through. Community-built path tracing shaders for Minecraft rely on octree traversal to achieve real-time performance on consumer GPUs.

Spatial Audio

Sound propagation in 3D games also benefits from octrees. Engines need to quickly determine which sound emitters are near the listener and how geometry between them affects propagation. Games like Hellblade: Senua's Sacrifice use spatial data structures to manage hundreds of dynamic sound sources efficiently.

Optimizations and Variants

Loose Octrees

Standard octrees struggle with objects that straddle node boundaries. A large object sitting exactly on a dividing plane has no single child to fall into. A loose octree solves this by expanding each node's effective bounds by a looseness factor $k$ (typically $k = 2$):

$$h_{\text{effective}} = h \cdot k$$

The logical partitioning (which octant an object belongs to, based on its center) remains the same, but the physical bounds of each node overlap with neighbors. This guarantees that any object smaller than the original node size fits entirely within at least one node, eliminating the need to store boundary-straddling objects at parent levels.

Morton Codes and Z-Order Curves

For cache-friendly memory access during traversal, you can linearize octree nodes using Morton codes. By interleaving the bits of the $x$, $y$, and $z$ coordinates, you produce a single integer that preserves spatial locality: nearby points in 3D space map to nearby values in the linear ordering:

function mortonEncode3D(x, y, z) {
  function spread(v) {
    v = (v | (v << 16)) & 0x030000FF;
    v = (v | (v <<  8)) & 0x0300F00F;
    v = (v | (v <<  4)) & 0x030C30C3;
    v = (v | (v <<  2)) & 0x09249249;
    return v;
  }
  return spread(x) | (spread(y) << 1) | (spread(z) << 2);
}

Storing octree nodes in Morton order means that spatially adjacent nodes are also adjacent in memory, which improves CPU cache hit rates during tree traversal.

Object Octrees vs. Point Octrees

The examples above demonstrate point octrees, where each item occupies a single point in space. Object octrees handle extended objects (with their own bounding volumes) differently. One approach stores each object at the smallest node that fully contains it. Another uses loose octrees as described above. Some engines maintain separate static and dynamic octrees: the static tree is built once at level load and never changes, while the dynamic tree is rebuilt or updated incrementally each frame for moving objects.

When to Use Octrees

Octrees are a strong choice when:

• Your game world is three-dimensional (for 2D, use quadtrees instead)
• Objects are unevenly distributed in space, as octrees naturally adapt to local density
• You need spatial queries: nearest neighbor, range search, ray intersection
• The dataset is relatively stable or changes incrementally between frames

Alternatives worth considering: BVH (Bounding Volume Hierarchies) often outperform octrees for ray tracing because they adapt to object shapes rather than uniform space subdivision. Spatial hashing can be faster for uniformly distributed objects of similar size. k-d trees may produce more balanced partitions for certain point distributions. Octrees remain a solid general-purpose choice for 3D spatial queries in game development, combining simplicity with predictable performance.

The interactive demo above lets you explore octree behavior firsthand. Add points to watch the tree subdivide, toggle the query sphere to see range queries prune the search space in real time, and orbit the camera to examine the spatial hierarchy from every angle.