Theory of subdivision surfaces

Subdivision algorithms are conceptually quite simple; at the same time answering even the basic questions about the properties of the resulting surfaces is quite challenging. One of such properties is C1 continuity, the mathematical expression of the intuitive idea of smoothness; C1 continuity of common subdivision surfaces known since 1978 was proved only recently.

Significant fraction of our work on the theory of subdivision focuses on smoothness properties of subdivision surfaces; the main achievements include general necessary and sufficient criteria for C1 and higher order continuity as well as practical methods for verification of C1 continuity for general subdivision schemes. Unlike previously used approaches, our approach does not assume that subdivision rules reduce to spline rules in the regular case. Our method was used to verify C1 continuity of a number of existing subdivision schemes ( modified Butterfly, Kobbelt's interpolating quad scheme, 4-8 subdivision, a family of high order primal and dual schemes up to order 9). It was also used to provide an independent verification of earlier proofs of C1 continuity of the well-known Catmull-Clark, Doo-Sabin and Loop schemes.

Our work in progress includes analysis of surfaces with boundaries, more precise characterization of smoothness, in terms of H\"{older} and Sobolev regularity, exploration of approximation power of subdivision surfaces, The latter aspect is particularly important for applications using subdivision-based finite elements.

Smoothness of subdivision on irregular meshes
Denis Zorin
Constructive Approximation, vol. 16, no. 3, 2000, pp. 359-397.
A method for analysis of C1-continuity of subdivision surfaces
Denis Zorin
SIAM Journal of Numerical Analysis, vol. 37, no. 5, 2000, pp. 1677-1708.
Subdivision and multiresolution surfaces
Denis Zorin
Ph.D. Thesis, Caltech, 1998.


Our techniques for analysis of C1 continuity of subdivision surfaces rely on symbolic computation and interval arithmetics. The symbolic computations of eigenvectors and eigenvalues of subdivision matrices were done using Maple V; The Maple worksheets with detailed descriptions of these computations and their PDF versions are available for the following schemes:

Two additional Maple files are requuired: additional utilities (plain text) and convergence estimate computations (Maple worksheet).

The Maple worksheets are used to generate C++ files for computation of control nets of characteristic maps for these subdivision schemes. These files are compiled into interval arithmetic code computing guaranteed bounds for Jacobians of the characteristic maps and verifying injectivity of such maps. This code will be made available at a later time.