Graphics Reference
In-Depth Information
Bézier curve), but not that they join up smoothly. For a smooth join, without a
crease along the joining curve, further conditions on the adjacent two columns of
control points are needed.
Arranging a gridlike “quilt” of patches requires that a substantial collection of
constraints be met; the web material for this chapter describes some of these. But
when we try to make rectangular patches glue together in a pattern that has them
meet three at a vertex, as in Figure 23.2, the constraints become overwhelming.
There are several solutions: We can deal with the overwhelming constraints and
continue to use rectangular patches, or we can shift to something like triangular
patches, where gluing together is a little easier, or we can, as we did with curves,
move to subdivision as a way to create shapes. We'll now briefly discuss this third
approach.
Figure
23.2:
A
spherical
blob
made
from
six
“rectangular”
patches
that
meet
three
at
a
vertex.
Subdivision surfaces don't start with individual patches to be joined: They start
from a polygonal mesh, which is repeatedly modified to approach a usually
smooth limit surface. This simplifies matters a good deal.
In the Catmull-Clark subdivision scheme [CC98, HKD93], we start with a
mesh, typically in
R
3
(although the process works in any dimension). The ver-
tices of each face need not actually be coplanar, although it's easiest to visualize
the subdivision process if they're nearly coplanar, so we'll start with an example
where this is true (see Figure 23.3). The faces of the initial mesh may be triangles,
quads, pentagons, etc., but after one level of subdivision all faces will be quads,
so we've drawn an example where they are all quads.
e
2
e
3
e
1
v
e
4
e
5
Figure 23.3: A mesh where one
vertex
v
has n adjacent vertices
e
1
,
e
2
, ...
e
n
, at the ends of the
edges, leaving
v
.
Just as with subdivision curves, we'll describe subdivision surfaces in terms of
a
neighborhood
of a vertex
v
, that is, a set of vertices near
v
in the graph structure
of the mesh.
The first step of subdivision is to compute the centroid
f
i
(the average of the
vertices of the
i
th face). (We'll follow the convention that primes denote points
of the subdivided mesh, and unprimed symbols denote points of the mesh before
subdivision.)
We next compute the edge points
e
i
by the formula
f
2
e
i
=
v
+
e
i
+
f
i
−
1
+
f
i
+
1
4
.
(23.6)
e
2
e
3
f
1
All subscripts are taken modulo
n
.
Finally, we compute a new location for the vertex
v
:
f
'
1
e
1
v
e
'
1
e
4
n
2
i
n
2
i
−
v
=
n
2
v
+
1
e
i
+
1
f
i
.
(23.7)
n
e
5
Figure 23.4: The new vertex
is connected to each new edge
point; the new edge points are
connected to the face points for
adjacent faces.
These new locations are connected as shown in Figure 23.4.
After subdivision, there are approximately four times as many faces as before
subdivision. After just a few levels of subdivision, we'll have a great many
faces.
