SceneTrees

SceneTrees keeps every mesh tree and the top level of a scene in three storage buffers on one GPUDevice: the buffers the walk binds. It works with any engine; three's sync drives it from a scene graph.

import { SceneTrees, type MeshGeometry } from '@pmndrs/bvh';

const trees = await SceneTrees.create(device, {
    onTree: (event) => console.log(`mesh ${event.mesh}: ${event.builtBy} tree after ${event.ms.toFixed(0)} ms`, event.replaced ? '(swap)' : ''),
});
const mesh = trees.addMesh(chair); // one tree per mesh, shared by its instances
for (const objectToWorld of chairMatrices) trees.addInstance({ mesh, objectToWorld }); // column-major 4x4

// Every frame (or whenever the scene changed):
const encoder = device.createCommandEncoder();
trees.update(encoder);
device.queue.submit([encoder.finish()]);

On a device with subgroups, every mesh an update brings is built twice:

A mesh's first tree is whichever arrives first. Without subgroups, or with gpuFirstTrees: false, every mesh waits for tinybvh: the declared fallback.

Sponza (132 meshes, 5.74 million triangles) on the Apple M5 (Chrome, scene-trees-sponza page, indicative): every mesh had a GPU tree 100-190 ms after the first update, depending on the run and the cap, and every tinybvh tree was in about 285-370 ms after it (trees.timeline). On the three load-gltf example (405 meshes, 3.7 million triangles), first trees took about 150-230 ms and every tinybvh tree about 600 ms after the first update.

frame(); // an update starts the builds
await trees.whenBuilt(); // every mesh with instances has a tree (GPU or tinybvh)
frame(); // the next update places them
await trees.whenRefined(); // every GPU tree has been replaced by tinybvh's
frame();

Builds start in update, never in addMesh: a mesh added since the last update counts as waiting, so whenBuilt() and whenRefined() never resolve if no update comes. Call update once after adding meshes, as frame() does above, then await. A frame loop that already runs needs nothing extra; a page that awaits before its first frame hangs.

onTree reports every placement: the mesh, builtBy ('gpu' or 'tinybvh'), replaced ('gpu' for a swap), fallbackReason and the milliseconds since the update that started it.

onTree says when a tree is placed. onBuild says what happens before: for each mesh (or merged group) and each builder ('gpu', 'tinybvh'), the build is 'requested' in the update that brings the mesh, 'started' when its GPU batch is submitted (a capped batch can wait in the queue first) or a worker takes the tinybvh build, and 'finished' with an outcome:

Each event has the milliseconds since the request, the triangle count, and rebuild for a deforming mesh's rebuild. A finished GPU build has gpuMs: the batch's pass from timestamps with timestamps: true, shared by the batch's meshes, else null. A build that ends before it starts skips 'started'. Nothing is reported after dispose().

const trees = await SceneTrees.create(device, {
    // Each mesh's build, per builder: 'requested' (in an update), 'started', 'finished' (with its outcome).
    onBuild: (event) => {
        const who = event.mesh !== null ? `mesh ${event.mesh}` : `merged group ${event.group}`;
        if (event.phase !== 'finished') console.log(who, event.builder, event.phase);
        else console.log(who, event.builder, event.outcome, `${event.ms.toFixed(0)} ms`, event.reason ?? '', event.gpuMs ?? '');
    },
    // Placed: what rays see from the next frame.
    onTree: (event) => console.log(`mesh ${event.mesh}: ${event.builtBy} tree placed`),
});

Two numbers, both from timestamp queries (the device needs timestamp-query):

// timestamps: each GPU build batch's pass, summed in counts.gpuBuildTimestampMs (needs timestamp-query).
const trees = await SceneTrees.create(device, { timestamps: true });
const querySet = device.createQuerySet({ type: 'timestamp', count: 2 });
const resolved = device.createBuffer({ size: 16, usage: GPUBufferUsage.QUERY_RESOLVE | GPUBufferUsage.COPY_SRC });
const read = device.createBuffer({ size: 16, usage: GPUBufferUsage.MAP_READ | GPUBufferUsage.COPY_DST });

const encoder = device.createCommandEncoder();
// A timestamp before and after everything the update records (copies, refits, the top level).
trees.update(encoder, { timestampWrites: { querySet, beginningOfPassWriteIndex: 0, endOfPassWriteIndex: 1 } });
encoder.resolveQuerySet(querySet, 0, 2, resolved, 0);
encoder.copyBufferToBuffer(resolved, 0, read, 0, 16);
device.queue.submit([encoder.finish()]);
await read.mapAsync(GPUMapMode.READ);
const [start, end] = new BigInt64Array(read.getMappedRange());
console.log(`update: ${Number(end - start) / 1e6} ms on the GPU; builds so far: ${trees.counts.gpuBuildTimestampMs ?? '-'} ms`);

