ME-BVH: Memory Efficient Bounding Volume Hierarchies

E. Shellshear, Y. Li, J.S. Carlson. In Proceedings of the 7th International Digital Human Modeling Symposium (DHM 2022), August 29-31, 2022. Iowa City, USA and virtually.


Collision detection and distance computation algorithms often form the bottlenecks of many digital human modelling simulations in industrial processes. When designing vehicle assembly lines or cobot assembly cells it is essential to be able to accurately simulate collision free interactions both for efficient and safe operations. Hence, any attempt to improve such algorithms can have a broad and significant impact. Most of the focus is typically on speeding up the queries, however, with models becoming larger as scenarios become more realistic and simulations include more elements such as musculoskeletal models and 3D human body modelling, other parts of the proximity query performance are becoming important such as the management of memory. In this paper, we demonstrate a new technique called ME-BVH (Memory Efficient Bounding Volume Hierarchies) to improve memory usage for proximity queries with bounding volume hierarchies. The approach utilizes a simple and effective way of grouping primitives together at the leaf level and building the bounding volume hierarchy top down to the grouped primitive leaves. The paper then shows ways of efficiently carrying out primitive and bounding volume queries to offset the greater number of potential queries. In addition, the modifications taken are simple enough to be easily applied to most bounding volume hierarchies. By using these approaches, we demonstrate on a number of real-life assembly scenarios with millions of primitives that, compared to existing approaches, our proposed method is able to save up to half of the memory used and can reduce the build times at little cost to the query performance. In addition, the methods developed here are compatible with all BVH types and queries used in ergonomic simulations, unlike many other approaches. The developed algorithms present advantages for proximity queries for deformable meshes used in digital human modelling by reducing the time it takes to build a bounding volume hierarchy which often must be rebuilt or updated many times during simulations due to mesh deformations.

Photo credits: Nic McPhee