Octree Spatial Partitioning

Particles

Particle count 120

Octree parameters

Max objects per node 6

Max subdivision depth 5

Live stats

Octree nodes

Depth reached

Octree comparisons

Naive O(n²) comparisons

Collisions this frame

How it works

An octree recursively cuts a cubic region of space into 8 equal octants whenever a node holds more objects than a threshold, down to a maximum depth:

if objects.length > MAX_OBJECTS and depth < MAX_DEPTH:
    subdivide node into 8 child cubes (half the side length)
    re-insert every object into the children it overlaps

This build uses a loose octree: a sphere is inserted into every leaf whose cube its bounding sphere touches, so nothing is missed at a boundary. Collision candidates are only checked within the same leaf, so the comparison count is roughly:

Octree:  Σ over leaves of  k·(k-1)/2   (k = objects in that leaf)
Naive:   n·(n-1)/2                    (every pair, always)

Because each leaf holds at most ~MAX_OBJECTS spheres, the octree sum grows close to O(n log n) as n increases, while the naive check stays O(n²) — the gap you see in the two comparison counters is exactly why broad-phase collision detection in physics engines and game worlds uses spatial trees instead of checking every pair.

Max objects per node — lower values subdivide earlier, creating more/smaller leaves and fewer comparisons per leaf, at the cost of more nodes to traverse.
Max subdivision depth — caps how far the tree can recurse, preventing runaway subdivision when many spheres cluster in one small region.
A true collision (sphere-sphere overlap, distance < r₁+r₂) turns both spheres red; the tree itself is rebuilt from scratch every frame since the spheres are moving.

Particle Colliding pair Octree node bounds

⚠ Couldn't load the 3D engineThree.js failed to load from the CDN. Check your connection and reload.