Research On Ray Tracing Based Photorealistic Global Illumination Issues

Digital animation and movie industry combines the information technology with arts and humanities, which has a huge economic potential. In recent years, the government has put in a great effort in this area. As an intelligence-intensive, non-polluting, high value-added industry, digital animation and movie industry is not only important to the development of the country's economic, but also important to propagate the national cultural and to enhance the country's image. The3D rendering technique plays a key part in the creation of the animations. According to statistics, all box office champions during the11years from2001to2011are masterpieces of3D rendering technique.Rendering is a process to observe the virtual scene and generate image based on the result. Depending on the application of different focus, rendering algorithm can be divided into two categories, that is, the real-time rendering which aims at fast image generation, and the offline rendering which aims at high-quality image generation. Rendering uses frame to describe an observation to the virtual scene in a particular time. Animation is composed of a group of consecutive frames. In order to ensure the visual continuity, animation usually requires a frame rate of no less than24frames per second. Therefore, a two-hour animation contains at least172,800frames. Even if the average rendering speed is one frame per minute, it takes120days to complete the whole animation. In order to achieve highly realistic lighting effects, animation production usually requires the introduction of a global illumination model. As an important global illumination algorithm, ray tracing generates realistic images through simulating the propagation of light. However, the highly complex scene and light model presents a challenge to ray tracing algorithm.The ray tracing algorithm for global illumination can be further divided into the recursive ray tracing, distributed ray tracing and Monte Carlo ray tracing. Recursive ray tracing can realize direct illumination, specular reflection and refraction effects. The distributed ray tracing introduces the idea of random sampling, and thus can realize area light, soft shadows, depth of field and motion blur. The light transfer equation can be used to describe the complete global illumination effects. However, due to the difficulty of describing incident light in the equation, solving the equation analytically is not feasible. Monte Carlo ray tracing gets discrete samples from the solution space of light transfer equation, and uses them to calculate the approximation to the true result. To reduce the error (noise) and ensure the coverage of all possible lighting effects, Monte Carlo ray tracing must launch a lot of rays.The process of a ray contains two parts, that is, visibility test and shading. The core of the visibility test is to find an intersection. There are two kinds of visibility test, which are finding the closest intersection and finding any intersection. Shading is only performed on the closest intersection. Finding any intersection is just a way to determine occluding. The naive way to find an intersection is to test the ray with all objects. However, the time complexity of this operation is O(N). It's unacceptable except for extremely simple scene. Visibility test usually employs acceleration structure to accelerate the intersection finding. KD tree and BVH are the most commonly used acceleration structure. They act as a spatial index tree, and can reduce the searching complexity to O(LogN). The Surface Area Heuristic (SAH) method is the best way to improve the quality of the tree. KD tree and BVH face two main problems. First, the construction time of the tree for a scene with high complexity is slow. Second, for a given tree, the traversal time for a huge number of sampling rays is also slow.When the closest intersection is found, ray tracing needs to shade the intersection point. The process is usually described by shader that is a program written in shading language. Every object in the scene is attached with a shader, and the shader corresponding to the intersection is executed at run-time by the language interpreter. The shading language provides the artists a flexible way for creation. However, because of the need of interpreting, the running efficiency of the shader is low. For a simple shading instruction, most execution time is spent on interpreting. In practice, a shader is usually made by a large number of simple instructions. Therefore, the total time spent on interpreting is considerable.Today, the development of the parallel technology is extremely rapid. How to absorb the achievements in the parallel technology field and to use them to improve the efficiency of rendering algorithms, becomes a hot research area. In this thesis, we present three optimized parallel algorithm to solve the computationally intensive problem in global illumination.First, to decrease the construction time of the acceleration structure for complex scene, we present a two-level parallel construction algorithm for KD tree and BVH. We define the parallel task unit as the construction of a tree node. The upper level of our parallel model splits the whole task set into several subsets, and assigns a persistent thread for each subset. Each thread has its own task queue. The load balance is achieved by employing work stealing. In the task of building large node, the SAH evaluation is a time consuming step. We accelerate this process by utilizing SIMD processor array which is located in the lower level of our parallel model. The experimental result shows our parallel method can significantly decrease the construction time for KD tree and BVH.Second, to increase the traversal speed of massive rays, we present a hybrid parallel traversal algorithm for KD tree and BVH. The hybrid model contains two parts. The scheduling part is responsible for the generating and scheduling ray traversal tasks. The executing part is responsible for performing the traversal for a large number of rays. We also present SIMD friendly traversal algorithm for BVH, to further improve the SIMD utilization of BVH traversal. The experimental result shows our method can greatly decrease the traversal time for massive rays.Third, to speed up the interpreting of the shading program, we present parallel shader interpreting algorithm which can efficiently run on the SIMD processor array. We introduce a new shading language called shading graph, which is suitable for modular shader design. It can be equivalently transformed into a two level DAG The low level DAG describes the dependency of the shading instructions. The high level DAG describes the dependency of the low level DAGs. In order to translate the DAG into instruction sequence, a two-step topological ordering is performed. First, topological ordering is performed on every low level DAG And then the generated sequences for each DAG are linked together according to the topological ordering result of the high level DAGs. The connection of the low level DAGs are translated into data transfer instruction, and inserted into the sequence. The interpreting algorithm takes a large number of shading points as input. At each step, the ready instructions from all shaders of the shading points are collected and reordered by using operator as the key. Then the reordered instructions are split into small packets and sent to SIMD processor array for massive parallel processing. The experimental result shows our interpreting method can efficiently decrease the shading time.