Interpolating Subdivision for Meshes with Arbitrary Topology


Abstract

Subdivision is a powerful paradigm for the generation of surfaces of arbitrary topology. Given an initial triangular mesh the goal is to produce a smooth and visually pleasing surface whose shape is controlled by the initial mesh. Of particular interest are interpolating schemes since they match the original data exactly, and are crucial for fast multiresolution and wavelet techniques. Dyn, Gregory, and Levin introduced the Butterfly scheme, which yields C^1 surfaces in the topologically regular setting. Unfortunately it exhibits undesirable artifacts in the case of an irregular topology. We examine these failures and derive an improved scheme, which retains the simplicity of the Butterfly scheme, is interpolating, and results in smoother surfaces.


Left: A tetrahedron is subdivided using the original Butterfly scheme
Right: A tetrahedron is subdivided using our modified Butterfly scheme.

Summary

Modeling the geometry of surfaces of arbitrary topology is an important area of research in computer graphics and approximation theory. A powerful paradigm for the construction of such surfaces is subdivision. Beginning with an input mesh a sequence of meshes is defined whereby new vertices are inserted as, preferably, simple local affine combinations of neighboring vertices. An attractive feature of these schemes is that they are local, i.e., no global system of equations needs to be solved. For example, classical spline constructions fit into this category since the resulting surface can be evaluated with the de Casteljau algorithm. These schemes are generally not interpolating, although modifications are possible to recover interpolating schemes (see below). Another class of schemes is based on interpolating subdivision. Perhaps the most common of these is piecewise linear interpolation. Unfortunately this is not smooth enough for many applications. A scheme that achieves $C^1$ continuity, at least in the topologically regular setting, was pioneered by Dyn, Gregory, and Levin~ and has been applied to the construction of smooth surfaces.

The mathematical analysis of the surfaces resulting from subdivision is not always straightforward. However, the simplicity of the algorithms and associated data structures makes them attractive for large datasets and interactive applications where speed is of the essence.

Recently interest in interpolating subdivision has increased since it allows fast multiresolution and wavelet decompositions of complex geometry, as it was shown by Lounsbery and others. Furthermore, the ability to build adaptive subdivisions relies on the interpolating nature of the subdivision rule. Multiresolution decomposition algorithms are of importance for compression, progressive display and transmission, multiresolution editing, and for multigrid/wavelet based numerical methods.

While the Butterfly scheme of Dyn, Gregory and Levin can be used to generate smooth surfaces over triangular meshes in which every vertex is of valence 6, it exhibits degeneracies when applied in a topologically irregular setting: smoothness can be lost at vertices of valence not equal to 6. The interpolation of a tetrahedron shows an example of such a failure for a vertex of valence 3. The left shows the control mesh, in the middle the resulting mesh after 3 levels of applying the Butterfly scheme, and on the right the result achieved with our modified scheme, which does not exhibit the cusp-like loss of smoothness.

The main result of our work is a simple modification of the Butterfly scheme around vertices of valence not equal to 6. It combats the cusp like artifacts exhibited by the unmodified scheme in those circumstances. We use eigen analysis and Fourier transform techniques to synthesize new interpolating subdivision schemes.

Pipe joint. Note the difference between Butterfly and Modified Butterfly.
initial mesh Butterfly subdivision Modified Butterfly subdivision
Left: Mannequin head. Right: Torso.
initial mesh Modified Butterfly subdivision
initial mesh Modified Butterfly subdivision
For more details see

Denis Zorin, Peter Schröder and Wim Sweldens, ``Interpolating subdivision for meshes with arbitrary topology,'' in Proceedings of SIGGRAPH 1996, ACM SIGGRAPH, 1996, pp. 189-192.

Compressed PostScript (2.8 MB), Compressed PostScript without images (25 KB)

The technical report CS-TR-96-06 has a few details that are not in the paper.