Theorticial ground / Subdivision method used in three-mesh-bvh

[yelouafi]

We were investigating on using this lib into our app to speedup raycasting and stumbled upon this answer on SO

https://computergraphics.stackexchange.com/questions/10098/is-bvh-faster-than-the-octree-kd-tree-for-raytracing-the-objects-on-a-gpu

The answer mentioned the influential work of Wald, Boulos and Shirley to implement efficient object subdivision schemas. I was wondering about the method used in this lib but couldn't find something on the docs.

Could you shed some light on this?

[gkjohnson]

Hello! The culmination of the library is from a smattering of online papers and resources and personal experience along with some decisions and options made available to make the library more viable for common, memory-conscious web use cases. The data structure used in the project is a Bounding Volume Hierarchy in which each node is split in to two children to contain a set of triangles until a set of termination conditions are met. The actual partition method used is set via the strategy option and defaults to "CENTER", which just splits any given set of triangle bounds directly down the center. I found this to be the best trade of build performance and run time performance. A Surface Area Heuristic (SAH) option is also available if you need to speed things up more and is commonly used in applications like path tracing but it takes much longer to build the tree -- there are still improvements to build time I plan to look in to, as well.

The specific paper you mentioned by Wald, Boulos, and Shirley (here) isn't easily available to read at that link but from the abstract seems to discuss dynamically adjusting BVHs for deformable meshes specifically for cases like physics objects or skinned or morphed geometry. The library provides a refit function to expand / shrink bounds to their child triangles if they've changed but SkinnedMeshes and morph targets are generally not supported by the library (yet?). Deforming meshes is a bit use case specific, though.

It looks like this article provides a good overview of the data structure as it applies to rayasting if you're interested. Though of course there's a lot more functionality provided in this library:

https://medium.com/@bromanz/how-to-create-awesome-accelerators-the-surface-area-heuristic-e14b5dec6160

Is there something more specific you're interested in hearing about? What's your use case for the library?

[yelouafi]

Thanks for your answer!

Is there something more specific you're interested in hearing about? What's your use case for the library?

Primary case is to speed raycasting and collision detection.

We actually use bounding boxes to speed raycasting (avoid perf. overhead of raycasting on complex 3D models) but it's suboptimal and sometimes doesn't work for some models (we don't control how models are built)

For collision detection we use an Octree data structure from threejs and check intersection with a capsule shape. It seems to work well, but building the octree from the entire scene seems to take some time

We don't have dynamic geometries, and most of our objects are static besides the player/camera and some animated 3D models.

[gkjohnson]

For collision detection we use an Octree data structure from threejs and check intersection with a capsule shape. It seems to work well, but building the octree from the entire scene seems to take some time

Yes the octree system in three.js examples is nice but the build process can be a bit slow. It's also very memory intensive because if I remember right when I took a look at it it stores all triangles as javascript objects which can work great in simple cases but it can bloat memory quite a bit.

This package puts a pretty big emphasis on memory allocation because it can inflate quite especially in javascript if you're not careful. Once the BVH is built the node bounds (6 floats) and contents pointers (~2 floats) are packed into a typed array so the memory footprint is controlled and known. And rather than creating copies of the triangle indices the geometrys index buffer is rearranged in place so no extra memory is required (though an index buffer is created if one doesn't exist yet).

And because typed array buffers are used the BVH can be easily built in a WebWorker (see example snipped here) to avoid blocking the UI. You can also build the BVH ahead of time, serialize it, and reload it at run time to avoid build costs, as well. The build performance in this project is pretty good already, though. But of course there's other room for improvement. Generally there's a lot of flexibility and consideration for the types of uses you've mentioned built in to the project.

Primary case is to speed raycasting and collision detection.

Are you using it for a game? Architecture visualization? I always like seeing / hearing more about what people are planning to use my work for!

[yelouafi]

It's more like Architecture visualization than a game

[gkjohnson]

It's more like Architecture visualization than a game

Gotcha -- if the project is public and you can share it at some point I'd love to see how you're using the library! I'll close this issue for now unless you have other questions

[yelouafi]

Sorry for the dry answer :sweat_smile: . I wasn't sure if I was allowed to disclose.

The project in question is https://oncyber.io/. It's a platform to visualise NFTs in a 3D scene. Basically we have a gallery as a 3d model where collectors can put various assets like images, videos, 3D models ...