226 CHAPTER 7 Averaging Schemes for Polyhedral Meshes
interpolation of arbitrary curves using subdivision. This scheme is the basis of a
trimming algorithm used to compute the intersection of two subdivision surfaces
[98]. In [109], [110], and [112], Nasri describes several schemes used to interpo-
late points and normals along curves.
7.3 Smooth Subdivision for Triangle Meshes
The previous section described a scheme for smoothly subdividing a quadrilat-
eral mesh in which a single round of subdivision is decomposed into two simpler
steps: bilinear subdivision and quad averaging. One of the major advantages of this
scheme is that almost all of the topological computation takes place during bilinear
subdivision. The only topological information computed during quad averaging is
the valence
val[v] for each vertex v in M
k
. Maintained as an array, val[v] can easily
be computed during a single pass through
M
k
or simply updated during bilinear
subdivision, in that all old vertices in
M
k−1
inherit the same valence and all new ver-
tices introduced into
M
k
have valence four. This decomposition of the subdivision
scheme into two steps is superior to the single-step approach because it avoids the
need to compute or maintain an explicit set of neighbors for each vertex in
M
k−1
.
Our goal in this section is to develop a similar two-step scheme for smoothly
subdividing triangle meshes. Again, the main benefit of this scheme is that it avoids
the need to compute or maintain explicit neighbor information for the meshes
M
k
.
Clearly, the first step of our scheme should be linear subdivision. As described in
section 7.1, linear subdivision can easily be implemented as a single pass through the
triangles of
M
k−1
. All that remains is to construct an averaging method for triangle
meshes that is analogous to quad averaging. Once we have derived this averaging
operator for uniform triangle meshes, an extension to meshes with extraordinary
vertices follows naturally.
7.3.1 Linear Subdivision Plus Triangle Averaging
The key to constructing an averaging rule for triangle meshes is to recall the three-
direction quartic box spline of Chapter 2. This spline is a
C
2
piecewise quartic
function defined over a three-direction triangle mesh. In particular, the set of di-
rection vectors
for this scheme has the form
={{1, 0}, {1, 0}, {0, 1}, {0, 1}, {1, 1}, {1, 1}}.