SAH can contain more than 1 triangle at leaf even when "maxLeafTris" is 1

[gkjohnson]

No description provided.

[agargaro]

If we consider that a MeshBVHNode can have more than maxLeafTris triangles only if:

• node depth > maxDepth
• all triangles in the node have the same bbox (we can split these anyway actually)

then we would probably have a problem for center and average as well.

I tried setting maxLeafTris to 1 in the inspector example and building the BVH with all 3 strategies and we always have max tris per leaf greater than maxLeafTris

I debugged a little bit and I think the problem might be here:

https://github.com/gkjohnson/three-mesh-bvh/blob/master/src/core/build/buildTree.js#L107

If a wrong axis is selected (usually longest), where all triangles have the same value, the split would fail returning the same previous offset. So probably in that case we should try a different axis?

In the case of SAH there could also be a problem related to axis -1. I don't really know how it works unfortunately, but I noticed that it can happen that axis is -1 because the initial bestCost is better than all the others calculated. What to do in this case? Use a different strategy for that node? Set bestCost to infinity?

I hope I didn't misunderstand the problem 😂

[gkjohnson]

If a wrong axis is selected (usually longest), where all triangles have the same value, the split would fail returning the same previous offset. So probably in that case we should try a different axis?

Yeah if I recall this is correct. And of course if a model has identical overlapping triangles then this will happen regardless of which axis picked, though that's a bit of an anomalous case.

In the case of SAH there could also be a problem related to axis -1. I don't really know how it works unfortunately, but I noticed that it can happen that axis is -1 because the initial bestCost is better than all the others calculated. What to do in this case? Use a different strategy for that node? Set bestCost to infinity?

This is by-design for SAH (Surface Area Heuristic) since the algorithm is trying to only split the hierarchy down until it reaches apparent computational cost of checking a bounding box will be larger than just checking the triangles.

Unless there's a strong need for this kind of guarantee I don't think it's worth spending too much time on - just something I noticed and made an issue. I originally noticed it when working on the path tracer and checking if I could adjust the code to support just one triangle in leaf but it's not a huge deal.

If we wanted a solution I think we need to add a new field to retain the current behavior. Ie something like:

{
  // if a leaf node has more than this number of triangles then
  // continue forcing a working split until we reach this threshold
  // If no axes can be picked then just split the remaining tris into
  // two groups. 
  maxLeafTris: Infinity,

  // if a leaf node reaches this threshold of triangles then it stops
  // being split. This is the current behavior of maxLeafTris
  targetLeafTris: 10
}

I don't think it's worth making a breaking change to the project right now, though.