High-performance Octree for Three.js
- Table of Contents
- Usage
- Quick Reference – API Cheat-Sheet
- Features
- Usage Cookbook
- 1. Vanilla Three.js – Raycasting against 100 k meshes
- 2. React-Three-Fiber – Automatic registration
- 3. Frustum Culling – Massive Tileset
- 4. Physics Broad-Phase – Overlap Queries
- 5. LOD Selection – Distance-Sorted List
- 6. Web Worker – Zero-Copy Batch Updates
- 7. Streaming – Add & Remove Tiles over Time
- 8. React-Three-Fiber + Worker (Full Pipeline)
- 9. Debug Visualization (r3f helper)
- 10. Manual Frame-by-Frame Update (Camera-Following Objects)
Install:
npm add oc3
With dependencies:
npm add three oc3
Import into your code:
import { Octree } from 'oc3'
import { OctreeWorkerBackend } from 'oc3/worker-backend'
- Check demo for a full-blown html example of
oc3
being used with Web-Worker backend. - Refer usage cookbook for stand alone ready-to-use examples of using
oc3
in various scenarios.
Task | Vanilla | R3F Hook |
---|---|---|
Insert | oct.insert({box,id}) |
<OctreeMesh> auto |
Remove | oct.remove({box,id}) |
unmount component |
Update | oct.update({box,id}) |
transform change auto |
Raycast | oct.raycast(ray,hits) |
useFrame(()=>oct.raycast(...)) |
AABB query | oct.aabbQuery(box,cb) |
useOctree().aabbQuery |
Frustum query | oct.frustumQuery(frustum,cb) |
useOctree().frustumQuery |
-
Goals
- Provide an octree spatial-index that is blazing-fast for three.js geometries and objects.
- Remain framework-agnostic: must work in vanilla three.js, r3f, A-Frame, Babylon (via adapters), etc.
- TypeScript-first, tree-shakeable ESM, zero runtime deps except
three
. - Offer both an acceleration structure (for raycasting, frustum culling, nearest-neighbor, etc.) and an optional ECS-friendly wrapper for reactive scenes (r3f).
- Memory & CPU budget:
- ≤ 40 ns per insertion in hot path (≈ 25 M ops/s on M2).
- ≤ 4 bytes per empty child pointer (typed arrays).
- GC pressure ≈ 0 (pre-allocated pools).
-
Use-Cases it is Optimised for
- Raycasting on 100 k meshes (r3f
<mesh>
). - Frustum culling for massive tilesets.
- Physics broad-phase (AABB queries).
- LOD selection (find all objects inside node).
- Streaming - fast insert / remove / update as tiles stream in.
- Raycasting on 100 k meshes (r3f
-
Design Highlights
- Does not allocate on every insertion/removal (object pooling).
- Does allow SIMD-like AABB tests (SoA float32 arrays).
- Reuses three.js math primitives (
THREE.Box3
,THREE.Vector3
, etc.) but allows zero-copy when caller already has flat arrays. - Exposes iterator-based API to avoid large temporary arrays.
-
API Surface (vanilla)
class Octree { constructor(box?: Box3, maxDepth?: number, maxObjects?: number); insert(object: Object3D | Box3): void; remove(object: Object3D | Box3): boolean; update(object: Object3D): void; // fast move aabbQuery(box: Box3, visitor: (o)=>void): void; frustumQuery(frustum: Frustum, visitor: (o)=>void): void; raycast(ray: Ray, hits: Array<Intersection>): void; clear(): void; }
- Each method is iterative (no recursion) to avoid call-stack overhead.
Object3D
is optional; plain AABB can be used for pure data.
-
r3f (react-three-fiber) Integration
A thin React reconciler wrapper that:- Subscribes to r3f’s
useFrame
to update moving objects viaOctree#update
. - Provides
<OctreeProvider>
context so child meshes register themselves automatically viaReact.useLayoutEffect
. - Exposes a hook
useOctree()
to run spatial queries in user land.
- Subscribes to r3f’s
-
Memory Layout (SoA)
Float32Array(8*3) // 8 corner xyz (static) Uint16Array(8) // child indices (-1 = null) Uint16Array(8) // object list heads (index into ObjectStore)
ObjectStore is a pool array of fixed-size records (32 bytes):
struct ObjectRecord { float minX, minY, minZ, maxX, maxY, maxZ; uint32 userId; // Object3D id or custom }
Hot loops operate on contiguous Float32Array → SIMD-friendly.
-
Build & Distribution
tsup
for ESM/CJS dual package.exports
map with"three"
as peer dependency."sideEffects": false
for full tree-shaking.- Provides
three-octree/three
entry for three.js specific helpers, andthree-octree/core
for framework-agnostic core.
-
Benchmark Harness
- vitest + @thi.ng/bench.
- Compare against
THREE.MeshBVH
, naive linear.
-
Future expansions:
- Compressed octree (SVO) for GPU storage.
- WebWorkers batch update API. (Update: already implemented. Refer the documentation)
• Internally uses an ObjectStore
which is a lock-free pool backed by contiguous typed arrays → achieves zero-allocation hot path.
• All recursive algorithms rewritten to iterative loops (not shown for brevity in split/query).
• The r3f layer only attaches lightweight event listeners (afterMatrixUpdate
) rather than diffing every frame.
Oc3 keeps the core octree engine entirely decoupled from three.js or React, while providing thin, optional adapters that stay out of the critical path.
Below are ready to use examples for every major scenario. Each example is self-contained and works in vanilla three.js, r3f, or Web-Workers without changes.
import * as THREE from 'three';
import { Octree } from 'oc3/core';
const scene = new THREE.Scene();
const camera = new THREE.PerspectiveCamera(75, window.innerWidth/window.innerHeight, 0.1, 1000);
const renderer = new THREE.WebGLRenderer();
document.body.appendChild(renderer.domElement);
// 1. Build the tree once
const oct = new Octree(new THREE.Box3().setFromCenterAndSize(
new THREE.Vector3(0,0,0),
new THREE.Vector3(100,100,100)
));
// 2. Insert every mesh
const inst = new THREE.InstancedMesh(
new THREE.BoxGeometry(1,1,1),
new THREE.MeshBasicMaterial(),
100_000
);
scene.add(inst);
const m = new THREE.Matrix4();
const box = new THREE.Box3();
for (let i = 0; i < 100_000; i++) {
m.setPosition(Math.random()*100-50, Math.random()*100-50, Math.random()*100-50);
inst.setMatrixAt(i, m);
box.setFromCenterAndSize(
new THREE.Vector3().setFromMatrixPosition(m),
new THREE.Vector3(1,1,1)
);
oct.insert({ box, id: i });
}
// 3. Fast raycasting
const raycaster = new THREE.Raycaster();
const hits: THREE.Intersection[] = [];
renderer.domElement.addEventListener('click', e => {
raycaster.setFromCamera(
{ x: (e.clientX/window.innerWidth)*2-1, y: -(e.clientY/window.innerHeight)*2+1 },
camera
);
oct.raycast(raycaster.ray, hits);
console.log('hits', hits);
});
Install
npm i oc3 @react-three/fiber
import { Canvas } from '@react-three/fiber';
import { OctreeProvider, OctreeMesh } from 'oc3/r3f';
function App() {
return (
<Canvas>
<OctreeProvider>
<Scene/>
</OctreeProvider>
</Canvas>
);
}
function Scene() {
return (
<>
{Array.from({ length: 5_000 }, (_, i) => (
<OctreeMesh key={i} position={[Math.random()*100-50, Math.random()*100-50, 0]}>
<boxGeometry/>
<meshBasicMaterial/>
</OctreeMesh>
))}
</>
);
}
The provider automatically registers every <OctreeMesh>
on mount and updates its AABB when it moves.
import { PerspectiveCamera, Frustum } from 'three';
import { Octree } from 'oc3/core';
const oct = new Octree();
tiles.forEach(t => oct.insert({ box: t.bbox, id: t.id }));
const cam = new PerspectiveCamera(60, 1, 1, 10000);
const frustum = new Frustum();
function updateCulling() {
cam.updateMatrixWorld();
frustum.setFromProjectionMatrix(cam.projectionMatrix.clone().multiply(cam.matrixWorldInverse));
const visible: string[] = [];
oct.frustumQuery(frustum, id => visible.push(id));
// hide / show tiles
}
import { Octree } from 'oc3/core';
import { Box3 } from 'three';
const oct = new Octree();
const boxes: Box3[] = /* initial set */;
boxes.forEach((b, i) => oct.insert({ box: b, id: i }));
// every frame
boxes.forEach((b, i) => {
oct.aabbQuery(b.expandByScalar(0.01), id => {
if (id !== i) console.log(`collision ${i} ↔ ${id}`);
});
});
import { Vector3, Box3 } from 'three';
import { Octree } from 'oc3/core';
const oct = new Octree();
const lodBoxes: { box: Box3; id: number; dist: number }[] = [];
// insert once
oct.insert({ box: lodBox, id });
function selectLOD(viewPos: Vector3, radius: number) {
const list: { id: number; dist: number }[] = [];
oct.aabbQuery(new Box3().setFromCenterAndSize(viewPos, new Vector3(radius,radius,radius)), id => {
const d = lodBoxes[id].box.getCenter(new Vector3()).distanceToSquared(viewPos);
list.push({ id, dist: d });
});
list.sort((a,b) => a.dist - b.dist);
return list.slice(0, 16); // nearest
}
worker.ts
import { OctreeWorkerBackend } from 'oc3/worker-backend';
const backend = new OctreeWorkerBackend(self);
backend.onBatch = batch => {
for (const { cmd, id, aabb } of batch) {
if (cmd === 'insert') backend.insert(id, aabb);
else if (cmd === 'remove') backend.remove(id);
else if (cmd === 'update') backend.update(id, aabb);
}
backend.commit(); // atomic swap, <0.1 ms
};
main.ts
import { OctreeProxy } from 'oc3/worker-proxy';
const oct = new OctreeProxy(new Worker(new URL('./worker.ts', import.meta.url), { type: 'module' }));
await oct.ready;
// stream 10 k tiles
const batch = [];
for (let i = 0; i < 10_000; i++) {
batch.push({ cmd: 'insert', id: i, aabb: tileAABBs[i] });
}
oct.postBatch(batch);
// raycast on main thread without worker round-trip
oct.raycast(ray, hits);
import { Octree } from 'oc3/core';
const oct = new Octree();
// simulate server push
socket.on('tile', tile => {
oct.insert({ box: tile.bbox, id: tile.id });
});
socket.on('unload', id => {
oct.remove({ box: new Box3(), id }); // box is not used for removal
});
import { Canvas } from '@react-three/fiber';
import { OctreeProvider } from 'oc3/r3f';
import { OctreeProxy } from 'oc3/worker-proxy';
const worker = new Worker(new URL('./worker.ts', import.meta.url), { type: 'module' });
const oct = new OctreeProxy(worker);
function App() {
return (
<Canvas>
<OctreeProvider octree={oct}>
<Terrain/>
</OctreeProvider>
</Canvas>
);
}
function Terrain() {
const oct = useOctree();
useEffect(() => {
fetch('/tiles.json').then(r => r.json()).then(tiles => {
oct.postBatch(tiles.map(t => ({ cmd: 'insert', id: t.id, aabb: new Float32Array(t.aabb) })));
});
}, [oct]);
return null; // terrain rendered from oct query results
}
import { OctreeHelper } from 'oc3/three';
function Debug() {
const oct = useOctree();
return <OctreeHelper octree={oct} depth={3} />;
}
import { Octree } from 'oc3/core';
import { Box3 } from 'three';
const oct = new Octree();
const objs = new Map<number, Box3>();
function animate() {
requestAnimationFrame(animate);
// move objects
objs.forEach((box, id) => {
box.translate(new Vector3(0, 0.1, 0));
oct.update({ box, id });
});
renderer.render(scene, camera);
}
MIT License.
For issues or contributions, please open a pull request or issue on the repository.