Graphics Reference
In-Depth Information
Observation (3) means that we can, except for a fixed number of arbitrarily small
regions, express the last subdivision surface as a collection of 3 ¥ 3 rectangular grids.
These 3 ¥ 3 grids can be replaced by a quadratic Bézier surface, so that our subdivi-
sions start looking more and more like quadratic Bézier surfaces. The parameteriza-
tion of the limit surface is C
1
(and has well-defined tangent planes) except at a finite
number of points.
An improved Doo-Sabin algorithm that gives one control over the boundary and
also allows for interpolation is described in [Nasr87]. An even simpler subdivision
construction than the one used in the Doo-Sabin algorithm, called the mid-edge sub-
division, is analyzed in [PetR97]. One disadvantage of the Doo-Sabin algorithm is that,
being based on quadratic B-splines, it shares a problem with those, namely, that the
limit surface may bulge too much to the control points.
The next subdivision algorithm we would like to describe is the Catmull-Clark
algorithm ([CatC78]), which is a vertex insertion algorithm that produces a quadri-
lateral mesh. Given a polygonal surface
S
, we create a new vertex for each of its faces,
edges, and vertices. The new vertex
v
F
for a face
F
of
S
is just its centroid, that is, if
v
1
,
v
2
,..., and
v
k
are the vertices of
F
, then
k
1
Â
v
=
v
.
F
i
k
i
=
1
If
E
is an edge of
S
with vertices
v
and
w
which is adjacent to faces
F
and
G
, then
the new vertex
v
E
for
E
is the centroid of
v
,
w
,
v
F
, and
v
G
, that is,
1
4
(
)
v
=+++
v
wv
v
.
E
F
G
Finally, there are several ways to define the new vertex
v
v
for a vertex
v
of
S
. We
follow the original definition given in [CatC78]. Let
F
av
denote the average of all the
v
F
, where
F
is face of
S
to which
v
belongs. Let
E
av
denote the average of all the mid-
points of all the edges
E
of
S
which contain
v
and assume that there are n such edges.
Then
1
2
n
-
3
v
=
FE
+
+
v
.
v
av
av
n
n
n
The subdivision
S
¢ of
S
is now defined as follows: We create an edge from each new
v
F
to all the new
v
E
, where
E
is an edge of
F
, and also an edge from each new
v
v
to
each
v
E
, where
v
belongs to
E
. See Figure 12.30. In that figure the vertices
v
F
are
marked by a cross, the vertices
v
E
are marked by hollow circles, and the vertices
v
v
are marked by hollow squares. After each subdivision in this algorithm all faces are
four-sided and most vertices belong to four edges, but there may be a constant number
of vertices that are incident to n edges, n π 4. In the limit one gets a surface that is
essentially built from cubic B-spline surfaces and has a parameterization that is C
2
except at a finite number of points. Although tangent planes are defined everywhere,
the singular points may exhibit curvature problems in that one may either get
