Research And Implementation Of Ray Tracing Software With Divide And Conquer Accelerating Algorithm

Ray tracing is a method for rendering realistic images, which has been widely applied to games, movies, animation and other areas. Since the basic principle of ray tracing is that generating images through shooting rays which intersect with objects in the scene, its computational complexity is very high. The main improvement of ray tracer is establishing acceleration structures to reduce the frequency of intersection between rays and objects. Although this method gain rendering acceleration, ray tracer software must maintain this structures which is an additional overhead for it. Therefore, a divide and conquer ray tracing method which reduce the frequency of intersection between rays and objects, and also does not occupy memory is necessary. This paper launches a study based on a divide and conquer ray tracer software design and acceleration structures. Below are the main contents:1. Introduce and research basic ray tracing fundamental theory, including anti-aliasing, sampling techniques, light.2. A generic basic ray tracing software framework is proposed and implemented based on above theory. The main contents include generating images through shooting rays intersected with objects called basic ray tracing approach, abstracting anti-aliasing, sampling, light and acceleration structures techniques. It has good generic and scalability. The implementation of software does not contain third library. It is implemented by C++. This is the basic work of following research.3. Introduce construction and traverse of Kd-tree and Grids based on basic ray tracing. Implement Kd-tree and Grids ray tracing acceleration algorithms based on basic ray tracing software framework. The experiment proves the effectiveness of these acceleration algorithms.4. The innovation of this paper is that research and implement Kd-tree based divide and conquer ray tracing algorithm, and introduce BVH idea to divide and conquer ray tracer. Implementation of divide and conquer ray tracer is based on basic ray tracing software framework. At last, the content of this paper form a divide and conquer ray tracing software. This method does not occupy extra memory. Rays intersect with primitives, meanwhile, it constructs acceleration structures. Also, its rendering speed accelerates. Combine above analysis, this paper implements Kd-tree and BVH divide conquer ray tracing approaches. The experiment shows that divide and conquer ray tracer has good efficiency in both statistic and dynamic scenes. This paper further proves that BVH divide and conquer ray tracer is better than Kd-tree divide and conquer ray tracer.