Mohammad Jakirul ISLAM, Ahmed Wasif REZA, Kamarul Ariffin NOORDIN

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

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.

Anahtar Kelimeler:

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

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

Keywords:

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

PDF

___

Mart´ınez D, Las-Heras F, Ayestaran RG. Fast methods for evaluating the electric field level in 2D-indoor environ- ments. Prog Electromagn Res 2007; 69: 247–255.
Iskander MF, Yun AZ. Propagation prediction models for wireless communication systems. IEEE T Microw Theory 2002; 50: 662–673.
Yang M, Stavrou S, Brown AK. Hybrid ray-tracing model for radio wave propagation through periodic building structures. IET Microw Antenna P 2011; 5: 340–348.
Tiberi G, Bertini S, Monorchio A, Giannetti F, Manara G. Computationally efficient ray-tracing technique for modelling ultrawideband indoor propagation channels. IEEE Antenn Propag M 2009; 57: 395–401.
Liu ZY, Guo LX. A quasi three-dimensional ray tracing method based on the virtual source tree in urban micro- cellular environments. Prog Electromagn Res 2011; 118: 397–414.
Maltsev A, Maslennikov R, Lomayev A, Sevastyanov A, Khoryaev A. Statistical channel model for 60 GHz WLAN systems in conference room environment. Radioengineering 2011; 20: 409–422.
Mohtashami V, Shishegar AA. Accuracy and computational efficiency improvement of ray tracing using line search theory. IET Microw Antenna P 2010; 4: 1290–1299.
Jianjun D, Ru-Shan C, Huan Z, Fan ZH. An improvement for the acceleration technique based on monostatic bistatic equivalence for shooting and bouncing ray method. Microw Opt Techn Lett 2011; 53: 1178–1183.
Cocheril Y, Vauzelle R. A new ray-tracing based wave propagation model including rough surfaces scattering. Prog Electromagn Res 2007; 75: 357–381.
Raida Z, Lukes Z, Lacik J. On using ray-launching method for modeling rotational spectrometer. Radioengineering 2008; 17: 98–107. de Adana SF, Gutierrez Blanco O, Diego IG, Perez Arriaga J, Catedra MF. Propagation model based on ray tracing for the design of personal communication systems in indoor environments. IEEE T Veh Technol 2000; 49: 2105–2112.
Saeidi C, Hodjatkashani F. Modified angular Z-Buffer as an acceleration technique for ray tracing. IEEE T Antenn Propag 2010; 58: 1822–1825.
Mohtashami V, Shishegar AA. Modified wavefront decomposition method for fast and accurate ray-tracing simula- tion. IET Microw Antenna P 2012; 4: 295–304.
Cormen TH, Leiserson CE, Rivest RL, Stein C. Introduction to Algorithms. 3rd ed. Cambridge, MA, USA: MIT Press, 2009.
Gatland IR. Thin lens ray tracing. Am J Phys 2002; 70: 1184.
Smith CJ. A Degree Physics. Part III, Optics. London, UK: Edward Arnold Publishers, 1960.
Tsingos N, Funkhouser T, Ngan A, Carlbom I. Modelling acoustics in virtual environments using the uniform theory of diffraction. In: Proceedings of the 28th Annual Conference on Computer Graphics and Interactive Techniques. New York, NY, USA: ACM, 2001. pp. 545–552.
Pena D, Feick R, Hristov HD, Grote W. Measurement and modeling of propagation losses in brick and concrete walls for the 900-MHz band. IEEE T Antenn Propag 2003; 51: 31–39.