Hierarchical Algorithms for Illumination (Thesis)
Abstract:
This dissertation is a discussion and development of hierarchical
algorithms for illumination. These algorithms operate through recursive,
adaptive refinement of the environment into hierarchical meshes ---
rather than computing light transport only between elements at the finest
level of refinement, the algorithms allow computation of transport between
higher level subpatches, as controlled by user specified error bounds.
As discussed in this dissertation, employment of hierarchical methods
yields significant savings in computation.
The initial work in hierarchical methods was that of Hanrahan and Salzman
for the computation of radiosity over unoccluded environments. In this
dissertation, we discuss extension of the algorithm to occluded
environments, incorporating visibility heuristics and acceleration via
radiosity weighting. Given an environment consisting of $k$ polygonal
patches and $n$ elements at the finest level of refinement, the
algorithm requires at most $O(n + k^2)$ transport interactions; traditional
methods require $O(n^2)$.
Application of hierarchical transport to nondiffuse reflection is developed
through the derivation of a radiance formulation for discrete three point
transport, incorporating a new measure and description of reflectance: {em
area reflectance}. This formulation and associated reflectance allow an
estimate of error in the computation of radiance across triples of surface
elements, and lead directly to a hierarchical refinement algorithm for
global illumination.
We have implemented and analyzed this algorithm over surfaces exhibiting
glossy and diffuse reflection. Theoretical growth in transport computation
is shown to be $O(n + k^3)$ --- this growth is exhibited in experimental
trials. Naive application of three point transport would require
computation over $O(n^3)$ element triples.
Global illumination within nondiffuse environments is ideally suited for
computation under importance and radiance driven refinement: a transport
interaction is of significance only if it lies within paths of directional
reflection of both radiance originating at a light source, and importance
originating at the eye. We have thus derived the adjoint to the radiance
transport formulation, and present preliminary results of application of
this adjoint in the form of an importance driven version of our
implementation. These results show significant reduction in computation,
and indicate that importance and radiance driven hierarchical techniques
possess great potential for efficient evaluation of global illumination
over general reflection.