oc3

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)

Usage

Install:

npm add oc3

With dependencies:

npm add three oc3

Import into your code:

import { Octree } from 'oc3'
import { OctreeWorkerBackend } from 'oc3/worker-backend'

Examples

• 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.

Quick Reference – API Cheat-Sheet

| 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 |

Features

1. 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).

2. 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.

3. 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.

4. 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.

5. r3f (react-three-fiber) Integration
   A thin React reconciler wrapper that:

   • Subscribes to r3f’s useFrame to update moving objects via Octree#update.
   • Provides <OctreeProvider> context so child meshes register themselves automatically via React.useLayoutEffect.
   • Exposes a hook useOctree() to run spatial queries in user land.

6. 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.

7. 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, and three-octree/core for framework-agnostic core.

8. Benchmark Harness

   • vitest + @thi.ng/bench.
   • Compare against THREE.MeshBVH, naive linear.

9. Future expansions:

   • [ ] Compressed octree (SVO) for GPU storage.
   • [x] WebWorkers batch update API. (Update: already implemented. Refer the documentation)

Performance Notes

• 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.

Usage Cookbook

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.

1. Vanilla Three.js – Raycasting against 100 k meshes

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);
});

2. React-Three-Fiber – Automatic registration

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.

3. Frustum Culling – Massive Tileset

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
}

4. Physics Broad-Phase – Overlap Queries

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}`);
  });
});

5. LOD Selection – Distance-Sorted List

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
}

6. Web Worker – Zero-Copy Batch Updates

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);

7. Streaming – Add & Remove Tiles over Time

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
});

8. React-Three-Fiber + Worker (Full Pipeline)

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
}

9. Debug Visualization (r3f helper)

import { OctreeHelper } from 'oc3/three';

function Debug() {
  const oct = useOctree();
  return <OctreeHelper octree={oct} depth={3} />;
}

10. Manual Frame-by-Frame Update (Camera-Following Objects)

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);
}

License

MIT License.

Contact

For issues or contributions, please open a pull request or issue on the repository.