i
i
i
i
i
i
i
i
620 13. Curves and Curved Surfaces
Figure 13.42. The cube on the left is subdivided using Loop’s scheme (middle), and the
modified butterfly scheme (right). Each face on the cube consists of two triangles. Note
the “unnatural” undulations on the right surface. This is because it is much harder to
interpolate a given set of vertices.
for all interpolating schemes. See Figure 13.42 for a nasty example.
Another disadvantage is that the masks are bigger than those used for
Loop’s scheme and the
√
3-scheme presented in Section 13.5.3, and thus it
is more expensive to evaluate.
Despite these disadvantages, interpolating schemes such as MB can be
well-suited for real-time rendering work. Meshes for real-time work are
normally not finely tessellated, so an interpolated surface is usually more
intuitive, as it more closely matches the location of the control mesh. The
tradeoff is that fairness problems can occur, but in many cases, minor ad-
justments to the underlying mesh can smooth out rippling [1159]. The
MB scheme is C
1
-continuous all over the surface, even at irregular ver-
tices [1413]. See Figure 13.38 on page 616, and Figure 13.43 for two exam-
ples. More about this scheme can be found in Zorin’s Ph.D. thesis [1413]
and in Sharp’s articles [1159, 1160].
Figure 13.43. A worm is subdivided three times with the modified butterfly scheme.
Notice that the vertices are interpolated at each subdivision step.
i
i
i
i
i
i
i
i
13.5. Subdivision Surfaces 621
Figure 13.44. Illustration of the
√
3-subdivision scheme. A 1-to-3 split is performed
instead of a 1-to-4 split as for Loop’s and the modified butterfly schemes. First, a
new vertex is generated at the center of each triangle. Then, this vertex is connected
to the triangle’s three vertices. Finally, the old edges are flipped. (Illustration after
Kobbelt [679].)
13.5.3
√
3-Subdivision
Both Loop’s and the MB schemes split each triangle into four new ones,
and so create triangles at a rate of 4
n
m,wherem is the number of triangles
in the control mesh, and n is the number of subdivision steps. A feature of
Kobbelt’s
√
3-scheme [679] is that it creates only three new triangles per
subdivision step.
7
The trick is to create a new vertex (here called mid-
vertex ) in the middle of each triangle, instead of one new vertex per edge.
This is shown in Figure 13.44. To get more uniformly shaped triangles,
each old edge is flipped so that it connects two neighboring midvertices.
In the subsequent subdivision step (and in every second subdivision step
thereafter), the shapes of the triangles more resemble the initial triangle
configuration due to this edge flip.
The subdivision rules are shown in Equation 13.58, where p
m
denotes
the midvertex, computed as the average of the triangle vertices: p
a
, p
b
,
and p
c
. Each of the old vertices, p
k
, are updated using the formula in the
second line, where p
k
i
(i =0...n− 1) denotes the immediate neighbors
of p
k
,andn is the valence of p
k
. The subdivision step is denoted by k
as before:
p
k+1
m
=(p
k
a
+ p
k
b
+ p
k
c
)/3,
p
k+1
=(1 − nβ)p
k
+ β
n−1
i=0
p
k
i
.
(13.58)
Again, β is a function of the valence n, and the following choice of β(n)
generates a surface that is C
2
continuous everywhere except at irregular
7
The name stems from the fact that while Loop’s and the MB schemes divide each
edge into two new edges per subdivision step, Kobbelt’s scheme creates three new edges
per two subdivision steps. Thus the name
√
3-subdivision.
i
i
i
i
i
i
i
i
622 13. Curves and Curved Surfaces
Figure 13.45. The masks for the
√
3-subdivision scheme. As can be seen, the face mask
gives minimal support, since it uses only the three vertices of the triangle. The vertex
mask uses all the vertices in the ring, called the 1-ring, around the vertex.
vertices (n = 6), where the continuity is at least C
1
[679]:
β(n)=
4 − 2cos(2π/n)
9n
(13.59)
The masks, which are of minimum size, for the
√
3-scheme are shown
in Figure 13.45.
The major advantage of this scheme is that it supports adaptive subdi-
vision in a simpler way, since no extra triangles are needed to avoid cracks.
See Kobbelt’s paper [679] for details. Some other advantages of this scheme
are smaller masks, and slower triangle growth rate than Loop’s and the MB
scheme. The continuity of this scheme is the same as Loop’s. Disadvan-
tages include that the edge flip introduces a little complexity, and that the
first subdivision step sometimes generates nonintuitive shapes due to the
flip. In Figure 13.46, a worm is subdivided with the
√
3-scheme, and in
Figure 13.38 on page 616, a tetrahedron is subdivided.
Figure 13.46. A worm is subdivided three times with the
√
3-subdivision scheme.
i
i
i
i
i
i
i
i
13.5. Subdivision Surfaces 623
Figure 13.47. The basic idea of Catmull-Clark subdivision. Each polygon generates a
new point, and each edge generates a new point. These are then connected as shown to
the right. Weighting of the original points is not shown here.
13.5.4 Catmull-Clark Subdivision
The two most famous subdivision schemes that can handle polygonal
meshes (rather than just triangles) are Catmull-Clark [163] and Doo-Sabin
[274].
8
Here, we will only briefly present the former. Catmull-Clark sur-
faces have been used in Pixar’s short film Geri’s Game [250] and in Toy
Story 2, and in all subsequent feature films from Pixar. This subdivision
scheme is also commonly used for making models for games, and is probably
the most popular one. As pointed out by DeRose et al. [250], Catmull-Clark
surfaces tend to generate more symmetrical surfaces. For example, an ob-
long box results in a symmetrical ellipsoid-like surface, which agrees with
intuition.
The basic idea for Catmull-Clark surfaces is shown in Figure 13.47, and
an actual example of Catmull-Clark subdivision is shown in Figure 13.32
on page 611. As can be seen, this scheme only generates faces with four
vertices. In fact, after the first subdivision step, only vertices of valence 4
are generated, thus such vertices are called ordinary or regular (compared
to valence 6 for triangular schemes).
Following the notation from Halstead et al. [494] (see Figure 13.48),
let us focus on a vertex v
k
with n surrounding edge points e
k
i
,where
i =0...n− 1. Now, for each face, a new face point f
k+1
is computed as
the face centroid, i.e., the mean of the points of the face. Given this, the
subdivision rules are [163, 494, 1415]
v
k+1
=
n − 2
n
v
k
+
1
n
2
n−1
j=0
e
k
j
+
1
n
2
n−1
j=0
f
k+1
j
,
e
k+1
j
=
v
k
+ e
k
j
+ f
k+1
j−1
+ f
k+1
j
4
.
(13.60)
8
Incidentally, both were presented in the same issue of the same journal.
i
i
i
i
i
i
i
i
624 13. Curves and Curved Surfaces
v
0
e
0
0
e
0
1
e
0
2
e
0
n-1
v
1
e
1
0
e
1
1
f
1
0
f
1
1
e
1
2
f
0
n-1
Figure 13.48. Before subdivision, we have the blue vertices and corresponding edges and
faces. After one step of Catmull-Clark subdivision, we obtain the red vertices, and all
new faces are quadrilaterals. (Illustration after Halstead et al. [494].)
As can be seen, new edge points are computed by the average of the
considered vertex, the edge point, and the two newly created face points
that have the edge as a neighbor. On the other hand, the vertex is computed
as weighting of the considered vertex, the average of the edge points, and
the average of the newly created face points.
The Catmull-Clark surface describes a generalized bicubic B-spline sur-
face. So, for a mesh consisting only of regular vertices we could actually
describe the surface as a B-spline surface.
9
However, this is not possible
for irregular settings, and being able to do this using subdivision surfaces
is one of the scheme’s strengths. Limit positions and tangents are also pos-
sible to compute [494]. See Section 13.6.5 for an efficient technique on how
to render Catmull-Clark subdivision surfaces on graphics hardware with
tessellation shaders.
13.5.5 Piecewise Smooth Subdivision
In a sense, curved surfaces may be considered boring because they lack
detail. Two ways to improve such surfaces are to use bump or displacement
maps (Section 13.5.6). A third approach, piecewise smooth subdivision,
is described here. The basic idea is to change the subdivision rules so
that darts, corners,andcreases can be used. This increases the range of
different surfaces that can be modeled and represented. Hoppe et al. [559]
first described this for Loop’s subdivision surfaces. See Figure 13.49 for a
9
See the SIGGRAPH course notes for more on this topic [1415].
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.