Published on *Computer Science Department at Princeton University* (http://www.cs.princeton.edu)

Report ID:

TR-434-93

Authors:

Date:

October 1993

Pages:

137

Download Formats:

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.