Interactive Direct Illumination in Complex Environments.

PhD thesis, Cornell University, June 2004.

Modeling the interaction of light with real-world environments is a difficult problem. In particular, the geometric and lighting complexity required to approximate reality are huge challenges. The ``Ray Tracing'' algorithm is well-suited to deal with geometric complexity since its performance is sub-linear in the number of geometric primitives. However, its computational cost is linear in the number of light sources. This leads to poor performance in environments with complex lighting.

In this thesis we present two algorithms that accelerate the rendering of direct lighting for complex environments within the context of a ray tracer. The first algorithm, ``Local Illumination Environments'' addresses direct lighting acceleration in scenes with up to a few dozen light sources. The second algorithm, ``Hierarchical Light Clusters'' accelerates direct lighting in models with hundreds to thousands of light sources.

The ``Local Illumination Environments'' algorithm reduces the cost of computing light visibility, the most expensive part of the direct lighting computation. It does so through an asynchronous process that caches, in a spatial data structure, the geometric primitives required to evaluate light visibility. This approach completely eliminates the cost of light visibility for fully visible and fully occluded light sources. It also substantially reduces the time to evaluate visibility from partially visible light sources by eliminating the cost of a traditional acceleration structure.

The ``Hierarchical Light Clusters'' algorithm reduces direct lighting computation in environments with very large numbers of light sources. This is done by using a single bright light to approximate the contribution of a group of lights. We present a locally adaptive technique that determines when this approximation is valid. We also introduce three algorithms that make use of this approach to provide varying levels of quality and performance.

``Local Illumination Environments'' and ``Hierarchical Light Clusters'' both provide order-of-magnitude acceleration in the computation of direct lighting over traditional ray tracing approaches. Together, they can be used to interactively generate images of models of widely varying geometric and lighting complexity.

This paper is available as a PDF file Fer04.pdf (3.5M).