Support refitting for index attribute updates

[Agelaste3]

Description

Sorry if this was already addressed somewhere and I simply couldn't find it, but recently while developing a sculpting tool with local tessellation, I encountered a usecase, where, obviously, adding new vertices/triangles to the target mesh was needed, but if I correctly understood the refit.template.js file, any changes to index won't be supported (and I think it was written somewhere in the documentation too).
So I wondered if it would be possible to have a more intricate control over the bvh refitting, if it doesn't contradict the existing architecture somehow/doesn't have significant performance degradation consequences.

Solution

A convenient way to handle this issue would probably be a function like "updateIndex" which would grant us the ability to specify removed and added triangles which could be added as nodes to the bvh tree (while refit() could be used to handle position updates as is now).

Alternatives

The problem seems to be that even with the current refit() function we seemingly can't easily map geometry's attribute indices unto nodes (let's say we want to refit a set of vertex indices, how do we get the corresponding nodeIndices?), so in order to implement these changes, we would probably need to either query the positions against the bvh (seems like an overkill) or keep some correspondence map, so I'm not totally sure if this change is really in the scope of the library.

Additional context

No response

[gkjohnson]

The architecture for the BVH is designed to be very memory efficient once built so unfortunately it's not so viable to add and remove data dynamically. In theory you could find the most relevant leaf to add new triangle into and expand the bounds but this would mean having to adjust the triangle points of all subsequent leaf nodes and refit all affected parent nodes. And eventually you'd add / move so many triangles that you'd have to rebuild the full structure to keep things efficient, anyway. All to say the current BVH is not designed for this kind of use case and should be considered "static" in it's structure once built (though the bounds can be refit as you've seen).

As far as I understand the sculptgl project (which the sculpting demo in this repo is based on) uses an octtree built from js objects which can be more easily readjusted but will otherwise be not so memory efficient since it's using js primitives instead of manually managing memory in a buffer.

It's on my list to write a "DynamicBVH" to provide as along side "BVH" (implicitly static) that can be expanded like this and hopefully it can be built to be tight on memory usage at the same time. I'm not sure when I'll be able to put time into that, though. But it's something I'd like to get added.