three-mesh-bvh

A Bounding Volume Hierarchy (BVH) implementation to speed up raycasting and enable spatial queries against three.js meshes. See the associated Wikipedia article for more information on bounding volume hierarchies and how they work.

Casting 500 rays against an 80,000 polygon model at 60fps!

Examples

Raycasting

Skinned geometry

Point cloud intersection

Line intersection

Shape intersection

Geometry edge intersection

SDF generation

WebWorker generation

BVH options inspector

BatchedMesh Raycasting

Tools

Sculpting

Distance comparison

Triangle painting

Lasso selection

Clipped edges

Geometry voxelization

Games

Sphere physics collision

Player movement

Path Tracing

Simple GPU Path Tracing

Lambert GPU Path Tracing

CPU Path Tracing

Gem Refraction Path Tracing

Object Hierarchy BVH

Accelerated Scene Raycasting

Skinned Meshes

Frustum Culling

External Projects

three-gpu-pathtracer

three-bvh-csg

three-edge-projection

Use

Using pre-made functions

import * as THREE from 'three';
import {
	computeBoundsTree, disposeBoundsTree,
	computeBatchedBoundsTree, disposeBatchedBoundsTree, acceleratedRaycast,
} from 'three-mesh-bvh';

// Add the extension functions
THREE.BufferGeometry.prototype.computeBoundsTree = computeBoundsTree;
THREE.BufferGeometry.prototype.disposeBoundsTree = disposeBoundsTree;
THREE.Mesh.prototype.raycast = acceleratedRaycast;

THREE.BatchedMesh.prototype.computeBoundsTree = computeBatchedBoundsTree;
THREE.BatchedMesh.prototype.disposeBoundsTree = disposeBatchedBoundsTree;
THREE.BatchedMesh.prototype.raycast = acceleratedRaycast;

// Generate geometry and associated BVH
const geom = new THREE.TorusKnotGeometry( 10, 3, 400, 100 );
const mesh = new THREE.Mesh( geom, material );
geom.computeBoundsTree();

// Or generate BatchedMesh and associated BVHs
const batchedMesh = new THREE.BatchedMesh( ... );
const geomId = batchedMesh.addGeometry( geom );
const instId = batchedMesh.addGeometry( geom );

// Generate bounds tree for sub geometry
batchedMesh.computeBoundsTree( geomId );

Or manually building the BVH

import * as THREE from 'three';
import { MeshBVH, acceleratedRaycast } from 'three-mesh-bvh';

// Add the raycast function. Assumes the BVH is available on
// the `boundsTree` variable
THREE.Mesh.prototype.raycast = acceleratedRaycast;

// ...

// Generate the BVH and use the newly generated index
geom.boundsTree = new MeshBVH( geom );

And then raycasting

// Setting "firstHitOnly" to true means the Mesh.raycast function will use the
// bvh "raycastFirst" function to return a result more quickly.
const raycaster = new THREE.Raycaster();
raycaster.firstHitOnly = true;
raycaster.intersectObjects( [ mesh ] );

Additional Geometry BVHs

In addition to MeshBVH for triangle meshes, the library provides specialized BVH implementations for other geometry types:

• PointsBVH - For THREE.Points geometries
• LineBVH - For THREE.Line geometries
• LineLoopBVH - For THREE.LineLoop geometries
• LineSegmentsBVH - For THREE.LineSegments geometries

These can be used with the extension functions by passing a type option into "computeBoundsTree" or constructing them explicitly:

import { PointsBVH } from 'three-mesh-bvh';

// For point clouds
THREE.Points.prototype.raycast = acceleratedRaycast;

const points = new THREE.Points( geometry, material );
geometry.computeBoundsTree( { type: PointsBVH } );

// Or create directly
geometry.boundsTree = new PointsBVH( geometry );

Each BVH type implements a core API including shapecast & raycastObject3D for its specific primitive type. See the point cloud intersection & line intersection examples for a working demonstration. Some features like webworker-generation and serialization are not supported at the moment.

Additional BVHs

