Subdivision and wavelets

Motivation

Representing curved shape is a fundamental problem in geometric modeling and design. A variety of approaches exist for modeling curved shape. One of the most popular methods is a boundary representation (B-rep) whose surfaces are trimmed NURBS (non-uniform rational B-splines). The use of NURBS patches with a B-rep involves addressing several difficult problems.

Trimming two NURBS patches to agree along a common edge usually involves substantial approximation. Even in the absence of sharp edges, patching is often required. A single NURBS patch is capable of modeling only objects that are topologically equivalent to a plane, a cylinder, or a torus. So, modeling a smooth object with no edges often requires smoothly patching together several distinct trimmed surfaces. Another difficulty with B-reps based on patching is that analysis tools such as finite element analysis require sophisticated mesh generation algorithms.

Subdivision

Subdivision provides a promising alternative to the use of NURBS. Consider a polygon below with dark vertices. Click for the figure. Replicate each vertex of the polygon and then reposition these new vertices 1/4 of the way along the edges incident on that vertex. The new polygon with light vertices has twice as many vertices. Repeating this process yields denser and denser polygons. The limit of this process is a smooth curve. In fact, this curve is the quadratic B-spline defined by the dark vertices.

The operation of replicating and averaging is referred to as subdivision . Subdivision is a geometric transformation that maps polygons into more densely faceted polygons. Surface subdivision methods map polyhedra into polyhedra. Methods due to those such as Doo-Sabin, Catmull-Clark or Loop yield limit surfaces that are smooth.

Hoppe, DeRose, et al. build a variant of Loop's method that can be used to define surfaces with distinct vertices and sharp, curved edges. Each vertex of the initial polyhedron is tagged as lying on a vertex, edge, or face of the limit object. Distinct averaging masks are then used for vertices of each type to produce a new, more densely faceted polyhedron whose vertices are also tagged. The limit of this process is an object with smooth, curved faces and smooth, sharp edges. Click here for an example of an initial polyhedron and a final limit object

The masks for the white edges on the initial object produce sharp creases on the final limit surface. This representation avoids the patching and trimming inherent in the use of NURBS-based B-reps. Compared to existing methods, subdivision surfaces have the following advantages:

Generality: The ability to model surfaces of arbitrary topology with smoothness and sharp features is built-in --- no trimming or patching is necessary.
Simplicity: This approach requires only polyhedral modeling. Analysis programs based on techniques such as finite elements can be applied without recourse to mesh generation.
Efficiency: Subdivision defines a natural hierarchy of spaces. Hierarchical bases for these spaces can be used to improve the efficiency of application algorithms.

If you are interested in more details on subdivision, you can consult a monograph that I have written on subdivision.

Wavelets

Wavelets are the buildings blocks for multi-resolution analysis (MRA), a hierarchical method for representing shape. MRA can be used to improve the efficiency of many algorithms for computing about shape. Although the mathematical underpinnings of MRA are somewhat involved, the resulting algorithms are quite simple. We start with a brief intuitive description of how the method can be applied to decompose the polyhedral object shown in the following figure . Part (a) shows a high resolution polyhedron. Part (b) shows a lower resolution approximation. Part (c) shows the lowest resolution approximation.

The main idea behind MRA is the decomposition of a function, in this case a polyhedron, into a low resolution part and a ``detail'' part. The low resolution part of the polyhedron in (a) is shown in (b). The vertices in (b) are computed as certain weighted averages of the vertices in (a). These weighted averages essentially implement a low pass filter denoted as A. The detail part consists of a collection of fairly abstract coefficients, called wavelet coefficients, that are also computed as weighted averages of the vertices in (a), the weights forming a high-pass filter B. The decomposition process, technically called analysis, can be used to further split (b) into an even lower resolution version and corresponding wavelet coefficients. This cascade of analysis steps is often referred to as a filter bank algorithm.

Subdivision and wavelets are intrinsically linked. Each step of subdivision produces a polyhedron with four times as many faces. Thus, subdivision automatically defines a series of nested spaces, V_0, V_1, V_2, ..., of finer and finer detail. Wavelets spans the complimentary, "detail" spaces, W_0, W_1, W_2, ... More precisely, the spaces V_j and W_j taken together span the space V_{j+1}.

The key to MRA is developing analysis filters that produce a low resolution version of the object (in V_j) that is a good approximation to the original object (in V_{j+1}) with the magnitude of each wavelet coefficient (in W_j) measuring the error introduced by that coefficient. If ``detail'' space W_j is orthogonal to the low resolution space W_j, then the filters have this property. More precisely, the low resolution version is guaranteed to be the best least squares approximation to the original object.

The main benefit of MRA (and wavelets) is that the efficiency of algorithms for computing about shape can be greatly improved. Using the filter bank described above, an algorithm can quickly convert to the level of detail appropriate for a particular application. For example, one could progressively transmit a shape across a slow network link by first transmitting a coarse, low resolution approximation to the shape and then transmitting the wavelets coefficients in order of decreasing magnitude. This approach is the basis for many popular image compression algorithms.

If you are interested in more details on wavelets, please consult the following paper on the subject.