In computer graphics, algorithms that attempt to create photographic images by simulating light transport are collectively known as Global Illumination methods. The most versatile of these are based on ray tracing (following ray paths through a scene), and numerical integration using random or quasi-random sampling. While ray tracing and sampling methods in global illumination have progressed much in the last two decades, the goal of fast and accurate simulation of light transport remains elusive. This dissertation presents a number of new sampling methods that attempt to address some of the shortcomings of existing global illumination algorithms. The first part of the dissertation concentrates on memory issues related to ray tracing of large scenes. In this part, we present memory-efficient lightweight bounding volumes as a data structure that can substantially reduce the memory overhead of a ray tracer, allowing more complicated scenes to be ray traced without complicated caching schemes. Part two of the dissertation concerns itself with sampling algorithms related to direct lighting, an important subset of global illumination. In this part, we develop two stage importance sampling} to sample the product of the BRDF function and a large light source such as an environment map. We then extend this method to include all three terms of the direct lighting equation, sampling the triple product of the BRDF, lighting and visibility. We show that the new sampling methods have a number of advantages over existing direct lighting algorithms, including comparatively low memory overhead, little precomputation, and the ability to sample all three terms of the direct lighting equation. Finally, the third part of the dissertation discusses sampling algorithms in the context of general global illumination. In this part, we develop two new algorithms that attempt to improve the sampling distribution over existing techniques by exploiting information gained during the course of sampling. The first of these methods, energy redistribution path tracing, works by using path mutation to spread energy, and thus share sampling information, between pixels. The second method, sample swarming, shares information gained during sampling by keeping importance maps for each pixel in the rendered image. Whenever a new pixel is to be rendered, the maps from neighboring pixels are averaged, propagating importance information through the scene. We demonstrate that both of these methods can perform substantially better than existing global illumination algorithms in a number of common rendering contexts.



College and Department

Physical and Mathematical Sciences; Computer Science



Date Submitted


Document Type





Computer graphics, Photorealism, Sampling, Monte Carlo