gkjohnson / three-mesh-bvh Goto Github PK

When the depth to render updates, it tosses out all the boxes and creates new ones for every bounds, which is slow. Instead, it should create new boxes only as needed and remove the unused boxes once the depth has been updated

This would skip triangle casts for an efficiency boost and allow for a shallower tree while still support tight raycast bounds.

#66 introduced multiple roots to accommodate groups. The bvh visualizer should be updated to display all.

https://github.com/AssemblyScript/assemblyscript

Provide index option for the MeshBVH.

• If an index is provided then that array is modified in place
• If the index option is null then a new index array is generated
• Defaults to null

From #62

index option

An option to provide an already existing index to modify to the BVH. If it's null then the BVH creates a new index array to use internally. If you wanted the BVH to modify the geometry index in place you might do this:

geometry.boundsTree = new MeshBVH( geometry, { index: geometry.index.array } );

or set it after the fact

geometry.boundsTree = new MeshBVH( geometry );
geometry.setIndex( new THREE.BufferAttribute( geometry.boundsTree.index, 1, false ) );

I guess there are actually three cases:

1. The geometry has no index. BVH generation should create one and then you can assign it.
2. The geometry has an existing index, but you care about it, so you want the BVH to create a new one and then you will assign it, maybe after retaining the existing one.
3. The geometry has an existing index, but you are happy to mutate it.

If we implemented your first suggestion (the "index option"), cases 1 and 2 could both be handled by the "set it after the fact" pattern and case 3 would be handled by the "pass it in" pattern. That seems OK.

Hmm, actually, now I'm not sure how I want the option to work. The thing is that IMO the common case is that the code should handle cases 1 and 3 I listed above. I don't really want to make users type something like

if (geometry.index) {
  geometry.boundsTree = new MeshBVH( geometry, { index: geometry.index.array } );
} else {
  geometry.boundsTree = new MeshBVH( geometry ); // it will create an index
  geometry.setIndex( new THREE.BufferAttribute( geometry.boundsTree.index, 1, false ) );
}

I don't really mind that. It's not really necessary to set the index of the geometry if one doesn't already exist because it should render the same either way and the memory impact should be identical, as well. In fact it might be best to not set it because then the index memory can be released by just removing the boundsTree from the geometry.

This should work for all cases, right?

geometry.boundsTree = new MeshBVH( geometry, { index: geometry.index && geometry.index.array } );

It could be cleaner if we instead took a BufferAttribute but there's no real reason to do so (if we ignore the InterleavedBufferAttribute case, which would mean other code has to change, as well).

