Wavelet Methods for Computer Graphics (Thesis)

Abstract:

This thesis discusses how a wavelet basis can be used in the context of
two computer graphics applications, realistic rendering and geometric
modeling, to produced more efficient and flexible algorithms.
The goal of realistic rendering is to simulate the interreflection of
light in some geometric environment in order to produce realistic
images. Radiosity is a commonly used solution method for this problem.
Recently Hanrahan et al. have introduced a hierarchical method that can solve
radiosity problems in $O(n)$ time instead of $O(n^2)$. This thesis
explores how the hierarchical radiosity algorithm can be formally understood
from the context of wavelet theory. When the radiosity problem is
expressed with respect to a wavelet basis, the resulting linear system
is sparse, with only $O(n)$ significant terms. By casting the hierarchical
method in this framework, a variety of wavelet basis functions can be
used, resulting in more efficient radiosity methods.
This thesis also discusses how wavelets can be used in the context of
geometric modeling. Geometric modeling is the study of how geometric
shapes can be represented and manipulated by a designer. This thesis
explores the use of wavelets to represent parametric curves and
surfaces within the context of geometric modeling interfaces.
One intuitive modeling interface commonly used in geometric modeling
allows the user to directly manipulate curves and surfaces. This
manipulation defines some set of constraints that the curve or surface
must satisfy (such as interpolation and tangent constraints). Direct
manipulation, however, usually leads to an underconstrained problem
since there are, in general, many possible surfaces meeting some set
of constraints. Therefore an optimization problem must be solved.
This thesis discusses how geometric modeling optimization problems can
be solved more efficiently by using a wavelet basis. Because the
wavelet basis is hierarchical, iterative optimization methods converge
rapidly. And because the wavelet coefficients indicate the degree of
detail in the solution, they can be used to determine the number of
basis functions needed to express the variational minimum, thus
avoiding unnecessary computation. An implementation is discussed and
experimental results are reported.