Cairn
data structures · spatial indexing · avg O(log n) insert/query, O(n) worst case (clustered points)

↩ back to Spatial

Octree

An Octree is a Quadtree with one more axis. Where a quadtree splits a square region into four equal quadrants the moment it overflows, an octree splits a cube region into eight equal octants — cut once through the middle on each of x, y, and z instead of just x and y. Everything that makes a quadtree's split cheap carries over unchanged: the split point is the box's own geometric center, decided before a single point is looked at, so computing which child a point belongs to is still three independent comparisons (one per axis), not a search against other points.

The three-axis split is also exactly what costs more. Four quadrants become eight children at every internal node, so the same point count spreads across twice as many boxes per level — a tree over evenly-spread 3D data is shallower in theory (each split roughly divides the point count by eight instead of four) but every internal node now owns eight child pointers instead of four, and a query that doesn't prune well touches more siblings per level on the way down. The trade is the same one Space for Time already names for other structures: more branching per node buys a shallower tree at the cost of a wider one.

Try it

Ten points inside a 240-unit cube, capacity 2 per box, drawn in an isometric projection so depth reads as "up the y-axis" on screen. Press Step or Run to insert them one at a time: watch a box split into eight equal octants — drawn as nested wireframe cubes, not point-to-point lines — the moment a third point would land inside an already-full box, with its existing points re-sorted into whichever new octant actually contains them. Once every point is placed, the demo switches automatically to a range query for the dashed query box: watch it walk the tree, skip (fade out, dashed) any box that doesn't overlap the query box at all — sometimes several octants at once — and mark every point that lands inside it as a match.

boxes visited: 0 · matches: 0
Press Step or Run.

Why it works

Inserting a point walks down from the root exactly like a quadtree: if the current box isn't yet divided and has room under capacity, the point is added to that box's own list. If the box is already divided, three comparisons — is the point past the box's x-midpoint, y-midpoint, and z-midpoint — pick exactly one of the eight children, each comparison independent of the other two. Packing the three yes/no answers into three bits gives an octant index from 0 to 7 directly, no lookup table needed. The interesting step is still what happens when an undivided box is already at capacity: it splits into eight new octants of exactly half its width, height, and depth, its existing points get re-homed into whichever new octant contains each of them, and only then does the new point get inserted the same way.

A range query prunes the same way the Quadtree's does, just with one more axis to check: a box's own boundary is the only thing that needs testing against the query box. If the two don't overlap on any of the three axes, nothing inside that box — none of its own points, none of its children's points, no matter how many levels deep — can possibly be inside the query box either, so the whole subtree is skipped in one O(1) test. A query box covering a small corner of the cube prunes entire octants, often several at a time, without ever looking at the points they contain.

Reference implementation

function makeOctree(boundary, capacity = 4, maxDepth = 8, depth = 0) {
  return { boundary, capacity, maxDepth, depth, points: [], divided: false, children: null };
}

function contains(node, pt) {
  const b = node.boundary;
  return pt[0] >= b.x && pt[0] < b.x + b.s &&
         pt[1] >= b.y && pt[1] < b.y + b.s &&
         pt[2] >= b.z && pt[2] < b.z + b.s;
}

// Three independent comparisons packed into one 0-7 index: bit 4 = past the x-midpoint,
// bit 2 = past the y-midpoint, bit 1 = past the z-midpoint.
function octantIndex(b, pt) {
  const hs = b.s / 2;
  let idx = 0;
  if (pt[0] >= b.x + hs) idx |= 4;
  if (pt[1] >= b.y + hs) idx |= 2;
  if (pt[2] >= b.z + hs) idx |= 1;
  return idx;
}

function octantBoundary(b, idx) {
  const hs = b.s / 2;
  return {
    x: b.x + ((idx & 4) ? hs : 0),
    y: b.y + ((idx & 2) ? hs : 0),
    z: b.z + ((idx & 1) ? hs : 0),
    s: hs,
  };
}

function subdivide(node) {
  node.children = [];
  for (let i = 0; i < 8; i++) {
    node.children.push(makeOctree(
      octantBoundary(node.boundary, i), node.capacity, node.maxDepth, node.depth + 1));
  }
  node.divided = true;

  const old = node.points;
  node.points = [];
  for (const pt of old) insertIntoChild(node, pt); // re-home every existing point
}

function insertIntoChild(node, pt) {
  return insert(node.children[octantIndex(node.boundary, pt)], pt);
}

