Efficient clustered BVH update algorithm for highly-dynamic models

We present a new algorithm that efficiently updates bounding volume hierarchy (BVH) for ray tracing. Our algorithm is applicable in handling various types of highly-dynamic models. The algorithm produces the SAH-based BVH of good quality for rendering. The algorithm unites the advantages of some previously developed methods and offers techniques and extensions to reduce the number of per-frame BVH update operations. It works with a binary BVH where every leaf is associated with a triangle. The algorithm always tries to perform less costly operations on BVH-clusters and avoids unnecessary work if it is possible. Firstly, it detects BVH-clusters of triangles that move coherently to each other, and reinserts only cluster-roots in the proper positions of the BVH. Thus it allows efficient handling of the structural motion. Secondly, the algorithm detects the exploded BVH-clusters for performing rebuild-operations on them. Careful and efficient localizing of rebuild-space into non-overlapping clusters greatly reduces the number of rebuild-operations. It can allow independent rebuilding of all detected clusters, even if one cluster is represented by an ancestor of another. Our algorithm accelerates the total BVH update time by 2-4times on the average in comparison to the full SAH-based binned-rebuild with a set of all triangles at input.