Fast Algorithm Of Target Electromagnetic Scattering Based On KD-tree

Shooting and Bouncing Rays method is a kind of high-frequency approximation algorithm in multi-scattering of complex object, widely applied in the multi-scattering calculation of objects having dihedral or cavity structure, and the calculation accuracy meets engineering requirements. However, the significant drawbacks of Shooting and Bouncing Rays method are the huge ray numbers and the low efficiency in the intersection calculation of ray and triangles. Especially in the calculation of electrical large complex objects, the ray tracing time is extremely time-consuming. Under the condition of ensuring accuracy, there are two ways to reduce the calculation time: reducing ray numbers and improving the efficiency of intersection test. My research focus is to reduce ray tracing time by improve intersection efficiency of ray and triangles.KD-tree is a special binary search tree in data structure. In Computer Graphics, KD-tree is applied as an accelerated data structure in Ray Tracing algorithm to improve the intersection test efficiency of ray and scenes. Based on the similarity of Shooting and Bouncing Rays method and Ray Tracing algorithm, high quality KD-tree with ropes is constructed depending on faces information of electrical large complex object. After the construction procedure, stack-less traversal algorithm is applied in this paper to update the reflecting counters, reflecting position, reflection direction of each ray. At the exit Face of ray tubes, Physical optics method is used to calculate scattering field of far field of current tubes. The total scattering field is obtained by summing the contributions of each ray tubes. The main work of the paper includes the following:1. Traditional Shooting and Bouncing Ray method is implemented and local-modified based on the basic principle of the algorithm. The results obtained by the method are very close to software simulation results through comparison.2. According to the geometrical structure of the target, High quality KD-tree with is built. The intersection of faces and bounding box is solved and ropes generation technique is simplified. Based on the ropes, the traversal procedure of rays is implemented and the total scattering field is obtained. The introduction of KD-tree withropes, extremely improve the efficiency of Shooting and Bouncing Rays method. Algorithm simulation results show that the efficiency improves by nearly 100 times at most, proving the "Soft acceleration" of KD-tree.3. Combined with CUDA parallel programming techniques, Shooting and Bouncing Ray parallel method is achieved. But with the increase of objects size or the frequency of electromagnetic waves, the ray numbers increase extremely and the ray tracing procedure is yet time-consuming. The introduction of CUDA, a kind of Multi-thread parallel programming techniques, provides possibilities to solve the problem. Besides, the ray tracing procedure of each ray can easily map one thread in GPU hardware. At last the efficiency of difference of kernel function parameter configuration and the difference of KD-tree height are also discussed in this paper. The simulation results prove the acceleration function of GPU hardware, achieving the collaboration of "Soft acceleration" of KD-tree and "hardware acceleration" of GPU.