CPU raycast in three

computeBoundsTree and acceleratedRaycast as drop-ins, a ray against the whole scene, and builds in a worker.

These are drop-ins for three-mesh-bvh's functions of the same names. They run the core's CPU walk over one tinybvh tree per geometry.

import { BufferGeometry, Mesh as ThreeMesh, Raycaster, SphereGeometry, MeshBasicMaterial, DoubleSide, Vector3 } from 'three';
import { acceleratedRaycast, computeBoundsTree, disposeBoundsTree, prepareBoundsTrees, SAH } from '@pmndrs/bvh/three';

await prepareBoundsTrees(); // once: loads tinybvh
BufferGeometry.prototype.computeBoundsTree = computeBoundsTree;
BufferGeometry.prototype.disposeBoundsTree = disposeBoundsTree;
ThreeMesh.prototype.raycast = acceleratedRaycast;

const mesh = new ThreeMesh(new SphereGeometry(1, 256, 128), new MeshBasicMaterial({ side: DoubleSide }));
mesh.geometry.computeBoundsTree({ strategy: SAH, maxLeafSize: 8 }); // three-mesh-bvh's options are accepted

const raycaster = new Raycaster(new Vector3(0, 0, 5), new Vector3(0, 0, -1));
raycaster.firstHitOnly = true;
const [hit] = raycaster.intersectObject(mesh); // distance, point, face, faceIndex, barycoord, uv, normal, ...

What it returns

The same intersections as three's Mesh.raycast:

the draw range and, with an array of materials, the groups; ranges off a multiple of 3 and overlapping groups too;
each material's side (front, back or double), read at every raycast;
raycaster.near and far;
the same fields: distance, point, face (a, b, c, normal, materialIndex), faceIndex, barycoord, uv, uv1 and normal;
InstancedMesh and BatchedMesh through Mesh.raycast (a tree per batched geometry with computeBatchedBoundsTree, below, or one over the whole batch with batchedMesh.geometry.computeBoundsTree()).

Without firstHitOnly every hit is returned, as three does. Tested against three on 8,000 random rays, and 5,000 more through ranges and groups off a multiple of 3. The one difference: three reports a triangle that reads past the end of the index at a NaN distance; we report nothing there.

When it falls back to three's raycast

The geometry has no tree.
A SkinnedMesh, or a mesh with morph targets (three poses each vertex on the CPU; that is exact), unless its tree is a SkinnedMeshBVH, which holds the pose (A tree that follows the pose).
The position attribute's version, or the index, changed since computeBoundsTree. It warns once and stays on three's raycast until geometry.boundsTree.refit() (same index) or computeBoundsTree runs again.

BatchedMesh

A tree per geometry of a BatchedMesh, as three-mesh-bvh's computeBatchedBoundsTree makes them: each instance's raycast walks only its own geometry's tree.

import { BatchedMesh, Mesh } from 'three';
import { acceleratedRaycast, computeBatchedBoundsTree, disposeBatchedBoundsTree } from '@pmndrs/bvh/three';

Mesh.prototype.raycast = acceleratedRaycast; // other meshes; the BatchedMesh needs only its own line below
BatchedMesh.prototype.raycast = acceleratedRaycast; // each instance walks its geometry's tree
BatchedMesh.prototype.computeBoundsTree = computeBatchedBoundsTree;
BatchedMesh.prototype.disposeBoundsTree = disposeBatchedBoundsTree;

batched.computeBoundsTree(); // a tree per geometry, in batched.boundsTrees
// After batched.setGeometryAt(changedGeometry, geometry): that geometry's tree again, the others refitted.
batched.computeBoundsTree(changedGeometry);
for (const tree of batched.boundsTrees ?? []) tree?.refit();

