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.

For a pdf version of these notes look here.

- What is a Subdivision/Refinement Process?
- Subdivision methods for biquadratic uniform B-spline surfaces
- Doo-Sabin Surfaces
- Subdivision methods for bicubic uniform B-spline surfaces
- Catmull-Clark Surfaces
- Loop Surfaces

2000-11-28