i
i
i
i
i
i
i
i
640 13. Curves and Curved Surfaces
p
00
p
01
p
02
p
03
p
10
p
11
p
12
p
13
p
20
p
21
p
22
p
23
p
30
p
31
p
32
p
33
Figure 13.62. A bicubic B´ezier patch with 4 × 4 control points.
tion 13.2.1). This is not possible for non-quadrilaterals, and so we assume
that there are no such polygons (recall that after the first step of subdivi-
sion there are only quadrilateral polygons). When a vertex has a valence
different from four, it is not possible to create a bicubic B´ezier patch that
is identical to the Catmull-Clark surface. Hence, an approximative repre-
sentation is proposed, which is exact for quads with valence-four vertices,
and very close to the Catmull-Clark surface elsewhere. To this end, both
geometry patches and tangent patches are used, which will be described
next.
The geometry patch is simply a bicubic B´ezier patch, as illustrated in
Figure 13.62, with 4 ×4 control points. We will describe how these control
points are computed. Once this is done, the patch can be tessellated and
the vertex shader can evaluate the B´ezier patch quickly at any parametric
coordinate (u, v). So, assuming we have a mesh consisting of only quads
with vertices of valence four, we want to compute the control points of the
corresponding B´ezier patch for a certain quad in the mesh. To that end,
the neighborhood around the quad is needed. The standard way of doing
this is illustrated in Figure 13.63, where three different masks are shown.
These can be rotated and reflected in order to create all the 16 control
points. Note that in an implementation the weights for the masks should
sum to one; that process is omitted here for clarity.
The above technique computes a B´ezier patch for the ordinary case.
When there is at least one extraordinary vertex, we compute an extraordi-
nary patch [790]. The masks for this are shown in Figure 13.64, where the
lower left vertex in the gray quad is an extraordinary vertex.
Note that this results in a patch that approximates the Catmull-Clark
subdivision surface, and, it is only C
0
along edges with an extraordinary
vertex. This often looks distracting when shading is added, and hence a
i
i
i
i
i
i
i
i
13.6. Efficient Tessellation 641
42
21
2
41
4
41
411
1
4
16
82
1
Figure 13.63. Top left: part of a quad mesh, where we want to compute a B´ezier patch
for the gray quad. Note that the gray quad only has vertices with valence four. The
blue vertices are neighboring quads’ vertices, and the green circles are the control points
of the B´ezier patch. The following three illustrations show the different masks used to
compute the green control points. For example, to compute one of the inner control
points, the upper right mask is used, and the vertices of the quad are weighted with the
weight shown in the mask.
similar trick as used for N-patches (Section 13.2.3) is suggested. However,
to reduce the computational complexity, two tangent patches are derived:
one in the u-direction, and one the v-direction. The normal is then found
as the cross-product between those vectors. In general, the derivatives of
aB´ezier patch are computed using Equation 13.30. However, since the de-
rived B´ezier patches approximate the Catmull-Clark surface, the tangent
patches will not form a continuous normal field. Consult Loop and Schae-
fer’s paper [790] on how to overcome these problems. Figure 13.65 shows an
example of the types of artifacts that can occur. With an early implemen-
tation, this method was able to produce over 100 million polygons/second
on an Xbox 360 [790].
i
i
i
i
i
i
i
i
642 13. Curves and Curved Surfaces
4
4
1
4
1
1
4
n
2
1
4
2
2
1
n
2
4
11
2
2n
Figure 13.64. Top left: part of a quad mesh, where we want to compute a B´ezier patch
for the gray quad. The lower left vertex in the gray quad is extraordinary, since its
valence is n = 4. The blue vertices are neighboring quads’ vertices, and the green circles
are the control points of the B´ezier patch. The following three illustrations show the
different masks used to compute the green control points.
Figure 13.65. Left: quad structure of a mesh. White quads are ordinary, green have one
extraordinary vertex, and blue have more than one. Mid-left: geometry path approxima-
tion. Mid-right: geometry patches with tangent patches. Note that the obvious shading
artifacts disappeared. Right: true Catmull-Clark surface. (Image courtesy of Charles
Loop and Scott Schaefer, reprinted with permission from Microsoft Corporation.)
i
i
i
i
i
i
i
i
13.6. Efficient Tessellation 643
Further Reading and Resources
The topic of curves and surfaces is huge, and for more information, it is
best to consult the books that focus solely on this topic. Mortenson’s
book [905] serves as a good general introduction to geometric modeling.
Books by Farin [332, 335], and by Hoschek and Lasser [569] are general
and treat many aspects of Computer Aided Geometric Design (CAGD). For
implicit surfaces, consult the excellent book by Bloomenthal et al. [117].
For much more information on subdivision surfaces, consult Warren and
Heimer’s book [1328], and the SIGGRAPH course notes on “Subdivision
for Modeling and Animation” [1415] by Zorin et al.
For spline interpolation, we refer the interested reader to Watt and
Watt [1330], Rogers [1076], and the Killer-B’s book [68]. Many proper-
ties of Bernstein polynomials, both for curves and surfaces, are given by
Goldman [416]. Almost everything about triangular B´ezier surfaces can be
found in Farin’s article [331]. Another class of rational curves and surfaces
is the Non-Uniform Rational B-Splines (NURBS) [334, 1015, 1078].
An easy-to-read article on how to implement a subdivision algorithm
is given by Sharp [1160], which is a follow-up to his article on subdivi-
sion surface theory [1159]. While Kobbelt’s
√
3-scheme is approximating,
there is also an interpolating
√
3-scheme [706]. Proposals for implementing
Loop’s subdivision scheme in hardware have been presented by various re-
searchers [88, 1036]. Biermann et al. [86] present schemes that have normal
control, i.e., that a normal can be set at a vertex and a tangent-plane con-
tinuous surface generated. Many good presentations on continuity analysis
on subdivision surfaces are available [679, 1056, 1328, 1412, 1414, 1415].
See also Stam’s paper [1212] on how to evaluate Catmull-Clark surfaces at
arbitrary parameter values using explicit formulae.
There are some different techniques for performing repeated subdivision
or tessellation on the GPU [147, 1175]. Most of these render out vertices
to two-dimensional textures and perform subdivision repeatedly until some
convergence criterion is fulfilled. Loop and Blinn use the GPU to render
piecewise algebraic surfaces, i.e., without any tessellation [789]. This looks
convincing, but on current GPUs, this disables Z-culling (Section 18.3.7)
and any early-Z test.
i
i
i
i
i
i
i
i
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.