| Accurately determining the visible region of a target relative to the sound source is a crucial step in calculating the acoustic characteristics of underwater targets. The ray tracing method based on the KD-tree (K-Dimensional Tree) can efficiently compute the intersection of a large number of rays with target facets, making it applicable to solving for the area illuminated by the sound beam. However, this method suffers from a significant efficiency bottleneck: before a ray intersects with the final leaf bounding box, it often must traverse multiple leaf bounding boxes and perform ray-facets intersection tests with each facet within every bounding box, resulting in substantial redundant computation. This computational approach significantly increases the time cost, particularly when handling complex target models or large-scale ray sets. To address these issues, this paper proposes a stackless traversal method based on an improved threaded KD-Tree. This method reduces the volume of leaf bounding boxes generated by the traditional threaded KD-tree, decreases the number of leaf bounding boxes traversed by rays, minimizes invalid intersection calculations between rays and facets, and significantly enhances tracing efficiency. Additionally, to overcome the time bottleneck of the traditional serial computing mode, this paper implements parallel processing of ray tracing on the CUDA (Compute Unified Device Architecture) platform using a GPU (Graphics Processing Unit), further accelerating the computation process. Experimental results demonstrate that, compared to the traditional serial computing method, the ray tracing algorithm proposed in this paper, based on the improved KD-Tree structure, achieves a computational efficiency improvement of 30.23% to 45.31%. After parallelization, the computational efficiency increases to 7.03 to 13.47 times that of the traditional method. |