This can be based on "max tree depth" or relative SAH value (only split if there's sufficient empty space between triangles).

So distance to mesh can be calculated.

• Triangle to Triangle: https://github.com/juj/MathGeoLib/blob/master/src/Geometry/Triangle.cpp#L1751
• Sphere to Triangle: https://github.com/juj/MathGeoLib/blob/master/src/Geometry/Triangle.cpp#L889
• Box to Triangle
• OBB to AABB

So that ranges of triangles can be quickly rolled up if a full bvh node is contained in a shape. The value range should encapsulate all the triangles contained by all the children.

This will mean that we should determine if a node is a leaf using node.left instead of node.count.

The shapecast function should be updated to include the bvh node itself in callbacks so these values can be used.

Possible option names are includeTrianglesOnInternalNodes, storeInternalTriangles, storeInternalIndices

Add sections for

• Describing how the raycasting approach works (BVH, KD Tree, SAH)
• Making the most out of the bounds tree (can't handle animated meshes, merge mesh sub parts to avoid overlapping bounds trees, intersecting leaf nodes)
• Memory issues when dealing with lots of MeshBVHNodes

A lot of functions depend on cached THREE objects:

const v1 = new Vector3();
function doSomething( triangle ) {

  v1.copy( triangle.a );
  // ... do stuff ...

}

which runs a risk of functions overwriting other functions variables mid-use, etc. It might be best to refactor to use the pattern that THREE.js uses:

const doSomething = ( function() {

  const v1 = new Vector3();
  return function doSomething ( triangle ) {
    // ...
  }

} )();

Or for class members:

MeshBVHNode.prototype.doSomething = ( function() {

  const v1 = new Vector3();
  return function doSomething ( triangle ) {
    // ...
  }

} )();

Update: See MeshBVH.js for the functions that need to be updated.

To computeBoundsTree() function and BoundsTree constructor

{
  // how to split the tree nodes
  splitStrategy,
  
  // the max depth to split the tree at
  maxDepth,

  // the max amount of error to allow when using the SAH strategy
  maxError,

  // whether or not to just intersect the leaf nodes for collision and forgo triangle intersections
  intersectLeafNodes
}

Related to #13
Related to #16
Related to #17

• Update Changelog
  • Fix the bounds tree not respecting groups
  • An index buffer is created on geometry if it does not exist
• Document caveat & throw an error if the index is an InterleavedBufferAttribute.
• Document that the index will be automatically created and changed on geometry
• Remove need to set index in README

Add a shapecast function that takes an object to collide with and functions to do collision checking with the bounding boxes and triangles.

// thisMesh
// - mesh that represents the bounding tree

// intersectsBounds( box3 )
// - callback that returns whether or not an inner node has been intersected
// with and to continue to traverse

// intersectsTri( triangle, indices )
// - callback that returns whether or not a triangle has been intersected with.
// If true then the function will stop and return immediately. If needed triangles
// can be pushed into an array here if all intersections are needed.
MeshBVHNode.shapecast( thisMesh, intersectsBounds, intersectsTri );

• Move all source files into src directory
• Decide on approach for initializing the extension to the THREE.Mesh.prototype & THREE.Geometry.prototype (call function? automatically include?)
• Add name, version, etc to package.json
• Update docs
• Produce a UMD variant
• Use three js named imports
• #47
• #37
• #51
• Rename rollup MeshBVH global variable to MeshBVHLib (#64)

Physically Based Rendering had this great suggestion for improving raycasting performance. Ordinarily, if you want to find only the closest intersection for your ray, you need to test your ray against both bounding volumes at each level of the tree hierarchy, and take whichever has the intersection with the closest distance, because it could intersect both. But if you use an SAH strategy and you remember at each node which axis was used for splitting, you can look at where the ray is coming from with respect to the split plane and you know right away which child bounding volume must have the closest intersection, if it intersects that bounding volume at all. You may not have to even look at the other one.

Of course this will cost a little memory but it sounds like it might improve raycasting firstHitOnly performance very substantially.

#36 (comment)

The raycast already seems really performant so it's not a big deal but I believe this check can be faster if you're interested.

This intersectRay function for the box will check all six faces of the box when really you only need to check a single component of one of the planes of the box. So if the split axis is z then you should only have to check if the z component of the split plane is greater than or less than the z component of the intersection (depending on the direction of the ray). That should also let you get rid of the call to distanceToSquared below.

Thanks for a great library!

I was thinking, could this approach also be used to speed up rendering of large meshes? IIRC Three doesn't render meshes whose bounds don't intersect the frustum, so if a large mesh was partitioned as it was here it would also lead to improvements in rendering speed. You might even get the fast raycasting behavior for free if you turn a Mesh into an Object3D hierarchy.

The intersectTri function seems to have changed so it needs to be recopied.

Today I learned that three.js BufferGeometry can have groups, which are ranges of the index that are meant to be drawn with a different material. For example, you can set the first half of the index to be drawn with one material, and the second half to be drawn with another.

This presents a problem for us because if we reorder the index, we are invalidating the group ranges, so the resulting geometry will be drawn with the wrong materials on different parts of the model.

There are maybe three reasonable things we could do to address this:

1. Don't construct BVHs for geometries with groups. Perhaps we could offer functionality to "ungroup" grouped geometries.
2. Add a layer of indirection like our tris which we retain in memory permanently, so that we leave the index alone and store ranges of tris in our tree nodes.
3. Create one BVH "root" for each group which only stores and reorders indices in that group. That way, we will still scramble up the index, but the integrity of the groups will remain. When we raycast, raycast down all the roots (minding bounding boxes.)

I think solution number 3 sounds pretty easy and has no real downsides (raycasting might be very slightly more expensive, but that was also true for solution 2, and if someone doesn't like that, they can ungroup their geometries), and we should implement it.

The difference between BoundsUtilities, GeometryUtilities, and IntersectionUtilities isn't super clear.

Reorganize into something like the following:

• BoxArrayUtilities.js: Utilities related to reading and creating the bounding box to Float32Array.
• ThreeIntersectionUtilities.js: The functions copied and slightly modified from the THREE source.
• IntersectionUtilities: Functions related to intersecting and colliding rays, triangles, and bounding shapes.

Babel is used to run the benchmarks and parcel is used to build the example page. Technically parcel should be using the babel config to transform the code but it could still be resulting in different enough code to be worth investigating.

I'm not sure what a good maximum depth is, but it seems to me a maximum depth of infinity means that fishy models can kind of DoS non-SaH trees by e.g. making sure that exactly one triangle gets partitioned off every time, causing construction to take forever, overflow the stack, run out of memory, make raycasting very slow, or all of the above. I think some conservative default of, say, 20-30 would be wiser. Assuming reasonable splits are being created that should suffice for models up to millions of tris.

@mquander

I added a function to the benchmark utils to interrogate the structure of the tree a bit more called getExtremes. It returns the min and max depth and triangle count per node. When running it against the geometry in the benchmark script I'm seeing that the "minimum" number of triangles in a node is negative:

const geometry = new THREE.TorusBufferGeometry( 5, 5, 700, 300 );
geometry.computeBoundsTree();

console.log( getExtremes( geometry.boundsTree ) );

// { depth: { min: 11, max: 22 }, tris: { min: -293, max: 304 } }

Maybe you have some thoughts?

To "intersectsSphere", etc to be more in line with the THREE.js convention.

Also geometrycast can be moved to use the shapecast function.

Right now there are two fishy-looking things about the maximum depth cutoff:

• If the maximum depth is hit, the leaf nodes will be left without an offset and count, so I don't think raycasting against them will work.
• When the splitting algorithm reaches the maximum depth, it will do a final split and then proceed to ignore the results. It should return early prior to splitting if it's at the maximum depth, just like it returns early if it meets the cutoff for leaf triangle count.

The former is kind of embarrassing, there probably ought to be a test for this.

Wireframe boxes in threejs show with diagonals on each face, with makes me sad :(

Provide an api for serializing and dserializing the tree so the cost of BVH creation can happen offline and be deserialized and instantiated on page load.

const serialized = geometry.boundsTree.serialize();

// ...

geometry.boundsTree = MeshBVH.deserialize(serialized);

// OR

geometry.computeBoundsTree(Strategy.SAH, serialized);

In tree construction, after a split has been decided, we need to establish a minimal bounding volume for the new child nodes. We do so by looking at each triangle in the child node and finding the smallest possible bounding box for all of them. This entails looking up each vertex for each triangle separately in the geometry and seeing whether that vertex needs to expand our box.

Since in the process of constructing the tree we consider each triangle many times for this purpose (at least once for each level of the tree) we could potentially gain by preparing a data structure beforehand that has a single bounding box for each triangle, which we then consult each time we need to do the process above. That would decrease the amount of random reads and cut the work per triangle by two thirds. It seems likely that this would be faster for trees with a lot of levels, although it's hard to say how much.

I think you could improve BVH construction time and memory consumption with two tricks :

• For inner nodes, instead of creating each time left and right primitives id collections before calling the recursive function for their two children (huge memory consumption), you can mutate origTris when the split occurs, and only provide to the two recursive functions the range to work with (basically just a start and end index).
  The final origTris -which is now properly ordered by primitive id of "successive leaves"- can then be a private property of the BVH object, and each leaf only stores start index and the number of primitives (+ things like min/max of the bound of course, and eventually split axis), so that it can retrieve its primitives.
  This approach is valid because, in a BVH, each primitive is associated to only one leaf, even if the primitive overlaps a neighbour leaf.

• After recursive construction, tranforming the BVH nodes to a compact representation (linearization in an Array, Float32Array or Float64Array?) can save a lot of memory (and improve raycast performance, in C++ it's significant, I'm not sure in javascript).

If you are looking for implementation details, the book "Physically Based Rendering" is a great ressource. Their BVH implementation relies on two algorithms of C++ standard library (partition and nth_element, used to reorder primitives collection in two groups, depending of split method), which can be easily implemented in javascript.
They also store each node information in 32 Bytes (memory alignment), but I can't see how to achieve this kind of optimization in javascript.

Add an option to get the first hit out the bounds tree so the rest of the bounds and triangles don't have to be iterated over.

Right now, all candidate indices are a collected and returned.

It's documented that the visualizer needs to be a sibling but it might be nice if instead it just worked no matter where the visualizer was added. Could just override "updateMatrixWorld" to copy the target meshes matrixWorld value.

When I profile tree construction, one main bottleneck I see is that multiple GCs have to happen due to the amount of garbage that gets created. Here are a few categories of things that we construct:

1. MeshBVHNodes. Of course, we need nodes in our tree.
2. Spheres, Box3s, and their underlying Vector3s. It seems like we mostly need to store different bounding boxes and spheres for all of our nodes, so this is hard to avoid.
3. For each node, the array of triangle indices in that node. This one is interesting. We need that list at each level when we are constructing child nodes, but we only need to store it permanently for leaf nodes; the arrays of triangles for intermediate nodes are discarded. It could be possible to rework the construction algorithm to not construct so many intermediate arrays.
4. For each node, lambdas referring to that node and its split volumes, to put into the creation queue. This one is also interesting. It seems like if we reworked the construction algorithm, the processing queue could just be a queue of nodes, where the meaning of each entry is "this node needs to be split." That would save us creating the lambdas.

3 and 4 could be productive avenues for optimizing tree construction.

The geometry in the benchmark with the default options winds up having the following min and max triangle counts:

tris: { min: 1, max: 76 }

despite the maxNodeTris option being set to 10. This could be solved by checking to make sure that both children counts will be above the tris threshold before splitting the nodes into separate children.

Some of the cached information in the OBB and SeparatingAxisTriangle classes isn't always needed and can cause a small performance hit to create when performing shape casts. Would be better to selectively update parts of the object as needed.

Right now, the BVH nodes are being split at the average point of all face vertices along the longest edge of the overall bounding box.

This allows for less-than optimal bounding boxes where there's a large gap between triangles instead of just containing the clusters of polygons.

Provide an API for progressive tree building, which can be slow for large meshes at the moment. Some ideas:

// uses requestIdleTick or requestAnimationFrame to build the tree and
// provides a promise and variable for whether or not the tree is done
const perFrameTime = 1;
geometry.computeBoundsTree(Strategy.SAH, perFrameTime).then(...);
console.log(geometry.boundsTree.ready); // false

// provides function for running the next tick of the building
geometry.computeBoundsTreeProgressively();

// every frame until finished
if (!geometry.boundsTree.ready) geometry.boundsTree.build(perFrameTime);

this would be easy to do with a generator

See implementations in this repo:

• Triangle intersects triangle: here
• Triangle intersects Sphere: here
• Triangle closest Point: here
• OBB / AABB Box intersection?
• OBB / AABB Distance?

OrientedBox and SeparatingAxisTriangle cache update seems to be a bit of a bottleneck, as well.

After generalizing the BVH construction and functions for generally accessing triangles between Geometry and BufferGeometry, the Geometry building process is significantly slower than it was before. See this function:

https://github.com/gkjohnson/threejs-raycast-updates/blob/7332865cc44e4bcd4dee64cac7695b29cc526050/lib/GeometryUtilities.js#L15-L19

It's possible that the added dictionary accesses would be causing slowdowns. Previously, this

const index= faces[tri]['a']; // dictionary access
const vert =  vertices[index];
const x = vert.x, y = vert.y, z= vert.z;
// ... do stuff ...

into

const x = vertices[faces[tri]['a']].x; // dictionary access
const y = vertices[faces[tri]['a']].y; // dictionary access
const z = vertices[faces[tri]['a']].z; // dictionary access

1 vs 3 dictionary lookups.

Verify that casts works as expected and match the values that the built in raycast give.
Make sure that ray casting functions work if the ray is cast from inside the geometry.

Provide lookups for sphere, capsule, box casting rather than just ray casting against the BVH.

The fast raycasting only works static meshes and doesn't account for co-location, grouping, or blocking of scene geometry.

Some approaches include generalizing the bvh, making it dynamic, or using another data structure (like threeocttree) to make scene-wide raycasts as fast as possible.

Some of the code in IntersectionUtils and GeometryUtils is copied from THREE js because its not otherwise exposed. If possible this copied code should be removed or at least reduced.

TODO: Document which functions are copied

The MeshBVH construction relies on accessing the index array directly, meaning that Interleaved Buffer Attributes are not supported as an index attribute. This limitation should be communicated (documented / error thrown) or code updated so it's supported.

The benchmark estimates the size of an object based on primitive, array, and dictionary key size calculations, but the javascript engine likely overhead associated with an object.

When computing a bounding box for a TorusKnotBufferGeometry with the arguments TorusKnotBufferGeometry(1, 0.4, 400, 100) the benchmark reports 2476.31 kb (including index buffer) used while the browser reports 6617.08 kb used.

Tons of nodes get created so any reduction we can make per object (even empty dictionary keys) may be worthwhile.

• _mesh does not necessarily need to be a pointer on every node.
• children can be removed if the node is a leaf node (or only be added if it's an internal one)
• tris can be removed if the node is an internal node.