Evaluación de estructuras de aceleración Kd-Trees vs BVH en arquitecturas CPU modernas
Barra lateral del artículo
Contenido principal del artículo
Resumen
Ray-tracing es una técnica de sintetizado de imágenes que destaca por el gran realismo y calidad que puede brindar en una imagen. Sin embargo, esta técnica es computacionalmente intensiva y lenta en comparación a otras metodologías de sintetizado tal como rasterización. Las Jerarquías de Volúmenes Limítrofes (BVH por sus siglas en inglés) son un mecanismo de aceleración basado en subdivisión de primitivas cuyo principal uso es la aceleración de ray-tracing en soluciones modernas. Comúnmente es referida como una solución que provee mejor aceleración con respecto a otras técnicas. Otra técnica bien conocida son los árboles-Kd (Kd-Trees en inglés), los cuales usan particionamiento de espacio binario con división adaptativa de planos. En esta investigación realizamos una evaluación actualizada de ambas estructuras de aceleración, usando algoritmos del estado del arte de BVH y Kd-Trees implementados en el lenguaje C. Entre los hallazgos encontramos que Kd-Trees provee mejor aceleración en una arquitectura x86 moderna para los escenarios planteados.
Detalles del artículo
Esta obra está bajo una licencia internacional Creative Commons Atribución-NoComercial-SinDerivadas 4.0.
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.
Citas
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.