Exact Evaluation of Subdivision Surfaces

This work unifies two important shape representations: polygonal meshes and parametric surfaces. Subdivision turns any polygonal mesh into a smooth surface. However, until this work it was believed that a subdivision surface did not admit an exact parametric representation everywhere. In this work we disprove that belief and show that a subdivision surface can be represented by a set of eigenbasis functions everywhere. These functions generalize the usual power basis to regions of  the mesh that have arbitrary connectivity. An alternative way to think about subdivision surfaces is to interpret the initial mesh as a set of control vertices for a parametric surface. The advantage of subdivision surfaces over NURBS or B-splines is of course that the mesh can have any connectivity (topology). Evaluation, therefore allows many useful techniques developed for parametric surfaces to be transferred to subdivision surfaces. Examples, include ray surface intersection, evaluating integrals over the surface (Finite Elements), curve on surface (for trimming), texture mapping, arbitrary tessellation, etc.

The basic observation behind the technique is that subdivision for certain meshes is equivalent to simply shrinking them by a given number called an eigenvalue. The surfaces corresponding to these meshes (called eigenvectors) are the new eigenbasis functions. The reason that they form a basis is that the corresponding eigenvectors span the entire space of all meshes. These eigenbasis functions can be evaluated exactly for Catmull-Clark and Loop subdivision surfaces (and for many other schemes), since they generate B-splines and Box Splines in the regular parts of their meshes.

This is the basis idea. To find out more you can either download my  SIGGRAPH'98 paper or the SIGGRAPH'99  course notes.    Also you might want to view the slides of my talk.

The files with the eigenstructures which are on the course CDROM can be downloaded right here:

Some binary files with the eigenvectors and eigenvalues (see the paper) up to valence 50 are given here for both Catmull-Clark and Loop  subdivision surfaces.

ccdata50.dat     :  eigenstructures for valences up to 50 for Catmull-Clark (Unix binaries)
ccdata50NT.dat   : eigenstructures for valences up to 50 for Catmull-Clark (Windows +linux binaries)
cctest.c             :  C-code that reads in and prints out the eigenstructures

lpdata50.dat     :  eigenstructures for valences up to 50 for Loop (Unix binaries)
lpdata50NT.dat   : eigenstructures for valences up to 50 for Loop (Windows + linux binaries)
lptest.c             :  C-code that reads in and prints out the eigenstructures.

Please report any bugs to jstam@aw.sgi.com. If you are going to use these files then please also acknowledge my company, Alias|wavefront, who allowed me to make these files publicly available.