Efficient Acceleration Structure For High Performance Graphics Rendering

As the rapid development of graphics hardware and the growing needs for photorealistic pictures from virtual reality system, games and film production, research on high-performance graphics rendering becomes more important and urgent. High-performance graphics rendering requires reducing rendering time while improving rendering quality. Ray tracing used to generate photorealistic pictures needs intense visual computation. Efficient acceleration structure helps significantly reduce computation, decrease the complexity of rendering, and reduce rendering time. However, high-performance graphics rendering requires acceleration structure with higher quality, faster construction and traversal, which increases the design complexity.This dissertation discusses an efficient acceleration structure methodology for high performance graphics rendering:Our first focus is what a fast parallel construction algorithm and efficient traversal algorithm will be fundamental for high quality acceleration structure, especially how to solve the irregular, dynamic and incoherent computation. Our second focus is how the current graphics algorithm should be evolved to efficiently render some advanced photorealistic effects. Based on their structure features and the influence on acceleration structure, we propose special acceleration structure to reduce the computational complexity, and render the scene more efficiently.In summary, this dissertation mainly identifies four problem areas:a highly parallel construction algorithm and efficient traversal algorithm for high quality acceleration structure, support for dynamic scenes, support for secondary ray effects, support for motion blur effect. The main contributions are listed as follows:●We propose a novel GPU data structure MKD to solve complex problems caused by hierarchy structure on GPU at both construction time and traversal time. We introduce a multi-dimensional SAH parallel construction to rapidly construct high quality acceleration structure. We design a MKD fast traversal algorithm, and use an incremental ordered combination to implement highly efficient ordered traversal. We offer an adaptive ray packet organization, and dynamically adjust data processing method. We also describe an efficient queue communication mechanism to distribute the work efficiently across the available processing units.●In order to fast ray tracing for dynamic scene, we propose an approach for fast BVH construction based on tree structure feature and multi-core architecture. This technique uses fine-grained parallelism granularity, and adaptes different construction strategies for the early, midterm and late construction phases.●We describe an efficient traversal algorithm for secondary rays. Considering dynamic and irregular features under the GPU memory hierarchy, we schedule tasks according to coherent data under the data-driven execution, and design a dynamic node visit strategy. These schemes reorganize the data, exploit inherent parallelism, reduce memory access, increase ray coherence, and optimize bandwidth usage.●We present a construction and ray traversal algorithm designed to accelerate rendering of scenes with high quality motion blur, which focuses on capturing irregular motion. We classify primitive motions into regular motion and irregular motion based on motion vector. At build-time, we track primitives with significantly irregular motion, and handle these difficult primitives at traversal time. We design a based time cost model to construct and traversal according to the time attribute. We also describe two heuristics to switch automatically the shrinking and updating during traversal. These two schemes can efficiently control the adjusting cost. At last, we present a building technique for the scene containing the big triangles, and reduce ray shoot costs.