OpenCL-based Real-time KD-Tree And Raytracing For Dynamic Scene

Ray Tracing is a rendering algorithm for global illumination effects. Due to its simplicity, it is widely applied in film production, industrial design, simulation, computer-aided design, etc. However it is far from being real time due to its high computational complexity. Real-time ray tracing is a long-term aim in computer graphics. In the past decades, high quality acceleration structure and parallel algorithm are adopted to accelerate the ray tracing. In this thesis, a cross-platform algorithm for ray tracing dynamic scenes based on OpenCL is proposed. By exploiting general purpose GPU parallel processing ability and evaluating the performance of Multi-Core CPU, three main steps in ray tracing, i.e., KD-Tree construction, scene traversal and shading, are totally performed on GPU. These three steps are scheduled by CPU. Thus GPU computing ability is exploited fully and the data transfer overhead is reduced efficiently. By designing algorithms of parallel partitions and parallel SAH, proposing strategies of compact data management and offset mark based leaf node storage, we construct a high quality KD-Tree for dynamic scene in GPU in real-time. It effectively facilitates scene traversal. We also use a "belong to" approach to describe the relationship between nodes and primitives, and a simple way to control the KD-Tree depth. Compared with CPU KD-Tree ray tracing algorithm, ours is breadth-first and suitable for large scale parallel implementation on SIMD architecture GPU. Compared with CUDA GPU KD-Tree ray tracing algorithm, ours is versatile and can be implemented on both NVIDIA GPU(G92 or higher) and AMD GPU(HD5000 series or higher) with lower computational complexity. Experimental results show that the proposed algorithm is capable to ray trace a middle scale dynamic scene in real-time on both NVIDIA GTX465 and AMD HD5850.