function insert(node, pt) {
  if (!contains(node, pt)) return false;
  if (!node.divided) {
    // maxDepth guard: past this depth, stop splitting and just keep growing this
    // box's own list -- see this page's Pitfalls section for what skipping it does.
    if (node.points.length < node.capacity || node.depth >= node.maxDepth) {
      node.points.push(pt);
      return true;
    }
    subdivide(node);
  }
  return insertIntoChild(node, pt);
}

function rangeQuery(node, range, found = []) {
  const b = node.boundary;
  const overlaps = !(range.x > b.x + b.s || range.x + range.sx < b.x ||
                      range.y > b.y + b.s || range.y + range.sy < b.y ||
                      range.z > b.z + b.s || range.z + range.sz < b.z);
  if (!overlaps) return found; // whole subtree pruned, points never even read

  for (const pt of node.points) {
    if (pt[0] >= range.x && pt[0] < range.x + range.sx &&
        pt[1] >= range.y && pt[1] < range.y + range.sy &&
        pt[2] >= range.z && pt[2] < range.z + range.sz) {
      found.push(pt);
    }
  }
  if (node.divided) {
    for (const child of node.children) rangeQuery(child, range, found);
  }
  return found;
}

Pitfalls

Skipping the max-depth guard doesn't crash — it silently deletes points, the exact same way it does for Quadtree. Dropping node.depth >= node.maxDepth and splitting purely on node.points.length < node.capacity looks like a harmless simplification, since the box's center split never separates two points that share one exact coordinate — in 3D exactly as much as in 2D. Feeding 500 inserts of the exact same coordinate to that stripped-down version, capacity 3: insert() itself reports success only 3 times (matching capacity), the recursion keeps halving the box's width, height, and depth every level until 64-bit float precision runs out — measured directly, at depth 55 the box's own side length underflows to 2.78e-14 — and past that point contains() starts returning false for every child, so the point subdivide() was mid-way through re-homing just vanishes with no error anywhere. Counting every point actually reachable in the finished tree after all 500 inserts: zero — not even the 3 that insert() itself claimed succeeded, swept into the same losing cascade during a later point's subdivide() call. Re-running the identical 500-duplicate-coordinate test with the maxDepth guard back in place (depth 8): all 500 succeed and all 500 are actually stored.

The guard that fixes data loss doesn't fix the complexity — and in 3D the same box can end up holding even more. With maxDepth in place, those same 500 duplicate points don't vanish, but they also don't spread across eight octants the way the capacity check assumes — they all land in the one leaf that happens to contain that exact coordinate, and once that leaf hits depth 8 it stops trying to split at all. The finished tree has a single leaf holding all 500 points against a nominal capacity of 3, and any range query touching that one box now degrades to a linear scan of 500 points — the same "correct answer, no longer fast" shape as Quadtree's own clustered-point pitfall, just reached by halving three axes instead of two.

Range queries themselves are correct when pruning is used. Checked against a brute-force linear scan across 5,000 random trials (1 to 60 points each, random query boxes in 3D): zero mismatches. This is a different check from the two above — it confirms the pruning logic never throws away a real match, only that clustered input can make the tree itself lopsided.

Where octrees show up

Anywhere 3D space itself — not just a fixed set of points — needs to be addressed and queried repeatedly: broad-phase collision detection in 3D game engines and physics simulators (only objects whose bounding boxes actually overlap need the expensive precise check), voxel engines that need to know which chunk of a large world is near a given position without scanning the whole world, point cloud processing from LIDAR or photogrammetry scans (millions of raw 3D samples, queried for nearby points or down-sampled region by region), and volumetric data like CT/MRI scans or sparse 3D textures, where most of the volume is empty and an octree lets a renderer skip entire empty sub-cubes instead of walking every voxel. The fixed, coordinate-derived octant boundaries matter here for the same reason a quadtree's fixed quadrants do: two independent systems — a renderer and a physics engine, say — can each compute the same octant boundary for the same coordinates without sharing any tree state.

Complexity

Insert: O(log n) average — each split roughly divides a region's point count by eight, so a tree over evenly-spread data reaches depth O(log₈ n), a shallower tree than a quadtree's O(log₄ n) over the same point count. Worst case is O(maxDepth), effectively O(1) once the depth cap is hit, at the same cost documented above: a box that hits the cap stops shrinking and can accumulate arbitrarily many points. Range query: O(log n + k) for k results under reasonably spread data — descend and prune down to the relevant boxes, then read off every match; the 5,000-trial stress test above confirms correctness but the pitfalls above show the "reasonably spread" assumption is exactly the thing clustered data breaks, same as every other region-based Spatial entry on this site. Space: O(n) points stored total, plus one node object per box actually created by a split — bounded by 8 · min(n / capacity, 8^maxDepth) in the worst case, eight child pointers per internal node instead of a quadtree's four.