# projects

## 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 C^{1}
continuity, the mathematical expression of the intuitive idea of
smoothness; C^{1} 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
C^{1} and higher order continuity as well as practical methods for
verification of C^{1} 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
C^{1} 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
C^{1} 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 C
^{1}-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.*

### Software

Our techniques for analysis of C^{1} 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:

- Butterfly and modified Butterfly Maple, PDF.
- Kobbelt's interpolating quad Maple, PDF.
- Loop and variants Maple, PDF.
- Catmull-Clark Maple, PDF.
- Doo-Sabin Maple, PDF.
- 4-8 subdivision Maple, PDF.

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.