Three-mesh-bvh: A plugin for fast geometry raycasting and spatial queries!

Hello! I wanted to share the three-mesh-bvh package I maintain which, among other things, can be used to greatly improve raycasting performance by multiple orders of magnitude against highly complex geometry as well as enable a variety of spatial queries against the triangles. It’s designed to be memory conscious, fast, and able to be generated asynchronously in a web worker.

It started off as a project to learn about spatial data structures and through need, suggestions, and contributions has grown into a very capable and well tested package for querying detailed geometry like medical, CAD, or photogrammetry models or even moderately detailed geometry in more constrained environments like WebVR or mobile phones.

If you check out the examples listed in the README you can see additional use case demos including basic ball and character controller physics, lasso triangle selection, geometry intersection detection, geometric triangle triangle painting, and others! There are some other examples I have in the works which I’ll be excited to share here once they’re added.

Bug reports, feature suggestions, PRs, and other contributions welcome! And feel free to share projects if you wind up using it. I always appreciate seeing how my work is used!

Garrett

13 Likes

Hello @gkjohnson , I tested a TorusKnotGeometry

      let mul = 8
      const geometry = new THREE.TorusKnotGeometry(10, 3, 100 * mul, 16 * mul)

which will let fps drop to 1 while keep moving mouse with defualt rarycaster.
Now with three-mesh-bvh, can smoothly run at full 300fps! So Great!

No need hand-made low poly, no need downgrade to rough boudingbox, just add these codes do the magic!

// Import via ES6 modules
import { computeBoundsTree, disposeBoundsTree, acceleratedRaycast } from 'three-mesh-bvh';

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

// Generate geometry and associated BVH
geometry.computeBoundsTree();

One question is, is there any standalone js or jsm bundle file?

I currently have a project that urgently needs this library, but this project uses pure <script> and <script type="module">, not cli.

I didn’t find a file like build/three.js or build/three.module.js after run npm run build.

PS: I need jsm version first. :innocent:

1 Like

I have case where I have 80,000 meshes of relatively few polygons each. Would this improve raycasting of this case, or is it only designed for high-poly meshes (not many meshes)?

1 Like

@gonnavis

Thanks! Glad it works well for you.

One question is, is there any standalone js or jsm bundle file?

There is a UMD version of the library in the /umd folder which you can use as a global script include and adds all imports to a global MeshBVHLib variable. There’s no bundled jsm version, yet, but you should be able to make one easily by modifying this rollup config to output a module rather than umd. I probably won’t be able to get to it for a bit myself but if you want to make a PR to make a jsm build as well as a umd one I’d be happy to provide some guidance and get it merged!

@prominent

I have case where I have 80,000 meshes of relatively few polygons each. Would this improve raycasting of this case, or is it only designed for high-poly meshes (not many meshes)?

This library is intended to speed up raycasting against individual meshes with complex geometry rather than many objects. If your objects are static you can merge them into one mesh and build a BVH using that for raycasting, though.

1 Like

Thanks a lot! I’ll try these two methods.

Hi @gkjohnson,

It’s a wonderful library that you have developed! Kudos!

I have been looking at this library for a week and have a couple of questions that I have been pondering over.

In the case of a WebXR based VR application, how would I use this library if I had to check constantly for the intersection of "gamepad controllers" and a few “interactive” grabbable objects in the scene?

Let’s consider that in my application I have a few objects that I can interact with. Other objects are static and make a part of the environment. The only objects of interest are the ones that the users can interact with which are spread across the scene.

In that case, should I multi ray cast from the gamepad controllers (to get better intersection results and not just in a single direction) or should I check for the intersection of the gamepad’s bounding box/sphere with the BVH of every interactable object?

Any help regarding this will be greatly valued as I am yet to decide the approach for the same.

Thanks!

Regards,
Srinivas

1 Like

Successfully modified the rollup.config.js and built a js module bundle file, it works well, thanks!

Made a pr Add `esm` ( module ) build output. by gonnavis · Pull Request #240 · gkjohnson/three-mesh-bvh · GitHub

1 Like

@gkjohnson I had a need for spatial indexing in a little physics engine I’m making for a game. I knew about your lib but I’m using three.js math primitive classes for collision, not meshes, so I assumed I couldn’t use three-mesh-bvh.

I coded my own makeshift ( and very suboptimal I’m sure ) binary tree, but now I’m wondering if I should have asked you before if I could use your lib for this. Is it possible to index objects such as OBB and Sphere and speed up collision detection between these objects ?

1 Like

@Srinivas_Prabhu

In that case, should I multi ray cast from the gamepad controllers (to get better intersection results and not just in a single direction) or should I check for the intersection of the gamepad’s bounding box/sphere with the BVH of every interactable object ?

Either one would work – it really depends on what you want. Raycasting with a visual indicator can be good for interacting with objects at far distances but if you want users to interact with objects at closer distances using something like a sphere attached to the controller to detect intersections can work well too.

The project doesn’t intend to dictate or suggest interactions as much as it enables interactions that may not have been possible or performant previously. I think the best thing to do is experiment and find what you like best for your project!

@felixmariotto

I coded my own makeshift ( and very suboptimal I’m sure ) binary tree, but now I’m wondering if I should have asked you before if I could use your lib for this. Is it possible to index objects such as OBB and Sphere and speed up collision detection between these objects ?

No the project is built to index the triangles of a mesh with a small memory footprint by rearranging the index buffer data and storing bounds information in an array buffer, as well, which means its not well suited for storing other types of dynamic objects (though static point and line geometry may be supported more fully at some point).

I haven’t had a need myself but I would think there’s a space for an efficient, stand alone dynamic spatial index of scene objects for uses like physics, other geometric spatial queries, or optimized raycasting capabilities in scenes with lots of objects as @prominent mentioned above. A spatial scene index like that could be used in conjunction with this one to, too, with the dynamic index being used for broad queries / detection while three-mesh-bvh is used for individual triangle intersection detection.

1 Like

Thanks to a recent contribution an example on how to use the library to improve point cloud raycasting performance by multiple orders of magnitude has been added! Right now it works by creating a separate mesh of degenerate triangles which can be treated as points which means some extra index memory and a bit of custom raycasting logic is required. In the future a more robust, built-in implementation could be added but it will require some reworking of the indexing functions.

Check the demo out here:

https://gkjohnson.github.io/three-mesh-bvh/example/bundle/pointCloudIntersection.html

3 Likes