A Novel 3D Ray-tracing Acceleration Technique Based on Kd-tree Algorithm for Radio Propagation Predictionin Complex Indoor Environment

This paper presents a new 3D ray tracing acceleration technique based on the kd-tree algorithm for predicting the radio coverage in complex indoor environment. For each ray emitted from the transmitter, all the valid ray propagation paths can be searched for by the hybrid ray tracing model which combines the shooting and bouncing ray (SBR) and the image method. The kd-tree algorithm is mainly used to accelerate the intersection test of ray tracing. In addition, the receiver power strength can be calculated based on geometrical optics (GO) and uniform theory of diffraction (UTD). As expected, the proposed method performs higher superiority than the conventional ray tracing model in terms of computational efficiency. Meanwhile, it also shows good agreement with measurements and the Winprop's simulated results with respect to computational accuracy.