Ray tracing is a versatile technique used across various fields, most notably in image rendering, but it also plays a critical role in scientific computation. Although ray tracing in its basic form requires extensive computational power, several strategies exist to improve efficiency. One approach is leveraging specialized hardware like GPUs, while optimized data structures, such as BSP-trees, KD-trees, and Octrees, also offer performance improvements.
In this thesis, we will improve the ray tracing-based mesh check algorithm deployed in an implementation of a polyhedral gravity model by Schuhmacher et al. The best-suited data structure for this application is the KD-tree because it focuses on optimal space subdivision and guarantees fast build times in O ( n · log ( n )) by adhering to the descriptions of Wald et al. Currently, there is no easy-to-use, high-quality implementation promising fast build times. Thus, we create a new KD-tree library written in modern C++17, employing the “lazy loading” pattern. It follows best software practices and is optimized to reduce runtime. We deploy multithreading techniques, achieving full CPU core utilization for 80% of total runtime. The mesh-check for the Eros asteroid mesh comprising 70150 vertices and 140296 faces takes 4.7 seconds using the highest optimization level of the library. Execution without the integrated KD-tree takes 54.4 seconds. We validate our implementation through extensive input fuzzing and regression testing, comparing differently optimized implementations of
KD-tree construction algorithms.