i
i
i
i
i
i
i
i
13.5. Subdivision Surfaces 615
Figure 13.37. A worm subdivided three times with Loop’s subdivision scheme.
mesh. See Figure 13.37 for an example of a mesh subdivided with Loop’s
scheme. A variant of Equation 13.50, which avoids trigonometric functions,
is given by Warren and Weimer [1328]:
β(n)=
3
n(n +2)
. (13.51)
For regular valences, this gives a C
2
surface, and C
1
elsewhere. The re-
sulting surface is hard to distinguish from a regular Loop surface. For a
mesh that is not closed, we cannot use the presented subdivision rules. In-
stead, special rules have to be used for such boundaries. For Loop’s scheme,
the reflection rules of Equation 13.48 can be used. This is also treated in
Section 13.5.5.
The surface after infinitely many subdivision steps is called the limit
surface. Limit surface points and limit tangents can be computed using
closed form expressions. The limit position of a vertex is computed [559,
1415] using the formula on the first row in Equation 13.49, by replacing
β(n)with
γ(n)=
1
n +
3
8β(n)
. (13.52)
Two limit tangents for a vertex p
k
can be computed by weighting the
immediate neighboring vertices, called the 1-ring or 1-neighborhood,as
shown below [559, 787]:
t
u
=
n−1
i=0
cos(2πi/n)p
k
i
, t
v
=
n−1
i=0
sin(2πi/n)p
k
i
. (13.53)
i
i
i
i
i
i
i
i
616 13. Curves and Curved Surfaces
Figure 13.38. A tetrahedron is subdivided five times with Loop’s, the
√
3, and the
modified butterfly (MB) scheme. Loop’s and the
√
3-scheme are both approximating,
while MB is interpolating.
The normal is then n = t
u
× t
v
. Note that this often is less expen-
sive [1415] than the methods described in Section 12.3, which need to com-
pute the normals of the neighboring triangles. More importantly, this gives
the exact normal at the point.
A major advantage of approximating subdivision schemes is that the
resulting surface tends to get very fair. Fairness is, loosely speaking, re-
lated to how smoothly a curve or surface bends [903]. A higher degree of
fairness implies a smoother curve or surface. Another advantage is that ap-
proximating schemes converge faster than interpolating schemes. However,
this means that the shapes often shrink. This is most notable for small,
convex meshes, such as the tetrahedron shown in Figure 13.38. One way
to decrease this effect is to use more vertices in the control mesh. i.e., care
must be taken while modeling the control mesh. Maillot and Stam present
a framework for combining subdivision schemes so that the shrinking can
be controlled [809]. A characteristic that can be used to great advantage
at times is that a Loop surface is contained inside the convex hull of the
original control points [1413].
The Loop subdivision scheme generates a generalized three-directional
quartic box spline.
6
So, for a mesh consisting only of regular vertices, we
could actually describe the surface as a type of spline surface. However,
this description is not possible for irregular settings. Being able to generate
smooth surfaces from any mesh of vertices is one of the great strengths
of subdivision schemes. See also Sections 13.5.5 and 13.5.6 for different
extensions to subdivision surfaces that use Loop’s scheme.
13.5.2 Modified Butterfly Subdivision
Here we will present the subdivision scheme by Zorin et al. [1411, 1413],
which is a modification of the butterfly scheme by Dyn et al. [291], and
6
These spline surfaces are out of the scope of this book. Consult Warren’s book [1328],
the SIGGRAPH course [1415], or Loop’s thesis [787].
i
i
i
i
i
i
i
i
13.5. Subdivision Surfaces 617
Figure 13.39. To the left is a simple three-dimensional star mesh. The middle image
shows the resulting surface using Loop’s subdivision scheme, which is approximating.
The right image shows the result using the modified butterfly scheme, which is inter-
polating. An advantage of using interpolating schemes is that they often resemble the
control mesh more than approximating schemes do. However, for detailed meshes the
difference is not as distinct as shown here.
therefore often referred to as the modified butterfly (MB) scheme. This
scheme is nonuniform, both because it uses different rules at the bound-
aries, and because different rules are used depending on the valence of the
vertices. The main difference from Loop subdivision, however, is that it is
interpolating, rather than approximating. An interpolating scheme means
that once a vertex exists in the mesh, its location cannot change. There-
fore, this scheme never modifies, but only generates new vertices for the
edges. See Figure 13.39 for an example between interpolating and approxi-
mating schemes. The connectivity is the same as for Loop’s scheme, shown
in Figure 13.34.
The MB scheme uses four different subdivision rules for creating new
vertices between two existing vertices. These are all described below, and
the corresponding masks are shown in Figure 13.40.
1. Regular setting. Assume that we want to generate a new vertex between
two existing vertices, v and w, that each has valence 6. These vertices
are called regular or ordinary, and we call the situation a regular setting.
The mask for this situation is shown to the left in Figure 13.40.
2. Semiregular setting. A semiregular setting occurs when one vertex is
regular (n = 6), and another is irregular (n = 6), also called extraor-
dinary, and we want to generate a new vertex between these vertices.
The following formula computes the new vertex, where n is the valence
of the irregular vertex:
n =3: w
0
=5/12,w
1
= −1/12,w
2
= −1/12,
n =4: w
0
=3/8,w
1
=0,w
2
= −1/8,w
3
=0,
n ≥ 5: w
j
=
0.25 + cos(2πj/n)+0.5cos(4πj/n)
n
.
(13.54)
i
i
i
i
i
i
i
i
618 13. Curves and Curved Surfaces
Figure 13.40. The mask to the left is the “butterfly” mask, which is used when generating
a new vertex between two regular vertices (those with weights 1/2). The mask to the
right shows the weights when one vertex is irregular (the one with weight 1−
w
i
), and
one vertex is regular (with weight w
0
). Note that black circles indicate which vertex is
generated. (Illustration after Zorin et al. [1415].)
Note that we used only the immediate neighborhood of the irregular
vertex to compute the new vertex, as shown in the mask in Figure 13.40.
3. Irregular setting. When an edge connects two vertices, where both ver-
tices are irregular (n = 6), we temporarily compute a new vertex for
each of these two vertices using the formula for the semiregular set-
ting (2). The average of these two vertices is used as the new vertex.
This can happen at only the first subdivision step, because after that
there will be only regular and semiregular settings in the mesh. There-
fore the continuity of this choice does not affect the limit surface. Zorin
et al. [1411] note that this rule generates shapes with better fairness.
4. Boundaries. At boundaries, where an edge in the triangle mesh has only
one triangle connected to it, the interpolating scheme [290] with w =
1/16, described in Section 13.4 (see Figure 13.30 and Equation 13.47)
is used. More types of boundary cases exist—consult the SIGGRAPH
course for more about this [1415]. Implementation details are discussed
by Sharp [1160]. Since this scheme is interpolating, limit positions of
the vertices are the vertices themselves. Limit tangents are more com-
plex to compute. For extraordinary vertices (n = 6), the tangents can
be calculated using Equation 13.53, that is, the same formulae as for
Loop [1413]. For ordinary vertices (n = 6), the 2-ring (also called the
2-neighborhood) is used. The 1-ring and the 2-ring of an ordinary vertex,
p, is shown in Figure 13.41. The tangents vectors, t
u
and t
v
,arethen
computed as
t
u
= u · r,
t
v
= v · r,
(13.55)
where r is a vector of the difference vectors p
i
− p of the entire 2-ring,
i
i
i
i
i
i
i
i
13.5. Subdivision Surfaces 619
Figure 13.41. An ordinary vertex, p,withits1-ring(p
0
,...,p
5
), and its 2-ring
(p
6
,...,p
17
).
and u and v are vectors of scalars:
r =(p
0
− p, p
1
− p, p
2
− p,...,p
16
− p, p
17
− p),
u =(16, −8, −8, 16, −8, −8, −
8
√
3
,
4
√
3
,
4
√
3
, −
8
√
3
,
4
√
3
,
4
√
3
,
1, −
1
2
, −
1
2
, 1, −
1
2
, −
1
2
),
v =(0, 8, −8, 0, 8, −8, 0, −
4
√
3
,
4
√
3
, 0, −
4
√
3
,
4
√
3
,
0,
1
2
, −
1
2
, 0,
1
2
, −
1
2
).
(13.56)
This means that, for example, t
u
is computed as
t
u
= 16(p
0
− p) − 8(p
1
− p) −···−0.5(p
17
− p). (13.57)
After computing both t
u
and t
v
, the normal is n = t
u
× t
v
.
When an interpolating scheme is desired, the MB scheme is a good
choice. An interpolating scheme will generate a surface that is more like the
control mesh. This is most notable when using meshes with few triangles.
For larger meshes, the differences disappear. However, the interpolating
characteristics come at the cost that the scheme may generate weird shapes
with “unnatural” undulations, and thus, less fairness. This is common
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.