three-mesh-bvh
three-mesh-bvh copied to clipboard
Remove intermediate object creation during build
- Number of nodes at depth d:
2^d
- Best case number of leaf nodes:
Math.min( Math.ceil( tris / maxTrisPerNode ), maxDepth )
- It's likely to be worse, though, if a split results in nodes that have 1 or 2 triangles, for example.
- If the exact number of triangles per node is known you can predict the number of nodes that will be in a the tree. However given that we afford flexibility it's possible we could estimate the worst case and ensure no nodes contain fewer than some threshold. The BVH buffer would contain (likely a decent amount) of extra, unused space but in this case we wouldn't have to create extra manually managed buffer space. Extra space could be removed by copying to another buffer afterward. Being able to strictly know this ahead of time may make it possible to just rebuild an individual subtrees without new allocation?
Perhaps some intermediate memory can still be saved while retaining flexibility if an array of buffers was created -- 1 for each node and then it gets packed into a single buffer. Or a new buffer can be created as needed to "extend" the existing buffer. Finally the buffers would all be packed into single buffer. This would require tracking the next global node index, the current extension buffer, and the offset within the index buffer.
The "populateBuffer" step after generating the object tree also takes ~9-15ms (~160ms total) in the benchmark so this should save at least a little time.