@pmndrs/bvh
Full documentation content.
\[!IMPORTANT] The package is at version 0.0.0 and not on npm yet. The API can still change before 0.1.
## What is in it
| Part | What it does | Page |
| ------------------------ | ------------------------------------------------------------------------------------------------------------------------------------ | ----------------------------------------------------------------------- |
| Builders | tinybvh (CPU, WebAssembly), H-PLOC and LBVH (GPU, WGSL), and a chooser that picks one. A new method from a paper is one more builder | [Choosing a builder](/bvh/builders/choosing-a-builder) |
| One GPU layout | 64-byte two-child nodes (32-byte quantized ones in scenes, by default), 48-byte triangles, a parent per node, `GPU_LAYOUT_VERSION` | [The GPU layout](/bvh/concepts/gpu-layout) |
| `SceneTrees` | A scene's trees on one device: GPU trees first, tinybvh's swapped in, the GPU top level, runtime changes | [SceneTrees](/bvh/scenes/scene-trees) |
| Refits | Top-level refit over moving instances, per-mesh refit for deforming meshes, both on the GPU | [Refits](/bvh/scenes/refits) |
| Clustering | Big meshes cut into clusters, each its own top-level leaf (three-mesh-bvh's `ClusteredBVH`) | [Clustered top level](/bvh/scenes/clustered-top-level) |
| The WGSL walk | `bvhTraceClosest` and `bvhTraceAny`, masks, a triangle filter, a watertight triangle test, ray batches | [Tracing in WGSL](/bvh/tracing/wgsl-walk) |
| GPU spatial queries | Closest point, sphere and box tests and your own shapecast in WGSL | [Spatial queries](/bvh/tracing/gpu-queries) |
| Signed distance fields | A 3D texture or buffer of distances to a scene's triangles, filled on the GPU | [SDF](/bvh/tracing/sdf) |
| CPU queries | Raycast, shapecast, bvhcast and closest point over the same layout | [Raycast](/bvh/cpu-queries/raycast) |
| Points and lines | Trees over points and line segments, on the CPU, with three's raycast thresholds | [Points and lines](/bvh/cpu-queries/points-and-lines) |
| Serialization and baking | Build once (in Node, at build time), save the bytes, load them with no build | [Serialization and baking](/bvh/serialization/serialization-and-baking) |
| three.js | Scenes from `Object3D`, GPU skinning, TSL nodes, and three-mesh-bvh's CPU API | [three.js](/bvh/three/overview) |
| Babylon.js | Picking with `scene.pick`'s result, scenes from meshes, the walk in a `ComputeShader` (basic) | [Babylon.js](/bvh/engines/babylon) |
| Workers | A pool of tinybvh workers that needs no cross-origin isolation | [Workers](/bvh/workers/workers) |
## What it is not
- It has no WebGL2 path. The CPU queries work anywhere JavaScript runs, but no GPU work targets WebGL2.
- It is not a renderer. The package ends at the hit: the triangle, instance, barycentrics, face normal and a material number it carries but never reads. What a hit looks like (lights, sampling, textures) is yours.
- Babylon.js support is "it works", not polish: `/babylon` has picking that returns `scene.pick`'s `PickingInfo`, a mesh conversion, and the walk in a `ComputeShader` on the `WebGPUEngine`'s device, reached through the engine's internals ([Babylon.js](/bvh/engines/babylon)). It has no scene sync or skinning.
- Points and lines are primitives on the CPU only ([Points and lines](/bvh/cpu-queries/points-and-lines)): the GPU walk and `SceneTrees` take triangles.
- It is not a drop-in for all of three-mesh-bvh. Nearly all of its CPU API is here, and a few things are left out on purpose ([Coming from three-mesh-bvh](/bvh/three/coming-from-three-mesh-bvh)).
## Where to start
1. [Installation](/bvh/getting-started/installation): the package and a device with `subgroups`.
2. [First build](/bvh/getting-started/first-build): a vanilla quick start and two three.js quick starts.
3. [The GPU layout](/bvh/concepts/gpu-layout), if you will write your own walk or read the trees yourself.
Users of three-mesh-bvh can start at [Coming from three-mesh-bvh](/bvh/three/coming-from-three-mesh-bvh).
## How the docs are organised
The sections run from first steps to depth, top to bottom in the sidebar:
- **Getting started** and **Concepts** teach the layout and the rules every builder follows.
- **Builders**, **Scenes**, **Workers** and **Engines** cover building trees and keeping them current, then sharing a device with three or Babylon.
- **Tracing** is the GPU side: the walk, queries and distance fields. **CPU queries** is the same on the CPU.
- **three.js** has the engine pages, including the drop-ins for three-mesh-bvh.
- **Serialization**, **Performance** (how every number was measured), **Examples** and the **API reference** close the site.
The repository front page, [the README](https://github.com/pmndrs/bvh#readme), has the three quick starts side by side, and [HISTORY.md](https://github.com/pmndrs/bvh/blob/main/HISTORY.md) tells how the package got here.
]]>
\[!NOTE] `@pmndrs/bvh` is not published yet. Until it is, build it from [the repository](https://github.com/pmndrs/bvh) (`pnpm install && pnpm build`) and link it.
For the three.js subpath, also install three. It is an optional peer dependency, pinned to `>=0.187.0 <0.188.0` because `BvhTraceNodes` reads three's WebGPU backend internals, and each three release is checked before the range widens.
```bash
npm install three@0.187
```
For the Babylon.js subpath, install `@babylonjs/core` (an optional peer dependency, `>=9.35.0 <10.0.0`, tested on 9.35.0). `@pmndrs/bvh/babylon` reads `WebGPUEngine`'s internal `_device`, so each Babylon release is checked before the range widens ([Babylon.js](/bvh/engines/babylon)).
```bash
npm install @babylonjs/core@9.35.0
```
## Entry points
| Import | What it holds |
| --------------------- | ----------------------------------------------------------------------------------------------------------------------------------------- |
| `@pmndrs/bvh` | The core: builders, refits, the layout, the WGSL walk and its CPU port, `SceneTrees`, CPU queries, serialization. No engine. |
| `@pmndrs/bvh/three` | three.js in, the core's inputs out; three-mesh-bvh's CPU API; `BvhTraceNodes` for TSL and WGSL. |
| `@pmndrs/bvh/babylon` | Babylon.js in, the core's inputs out; picking with `scene.pick`'s result; the engine's device and a `ComputeShader` for the walk (basic). |
| `@pmndrs/bvh/worker` | The tinybvh worker pool and the worker builders. |
The package is ES modules only, with `sideEffects: false`. The worker files are loaded with `new Worker(new URL(..., import.meta.url))`, which Vite and webpack 5 builds follow without configuration. esbuild doesn't, so its builds run on the main thread unless you add the worker files as entry points. Vite's dev server needs `optimizeDeps: { exclude: ['@pmndrs/bvh'] }`, and a checkout linked from outside the project needs its folder in `server.fs.allow`; see [Workers](/bvh/workers/workers#bundlers-and-dev-servers).
## Requirements
- **WebGPU** for anything on the GPU. The CPU queries and the tinybvh builder need only WebAssembly SIMD, which every current browser and Node have.
- **The `subgroups` feature** for the GPU builders (H-PLOC, LBVH) and both GPU refits. Without it there is one fallback: tinybvh builds every tree on the CPU, and the top level is rebuilt on the CPU. Chrome exposes subgroups on the GPUs the package is tested on (Apple M5, RTX 3060, Intel UHD). Safari and Firefox don't expose them yet.
- **Limits for big scenes.** A default device allows 128 MiB per storage binding, about 2.7 million triangles in the default layout. Ask for the adapter's limits when you need more.
## A device with subgroups
Ask for `subgroups` when the adapter has it, and for the adapter's buffer limits:
```ts
export async function requestBvhDevice(): Promise {
const adapter = await navigator.gpu.requestAdapter();
if (!adapter) throw new Error('WebGPU is not available');
const device = await adapter.requestDevice({
// The GPU builders and refits need subgroups. Without them, tinybvh builds every tree on the CPU.
requiredFeatures: adapter.features.has('subgroups') ? ['subgroups'] : [],
// A big scene needs more than the default 128 MiB per storage binding.
requiredLimits: {
maxStorageBufferBindingSize: adapter.limits.maxStorageBufferBindingSize,
maxBufferSize: adapter.limits.maxBufferSize,
},
});
return device;
}
```
The GPU code never assumes a subgroup size. It reads it from the device, and builds the same trees at 8, 16 or 32 lanes.
With three.js, the renderer makes the device. See [Sharing a device with an engine](/bvh/engines/sharing-a-device).
## Checking what you got
Every builder result says which builder made it and why the GPU wasn't used, if it wasn't:
- `createMeshLayoutBuilder(device).fallbackReason`, for example `the device has no "subgroups" feature`;
- `SceneTrees.gpuFirstTrees`, `{ enabled, reason }`;
- each `SceneTreeEvent.fallbackReason`, per mesh.
Show it in your app. A slow load on a device without subgroups is the CPU fallback, not a slow library.
]]>
{
const encoder = device.createCommandEncoder();
trees.update(encoder); // starts builds, places finished trees, refits the top level
device.queue.submit([encoder.finish()]);
};
update();
await trees.whenBuilt(); // every mesh has a tree
update();
// One ray, traced with the package's batch kernel.
const kernel = await TraceBatchKernel.create(device);
const rays = device.createBuffer({ size: RAY_BYTES, usage: GPUBufferUsage.STORAGE | GPUBufferUsage.COPY_DST });
device.queue.writeBuffer(rays, 0, packRays([{ origin: [0, 0, 5], direction: [0, 0, -1], tMin: 0, tMax: 1e30 }]));
const results = device.createBuffer({ size: HIT_RECORD_BYTES, usage: GPUBufferUsage.STORAGE | GPUBufferUsage.COPY_SRC });
const encoder = device.createCommandEncoder();
kernel.encode(encoder, trees.traceBuffers, { mode: 'closest', rays, results, count: 1 });
device.queue.submit([encoder.finish()]);
```
What happens:
- `SceneTrees.create` compiles the GPU builder's kernels (when the device has `subgroups`).
- The first `update` builds the mesh with H-PLOC on the GPU, and also starts a tinybvh build in a worker.
- Builds start only in `update`, so the first `update()` must come before `await trees.whenBuilt()`; without it the promise never resolves.
- The next `update` after `whenBuilt()` places the tree. When tinybvh's tree arrives, a later `update` swaps it in. See [Fast first trees](/bvh/scenes/scene-trees#fast-first-trees-and-swaps).
Read the hit back:
```ts
import { HIT_RECORD_WORD } from '@pmndrs/bvh';
const readback = device.createBuffer({ size: HIT_RECORD_BYTES, usage: GPUBufferUsage.MAP_READ | GPUBufferUsage.COPY_DST });
const encoder = device.createCommandEncoder();
encoder.copyBufferToBuffer(results, 0, readback, 0, HIT_RECORD_BYTES);
device.queue.submit([encoder.finish()]);
await readback.mapAsync(GPUMapMode.READ);
const floats = new Float32Array(readback.getMappedRange());
const words = new Uint32Array(floats.buffer);
const t = floats[HIT_RECORD_WORD.t]; // < 0: a miss
if (t >= 0) console.log('hit triangle', words[HIT_RECORD_WORD.triangle], 'of instance', words[HIT_RECORD_WORD.instance], 'at', t);
readback.unmap();
```
To trace from your own shader instead of the batch kernel, see [Tracing in WGSL](/bvh/tracing/wgsl-walk).
## three.js on the GPU
The same trees, on the renderer's own device, kept in step with the scene graph, and read from TSL or WGSL:
```ts
import { Fn, If, vec3 } from 'three/tsl';
import { WebGPURenderer, type Scene } from 'three/webgpu';
import { BvhTraceNodes, deviceFromRendererAsync, SceneTreesObject3DSync, type BvhTslNode } from '@pmndrs/bvh/three';
const renderer = new WebGPURenderer();
const device = await deviceFromRendererAsync(renderer); // the renderer's own GPUDevice
const trees = await SceneTrees.create(device);
const sync = new SceneTreesObject3DSync(trees, scene); // adds every mesh and instance under `scene`
const bvh = new BvhTraceNodes(renderer, trees); // the walk in three's node system
// A TSL compute pass that traces (a material's nodes can call the same helpers):
const kernel = Fn(() => {
const hit = bvh.traceClosest(vec3(0, 1, 5), vec3(0, 0, -1)).toVar() as BvhTslNode;
If(hit.get('t').greaterThanEqual(0), () => {
/* hit.get('normal'), hit.get('instance'), hit.get('material'), ... */
});
})().compute(1);
// Each frame, before three uses the nodes:
const frame = () => {
scene.updateMatrixWorld();
sync.update(); // moved objects only
const encoder = device.createCommandEncoder();
trees.update(encoder);
device.queue.submit([encoder.finish()]);
bvh.update(); // rebinds if SceneTrees replaced a buffer
renderer.compute(kernel);
};
```
More in [three.js: scenes and the sync](/bvh/three/scenes-and-sync) and [BvhTraceNodes](/bvh/three/trace-nodes).
## three.js on the CPU
Drop-ins for three-mesh-bvh's functions of the same names. The raycast returns what three's `Mesh.raycast` returns:
```ts
import { BufferGeometry, Mesh, Raycaster, type Camera, type Vector2 } from 'three';
import { acceleratedRaycast, computeBoundsTree, disposeBoundsTree, prepareBoundsTrees } from '@pmndrs/bvh/three';
await prepareBoundsTrees(); // loads tinybvh (WebAssembly) once
BufferGeometry.prototype.computeBoundsTree = computeBoundsTree;
BufferGeometry.prototype.disposeBoundsTree = disposeBoundsTree;
Mesh.prototype.raycast = acceleratedRaycast;
mesh.geometry.computeBoundsTree();
const raycaster = new Raycaster();
raycaster.setFromCamera(pointer, camera); // pointer: -1 to 1 on both axes
raycaster.firstHitOnly = true; // optional: the closest hit only
const hits = raycaster.intersectObject(mesh); // the same intersections three's raycast returns
```
More in [CPU raycast in three](/bvh/three/cpu-raycast).
## Without SceneTrees
`SceneTrees` is the usual entry point. For a single tree, or full control over buffers, use a builder directly ([Choosing a builder](/bvh/builders/choosing-a-builder)) and `buildTraceScene` with `uploadTraceScene` ([Serialization and baking](/bvh/serialization/serialization-and-baking) has an example).
## Where next
- Scenes that change while they run: [Runtime changes](/bvh/scenes/runtime-changes), [Refits](/bvh/scenes/refits) and [Deforming meshes](/bvh/scenes/deforming-meshes).
- Writing your own kernel: [Tracing in WGSL](/bvh/tracing/wgsl-walk), or [Ray batches](/bvh/tracing/batches-and-the-cpu-walk) to trace without one.
- Picking and collision on the CPU: [Raycast](/bvh/cpu-queries/raycast).
- Coming from three-mesh-bvh: [the mapping](/bvh/three/coming-from-three-mesh-bvh).
]]>
bool
```
`true` means the ray passes through: nothing is recorded and the closest distance stays, so what lies behind is still found. Unflagged triangles never ask, so a scene pays only for the triangles that need it. Use it for alpha-tested foliage, glass that casts no shadow, or one-sided surfaces.
The candidate holds `instance`, `triangle` (the original index), `t`, `barycentrics`, `frontFace`, `query` (`BVH_QUERY_CLOSEST` or `BVH_QUERY_ANY`) and `rayMask`. It is a struct, so fields can be added without breaking filters.
The filter must not trace or query (`bvhTraceAny`, `bvhClosestPoint`, `bvhIntersects*`, `bvhShapecast`): a nested walk overwrites state the outer walk keeps in private variables (the node frame of quantized nodes), and the outer walk would read the rest of its instance wrongly. A shapecast's triangle hook may nest; see [Spatial queries on the GPU](/bvh/tracing/gpu-queries).
```ts
// Asked only for triangles with TRIANGLE_FLAG_FILTER set. true: the ray passes through.
const triangleFilter = /* wgsl */ `
fn bvhTrianglePasses(candidate: BvhCandidate) -> bool {
// Shadow rays pass through flagged triangles (foliage cards, glass); closest-hit rays still see them.
return candidate.query == BVH_QUERY_ANY;
}`;
const code = traceModuleWgsl({ triangleFilter });
```
The default filter, `DEFAULT_TRIANGLE_FILTER_WGSL`, lets nothing through. `triangleFilter: null` leaves the function out, for a kernel that declares `bvhTrianglePasses` itself (to read a texture, for example).
Flag the triangles when you add the mesh:
```ts
import { TRIANGLE_FLAG_FILTER, type MeshGeometry } from '@pmndrs/bvh';
const triangleCount = indices.length / 3;
const triangleFlags = new Uint32Array(triangleCount);
for (let triangle = 0; triangle < triangleCount; triangle++) if (isGlass(triangle)) triangleFlags[triangle] = TRIANGLE_FLAG_FILTER;
const window: MeshGeometry = { positions, indices, triangleFlags }; // only bit 0 may be set
const mesh = trees.addMesh(window);
```
For a scene assembled with `buildTraceScene`, `writeTriangleFilterFlags(scene, (originalIndex, sourceInstance) => ..., scene.meshes[i])` writes the flags into the scene's own buffer after assembly. The CPU walk and the reference tracer take the same filter as a TypeScript function (`TrianglePasses`).
## Materials
Each instance can carry a material index, 0 to 65534. It comes back as `hit.material` (and as word 6 of the batch kernel's 40-byte hit record). `BVH_NO_MATERIAL` (`0xffffffff`, `NO_MATERIAL` in TypeScript) means none was given, and is what a miss reports.
- It costs no binding and two loads per ray, after the walk.
- A merged static triangle keeps its source's material.
- In three, the sync's `material(mesh, info)` callback sets it per object and group.
### Per-triangle materials
A mesh can carry a material per triangle instead: `MeshInput.triangleMaterials`, one value per original triangle, 0 to 65534, or `TRIANGLE_MATERIAL_NONE` (`0xffff`) for none. **A hit's material is its triangle's when it has one, else its instance's, else `BVH_NO_MATERIAL`.**
```ts
import { TRIANGLE_MATERIAL_NONE } from '@pmndrs/bvh';
// One material per triangle (0-65534), by original triangle; TRIANGLE_MATERIAL_NONE (0xffff) takes the instance's.
const triangleMaterials = new Uint16Array(indices.length / 3).fill(TRIANGLE_MATERIAL_NONE);
triangleMaterials.fill(3, 0, 100); // triangles 0-99 are material 3
const mesh = trees.addMesh({ positions, indices, triangleMaterials });
trees.addInstance({ mesh, objectToWorld: matrix, material: 7 });
// hit.material: 3 on triangles 0-99, 7 (the instance's) on the others.
```
- Records keep it in flags bits 16-31 (`material + 1`), which every builder writes. Indexed scenes keep a 16-bit table per mesh before its header, and merged groups their side table. `triangleFlags` still may set bit 0 only.
- A merged triangle takes its source triangle's material, else its source instance's.
- It costs one select after the walk, nothing in the loop.
- `assembleTraceScene` with prebuilt trees: records scenes report the trees' bits. Indexed scenes take `geometries[i].triangleMaterials` when it is there, else the tree's records' bits, so both formats report the same; both present and different throws.
- `@pmndrs/bvh/three` fills it from a multi-material mesh's groups ([Scenes and the sync](/bvh/three/scenes-and-sync)).
The hit also has `normal`: the world-space geometric normal of the authored front side, unit length. Interpolated normals need your own attributes, through `hit.triangle` and `hit.barycentrics`.
]]>
console.log(`${inBatch.length} meshes: ${gpuMs ?? 'no timestamp-query'} ms on the GPU, ${wallMs} ms submit to done`),
});
```
To time the builders yourself, each GPU builder's `createBatch(...).encode(encoder, timestampWrites)` records a batch's one compute pass with your timestamp writes, and `buildMany(meshes, options, timestampWrites)` does the same in its own submit (resolve the query set after it resolves).
## tinybvh
```ts
import { createTinyBvhBuilder } from '@pmndrs/bvh';
const tiny = await createTinyBvhBuilder(); // loads the WebAssembly once
const { layout, buildMs } = tiny.buildLayout({ positions, indices }, { maxLeafPrimitives: 8 });
```
`buildLayout` runs on the calling thread. A big mesh blocks it for a second or more, so in a browser use `@pmndrs/bvh/worker` ([Workers](/bvh/workers/workers)). In Node it needs no GPU: see [Serialization and baking](/bvh/serialization/serialization-and-baking).
**Memory.** Each builder has its own WebAssembly memory, which starts at 64 MiB and grows to a build's peak: about 230 bytes per triangle (tinybvh's working arrays, the input copies and the output; one 5.7M-triangle mesh: 1,349 MiB). A WebAssembly memory never shrinks, so after a build that left it past `releaseAboveBytes` (default 256 MiB, `TINYBVH_RELEASE_ABOVE_BYTES`) the builder drops its instance and starts a fresh one on the next build; the old memory is freed when the garbage collector collects it (`createTinyBvhBuilder({ releaseAboveBytes: Infinity })` keeps one instance). `tiny.heapBytes`, `tiny.lastBuildHeapBytes` and `tiny.releases` show what it holds.
## GPU H-PLOC
```ts
import { GpuHplocBuilder, planGpuHplocBatches, type GpuMeshGeometry } from '@pmndrs/bvh';
const builder = new GpuHplocBuilder(device);
await builder.prepare(); // compiles the kernels, asynchronously
// One batch builds many meshes with the same dispatches. planGpuHplocBatches splits
// a scene that doesn't fit the device's buffers (or maxBatchBytes) into several.
const { batches, tooBig } = planGpuHplocBatches(device, meshes, { maxBatchBytes: 256 * 1024 * 1024 });
for (const batch of batches) {
const trees = await builder.buildMany(batch.map((index) => meshes[index]));
// trees.nodes, trees.triangles and trees.parents are GPU buffers the batch's meshes share.
for (const mesh of trees.meshes) {
if (mesh.problem) continue; // refused (too deep, for example): build this one with tinybvh
// mesh.nodeOffset and mesh.triangleOffset say where its tree sits in those buffers.
}
trees.destroy(); // when nothing reads them any more
}
console.log('for tinybvh:', tooBig);
```
- One batch builds many meshes with the same dispatches. All of a batch's trees share three buffers.
- Every GPU build reads a few stats words back (nothing per vertex), then the trees are ready.
- A mesh's tree is refused (`mesh.problem` set) on an index past the end of the positions, a word one GPU thread hands to another still unwritten after a bounded wait, a merge that found no pair (NaN boxes), or a tree too deep. Build that mesh with tinybvh. The chooser and `SceneTrees` do this for you.
- `readLayouts(trees)` copies trees to the CPU, which a refit's `setTree` and `serializeLayout` need.
Options (`HplocOptions`), besides the [contract's](/bvh/concepts/builder-contract#options):
- `mortonCodes`: `'cubic-30'` (default) or `'tinybvh-63'` (tinybvh's 63-bit codes).
- `tieBreak`: `'pairs'` (default) or `'tinybvh'`. On equal merged areas tinybvh's rule chains the tree: 3,000 identical triangles give depth 128, twice the walk's stack. `'pairs'` keeps it balanced.
With tinybvh's codes and tie rule, the CPU twin (`buildHplocOnCpu`) builds exactly the tree of tinybvh's `BuildHPLOC`. The GPU builds the same trees on every subgroup size (RTX 32 lanes, Intel 8-16).
## GPU LBVH
```ts
import { GpuLbvhBuilder } from '@pmndrs/bvh';
if (GpuLbvhBuilder.isSupported(device)) {
const builder = new GpuLbvhBuilder(device);
await builder.prepare();
const trees = await builder.buildMany(meshes);
const layouts = await builder.readLayouts(trees); // CPU copies, for a refit's setTree or a file
trees.destroy();
console.log(layouts.map((layout) => layout?.nodeCount));
}
```
Same API as H-PLOC. Its CPU twin is `buildLbvhOnCpu`.
## Trees from the GPU, used on the CPU
A tree from H-PLOC or the LBVH lives on the GPU. Refits order nodes by level on the CPU, so a GPU-built tree that will be refit is read back once with `readLayouts` after its build. Its shape doesn't change while the mesh deforms, so this is once per build, never per frame. `SceneTrees` does it for its deforming meshes.
Next: [Fallbacks and limits](/bvh/builders/fallbacks-and-limits).
]]>
triangle);
if (triangleCount <= 2) return singleLeafTopology(order, 0, triangleCount);
const centre = (triangle: number, axis: number) =>
(positions[indices[triangle * 3] * 3 + axis] + positions[indices[triangle * 3 + 1] * 3 + axis] + positions[indices[triangle * 3 + 2] * 3 + axis]) / 3;
// Four words per node: leftIndex, leftCount, rightIndex, rightCount. A count above 0 is a leaf of
// order[index .. index + count); a count of 0 is the inner node `index`. Node 0 is the root.
const children: number[] = [];
const emit = (start: number, count: number): number => {
const node = children.length / 4;
children.push(0, 0, 0, 0);
const run = order.subarray(start, start + count);
const extent = [0, 1, 2].map((axis) => Math.max(...run.map((t) => centre(t, axis))) - Math.min(...run.map((t) => centre(t, axis))));
const axis = extent.indexOf(Math.max(...extent));
run.sort((a, b) => centre(a, axis) - centre(b, axis));
const left = count >> 1;
for (const [side, from, size] of [[0, start, left], [2, start + left, count - left]]) {
if (size <= 4) children.splice(node * 4 + side, 2, from, size);
else children[node * 4 + side] = emit(from, size);
}
return node;
};
emit(0, triangleCount);
return { order, children: Uint32Array.from(children) };
}
export function treeFromTopology(positions: Float32Array, indices: Uint32Array) {
// The package writes the boxes, the triangle records and the parents from the shape alone.
return buildMeshBvhFromTopology({ positions, indices }, medianSplitTopology(positions, indices));
}
```
Two rules about the shape: a child's node number is larger than its parent's, and every triangle sits in exactly one leaf. Leaves larger than `maxLeafPrimitives` (8 by default) are cut in half for you. A mesh of one or two triangles has no inner node to split; `singleLeafTopology` makes its root.
## The checks
A builder is used only after it passes two checks. The first needs no GPU.
1. **The layout check.** `checkGpuLayout(layout, mesh)` returns a list of problems, empty when the tree is right: every triangle is there bit for bit, every box is exactly the box below it, and the parents, depth and counts agree. `treeSahCost(layout)` scores the tree (lower is better), so your builder can be compared with tinybvh's on the same mesh.
2. **The oracle.** The CPU walk over your trees must give the same answers as the tree-less reference on fixed hard cases and random rays, then the GPU walk must too, on every GPU you have. Why it is a gate, what its cases are and how to run the GPU page: [The oracle rule](/bvh/concepts/oracle).
```ts
import { buildReferenceScene, buildTraceScene, checkGpuLayout, compareClosest, createCpuTracer, createRandom, IDENTITY_TRANSFORM, randomRays, randomTriangleSoup, traceClosestReference, treeSahCost } from '@pmndrs/bvh';
const random = createRandom(1);
const geometry = randomTriangleSoup(random, 2000, 10, 1.5);
const mesh = { positions: geometry.positions, indices: new Uint32Array(geometry.positions.length / 3).map((_, i) => i) };
const instances = [{ meshIndex: 0, instanceIndex: 0, objectToWorld: IDENTITY_TRANSFORM }];
// 1. The tree is well formed: every triangle bit for bit, every box exactly the box below it.
const layout = treeFromTopology(mesh.positions, mesh.indices);
const problems = checkGpuLayout(layout, mesh); // [] when right
const sah = treeSahCost(layout); // lower is better; compare with tinybvh's on the same mesh
// 2. The CPU walk over your trees agrees with the tree-less reference on random rays.
const scene = await buildTraceScene([mesh], instances, { build: (input) => treeFromTopology(input.positions, input.indices as Uint32Array) });
const tracer = createCpuTracer(scene);
const reference = buildReferenceScene([mesh], instances);
const rays = randomRays(random, 5000, [-10, -10, -10, 10, 10, 10], 2);
let mismatches = 0;
for (const ray of rays) {
const hit = tracer.closest(ray);
if (compareClosest(hit && { hit: true, ...hit }, traceClosestReference(reference, ray), ray).verdict === 'mismatch') mismatches++;
}
```
Random rays are the easy part. The oracle's fixed cases (thin walls, mirrored transforms, rays aimed at shared edges, instance masks) are what find a builder's real mistakes; the fixtures are exported, so your own page can use them. The quantized and indexed layout variants run the same cases, and a builder is expected to pass them all.
## The bench rows
Correctness is a gate, speed is measured. A new builder adds its rows next to the others so the comparison stays honest:
- **The trace bench.** `tests/gpu/pages/trace-bench` times the walk on Sponza, Bistro and the other scenes, one `tracer` id per way of building trees (`ours-tinybvh`, `ours-lbvh`, `ours-hploc`, `ours-tmbuild`). Add yours as one more id. A GPU builder also reports its build time, tree size and SAH cost. Rows go to `bench/results/trace.csv` with the date, commit, device and browser.
- **The method is fixed:** a loaded GPU, medians, the same rays for every tracer, and the clock rule. How to read and repeat it: [Builds and tracing](/bvh/performance/builds-and-tracing#method).
- **The builders example.** `examples/vanilla/builders` shows each builder on one mesh: build time, SAH cost, depth, bytes, and trace speed on the same rays. A builder worth keeping gets a row there too.
Report the SAH cost and trace speed against tinybvh's trees, the quality reference. A faster build with worse trees is a trade, and the numbers should say which.
## The licence rule
Only code under **MIT or Apache-2.0** is ported into this package. Otherwise, build from the paper alone: papers are fine to implement, code with no licence or a copyleft one is not to be read and translated. When you port:
- put the licence text in `licenses/` and add the source, version and commit to `THIRD_PARTY.md`;
- say where the port differs from its source in `docs/internals/DIVERGENCES.md`;
- if code ends up in the `.wasm` or a bundled file, the build keeps its licence in a comment, and fails if a built file loses it.
The package's own licences are in the [README](https://github.com/pmndrs/bvh#licences).
## Candidates already researched
Two methods were researched and not built:
- **DOBB-BVH** (Kern et al., Computer Graphics Forum 44(8), 2025; arXiv:2506.22849), which turns a wide BVH into a tree of oriented bounding boxes with discretized rotations.
- **Tetrahedral cages**, a different shape for what a node bounds.
Both change what a node holds, so each would be a new node format as well as a builder, and its walk would need the same oracle. Their notes live in `research/` of the ddgi research repository, not here. One more builder that was tried and dropped is a compressed 8-wide layout (CWBVH): about the same trace speed on Sponza and slower on Bistro, for nodes four times smaller; the reasons are in [`docs/internals/design/bvh-framework.md`](https://github.com/pmndrs/bvh/blob/main/docs/internals/design/bvh-framework.md).
]]>
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()]);
```
- `addMesh(geometry)` returns a mesh handle. The geometry is read at the next `update` and copied into a worker (`transferGeometry: true` moves it instead).
- `addInstance({ mesh, objectToWorld, mask, material, visible, static, instanceIndex })` returns an instance handle. `instanceIndex` (default: the handle) comes back as `hit.instance`.
- `update(encoder)` does everything in the order the walk needs: starts builds, places finished trees, applies changes, refits deforming meshes and refits the top level. Record it before anything traces in that encoder.
## Fast first trees and swaps
On a device with `subgroups`, every mesh an `update` brings is built twice:
1. **On the GPU, with H-PLOC**, in batches (one for the whole scene unless the [build-peak cap](/bvh/builders/fallbacks-and-limits#the-build-peak-cap) splits it). Rays see these trees a few frames later.
2. **With tinybvh, in the worker pool**, biggest mesh first. Each tinybvh tree replaces the mesh's GPU tree as it arrives. Only that mesh's range and its table entry change, so nothing recompiles and the top level keeps its shape.
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](/bvh/examples/examples) (405 meshes, 3.7 million triangles), first trees took about 150-230 ms and every tinybvh tree about 600 ms after the first update.
```ts
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.
## Build events
`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`:
- `'built'`: a tree came back. It is placed at a later update (`onTree`), unless a better one came first (tinybvh's before the GPU's).
- `'refused'`: no usable tree (too big for a GPU batch, deeper than `gpuMaxDepth`, a batch that failed), with a `reason`.
- `'failed'`: tinybvh threw. `'cancelled'`: the mesh was removed while it built.
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()`.
```ts
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`),
});
```
## GPU time
Two numbers, both from timestamp queries (the device needs `timestamp-query`):
- **An update's GPU time.** `update(encoder, { timestampWrites })` writes `beginningOfPassWriteIndex` in a tiny compute pass before the first command it records and `endOfPassWriteIndex` in one after the last: tree copies, quantize and identity passes, refits, growth copies and the top-level refit. You resolve the query set. Both passes are recorded however the update ends, so the pair is never half written. GPU builds are not in it: they go in submits of their own.
- **The GPU builds.** With `timestamps: true`, each H-PLOC batch's pass is timed, and `counts.gpuBuildTimestampMs` sums them (null until one is timed). `counts.gpuBuildMs` stays the wall time from each batch's submit to its stats.
```ts
// 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`);
```
## GPU trees only
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.
```ts
// GPU trees only: tinybvh builds just the meshes the GPU refuses (and every mesh without subgroups).
const trees = await SceneTrees.create(device, { refine: false });
```
## Trees you built
`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'`.
```ts
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](/bvh/serialization/serialization-and-baking#baked-trees-in-scenetrees)).
## Rebinding when a buffer grows
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.
```ts
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.
## Options
```ts
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)
});
```
| Option | Default | What it does |
| -------------------------------------------------------- | -------------------------------------- | ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- |
| `gpuFirstTrees` | `true` | H-PLOC first trees on a device with subgroups. `false`: tinybvh only. |
| `gpuTreeOutputs` | `'copy'` | `'adopt'` makes the load batch's output buffers the scene's own (no copy), for a lower load peak and more node memory after the swaps. Any node and triangle format: quantized scenes adopt batches whose nodes H-PLOC wrote quantized (`gpuQuantizeOnEmit`, the default), and indexed scenes' builds leave room for each mesh's header. |
| `gpuQuantizeOnEmit` | `true` | Quantized scenes: H-PLOC writes the first trees' nodes quantized itself, so a batch holds 32-byte nodes, not 64, and no quantize pass runs (the same trees). Deforming meshes' builds stay `f32`. A custom first-tree builder that returns `f32` nodes still works with `'copy'`: they are packed on the way in. |
| `positionsBuffer` | none | Indexed scenes: bind [your own positions buffer](#your-own-positions-buffer) instead of the scene's copy. |
| `gpuMaxBatchBytes` | 256 MiB | [The build-peak cap](/bvh/builders/fallbacks-and-limits#the-build-peak-cap). `Infinity` turns it off. |
| `workers` | a pool of its own | A `BvhWorkerPool` to share, or options for the one it makes (and disposes). The scene's own pool ends workers idle for 30 s (`SCENE_WORKER_IDLE_TIMEOUT_MS`) unless the options set `idleTimeoutMs`. |
| `transferGeometry` | `false` | Move each mesh's arrays into the worker instead of copying them. |
| `mergeStaticInstances` | `true` | [Merged static instances](/bvh/scenes/merged-static): instances added with `static: true` before the first update merge into world-space trees. Nothing else is touched. |
| `refine` | `true` | tinybvh builds every mesh too and its tree replaces the GPU's. `false`: [GPU trees only](#gpu-trees-only). |
| `holdRefinements` | `false` | tinybvh trees wait until `releaseRefinements()`, for tools that check a scene mid-swap. |
| `gpuMaxDepth` | `GPU_TREE_MAX_DEPTH` (47) | Deeper trees are refused, keeping every tree within the walk's stack. |
| `topLevel` | `'auto'` | The GPU top level with subgroups, the CPU one without. `'cpu'`: always the CPU one. |
| `triangleLeaves`, `positionLayout`, `nodeFormat`, `weld` | records, `vec4`, `'quantized'`, `true` | [Layout variants](/bvh/concepts/gpu-layout#variants). Compile your walk from `trees.nodeFormat` (or leave the walk's default, also quantized). |
| `diagnostics` | `false` | Read the top level's refit stats back. |
| `timestamps` | `false` | Time each GPU build batch with timestamp queries (`counts.gpuBuildTimestampMs`; see [GPU time](#gpu-time)). |
| `onTree`, `onBuild`, `warn`, `label` | | Events (trees placed; [builds](#build-events)), where problems are reported, GPU object labels. |
## Your own positions buffer
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:
- the buffer holds every mesh's vertices in the walk's stride (`positionLayout: 'vec4'`, 16 bytes per vertex, the `w` unused; or `'packed'`, 12), each mesh's from the `vertexBase` given to `addMesh(geometry, { vertexBase })`, with exactly the bits of `geometry.positions` (the trees are built from the geometry, the walk reads the buffer);
- it needs `STORAGE` usage, and must stay alive and unchanged while the scene uses it;
- the scene doesn't weld (`weld` is false; the trees name the app's own vertices), doesn't merge static instances (`mergeStaticInstances` is false: a merged group's world-space vertices aren't in the buffer) and takes no deforming meshes (their refit writes each pose into the scene's copy). Asking for any of these throws.
`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.
## What it holds
```ts
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');
```
- `counts`: meshes, instances, trees on the GPU and from tinybvh, swaps, GPU batches and build times.
- `memory`: bytes of every buffer, in use and allocated, resident and transient, and the `peak` since creation.
- `meshStatus(mesh)`, `instanceStatus(instance)`, `groupStatus(group)` for one mesh, instance or merged group.
- `timeline`: when every mesh first had a tree, and when every tinybvh tree was in.
`SceneTrees` keeps no CPU copy of its trees. For CPU picking on the same scene, build a [CPU scene](/bvh/cpu-queries/helpers#a-whole-scene) too.
`dispose()` frees its buffers and the worker pool it made.
]]>
{
const mesh = trees.addMesh(geometry);
// static: never moves. Merged at the first update when its mesh has no other instance.
trees.addInstance({ mesh, objectToWorld: matrices[index], static: true });
});
```
## What merges
An instance with `static: true`, whose mesh no other instance uses, with an invertible transform, visible and contributing to GI, added before the first update. Merged instances are grouped by mask; each group becomes one mesh with one identity-transform instance. Everything else stays a normal instance in the same top level.
Meshes used more than once never merge: copying them would cost memory per copy.
## Hits stay exact
On rays with one nearest triangle, `hit.instance` is the source instance, `hit.triangle` the triangle's index in its source mesh, `hit.frontFace` the source's authored side (mirrored sources included), and `hit.material` the source's material. The ids use words the layout already had, so merging adds no memory to the resident scene.
Near-ties are the exception. Merged triangles are stored in world space, so `t` agrees with the instanced scene to rounding, not bit for bit. Where two triangles lie at the same distance, the merged walk may pick the other one, and so another instance. The surface-ray benches measured it: 99.949-99.996% of closest hits named the same instance and triangle (RTX 3060 Laptop, Sponza and Bistro interior).
## Static means static
Since merging is on by default, `static: true` now means "merged" for any instance whose mesh it doesn't share. Before 2026-11-13 it changed nothing unless `mergeStaticInstances` was turned on. Check what you mark:
- `SceneTrees`: moving, hiding, re-masking or removing a merged instance throws.
- `SceneTreesObject3DSync` (`/three`): changes to a merged object (removal, new geometry, draw range, groups or materials) are skipped with one warning per object, and rays keep seeing it as merged.
- `mergeStaticGeometry` (and `buildTraceScene`) throw if two static instances that would merge share an `instanceIndex`: a hit names its source by it.
`mergeStaticInstances: false` keeps every instance an ordinary one.
The source transforms are baked into the merged geometry. In `SceneTrees`, moving, hiding, re-masking or removing a merged instance throws. With `buildTraceScene`, only assembling again notices that a merged source moved; nothing checks between assemblies. Never refit a merged range: its corners are in world space.
## Measured
Merged over instanced, 3 runs of 5 paired rounds each per GPU (the median over runs of each run's paired median; pages `trace-bench-surface-sponza` and `trace-bench-surface-bistro-interior`, rows in `bench/results/trace.csv`):
| Scene | GPU | Surface rays, closest | Surface rays, any | Air grid, closest | Air grid, any |
| --------------- | ------------------------- | --------------------- | ----------------- | ----------------- | ------------- |
| Sponza | RTX 3060 Laptop | 1.67x | 1.48x | 1.44x | 1.24x |
| Sponza | Apple M5 Pro (indicative) | 1.85x (1.83-1.93) | 1.36x (1.33-1.44) | 1.49x | 1.20x |
| Bistro interior | RTX 3060 Laptop | 1.20x | 1.16x | 1.19x | 1.35x |
| Bistro interior | Apple M5 Pro (indicative) | 1.22x (1.21-1.24) | 1.11x (1.10-1.11) | 1.19x | 1.31x |
RTX 3060 Laptop: Windows, headless Chrome 157, 2026-11-13. Apple M5 Pro: Chrome 157, under a bench lock. On the RTX 3060, closest hits named the instanced tree's instance and triangle on 99.949-99.996% of rays, and any hits blocked exactly the same rays. On Sponza, steps per surface ray drop from 113.8 to 70.3, and instance entries from 9.8 to 1.0. The option became the default after the RTX 3060 run.
## Costs
- **Build time.** One big build replaces many small ones, and one build can't spread over the worker pool. tinybvh took 1.53 s for merged Sponza (Node, M5 Pro), against 1.25 s for the per-mesh builds summed (54 ms for the largest). `SceneTrees` builds the merged mesh on the GPU first, like any mesh, and tinybvh's in a worker.
- **CPU memory while it builds.** The merge plan holds world-space positions and indices plus 11 bytes per triangle of source ids: 161.6 MiB on Sponza, until the tree is built.
- **One batch.** A merged Sponza is one GPU batch of 5.7 million triangles, whatever the [build-peak cap](/bvh/builders/fallbacks-and-limits#the-build-peak-cap).
- **Precision.** Merged triangles are stored in world space as f32. At 10 km from the origin the f32 step is about 1 mm. Merge only what sits near the origin, or re-centre the world first.
## Without SceneTrees
`buildTraceScene(meshes, instances, { build })` builds and assembles in one call, merging the instances marked `static` (`mergeStaticInstances: false` turns it off). The lower level is `mergeStaticGeometry(meshes, instances)`, which returns a plan whose groups you build with any builder and pass to `assembleTraceScene(..., { merged: { plan, meshes } })`.
]]>
buildMeshBvhWithTinyBvh(geometry, tiny) });
// Cut every unshared mesh's tree into subtrees of fewer than 64 triangles, each its own top-level leaf.
const clustered = clusterTraceScene(scene, { primitiveLimit: 64 });
console.log(clustered.clusters.records, '->', clustered.clusters.clusterRecords, 'top-level records');
// The same walk, kernels and queries trace it.
const buffers = uploadTraceScene(device, clustered);
```
The result is an ordinary scene. Nothing in the walk changes, so `traceModuleWgsl`, the batch kernels, the CPU walk, the GPU queries and `SdfGenerator` trace it as they are, in every node and triangle format, merged groups included.
## Options
- **`primitiveLimit`** (default 64, as in three-mesh-bvh): the walk down a tree stops at a subtree with fewer triangles than this. Lower gives more, smaller clusters: a deeper top level over shallower trees. `Infinity` splits nothing, and the scene comes back as it was.
- **`split(record)`**: which instance records to cut. The default cuts a record whose mesh no other record uses, as three-mesh-bvh references instanced meshes whole. The callback gets the record's `instanceIndex`, `meshIndex` (or `mergedGroup`), `merged` and `sharedBy` (how many records use its mesh). Instanced meshes can be cut too; their cluster copies are shared by every instance.
- **`topLevel`**: the top level's SAH options.
```ts
const clustered = clusterTraceScene(scene, {
// Instanced meshes too, but not the mesh you refit (its cluster copies would not follow).
split: (record) => record.meshIndex !== characterMesh,
});
```
`meshClusters(scene, nodeOffset, primitiveLimit)` returns one mesh's cut without building anything: each cluster's root, triangle count and object-space box.
## Hits stay exact
Each cluster's record is the instance's own record (transform, instance index, mask, material, flags) pointing at the cluster's subtree, so a hit names the same instance and triangle, with the same side, material and normal, and `t` is the same to the bit. The one difference is which of two triangles at the same distance (or a few ulps apart, where faces meet) is reported, because the walk meets them in another order.
## What it costs
- **Memory:** a 64-byte record and about two top-level nodes per cluster, and a 32-byte frame slot per cluster in a quantized scene. A subtree is copied once, so that the walk can enter it at its root. A mesh tree that only split records use is left out, as three-mesh-bvh uploads only the subtrees its leaves enter, so the mesh's nodes move into the copies rather than being held twice. `clustered.clusters` reports the counts and `addedBytes`.
- **Stack:** a deeper top level over shallower trees. `clusterTraceScene` throws if the trace stack (64 entries) can't hold the result; raise `primitiveLimit` then.
- **Build time:** a CPU pass over the nodes and a CPU top-level build over every cluster.
## Measured
CPU walk, nodes visited per ray (both levels), not time. Sixteen meshes of 4,000 triangles whose boxes overlap, one instance each, quantized nodes, 20,000 random rays:
| Scene | Top-level records | Bytes | Closest hit | Any hit |
| ------------------------------------------ | ----------------- | ------- | ----------- | ------- |
| Instanced (one leaf per mesh) | 16 | 5.07 MB | 271.9 | 139.6 |
| Clustered, `primitiveLimit` 256 | 384 | 5.12 MB | 214.4 | 130.5 |
| Clustered, 64 (default) | 1,515 | 5.27 MB | 185.8 | 120.1 |
| Clustered, 16 | 6,263 | 5.87 MB | 135.4 | 97.7 |
| [Merged static](/bvh/scenes/merged-static) | 1 | 4.84 MB | 53.2 | 48.6 |
GPU timings are not measured yet.
## Clustered or merged?
For instances that never move, [merging](/bvh/scenes/merged-static) does more: one world-space tree over all of them, no top level to walk. Clustering keeps each mesh in its own space, so it also works where merging doesn't: instanced meshes (merging never copies a mesh used twice), instances you will move (cluster again after moving them), and a scene that mixes merged groups with other instances (a merged group is cut like any mesh). It costs no triangle copies.
## Limits
- **Assembled scenes only.** It works on a `TraceSceneData` (`buildTraceScene`, `assembleTraceScene`). `SceneTrees` and its GPU top level have no clustered mode, and neither does the `/three` sync.
- **Static meshes.** A refit does not reach a mesh's cluster copies. A mesh whose own tree was left out has `clustered: true` in `scene.meshes` (its triangles are where they were, so filter flags are written there as before), and `meshRefitPlacement` refuses it. Leave meshes you refit out with `split`.
- **Moving instances:** a clustered scene is a CPU build of the whole top level. After a move, assemble and cluster again.
]]>
pool.build(geometry) });
// SceneTrees makes its own pool unless you hand it one to share.
const trees = await SceneTrees.create(device, { workers: pool });
// A CPU query tree built off the main thread.
const cpuTree = await generateCpuMeshBvh(pool, meshes[0]);
```
## The pool
- **Each worker is single-threaded.** tinybvh's WebAssembly build has no threads, so the pool needs no `SharedArrayBuffer` and no cross-origin isolation, unlike three-mesh-bvh's `ParallelMeshBVHWorker`.
- **Parallel across meshes.** A scene of many meshes spreads over the pool. One big mesh (a merged static group, say) occupies one worker and leaves the rest to the others.
- **Size:** one less than the logical cores, at least 1 and at most 4 (`defaultWorkerPoolSize()`). Workers start when builds need them, so an idle pool costs nothing.
- **Order:** first in, first out. Ask for your biggest meshes first to finish sooner (`SceneTrees` does).
- **A worker gets a build only once it has loaded.** Each worker posts a ready message when its module has run, and the pool sends nothing to it before that. A worker that can't load therefore holds no input, moved or copied.
- **Without `Worker`** (Node, a host that blocks workers), or when a worker can't start or load, the pool builds on the calling thread, one mesh per turn, so callers see the same asynchronous behaviour. Every build still completes, including those with `transferInput` (`SceneTrees` moves its merged groups' geometry). `pool.inlineReason` says why builds run inline. `worker: 'never'` always builds inline; `'always'` throws where there is no `Worker`, and rejects the builds when a worker can't start or load.
- **A worker that dies while building** fails that build only; the next build starts a fresh worker.
```ts
const pool = createBvhWorkerPool({ size: 2, transferInput: false });
const controller = new AbortController();
const pending = pool.build(meshes[0], {}, { signal: controller.signal });
controller.abort(); // rejects at once with an AbortError; a running build finishes in its worker and is dropped
await pending.catch((error: Error) => console.log(error.name));
console.log(pool.stats); // { queued, running, workers, finished }
pool.dispose(); // stops the workers; unfinished builds reject
```
### Per-build events
For a tool that shows when each mesh's build waited, ran and answered: `onBuild` on the pool reports every build `'queued'`, `'started'` (with `inWorker`: on a worker, or inline) and `'finished'` (`outcome`: `'built'`, `'failed'` or `'cancelled'`, with `error`), with the geometry object it was given (to tell meshes apart) and the milliseconds since it was queued. A build cancelled before it started skips `'started'`. One request's `onStart` says only when that build is taken. A listener that throws doesn't stop the pool; its error comes on a later turn. With `SceneTrees`, its own [`onBuild`](/bvh/scenes/scene-trees#build-events) names the mesh handles instead.
```ts
const names = new Map(meshes.map((mesh, index) => [mesh, `mesh ${index}`]));
const pool = createBvhWorkerPool({
// Every build: 'queued', 'started' (on a worker, or inline) and 'finished' (built, failed or cancelled).
onBuild: (event) => console.log(names.get(event.geometry), event.phase, event.inWorker ? 'worker' : 'inline', event.outcome ?? '', `${event.ms.toFixed(1)} ms`),
});
// Or per build: onStart when a worker takes it.
await pool.build(meshes[0], {}, { onStart: () => console.log('mesh 0 is building') });
```
## What moves and what is copied
- **Inputs are copied** into the worker (structured clone), unless `transferInput` is set. Then the caller's arrays are empty afterwards; an array that views only part of its buffer (glTF accessors into one BIN buffer) is copied anyway, so the buffer's other arrays stay usable. `SceneTrees` has the same switch as `transferGeometry`.
- **Results are transferred**, never copied: nodes, triangles, parents and bounds arrive as `ArrayBuffer`s.
- **Each worker keeps a WebAssembly heap**, 64 MiB measured (it held the largest Sponza mesh without growing). A pool of 4 holds 256 MiB of CPU memory for as long as it lives. `pool.dispose()` frees it, and `idleTimeoutMs` (default `Infinity`; 30 s for the pool a `SceneTrees` makes for itself) ends a worker left idle that long, so an idle pool holds nothing (`pool.stats.idleEnded` counts them; inline, the calling thread's tinybvh instance is dropped the same way). The next build starts a fresh worker.
- **Big builds belong here.** A WebAssembly memory can grow but never shrink, and one build grows tinybvh's to about 230 bytes per triangle (Sponza merged into one 5.7M-triangle mesh: 1,349 MiB). A worker whose build left its memory past `recycleAboveBytes` (default 256 MiB, `WORKER_RECYCLE_ABOVE_BYTES`; `Infinity` keeps workers) is ended once it has answered, and the next build starts a fresh one, so the memory goes back to the system at once. `pool.stats.recycled` counts them. On the main thread the builder drops its grown instance too (below), but the memory is only freed when the garbage collector gets to it.
## Other worker builders
- `generateCpuMeshBvh(pool, input, options)` builds a [CPU query tree](/bvh/cpu-queries/raycast) on the pool. In three, `GenerateMeshBvhWorker` does the same for a `BufferGeometry` ([CPU raycast in three](/bvh/three/cpu-raycast#off-the-main-thread)).
- `createMeshBvhBuilder({ worker, transferInput })` is a pool of one worker, with the pool's rules.
- `createTopLevelBuilder()` builds and checks top-level shapes in a worker. `SceneTrees`' GPU top level uses it. It waits for its worker to load in the same way, and works on the calling thread (reported once through `warn`) if the worker can't load.
## Bundlers and dev servers
The pool starts its workers with `new Worker(new URL('./x.js', import.meta.url))`. We checked the built package in a small app with each bundler:
- **Vite and webpack 5** see that line, bundle the two worker files and ship them. Production builds need no setup.
- **esbuild** doesn't: it leaves the URL as written and ships no worker files. Everything still works, but the builds run on the main thread (`pool.usesWorkers` is false, `pool.inlineReason` says why). To get workers, build the two worker files as extra entry points, where the bundle looks for them. For a bundle served from the site's root:
```sh
esbuild src/main.js --bundle --format=esm --outdir=dist \
trace/mesh-bvh-worker=node_modules/@pmndrs/bvh/dist/trace/mesh-bvh-worker.js \
top-level-worker=node_modules/@pmndrs/bvh/dist/trace/top-level-worker.js
```
The bundle looks for `../trace/mesh-bvh-worker.js` and `./top-level-worker.js` relative to itself (at the site's root, `..` stays at the root). These are file paths inside the package, so check them when you upgrade.
Vite's dev server needs two settings:
- **`optimizeDeps: { exclude: ['@pmndrs/bvh'] }`.** In dev, Vite pre-bundles installed dependencies into `node_modules/.vite/deps`, and a pre-bundled copy looks for its workers next to itself, where they don't exist (`node_modules/.vite/trace/mesh-bvh-worker.js`, a 404). Excluding the package serves it as it is. It has no dependencies to pre-bundle.
- **`server.fs.allow`, for a checkout linked from outside the project** (`link:` or `pnpm link`). Vite doesn't pre-bundle a linked package, but it serves files outside the project only when a module imports them. The workers are loaded by URL, not imported, so Vite refuses them (`403 Restricted: outside of Vite serving allow list`). Add the checkout's folder to `server.fs.allow`, next to `searchForWorkspaceRoot(process.cwd())`.
Without them, `worker: 'auto'` builds on the main thread: everything still works, but slower, and `pool.inlineReason` (and `SceneTrees.usesWorkers`, false) shows it. Browsers give no reason for a worker that failed to load, so the message lists these causes.
## GPU builds and workers
A GPU build runs on a device, and a device's buffers can't be shared with another device. So:
1. **On the render device** (the usual case): the trees stay on the GPU with no copy. GPU H-PLOC trees take milliseconds, and the CPU waits only for a few stats words.
2. **In a worker with its own `GPUDevice`:** build there, read the trees back (`readLayouts`), transfer the `ArrayBuffer`s to the main thread, and upload them to the render device. That costs a readback, a transfer and an upload, and the GPU itself is still shared, so it saves no GPU time.
3. **Everything in a worker**, rendering to an `OffscreenCanvas`: one device, no copies, and the main thread is free.
`SceneTrees` uses option 1, and tinybvh on the pool for the swaps. The vanilla `workers-gpu` example runs all three side by side on the same meshes, against tinybvh's pool alone, and reports the time to a first usable scene and to the best trees for each ([Examples](/bvh/examples/examples)).
]]>
=9.35.0 <10.0.0`; tested on 9.35.0). It is **"it works", not polish**: a thin layer that turns Babylon meshes into the core's inputs, picks like `scene.pick`, and binds the core's buffers into a Babylon `ComputeShader`. It has no scene sync, no skinning and no `BvhTraceNodes` equivalent.
| You want | Use | Needs |
| ---------------------------------------------------------- | ---------------------------------------------- | --------------------------------------------------------- |
| Faster `scene.pick` on a big mesh, any engine | `BabylonBvhPicker` | WebAssembly only (the WebGL engine and `NullEngine` work) |
| Babylon meshes as `SceneTrees` or `buildTraceScene` inputs | `bvhSceneFromBabylon` | nothing |
| The `WebGPUEngine`'s `GPUDevice` | `deviceFromEngine` | a `WebGPUEngine` (reads `engine._device`) |
| The WGSL walk in a `ComputeShader` | `createTraceComputeShader`, `bindTraceBuffers` | a `WebGPUEngine` |
The [examples](/bvh/examples/examples#babylonjs) show both halves: `babylon/picking` and `babylon/gpu-trace`.
## The engine's device
Babylon has no public accessor for its `GPUDevice`. `WebGPUEngine` keeps it in `_device`, an underscore field its own declarations mark internal. `deviceFromEngine(engine)` reads it, after checking that the engine is a WebGPU one (`engine.isWebGPU`) and has a device, so a Babylon release that moves the field fails there with a message that says what to check.
```ts
import { WebGPUEngine } from '@babylonjs/core/Engines/webgpuEngine.js';
import { deviceFromEngine } from '@pmndrs/bvh/babylon';
// Babylon asks for WebGPU's default limits and no optional features: ask for the adapter's limits
// (a scene past 128 MiB of triangles needs them) and for its features (the GPU builders need `subgroups`).
const engine = await WebGPUEngine.CreateAsync(canvas, { enableAllFeatures: true, setMaximumLimits: true });
const device = deviceFromEngine(engine); // engine._device, checked; throws on the WebGL engine
```
### Why this is fragile
- **`engine._device` is not API.** Babylon can rename it, wrap it or move it in any release. The peer range stops at the next major, and `pnpm examples:smoke` runs both Babylon examples against the pinned version, but a minor release can still break it. The check in `deviceFromEngine` makes that a clear error, not a crash three calls later.
- **Wrapping a `GPUBuffer` uses another internal.** `ComputeShader.setStorageBuffer` takes a Babylon `DataBuffer`, and on WebGPU a `DataBuffer` is `WebGPUDataBuffer`, whose constructor Babylon exports but marks internal. `gpuBufferToDataBuffer` is the one place that calls it.
- **Babylon's compute path is young.** It resolves bindings by name from a mapping you give it, compiles WGSL through its own preprocessor (below), and decides when its command buffers are submitted.
The walk needs none of Babylon's _rendering_ internals: if `_device` ever goes away, the fallback is to make the device yourself and give Babylon your own ([Sharing a device](/bvh/engines/sharing-a-device)) or to run the walk in compute passes of your own on the engine's device obtained any other way. The CPU picker needs no device at all.
## Scenes
`bvhSceneFromBabylon(scene)` (or a list of meshes) returns what `SceneTrees.addMesh`/`addInstance`, `buildTraceScene` and `CpuSceneBvh` take, plus the Babylon object behind every instance:
- one mesh per geometry, shared by every `Mesh` and `InstancedMesh` that draws it (positions through `getVerticesData`, so strided and normalized buffers work; the whole index buffer, or a plain triangle list);
- one instance per mesh and `InstancedMesh`, with its world matrix (`computeWorldMatrix(true)`): Babylon's matrices are row-vector and their memory is the column-major layout of the same transform, so the 16 floats go in as they are;
- `visible` is `isEnabled() && isVisible`; the instance mask has bit 0 on every instance and bit 1 on pickable ones; `material(mesh)` may give `BvhHit.material`; `static` marks instances for `mergeStaticInstances`.
```ts
import { SceneTrees } from '@pmndrs/bvh';
import { bvhSceneFromBabylon } from '@pmndrs/bvh/babylon';
const read = bvhSceneFromBabylon(scene); // one mesh per geometry, one instance per Mesh and InstancedMesh
const trees = await SceneTrees.create(device);
const meshes = read.meshes.map((geometry) => trees.addMesh(geometry));
for (const instance of read.instances) {
trees.addInstance({
mesh: meshes[instance.meshIndex],
objectToWorld: instance.objectToWorld, // Babylon's world matrix memory is column-major as it is
instanceIndex: instance.instanceIndex, // so a hit's `instance` indexes read.sources
mask: instance.mask,
visible: instance.visible,
});
}
// A hit's instance names the Babylon mesh: read.sources[hit.instance].object
```
There is no sync object: after meshes move, call `trees.setTransform(handle, mesh.computeWorldMatrix(true).m)` for the ones that did (the `babylon/gpu-trace` example does this for a bobbing sphere).
Not read: thin instances, skinned and morphed meshes (rest pose), a mesh's submesh ranges and material groups (the whole index buffer is read), lines and points (`fillMode` other than triangles).
## Picking
`BabylonBvhPicker` holds one tinybvh tree per geometry and a scene-level tree over the instances, and answers with the `PickingInfo` `scene.pick` returns.
```ts
import { BabylonBvhPicker } from '@pmndrs/bvh/babylon';
import type { PickingInfo } from '@babylonjs/core/Collisions/pickingInfo.js';
import type { Scene } from '@babylonjs/core/scene.js';
const picker = await BabylonBvhPicker.create(scene); // loads tinybvh, builds a tree per geometry
const info = picker.pick(scene.pointerX, scene.pointerY); // a PickingInfo, as scene.pick returns
if (info.hit) console.log(info.pickedMesh?.name, info.faceId, info.distance);
// The picker sees the scene as of the last update(): call it after meshes move, show, hide or change.
picker.update();
```
`pickWithRay(ray, options)` is `scene.pickWithRay`; `options` take `predicate` (and `camera` for `pick`). The result has `hit`, `distance` (world units), `pickedPoint`, `pickedMesh` (the `Mesh` or `InstancedMesh`), `bu` and `bv` (the weights of vertices 0 and 1, as Babylon reports them), `faceId`, `subMeshId`, `subMeshFaceId`, `ray`, and a working `getNormal()`. The Node tests check all of it against Babylon's own picking, on random rays, with mirrored and scaled instances and `InstancedMesh`es, on a `NullEngine`.
| | `scene.pick` | `BabylonBvhPicker` |
| -------------------------------- | ----------------------------------------------------------------------- | -------------------------------------------------------------------------------------------------- |
| Cost | every triangle of every candidate mesh, or the submesh octree you built | a tree walk |
| A mesh with no material | picked by its bounding box | always its triangles |
| A moved mesh | seen at once | seen after `update()` (transforms only: no tree is built) |
| Edited vertex data | seen at once | a replaced array gets a new tree at `update()`; an edit in place needs `update({ rebuild: true })` |
| `fastCheck`, `trianglePredicate` | supported | `fastCheck` is accepted and ignored (the closest hit is returned); no `trianglePredicate` |
| Pixel coordinates | canvas pixels (`scene.pointerX`) | the same: with a hardware scaling level, pass canvas pixels |
How much faster depends on the mesh: [Comparison](/bvh/performance/comparison) has Babylon's picking, with and without the submesh octree, against ours on the same rays.
## The walk in a `ComputeShader`
`createTraceComputeShader(name, engine, kernel, options)` makes a Babylon `ComputeShader` whose WGSL is `traceModuleWgsl(options.trace)` followed by your kernel. The walk's three storage buffers are bound by name (`bvhTraceNodes`, `bvhTraceTriangles`, `bvhTraceTopLevel`; an indexed scene's `bvhTracePositions` is the fourth) at group 0, bindings 0-2, and your own resources go after them. `bindTraceBuffers(shader, trees.buffers)` binds `SceneTrees`' own `GPUBuffer`s, with no copy.
```ts
import { Constants } from '@babylonjs/core/Engines/constants.js';
import { StorageBuffer } from '@babylonjs/core/Buffers/storageBuffer.js';
import type { WebGPUEngine as Engine } from '@babylonjs/core/Engines/webgpuEngine.js';
import { bindTraceBuffers, createTraceComputeShader } from '@pmndrs/bvh/babylon';
// The walk (traceModuleWgsl) comes first; the kernel's own bindings follow its three (0-2).
const kernel = `
@group(0) @binding(3) var rays: array;
@group(0) @binding(4) var results: array;
@compute @workgroup_size(64)
fn main(@builtin(global_invocation_id) id: vec3u) {
if (id.x >= arrayLength(&rays)) { return; }
let hit = bvhTraceClosest(rays[id.x]);
results[id.x] = vec2f(hit.t, f32(hit.instance));
}`;
const shader = createTraceComputeShader('bvh trace', engine, kernel, {
trace: { nodeFormat: trees.nodeFormat, triangleLeaves: trees.triangleLeaves, positionLayout: trees.positionLayout },
bindings: { rays: { group: 0, binding: 3 }, results: { group: 0, binding: 4 } },
});
const rays = new StorageBuffer(engine, rayCount * 32, Constants.BUFFER_CREATIONFLAG_READWRITE); // BvhRay is 32 bytes: origin, tMin, direction, tMax
const results = new StorageBuffer(engine, rayCount * 8, Constants.BUFFER_CREATIONFLAG_READWRITE);
shader.setStorageBuffer('rays', rays);
shader.setStorageBuffer('results', results);
// Each frame, after trees.update(encoder) was submitted: bind SceneTrees' own GPUBuffers (no copy) and dispatch.
// Bind again whenever trees.version changes (a buffer grew).
const dispatch = () => {
bindTraceBuffers(shader, trees.buffers);
shader.dispatch(Math.ceil(rayCount / 64));
};
```
Each frame, record `trees.update(encoder)` in your own encoder and submit it before Babylon's frame uses the buffers (Babylon submits its own command buffers at the end of its frame), then bind if `trees.version` changed and dispatch. The `babylon/gpu-trace` example does this in a `scene.onBeforeRenderObservable` step, writes a shadow mask to a storage texture, and blends it over Babylon's render with a `Layer`. The mask comes from `bvhTraceAny` toward the sun, so it has no sampling: the package ends at the hit.
### What went wrong on the way (Babylon 9.35)
These cost time; the helpers handle the first two, and the rest are yours to know.
- **Comments with a semicolon break the shader.** Babylon's WGSL preprocessor splits the source at every `;`, comments included, and the walk's comments have them ("expected ':' for struct member"). `createTraceComputeShader` strips comments (`wgslForBabylon`); do the same if you give `ComputeShader` WGSL yourself.
- **`ComputeShader` needs an engine extension imported.** In a tree-shaken build nothing imports `Engines/WebGPU/Extensions/engine.computeShader.js`, and `new ComputeShader` fails with "engine.createComputeContext is not a function". `/babylon` imports it.
- **Bindings are resolved by the names you map.** The names in `bindingsMapping` are the WGSL variable names. The kernel's bindings are in group 0 after the walk's three; other groups are untested.
- **A foreground `Layer` needs `applyPostProcess = true`** to show a texture over the scene on the `WebGPUEngine`: without it, the scene's meshes disappeared behind the layer in 9.35.
- **Pixel coordinates and hardware scaling.** `scene.createPickingRay` takes canvas pixels, which `engine.setHardwareScalingLevel(n)` divides; a compute pass at the render size must multiply back to compare rays.
- **`InstancedMesh` has to be imported** (`@babylonjs/core/Meshes/instancedMesh.js`) before `createInstance`, in a tree-shaken build.
- **Babylon never frees what it wraps.** A `StorageBuffer` you make is yours to `dispose()`; `SceneTrees`' buffers stay the scene's, so `trees.dispose()` frees them, not Babylon.
## Not supported
- WebGL for the walk: the GPU path needs the `WebGPUEngine`. Picking works on any engine, and the examples run it on the WebGL engine.
- A scene sync (`SceneTreesObject3DSync` has no Babylon twin), skinning and morph targets, thin instances.
- A node-material or `ShaderMaterial` binding of the walk (three's `BvhTraceNodes`): compute passes are what Babylon offers.
]]>
points: array;
@group(1) @binding(1) var shade: array;
@compute @workgroup_size(64)
fn main(@builtin(global_invocation_id) id: vec3u) {
if (id.x >= arrayLength(&shade)) { return; }
let sun = normalize(vec3f(0.3, 1.0, 0.2));
let blocked = bvhTraceAny(BvhRay(points[id.x].xyz, 1e-3, sun, 1e30));
shade[id.x] = select(1.0, 0.0, blocked);
}`;
const sceneLayout = device.createBindGroupLayout({ entries: traceModuleEntries().map((entry, binding) => ({ ...entry, binding })) });
const ioLayout = device.createBindGroupLayout({
entries: [
{ binding: 0, visibility: GPUShaderStage.COMPUTE, buffer: { type: 'read-only-storage' } },
{ binding: 1, visibility: GPUShaderStage.COMPUTE, buffer: { type: 'storage' } },
],
});
const pipeline = await device.createComputePipelineAsync({
layout: device.createPipelineLayout({ bindGroupLayouts: [sceneLayout, ioLayout] }),
compute: { module: device.createShaderModule({ code }), entryPoint: 'main' },
});
// Make the scene's bind group again whenever trees.version changes (a buffer grew).
const { nodes, triangles, topLevel } = trees.buffers;
const sceneGroup = device.createBindGroup({ layout: sceneLayout, entries: [nodes, triangles, topLevel].map((buffer, binding) => ({ binding, resource: { buffer } })) });
const ioGroup = device.createBindGroup({ layout: ioLayout, entries: [{ binding: 0, resource: { buffer: points } }, { binding: 1, resource: { buffer: shade } }] });
const encoder = device.createCommandEncoder();
trees.update(encoder); // before anything traces
const pass = encoder.beginComputePass();
pass.setPipeline(pipeline);
pass.setBindGroup(0, sceneGroup);
pass.setBindGroup(1, ioGroup);
pass.dispatchWorkgroups(Math.ceil(count / 64));
pass.end();
device.queue.submit([encoder.finish()]);
```
## The entry points
```wgsl
struct BvhRay { origin: vec3f, tMin: f32, direction: vec3f, tMax: f32 } // 32 bytes
struct BvhHit { t: f32, instance: u32, triangle: u32, barycentrics: vec2f, frontFace: bool,
material: u32, normal: vec3f }
fn bvhTraceClosest(ray: BvhRay) -> BvhHit
fn bvhTraceAny(ray: BvhRay) -> bool
fn bvhTraceClosestMasked(ray: BvhRay, mask: u32) -> BvhHit // unless rayMasks: false
fn bvhTraceAnyMasked(ray: BvhRay, mask: u32) -> bool // unless rayMasks: false
```
- **Closest hit** returns the nearest hit in `[tMin, tMax]`. `hit.t < 0` is a miss.
- **Any hit** returns at the first triangle hit in `[tMin, tMax]`. Use it for shadows and visibility.
- `hit.instance` is the instance's `instanceIndex`; `hit.triangle` the triangle's original index in its mesh; `hit.barycentrics` the weights of corners 1 and 2 (corner 0 is `1 - u - v`).
- `hit.frontFace` is true when the ray hit the side the mesh was authored as front, through mirrored transforms too. Back-face hits count as hits.
- `hit.normal` is the world-space geometric normal of the authored front side, unit length (0 on a miss).
- `hit.material` is the triangle's material (`triangleMaterials`) when it has one, else the instance's, else `BVH_NO_MATERIAL`.
- Pass a unit-length world direction: `t` is then the distance in world units, through scaled instances too.
```ts
const code = /* wgsl */ `
${traceModuleWgsl()}
fn shadowFrom(p: vec3f, l: vec3f) -> bool {
// Only instances whose mask has bit 0 cast shadows here.
return bvhTraceAnyMasked(BvhRay(p, 1e-3, l, 1e30), 0x1u);
}
fn firstHit(o: vec3f, d: vec3f) -> BvhHit {
let hit = bvhTraceClosest(BvhRay(o, 0.0, d, 1e30)); // all ones: every instance with a non-zero mask
// hit.t < 0: a miss. Else hit.instance, hit.triangle, hit.barycentrics (corners 1 and 2),
// hit.frontFace, hit.material (BVH_NO_MATERIAL for none) and hit.normal (world, geometric).
return hit;
}`;
```
Masks and the filter are on [Masks, the triangle filter and materials](/bvh/concepts/masks-filter-materials).
## Options
| Option | Default | What it does |
| ------------------------------------------------ | ------------------------------------------------------ | ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- |
| `traceSlot` | `{ group: 0, firstBinding: 0 }` | Where the bindings land: nodes, triangles, top level, in order (and positions, for indexed leaves). |
| `triangleFilter` | `DEFAULT_TRIANGLE_FILTER_WGSL` (every triangle blocks) | Your `bvhTrianglePasses`, or `null` to declare it yourself. |
| `rayMasks` | `true` | `false` compiles masks out. |
| `triangleLeaves`, `positionLayout`, `nodeFormat` | records, `vec4`, `'quantized'` | Must match the scene. A scene's defaults are the same, so a scene and a walk made without these options agree. |
| `anyHitOrder` | `'far'` | Which child any hit enters first: `'far'`, `'near'` or `'larger'` (below). |
| `quantizedDecode` | `'exact'` | How quantized nodes become distances: `'exact'` decodes each plane, `'folded'` folds the frame into the ray once per instance (below). Not measured on a GPU yet; quantized nodes only, not with `anyHitOrder: 'larger'`. |
Compile the walk for the scene it reads:
```ts
// Compile the walk for the scene's formats (the defaults: records, vec4 positions, quantized nodes).
const options = { triangleLeaves: trees.triangleLeaves, positionLayout: trees.positionLayout, nodeFormat: trees.nodeFormat };
const walk = traceModuleWgsl({ traceSlot: { group: 0, firstBinding: 0 }, ...options });
const entries = traceModuleEntries(options); // a fourth binding, the positions, for indexed leaves
```
All three buffers are `read-only-storage` in the compute stage; `traceModuleEntries(options)` gives the layout entries without binding numbers. A kernel refuses buffers of the other format.
## The counted walk
`counters: true` adds the walk with step counters, for heat maps and tools that ask why one tree is faster than another: `bvhTraceClosestCounted(ray)` and `bvhTraceAnyCounted(ray)` (and `*Masked(ray, mask)` unless `rayMasks: false`) return a `BvhWalkCounts`: the hit (`t`, `instance`, `triangle`; any hit: `t` 1.0 blocked, -1.0 clear) and the work: `steps` (loop iterations, both levels), `meshNodes` and `topLevelNodes` (inner nodes whose children were tested), `instanceEntries`, `triangleTests` and `instancesWithHit`. `TraceBatchKernel.create(device, { counters: true })` writes one record per ray (`WALK_COUNTS_BYTES`, words in `WALK_COUNTS_WORD`), and `GpuRays.countWalk(rays)` reads them back.
```ts
import { traceModuleWgsl } from '@pmndrs/bvh';
// In your own kernel: the walk with its work counted, compiled in only when asked.
const code = /* wgsl */ `
${traceModuleWgsl({ counters: true })}
@group(1) @binding(0) var heat: array;
@compute @workgroup_size(64)
fn main(@builtin(global_invocation_id) id: vec3u) {
let counts = bvhTraceClosestCounted(BvhRay(vec3f(0.0, 1.0, 5.0), 0.0, vec3f(0.0, 0.0, -1.0), 1e30));
heat[id.x] = counts.steps; // also meshNodes, topLevelNodes, instanceEntries, triangleTests, instancesWithHit
}`;
// Or through GpuRays: the counted kernel over the same source, read back.
const counted = await rays.countWalk(cameraRays);
console.log(`${counted.meanSteps.toFixed(1)} steps per ray, at most ${counted.maxSteps}`, counted.counts(0));
```
The counted functions are cut from the walk's own text with counters inserted at fixed places, as the benches' copy is, so the traversal and the hits are the production walk's (a change to the walk that the insertions no longer fit throws). The default walk is untouched: without the option the module is the same text, and with it the module only gains the counted declarations. Its times mean little (it carries and writes more per ray): time the plain walk.
## How the walk works
- **One loop, one stack per thread** (`array` in private memory) for both levels. Entering an instance pushes a marker, moves the ray into object space and continues with that mesh's root.
- **Both child boxes are tested** with a precomputed inverse direction. Closest hit goes to the nearer child first; any hit goes to the **farther** child first. A shadow ray starts on a surface, so the nearer child is mostly the geometry it starts on. That made any-hit 1.1-2.8x faster on the bench scenes, with the same answers. `anyHitOrder: 'larger'` enters the larger child first instead, for occlusion rays from outside the model or across open space: 1.11-1.48x far-first on instanced trees on the RTX 3060 Laptop, but 0.80-0.87x on merged trees with rays from surfaces (Windows, headless Chrome 157, 2026-11-13, Sponza and Bistro interior).
- **Boxes beyond the current closest hit are skipped.**
- **Quantized nodes** (the default node format) store each child box as 16-bit planes on a per-mesh grid, read from a frame slot when the walk enters an instance. By default each plane is decoded to its exact `f32` (`origin + q * step`) and tested as an `f32` box. `quantizedDecode: 'folded'` folds the frame into the ray at instance entry (`step / direction` and `(origin - rayOrigin) / direction` per axis), so a plane's distance along the ray is one `fma`. The fold rounds its offset, which can move a plane inward by a few ulps of the mesh's size, so every folded box is padded by `|offset| * 2^-21` per axis: it holds the real box and never loses a hit (a few more node visits at worst; a closest hit at exactly the same `t` can name another triangle). It is the ray walk only: the spatial queries and the shapecast keep the exact decode. It is opt-in and not yet timed on a GPU; the surface-ray pages time it (section 9, `folded_over_exact`).
## The stack size
64 entries. The top level and one mesh tree share it: 47 levels are left for a mesh tree (`GPU_TREE_MAX_DEPTH`), and `SceneTrees` refuses deeper trees, and the CPU walk throws a `RangeError` past the stack. tinybvh's trees on real scenes are about 28 deep.
## The watertight test
The triangle test is watertight (Woop, Benthin and Wald 2013), with per-ray shear rows computed once per ray. No ray slips between two triangles that share an edge, on every GPU the [oracle](/bvh/concepts/oracle) runs on. It needs bit-identical shared vertices, which the layout keeps. Building the per-ray rows with `select()` instead of indexing a vector by a per-ray value kept it fast: Sponza closest-hit went from 61 to 101 Mrays/s on the RTX 3060.
## In three.js
`BvhTraceNodes.module` is this walk as a three node: include it in a `wgslFn`, or use the TSL helpers ([BvhTraceNodes](/bvh/three/trace-nodes)).
## See also
- [Ray batches and the CPU walk](/bvh/tracing/batches-and-the-cpu-walk): many rays in one dispatch, without writing a kernel.
- [Spatial queries on the GPU](/bvh/tracing/gpu-queries) and [Signed distance fields](/bvh/tracing/sdf): the walk's other questions.
- [BvhTraceNodes](/bvh/three/trace-nodes): the same walk in three's node system.
- [The oracle rule](/bvh/concepts/oracle): why the walk is trusted.
]]>
({ origin: [i * 0.01, 1, 5], direction: [0, 0, -1], tMin: 0, tMax: 1e30 })));
const closest = await rays.traceClosest(batch);
console.log(`${closest.hits} of ${closest.count} hit, ${closest.gpuMs ?? closest.wallMs} ms`, closest.hit(0));
const shadows = await uploaded.traceAny(batch, { mask: 0x1 });
console.log(`${shadows.blockedCount} blocked`, shadows.blocked(0));
rays.destroy();
```
- **What it compiles:** one batch kernel for the source's formats, read from its buffers (records or indexed, `f32` or quantized nodes). Options: `triangleFilter`, `anyHitOrder`, `label`, and `timestamps` (default true).
- **Results:** `traceClosest` gives `hits`, `hit(i)` (`{ t, instance, triangle, frontFace, barycentrics, material, normal }` or null) and the raw `records`; `traceAny` gives `blockedCount`, `blocked(i)` and the words. Both say `gpuMs` (timestamps, where the device has `timestamp-query`, else null) and `wallMs` (submit to results on the CPU).
- **The walk's work:** `countWalk(rays, { mode })` traces with the [counted walk](/bvh/tracing/wgsl-walk#the-counted-walk) (its own kernel, compiled at the first call) and gives `counts(i)` (the hit, steps, nodes, instance entries, triangle tests), `meanSteps` and `maxSteps`: a heat map's numbers.
- **One trace at a time** per `GpuRays`: calls queue up, and `pending` says one is in flight, so a frame loop can skip a trace rather than build a backlog. `retire()` frees it once the queued traces are done (a page swapping scenes); `destroy()` at once.
- **When it sees the scene:** a `SceneTrees` is traced as of its last submitted `update`; its buffers are read again at each trace, so a scene whose buffers grew is traced in the new ones.
- **Limits:** a readback per trace, so it suits picking, tools and checks, not a renderer's rays (use `TraceBatchKernel` or the WGSL walk in your own kernel and keep the hits on the GPU). Closest-hit records are always the 40-byte ones.
## TraceBatchKernel
For rays you have in a buffer (picking, AO samples, visibility tests), the package has its own kernel: one dispatch for any number of rays, group 0 the scene, group 1 the rays and results. One kernel serves any number of scenes.
```ts
import { HIT_RECORD_BYTES, packRays, RAY_BYTES, TraceBatchKernel } from '@pmndrs/bvh';
const kernel = await TraceBatchKernel.create(device, {
triangleLeaves: trees.triangleLeaves,
positionLayout: trees.positionLayout,
nodeFormat: trees.nodeFormat,
hitNormal: true, // 40-byte records with material and normal; false: 24 bytes
});
const count = 4096;
const rays = device.createBuffer({ size: count * RAY_BYTES, usage: GPUBufferUsage.STORAGE | GPUBufferUsage.COPY_DST });
const results = device.createBuffer({ size: count * HIT_RECORD_BYTES, usage: GPUBufferUsage.STORAGE | GPUBufferUsage.COPY_SRC });
const shadowResults = device.createBuffer({ size: count * 4, usage: GPUBufferUsage.STORAGE | GPUBufferUsage.COPY_SRC });
device.queue.writeBuffer(rays, 0, packRays(Array.from({ length: count }, (_, i) => ({ origin: [i * 0.01, 1, 5], direction: [0, 0, -1], tMin: 0, tMax: 1e30 }))));
const encoder = device.createCommandEncoder();
kernel.encode(encoder, trees.traceBuffers, { mode: 'closest', rays, results, count });
kernel.encode(encoder, trees.traceBuffers, { mode: 'any', rays, results: shadowResults, count, mask: 0x1 }); // one u32 per ray, 1 = blocked
device.queue.submit([encoder.finish()]);
```
- **Rays:** 32 bytes each (`RAY_BYTES`), as `BvhRay`: origin, `tMin`, direction, `tMax`. `packRays` writes them from `{ origin, direction, tMin, tMax }` objects.
- **Closest-hit records** (`hitNormal: true`, the default): 40 bytes (`HIT_RECORD_BYTES`), words in `HIT_RECORD_WORD`: 0 `t`, 1 `instance`, 2 `triangle`, 3 `frontFace` (0 or 1), 4-5 `barycentrics`, 6 `material`, 7-9 `normal`.
- **Compact records** (`hitNormal: false`): 24 bytes (`HIT_RECORD_COMPACT_BYTES`), words 0-5 only.
- **Any-hit results:** one `u32` per ray, 1 when blocked.
- **Masks:** one ray mask per batch (`mask`), a uniform; there is no per-ray mask buffer.
- **Timing:** pass `timestampWrites` to time the dispatch's pass.
- **Counters:** a kernel made with `counters: true` runs the [counted walk](/bvh/tracing/wgsl-walk#the-counted-walk) and writes one `BvhWalkCounts` (`WALK_COUNTS_BYTES`) per ray in either mode.
- **Sizes:** `encode` throws a `RangeError` when `rays` or `results` holds fewer than `count` items.
The 40-byte record is the default: a hit carries its material and normal unless you say otherwise. It has a cost on NVIDIA. Against the 24-byte record, closest-hit rays traced at 0.88-0.92x on Sponza and 0.93-0.94x on Bistro interior on the RTX 3060 Laptop, a 6-12% cost (Windows, headless Chrome 157, 2026-11-13, surface and air rays, instanced and merged trees, the median of three runs of 5 paired rounds). On the Apple M5 it cost nothing measurable: 0.96-1.15x, medians 1.02-1.11 in favour of the bigger record (indicative). Intel has not run it.
So a shadow or occlusion pass that reads neither material nor normal should pass `hitNormal: false`, or trace any-hit rays, which write one word per ray.
`batchKernelWgsl(mode, options)` gives the kernel's WGSL, for a pipeline of your own.
## The CPU walk
`createCpuTracer(scene)` is the WGSL walk, step for step, in TypeScript, over the same buffers (`TraceSceneData`, as `buildTraceScene` or `assembleTraceScene` return it). It runs in Node, so tests cover the walk and the layout without a GPU.
```ts
import { buildMeshBvhWithTinyBvh, buildTraceScene, createCpuTracer, createTinyBvhBuilder, IDENTITY_TRANSFORM } from '@pmndrs/bvh';
const tiny = await createTinyBvhBuilder();
const scene = await buildTraceScene([geometry], [{ meshIndex: 0, instanceIndex: 0, objectToWorld: IDENTITY_TRANSFORM }], {
build: (mesh) => buildMeshBvhWithTinyBvh(mesh, tiny),
});
// The WGSL walk, step for step in TypeScript, over the same buffers.
const tracer = createCpuTracer(scene);
const hit = tracer.closest({ origin: [0, 0, 5], direction: [0, 0, -1], tMin: 0, tMax: 1e30 });
const blocked = tracer.any({ origin: [0, 0, 5], direction: [0, 0, -1], tMin: 0, tMax: 1e30 }, { mask: 0x1 });
```
- `closest(ray, { mask, side, stats })` returns `{ t, instanceIndex, triangleIndex, u, v, frontFace, material, normal }` or null. `any(ray, { mask })` returns a boolean.
- `side` (CPU only: the WGSL walk has no side option) culls front or back faces: `CPU_TRACE_FRONT_SIDE`, `CPU_TRACE_BACK_SIDE`, `CPU_TRACE_DOUBLE_SIDE` (the default, as the GPU walk).
- `stats` (from `newTraceStats()`) counts nodes visited, triangles tested and the deepest stack.
- `createCpuTracer(scene, { triangleFilter, rayMasks })` takes the filter as a TypeScript function.
For queries on one mesh (raycasts with sides, shapecasts, closest points), use [`CpuMeshBvh`](/bvh/cpu-queries/raycast).
## See also
- [Tracing in WGSL](/bvh/tracing/wgsl-walk): the walk these batches call, in your own kernel.
- [The oracle rule](/bvh/concepts/oracle): the CPU walk as one of three tracers that must agree.
- [Builds and tracing](/bvh/performance/builds-and-tracing): ray rates, and how they were measured.
]]>
data.set([...point, 1e30], i * 4));
const queries = device.createBuffer({ size: count * POINT_QUERY_BYTES, usage: GPUBufferUsage.STORAGE | GPUBufferUsage.COPY_DST });
const results = device.createBuffer({ size: count * CLOSEST_POINT_RECORD_BYTES, usage: GPUBufferUsage.STORAGE | GPUBufferUsage.COPY_SRC });
device.queue.writeBuffer(queries, 0, data);
const encoder = device.createCommandEncoder();
kernel.encode(encoder, trees.traceBuffers, { queries, results, count, mask: 0xff });
device.queue.submit([encoder.finish()]);
// 48-byte records, words in CLOSEST_POINT_RECORD_WORD: distance (negative: nothing within maxDistance),
// instance, triangle, material, barycentrics, point (world) and normal (the triangle's authored front side).
```
- **Queries:** 16 bytes each (`POINT_QUERY_BYTES`): the point in world space, then `maxDistance`. Larger distances (and infinity) are clamped to `CLOSEST_POINT_MAX_DISTANCE` (1e18).
- **Records:** 48 bytes (`CLOSEST_POINT_RECORD_BYTES`), words in `CLOSEST_POINT_RECORD_WORD`: 0 `distance`, 1 `instance`, 2 `triangle`, 3 `material`, 4-5 `barycentrics`, 6-8 `point`, 9-11 `normal`. A miss has `distance` -1 and `material` `NO_MATERIAL`.
- **Masks:** one instance mask per batch, as for rays; `rayMasks: false` compiles masks out.
- The kernel refuses a scene whose formats differ from the ones it was made for, and a queries or results buffer too small for `count`. `closestPointKernelWgsl(options)` gives its WGSL, for a pipeline of your own.
## In your own kernel
`traceModuleWgsl({ queries: true })` adds the queries to the module:
```ts
const code = /* wgsl */ `
${traceModuleWgsl({ queries: true })}
fn nearestSurface(p: vec3f) -> vec3f {
let hit = bvhClosestPoint(p, 10.0); // world space; hit.distance < 0: nothing within 10
return select(p, hit.point, hit.distance >= 0.0);
}
fn overlaps(p: vec3f, axes: mat3x3f) -> bool {
return bvhIntersectsSphere(p, 0.5)
|| bvhIntersectsBox(p - vec3f(1.0), p + vec3f(1.0))
|| bvhIntersectsOrientedBox(p, vec3f(2.0, 0.5, 0.5), axes); // axes: orthonormal columns
}`;
```
```wgsl
struct BvhClosestHit { distance: f32, instance: u32, triangle: u32, material: u32,
barycentrics: vec2f, point: vec3f, normal: vec3f }
fn bvhClosestPoint(point: vec3f, maxDistance: f32) -> BvhClosestHit
fn bvhIntersectsSphere(center: vec3f, radius: f32) -> bool
fn bvhIntersectsBox(boxMin: vec3f, boxMax: vec3f) -> bool
fn bvhIntersectsOrientedBox(center: vec3f, halfSize: vec3f, rotation: mat3x3f) -> bool
// and bvhClosestPointMasked(point, maxDistance, mask), bvhIntersectsSphereMasked(..., mask), ... unless rayMasks: false
```
- Everything is in **world space**, through scaled, rotated and mirrored instances: distances are world distances, and a sphere stays a sphere. (A ray can be moved into an instance's space because `t` survives any affine map; a distance doesn't, so queries move the scene to the query instead.)
- `bvhClosestPoint` counts only triangles strictly nearer than `maxDistance`. Of triangles at the same distance it returns one; which one is not specified. `instance`, `triangle`, `material` and `barycentrics` mean what they mean in `BvhHit`, merged scenes included; `normal` is the triangle's authored front side in world space.
- Touching counts as intersecting in the sphere and box tests. `bvhIntersectsOrientedBox` takes the box's axes as the columns of `rotation`; fold a scale into `halfSize`.
- The triangle filter is not asked: every triangle counts. Instances with mask 0 are left out, as for rays; with `rayMasks: false` masks are compiled out and every instance counts, mask 0 included.
- `maxDistance` of 0 or less finds nothing; infinity is clamped to 1e18 and finds the nearest point.
- Degenerate triangles (segments, points) and slivers thinner than about 1:3000 are measured to their three edges: three's region arithmetic cancels in f32 there. A sliver's answer is off by at most its own height.
- They are `CpuMeshBvh`'s `closestPointToPoint`, `intersectsSphere` and `intersectsBox` on the GPU, and the `query-oracle` GPU page checks them against those (below).
## Your own shapecast
`traceModuleWgsl({ shapecast })` compiles the same walk around three functions you write, and adds `bvhShapecast()` (`bvhShapecastMasked(mask)` with ray masks), which returns true when your triangle test stopped it:
```ts
// Count the triangles within a radius of a point: the caller's three hooks, compiled into the walk.
const shapecast = /* wgsl */ `
var queryCenter: vec3f;
var queryRadiusSq: f32;
var touched: u32;
fn bvhShapecastBounds(bounds: BvhShapecastBounds) -> f32 {
let distanceSq = bvhPointBoxDistanceSq(queryCenter, bounds.min, bounds.max);
return select(-1.0, distanceSq, distanceSq <= queryRadiusSq); // < 0 skips the box; else the lower goes first
}
fn bvhShapecastKeep(score: f32) -> bool {
return true; // asked when a pushed box is popped, with its score: false skips it
}
fn bvhShapecastTriangle(triangle: BvhShapecastTriangle) -> bool {
let offset = bvhClosestPointToTriangle(queryCenter, triangle.a, triangle.b, triangle.c).point - queryCenter;
if (dot(offset, offset) <= queryRadiusSq) {
touched += 1u; // triangle.instance and triangle.triangle name it; its corners are in world space
}
return false; // true stops the cast
}`;
const code = /* wgsl */ `
${traceModuleWgsl({ shapecast })}
fn countNear(p: vec3f, radius: f32) -> u32 {
queryCenter = p;
queryRadiusSq = radius * radius;
touched = 0u;
_ = bvhShapecast();
return touched;
}`;
```
- `bvhShapecastBounds(bounds)` scores a box (world space): negative skips it; of two children the lower score is entered first and the other pushed with its score. three-mesh-bvh's `intersectsBounds` and `boundsTraverseOrder` in one.
- `bvhShapecastKeep(score)` is asked when a pushed box comes off the stack. Return `score < best` to cull by a distance that has shrunk since the box was pushed, as `bvhClosestPoint` does; return true otherwise.
- `bvhShapecastTriangle(triangle)` gets each triangle of an entered leaf: corners `a`, `b`, `c` in world space, `instance` and `triangle` as in `BvhHit`, `mirrored` (the world winding is the reverse of the authored one), and `record` and `slot` for `bvhShapecastMaterial(triangle)` and `bvhShapecastNormal(triangle)`.
- Mesh boxes reach your hook as the world box around the instance's moved box, grown by `QUERY_BOX_PADDING` (1e-6) of the sizes of the terms the f32 transform adds (the moved centre's terms, the translation and the half size), so the corners the walk hands to your triangle hook lie inside, also for an instance far from the origin whose geometry is offset back near it. They are a little larger than the exact world boxes.
- WGSL has no closures, so hooks keep their state in `var` variables. Pass `shapecast: ''` to declare the hooks in your kernel instead.
- `bvhShapecastTriangle` may call the module's other walks (`bvhTraceAny`, `bvhClosestPoint`, `bvhIntersects*`): the shapecast re-reads its instance's quantized node frame after each leaf, which a nested walk overwrites. `bvhShapecastBounds` and `bvhShapecastKeep` must not call a walk (a node is decoded right after them), and neither may the ray walk's triangle filter, `bvhTrianglePasses`.
- The library's queries are shapecasts of their own, so `queries` and `shapecast` can be used together.
## Triangle helpers
The walk's watertight ray-triangle test and a closest point on one triangle are in every trace module, and alone, with no bindings, in `triangleGeometryWgsl()`:
```ts
import { triangleGeometryWgsl } from '@pmndrs/bvh';
// The walk's watertight test and the closest point on one triangle, with no scene and no bindings.
const code = /* wgsl */ `
${triangleGeometryWgsl()}
fn pick(ray: BvhRay, a: vec3f, b: vec3f, c: vec3f) -> f32 {
let hit = bvhIntersectRayTriangle(ray, a, b, c); // hit.hit, hit.t, hit.barycentrics, hit.frontFacing
return select(-1.0, hit.t, hit.hit);
}
fn snap(p: vec3f, a: vec3f, b: vec3f, c: vec3f) -> vec3f {
return bvhClosestPointToTriangle(p, a, b, c).point; // .barycentrics: the weights of b and c
}`;
```
`bvhIntersectRayTriangle` is the walk's own test (`bvhMakeRaySetup` and `bvhIntersectWatertight`), not a copy: a ray through an edge two triangles share hits one of them. `bvhClosestPointToTriangle` is three's `Triangle.closestPointToPoint`, except that segments, points and slivers are measured to their edges. Use one or the other text in a kernel, never both: the trace module already contains it.
## /three
`new BvhTraceNodes(renderer, trees, { queries: true })` puts the queries in `bvh.module` (call them by name from a `wgslFn`), and `bvh.closestPoint(point, maxDistance)` returns a `BvhClosestPointHit` struct node (`.get('distance')`, `'instance'`, `'triangle'`, `'material'`, `'barycentrics'`, `'point'`, `'normal'`); `closestPointMasked` takes a mask. `bvh.getShapecastFn({ shape, intersectsBounds, intersectsTriangle, keep })` compiles a shapecast whose hooks are TSL `Fn`s or `wgslFn`s, three-mesh-bvh's `getShapecastFn` ([Shapecasts with TSL hooks](/bvh/three/trace-nodes#shapecasts-with-tsl-hooks)).
## How they are checked
The `query-oracle` GPU page runs the queries on the oracle's scenes (thin walls, instancing, mirrored and non-uniformly scaled boxes, random soups under random rotations, scales and mirrors, 200 instances, a 30,000-triangle mesh), plus instances 1000-1500 from the origin with their geometry offset back near it, degenerate triangles, and a mask-0 instance, in `f32` and quantized nodes, records and indexed leaves, instanced and merged, with masks on and off and per-triangle materials, and compares with `CpuMeshBvh` built over each instance in world space. A tie (another triangle at the same distance, within the tolerance) agrees; a shape within the tolerance of touching is not counted. It also checks nesting (a shapecast hook tracing `bvhTraceAny` per triangle, against the CPU walk) and the box padding (every corner as the walk moves it, queried at radius 0, must be found with culling as without). On the Apple M5 every query agrees. The `three-trace` page checks that `closestPoint` gives exactly the batch kernel's records.
## Not here
- Signed distance fields and the inside test (`bvhRayCrossings`, `bvhInsideVotes`, `bvhIsInside`, also in this module): see [Signed distance fields](/bvh/tracing/sdf).
- Closest point between two meshes (`closestPointToGeometry`) and `bvhcast` exist on the CPU only.
## See also
- [Closest point](/bvh/cpu-queries/closest-point) and [Shapecast and bvhcast](/bvh/cpu-queries/shapecast): the same queries on the CPU.
- [Signed distance fields](/bvh/tracing/sdf): built on the closest-point query and an inside test.
- [Masks, the triangle filter and materials](/bvh/concepts/masks-filter-materials): which instances and triangles a query sees.
]]>
BvhRayCrossings
fn bvhInsideVotes(point: vec3f) -> vec2u
fn bvhIsInside(point: vec3f) -> bool
```
with `*Masked` forms (a last `mask: u32`) unless `rayMasks: false`.
- `bvhRayCrossings` walks every triangle a ray crosses (`t >= 0`), with the walk's own watertight triangle test, and returns how many there were and their signed sum: +1 for a triangle the ray leaves through its front side, -1 for one it enters through it.
- `bvhInsideVotes` casts three fixed rays (`INSIDE_TEST_DIRECTIONS`: along no axis or diagonal, into three different octants) and counts how many vote inside: `.x` by **parity** (an odd number of crossings), `.y` by **winding** (a signed sum other than 0). Two or three votes is inside.
- `bvhIsInside` is the parity vote.
```ts
// A signed distance in your own kernel: the closest point, negated where the inside test says inside.
const code = /* wgsl */ `
${traceModuleWgsl({ queries: true })}
fn signedDistance(p: vec3f) -> f32 {
let hit = bvhClosestPoint(p, 1e30);
return select(hit.distance, -hit.distance, bvhIsInside(p));
}
fn insideByWinding(p: vec3f) -> bool {
return bvhInsideVotes(p).y >= 2u; // .x: rays voting inside by parity, .y: by winding (of 3)
}`;
```
### Why ray parity with a vote
The other common choice is the generalized winding number (Jacobson et al. 2013): the sum of the solid angles every triangle subtends at the point. It degrades gracefully on open meshes, but exactly it costs one term per triangle per voxel; the fast form needs a tree of dipole moments per node (Barill et al. 2018), which our nodes don't store. A ray cast walks the tree we already have, with the walk's watertight test, so on a closed mesh a ray can't slip between two triangles that share an edge, and the answer is exact away from the surface. A ray exactly through an edge counts both triangles (the walk's rule); casting three rays in different directions and taking the majority outvotes that ray.
Parity and winding differ where shells overlap or nest:
| Geometry | `'parity'` | `'winding'` |
| ------------------------------------------------------ | --------------------------------------------------------------------- | ---------------------------- |
| One closed mesh, either winding | right | right |
| Two closed meshes that overlap | the overlap is outside (two crossings) | right (winding 2) |
| A hollow: an outer shell and an inner one wound inward | right | right |
| Triangles wound inconsistently | right | wrong where the signs cancel |
| A mesh with a hole or a missing face | each ray that leaves through the hole votes outside; the vote decides | the same |
### Meshes that aren't watertight
A gap, a missing face or a crack between two vertices that should be one makes some rays pass through, and each such ray votes "outside". With three rays in different octants, a point is still found inside unless two of the three leave through openings: a box without its top keeps its middle inside. A mesh open on a large part of its surface (a terrain patch, a plane, a cloth) has no inside; use `sign: 'unsigned'`. Seams are the common trap: three's built-in geometries repeat their vertices along UV seams, and two copies that round apart leave a crack. Weld positions first (`mergeVertices` from three's `BufferGeometryUtils`, after deleting the other attributes), as the `three/sdf` example does.
### Cost
A signed voxel walks the tree four times: once for the closest point, which prunes by distance, and three times along rays that can't stop early (every crossing counts). An unsigned voxel walks it once. Points far from everything are cheap with `maxDistance`; the rays are not limited by it.
## On the CPU
`CpuMeshBvh` has the same test (`rayCrossings`, `insideVotes`, `isPointInside`), the same rays and the same watertight walk in doubles, and `generateSdfCpu` fills a grid voxel for voxel at the GPU's points: the reference the GPU is checked against, and a field where there is no GPU. Several trees count as one scene (`insideVotesOf` adds their crossings up).
```ts
import { CpuMeshBvh, generateSdfCpu } from '@pmndrs/bvh';
const tree = await CpuMeshBvh.create(geometry); // world-space positions
const inside = tree.isPointInside([0, 0, 0]); // or isPointInside(point, 'winding'), or insideVotes(point)
// The same field on the CPU, voxel for voxel the GPU's points: a reference, or a field with no GPU.
const field = generateSdfCpu(tree, { min: [-2, -2, -2], max: [2, 2, 2], resolution: 9 });
const center = field[(4 * 9 + 4) * 9 + 4]; // voxel (4, 4, 4) is the box's centre
```
## In three
`generateSdfTexture` from `@pmndrs/bvh/three` fills a three `Storage3DTexture` on the renderer's device from a `SceneTrees` (or `{ buffers: uploadTraceScene(...) }`), and gives TSL helpers to read it:
```ts
import { generateSdfTexture } from '@pmndrs/bvh/three';
import { positionWorld, vec3 } from 'three/tsl';
import type { MeshBasicNodeMaterial, WebGPURenderer as Renderer } from 'three/webgpu';
const box = new Box3().setFromObject(object).expandByScalar(0.1);
const sdf = await generateSdfTexture(renderer, trees, { box, resolution: 64 }); // the trees after their update
// sdf.texture is a three Storage3DTexture (r32float); sdf.sample(p) reads it at a world position in TSL.
material.colorNode = sdf.sample(positionWorld).lessThan(0).select(vec3(0.3, 0.5, 1), vec3(1, 0.6, 0.3));
// After the scene moved, fill the same texture again: generateSdfTexture(renderer, trees, { box, resolution: 64, texture: sdf.texture }).
```
The result also has `uvw(p)` (the texture coordinate of a world position, for `texture3D`), `gpuTexture` and `grid` (for `readSdf` or your own WebGPU passes), `box`, `resolution` and `ms`. three makes and owns the texture; the generator only writes into it. Don't set its `needsUpdate` afterwards: three would make a new, empty one. The texture filters linearly where the device has `float32-filterable`, else nearest.
The [`three/sdf`](https://github.com/pmndrs/bvh/tree/main/examples/three/sdf) example raymarches the field and shows a slice with contours; [`compare/sdf`](https://github.com/pmndrs/bvh/tree/main/examples/compare/sdf) times it against three-mesh-bvh's `webgpu_sdfGeneration` kernel.
## Limits
- **Formats:** `r32float` textures and `f32` buffers. `r16float` isn't a storage format in core WebGPU; write a buffer and convert it in a pass of your own if you need half floats.
- **Memory:** a 128³ field is 8 MiB, 256³ is 64 MiB; a 3D texture's side is limited by `maxTextureDimension3D` (2048 by default).
- **The sign near the surface:** within rounding of a triangle, the closest point is still right but the sign may go either way; a voxel that small a distance from the surface reads as about zero anyway.
- **Static:** a field is a snapshot. After the scene moves, generate it again (into the same texture or buffer).
- **The box:** voxels outside the scene's reach still get a value (the distance to the nearest triangle, however far, up to `maxDistance`); a clamp-to-edge sampler (the three helper's) repeats the edge outside the box.
## Correctness
`tests/gpu/pages/sdf-oracle` compares the GPU field with `generateSdfCpu` voxel for voxel: welded solids, overlapping and hollow shells under rotations, non-uniform scales and a mirror, a box without its top and a triangle soup; every node and triangle format, merged trees, masks on and off, a distance band and unsigned fields. Distances must agree to 4e-6 of the scene's size (plus the point's distance from the origin), and signs everywhere farther than 1e-5 of the size from the surface (on the open scene, at most 0.2% of voxels may differ). The texture and buffer outputs must match bit for bit.
## See also
- [Spatial queries on the GPU](/bvh/tracing/gpu-queries): the closest-point query the field is made of.
- [Closest point](/bvh/cpu-queries/closest-point): the same query on the CPU.
]]>
sphereIntersectsBox(sphere, box), // false skips the box
intersectsTriangle: (triangle, triangleIndex) => {
if (sphereIntersectsTriangle(sphere, triangle)) touched.push(triangleIndex); // the original index
return false; // true stops the cast
},
});
const any = tree.intersectsSphere(sphere); // the same test as one call
```
- `intersectsBounds(box, isLeaf, score, depth, nodeIndex)` decides whether the walk enters a box: falsy skips it, `BVH_CONTAINED` takes its whole subtree as contained, anything else truthy (`BVH_INTERSECTED`, `true`) enters it. The root's box is never asked about; the first boxes asked are its children, at depth 1.
- `intersectsTriangle(triangle, triangleIndex, contained, depth)` gets each triangle of an entered leaf or contained box, as a scratch `ExtendedTriangle`, with its **original** index. A truthy return stops the cast.
- `intersectsRange(offset, count, contained, depth, nodeIndex, box)` gets a range of tree positions first; a truthy return stops the cast. With neither callback, the cast stops at the first contained box.
- `boundsTraverseOrder(box)` scores boxes; of two siblings the lower score is visited first.
- Casts may nest.
`traverse(callbacks)` is the raw box walk underneath, with boxes as `Float32Array(6)` and tree-position ranges.
## Boxes and spheres
```ts
import { OrientedBox } from '@pmndrs/bvh';
const box = { min: { x: -1, y: -1, z: -1 }, max: { x: 1, y: 1, z: 1 } };
const rotated = [0.7071, 0.7071, 0, 0, -0.7071, 0.7071, 0, 0, 0, 0, 1, 0, 0, 0.5, 0, 1]; // box to mesh, column-major
const inside = tree.intersectsBox(box, rotated);
// The oriented box and the triangle class have three-mesh-bvh's methods, over plain points.
const obb = new OrientedBox();
obb.min.x = obb.min.y = obb.min.z = -1;
obb.max.x = obb.max.y = obb.max.z = 1;
obb.needsUpdate = true;
console.log(obb.distanceToPoint({ x: 3, y: 0, z: 0 }));
```
- `intersectsBox(box, boxToMesh)`: an oriented box test (`boxToMesh` may be left out).
- `intersectsSphere(sphere)`: `{ center, radius }`.
- `intersectsGeometry(other, geometryToBvh)`: another tree (a `bvhcast`), or `{ positions, indices }`.
The shape classes (`ExtendedTriangle`, `OrientedBox`, `SeparatingAxisBounds`) and their math (`triangleIntersectsTriangle`, `closestPointsSegmentToSegment`, `sphereIntersectsBox`, ...) are three-mesh-bvh's, ported operation for operation over plain `{ x, y, z }` points. They give its results bit for bit (4,000 random triangle pairs with coplanar and degenerate cases, 3,000 oriented-box cases, in the unit tests).
## Bvhcast
One tree against another, three-mesh-bvh's walk step for step:
```ts
let pairs = 0;
tree.bvhcast(other, otherToTree, {
// Tree positions in each tree (three-mesh-bvh's indirect mode): map them with resolveTriangleIndex.
intersectsTriangles: (triangle1, triangle2, i1, i2) => {
if (triangle1.intersectsTriangle(triangle2)) {
pairs++;
console.log(tree.resolveTriangleIndex(i1), other.resolveTriangleIndex(i2));
}
return false;
},
});
const touching = tree.intersectsGeometry(other, otherToTree); // a bvhcast that stops at the first pair
```
- `intersectsTriangles(triangle1, triangle2, i1, i2, depth1, nodeIndex1, depth2, nodeIndex2)` gets every pair of triangles of two overlapping leaves, the other's moved into this tree's space, with **tree positions** (as in three-mesh-bvh's indirect mode). Map them with each tree's `resolveTriangleIndex`.
- `intersectsRanges(...)` gets the overlapping leaves first.
- Unlike three-mesh-bvh, casts may nest, and a cast with neither callback throws.
## Agreement and speed
Two callers' patterns against three-mesh-bvh 0.9.18 (`bench/query-parity.ts`, Node 22 on the Apple M5, a furnished room of 269,764 triangles, 2,000 capsules and 100 brush placements, means of 3 rounds; indicative):
| Pattern | Agreement | Ours | three-mesh-bvh |
| ---------------------------------------------------------------------------------------------------- | --------------------------------------------------------------- | --------------------- | -------------- |
| A character controller (two capsule shapecasts per step) | 2,000 of 2,000 capsules: the same 4.9 million contact triangles | 1.71 ms per capsule | 1.84 ms |
| three-bvh-csg's `collectIntersectingTriangles` (bvhcast, room against a 3,380-triangle sphere brush) | 100 of 100 placements: the same 21,160 pairs | 1.51 ms per placement | 1.61 ms |
## See also
- [Closest point](/bvh/cpu-queries/closest-point): the nearest point on a mesh, which a shapecast can also find.
- [Spatial queries on the GPU](/bvh/tracing/gpu-queries): your own shapecast in WGSL.
- [Coming from three-mesh-bvh](/bvh/three/coming-from-three-mesh-bvh): what matches three-mesh-bvh's shapecast and what differs.
]]>
buildMeshBvhWithTinyBvh(mesh, tiny));
const hits = picker.raycast({ origin: [0, 1, 5], direction: [0, 0, -1], tMin: 0, tMax: 1e30 }, { firstHitOnly: true, mask: 0x1 });
// Frustum culling over the top level: planes as [a, b, c, d] with a*x + b*y + c*z + d >= 0 inside.
const visible = picker.intersectsFrustum([0, 0, -1, 10, 0, 0, 1, 10]);
picker.setInstances(instances); // moved instances: rebuilds the top level only
```
- `raycast(ray, { firstHitOnly, mask, accept })` returns `{ instance, triangle, t, u, v, frontFace, ... }` per hit, sorted. `accept(instance, triangle, frontFace)` decides whether a hit counts (side culling, groups).
- `intersectsFrustum(planes, { mask })` and `intersectsBox(box, { mask })` walk the top level and return the instances whose world box meets the shape. A subtree outside a plane is skipped; one inside every plane is taken whole.
- `setInstances(instances)` takes new transforms, visibility, masks or materials, and rebuilds only the top level.
`SceneTrees` keeps its trees on the GPU only, so a CPU scene is built from the same meshes separately. In three, `BvhSceneRaycaster` does it from the scene graph ([CPU raycast in three](/bvh/three/cpu-raycast#a-whole-scene)).
## Debug helpers
```ts
import { bvhHelperIndices, bvhHelperPositions, estimateMemoryInBytes, getBVHExtremes, validateBounds } from '@pmndrs/bvh';
console.log(getBVHExtremes(tree)); // [{ nodeCount, leafNodeCount, depth, primitives, splits, surfaceAreaScore }]
console.log(validateBounds(tree)); // every box holds its triangles (reads the source geometry)
console.log(estimateMemoryInBytes(tree)); // the tree's own bytes, not the geometry's
// The boxes down to depth 10 as line segments, for any engine to draw.
const positions = bvhHelperPositions(tree, 10, false);
const indices = bvhHelperIndices(positions, true);
```
- `getBVHExtremes(tree)`: three-mesh-bvh's `ExtremeInfo`, one entry for our one root. The split axis isn't stored in the layout, so `splits` counts the axis the children's centres lie furthest apart on.
- `validateBounds(tree)`: three-mesh-bvh's checks and `console.assert` messages, reading the source geometry, so edits without `refit()` fail.
- `estimateMemoryInBytes(tree)`: the tree's layout, its lookups and top level, not the geometry.
- `bvhHelperPositions(tree, depth, displayParents)` and `bvhHelperIndices(positions, edges)`: the boxes as line segments (or faces), for any engine to draw. three's `MeshBVHHelper` uses them.
- `checkGpuLayout` and `treeSahCost` check and score any tree ([The builder contract](/bvh/concepts/builder-contract#the-rule)).
- `getJSONStructure(tree)`: three-mesh-bvh's plain-object tree, for looking at or logging a tree's shape. Each node has `bounds` and either `offset` and `count` (a leaf; tree positions, as `traverse` reports them) or `left` and `right`. The root's box is the tree's bounds. Boxes are `BvhBox3`s here and three `Box3`s from `@pmndrs/bvh/three`; pass `makeBox` for another type. A tree written in three-mesh-bvh's format gives the same structure from its `getJSONStructure`, node for node.
```ts
import { getJSONStructure, type CpuMeshBvh } from '@pmndrs/bvh';
import { getJSONStructure as getJSONStructureThree } from '@pmndrs/bvh/three';
const root = getJSONStructure(tree); // { bounds: BvhBox3, left, right }, or { bounds, offset, count } at a leaf
console.log(JSON.stringify(root, null, 2));
// In three, the boxes are Box3s:
const threeRoot = getJSONStructureThree(geometry.boundsTree!);
```
]]>
box.min.y < 0.5, // false skips the box
intersectsLine: (line, index) => {
if (line.start.y < 0.5 && line.end.y < 0.5) below.push(index); // the segment's first entry
return false; // true stops the cast
},
});
```
## The input
Points and lines come as three draws them: `positions` (`x, y, z` per vertex, `Float32Array`), an optional `indices`, and a range of entries (`start`, `count`, like a draw range; default all). An **entry** is a position in `indices`, or a vertex without them. A point is one entry. A segment starts at an entry and ends at the next:
| `mode` | three object | Segments |
| ---------------------- | -------------- | ------------------------------------------------ |
| `'segments'` (default) | `LineSegments` | entries 0-1, 2-3, ... |
| `'strip'` | `Line` | 0-1, 1-2, ..., to the last entry |
| `'loop'` | `LineLoop` | the strip, then the last entry back to the first |
A hit's `index` is the point's entry, or the segment's first entry (three's `index` for lines; for points three reports the entry's vertex, `indices[index]`). The positions are copied into the tree as `f32`, so moving them later needs `refit()`.
## Queries
- `raycast(ray, { threshold, near, far, accept })` returns every primitive within `threshold` of the ray, nearest first (then by entry). It is three's test, computed with three's `Ray` operations in three's order: a point counts when strictly closer than `threshold`, a segment when no farther. `distance` runs from the ray's origin to `pointOnRay`; `distanceToRay` is the gap between the ray and the primitive. The default threshold is 1, three's. A direction that isn't unit length is normalized first. `accept(hit)` can drop hits (a draw range, a distance in another space).
- `raycastFirst(ray, options)` returns the closest hit (the lower entry on a tie), or null. Boxes beyond the closest hit so far are skipped, as in three-mesh-bvh's `firstHitOnly`.
- `closestPointToPoint(point, target, minThreshold, maxThreshold)` returns `{ point, distance, index }` (a point on a segment, clamped to its ends), or null when nothing is within `maxThreshold`. It stops at the first one within `minThreshold`.
- `shapecast({ intersectsBounds, intersectsPoint | intersectsLine, intersectsRange, boundsTraverseOrder })` has [`CpuMeshBvh.shapecast`'s](/bvh/cpu-queries/shapecast) contract, with each point or segment handed over as a scratch object, with its entry.
- `traverse`, `traverseNodes`, `getBoundingBox`, `resolvePrimitiveIndex`, `getPoint` / `getSegment`, `refit(input)`, `serialize()` and `CpuPointsBvh.deserialize(bytes)` / `CpuSegmentsBvh.deserialize(bytes)` (checked: a corrupt file throws). `getBVHExtremes`, `validateBounds` and `bvhHelperPositions` take these trees too.
## The tree and its limits
- **The builder is a centre split** (three-mesh-bvh's default `CENTER`), in TypeScript: the longest axis of the primitives' centres is cut at its middle, with a median cut when that leaves a side empty or past depth 40. It runs on the calling thread; a million points take about a second, as long as three-mesh-bvh's `PointsBVH`. tinybvh isn't used: it builds over triangles, and points given to it as flat triangles come out with one node per point.
- **Nodes are the GPU layout's** 64-byte two-child nodes, leaves of up to 8 primitives. A point record is 16 bytes, a segment 32: about 27 bytes per point and 43 per segment with the nodes.
- **CPU only.** The GPU walk and `SceneTrees` take triangles; there are no point or segment leaves on the GPU. They are not built because no consumer has asked, and the reasons and a design are in [`docs/internals/design/points-and-lines.md`](https://github.com/pmndrs/bvh/blob/main/docs/internals/design/points-and-lines.md).
- An empty input builds an empty tree, which every query answers with nothing.
]]>
deserializeLayout(await (await fetch(url)).arrayBuffer())));
const scene = assembleTraceScene(trees, instances); // instances name their tree by meshIndex
const buffers = uploadTraceScene(device, scene); // nodes, triangles, topLevel: bind them to the walk
```
A loaded tree is a `GpuLayoutMeshBvh`, the same thing any builder returns. Use it wherever a tree goes: `assembleTraceScene` (above), a `build` function for `buildTraceScene`, `SceneTrees.placeTree` ([below](#baked-trees-in-scenetrees)), `GpuMeshRefit.setTree`, or `new CpuMeshBvh(layout)`.
## Check a file before loading it
A file records what it is and the versions it was written with. `readSerializedHeader(bytes)` reads them from the header alone:
- `kind`: `'tree'` or `'scene'`;
- `formatVersion` and `layoutVersion`;
- `current`: true when this package loads the file. When it's false, `reason` says why, in the words `deserializeLayout` would throw;
- the formats (`triangleLeaves`, `nodeFormat`, and a scene's `positionLayout`);
- the counts, and a tree's `bounds` and `geometryHash`.
It throws only for bytes that are neither kind of file. `isSerializedCurrent(bytes)` is the yes or no, and never throws. To fall back instead of failing:
```ts
import { createTinyBvhBuilder, deserializeLayout, readSerializedHeader, type GpuLayoutMeshBvh, type MeshInput } from '@pmndrs/bvh';
/** The baked tree at `url`, or a fresh build of `mesh` when the file is from another version of the package. */
export async function loadOrRebuild(url: string, mesh: MeshInput): Promise {
const bytes = await (await fetch(url)).arrayBuffer();
// The 64-byte header alone: the kind of file, the versions it was written with, and whether this package reads it.
const header = readSerializedHeader(bytes);
if (header.kind === 'tree' && header.current) return deserializeLayout(bytes, { geometry: mesh });
// A stale bake (header.reason says why): build it again, or fail the deploy.
console.warn(`${url}: ${header.reason ?? 'a scene file, not a tree'}; building instead`);
const tiny = await createTinyBvhBuilder();
return tiny.buildLayout(mesh, { maxLeafPrimitives: 8 }).layout;
}
```
A stale file is refused when it loads, but only someone who opens the page would see the error. Check the committed or deployed bakes in CI as well:
```ts
import { readdir, readFile } from 'node:fs/promises';
import { isSerializedCurrent } from '@pmndrs/bvh';
// In CI: every committed bake must be one this package loads, or the deploy ships files it refuses.
const stale: string[] = [];
for (const name of (await readdir(folder)).filter((file) => file.endsWith('.bvh'))) {
if (!isSerializedCurrent(await readFile(`${folder}/${name}`))) stale.push(name);
}
if (stale.length) throw new Error(`bake these again: ${stale.join(', ')}`);
```
## Scene files
A scene file holds everything `uploadTraceScene` needs:
- every mesh tree, and the merged static groups;
- the top level, with each instance's transform, mask and material;
- the triangles, with their per-triangle materials and filter flags;
- an indexed scene's positions;
- the formats.
Loading it builds and assembles nothing.
```ts
import { buildTraceScene, serializeTraceScene } from '@pmndrs/bvh';
const tiny = await createTinyBvhBuilder();
// Every tree, merged static instances, the top level, instance and triangle materials, the formats.
const scene = await buildTraceScene(meshes, instances, { build: (mesh) => tiny.buildLayout(mesh, { maxLeafPrimitives: 8 }).layout });
await writeFile(path, new Uint8Array(serializeTraceScene(scene)));
```
```ts
import { deserializeTraceScene } from '@pmndrs/bvh';
// No build and no assembly: the buffers go to the GPU as they were baked.
const scene = deserializeTraceScene(await (await fetch(url)).arrayBuffer());
const buffers = uploadTraceScene(device, scene); // compile the walk for scene.nodeFormat and scene.triangleLeaves
```
Any `TraceSceneData` can be saved: from `assembleTraceScene` or `buildTraceScene`, in any node or triangle format, with merged static instances, or cut into clusters (`clusterTraceScene`; the placements are kept, the `clusters` statistics are not). A loaded scene writes the same bytes again, and traces the same hits as the scene it was saved from.
**A scene file is a snapshot.** Its top level is baked, so its instances can't move, and its merged meshes hold their instances' transforms. For a scene whose instances move, bake one tree per mesh, then assemble them at load or place them in `SceneTrees`.
## Baked trees in SceneTrees
`SceneTrees` builds a tree for each mesh it's given, unless the app places one first. A baked file per mesh, placed with `placeTree` before the first update, means no build starts at all: neither the GPU's nor tinybvh's.
```ts
import { SceneTrees, type MeshGeometry } from '@pmndrs/bvh';
const trees = await SceneTrees.create(device);
for (const [index, geometry] of geometries.entries()) {
const mesh = trees.addMesh(geometry);
const bytes = await (await fetch(urls[index])).arrayBuffer();
// Checked against the geometry (its hash, when the bake has one); placed before the first update, so no build starts.
trees.placeTree(mesh, deserializeLayout(bytes, { geometry }));
trees.addInstance({ mesh, objectToWorld: matrix });
}
// The next update places every tree: trees.counts.onAppTrees === geometries.length.
```
The tree must have been baked from the geometry given to `addMesh`. With a hash in the file, `deserializeLayout(bytes, { geometry })` checks this. `placeTree` also requires:
- the scene's triangle format;
- `f32` trees for deforming meshes (a quantized scene quantizes `f32` trees, but an `f32` scene refuses quantized ones);
- `weld: false` for indexed trees in an indexed scene;
- a depth within `gpuMaxDepth`.
A deforming mesh's rebuilds still replace its baked tree ([Scene trees](/bvh/scenes/scene-trees#trees-you-built)).
## Indexed bakes
An `indexed` tree holds 16-byte triangles of vertex indices, not positions. That makes the file small, but it only works next to the exact positions and indices it was baked from. Hand them over wherever the tree goes:
```ts
// An indexed tree holds vertex indices, not positions: it only works next to the geometry it was baked from.
const tree = deserializeLayout(await (await fetch(url)).arrayBuffer(), { geometry });
const scene = assembleTraceScene([tree], instances, {}, { geometries: [geometry] }); // the scene copies the positions
const buffers = uploadTraceScene(device, scene);
const cpu = new CpuMeshBvh(tree, { source: geometry }); // the CPU walk reads them from the geometry
// SceneTrees takes it too: SceneTrees.create(device, { triangleLeaves: 'indexed', weld: false }), then placeTree.
```
`new CpuMeshBvh(tree, { source: geometry })` expands the tree to 48-byte records once; add `corners: 'positions'` to keep its 16-byte triangles and read every corner from the geometry's positions instead (the same answers, [CPU raycast](/bvh/cpu-queries/raycast)). In three, `deserializeBoundsTree(bytes, geometry)` keeps an indexed file indexed.
`deserializeLayout(bytes, { geometry })` checks that the geometry fits the tree:
- the triangle count matches;
- every vertex index falls within the geometry's vertices;
- the hash matches, if the file was written with `{ geometry }`.
Without the hash, positions that moved but kept their count would still load, and would trace wrong triangles. Bake indexed trees with their geometry. An indexed **scene** file carries its positions, so it needs no geometry.
## The format
```text
header, 16 words (64 bytes, little-endian)
0 magic 'PBVH' (a scene file: 'PBVS')
1 format version (SERIALIZED_FORMAT_VERSION, now 1)
2 GPU layout version (GPU_LAYOUT_VERSION, now 2)
3 nodeCount
4 triangleCount
5 maxDepth
6 leafCount
7 formats: bits 0-7 triangles (0 records, 1 indexed), bits 8-15 nodes (0 f32, 1 quantized)
8-13 bounds: minX, minY, minZ, maxX, maxY, maxZ (f32)
14-15 the geometry's hash (0 and 0: written without one)
nodes nodeCount x 64 bytes (f32), or (nodeCount + 1) x 32 (quantized: the frame slot, then the nodes)
triangles triangleCount x 48 bytes (records) or x 16 (indexed)
parents nodeCount x 4 bytes
```
`serializedLayoutBytes(layout)` gives the size before writing. The arrays are copied byte for byte, as the GPU reads them. WebGPU buffers are little-endian, as is every machine that runs WebGPU. Words 14-15 were 0 before the hash: older files load as files with no hash, and older readers ignore the words.
A scene file has its own magic and format version, and the same words 0-2:
```text
header, 16 words (64 bytes, little-endian)
0 magic 'PBVS'
1 format version (SERIALIZED_SCENE_FORMAT_VERSION, now 1)
2 GPU layout version (GPU_LAYOUT_VERSION, now 2)
3 formats: bits 0-7 triangles, bits 8-15 nodes (as a tree's), bits 16-23 positions (0 vec4, 1 packed)
4 meshes 5 merged static groups 6 top-level instance records
7 vertices 8 trace stack entries the scene needs
9-14 byte sizes: description, nodes, triangles, top level, recordOrder (entries), positions
15 0
description JSON: each mesh's and merged group's placement, the top level's node count, depth and skipped instances
nodes, triangles, top level, recordOrder (u32), positions: the scene's buffers, byte for byte
```
**Files from another version are refused, not converted.** That holds for the byte format and for the layout version. A tree is cheap to rebuild, and a wrong word position would only show up as wrong rays. Bake again when `GPU_LAYOUT_VERSION` changes, which is a breaking release. A scene that needs a deeper trace stack than the walk has is refused too.
## CPU trees
```ts
import { CpuMeshBvh } from '@pmndrs/bvh';
const tree = await CpuMeshBvh.create(input);
const bytes = tree.serialize();
// The layout is checked when it is loaded (children in range, every node reached once),
// so corrupt bytes throw instead of hanging a walk.
const loaded = CpuMeshBvh.deserialize(bytes, { source: input });
```
In three, `geometry.boundsTree.serialize()` and `deserializeBoundsTree(bytes, geometry)` do the same ([The tree object](/bvh/three/bounds-tree#save-and-load)). These are our layout's bytes.
## three-mesh-bvh's format
To hand trees to three-mesh-bvh, or read ones it stored, use its own serialized format: `serializeThreeMeshBvh(tree, { index })` writes its `SerializedBVH` (`{ version: 1, roots, index, indirectBuffer }`, indirect mode), and `meshBvhFromThreeMeshBvh(data, { positions, indices })` reads one into our layout, keeping its shape and making its boxes exact. In three, `MeshBVH.serialize(tree)` and `MeshBVH.deserialize(data, geometry)` take it, the latter our bytes too ([The tree object](/bvh/three/bounds-tree#save-and-load)). It isn't for baking: it holds no triangle records, so loading it builds our layout from the geometry (no SAH build, but a pass over every triangle).
## Bake at build time
The trees are built once, when the app is built, and shipped as files next to the models. There are two ways to do it, and neither needs a new package:
- **A script.** The Node snippet above, run before the bundler: `"prebuild": "node scripts/bake.ts"` writes the `.bvh` files into `public/`, and the page fetches them as it would a texture. The repo's [`examples:bake`](#the-bake-cli) is such a script.
- **A Vite plugin.** The same calls in `generateBundle`, so `vite build` emits the trees with the other assets (the dev server doesn't run `generateBundle`: run the script once, or serve the file from `configureServer`).
```ts
// vite.config.ts: bake at build time; the trees are emitted next to the app's other assets.
import { createTinyBvhBuilder, serializeLayout, type MeshInput } from '@pmndrs/bvh';
import type { Plugin } from 'vite';
/** `meshes` reads the app's models and returns each one's positions and indices, keyed by file name. */
export function bakeTrees(meshes: () => Promise>): Plugin {
return {
name: 'bake-trees',
async generateBundle() {
const tiny = await createTinyBvhBuilder();
for (const [name, mesh] of Object.entries(await meshes())) {
const { layout } = tiny.buildLayout(mesh, { maxLeafPrimitives: 8 });
this.emitFile({ type: 'asset', fileName: `trees/${name}.bvh`, source: new Uint8Array(serializeLayout(layout)) });
}
},
};
}
```
A tree file is one mesh's tree, and a tree must be loaded with the geometry it was built from. Meshes that share a tree are baked once and placed by many instances (`meshIndex`). A [scene file](#scene-files) holds a whole assembled scene.
## What invalidates a bake
Bake again when any of these change:
- **The geometry:** positions, indices, triangle order, or the per-triangle material numbers and filter flags. A `records` file carries the triangles, flags included, so its only link to the source mesh is that it was built from it. An `indexed` file holds no positions at all, and is only good next to the exact positions and indices it was built from. The geometry hash catches a changed position or index, but not changed flags or materials.
- **The mesh space:** a baked tree is in the mesh's own space. Moving or scaling the mesh object changes nothing, but a transform baked into the positions is part of the file (a glTF merged to world space, as `examples:bake` does).
- **A scene file's instances:** their transforms, masks and materials are part of the file.
- **The options:** `maxLeafPrimitives`, `triangleLeaves`, `nodeFormat`, and the builder (a tinybvh tree and an H-PLOC tree of one mesh differ). The formats are in the header, so a reader sees what it was given; the other options only change the tree.
- **`GPU_LAYOUT_VERSION`, `SERIALIZED_FORMAT_VERSION` or `SERIALIZED_SCENE_FORMAT_VERSION`:** a breaking release. The file is refused, not converted.
A newer tinybvh may build a different (equally valid) tree from the same mesh. An old bake still loads, and traces the same hits. A refit changes the tree's boxes, but it's applied at load and never baked, so bake the rest pose.
## The bake CLI
`pnpm examples:bake` bakes a model with tinybvh in Node and writes a tree or a scene, with no GPU involved:
```bash
pnpm examples:bake # the default torus knot -> examples/node/bake/fixtures/torus-knot.bvh
pnpm examples:bake model.glb --out public/model.bvh # a glTF's meshes, merged into one world-space mesh
pnpm examples:bake model.glb --leaf 4 --quantized # smaller leaves, 32-byte nodes
pnpm examples:bake model.glb --indexed # 16-byte indexed triangles: load next to the same geometry
pnpm examples:bake --scene # the default scene -> examples/node/bake/fixtures/knots.scene.bvh
pnpm examples:bake model.glb --scene # one tree per glTF mesh, its nodes as instances -> model.scene.bvh
```
It reads `.glb` and `.gltf` files, but not Draco, meshopt or quantized positions. It prints the counts, the build time, and the kind, formats and versions it wrote.
- **Tree files** carry their geometry's hash.
- **`--scene`** marks every instance static (a scene file's instances can't move anyway), so meshes used once merge into one world-space mesh. `--no-merge` keeps them as instances.
- **`--f32`** gives 64-byte nodes. A scene's default is quantized, a tree's is `f32`.
## An example
[`node/bake`](https://github.com/pmndrs/bvh/tree/main/examples/node/bake) is the CLI above (`cli.ts`, `bake.ts`, `model.ts`) and a page that loads either kind of file with no build at all. The page:
1. reads the header with `readSerializedHeader`;
2. loads the file with `deserializeLayout` or `deserializeTraceScene`;
3. uploads it, and traces it with the WGSL walk in the shared ray-cast view.
The overlay's `builtBy` says `baked tree: torus-knot.bvh` or `baked scene: `. It also shows the fetch and deserialize times, and the header's versions next to this package's.
An indexed tree loads next to the default knot, or next to the glTF named by `?model=` (merged to world space as the CLI does it). The page refuses it next to anything else.
`?bake=` (try `fixtures/knots.scene.bvh`) or a dropped `.bvh` loads another file. The smoke run checks three files: the default tree, an indexed tree baked in the page, and the committed scene file. It compares each against the CPU walk, and the committed files byte for byte against fresh bakes.
]]>
=0.187.0 <0.188.0`: `BvhTraceNodes` relies on three's WebGPU backend internals, so each three release is checked before the range widens.
## On the GPU (WebGPURenderer)
| You want | Use | Page |
| ----------------------------------------------------------- | ----------------------------------------------- | -------------------------------------------------------------------- |
| The renderer's device | `deviceFromRenderer`, `deviceFromRendererAsync` | [Sharing a device](/bvh/engines/sharing-a-device#threejs) |
| A scene graph's meshes and instances as trees, kept in step | `SceneTrees` + `SceneTreesObject3DSync` | [Scenes and the sync](/bvh/three/scenes-and-sync) |
| Rays from TSL or a `wgslFn` | `BvhTraceNodes` | [BvhTraceNodes](/bvh/three/trace-nodes) |
| Skinned and morphed meshes posed on the GPU | the sync with a `renderer`, `BvhPosePass` | [Skinned and morphed meshes](/bvh/three/skinned-and-morphed) |
| The scene once, without the sync | `bvhSceneFromObject3D`, then `buildTraceScene` | [Scenes and the sync](/bvh/three/scenes-and-sync#without-scenetrees) |
## On the CPU (any renderer)
| You want | Use | Page |
| ----------------------------------------------------------------------------------- | ------------------------------------------------------------------------------------- | --------------------------------------------------------- |
| Faster `Mesh.raycast` | `computeBoundsTree`, `acceleratedRaycast` | [CPU raycast](/bvh/three/cpu-raycast) |
| A ray against the whole scene, frustum culling | `BvhSceneRaycaster`, `raycastScene` | [CPU raycast](/bvh/three/cpu-raycast#a-whole-scene) |
| Faster `Points` and line raycasts | `computeBoundsTree({ type: PointsBVH })`, `LineSegmentsBVH`, `LineLoopBVH`, `LineBVH` | [Points and lines](/bvh/three/points-and-lines) |
| three-mesh-bvh's `MeshBVH` API: shapecast, bvhcast, closest point, refit, serialize | `geometry.boundsTree` (`BvhBoundsTree`, also exported as `MeshBVH`) | [The tree object](/bvh/three/bounds-tree) |
| A tree built off the main thread | `GenerateMeshBvhWorker` | [CPU raycast](/bvh/three/cpu-raycast#off-the-main-thread) |
| The tree's boxes drawn | `MeshBVHHelper`, `BVHHelper` | [The tree object](/bvh/three/bounds-tree#the-helper) |
Coming from three-mesh-bvh? [The mapping and what's missing](/bvh/three/coming-from-three-mesh-bvh).
## Types
`/three` augments three's types as three-mesh-bvh does: `BufferGeometry.boundsTree` (a `BvhBoundsTree`), `computeBoundsTree`, `disposeBoundsTree` and `Raycaster.firstHitOnly`, so the setup needs no casts. A program that imports both libraries gets two declarations of the geometry members with different types (TS2717); `skipLibCheck`, on in most templates, hides it.
## Not supported
- WebGL2: `BvhTraceNodes` needs the WebGPU backend. The CPU raycast works with either backend.
- Points, lines and sprites are not read by the scene sync, the GPU walk or the scene raycast, which take triangles. Points and lines have their own CPU trees ([Points and lines](/bvh/three/points-and-lines)); sprites have none.
- Layers 8-31 are not seen: the instance mask holds layers 0-7.
]]>
!object.userData.moves, // static instances can merge, and are never pushed again
material: (mesh) => materialIndexOf(mesh), // becomes hit.material (0-65534)
layers: true, // layers 0-7 become the instance mask (default)
});
// After adding or removing objects, or changing geometry, groups or materials:
sync.sync();
// Every frame: moved, shown, hidden or re-layered objects only.
sync.update();
```
- **`sync()`** after objects are added or removed, or a geometry, draw range, group or material changes: only the meshes and instances that changed are added or removed. It walks and plans before it changes anything, so a throwing `material` callback leaves everything as it was.
- **`update()`** each frame: it skips an object whose `matrixWorld`, effective visibility, layers and `instanceMatrix.version` are unchanged, without allocating. Set `instanceMatrix.needsUpdate = true` after `setMatrixAt`, as three needs anyway.
- Then `trees.update(encoder)`, submit, and `bvh.update()` if you use [BvhTraceNodes](/bvh/three/trace-nodes).
## What is read
- `Mesh`, `InstancedMesh` (instances below its `count`), `BatchedMesh` (active, visible instances) and `SkinnedMesh` (posed on the GPU with a `renderer`; [Skinned and morphed meshes](/bvh/three/skinned-and-morphed)).
- The triangles three's `Mesh.raycast` tests: the draw range and, with an array of materials, the groups within it. Ranges are read as three steps through them, even off a multiple of 3 or overlapping.
- **Multi-material meshes** (an array of materials, with groups) are folded: one mesh holding every group, in group order, and one instance per object (and per instance of an `InstancedMesh`). Each triangle carries its group's material (`triangleMaterials`, from `material(mesh, info)`, asked once per group with `info.group` and `info.materialIndex`). The sync, `bvhSceneFromObject3D` and `BvhSceneRaycaster` fold the same way, so instance N is the same object in all three. A folded source's `group` and `materialIndex` are -1 (the hit's triangle names its group: see "Hits back to objects" below). An object whose instances give a group different materials (an `InstancedMesh` with a material per instance) is not folded: it keeps one mesh per group, shared by its instances, with each instance's material on the instance. `multiMaterial: 'groups'` keeps one mesh and instance per group for every object, as the sync and the scene raycaster did before.
- Indexed, non-indexed and interleaved positions. Interleaved, normalized or non-float positions are compacted once per geometry.
- One mesh per geometry and range, shared by every object and instance that uses it.
- **Visibility:** an object counts as visible when it and every ancestor are. Hidden objects stay in as hidden instances.
- **Layers:** layers 0-7 become instance mask bits 0-7; layers 8-31 are dropped. An object on none of layers 0-7 gets mask 0, which no ray hits. A default object (layer 0) gets `0x01`. `layers: false` gives every instance `0xff`.
- **Materials:** the `material(mesh, info)` callback is read at `sync()` only. After changing what it returns, call `sync()`.
Call `scene.updateMatrixWorld()` first: world matrices are read as they are.
## Hits back to objects
```ts
import { threeGroupOf, threeMaterialOf } from '@pmndrs/bvh/three';
const source = sync.sourceOf(hitInstance); // { object, instanceId, group, materialIndex, mesh, static }
const meshSource = sync.meshSourceOf(hitInstance);
if (source && meshSource) {
console.log(source.object.name, source.instanceId);
// A folded multi-material mesh has group -1: the hit's triangle names its group and three material.
const group = threeGroupOf(meshSource, hitTriangle); // { group, materialIndex, material, ... } or null
const material = threeMaterialOf(source, meshSource, hitTriangle); // object.material[group.materialIndex], or object.material
console.log(group?.materialIndex, material?.name);
}
```
`hit.triangle` is the triangle within its mesh (a folded mesh's groups one after another, a group, a draw range or a batch range). `threeFaceIndex(meshSource, triangle)` turns it into three's `faceIndex`; `sync.meshSourceOf(instance)` gives the mesh source (`BvhSceneRaycaster.meshSourceOf`, or `scene.meshSources[source.mesh]`, elsewhere).
`hit.material` is what your `material` callback returned for the hit triangle's group (or the instance's answer, for a mesh of one material). To get from a hit to three's `object.material[i]`, either return `info.materialIndex` (or a value you map back from it) in the callback, or call `threeMaterialOf(source, meshSource, hit.triangle)`, which works without a callback. `threeGroupOf(meshSource, hit.triangle)` gives the group itself.
`sync.meshHandles` lists the `SceneTrees` mesh handles the sync holds (one per mesh it added: a shared geometry range, or a posed object's own), for `trees.meshStatus(handle)` and stats. It is a new array each time; `sync()` can add and remove handles. Merged static groups are `SceneTrees`' own (`trees.groupStatus`).
```ts
// The SceneTrees mesh handles the sync holds now: one per shared geometry (or posed object).
let nodes = 0;
for (const handle of sync.meshHandles) nodes += trees.meshStatus(handle).placement?.nodeCount ?? 0;
```
## Static objects
`static: true`, or `(object, instanceId) => boolean`, marks instances for `mergeStaticInstances` ([Merged static instances](/bvh/scenes/merged-static)). The sync never pushes changes to static instances.
After `SceneTrees` merged an object's static instances, `sync()` skips removing that object or changing its geometry, draw range, groups or materials, and warns once per object (`skipped` in the counts). Mark objects that may go away `static: false`.
## Without SceneTrees
`bvhSceneFromObject3D(root, options)` reads the scene once and returns `meshes`, `instances` and their three `sources`. Build it with `buildTraceScene(scene.meshes, scene.instances, { build })`, upload it with `uploadTraceScene`, and `BvhTraceNodes` takes the result as `{ buffers }`.
]]>
BvhTraceHit struct node
bvh.traceAny(origin, direction, tMin = 0, tMax = 1e30) -> bool node
bvh.traceClosestMasked(origin, direction, tMin, tMax, mask) -> BvhTraceHit
bvh.traceAnyMasked(origin, direction, tMin, tMax, mask) -> bool
bvh.closestPoint(point, maxDistance = 1e30) -> BvhClosestPointHit // with queries: true
bvh.closestPointMasked(point, maxDistance, mask) -> BvhClosestPointHit
```
`BvhTraceHit` has `BvhHit`'s members: `t`, `instance`, `triangle`, `barycentrics`, `frontFace`, `material` and `normal`. Read them with `hit.get('t')`. The [first build](/bvh/getting-started/first-build#threejs-on-the-gpu) has a full example; the [path tracer example](/bvh/examples/examples) traces a bounce loop with it.
With `queries: true` the module also has the [spatial queries](/bvh/tracing/gpu-queries). `BvhClosestPointHit` has `BvhClosestHit`'s members: `distance` (negative when nothing is nearer than `maxDistance`), `instance`, `triangle`, `material`, `barycentrics`, `point` and `normal`, in world space. From WGSL, call `bvhClosestPoint`, `bvhIntersectsSphere`, `bvhIntersectsBox` and `bvhIntersectsOrientedBox` by name; `shapecast: wgsl` compiles your own shapecast hooks into the module.
## WGSL
```ts
import { wgslFn } from 'three/tsl';
import { BvhTraceNodes } from '@pmndrs/bvh/three';
const bvh = new BvhTraceNodes(renderer, trees); // binds SceneTrees' own buffers, no copy
// WGSL: three's wgslFn with the walk as an include, calling it by name.
const shadow = wgslFn(
/* wgsl */ `fn shadow(p: vec3f, l: vec3f, d: f32) -> f32 {
return select(1.0, 0.0, bvhTraceAny(BvhRay(p, 1e-3, l, d)));
}`,
[bvh.module],
);
```
`bvh.module` is the walk without bindings: three binds the storage nodes. Call `bvhTraceClosest`, `bvhTraceAny` and the masked forms by name ([Tracing in WGSL](/bvh/tracing/wgsl-walk)).
## Options
```ts
const bvh = new BvhTraceNodes(renderer, trees, {
rayMasks: true, // default: traceClosestMasked and traceAnyMasked exist
anyHitOrder: 'far', // default; 'larger' for occlusion rays from outside the model or across open space
triangleFilter: /* wgsl */ `fn bvhTrianglePasses(candidate: BvhCandidate) -> bool { return candidate.query == BVH_QUERY_ANY; }`,
});
```
`anyHitOrder` is the any-hit walk's child order, compiled in: `'far'` (the default) is best for rays that start on surfaces, `'larger'` for rays from outside or across open space. Answers are the same either way. On the RTX 3060 Laptop (Windows, headless Chrome 157, 2026-11-13, Sponza and Bistro interior, the median of three runs), `'larger'` was 1.11-1.48x `'far'` on instanced trees and 1.03-1.07x on merged trees with rays from the air, but 0.80-0.87x on merged trees with rays from surfaces. The Apple M5 showed the same pattern (1.15-1.42x instanced, 0.78x merged surface rays). Merged trees are the default, so `'far'` stays the default.
The walk is compiled for the source's formats (`triangleLeaves`, `positionLayout`, `nodeFormat`); with indexed leaves a fourth storage node, `bvh.storage.positions`, is bound. A `SceneTrees` names them; so does an upload (`new BvhTraceNodes(renderer, { buffers: uploadTraceScene(device, scene) })` reads them from the buffers). A source of your own must name all three: the formats are never guessed, and a source without them is refused.
## Each frame
Call `bvh.update()` after every `SceneTrees.update` that may grow a buffer, and before three uses the nodes again. When `SceneTrees.version` changed it swaps in an attribute bound to the new buffer, and three makes new bind groups. Nothing recompiles.
## Waiting for every tree
three-mesh-bvh's `await bvh.updateAsync()` builds every tree before the scene is traced. Here the builds already run in the background (GPU first trees, tinybvh in workers), so a frame loop needs nothing extra: its next frame starts them and each tree is placed when it arrives. For a first load that should be complete before the first traced frame, wait for it:
```ts
import { BvhTraceNodes, SceneTreesObject3DSync, deviceFromRenderer, updateSceneTreesAsync } from '@pmndrs/bvh/three';
import { SceneTrees } from '@pmndrs/bvh';
import type { WebGPURenderer } from 'three/webgpu';
const trees = await SceneTrees.create(deviceFromRenderer(renderer));
const sync = new SceneTreesObject3DSync(trees, scene, { renderer });
const bvh = new BvhTraceNodes(renderer, trees);
// three-mesh-bvh's `await bvh.updateAsync()`: every tree built and placed before the first traced frame.
await bvh.updateAsync({ sync }); // or updateSceneTreesAsync(trees, { sync, nodes: bvh, until: 'refined' })
```
`updateSceneTreesAsync(trees, { sync, nodes, until })` walks the scene (`sync.sync()`) and waits for its pose pipelines (`sync.ready`), runs an update in an encoder of its own (which starts every build), waits for `whenBuilt()` (or `whenRefined()` with `until: 'refined'`: tinybvh's trees, not the GPU's first ones), runs another update (which places the trees) and rebinds the nodes. `bvh.updateAsync({ sync, until })` does the same for a `SceneTrees` source, and only rebinds an uploaded one.
## Shapecasts with TSL hooks
`bvh.getShapecastFn(options)` is three-mesh-bvh's `getShapecastFn`: a shapecast over the whole scene whose box and triangle tests are three function nodes, a TSL `Fn` with `setLayout` or a `wgslFn`. It returns a TSL function that runs the cast and returns true when the triangle test stopped it. It needs `queries: true`.
```ts
import { BvhTraceNodes, type BvhTslNode } from '@pmndrs/bvh/three';
import type { SceneTrees } from '@pmndrs/bvh';
import { Fn, If, float, instanceIndex, max, select, storage, uint, vec3, wgslFn } from 'three/tsl';
import { StorageBufferAttribute, type WebGPURenderer } from 'three/webgpu';
const bvh = new BvhTraceNodes(renderer, trees, { queries: true });
// A box test as a TSL Fn with a layout (a pure function of its arguments): the box's score, negative to skip it.
const sphereBounds = Fn(([sphere, boxMin, boxMax]: BvhTslNode[]) => {
const outside = max(max(boxMin.sub(sphere.xyz), sphere.xyz.sub(boxMax)), vec3(0));
const distanceSq = outside.dot(outside);
return select(distanceSq.lessThanEqual(sphere.w.mul(sphere.w)), distanceSq, float(-1));
}).setLayout({ name: 'sphereBounds', type: 'float', inputs: [{ name: 'sphere', type: 'vec4' }, { name: 'boxMin', type: 'vec3' }, { name: 'boxMax', type: 'vec3' }] });
// A triangle test as a wgslFn, which may call the module's helpers: true stops the cast.
const sphereTriangle = wgslFn(
`fn sphereTriangle(sphere: vec4f, a: vec3f, b: vec3f, c: vec3f) -> bool {
let offset = bvhClosestPointToTriangle(sphere.xyz, a, b, c).point - sphere.xyz;
return dot(offset, offset) <= sphere.w * sphere.w;
}`,
[bvh.module],
);
// Does each sphere (centre, radius) touch the scene?
const touches = bvh.getShapecastFn({ name: 'sphereTouches', shape: 'vec4', intersectsBounds: sphereBounds, intersectsTriangle: sphereTriangle });
const sphereNode = storage(spheres, 'vec4', count).toReadOnly();
const out = new StorageBufferAttribute(new Uint32Array(count), 1);
const outNode = storage(out, 'uint', count);
const kernel = Fn(() => {
If(instanceIndex.lessThan(count), () => {
outNode.element(instanceIndex).assign(select(touches(sphereNode.element(instanceIndex)), uint(1), uint(0)));
});
})().compute(count, [64]);
await renderer.computeAsync(kernel);
const touching = new Uint32Array(await renderer.getArrayBufferAsync(out));
```
- **`shape`**: the TSL type of the value the cast is called with (`'vec4'`, `'mat4'`, a `StructTypeNode`, ...). Every hook gets it first. Without it, the hooks and the call take no shape.
- **`intersectsBounds(shape?, boxMin, boxMax) -> float`**: a world box's score. Negative skips the box; of two siblings the lower score is entered first.
- **`intersectsTriangle(shape?, a, b, c, instance, triangle, material, normal) -> bool`**, or any leading part of those arguments (only what the hook declares is computed): a triangle in world space, its instance (`hit.instance`), original triangle, material and the world normal of its authored front side. True stops the cast.
- **`keep(shape?, score) -> bool`** (optional): asked when a box comes off the stack with the score it was pushed with; false skips it. Use it to cull boxes farther than the best answer so far. Default: keep every box.
- **`name`**: the WGSL name of the cast (default `bvhThreeShapecast`, numbered in order of creation). Name your casts to keep the shader text the same across loads.
- The call takes `(shape?, mask?)`; `mask` (a `u32`, default every instance) only with `rayMasks`.
The hooks become functions of their own in the shader, and the walk is the trace module's shapecast walk (the one `traceModuleWgsl({ shapecast })` stamps for WGSL hooks, [Your own shapecast](/bvh/tracing/gpu-queries#your-own-shapecast)): world space, every instance, node and triangle format. Two limits come from three:
- A TSL `Fn` with a layout is cached across shaders, so its body must depend only on its arguments. Pass per-call data as the `shape`, not as a uniform read in the hook.
- TSL hooks can't keep state between calls. A hook that counts or keeps a best distance is a `wgslFn` writing a `var` (declared in a `code()` node it includes) or a storage buffer; another `wgslFn` with the same include reads it after the cast.
The triangle hook may call the module's other walks (`bvhTraceAny`, `bvhClosestPoint`, ...); the box and keep hooks must not. The differences from three-mesh-bvh's: the triangle test gets one world-space triangle at a time rather than a leaf's index range, and there is no result pointer (the shape goes in by value; results come back through state, as above).
Checked in Node, with three's own WGSL node builder, that a kernel calling a cast compiles to the expected text, and on a GPU by the `three-shapecast` page: a sphere cast against the library's `bvhIntersectsSphere`, and a counting cast with private state against a CPU count.
## How it binds, and what can break
- The storage nodes are bound to `SceneTrees`' own `GPUBuffer`s, with no copy. `BvhTraceNodes` sets three's backend buffer for each node before three first uses it. That is three's internals, not its API; it is in one place, `threeInternals` in `src/three/trace-nodes.ts`.
- **Checked:** once three has used a node, `update()` checks that three still binds our buffer. A three version that looks buffers up differently makes `update()` throw, naming the version, rather than read a 16-byte placeholder.
- **Disposal:** `renderer.dispose()` doesn't destroy `SceneTrees`' buffers. `bvh.dispose()` releases the nodes.
- **Shader size:** the walk goes into each shader once, as plain WGSL (one loop, a 64-entry stack), and each TSL helper is one small function. The names are fixed, so the shader text is the same on every load.
- It needs an initialized `WebGPURenderer` on its WebGPU backend (`await renderer.init()`).
]]>
boolean` says otherwise. Without a renderer they stay in their rest pose.
Not posed: `BatchedMesh`, and an `InstancedMesh` with per-instance morphs (`morphTexture`) and more than one instance (the sync warns once and reads its rest pose). A posed object gets its own mesh per triangle range; its instances never merge. Hidden objects aren't posed.
## The pass
`BvhPosePass` runs three r187's math in three's order: morphs as `morphReference` does them, then skinning as `getSkinnedPosition` does it, after `skeleton.update()`. It writes one `vec4` per vertex. On the Apple M5 the posed vertices match three's CPU pose (`getVertexPosition`, `applyBoneTransform`) to 6.4e-7.
- **Compile cost:** one shader per variant (skinned, morphed, both), shared by every posed mesh of that variant. The sync compiles each variant when its first mesh is added. Until the compile settles, `update()` doesn't pose that variant's objects (`sync.poseCounts.waiting`); `await sync.ready` has every object posed from the first update.
- **Inputs are read once:** rest positions, skin indices and weights and morph targets are packed when the pass is made. A new geometry object gets a new pass at `sync()`; editing those attributes in place is not followed.
- **A replaced skeleton** gets a new pass at the next `update()`.
## The top-level box follows the pose
The top level keeps one box per deforming mesh. The sync sets it (`SceneTrees.setDeformBounds`) from `pass.bounds()`, a box that holds the pose, computed from the skeleton on the CPU. It moves only when the pose leaves the box, or the box grows past twice the padded pose. `deformSlack` (default 0.25 of the largest extent, on every side) sets the room. A walking character's root motion is followed.
## Picking
GPU picking (`TraceBatchKernel` or `BvhTraceNodes`) hits the posed surface. CPU picking on a posed mesh stays on three's own raycast (`acceleratedRaycast` falls back for a `SkinnedMesh` or morph targets), which poses each vertex on the CPU. For CPU queries on the live pose with a tree, use `SkinnedMeshBVH` (one mesh, in its own space) or bake the meshes with `StaticGeometryGenerator` (below).
Tested on the `three-skinned` GPU page (Apple M5): 0 disagreements over 16,384 rays at 4 frames, against three's CPU pose. The [skinned example](/bvh/examples/examples) shows nine characters.
## A tree that follows the pose
`SkinnedMeshBVH` is three-mesh-bvh's class: a CPU tree over one `SkinnedMesh`'s (or morph-target mesh's) posed triangles, in the mesh's own space. Set it as the geometry's tree and `acceleratedRaycast` hits the pose; refit it after the pose moves.
```ts
import { SkinnedMeshBVH, acceleratedRaycast, prepareBoundsTrees, setBoundsTree } from '@pmndrs/bvh/three';
import { Mesh, SkinnedMesh, type Raycaster } from 'three';
await prepareBoundsTrees();
Mesh.prototype.raycast = acceleratedRaycast;
SkinnedMesh.prototype.raycast = acceleratedRaycast; // three's SkinnedMesh has a raycast of its own
const bvh = new SkinnedMeshBVH(character); // the current pose, in the mesh's own space
setBoundsTree(character.geometry, bvh); // geometry.boundsTree = bvh
// Each frame, after the animation mixer and updateMatrixWorld():
const frame = () => {
bvh.refit(); // poses every vertex again (three's getVertexPosition) and refits the boxes
raycaster.firstHitOnly = true;
const [hit] = raycaster.intersectObject(character); // the live pose
console.log(hit?.point, hit?.face?.normal);
};
```
- **The pose** is three's own CPU pose: each vertex through `mesh.getVertexPosition` (morph targets, then skinning), the one three's raycast tests. `matrixWorld` places the tree as it places the mesh, so the object can move freely.
- **`refit()`** poses every vertex again and refits the boxes, keeping the tree's shape (`CpuMeshBvh.refit`). A tree refitted many times over very different poses gets slower boxes; build a new one now and then if that matters.
- **Queries** (`raycast`, `raycastFirst`, `shapecast`, `closestPointToPoint`, ...) read the posed corners. A raycast hit's `face.normal` comes from the pose; its `uv` and interpolated `normal` from the geometry's attributes, as three's raycast of a `SkinnedMesh` gives them.
- **`SkinnedMesh.prototype.raycast`** must be set too: three's `SkinnedMesh` has a raycast of its own, so setting `Mesh.prototype.raycast` alone never reaches it (as with three-mesh-bvh).
- The options are `computeBoundsTree`'s. The tree belongs to one mesh: two meshes sharing a geometry need a tree each, and only one can be `geometry.boundsTree`.
- **Cost:** `refit()` poses every vertex on the main thread. For many characters, pose on the GPU (above).
It isn't built on `StaticGeometryGenerator`, which bakes every visible mesh under an object into world space and flips a mirrored mesh's winding; this tree is one mesh in its own space, with the geometry's triangle numbering. Tested against three-mesh-bvh's `SkinnedMeshBVH` and three's raycast of the posed mesh (skinned, mirrored and morphed, indexed and not, over three poses), and its shapecast against three-mesh-bvh's.
## On the CPU: StaticGeometryGenerator
`StaticGeometryGenerator` is three-mesh-bvh's class: it bakes skinned and morph-target meshes (and plain ones) into one static `BufferGeometry`, on the CPU, so a tree over it answers CPU raycasts, shapecasts and closest-point queries for the live pose. Use it for a character's collider or for picking on an animated mesh without a GPU readback.
```ts
import { StaticGeometryGenerator, computeBoundsTree } from '@pmndrs/bvh/three';
import { Mesh, type Raycaster, type SkinnedMesh } from 'three';
const generator = new StaticGeometryGenerator(character); // every visible mesh under it
const geometry = generator.generate(); // the current pose, in world space, a group per mesh
computeBoundsTree.call(geometry);
const collider = new Mesh(geometry, generator.getMaterials()); // identity transform: the pose is in world space
// Each frame, after the animation mixer and updateMatrixWorld():
const frame = () => {
generator.generate(geometry); // the same arrays; the index is left alone
geometry.boundsTree!.refit();
raycaster.firstHitOnly = true;
const [hit] = raycaster.intersectObject(collider); // the live pose
console.log(hit?.point);
};
```
- **What it bakes:** every visible `Mesh` under the objects you pass (`traverseVisible`), in that order. `meshes` lists them, and `getMaterials()` gives their materials in the order of the geometry's groups (one group per mesh with `useGroups`, the default).
- **three's math:** each vertex is morphed as three's `Mesh.getVertexPosition` morphs it, then skinned with `SkinnedMesh.applyBoneTransform`, so the baked positions are what three's own CPU raycast tests. Normals and tangents go through the blended bone matrix. With `applyWorldTransforms` (default true) everything is in world space; a mirrored mesh's triangles are flipped to keep their winding.
- **Updating:** pass the same geometry to `generate` again. Its arrays are written in place and its index is left alone, so `geometry.boundsTree.refit()` is enough, as with three-mesh-bvh. Meshes that didn't change (matrix, positions version, bone matrices, morph weights) are skipped.
- **`attributes`** (default `position`, `normal`, `color`, `tangent`, `uv`, `uv2`) says what to copy. Every mesh must have the same attributes, and all must be indexed or none; `generate` throws otherwise, or when a mesh's attribute sizes changed since the last call.
- **Cost:** every vertex of every changed mesh, every call, on the main thread. For many or large characters, pose on the GPU (above) instead.
It is a port of three-mesh-bvh 0.9.18's class (MIT). One difference: three-mesh-bvh doesn't notice a change of morph weights alone and keeps the old pose; this one bakes again. Tested bit for bit against three-mesh-bvh's output and three's `getVertexPosition`, and a tree over the baked geometry hits what three's raycast of the posed meshes hits, before and after the pose moves.
## See also
- [Deforming meshes](/bvh/scenes/deforming-meshes): what `SceneTrees` does with a pose, whatever made it: the refit, drift and rebuilds.
- [Refits](/bvh/scenes/refits): `GpuMeshRefit` on its own.
]]>
{
if (!sphere.intersectsBox(box)) return NOT_INTERSECTED;
return sphere.containsPoint(box.min) && sphere.containsPoint(box.max) ? CONTAINED : INTERSECTED;
},
// Each object in an entered box: instanceId is the InstancedMesh or BatchedMesh instance, else 0.
intersectsObject: (object, instanceId) => {
console.log(object.name, instanceId);
near.push(object);
return false; // true stops the cast
},
});
```
- `intersectsBounds(box, isLeaf, score, depth, nodeIndex)`: a world `Box3` (scratch, valid during the call). Return `NOT_INTERSECTED` (or anything falsy) to skip it, `INTERSECTED` to enter it, `CONTAINED` to hand over every object under it without asking about the boxes below.
- `intersectsObject(object, instanceId, contained, depth, source)`: each object in an entered box. `instanceId` is the `InstancedMesh` or `BatchedMesh` instance, else 0, as in three-mesh-bvh; `source` is ours (`{ object, instanceId, group, ... }`; a multi-material mesh with `multiMaterial: 'groups'` comes once per group). True stops the cast.
- `intersectsRange(offset, count, contained, depth, nodeIndex, box)` and `boundsTraverseOrder(box)` work as in three-mesh-bvh. Ranges are positions in the top level (`picker.cpuScene.instanceAt(position)`).
- The boxes are the padded world boxes of each object's mesh tree, not three-mesh-bvh's (the geometry's box shrunk to its sphere); both hold the object. Hidden objects are in unless `includeHidden: false`; a `BatchedMesh`'s hidden instances are not.
- Without three: `CpuSceneBvh.shapecast({ intersectsBounds, intersectsInstance, intersectsRange, boundsTraverseOrder })`, with instances by `instanceIndex`, and `CpuSceneBvh.traverse`.
Tested call for call against three-mesh-bvh's `shapecastTraverse` run over the same top level, and against `ObjectBVH.shapecast` on sphere casts before and after objects move.
## Off the main thread
```ts
import { GenerateMeshBvhWorker } from '@pmndrs/bvh/three';
const generator = new GenerateMeshBvhWorker(); // on @pmndrs/bvh/worker's pool; inline in Node
geometry.boundsTree = await generator.generate(geometry, { maxLeafSize: 8, onProgress: (p) => console.log(p) });
generator.dispose(); // stops the pool and rejects unfinished builds
```
`GenerateMeshBvhWorker` builds on `@pmndrs/bvh/worker`'s pool ([Workers](/bvh/workers/workers)). The geometry's arrays are copied, not moved, so it stays usable, and several builds may run at once. Pass `{ pool }` to share a pool.
## Speed
On a 100,000-triangle torus knot, Node 22 on the Apple M5 (indicative): 692,630 `firstHitOnly` raycasts per second against three-mesh-bvh's 664,652 (CENTER) and three's 294; build 28 ms against 31 ms (CENTER) and 95 ms (SAH). How it was measured: [Raycast](/bvh/cpu-queries/raycast#speed). In the browser (`three/raycast` example, headless Chrome on the M5): 0.40 million raycasts per second against three's 306.
]]>
(sphere.intersectsBox(box) ? INTERSECTED : NOT_INTERSECTED),
intersectsTriangle: (triangle: ExtendedTriangle) => {
if (triangle.intersectsSphere(sphere)) count++;
return false;
},
});
```
**Queries read the tree's triangles**, not the geometry's current positions. After editing positions, call `refit()` first (three-mesh-bvh reads the geometry, so it sees edits straight away).
## Build options
`computeBoundsTree`, `new BvhBoundsTree`, `new MeshBVH` and `GenerateMeshBvhWorker.generate` take three-mesh-bvh's options:
| Option | What happens |
| ---------------------------------------------- | ------------------------------------------------------------------------------------------------------------------------------------------------------- |
| `strategy` (`CENTER` 0, `AVERAGE` 1, `SAH` 2) | Accepted. Every value builds the same tree: tinybvh's binned SAH, whose trees have a lower SAH cost than a centre or average split. Other values throw. |
| `maxLeafSize`, `targetLeafSize`, `maxLeafTris` | The largest leaf (`targetLeafSize` wins, then `maxLeafSize`), clamped to 1-8: three-mesh-bvh's default 10 gives 8. |
| `maxDepth` | Accepted, not honoured: tinybvh decides the depth (`boundsTree.depth`). A value below it logs one warning. |
| `setBoundingBox` | Default `true`: sets `geometry.boundingBox` from the tree when it has none, and `refit()` keeps it current. |
| `indirect` | Accepted and ignored: the geometry's index is never reordered. |
| `onProgress` | Called with 0 before the build and 1 after it: tinybvh builds in one call. |
| `verbose`, `useSharedArrayBuffer` | Accepted and ignored. |
| `range` | Throws: the tree holds every triangle, and raycasts follow the draw range. |
| `builder`, `layout`, `snapshot` (ours) | A tinybvh builder to use; a tree already built for this geometry; the geometry's versions when that build started (`snapshotGeometry`). |
`buildOptionsFromThreeMeshBvh(options)` gives the core options these map to.
## Save and load
Two formats, one call to read either:
- **Ours:** `boundsTree.serialize()` gives our layout's bytes (`serializeLayout`), and `deserializeBoundsTree(bytes, geometry)` or `MeshBVH.deserialize(bytes, geometry)` reads them. These are what the GPU uploads, so a baked tree loads with no build. See [Serialization and baking](/bvh/serialization/serialization-and-baking). Either triangle format loads: an indexed file (or an indexed `layout`) stays indexed, 16 bytes per triangle, its corners read from the geometry's own positions (`CpuMeshBvh`'s `corners: 'positions'`), with the same answers as the records tree. It reads the positions live, so after editing them call `refit()` before querying the tree directly.
- **three-mesh-bvh's:** `MeshBVH.serialize(tree)` gives its `SerializedBVH` (`{ version, roots, index, indirectBuffer }`), which three-mesh-bvh's `MeshBVH.deserialize` reads, and `MeshBVH.deserialize(data, geometry)` reads one written by three-mesh-bvh. Use it to swap a library in or out without rebuilding stored trees.
```ts
import { MeshBVH } from '@pmndrs/bvh/three';
import type { BufferGeometry } from 'three';
// Ours to three-mesh-bvh: its MeshBVH.deserialize(data, geometry) reads this.
const data = MeshBVH.serialize(new MeshBVH(geometry)); // { version: 1, roots, index, indirectBuffer }
// three-mesh-bvh's to ours: its MeshBVH.serialize(bvh) output, structured-cloned from a worker or stored.
const tree = MeshBVH.deserialize(theirs, geometry); // setIndex: true sets the index three-mesh-bvh wrote
geometry.boundsTree = tree;
// Our own bytes still go through the same call.
const again = MeshBVH.deserialize(tree.serialize(), geometry);
```
- **Writing** always gives indirect mode (our trees never reorder the geometry): one root, `indirectBuffer` mapping tree positions to triangles, `index` a copy of the geometry's (`cloneBuffers: false` hands over the same array). A geometry without an index gives `index: null`; pass `setIndex: false` to three-mesh-bvh's `deserialize` then.
- **Reading** keeps the tree's shape (which triangles share a leaf, which nodes are whose children) and recomputes every box from the triangles, so the boxes are exact. Leaves of more than 8 triangles (three-mesh-bvh's default is 10) are cut in half. A tree that reordered the index (not `indirect`) needs that index: `setIndex: true` (the default) copies `data.index` into the geometry as three-mesh-bvh does. Several roots (one per group) are joined; version 0 files are read as three-mesh-bvh reads them.
- **Limit:** the tree must hold every triangle of the geometry. One built over a draw range or groups that leave triangles out is refused, since our trees hold every triangle.
- The core has the same without three: `serializeThreeMeshBvh(tree, { index })` and `meshBvhFromThreeMeshBvh(data, { positions, indices })` from `@pmndrs/bvh`.
Tested against three-mesh-bvh 0.9.18: its `deserialize` reads our trees and its raycasts, box casts, `validateBounds` and `getJSONStructure` agree with ours; its trees (indirect or not, with groups, version 0) read into ours give its hits.
## The helper
`new MeshBVHHelper(mesh, depth)` (or `BVHHelper`) is a `Group` that draws the tree's boxes down to `depth` (default 10) as line segments: `displayEdges = false` gives see-through faces, `displayParents` draws inner boxes too, with `color`, `opacity`, `edgeMaterial`, `meshMaterial` and `instanceId`. It follows the mesh's world matrix. Call `update()` after changing the tree or those fields. The boxes come from the core (`bvhHelperPositions`), so another engine can draw the same thing.
]]>
box.intersectsBox(bounds),
intersectsPoint: (point, index) => {
if (box.containsPoint(point)) inside.push(index); // the entry; its vertex is geometry.index?.getX(index) ?? index
return false;
},
});
const nearest = tree.closestPointToPoint(new Vector3(0, 2, 0)); // { point: Vector3, distance, index } or null
tree.refit(); // after editing the positions in place (bump the attribute's version)
const bytes = tree.serialize(); // new PointsBVH(geometry, { layout: PointsBVH.deserialize(bytes).layout })
```
The line trees' `shapecast` takes `intersectsLine(line, index, contained, depth)` with a `Line3`. `BVHHelper` draws these trees, and `getBVHExtremes`, `validateBounds` and `estimateMemoryInBytes` read them. Without three, the same trees are the core's [`CpuPointsBvh` and `CpuSegmentsBvh`](/bvh/cpu-queries/points-and-lines).
## Where three-mesh-bvh differs
We follow three where three-mesh-bvh 0.9.18 doesn't:
- it skips three's bounding-sphere test;
- it builds over the draw range and groups at build time, where three's raycast ignores groups and reads the draw range when it runs (for a range from an odd entry its `LineSegmentsBVH` still pairs entries from an even one, and its `LineLoopBVH` closes a range back to entry 0);
- outside `indirect: true` it reorders the geometry's index (and adds one to a geometry without), so a line hit's `index` changes meaning. Our trees never touch the geometry; `indirect` is ignored;
- `intersectsPoint` and `intersectsLine` get its buffer position; ours get the entry.
On an exact tie (two segments meeting at a vertex) our `firstHitOnly` keeps the lower entry, three's sorted order; three-mesh-bvh keeps the one its tree reaches first.
## Limits and fallbacks
- When the position attribute's version or the index changed since the build, raycasts use three's own (with a warning) until `tree.refit()` or `computeBoundsTree` runs again. A tree of the wrong kind (a `PointsBVH` on a `Line`) does too.
- Positions that aren't plain `f32` (normalized or interleaved attributes) are copied as `f32`, which may round them where three reads the exact value.
- An empty draw range on a `LineLoop` returns nothing; three reads entry -1 there and reports a `NaN` distance.
- `geometry.boundsTree` is typed as the mesh tree (`BvhBoundsTree`); for these objects it holds the class built, which `computeBoundsTree({ type })` returns typed.
- CPU only: `SceneTrees` and the GPU walk take triangles.
]]>
bool` | WGSL `bvhTraceClosest(ray) -> BvhHit` (`hit.t < 0` on a miss); TSL `bvh.traceClosest(origin, direction, tMin, tMax)` |
| `bvh.fns.raycastAnyHit(ray) -> bool` | WGSL `bvhTraceAny(ray) -> bool`; TSL `bvh.traceAny(...)` |
| (none) | Ray masks: `bvhTraceClosestMasked`, `bvhTraceAnyMasked`; `rayMaskFromLayers(camera.layers)` |
| `wgslTagFn` with `${bvh.fns.raycastFirstHit}` | three's `wgslFn(code, [bvh.module])`, calling the walk by name |
| `bvh.getShapecastFn({ shapeStruct, intersectsBoundsFn, intersectRangeFn, ... })` | `bvh.getShapecastFn({ shape, intersectsBounds, intersectsTriangle, keep })`, hooks as TSL `Fn`s or `wgslFn`s ([Shapecasts with TSL hooks](/bvh/three/trace-nodes#shapecasts-with-tsl-hooks)) |
| `rayStruct` (`origin, direction, maxDist`; 0 is unbounded) | `BvhRay(origin, tMin, direction, tMax)`, an explicit interval |
| `hit.dist`, `hit.didHit` | `hit.t`, and `hit.t >= 0.0` |
| `hit.normal` and `hit.side` | `hit.normal` (world, geometric, authored front side) and `hit.frontFace` |
| `hit.barycoord` (weights of a, b, c) | `hit.barycentrics`: weights of corners 1 and 2; corner 0 is `1 - u - v` |
| `hit.indices` | `hit.triangle`, the triangle's index in its mesh |
| `hit.objectIndex` | `hit.instance`; `sync.sourceOf(hit.instance)` gives `{ object, instanceId, group }` |
| Per-vertex attribute buffers | None: use `hit.triangle` and `hit.barycentrics` against your own attributes, or `hit.material` |
| `writeTransformData` override (material in the pad words) | `material(object, info)` in the sync's options, which becomes `hit.material` |
## Both libraries in one TypeScript program
Both packages add the same members to three's types, typed with their own classes: `BufferGeometry.boundsTree`, `computeBoundsTree` and `disposeBoundsTree`, and `BatchedMesh.boundsTrees`, `computeBoundsTree` and `disposeBoundsTree`. TypeScript can't merge two different types for one member, so it keeps the declaration it reads first and the other doesn't apply. A program that imports both (while migrating, or to compare them) can then refuse `BatchedMesh.prototype.computeBoundsTree = computeBatchedBoundsTree`, or type `batchedMesh.boundsTrees` as three-mesh-bvh's trees.
Our declarations can't be made to match three-mesh-bvh's: its types name its own classes (`GeometryBVH`), whose `traverse` and `refit` take other arguments than ours (our `traverse` is the shapecast box walk; our `refit` takes the new positions). The way around it:
- Keep three-mesh-bvh's types out of the program that uses ours. Importing anything from `three-mesh-bvh`, types included, brings its declarations in. If you need both, put the code that uses three-mesh-bvh in its own `tsconfig` project, as this repository does for its comparison suite.
- Or cast where the two meet: assign through `BatchedMesh.prototype as unknown as { computeBoundsTree: typeof computeBatchedBoundsTree }`, and read `batchedMesh.boundsTrees as (BvhBoundsTree | null)[] | null` and `geometry.boundsTree as BvhBoundsTree | undefined`.
- Either way, set `skipLibCheck`: the second declaration reports TS2717 in the other package's `.d.ts`.
At run time nothing clashes: whichever functions you assign to the prototypes are the ones that run.
## Partly there
- **`maxDepth`:** accepted, not honoured.
- **`setBoundingBox`, `verbose`, `onProgress`:** `onProgress` reports 0 and 1 only: tinybvh builds in one WebAssembly call and has no progress callback (its task hooks run only in threaded builds; ours is single-threaded). `verbose` is ignored.
There, with differences:
- **`serialize`:** three-mesh-bvh's format is read and written. Reading keeps the tree's shape and recomputes exact boxes; a tree built over a draw range or groups that leave triangles out can't be read.
- **`getShapecastFn`:** the triangle test gets one world-space triangle at a time, not a leaf's index range, and there is no result pointer: the shape goes in by value, and results come back through a `wgslFn`'s private state.
- **`StaticGeometryGenerator`:** it also bakes a mesh again when only a morph weight changed (three-mesh-bvh keeps the old pose then).
- **Points and lines:** CPU only (`SceneTrees` and the GPU walk take triangles), as three-mesh-bvh's are. Where three-mesh-bvh departs from three's raycast (no bounding-sphere test, the draw range and groups fixed at build time, the index reordered outside `indirect` mode), we follow three ([Points and lines](/bvh/three/points-and-lines#where-three-mesh-bvh-differs)).
## Missing
Nothing on the CPU. On the GPU nothing is missing either. SDF generation exists ([Signed distance fields](/bvh/tracing/sdf), `generateSdfTexture` in `/three`), and so do closest point, sphere and box tests, shapecasts (with WGSL or TSL hooks) and the WGSL helpers `intersectRayTriangle` and `closestPointToTriangle` ([Spatial queries on the GPU](/bvh/tracing/gpu-queries)); the queries run over the whole scene in world space rather than over one mesh. `ClusteredBVH`'s cut is `clusterTraceScene` ([Clustered top level](/bvh/scenes/clustered-top-level)), for scenes assembled without `SceneTrees`.
## Won't be done
- **GLSL and WebGL2** (`MeshBVHUniformStruct`, `BVHShaderGLSL`, the `VertexAttributeTexture` classes): WebGL2 isn't a target.
- **`ParallelMeshBVHWorker`:** it needs `SharedArrayBuffer` and cross-origin isolation. A large mesh goes to the GPU H-PLOC builder instead.
- **`useSharedArrayBuffer`:** our trees are copied to the GPU, and the worker pool needs no shared memory.
- **`sampleTrianglePoint` and `ndcToCameraRay`:** the package ends at the hit. A hit gives the triangle and its barycentrics; interpolating attributes and making camera rays belong to the renderer above it.
## What you get that three-mesh-bvh doesn't have
- GPU builds (H-PLOC and LBVH) and GPU refits (top level and per mesh), with nothing read back per frame.
- The same trees for three, for raw WebGPU passes, for workers and for other libraries on the device.
- The ray oracle on every builder and walk, and a watertight triangle test.
- Instance masks, a triangle filter and per-instance materials in the walk.
## When to stay with three-mesh-bvh
- You need WebGL2 GPU traversal, or GLSL.
- Memory matters more than ray speed. Our GPU scenes use about 7 times three-mesh-bvh's bytes beyond the geometry on Sponza (356 MiB against 51 MiB with defaults on both sides; 6.5 times on Bistro exterior). Indexed leaves, off by default, bring Sponza to 226 MiB. Our CPU trees (`computeBoundsTree`) keep 64-byte nodes: 8-9 times. See [Memory](/bvh/performance/memory).
- You rely on years of other people's use: this package is new.
]]>
\[!NOTE] Every number here is from one Apple M5 Pro (Node 22 and headless Chrome), and is **indicative**. The suite has not run on the RTX 3060 yet; our own levers' RTX 3060 numbers are in [Builds and tracing](/bvh/performance/builds-and-tracing). The GPU rows were taken with `f32` nodes, the default before 2026-11-13 (quantized nodes are the default now). The CPU box, closest-point and refit numbers are from the CPU query pass (2026-11-13), measured while other projects loaded the machine (load average 8–10): ranges over two full runs before and two after.
## The libraries
- [three-mesh-bvh](https://github.com/gkjohnson/three-mesh-bvh) 0.9.18: `MeshBVH` (CENTER and SAH), `ObjectBVH`, and `three-mesh-bvh/webgpu`.
- [three](https://github.com/mrdoob/three.js) 0.187: `Mesh.raycast`, the no-BVH baseline.
- [bvh-tree](https://github.com/benraziel/bvh-tree) 1.0.1: a plain-JS triangle BVH.
- [Babylon.js](https://github.com/BabylonJS/Babylon.js) 9.35: an engine's own picking, with and without the submesh octree.
- [bvh.js](https://github.com/agargaro/bvh.js) 0.0.13: a scene-level box BVH (objects, not triangles).
- [Rapier](https://github.com/dimforge/rapier.js) 0.21: a physics engine's ray, point and shape queries on a trimesh collider.
## Headline results
| What | Result (ours = 1; above 1 means faster than ours) |
| ------------------------------------------------------- | --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- |
| CPU closest-hit rays, Sponza (5.74M triangles) | ours 580k rays/s; three-mesh-bvh 0.75 (SAH) and 0.57 (CENTER), Rapier 0.95, bvh-tree 0.12 |
| Tree quality, Sponza (SAH cost, lower is better) | ours 90; three-mesh-bvh 122 (SAH) and 141 (CENTER); bvh-tree 205 |
| GPU rays, against three-mesh-bvh/webgpu (paired rounds) | ours 0.96–1.12× theirs closest-hit and 1.25–1.28× any-hit on Sponza and the knot; 0.85–0.91× closest on the furnished room. Any-hit from outside the room: 0.32× with the default order, 1.73× with `anyHitOrder: 'larger'` |
| Scene-level trees, 10k objects | ours is ahead of three-mesh-bvh's `ObjectBVH` on every query |
## Where other libraries win
Measured on the same harness. These are open items, not footnotes:
- **Rapier** ties our closest point on the torus knot (0.99–1.04×). Until the CPU query pass of 2026-11-13 it answered box queries 2.3–2.7× and closest point 1.7–2.4× faster than ours; ours now leads both everywhere else (Rapier 0.56–0.88× on boxes, 0.64–0.77× on closest point). Both queries became flat walks over the typed arrays with no objects per node or triangle, giving the same answers bit for bit ([`compare/RESULTS.md`](https://github.com/pmndrs/bvh/blob/main/compare/RESULTS.md), "compare/queries").
- **three-mesh-bvh, CPU:** refits Sponza (5.7M triangles) 1.3–1.5× faster. It was 6–7× faster until our refit stopped sorting and allocating per node, and 1.6–2× until the CPU query pass made it one pass. The knot and the room are now level (0.93–1.06×). We still write 48-byte triangle records and 3 million 64-byte nodes, where three-mesh-bvh writes 1.7 million 32-byte nodes over the app's positions. Its box queries (1.2–1.4× ours before) and closest point are 0.23–0.54× ours now. With SAH its sphere queries are a little faster than ours on the knot (1.05–1.13×) and Sponza (0.95–1.24×).
- **three-mesh-bvh, GPU:** its closest-hit walk is 1.1–1.2× ours on the furnished room. Its any-hit from outside the room was 3.2× our default kernel's: our any-hit enters the farther child first (right for shadow rays from surfaces), and a few rays per SIMD group of 32 went deep into the far side's furniture. With `anyHitOrder: 'larger'` (enter the larger child first) ours is 1.73× theirs on those rays; it stays a setting because it costs 0.78× on merged surface rays on the M5 and 0.80–0.87× on the RTX 3060 ([trace design](https://github.com/pmndrs/bvh/blob/main/docs/internals/design/trace.md)), and merged trees are the default.
- **bvh.js** builds its scene tree about 3× faster.
- **Memory:** our CPU trees (`CpuMeshBvh`, what the suite measures) hold about 9–10× more bytes beyond the app's geometry than three-mesh-bvh, because our triangle records copy the corners. On the GPU the default scene now has quantized nodes: Sponza 355.5 MiB beyond the geometry against three-mesh-bvh's 51.2, about 7×. Indexed leaves take it to 225.5 ([memory page](/bvh/performance/memory)). Building one huge mesh with tinybvh grows its WebAssembly memory to about 230 bytes per triangle while the build runs (Sponza as one mesh: 1.3 GiB); the builder now drops that memory afterwards and the worker pool ends such a worker, so the build leaves 391 MiB behind instead of 1.7 GiB ([workers](/bvh/workers/workers)).
## The compare pages
The suite also runs live in the [examples site](/bvh/examples/examples) (`examples/compare/`): each page puts the same geometry through both libraries, checks every answer against ours, shows the tables and the CSV rows, and has a "what else you can do" box with one thing only our pipeline does. Smoke runs use small scenes and short timings; the numbers for this page come from full runs on the RTX 3060 and the M5, which are still to be taken for the two newest pages.
| Page | What it compares | What else (live) |
| ---------------------- | ----------------------------------------------------------------------------------------------------------------------------------------------------------------- | ---------------------------------------------------------------------------- |
| `compare/raycast` | CPU first and all hits per second, every library; a GPU batch against three-mesh-bvh/webgpu | the batch is a raw WebGPU pass three never sees |
| `compare/build` | build, refit, memory; main-thread stalls of builds on the main thread and in workers | a GPU H-PLOC build of the same mesh |
| `compare/tree-quality` | SAH cost, depth, boxes, leaves, bytes | three builders, one layout |
| `compare/queries` | box, sphere and closest point (three-mesh-bvh, Rapier) | the GPU builder's tree answers the same CPU queries |
| `compare/scene` | scene trees over thousands of moving objects (bvh.js, `ObjectBVH`) | the GPU top-level refit every frame |
| `compare/gpu` | GPU closest and any hit against three-mesh-bvh/webgpu, paired rounds | a GPU-built tree traced by the same kernel |
| `compare/sdf` | SDF generation on the GPU against three-mesh-bvh's `webgpu_sdfGeneration` | the scene's GPU-built tree straight into a three texture |
| `compare/skinned` | skinned meshes kept on their pose every frame: three-mesh-bvh's `SkinnedMeshBVH.refit()` on the CPU against our GPU pose pass and refit, CPU and GPU ms per frame | a plain WebGPU pass, never seen by three, traces the refit trees every frame |
| `compare/pathtracer` | the same small path tracer on three-mesh-bvh/webgpu's WGSL functions and on our walk: Mrays/s for the whole tracer, its closest-hit rays and its any-hit rays | the scene's GPU-built trees traced by the same kernel |
### Method: `compare/skinned`
Nine skinned characters (tubes on a chain of six bones, `?characters=`, `?rings=`). In each measured frame both libraries see the same pose (the bones are set from the frame's time), in alternating order:
- **three-mesh-bvh** (its `skinnedMesh` example): one `SkinnedMeshBVH` per character and `refit()` each frame, which skins every vertex on the CPU (`SkinnedMesh.getVertexPosition`). CPU ms is the refits' wall time. Its trees stay on the CPU; to trace the pose on the GPU it re-packs them with `BVHComputeData.update()`, which skins every vertex again. That is a row of its own (the upload itself happens at the next compute and is not counted).
- **ours**: `SceneTreesObject3DSync` with the renderer poses each `SkinnedMesh` on the GPU (`BvhPosePass`) and `SceneTrees.setPose` refits its tree from that buffer, in the frame's encoder. CPU ms is the sync and the recording; GPU ms is the pose passes (three's compute timestamps) plus what `SceneTrees.update` records (its `timestampWrites`), or without `timestamp-query` the wall time to the queue being done (an upper bound).
Medians over the measured frames. Tree quality is reported beside the times: three-mesh-bvh's summed SAH score against its fresh build (`getBVHExtremes`), and our refit and drift-rebuild counts. The check: on a frozen pose, a top-down grid of rays through our GPU-refit trees agrees with three-mesh-bvh's refit trees (CPU raycast) on every ray away from a silhouette.
### Method: `compare/pathtracer`
One kernel (`examples/three/pathtracer/kernel.ts`: jittered camera rays, PCG random numbers, diffuse bounces, one sun shadow ray per hit, accumulation) over two walks: ours through `BvhTraceNodes` (`traceClosest`, `traceAny`, the library's defaults: merged static meshes, quantized nodes), and three-mesh-bvh's `BVHComputeData` (a `MeshBVH` with SAH per geometry) through `bvh_RaycastFirstHit` and `bvh_RaycastAnyHit` in a `wgslFn`. Both read one palette colour per mesh, so the shading is the same. Measured in paired rounds (the two back to back, the order reversed every other round, the ratio taken within each round):
- **path**: every ray of the full tracer, closest and any hit;
- **closest**: the tracer with its shadow rays compiled out (the same closest-hit rays, since the shadow ray draws no random number);
- **any**: the shadow rays alone, derived as their count over the time the full tracer takes beyond the closest-only one (noisier than the other two).
Rays are counted in the kernel (one atomic per pixel); time is three's compute timestamps, else the wall time of one dispatch with the queue drained before and after. Each pixel's first hit is checked against ours; a pixel through a silhouette may graze either way between two different triangle tests, so up to 0.1% of pixels may differ.
## three-mesh-bvh's examples, ported
These are three-mesh-bvh's own examples on our API (`@pmndrs/bvh/three`), not timed comparisons. Each page says where it departs from the original, and its smoke run checks our answers (against three-mesh-bvh's where the example asks a query both answer).
| Page | Shows | Departure from the original |
| ------------------------- | -------------------------------------------------------------------------------------------------------------- | ------------------------------------------------------------------------- |
| `three/shapecast` | `intersectsSphere`, `intersectsBox`, `intersectsGeometry` against a spinning knot | none |
| `three/distancecast` | `closestPointToGeometry` (tree against tree) and a marching-cubes volume of `closestPointToPoint` | three's seeded `SimplexNoise` |
| `three/characterMovement` | a capsule walked through a level baked by `StaticGeometryGenerator`, pushed out of what `shapecast` hands back | a level of three's primitives instead of a downloaded dungeon |
| `three/physics` | spheres pushed out of an environment's triangles (`shapecast`, nearest boxes first) | an environment of three's primitives instead of a downloaded jungle |
| `three/sculpt` | brushes that find vertices with `shapecast` (contained boxes whole), then a refit | our `refit()` is whole-tree; three-mesh-bvh refits only the visited nodes |
| `three/selection` | lasso and box selection narrowed by each box's screen hull | the knot stays indexed |
]]>
` or a dropped `.bvh` loads another. |
]]>