On-Line Geometric Modeling Notes
DOO-SABIN SURFACES

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:

• For each vertex of each face of the object, generate a new point as average of the vertex, the two edge points and the face point of the face.

• For each face, connect the new points that have been generated for each vertex of the face.

• For each vertex, connect the new points that have been generated for the faces that are adjacent to this vertex.

• For each edge, connect the new points that have been generated for the faces that are adjacent to this edge.
The polygons generated through this refinement step become the set of polygons for the next step.

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 after the first subdivision, all vertices have valence four - which is a characteristic of the Doo-Sabin method. Note the triangular facets that arise in the corners. This develops because the original corner vertices have valence three (i.e. three edges are adjacent to the point). These triangular facets continue throughout the algorithm and converge to the 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.

Summary

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.

## Bibliography

1
DOO, D.
A subdivision algorithm for smoothing down irregularly shaped polyhedrons.
In Proced. Int'l Conf. Ineractive Techniques in Computer Aided Design (1978), pp. 157-165.
Bologna, Italy, IEEE Computer Soc.

2
DOO, D., AND SABIN, M.
Behaviour of recursive division surfaces near extraordinary points.
Computer-Aided Design 10 (Sept. 1978), 356-360.

Ken Joy
2000-11-28