Subdivision Surfaces utilize a mesh of polygonal shapes, or a sequence of meshes, to describe a surface. 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.
Daniel Doo and Malcolm Sabin took the refinement paradigm developed by George Chaikin and, by adapting the refinement techniques for the bi-quadratic uniform B-spline surface were able to develop a new surface definition procedure based upon refinement. This study led to a simple procedure by which a surface could be developed via a polyhedral mesh of points.
The Procedure for the Biquadratic Uniform B-Spline Patch
Given the subdivision masks generated for subdivision of biquadratic uniform B-spline patches
Doo and Sabin observed that the points are simply the average of four particular points taken in a polygon - the vertex for which the new point is being defined, the two edge points (the midpoints of the edges that are adjacent to this vertex in the polygon), and the face point (average of the vertices of the polygon). This can be seen in the following illustration:
Thus the uniform B-spline case is easy, just generate these new points on each face. Each new face generated has four vertices, and the new points form a rectangular grid, from which we can again use this procedure to obtain new points on the faces, etc.
The Procedure for Meshes of Arbitrary Topology
This procedure can be utilized to specify a refinement procedure for surfaces of arbitrary topologies. The rules of the refinement are as follows:
We note the appearance of the ``cutting off the corners'' of the polygonal mesh - from which these class of algorithms derives their name.
The following illustrations show three iterations of a Doo-Sabin bicycle seat. We note that locally these are equivalent to uniform quadratic B-spline surfaces, except at the corner points of the initial control point set (usually called extraordinary points).
We note that the last illustration is shaded poorly as the dark polygons are nonplanar and the rendering algorithm is assuming polygonal objects.
Since the algorithm for refinement of bi-quadratic B-spline patches resolves into a procedure that defines new points on each face in the refinement process, and these new points only depend on the face point, the vertex on a face and two edge midpoints for edges adjacent to the vertex, it is easily extended into an algorithm that works on a mesh with an arbitrary topology.
This Doo-Sabin surface is locally a bi-quadratic B-spline surface, except at a finite number of control points.