The main application of subdivision in computer graphics and CAGD is generation of smooth or piecewise smooth surfaces, that is, surfaces with a smooth regular parameterization in a neighborhood of any point. Given an initial mesh, subdivision computes a sequence of refined meshes converging to a limit surface. The refined meshes are obtained by adding new vertices to the mesh and connecting them with old vertices. The positions of new vertices are computed as functions of positions of the old vertices; the positions of old vertices in the refined mesh can be modified.

While the criteria for smoothness of subdivision surfaces on regular grids are relatively well understood, little was known about smoothness of subdivision on arbitrary meshes, despite the fact that initially subdivision surfaces were introduced by Catmull and Clark and Doo and Sabin as extensions of splines to that are able to handle arbitrary initial meshes.

The goal of this work is to build a systematic theory of stationary subdivision surfaces on arbitrary meshes. We find necessary and sufficient conditions for C^k-continuity of subdivision schemes, that generalize and extend most known conditions. These conditions can be used to evaluate smoothness of particular schemes; more importantly, they provide us with a more explicit description of the whole class of C^k-continuous schemes; it is our hope that such description can be used for finding schemes in the class that are optimal in other senses, for example, schemes that produce surfaces with improved fairness.

Our analysis of stationary subdivision around extraordinary vertices builds on the ideas from the work of Warren, Reif and Cavaretta, Dahmen and Miccelli.

Our main results include

- necessary and sufficient conditions for geometric continuity (existence of limit normals);
- necessary and sufficient conditions for C^k-continuity of subdivision schemes at extraordinary vertices under some assumptions;
- a practical sufficient criterion for smoothness of a subdivision scheme around an extraordinary vertex;
- an extension of a result by Reif on the degree estimate of C^2-continuous piecewise polynomial subdivision to the case of C^k-continuity;
- a formalism for description of subdivision schemes on arbitrary meshes in terms of graph neighborhoods.

The necessary and sufficient criteria for also give some clues for construction of C^k subdivision schemes, in particular, schemes on tagged meshes, where non-standard behavior is desired for tagged vertices, edges or faces.

The sufficient conditions does not require knowledge of the explicit formula for the limit surface, which makes it useful for analysis of \ interpolating subdivision schemes, such as the Butterfly scheme.

Complete paper

The paper is temporarily unavailable; I will post an updated version soon.Denis Zorin, ``C^k Continuity of Subdivision Surfaces,'' California Institute of Technology Department of Computer Science Technical Report CS-TR-96-23. Some intuition about behavior of subdivision surfaces an be gained by experimenting with the coefficeints of subdivison schemes as it was done in