SIMD Optimized Bounding Volume Hierarchies for Fast Proximity Queries

Abstract

3D models of physical objects are used in an ever-growing number of areas to help visualize and simulate digital environments. Applications must often simulate complex processes involving physical phenomena such as forces, velocities and physical interactions between objects. In such environments, it is crucial to be able to e ectively determine proximity between objects by using collision- and distance tests. As the number and complexity of 3D models increases, together with an increasing demand for simulation precision and realism, heavy demands are placed on the performance of the proximity tests that are used. This thesis investigates the possibilities of increasing proximity test performance by combining Bounding Volume Hierarchies, which are common data structures for accelerating proximity tests, with a certain method for parallel computation called SIMD. Some SIMD-based construction strategies are presented and shown to increase proximity test speed by up to 50% and reducing BVH memory footprint by up 60%.