| With the increasing requirements for real-time ray tracing,researchers are continuing to propose more efficient acceleration algorithms,and equipment manufacturers keep upgrading the hardware.Due to the natural parallelism,it is a good choice for the ray tracing algorithm to parallel acceleration by GPUs.The ray tracing is mainly applied to image rendering previously and now it is also spreading into various fields such as electromagnetic scattering simulation and sound field simulation.Compared with other structures,KD-Tree,as a widely used acceleration structure in ray tracing,has better acceleration performance on ray tracing.However,it takes a long time to construct the KD-Tree,which limits the application of KD-Tree.Most research about KD-Tree only focus on the acceleration of SAH algorithm.Based on the existing construction methods,a parallel construction scheme,which uses GPU to accelerate the whole process,is proposed to increase the speed of construction.The main innovations of this thesis are as follows:1.A method of distributing triangular-patches on GPU is proposed.Aiming at the problem that the triangular-patches distribution is completed on the CPU,this thesis introduces an idea of parallel computing prefix sum and proposes a parallel triangular-patches distribution scheme on GPU,which effectively reduces the distribution time and the amount of transmission data between the CPU and GPU.Using the benchmark model,the total time for distributing triangular-patches to child nodes on GPU is reduced by more than 50%rather than the distributing work on CPU.2.Aiming at the memory growth problem caused by overlapping triangular-patches in the process of constructing KD-Tree,this thesis proposes a method for estimating the size of pre-applied memory.The length of the final triangular-patches array is estimated according to the number of initial triangular-patches,which can ensure that there is sufficient memory at the beginning of the program.To use the applied memory reasonably,a method of dynamically allocating memory according to the proportion of the number of triangular-patches in the child nodes is proposed for achieving conflict-free access to the pre-applied memory.Combined the optimization algorithm for calculating the SAH value,which is introduced in this thesis with the reduction algorithm,the calculation process of the minimum SAH value is accelerated.In the experimental environment of this thesis,the proposed method used for calculating the minimum SAH value reaches 5.8 × speedup than the serial algorithm.3.Based on the above work,aiming at the problem of frequent data transmission between CPU and GPU caused by recursive constructing,a breadth-first based method to construct KD-Tree is proposed.In this method,two queues are used to store split nodes in the even layers and the odd ones,respectively,KD-Tree is constructed layer by layer.Each layer only sends the CPU the number of triangular-patches in split node at the next layer.The whole constructing tasks are completed on GPU and the CPU only needs to calculate the number of threads,which significantly reduces the frequency of data interaction between the CPU and the GPU,and reduces the time cost.The experimental results show that the GPU parallel algorithm proposed in this thesis can construct KD-Tree rapidly in common scenarios without reducing the quality of KD-Tree.Using the method proposed in this thesis to construct KD-Tree,the acceleration can reach 4.1-7.9 × and 1.2-1.3 × compared with the traditional serial algorithm and compared with the parallel algorithm based on space tree,respectively. |
PDF Full Text Request