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!
Tools
Games
Path Tracing
External Projects
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 ] );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 );import { StaticGeometryGenerator } from 'three-mesh-bvh';
const generator = new StaticGeometryGenerator( [ ...skinnedMeshes ] );
const geometry = generator.generate();
geometry.computeBoundsTree();
// ...
// update the geometry in place
generator.generate( geometry );
geometry.boundsTree.refit();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;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;
} );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.
Option for splitting each BVH node down the center of the longest axis of the bounds.
This is the fastest construction option and will yield a good, performant bounds.
Option for splitting each BVH node at the average point along the longest axis for all triangle centroids in the bounds.
This strategy may be better than CENTER with some geometry.
Option to use a Surface Area Heuristic to split the bounds more optimally. This SAH implementation tests 32 discrete splits in each node along each axis to determine which split is the lowest cost.
This is the slowest construction option but will yield the best bounds of the three options and use the least memory.
Indicates the shape did not intersect the given bounding box.
Indicates the shape did intersect the given bounding box.
Indicate the shape entirely contains the given bounding box.
The MeshBVH generation process modifies the geometry's index bufferAttribute in place to save memory. The BVH construction will use the geometry's boundingBox if it exists or set it if it does not. The BVH will no longer work correctly if the index buffer is modified.
Only triangles within the geometry's draw range (or provided range option) are included in the BVH. When a geometry has multiple groups, only triangles within the defined group ranges are included. Triangles in gaps between groups are excluded.
Note that all query functions expect arguments in local space of the BVH and return results in local space, as well. If world space results are needed they must be transformed into world space using object.matrixWorld.
static serialize( bvh : MeshBVH, options : Object = null ) : SerializedBVHGenerates a representation of the complete bounds tree and the geometry index buffer which can be used to recreate a bounds tree using the deserialize function. The serialize and deserialize functions can be used to generate a MeshBVH asynchronously in a background web worker to prevent the main thread from stuttering. The BVH roots buffer stored in the serialized representation are the same as the ones used by the original BVH so they should not be modified. If SharedArrayBuffers are used then the same BVH memory can be used for multiple BVH in multiple WebWorkers.
bvh is the MeshBVH to be serialized. The options object can have the following fields:
{
// if true then a clone of the `geometry.index.array` and MeshBVH buffers are made which slightly slower but
// ensures modifications do not affect the serialized content. Can be set to "false" if it is guaranteed that
// no modifications will be made, to save memory, or transfer and share them across WebWorkers if SharedArrayBuffers
// are being used.
cloneBuffers: true
}static deserialize( data : SerializedBVH, geometry : BufferGeometry, options : Object = null ) : MeshBVHReturns a new MeshBVH instance from the serialized data. geometry is the geometry used to generate the original BVH data was derived from. The root buffers stored in data are set directly on the new BVH so the memory is shared.
The options object can have the following fields:
{
// If true then the buffer for the `geometry.index` attribute is set from the serialized
// data attribute or created if an index does not exist.
setIndex: true,
}NOTE: In order for the bounds tree to be used for casts the geometry index attribute must be replaced by the data in the SeralizedMeshBVH object.
constructor( geometry : BufferGeometry, options : Object )Constructs the bounds tree for the given geometry and produces a new index attribute buffer. A reference to the passed geometry is retained. The available options are
{
// Which split strategy to use when constructing the BVH.
strategy: CENTER,
// The maximum depth to allow the tree to build to.
// Setting this to a smaller trades raycast speed for better construction
// time and less memory allocation.
maxDepth: 40,
// The number of triangles to aim for in a leaf node. Setting this to a lower
// number can improve raycast performance but increase construction time and
// memory footprint.
maxLeafTris: 10,
// If true then the bounding box for the geometry is set once the BVH
// has been constructed.
setBoundingBox: true,
// If true then the MeshBVH will use SharedArrayBuffer rather than ArrayBuffer when
// initializing the BVH buffers. Geometry index data will be created as a
// SharedArrayBuffer only if it needs to be created. Otherwise it is used as-is.
useSharedArrayBuffer: false,
// An optional function that takes a "progress" argument in the range [0, 1]
// indicating the progress along BVH generation. Useful primarily when generating
// the BVH asynchronously with the GenerateMeshBVHWorker class.
onProgress: null,
// If false then an index buffer is created if it does not exist and is rearranged
// to hold the bvh structure. If true then a separate buffer is created to store the
// structure and the index buffer (or lack thereof) is retained. This can be used
// when the existing index layout is important or groups are being used so a
// single BVH hierarchy can be created to improve performance.
indirect: false,
// Print out warnings encountered during tree construction.
verbose: true,
// If given, the MeshBVH will be computed for the given range on the geometry.
// If not specified, geometry.drawRange is used.
range: { start: number, count: number }
}NOTE: The geometry's index attribute array is modified in order to build the bounds tree unless indirect is set to true. If the geometry has no index then one is added if indirect is set to false.
resolveTriangleIndex( index : Number ) : NumberHelper function for use when indirect is set to true. This function takes a triangle index in the BVH layout and returns the associated triangle index in the geometry index buffer or position attribute.
raycast( ray : Ray, side : FrontSide | BackSide | DoubleSide = FrontSide, near : Number = 0, far : Number = Infinity ) : Array<RaycastHit>raycast( ray : Ray, material? : Array<Material> | Material, near : Number = 0, far : Number = Infinity ) : Array<RaycastHit>Returns all raycast triangle hits in unsorted order. It is expected that ray is in the frame of the BVH already. Likewise the returned results are also provided in the local frame of the BVH. The side identifier is used to determine the side to check when raycasting or a material with the given side field can be passed. If an array of materials is provided then it is expected that the geometry has groups and the appropriate material side is used per group.
Note that unlike three.js' Raycaster results the points and distances in the intersections returned from this function are relative to the local frame of the MeshBVH. When using the acceleratedRaycast function as an override for Mesh.raycast they are transformed into world space to be consistent with three's results.
raycastFirst( ray : Ray, side : FrontSide | BackSide | DoubleSide = FrontSide, near : Number = 0, far : Number = Infinity ) : RaycastHitraycastFirst( ray : Ray, material : Array<Material> | Material, near : Number = 0, far : Number = Infinity ) : RaycastHitReturns the first raycast hit in the model. This is typically much faster than returning all hits. See raycast for information on the side and material options as well as the frame of the returned intersections.
intersectsSphere( sphere : Sphere ) : BooleanReturns whether or not the mesh intersects the given sphere.
intersectsBox( box : Box3, boxToBvh : Matrix4 ) : BooleanReturns whether or not the mesh intersects the given box.
The boxToBvh parameter is the transform of the box in the meshes frame.