Catmull-Clark subdivision is a refinement algorithm for polygonal surface meshes that generalizes uniform cubic B-spline refinement to meshes with nonrectangular connectivity (Catmull and Clark 1978). Its repeated application is used to define a subdivision surface. The interior rules can be stated for a closed polygonal surface mesh whose cell incidence forms a two-dimensional manifold without boundary, with at least three incident edges at every vertex. The positions of the vertices lie in three-dimensional Euclidean space.
For a face with 
vertices 
, ..., 
, introduce the face point
 |
(1)
|
Thus 
is the arithmetic mean of the vertex
positions. For an edge with endpoints 
and 
and the two adjacent face points 
and 
, introduce the edge point
 |
(2)
|
Finally, replace each old vertex 
of valence 
by
 |
(3)
|
where 
is the arithmetic mean of its 
incident face points and 
is the arithmetic mean
of the midpoints of its 
incident old edges. All these
positions are computed from the same old mesh (Catmull and
Clark 1978, DeRose et al. 1998).
Each old face is split into quadrilaterals. For each corner of the old face, one new quadrilateral
joins the replacement vertex, the edge point on the following
edge, the face point, and the edge point on the preceding
edge, in this cyclic order. Consequently every face
is a quadrilateral after one refinement. A face
point introduced at an old 
-sided face has valence 
,
so it need not have valence four in this first refinement.
On a regular quadrilateral grid, where each vertex has valence four, these rules are the uniform tensor-product cubic B-spline refinement rules (Catmull and Clark 1978). Vertices of other valences require separate analysis of the limit. The formulas alone do not assert that every control mesh gives a regular smooth surface.
For the stated valences, each new point is a convex combination of old vertex positions. The weights are nonnegative and have sum one, so every refined mesh lies in the old mesh's convex hull. The rules also commute with affine transformations, because each weighted average has total weight one. These properties do not by themselves prove convergence of the refinement process.
