SIMD Optimized Bounding Volume Hierarchies for Fast Proximity Queries

R. Ytterlid, Master thesis, Chalmers University of Technology, supervisor E. Shellshear, October 2013.


3D models of physical objects are used in an ever-growing number of areas to help visualize and simulate digital environments. Appli- cations must often simulate complex processes involving physical phe- nomena such as forces, velocities and physical interactions between objects. In such environments, it is crucial to be able to effectively 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 cer- tain 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%.


This study was performed at the Fraunhofer Chalmers Centre (FCC) in Göteborg during the spring and summer of 2013. I would like to thank the staff at FCC for giving me access to their computers, software and free fruit, as well as giving me my own room to work in, with the office’s best window view as an added bonus. Special thanks goes to my supervisor Evan Shellshear at FCC for the immense amount of help and guidance he has offered during the thesis work, and Ulf Assarsson at Chalmers for his valuable feedback.

Authors and Affiliations

  • R. Ytterlid, Fraunhofer-Chalmers Centre

Photo credits: Nic McPhee