What is Multiresolution?

Multiresolution Analysis

Classically the term multiresolution has been intimately connected with the study of wavelets. Wavelets are useful to describe mathematical objects such as functions (or signals) at different levels of resolution. For example, an image can be described at different levels of resolution. Understanding and characterizing the differences between images (or functions) at different levels of resolution is what wavelets are all about (learn more)

Variationally optimal interpolating scaling function and associated wavelet

The classic techniques work well in a regular, somewhat sanitized, setting. They are less useful in the more general settings that engineers and computer scientists encounter in real life examples. Graphics folks recognized a while ago that in principle wavelets are a very powerful ally in addressing many of the computational challenges in graphics. However, the wavelet constructions had to be much more flexible than what the classical literature described. Researchers quickly took advantage of the connection between subdivision and wavelets. In particular, there are a number of arbitrary topology subdivision schemes for surfaces which make for an elegant foundation on which to build multiresolution representations.

Subdivision

Subdivision defines smooth surfaces as the limit of a sequence of successively refined polyhedra. It was originally developed as a generalization of polynomial patch based methods to the arbitrary topology setting and has been studied for about 15 years in the mathematical CAGD literature. In the last few years these techniques have received more interest in the computer graphics literature because of the many attendant benefits of subdivision.

Level 1 mesh of subdivision; each triangle is split into 4

The basic algorithms are exceptionally simple. A given triangle (or quadrilateral) is split through the insertion of new midpoints along the edges (and a center point in the case of quadrilaterals). The new points are computed as weighted averages of nearby points. Because of this simplicity very few assumptions have to be made about the global nature of the objects to be modeled. For example, data structures only need to support operations such as neighbor finding in a graph. Special constraints, e.g., boundary conditions, can be incorporated simply by locally modifying the weights of the subdivision scheme. No global constraint systems are necessary to enforce smoothness. The domain of subdivision is an abstract topological complex. No metric is required, no global (or even local) parameterization, nor is an embedding presupposed. No less, important functionals such as bases for the tangent spaces to the limit surface and values of the limit surface, can be computed exactly.

Adaptively subdivided model generated from original scanner data

Because the entire process is based on mesh refinement, subdivision naturally bridges the gap between polygonal mesh representations and higher level modeling paradigms such as patches. Through this, subdivision provides a basic framework for techniques such as level-of-detail rendering, compression, progressive transmission, adaptive meshing and many other algorithms based on multiresolution. Together with its deep and rich connections to wavelets a powerful paradigm for concise representation and efficient numerical computation emerges.

Resources

This summer a group of researchers will teach a course on subdivision at the annual Siggraph conference. Also be sure to check our publications page as well as some of the demos under the teaching category. An excellent introductory text is the monograph by Joe Warren on Subdivision Methods for Geometric Design.