A SkinnedMeshBVH for SkinnedMeshes and ObjectBVH for constructing scene-wide BVH to query a hierarchy of objects. These are recently added so the APIs may change over time.

Querying the BVH Directly

import * as THREE from 'three';
import { MeshBVH, acceleratedRaycast } from 'three-mesh-bvh';

let mesh, geometry;
const invMat = new THREE.Matrix4();

// instantiate the geometry

// ...

const bvh = new MeshBVH( geometry );
invMat.copy( mesh.matrixWorld ).invert();

// raycasting
// ensure the ray is in the local space of the geometry being cast against
raycaster.ray.applyMatrix4( invMat );
const hit = bvh.raycastFirst( raycaster.ray );

// results are returned in local spac, as well, so they must be transformed into
// world space if needed.
hit.point.applyMatrixWorld( mesh.matrixWorld );

// spherecasting
// ensure the sphere is in the local space of the geometry being cast against
sphere.applyMatrix4( invMat );
const intersects = bvh.intersectsSphere( sphere );

Serialization and Deserialization

const geometry = new KnotGeometry( 1, 0.5, 40, 10 );
const bvh = new MeshBVH( geometry );
const serialized = MeshBVH.serialize( bvh );

// ...

const deserializedBVH = MeshBVH.deserialize( serialized, geometry );
geometry.boundsTree = deserializedBVH;

Asynchronous Generation

NOTE WebWorker syntax is inconsistently supported across bundlers and sometimes not supported at all so the GenerateMeshBVHWorker class is exported separately via three-mesh-bvh/worker subpath. If needed the code from src/worker can be copied and modified to accommodate a particular build process.

import { GenerateMeshBVHWorker } from 'three-mesh-bvh/worker';

// ...

const geometry = new KnotGeometry( 1, 0.5, 40, 10 );
const worker = new GenerateMeshBVHWorker();
worker.generate( geometry ).then( bvh => {

    geometry.boundsTree = bvh;

} );

Parallel BVH generation is also supported using "ParallelMeshBVHWorker", which requires support for SharedArrayBuffer. If SharedArrayBuffer is not available it falls back to "GenerateMeshBVHWorker". It is recommended that geometry passed to this function have position and index with SharedArrayBuffer arrays, otherwise buffer copies must be made.

import { ParallelMeshBVHWorker } from 'three-mesh-bvh/worker';

// ...

const geometry = new KnotGeometry( 1, 0.5, 40, 10 );
const worker = new ParallelMeshBVHWorker();
worker.generate( geometry ).then( bvh => {

    geometry.boundsTree = bvh;

} );

BVH Queries in a Shader

See the shader implementation in the simple GPU Path Tracing example for an example on how to perform BVH ray queries in a shader. Or the GPU SDF Generation example for how to perform distance and closest point to point queries in a shader.

API

See API.md for full API documentation.

Gotchas

• When querying the MeshBVH directly all shapes and geometry are expected to be specified in the local frame of the BVH. When using three.js' built in raycasting system all results are implicitly transformed into world coordinates.
• A bounds tree can be generated for either an indexed or non-indexed BufferGeometry, but an index will be produced and retained as a side effect of the construction unless the "indirect" option is used.
• The bounds hierarchy is not dynamic, so geometry that uses morph targets or skinning cannot be used. Though if vertex positions are modified directly the refit function can be used to adjust the bounds tree.
• If the geometry is changed then a new bounds tree will need to be generated or refit.
• InterleavedBufferAttributes are not supported with the geometry index buffer attribute.
• A separate bounds tree root is generated for each geometry group, which could result in less than optimal raycast performance on geometry with lots of groups. Triangles excluded from these groups are not included in the BVH.
• Due to errors related to floating point precision it is recommended that geometry be centered using BufferGeometry.center() before creating the BVH if the geometry is sufficiently large or off center so bounds tightly contain the geometry as much as possible.

Running Examples Locally

To run the examples locally:

• Run npm start
• Then visit localhost:5173/<demo-name>.html

Where <demo-name> is the name of the HTML file from example folder.

Used and Supported by

...and more!