An accelerated and accurate three-dimensional ray tracing using red-black tree with facet mining and object bouncing techniques

Authors: MOHAMMAD JAKIRUL ISLAM, AHMED WASIF REZA, KAMARUL ARIFFIN NOORDIN, KAHARUDIN DIMYATI, ABU SULAIMAN MOHAMMAD ZAHID KAUSAR

Abstract: Recent trends show that it is a major challenge to predict the exact propagation path accurately and efficiently for three-dimensional (3D) indoor environments. Therefore, this study introduces a new 3D ray tracing algorithm based on a red-black tree with facet mining and object bouncing techniques. The red-black tree data structure offers a faster object searching operation while repeatedly performing intersection tests. On the other hand, extensive ray-facet intersection tests can be eliminated by using object and facet bouncing techniques, whereas the facet mining makes it easier to trace the transmitted ray paths accurately. The proposed method is compared with ray launching, bidirectional path tracing, modified angular Z-buffer, and binary space partitioning-based modified wavefront decomposition techniques and it is found that it obtains better prediction results in terms of computation time, the number of predicted rays, and radio propagation path loss.

Keywords: Ray tracing, red-black tree, facet mining, object bouncing

Full Text: PDF