Wavelet Methods for Computer Graphics (Thesis)
Report ID: TR-473-94Author: Gortler, Steven J.
Date: 1994-12-00
Pages: 183
Download Formats: |PDF| |Postscript|
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.