On-Line Geometric Modeling Notes
SUBDIVISION SURFACES

Surface generation methods are an important topic in computer graphics and computer-aided geometric design research. Much of the important work to date has concentrated on surfaces based upon closed-form mathematical expressions (Bézier Curves, Spline Methods), but these methods are limited as to the number of surfaces and surface types that can be generated.

A new set of methods is now becoming popular which utilize a mesh of polygonal shapes, or a sequence of meshes, to describe a surface. By doing this, freedom from the closed-form mathematical expression is achieved, and a wide variety of surface types can be expressed. The surfaces are commonly called subdivision surfaces as they are based upon the binary subdivision of the uniform B-spline curve/surface. In general, they are defined by a initial polygonal mesh, along with a subdivision (or refinement) operation which, given a polygonal mesh, will generate a new mesh that has a greater number of polygonal elements, and is hopefully closer'' to some resulting surface. By repetitively applying the subdivision procedure to the initial mesh, we generate a sequence of meshes that (hopefully) converges to a resulting surface.

As it turns out, this is a well known process when the mesh has a rectangular'' structure and the subdivision procedure is an extension of binary subdivision for uniform B-spline surfaces. Therefore, we first present a somewhat extensive study of the uniform B-spline case, and then show how these results can be generalized to treat the case when the mesh is not based on a rectangular structure.

These algorithms are from a class called corner cutting'' algorithms - that is, their action can be described by cutting the corners off of polygonal meshes. To understand the basis of this method, the reader should first review the section on subdivision curves which includes Chaikin's Algorithm - which can be pointed to as the first of these subdivision algorithms. The study of quadratic and cubic B-spline surfaces lead respectively to the two better known surface subdivision schemes, the Doo-Sabin and Catmull-Clark methods. We also outline a method by Charles Loop that is based upon a mesh with a triangular based structure.

Ken Joy
2000-11-28