With refine: false, a device with subgroups keeps its GPU trees: tinybvh builds only the meshes the GPU gave no usable tree (too big for a batch, deeper than gpuMaxDepth, a batch that failed), as the declared fallback, and their fallbackReason says why. It suits scenes that change often, where tinybvh's better trees would arrive too late to matter, and tools that compare the GPU builder alone. Each mesh's geometry is kept until its GPU tree is in (for that fallback). Without subgroups, or with gpuFirstTrees: false, tinybvh builds every mesh either way.

// GPU trees only: tinybvh builds just the meshes the GPU refuses (and every mesh without subgroups).
const trees = await SceneTrees.create(device, { refine: false });

placeTree(mesh, layout) places a tree the app made (on a worker's own device, from a file, with any builder that writes the GPU layout) as the mesh's tree from the next update. It is final, as tinybvh's is: given before the first update that brings the mesh, no build starts for it; given later, a tinybvh build still running is cancelled and a GPU tree that comes after it is dropped. A deforming mesh's rebuilds still replace it. onTree, meshStatus and counts.onAppTrees say 'app'.

const trees = await SceneTrees.create(device);
const mesh = trees.addMesh(crate);
// A tree you built (another device, a file, any builder of the GPU layout) from the same geometry:
// given before the first update, the mesh starts no builds; later, its builds are cancelled or dropped.
trees.placeTree(mesh, crateLayout);
trees.addInstance({ mesh, objectToWorld: matrix });
// The next update places it: trees.meshStatus(mesh).builtBy === 'app'.

The limits: the tree must be built from the geometry given to addMesh (with its triangle flags and materials), in the scene's triangle format; f32 nodes are quantized for a quantized scene, but a quantized tree needs a quantized scene; a deforming mesh needs an f32 tree; an indexed scene welds each mesh's vertices unless weld: false (or the mesh deforms), and refuses an indexed tree then; and the tree must be within gpuMaxDepth. Each refusal is a RangeError. The layout's arrays are read at the next update.

Trees baked to files go the same way: placeTree(mesh, deserializeLayout(bytes, { geometry })), which checks the file against the mesh's geometry first (Baked trees in SceneTrees).

The node and triangle buffers grow by doubling. A growth replaces the GPUBuffer and bumps trees.version. Make your bind groups again when it changes; nothing recompiles.

let boundVersion = -1;
const afterUpdate = () => {
    if (trees.version !== boundVersion) {
        rebind(trees.buffers); // a buffer grew: make the bind groups again (nothing recompiles)
        boundVersion = trees.version;
    }
};

trees.traceBuffers gives the buffers in the shape TraceBatchKernel and BvhTraceNodes take, with the scene's formats.

const trees = await SceneTrees.create(device, {
    gpuFirstTrees: true, // H-PLOC trees first on a device with subgroups (default)
    gpuMaxBatchBytes: 256 * 1024 * 1024, // the build-peak cap (default); Infinity: one batch
    workers: { size: 4 }, // the tinybvh worker pool, or a pool of your own
    topLevel: 'auto', // the GPU top level with subgroups, the CPU one without (default)
    mergeStaticInstances: true, // the default: static instances merge at the first update
    triangleLeaves: 'records', // the default; or 'indexed' (16-byte triangles)
    nodeFormat: 'quantized', // the default; or 'f32' (64-byte nodes)
});

An indexed scene (triangleLeaves: 'indexed') keeps a copy of every mesh's vertices for the walk, buffers.positions (45.2 MiB on Sponza with vec4 positions). An app that already keeps all its vertices in one f32 storage buffer can have the walk bind that buffer instead, with positionsBuffer, and the copy is never made:

trees.buffers.positions is then your buffer, and memory.positions is 0. A three.js app can't use it today: three keeps each attribute in a buffer of its own, without storage usage.

console.log(trees.gpuFirstTrees); // { enabled, reason }: why GPU first trees are off, if they are
console.log(trees.counts.onGpuTrees, trees.counts.onTinybvhTrees, trees.counts.swaps);
console.log(trees.timeline.firstTreesMs, trees.timeline.tinybvhTreesMs);
console.log((trees.memory.resident / 2 ** 20).toFixed(1), 'MiB resident,', (trees.memory.peak / 2 ** 20).toFixed(1), 'MiB peak');

SceneTrees keeps no CPU copy of its trees. For CPU picking on the same scene, build a CPU scene too.

dispose() frees its buffers and the worker pool it made.