computeBoundsTree(index = -1, options) builds every geometry's tree into batchedMesh.boundsTrees (by geometry id) and returns the array, or builds one geometry's tree and returns it (null past the geometries, or for a deleted one). The options are computeBoundsTree's. disposeBoundsTree(index = -1) drops one tree or all of them.
Each tree is a BvhBoundsTree over that geometry's range of the batched geometry. The hits are three's: faceIndex, face and the interpolated attributes over the whole batched geometry, and batchId. three-mesh-bvh reorders the batch's index in place, so its faceIndex numbers differ from three's; ours don't.
BatchedMesh.prototype.raycast = acceleratedRaycast is enough for a BatchedMesh: it runs three's BatchedMesh.raycast loop (active, visible instances, each geometry's draw range, matrix, box and sphere) through a stand-in of its own that walks the trees, so Mesh.prototype.raycast may stay three's. With only Mesh.prototype.raycast set, three's own BatchedMesh.raycast sends its stand-in there and the trees are walked too. A geometry with no tree gets three's raycast either way.
TypeScript: with three-mesh-bvh's types in the same program, computeBoundsTree and boundsTrees on BatchedMesh may take three-mesh-bvh's types; see Both libraries in one TypeScript program.
After setGeometryAt, or another edit of the batch's positions or index, the trees are stale: raycasts fall back to three's, with one warning, until the changed geometry's tree is built again and the others are refitted or rebuilt.
A geometry whose index count isn't a multiple of 3 loses the one triangle three would read past its range.

Tested against three's raycast and three-mesh-bvh's accelerated BatchedMesh raycast, indexed and not, and with only BatchedMesh.prototype.raycast set.

A whole scene

BvhSceneRaycaster is three-mesh-bvh's ObjectBVH: one walk over the scene's top level and its mesh trees, in place of a raycast per object.

import { BvhSceneRaycaster, raycastScene } from '@pmndrs/bvh/three';
import { Frustum, Matrix4, type Camera } from 'three';

await prepareBoundsTrees();
const picker = new BvhSceneRaycaster(scene); // a tree per geometry and range, and the top level
const hits = raycastScene(picker, raycaster); // what raycaster.intersectObject(scene, true) returns

// After objects move, show, hide, or come and go:
scene.updateMatrixWorld();
picker.update(); // the top level only, unless meshes changed

const frustum = new Frustum().setFromProjectionMatrix(new Matrix4().multiplyMatrices(camera.projectionMatrix, camera.matrixWorldInverse));
const seen = picker.intersectsFrustum(frustum, camera.layers); // [{ object, instanceId, group }]

It returns three's intersectObject(root, true) with three's own Mesh.raycast: the same triangles, side, near/far, instanceId and batchId, sorted. Hidden objects are hit too, as three's Raycaster hits them (includeHidden: false skips them). raycaster.firstHitOnly returns the one closest hit over the scene.
Multi-material meshes are folded as bvhSceneFromObject3D and the sync fold them (one instance per object, the groups in one mesh; multiMaterial: 'groups' splits them), so picker.sourceOf(i) is the same source as scene.sources[i]. Each hit still gets its group's side and face.materialIndex; picker.meshSourceOf(i) with threeGroupOf or threeMaterialOf gives a hit's group from its triangle.
Differs from three: layers 8-31 aren't seen, skinned and morphed meshes are read in their rest pose, and points, lines and sprites aren't read.
Raycasts see the scene as of the last update(). Call scene.updateMatrixWorld() and update() after objects move, show or hide, come or go, and after geometry edits. With the same meshes it rebuilds only the top level.
intersectsFrustum(frustum, layers) walks the top level with three's Frustum.intersectsBox and returns the objects and instances whose world box meets it.

Tested against three's intersectObject on 10,000 rays before and after moves, and 300 camera frustums against brute force.

Shapecast over the objects

picker.shapecast(callbacks) is three-mesh-bvh's ObjectBVH.shapecast: the walk over the objects' world boxes that the raycast uses, with your own tests. Use it to find what a shape (a sphere, a box, a capsule) might touch, then test those objects' triangles.

import { BvhSceneRaycaster, CONTAINED, INTERSECTED, NOT_INTERSECTED } from '@pmndrs/bvh/three';
import type { Object3D, Sphere } from 'three';

const picker = new BvhSceneRaycaster(scene); // after `await prepareBoundsTrees()`
const near: Object3D[] = [];
picker.shapecast({
    // World boxes of the objects (and instances); CONTAINED takes a subtree whole.
    intersectsBounds: (box) => {
        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

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). 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. In the browser (three/raycast example, headless Chrome on the M5): 0.40 million raycasts per second against three's 306.

src/three/raycast.ts

Edit this page