MeshBVH index offset for merged geometries into one buffer

[minitoine]

Hello gkjohnson, it's been a while :)

Is your feature request related to a problem? Please describe.

I'm trying to load a huge number of objects in a scene, with precomputed BVH trees, and I want to merge these objects to have one draw call (at least, less).

Let's say I have N different indexed geometries with their own BVH and that I merge these geometries into a big one (by concatenating index and position buffers).

Now, let's say, I don't keep individual geometries in memory, but only BVH trees. If I give to each BVH trees a reference to the merged geometry instead of the individual ones, I have no way of telling each BVH tree that the vertex indices it is interest in start at a certain offset in the buffer.

Describe the solution you'd like

Add a offset param to the MeshBVH to tell where the indice "0" really starts

Describe alternatives you've

Alternative 1:
Keep individual geometries in memory to perform BVH operations.
con: memory cost

Alternative 2:
Generate a BVH for the merged geometry
con: computation cost for millions of triangles.

[gkjohnson]

Hey minitone! This seems like a reasonable use case especially for supporting something like mrdoob/three.js#22376 more easily and performantly in the future. Would you like to make a PR with some tests? Happy to provide some guidance to get it added.

Add a offset param to the MeshBVH to tell where the indice "0" really starts

You'd need a "count" value, as well, right? How do you feel about a "range" option that provides a start and count value?

const bvh = new MeshBVH( geometry, {
  strategy: SAH,
  range: { start: 10, count: 10 },
  // ...
} );

Alternative 2:
Generate a BVH for the merged geometry
con: computation cost for millions of triangles.

Out of curiosity how much of a performance difference are you seeing here?

[minitoine]

Hello gkjohnson,

I finally have some time to work on this.
I do have one question though. Let's admit I have 20 bvhs pointing to the same geometry index buffer but at different indexes. Would I be able to move the geometry indexes around (like rearranging groups) and update the bvhs accordingly ?

Example:
Object A has indices from 20 to 56. BVH is then built from index 20 to 56 (range = {start:20, count: 36})
Object A is moved to indices 120 to 156. BVH is updated with range = {start:120, count: 36}

What's happening now if we perform a raycast ?

Does the MeshBVH tree stores the indices of the index buffer relatively to the beginning of the input range, and so, updating the index range should still work ?
Or do you store the indices in a absolute way in the tree nodes ? And in that case, adding an "offset" param wouldn't work ?

I'm not sure to be clear. :/

-------- Why ? --------

Still in the idea of a batch mesh, but sub meshes can change transparency, and thus, material group. Instead of adding more groups and more gpu draw calls, each batch mesh has a defined amount of material (typically opaque, transparent and hidden), so 3 geometry groups. And so if a submesh change group, I am currently rearranging the index buffer in a web worker with a SharedArrayBuffer. Still, the goal behind is to keep a BVH by submesh (at best, per geometry), so objects can be moved in space in real time without having to refit millions of triangles (in case you compute a BVH on the whole batch mesh). In that cas BVH can be precomputed as well on server.

[gkjohnson]

Hi @minitoine!

Or do you store the indices in a absolute way in the tree nodes ?

The indices are stored against the 0 index of the underlying buffer.

And in that case, adding an "offset" param wouldn't work ?

A range offset and count as I mention above would work and not be too difficult to add but only in the sense that you'd be generating a bvh using a sub-range of the geometry. Rearranging those ranges would not work.

Does the MeshBVH tree stores the indices of the index buffer relatively to the beginning of the input range, and so, updating the index range should still work ?

This is a new feature so there had been no need for this kind of thing before.

That said I think supporting the use case replacing and rearranging the underlying buffer underneath the BVH is a bit convoluted. For the behavior you're looking for (changing the material of one item in the custom batched mesh) a proper BatchedMesh implementation using multi draw arrays would suit it just fine.

I think I'd prefer to work towards a flexible BatchedMesh implementation in three.js rather than working around it in three-mesh-bvh. You can vocalize your opinion and usecase for that kind of flexibility at the ongoing batched mesh issue: mrdoob/three.js#22376.