Graphics Reference
In-Depth Information
Figure 12.29(d) shows the result of applying the algorithm to the surface
S
whose
vertices are the solid circles and the edges are drawn as bold lines. The vertices
and edges of the subdivided surface
S
¢ are the hollow circles and thin lines, respec-
tively.
To finish the Doo-Sabin algorithm, all that is left to do is to explain how the new
vertices are defined in each face of the original surface
S
. Various schemes exist. Let
v
i
be the new vertex created for vertex
w
i
in an n-sided face
F
of
S
. The original idea
was to let
v
i
be the midpoint of the segment from
w
i
to the centroid of
F
. Another
expresses
v
i
in the form
n
Â
a
1
v
=
w
i
ij
j
j
=
and sets
n
+
5
a
=
for
i
=
j
,
ij
4
n
(
)
2
p
ij
n
-
32
+
cos
a
=
for
i
π
j
.
ij
4
n
The a
ij
are not as strange as they may look at first glance. They are closely related to
the nth roots of unity. In fact, they are barycentric coordinates because
n
Â
a
ij
=
1.
j
=
1
This follows easily from the fact that the sum of the real parts of the nth roots of unity
is 0, namely,
n
2
pk
n
Ê
Ë
ˆ
¯
Â
cos
=
0
.
k
=
1
The following observations can be made about the subdivision surfaces:
(1) After the first subdivision all vertices will be incident to four edges.
(2) Each n-sided face gives rise to an n-sided face in the subdivision but the
number of n-sided faces, n π 4, stays constant. As one keeps subdividing, such
faces get smaller and smaller and converge to the centroid of the original face.
(3) We will get more and more four-sided faces and our subdivision will look more
and more like a rectangular grid.
(4) The surfaces satisfy the convex hull and local control property. They are also
affinely invariant.
