An evaluation of Kd-Trees vs Bounding Volume Hierarchy (BVH) acceleration structures in modern CPU architectures
Article Sidebar
Main Article Content
Abstract
Ray tracing is a rendering technique that is highly praised for its realism and image quality. Nonetheless, this is a computationally intensive task that is slow compared to other rendering techniques like rasterization. Bounding Volume Hierarchy (BVH) is a primitive subdivision acceleration mechanism that is the mainly used method for accelerating ray tracing in modern solutions. It is regarded as having better performance against other acceleration methods. Another well-known technique is Kd-Trees that uses binary space partitioning to adaptively subdivide space with planes. In this research, we made an up-to-date evaluation of both acceleration structures, using state-of-the-art BVH and Kd-Trees algorithms implemented in C, and found out that the Kd-Trees acceleration structure provided better performance in all defined scenarios on a modern x86 CPU architecture.
Article Details
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
Los autores conservan los derechos de autor y ceden a la revista el derecho de la primera publicación y pueda editarlo, reproducirlo, distribuirlo, exhibirlo y comunicarlo en el país y en el extranjero mediante medios impresos y electrónicos. Asimismo, asumen el compromiso sobre cualquier litigio o reclamación relacionada con derechos de propiedad intelectual, exonerando de responsabilidad a la Editorial Tecnológica de Costa Rica. Además, se establece que los autores pueden realizar otros acuerdos contractuales independientes y adicionales para la distribución no exclusiva de la versión del artículo publicado en esta revista (p. ej., incluirlo en un repositorio institucional o publicarlo en un libro) siempre que indiquen claramente que el trabajo se publicó por primera vez en esta revista.
References
T. Akenine-Möller, E. Haines, and N. Hoffman, Real-Time Rendering, Fourth Edition. A K Peters/CRC Press, 2018.
J. Buck, The Ray Tracer Challenge: A Test-Driven Guide to Your First 3D Renderer (Pragmatic Bookshelf). Pragmatic Bookshelf, 2019.
Chitalu, Floyd M. and Dubach, Christophe and Komura, Taku, “Bulk-synchronous Parallel Simultaneous BVH Traversal for Collision Detection on GPUs,” in Proceedings of the ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games, ser. I3D ’18. New York, NY, USA: ACM, 2018, pp. 4:1–4:9.
B. Choi, B. Chang, and I. Ihm, “Improving memory space efficiency of kd-tree for real-time ray tracing,” Computer Graphics Forum, vol. 32, 10 2013.
P. Du, E. S. Liu, and T. Suzumura, “Parallel Continuous Collision Detection for High-performance GPU Cluster,” in Proceedings of the 21st ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games, ser. I3D ’17. New York, NY, USA: ACM, 2017, pp. 4:1–4:7.
E. Haines and T. Akenine-Möller, Ray Tracing Gems: High-Quality and Real-Time Rendering with DXR and Other APIs. Apress, 2019.
V. Havran, “Heuristic Ray Shooting Algorithms,” Ph.D. dissertation, Czech Technical University, 166 36 Prague 6, Czechia, 2000.
J. Hennessy, Computer Architecture: A Quantitative Approach. Cambridge, MA: Morgan Kaufmann Publishers, an imprint of Elsevier, 2018.
J. F. Hughes, A. van Dam, M. McGuire, D. F. Sklar, J. D. Foley, S. K. Feiner, and K. Akeley, Computer Graphics: Principles and Practice (3rd Edition), 3rd ed. Pearson India, 2019.
M. R. Kaplan, “The use of spatial coherence in ray tracing,” 1987.
T. L. Kay and J. T. Kajiya, “Ray tracing complex scenes,” in Proceedings of the 13th Annual Conference on Computer Graphics and Interactive Techniques, ser. SIGGRAPH ’86. New York, NY, USA: Association for Computing Machinery, 1986, p. 269–278.
J. P. Molina Masso and P. González, “Automatic hybrid hierarchy creation: a cost-model based approach,” Computer Graphics Forum, vol. 22, pp. 5–13, 03 2003.
D. C. Montgomery, Design and Analysis of Experiments. Tenth Edition. Wiley, 2020.
D. Patterson, Computer Organization and Design: The Hardware/Software Interface. Sixth Edition. Morgan Kaufmann, 2020.
M. Pharr, W. Jakob, and G. Humphreys, Physically Based Rendering: From Theory to Implementation, 4th ed. Early Release, Morgan Kaufmann, 11 2022.
E. Rivera-Alvarado and F. J. Torres-Rojas, “Ray tracing acceleration through heterogeneous integrated commodity hardware,” in 2019 38th International Conference of the Chilean Computer Science Society (SCCC), 2019, pp. 1–8.
E. Rivera-Alvarado and F. J. Torres-Rojas, “Apu performance evaluation for accelerating computationally expensive workloads,” Electronic Notes in Theoretical Computer Science, vol. 349, pp. 103 – 118, 2020, proceedings of CLEI 19, the XLV Latin American Computing Conference.
E. Rivera-Alvarado and F. J. Torres-Rojas, “Bounding volume hierarchy acceleration through tightly coupled heterogeneous computing,” in High Performance Computing, J.L. Crespo-Mariño and E. Meneses-Rojas, Eds. Cham: Springer International Publishing, 2020, pp. 94–108.
M. Vinkler, V. Havran, and J. Bittner, “Bounding volume hierarchies versus kd-trees on contemporary many-core architectures,” in Proceedings of the 30th Spring Conference on Computer Graphics, ser. SCCG ’14. New York, NY, USA: Association for Computing Machinery, 2014, p. 29–36.
H. Wickham and G. Grolemund, R for Data Science: Import, Tidy, Transform, Visualize, and Model Data. O’Reilly Media, 2017.
H. Ylitie, T. Karras, and S. Laine, “Efficient Incoherent Ray Traversal on GPUs Through Compressed Wide BVHs,” in Proceedings of High Performance Graphics ser. HPG ’17. New York, NY, USA: ACM, 2017, pp. 4:1–4:13.
Seacord, Robert, Effective Cs: an introduction to professional C programming, No Starch Press, Inc, 2020.