kD-Tree Traversal Implementations for Ray Tracing on Massive Multiprocessors: A Comparative Study

• Artur L. dos Santos UFPE
• Joao Marcelo X. N. Teixeira UFPE
• Thiago S. M. C. de Farias UFPE
• Veronica Teichrieb UFPE
• Judith Kelner UFPE

Resumo

Current GPU computational power enables the execution of complex and parallel algorithms, such as Ray Tracing techniques supported by kD-trees for 3D scene rendering in real time. This work describes in detail the study and implementation of five different kD-Tree traversal algorithms using the parallel framework NVIDIA Compute Unified Device Architecture (CUDA), in order to point their pros and cons regarding adaptation capability to the chosen architecture. In addition, a new algorithm is proposed by the authors based on this analysis, aiming performance improvement. A performance analysis of the implemented techniques demonstrates that two of these algorithms, once adequately adapted to CUDA architecture, are capable of reaching speedup gains up to 15x when compared to former CPU implementations and up to 4x in comparison to existing and optimized parallel ones. As a consequence, interactive frame rates are possible for scenes with 1376x768 pixels of resolution and 1 million primitives.

Palavras-chave: Ray tracing, Parity check codes, Decoding, Network-on-a-chip, Integrated circuit interconnections, Iterative algorithms, Error correction codes, Communication standards, Digital video broadcasting, WiMAX, Ray Tracing, kD-Tree, Traversal, CUDA