i
i
i
i
i
i
i
i
610 13. Curves and Curved Surfaces
Figure 13.30. The 4-point subdivision scheme in action. This is an interpolating scheme
as the curve goes through the initial points, and in general curve P
i+1
goes through the
points of P
i
. Note that the same control polygon is used in Figure 13.29.
is the result, but when w =1/16, we get the kind of behavior shown in
Figure 13.30. It can be shown [290] that the resulting curve is C
1
when
0 <w<1/8. For open polylines we run into problems at the endpoints
because we need two points on both sides of the new point, and we only
have one. This can be solved if the point next to the endpoint is reflected
across the endpoint. So, for the start of the polyline, p
1
is reflected across
p
0
to obtain p
−1
. This point is then used in the subdivision process. The
creation of p
−1
is shown in Figure 13.31.
Another interesting approximating scheme uses the following subdivi-
sion rules:
p
k+1
2i
=
3
4
p
k
i
+
1
8
(p
k
i−1
+ p
k
i+1
),
p
k+1
2i+1
=
1
2
(p
k
i
+ p
k
i+1
).
(13.48)
The first line updates the existing points, and the second computes the
midpoint on the line segment between two neighboring points. This scheme
generates a cubic B-spline curve. Consult the SIGGRAPH course on sub-
division [1415], the Killer B’s book [68], Warren and Weimer’s subdivision
book [1328], or Farin’s CAGD book [332] for more about these curves.
Given a point p and its neighboring points, it is possible to directly
“push” that point to the limit curve, i.e., determine what the coordinates
Figure 13.31. The creation of a reflection point, p
−1
, for open polylines. The reflection
point is computed as: p
−1
= p
0
− (p
1
− p
0
)=2p
0
− p
1
.
i
i
i
i
i
i
i
i
13.5. Subdivision Surfaces 611
of p would be on P
∞
. This is also possible for tangents. See, for example,
Joy’s online introduction to this topic [615].
The topic of subdivision curves has only been touched upon, but it is
sufficient for the presentation of subdivision surfaces that follows in the
next section. See the Further Reading and Resources section at the end of
this chapter for more references and information.
13.5 Subdivision Surfaces
Subdivision surfaces are a powerful paradigm in defining smooth, contin-
uous, crackless surfaces from meshes with arbitrary topology. As with all
other surfaces in this chapter, subdivision surfaces also provide infinite level
of detail. That is, you can generate as many triangles or polygons as you
Figure 13.32. The top left image shows the control mesh, i.e., that original mesh, which is
the only geometrical data that describes the resulting subdivision surface. The following
images are subdivided one, two, and three times. As can be seen, more and more
polygons are generated and the surface gets smoother and smoother. The scheme used
here is the Catmull-Clark scheme, described in Section 13.5.4.
i
i
i
i
i
i
i
i
612 13. Curves and Curved Surfaces
Figure 13.33. Subdivision as refinement and smoothing. The refinement phase creates
new vertices and reconnects to create new triangles, and the smoothing phase computes
new positions for the vertices.
wish, and the original surface representation is compact. An example of
a surface being subdivided is shown in Figure 13.32. Another advantage
is that subdivision rules are simple and easily implemented. A disadvan-
tage is that the analysis of surface continuity often is very mathematically
involved. However, this sort of analysis is often only of interest to those
who wish to create new subdivision schemes, and is out of the scope of this
book—for such details, consult Warren and Weimer’s book [1328] and the
SIGGRAPH course on subdivision [1415].
In general, the subdivision of surfaces (and curves) can be thought of as
a two-phase process [679]. Starting with a polygonal mesh, called the con-
trol mesh, the first phase, called the refinement phase, creates new vertices
and reconnects to create new, smaller triangles. The second, called the
smoothing phase, typically computes new positions for some or all vertices
in the mesh. This is illustrated in Figure 13.33. It is the details of these two
phases that characterize a subdivision scheme. In the first phase, a polygon
can be split in different ways, and in the second phase, the choice of sub-
division rules give different characteristics such as the level of continuity,
and whether the surface is approximating or interpolating.
A subdivision scheme can be characterized by whether it is stationary,
whether it is uniform, and whether it is triangle-based or polygon-based .
A stationary scheme uses the same subdivision rules at every subdivision
step, while a nonstationary may change the rules depending on which step
currently is being processed. The schemes treated below are all stationary.
A uniform scheme uses the same rules for every vertex or edge, while a
nonuniform scheme may use different rules for different vertices or edges.
As an example, a different set of rules is often used for edges that are on the
boundaries of a surface. A triangle-based scheme only operates on triangles,
and thus only generates triangles, while a polygon-based scheme operates
on arbitrary polygons. We will mostly present triangle-based schemes here
because that is what graphics hardware is targeted for, but we will also
briefly cover some well-known polygon-based schemes.
i
i
i
i
i
i
i
i
13.5. Subdivision Surfaces 613
Several different subdivision schemes are presented next. Following
these, two techniques are presented that extend the use of subdivision sur-
faces, along with methods for subdividing normals, texture coordinates,
and colors. Finally, some practical algorithms for subdivision and render-
ing are presented.
13.5.1 Loop Subdivision
Loop’s subdivision scheme [787]
5
was the first subdivision scheme for tri-
angles. It is similar to the last scheme in Section 13.4 in that it is approxi-
mating, and that it updates each existing vertex and creates a new vertex
for each edge. The connectivity for this scheme is shown in Figure 13.34.
As can be seen, each triangle is subdivided into four new triangles, so after
n subdivision steps, a triangle has been subdivided into 4
n
triangles.
First, let us focus on an existing vertex p
k
,wherek is the number of
subdivision steps. This means that p
0
is the vertex of the control mesh.
Figure 13.34. The connectivity of two subdivision steps for schemes such as Loop’s and
the modified butterfly scheme (see Section 13.5.2). Each triangle generates four new
triangles.
Figure 13.35. The notation used for Loop’s subdivision scheme. The left neighborhood
is subdivided into the neighborhood to the right. The center point p
k
is updated and
replaced by p
k+1
, and for each edge between p
k
and p
k
i
, a new point is created (p
k+1
i
,
i ∈ 1,...,n).
5
A brief overview of Loop’s subdivision scheme is also presented by Hoppe et al. [559].
i
i
i
i
i
i
i
i
614 13. Curves and Curved Surfaces
After one subdivision step, p
0
turns into p
1
. In general, p
0
→ p
1
→
p
2
→···→p
∞
,wherep
∞
is the limit point. If the valence of p
k
is n,then
p
k
has n neighboring vertices, p
k
i
, i ∈{0, 1,...,n− 1}. See Figure 13.35
for the notation described above. Also, a vertex that has valence 6 is called
regular or ordinary; otherwise it is called irregular or extraordinary.
Below, the subdivision rules for Loop’s scheme are given, where the first
formula is the rule for updating an existing vertex p
k
into p
k+1
,andthe
second formula is for creating a new vertex, p
k+1
i
, between p
k
and each of
the p
k
i
. Again, n is the valence of p
k
:
p
k+1
=(1− nβ)p
k
+ β(p
k
0
+ ···+ p
k
n−1
),
p
k+1
i
=
3p
k
+3p
k
i
+ p
k
i−1
+ p
k
i+1
8
,i=0...n− 1.
(13.49)
Note that we assume that the indices are computed modulo n,sothat
if i = n −1, then for i + 1, we use index 0, and likewise when i =0,thenfor
i − 1, we use index n − 1. These subdivision rules can easily be visualized
as masks, also called stencils; see Figure 13.36. The major use of these is
that they communicate almost an entire subdivision scheme using only a
simple illustration. Note that the weights sum to one for both masks. This
is a characteristic that is true for all subdivision schemes, and the rationale
for this is that a new point should lie in the neighborhood of the weighted
points. In Equation 13.49, the constant β is actually a function of n,and
is given by
β(n)=
1
n
5
8
−
(3 + 2 cos(2π/n))
2
64
. (13.50)
Loop’s suggestion [787] for the β-function gives a surface of C
2
continu-
ity at every regular vertex, and C
1
elsewhere [1413], that is, at all irregular
vertices. As only regular vertices are created during subdivision, the sur-
face is only C
1
at the places where we had irregular vertices in the control
Figure 13.36. The masks for Loop’s subdivision scheme (black circles indicate which
vertex is updated/generated). A mask shows the weights for each involved vertex. For
example, when updating an existing vertex, the weight 1 − nβ is used for the existing
vertex, and the weight β is used for all the neighboring vertices, called the 1-ring.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.