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 |
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.