Research On Parallel Ray Tracing Based On KD-tree In CPU/GPU Heterogeneous Platform

Ray tracing is one of the classic algorithms of global illumination,it provides a complete solution for photo-realistic images rendering.KD-tree is one of the most popular acceleration data structure for ray tracing.Ray tracing based on KD-tree has been improved both on CPU and GPU,but there are still some problems such as inefficient parallel performance of KD-tree construction and scene traversal.In the heterogeneous platform,existing algorithm unable to use CPU and GPU computing power at the same time.In this thesis,parallel ray tracing in the heterogeneous platform is taken as the object of study.A multi-level construction algorithm of KD-tree acceleration structure and path compression pretreatment before scene traversal are proposed.Rendering process of ray tracing is also improved according to the characteristics of the heterogeneous platform.Finally,the algorithm is verified by experiments and the result proved that the improved algorithm in this thesis performs better.Specific research work is as follows:(1)A multi-level construction algorithm of KD-tree is proposed to improving parallel performance during ray tracing rendering.The multi-level construction algorithm based on SAH,but at the first level of the construction,uniform grid is used to divide space quickly.Then approximate SAH based on min-max binning algorithm and exact SAH algorithm are used in second and third level.The time consuming of KD-tree construction is been reduced by using different algorithms in different stages.(2)During the process of ray traversal,there may be many blank nodes without any primitive in them.As Morton Code is introduced when construct the KD-tree,this thesis uses a path compression algorithm based on Morton Code to reduce the cost of traversal for the blank nodes.(3)In addition,optimization algorithm for only CPU or GPU can neither make the best use of them at the same time.In this thesis,a complete process,including task allocation and data management,is presented based on CUDA.Because the consideration of the heterogeneous platform,the rendering time-consuming for 3D models is shortened.As described above,two experiments are designed to verify the research in this thesis.From the experimental results obtained the following conclusions: Firstly,under the same conditions,compared to the conventional ray tracing based on KD-tree,algorithm using multilevel KD-tree construction and path compression achieves better performance.Secondly,under the same conditions,compared to the algorithm optimized for only CPU or GPU,the improved algorithm for heterogeneous platform can achieve better rendering speed.In summary,our research on parallel ray tracing based on KD-tree in heterogeneous platform achieved remarkable results,greatly improved the ray tracing rendering efficiency.