The Wavelet IDR Center Research Subteam
Multiscale Applications in Computer Graphics
P. Schröder
Subteam Leader |
I. Daubechies
|
M. Orchard
|
[ Top | Vision | Technology | Recent Work | Problems ]
Computer graphics is a broad domain touching many areas of our lives through computers everywhere. The images the user sees are merely the externally visible signs of a rich world of underlying mathematical representations of objects and operators. In a fundamental sense, computer graphics is about building models of the real world and manipulating them efficiently for broad access by many different people. For example, content based image retrieval attempts to extract meaning from pixels; image compression delivers rich multi media content to inner city schools over low bandwidth, low cost channels; animation of creatures delights and entertains millions; simulation based design promises to revolutionize manufacturing and commerce. As dataset sizes grow and the insatiable appetite for ever higher fidelity shows no signs of abating, scalable representations and algorithms are of utmost importance. This includes all stages of acquisition, manipulation, editing, simulation, transmission, and display, and pervades all applications of graphics.
[ Top | Vision | Technology | Recent Work | Problems ]
Multiresolution representations based on wavelets have already shown great promise as powerful tools in computer graphics research [S96a] and are now rapidly moving into computer graphics practice [SS96]. A particular challenge to computational harmonic analysis presented by these applications is the sheer size of geometry to be manipulated. Classical methods are rarely applicable as the geometry is typically of arbitrary topology and its connectivity highly irregular. Additionally, researchers have found that redundent representations often offer better asymptotics or are much more amenable to manipulation [ZSS97]. Most current approaches either attempt to "warp" classical constructions (with mixed success) or are based on semi-regular subdivision approaches [ZSS97], [SS95], [LSSCD97]. First steps have been taking into completely irregular settings [DGS98], but we are only at the beginning to build tools in this setting.One area in particular the calls out for such tools is the acquisition, processing, modeling, and transmission of large scale, complex geometry. Today, range scanners are available to acquire samples of the geometry of real world objects at high rates and at times high accuracy. The application domains are very broad and include education (e.g., acquiring models of museum sculptures for access on the WWW); entertainment (e.g., special effects); reverse engineering (e.g., building CAD models for object which may not even have documented drawings); medical diagnostics (e.g., using volumetric imaging techniques for non-invasive examination); scientific computing (e.g., running solid mechanics simulations using real world objects as boundary conditions); and commerce (e.g., industrial parts databases for access over the WWW).
[ Top | Vision | Technology | Recent Work | Problems ]
Some recent papers can be found at the Caltech Multi-Res Modeling Group home page as well as at web pages of Ingrid Daubechies and Michael Orchard.
[ Top | Vision | Technology | Recent Work | Problems ]
There are many interesting problems in computer graphics which can benefit from multiresolution ideas and algorithms. We list here a few such areas, which are by no means meant to be exclusive. Some of these arise in the processing of data coming from 3D range scanners. The main challenge there is that the data is not neatly arranged on a regular and "lives" on arbitrary, piecewise smooth two-manifolds (possibly with boundaries). Some applications are:
- Denoising of range data: Some simple noise models exist for the acquisition process of structured light range scanners, for example. Since the output is a set of 3D points whose noise is a function of 3D space and the underlying geometry itself, straightforward application of image denoising methodologies is not applicable. How can such data be denoised while respecting the intrinsic geometry and important features of the underlying real world object?
- Numerical solution of PDEs: Once a model is built many engineering applications call for the solution of PDEs over the surface of the model. Without multiresolution decompositions of highly irregular geometry the asymptotics of solving elliptic PDEs, for example, are overwhelming. How can we build smooth constructions with the appropriate approximation order over irregular triangulations of arbitrary topology, piecewise smooth surfaces?
- Compression: Once we can acquire and manipulate large scale geometry, compressing it for efficient storage and transmission will be tremendously important. It is intuitively clear that multiresolution methods offer great promise for efficiently encoding arbitrary connectivity meshes. The details are not understood at all at this point. For example, simple quantization of vertex positions quickly leads to topological catastrophies such as inverted or zero area triangles. How can we build multiresolution compression and encoding schemes in this setting?