Refit: Survey of fast BVH update strategies

[gkjohnson]

Related to #132

Refitting references here.

[gkjohnson]

• [8] Asynchronous BVH Construction for Ray Tracing Dynamic Scenes on Parallel Multi-Core Architectures
  • traverse and refit in a background worker continuously
  • refit occasionally and rebuild entirely once it's deteriorate too far
  • rebuild constantly in a background thread using copy of vertex data and swap to the new build once finished and refit
  • refit can be done across multiple threads
• [10] A dynamic bounding volume hierarchy for generalized collision detection
• [11] RT-DEFORM: Interactive Ray Tracing of Dynamic Scenes using BVHs
  • Ray Tracing with Reduced-Precision Bounding Volume Hierarchies (discusses optimal number of primitives per leaf)
  • Heuristic for determining whether BVH has degraded too far
    • Measure ratio of parent node surface area to sum of two children.
    • Ratio is computed at the beginning on BVH generation and ratio is stored per node
    • After change the ratio differences can be summed, divided by the number of inner nodes (n - 1) and used to determine whether the tree should be rebuilt or not.
    • Paper suggests 40% difference is a good time
    • A similar approach should be able to work with the surface area score provided by getBVHExtremes to see how high the score has gotten relative to the original score.
• [14] Collision detection for deformable objects
  • Read "Geometric data structures for computer graphics"
  • Useful for improving collision detection logic, tree traversal
  • recommends minimizing the volume for collision detection
  • can split up hierarchy bounds based on mesh connectivity
  • 4 or 8-split trees may be better than binary trees for collision detection
  • Discusses self-intersections
  • BVs can cover the movement of a primitives over a time step
• [15] Efficient collision detection of complex deformable models using AABB trees
  • Because all children are described after the parent in the node array the children can just be traversed in reverse order in the case that all bounds are being updated. (benefit isn't mind blowing even in the worst case where everything must update compared to the current recursive approach)
• [18] Ray Tracing Deformable Scenes using Dynamic Bounding Volume Hierarchies
  • The "split" axis can be described as the one where the child nodes are furthest separated. Could it be possible that the partition axis is not the optimal "split" axis after the triangles have been split and bounds created?
  • When refitting it's possible that the best split axis will have changed and should be updated in the bounds data. The paper recommends using centroid distance to determine the best split.
  • When trying to build a BVH for an animated model you can create multiple BVHs with representative poses over the course of the animation and select the one that has lowest max score across all poses (assuming a good representative pose cannot be used).
  • Or SAH can account for multiple poses during testing.
• [22] Ray Tracing Dynamic Scenes using Selective Restructuring
  • find BVH nodes with high overlap and restructure them rather than rerunning the whole tree
  • Any two nodes that aren't ancestors can be candidates for restructuring
  • The amount of required memory would need to be known and fixed for this to work (Remove intermediate object creation during build #224)

[gkjohnson]

Key thoughts:

• Rebuild in a background worker while consistently refitting on main thread
• Add heuristic for determining if a tree has become too out of poorly structured so it can be rebuilt
• Refit / rebuild can be done across multiple workers
• The split axis can be re-selected on refit based on how far the child centroids are from eachother
• BVH can be selectively restructured based on bounds overlaps and subtrees rebuilt
• Only rebuild some parts of the tree that need to be rebuilt