Acceleration methods for ray tracing based global illumination [Elektronische Ressource] / Holger Dammertz

Sujets

• Informatik

Informations

• Publié par: universitat_ulm
• Publié le: 01 janvier 2011
• Nombre de lectures: 15
• Langue: English
• Poids de l'ouvrage: 9 Mo

Extrait

Acceleration Methods for Ray Tracing based
Global Illumination
Dissertation
zur Erlangung des Doktorgrades
Dr. rer. nat.
der Fakultät für Ingenieurwissenschaften und Informatik
der Universität Ulm
vorgelegt von
Holger Dammertz
aus München
Institut für Medieninformatik, 2011Amtierender Dekan: Prof. Dr.-Ing. Klaus Dietmayer,
Ulm University, Germany
Gutachter: Dr. rer. nat. Alexander Keller,
mental images, Berlin
Gutachter: Prof. Dr.-Ing. Hendrik P. A. Lensch,
Ulm University, Germany
Externer Gutachter: Peter Shirley, Adjunct Professor, Ph.D.
University of Utah, Salt Lake City, UT, USA
Tag der Promotion: 19.04.2011Abstract
The generation of photorealistic images is one of the major topics in computer gra-
phics. By using the principles of physical light propagation, images that are indistin-
guishable from real photographs can be generated. This computation, however, is a
very time-consuming task. When simulating the real behavior of light, individual images
can take hours to be of sufficient quality. For this reason movie production has relied
on artist driven methods to generate life-like images. Only recently there has been a
convergence of techniques from physically based simulation and movie production that
allowed the use of these techniques in a production environment. In this thesis we advo-
cate this convergence and develop novel algorithms to solve the problems of computing
high quality photo-realistic images for complex scenes. We investigate and extend the
algorithms that are used to generate such images on a computer and we contribute
novel techniques that allow to perform the necessary ray-tracing based computations
faster. We consider the whole image generation pipeline starting with the low level
fundamentals of fast ray tracing on modern computer architectures up to algorithmic
improvements on the highest level of full photo-realistic image generation systems.
In particular, we develop a novel multi-branching acceleration structure for high per-
formance ray tracing and extend the underlying data structures by software caching to
further accelerate the result. We also provide a detailed analysis on the factors that
influence ray tracing speed and derive strategies for significant improvements. These
create the foundations for the development of a production quality global illumination
rendering system. We present the system and develop several techniques that make
it usable for realistic applications. The key aspect in this system is a path space par-
titioning method to allow for efficient handling of highly complex illumination situations
as well as the handling of complex material properties. We further develop methods
to improve the illumination computation from environment maps and provide a filtering
technique for preview applications.
iiiAcknowledgments
Many thanks to
Alexander Keller for his guidance, support, and his passion for computer graphics
Johannes Hanika for a fun and highly productive research cooperation
Hendrik P. A. Lensch for his feedback, support and for providing the environment
to finish this Ph.D. thesis
the old and new computer graphics group
mental images for the financial support
Carsten Wächter, Matthias Raab, Leonhard Grünschloss, and Daniel Seibert for
proofreading and many rendering related discussions
my wife and family
ivContents
1 Introduction 1
1.1 Physically Based Rendering and Visual Effects . . . . . . . . . . . . . . . 2
1.2 Thesis Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2.1 Summary of Contributions . . . . . . . . . . . . . . . . . . . . . . . 3
2 Image Generation Fundamentals 5
2.1 Image Generation by Camera Simulation . . . . . . . . . . . . . . . . . . 5
2.2 Light Transport Simulation by Path Tracing . . . . . . . . . . . . . . . . . 8
2.3 Rendering Software Architecture Design . . . . . . . . . . . . . . . . . . . 9
2.3.1 Enabling Physically Based Global Illumination in Movie Production 9
2.3.2 Scene Description . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.3.3 Boundary Representation . . . . . . . . . . . . . . . . . . . . . . . 11
2.3.4 Material . . . . . . . . . . . . . . . . . . . . . . . 15
2.3.5 Sampling Light Sources . . . . . . . . . . . . . . . . . . . . . . . . 18
2.4 Processor Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3 Efficient Tracing of Incoherent Rays 31
3.1 Overview of Acceleration Data Structures . . . . . . . . . . . . . . . . . . 33
3.1.1 Bounding Volume Hierarchies . . . . . . . . . . . . . . . . . . . . 33
3.1.2 kd-Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.1.3 Grids . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.2 n-ary Bounding Volume Hierarchies . . . . . . . . . . . . . . . . . . . . . 36
3.3 Investigation ofn-ary Hierarchy Traversal . . . . . . . . . . . . . . . . . . 38
3.3.1 Data Structures for Traversal . . . . . . . . . . . . . . . . . . . . . 38
3.3.2 Unsorted Traversal . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.3.3 Sorted Traversal . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.3.4 t-Far Stack for Early Out . . . . . . . . . . . . . . . . . . . . . . . . 48
3.4 On Demand Construction . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
v3.5 Results and Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.5.1 Rendering Performance . . . . . . . . . . . . . . . . . . . . . . . . 50
3.5.2 Memory Bound Performance . . . . . . . . . . . . . . . . . . . . . 51
3.5.3 Explicit Coherence in Ray Tracing . . . . . . . . . . . . . . . . . . 51
4 Efficiency of Hierarchies 57
4.1 Overview of Hierarchy Construction Heuristics . . . . . . . . . . . . . . . 58
4.1.1 Median Split . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
4.1.2 Center Split . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
4.1.3 Surface Area Heuristic (SAH) . . . . . . . . . . . . . . . . . . . . 60
4.2 Split Heuristics for the QBVH . . . . . . . . . . . . . . . . . . . . . . . . . 61
4.2.1 Visual Comparison of Center-Split and SAH-Split . . . . . . . . . 62
4.2.2 Validity of the SAH for Physically Based Rendering . . . . . . . . 62
4.3 More Efficient Hierarchies by Triangle Subdivision . . . . . . . . . . . . . 66
4.3.1 Edge Volume Heuristic . . . . . . . . . . . . . . . . . . . . . . . . 67
4.3.2 Bounding Box Area Heuristic (BBAH) . . . . . . . . . . . . . . . . 72
4.3.3 Leaf Compaction . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
4.3.4 Triangle Subdivision and the SAH . . . . . . . . . . . . . . . . . . 75
4.4 Crack-Free Triangle Intersection . . . . . . . . . . . . . . . . . . . . . . . 82
4.5 SAH Clustering for Ray Tracing of Dynamic Scenes . . . . . . . . . . . . 83
4.6 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
5 Software Caching for Ray Tracing 91
5.1 Triangle Intersection and SIMD Caching . . . . . . . . . . . . . . . . . . . 92
5.2 Parallel Triangle Intersection . . . . . . . . . . . . . . . . . . . . . . . . . 97
5.3 Accelerating Shadow Rays . . . . . . . . . . . . . . . . . . . . . . . . . . 98
5.4 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
6 Practical Physically-Based Image Synthesis 105
6.1 Principles of Light Transport Simulation . . . . . . . . . . . . . . . . . . . 106
6.1.1 Path Tracing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
6.1.2 Light Tracing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
6.1.3 Photon Mapping . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
6.1.4 Instant Radiosity . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
6.2 Hierarchical Monte Carlo Integro-Approximation . . . . . . . . . . . . . . 112
6.2.1 Monte Carlo Integration and Monte Carlo Integro-Approximation . 113
6.2.2 Iterative Block Partitioning and Termination . . . . . . . . . . . . . 114
6.2.3 Adaptive Light Tracing . . . . . . . . . . . . . . . . . . . . . . . . . 118
6.2.4 Results and Discussion . . . . . . . . . . . . . . . . . . . . . . . . 119
6.3 Path Space Partitioning . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
6.3.1 Eye Path Generation and Glossy Effects . . . . . . . . . . . . . . . 130
6.3.2 Point-Light-Based Diffuse Illumination . . . . . . . . . . . . . . . . 132
6.3.3 Caustic Histogram Method . . . . . . . . . . . . . . . . . . . . . . 133
6.3.4 Subsurface Scattering . . . . . . . . . . . . . . . . . . . . . . . . . 136
vi6.3.5 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
6.3.6 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
6.4 High Dynamic Range Environment Map Lighting . . . . . . . . . . . . . . 146
6.4.1 Domains of Integration . . . . . . . . . . . . . . . . . . . . . . . . . 146
6.4.2 Plane Sampling for Starting Light Paths from Environment Maps . 148
6.4.3 Results and Discussion . . . . . . . . . . . . . . . . . . . . . . . . 150
6.5 Interactive Preview for Design and Editing . . . . . . . . . . . . . . . . . . 153
6.5.1 Edge-Avoiding À-Trous Irradiance Filtering . . . . . . . . . . . . . 155
6.5.2 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
6.5.3 Results . . . . . . . . . . . .