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

Report ID:

TR-466-94

Authors:

Schroeder, Peter [1]

Date:

October 1994

Pages:

151

Download Formats:

[PDF [2]]

One of the core problems of computer graphics is the computation of the

equilibrium distribution of light in a scene. This distribution is given as

the solution to a Fredholm integral equation of the second kind involving

an integral over all surfaces in the scene. In the general case such

solutions can only be numerically approximated, and are generally costly to

compute, due to the geometric complexity of typical computer graphics

scenes. For this computation both Monte Carlo and finite element techniques

(or hybrid approaches) are typically used.

A simplified version of the illumination problem is known as {em

radiosity}, which assumes that all surfaces are diffuse reflectors. For

this case hierarchical techniques, first introduced by Hanrahan {em et

al./}cite{hanr91}, have recently gained prominence. The hierarchical

approaches lead to an asymptotic improvement when only finite precision is

required. The resulting algorithms have cost proportional to $O(k^2+n)$

versus the usual $O(n^2)$ ($k$ is the number of input surfaces, $n$ the

number of finite elements into which the input surfaces are meshed).

Similarly a hierarchical technique has been introduced for the more general

radiance problem (which allows glossy reflectors) by Aupperle {em et

al./}cite{aupp93a}.

In this dissertation we show the equivalence of these hierarchical

techniques to the use of a Haar wavelet basis in a general Galerkin

framework. By so doing, we come to a deeper understanding of the properties

of the numerical approximations used and are able to extend the hierarchical

techniques to higher orders. In particular, we show the correspondence of

the geometric arguments underlying hierarchical methods to the theory of

Calderon-Zygmund operators and their sparse realization in wavelet bases.

The resulting wavelet algorithms for radiosity and radiance are analyzed

and numerical results achieved with our implementation are reported. We

find that the resulting algorithms achieve smaller and smoother errors at

equivalent work.

**Links**

[1] https://www.cs.princeton.edu/research/techreps/author/340

[2] ftp://ftp.cs.princeton.edu/techreports/1994/466.pdf