Scalable Algorithms for Realistic Real-time Rendering

In computer graphics, realistic rendering of virtual scenes is a computationally complex problem. State-of-the-art rendering technology must become more scalable to meet the performance requirements for demanding real-time applications. This dissertation is concerned with core algorithms for rendering, focusing on the ray tracing method in particular, to support and saturate recent massively parallel computer systems, i.e., to distribute the complex computations very efficiently among a large number of processing elements. More specifically, the three targeted main contributions are: 1. Collaboration framework for large-scale distributed memory computers The purpose of the collaboration framework is to enable scalable rendering in real-time on a distributed memory computer. As an infrastructure layer it manages the explicit communication within a network of distributed memory nodes transparently for the rendering application. The research is focused on designing a communication protocol resilient against delays and negligible in overhead, relying exclusively on one-sided and asynchronous data transfers. The hypothesis is that a loosely coupled system like this is able to scale linearly with the number of nodes, which is tested by directly measuring all possible communication-induced delays as well as the overall rendering throughput. 2. Ray tracing algorithms designed for vector processing Vector processors are to be efficiently utilized for improved ray tracing performance. This requires the basic, scalar traversal algorithm to be reformulated in order to expose a high degree of fine-grained data parallelism. Two approaches are investigated: traversing multiple rays simultaneously, and performing multiple traversal steps at once. Efficiently establishing coherence in a group of rays as well as avoiding sorting of the nodes in a multi-traversal step are the defining research goals. 3. Multi-threaded schedule and memory management for the ray tracing acceleration structure Construction times of high-quality acceleration structures are to be reduced by improvements to multi-threaded scalability and utilization of vector processors. Research is directed at eliminating the following scalability bottlenecks: dynamic memory growth caused by the primitive splits required for high- quality structures, and top-level hierarchy construction where simple task par- allelism is not readily available. Additional research addresses how to expose scatter/gather-free data-parallelism for efficient vector processing. Together, these contributions form a scalable, high-performance basis for real-time, ray tracing-based rendering, and a prototype path tracing application implemented on top of this basis serves as a demonstration. The key insight driving this dissertation is that the computational power necessary for realistic light transport for real-time rendering applications demands massively parallel computers, which in turn require highly scalable algorithms. Therefore this dissertation provides important research along the path towards virtual reality