21.1 Recursive Subdivision Curves

We already encountered Chaikin’s algorithm in Section 8.4. Starting with a polygon, it produces a sequence of refined polygons that ultimately converge to the uniform quadratic B-spline curve defined by the initial polygon.

This principle may be applied to higher-degree uniform splines; we discuss the cubic case here. If we double a uniform knot sequence by inserting the midpoint of every knot, new control points are generated from the existing ones by setting

(21.1)

See Figure 21.1 for an illustration. We may analyze the resulting curve by exploiting the fact that we are dealing with a cubic B-spline curve. However, that analysis may also be carried out without this knowledge. Let us investigate the limit of the sequence . We may write the recursion in matrix form as

and abbreviate it as

(21.2)

The matrix A has eigenvalues and may be diagonalized¹ as

where

The matrix E contains A’s eigenvectors, and the diagonal matrix Λ contains A’s eigenvalues.

For the next iteration, we have

(21.3)

Using our diagonalization for A, we get

and further

Taking the limit r → ∞ yields

Since

this becomes

implying that all three points d_k–1, d_k, d_k+1 converge to the same point (d_k–1+ 4d_k + d_k+1)/6. This result is no surprise since we know we are dealing with B-spline curves. It does illustrate, however, a general principle that is ubiquitous in all subdivision theory, namely, that convergence analysis is normally carried out via an eigenvalue analysis.

Subdivision may also be used to generate interpolating curves. The basic four-point principle was developed by Dyn, Levin, and Gregory [178], [176]. Let a sequence of points p_i be given; then successively construct new sequences by setting

(21.4)

For an illustration, see Figure 21.2. The point is the result of applying cubic Lagrange interpolation at uniform knots, see [519].

At each level of the subdivision process, the points of the previous step are retained; this causes the scheme to interpolate to the initial set of points. The limit curve is C¹, but fails to be C².

21.2 Doo–Sabin Surfaces

The fundamental idea of this kind of surface goes back to Chaikin’s algorithm; see Section 8.4. There, we started with a polygon, iteratively applied a refinement procedure to it, and observed that in the limit we ended up with a smooth curve. M. Sabin and D. Doo asked if this principle could be carried over to surfaces: start with a polyhedron, iteratively apply a refinement procedure to it, and see if a smooth surface would result.

They then came up with the following algorithm, illustrated in Fig. 21.3 and documented in [174]: input: an arbitrary closed polyhedron with vertices p_i. These vertices form (straight) edges and (not necessarily planar) faces, thus defining the topology of the polyhedron. The refinement step now becomes:

Step 2 needs some more explanation. The new polyhedron will have faces that are constructed according to three different rules:

As we keep repeating the algorithm, it produces mostly four-sided faces. The only non-four-sided faces are V-faces generated by those initial vertices whose valency² is not four, or F-faces whose initial faces are not four sided. These faces give rise to limit points whose valency is not four, so-called extraordinary vertices. In fact, it is not hard to see that after the first step the valency of every new vertex is four. In this manner, large regions of the new polyhedra are covered with nets that have a tensor product structure. Doo–Sabin surfaces are thus “mostly” biquadratic B-splines. See Figure 21.4 for an example.

Let us briefly analyze the structure of the Doo–Sabin algorithm. New face points are created from previous ones in a linear fashion that lends itself to a matrix formulation. Let us consider a five-sided face such as the center face in Figure 21.3. We obtain

(21.7)

We may write this as

which becomes

after r applications of the algorithm. In the general case, we have the same structure but have to replace A₅ by a matrix A_n for faces with n edges.

As r increases, the behavior of the subdivision process depends crucially on the eigenvalues of A_n since we may write as

following the approach of Section 21.1. Since all rows of A_n sum to unity, one eigenvalue is λ₁ = 1. The remaining ones are all real since A is symmetric and are all between 0 and 1 since each V^(k) is contained in the convex hull of V^(k–1). An exact analysis of this process is fairly involved and is omitted here. It reveals, however, that Doo–Sabin surfaces are G¹ everywhere. For more details, see [174] or [18], [19], [503]. The matrices A_n are circulant, and their eigenstructure has been studied in detail by P. Davis [134]. A matrix is circulant if each row may be obtained from the previous row by a “right shift.”

Figure 21.4 gives an example of several steps of the algorithm.

As a rather trivial observation, Doo–Sabin surfaces have the convex hull and local control properties, and their construction is affinely invariant. But they also do not need an underlying parametrization, which makes them more geometric than tensor product B-spline surfaces. A drawback of this nice feature is the problem of point evaluation: though we can evaluate as many points as close to the surface as we like, computation of just one point is not trivial.

One set of points on the surface is easy to identify: at every level of subdivision, the centroid of any face will be on the final surface. For a proof, we observe that any face will produce a sequence of F-faces converging to its centroid. In the limit, the centroid is thus on the surface.

21.3 Catmull–Clark Subdivision

The same issue of Computer-Aided Design that included the Doo–Sabin algorithm also contained a competing method, invented by E. Catmull and J. Clark; see [103]. Whereas Doo–Sabin surfaces are a generalization of biquadratic B-splines to arbitrary topology, Catmull–Clark surfaces generalize bicubic B-spline surfaces to arbitrary topology.

We start with a polygonal mesh consisting of vertices . We iteratively refine the mesh, resulting in finer and finer meshes consisting of vertices . Each refinement step can be described by explaining what happens locally for the points adjacent to a vertex vⁱ:

Note that all faces after the first level will be four sided. The basic principle is shown in Figure 21.5. Figure 21.6 gives an example.

For the example of a vertex with valency n = 4, the relationship between new and old vertices may be expressed as a matrix equation:

For valencies other than four, similar matrix equations hold; see [308]. Those vertices converge to extraordinary vertices.

We may abbreviate (21.3) as

(21.9)

An equivalent form of (21.9) is given by

(21.10)

We note that the matrix A must be stochastic; that is, the elements of each row must sum to one. This is a consequence of the fact that (21.8) represents a barycentric combination. We further note that our mesh refinement consists of taking convex combinations at each level: this implies that all meshes lie in the convex hull of

It follows that A has the dominant eigenvalue 1; the magnitudes of all other (possibly complex) eigenvalues are bounded by 1.

A careful eigenvalue analysis (see Ball and Storry [18]) can now be used to show that

(21.11)

While Catmull–Clark surfaces are generalizations of uniform bicubic spline surfaces, a generalization of the nonuniform case also exists; it is described in [561].

21.4 Midpoint Subdivision

This algorithm is simpler than either Catmull–Clark or Doo–Sabin and goes back to Peters and Reif [469] who call it “the simplest scheme.”

Matrices of the form (21.12) are called circulant.

After k iterations, this becomes

The matrix M may be decomposed into a product

where E is the matrix containing M’s eigenvectors and Λ is the diagonal matrix containing M’s eigenvalues. We then have, following the reasoning in Section 21.1,

The analysis of the limit process is thus closely related to the eigenstructure of M. A result from Davis [134] asserts that for any initial polygon P, we obtain regular planar polygons in the limit. These will be the tangent planes to our surface, which therefore is G¹.

21.5 Loop Subdivision

A triangle-based subdivision scheme was discussed by C. Loop [397]. Its input is a triangular mesh as discussed in Section 21.9. It then successively refines this mesh, resulting in a smooth limit surface.

Loop subdivision proceeds as follows.

Now consider the mesh that is obtained after some number k of iterations. Select any vertex v of it. This vertex will converge to a point v^∞ on the limit surface. Using an eigenvalue analysis as mentioned, we can show (see [584]) that this limit point is given by

(21.15)

where the v_j are the neighbors of v in the mesh obtained after k iterations. For the special case k = 0, (21.15) gives the limit points corresponding to the original mesh vertices.

If all vertices in the mesh have valency six, then the resulting limit surface will be a collection of quartic Bézier triangles that form a C² surface over an equilateral triangulation of a simply connected region of a (domain) plane. We note that closed surfaces cannot be formed using only points with valency six. Vertices with different valencies converge to extraordinary vertices, where the surface is only G¹.

21.6 Subdivision

This scheme was developed by L. Kobbelt [362] and was also considered by Sabin [517]. We start with a triangular mesh and then subdivide each triangle into three triangles by splitting it at its centroid. Next, all edges of the initial mesh are flipped—instead of joining the initial vertices, they now join adjacent centroids. Finally, each initial vertex p (having valency n) is replaced by a barycentric combination of its neighbors:

where the neighbors of p are averaged to obtain c. The value for α_n is set at

An example of one step of the scheme is shown in Figure 21.10.

Each subdivision step rotates the directional structure of the triangular mesh; after two applications, the initial orientation is reestablished. Each original triangle has then given rise to nine new triangles. Following a rigorous study of the eigenstructure of the operator, we can show that the resulting limit surface is G² except at extraordinary points, where it still is G¹.

21.7 Interpolating Subdivision Surfaces

When dealing with B-splines, we could start from a control polygon and design a curve, or we could start with data points and find an interpolating curve. We can also use recursive subdivision surfaces for interpolation. The idea goes back to Nasri [440] and to M. Lounsbery, S. Mann, and T. DeRose [402]. The latter reference constructs interpolating Catmull–Clark surfaces, whereas Nasri constructs interpolating Doo–Sabin surfaces—we will start with them.

Given is a polyhedron with vertices p_i, and we wish to find another polyhedron with vertices v_i such that the resulting Doo–Sabin surfaces pass through the p_i. Each of the (unknown) v_i will generate a V-face with vertices q_i,k; k= 1, …, n_i, where n_i is the valency of v_i. We know that the centroids of these V-faces are on the surface, and we simply require them to be the given data points:

Note that the given points are not on the faces of the desired polyhedron, but rather on the V-faces obtained from it after one level of subdivision; see Figure 21.11 for an illustration.

Since the relationship between the q_i,k and the unknowns v_i is known, we have a set of linear equations relating the given p_i to the unknown v_i. For closed polyhedra, the number of equations equals the number of unknowns, leading to a sparse linear system.

This method lends itself to a hybrid usage: some control mesh vertices v_i may be given as with freeform design, whereas others are replaced by interpolation points p_i Each of the interpolation points gives rise to one linear equation, and the resulting system is easily solved. See Figure 21.12 for an example.

For open polyhedra, the situation is more complicated; it is dealt with by Nasri [439], [440], [441].

Catmull–Clark subdivision surfaces may also be employed to generate surfaces passing through a prescribed set of data points. We can use (21.11) to generate a control mesh that interpolates to a set of known data points v^∞. All (21.11) form a linear system for the unknowns v^1. This is a sparse system and thus quickly solved even if there are many (> 1000) data points.

It is mentioned in [308] that simply solving the least squares equations for the control points will result in “wiggly” surfaces. Adding shape equations as in Section 15.6 will overcome this problem.

In an similar fashion, (21.15) may be used to find a set of vertices v_i that will generate a Loop surface through the data points p_i. All these equations form a sparse linear system for the v_i. It may be solved using a sparse solver or by an iterative method.

A more direct way to interpolation, that is, without the need to “invert” existing methods, is given by the butterfly scheme, due to Dyn, Gregory, and Levin [176]. Its structure is identical to Loop subdivision, but different weights are applied. At a given level in the refinement process, the vertex points are kept, and only new edge points are generated. Each new edge point is generated from the surrounding vertex points by a mask as shown in Figure 21.13. The (solid) edge point is obtained as a barycentric combination of nearby points; the coefficients in that combination are indicated in the figure. They have to be multiplied by a factor of 1/16.

Just as in the four-point curve interpolation scheme of Section 21.1, interpolation is assured since vertex points are kept.

21.8 Surface Splines

As we iterate through the Doo–Sabin algorithm, more and more of the surface is covered by biquadratic patches, just leaving the extraordinary regions. After two iterations, these are already nicely separated—they correspond to s-sided regions. J. Peters had the idea of deviating from the Doo–Sabin procedure after two steps and to fill in these s-sided regions with a collection of bicubics, such that the overall surface is G¹; see [467] and also [466] or [463].³ It is not equivalent to the Doo–Sabin surface, but it has the advantage of being a collection of standard patches without singularities.

The situation after two (or more) steps of the Doo–Sabin algorithm is shown in Figure 21.14. We have so far created the points marked by squares. The solid squares mark control points surrounding an s-sided region, whereas the open ones are control points of the network of biquadratic patches. We are going to cover the s-sided region by a collection of s bicubic patches, all having a center point c in common. This center point is simply the average of all solid control points surrounding the s—sided region, only partially shown in Figure 21.14.

Next, we have to degree elevate each quadratic boundary curve of the s-sided region and to subdivide it at its (parametric) midpoint. This gives two boundary curves of each bicubic patch.

The “outer” two layers of each bicubic patch lie on bilinear patches as shown in Figure 21.14. Their computation⁴ is illustrated for the four top left points in that figure:

The remaining eight Bézier points along the outer patch boundary are found analogously.

The three remaining Bézier points b₂₂, b₂₃, b₃₂ are determined as follows:

where the superscript (i) refers to the ith bicubic patch of the patch collection covering the s-sided region. Now all angles ∠(b₃₃, b₃₂, b₂₃) are equal. The points must be determined such that G¹ continuity is ensured around b₃₃. Setting c = cos(2π/s) and , they are

A surface spline is shown in Figure 21.15.

Surface splines may also be used to interpolate to a mesh of data points in the same way as Doo–Sabin surfaces did: after two steps of the Doo–Sabin algorithm, move those control points that surround given data points such that their average equals that data point. Then proceed as before, and interpolation is ensured.

21.9 Triangular Meshes

We encountered triangular meshes in Section 3.7—there, we were dealing with 2D meshes. Keeping the same data structure, we may generalize 2D triangulations to 3D triangle meshes: these are surfaces consisting of a collection of triangles; see Figure 21.16. The vertices p_i of the triangles are now 3D points. Triangle meshes are piecewise linear and thus are not smooth—although this defect may be overcome by using very many triangles. One example is provided by the “Digital Michelangelo” project, carried out by M. Levoy. The aim of the project is to digitally record sculptures by Renaissance artist Michelangelo. Each sculpture was digitized using a laser digitizer; the resulting “point cloud” was then triangulated. For some sculptures, around two billion triangles were needed; see [386].

Boundary edges are edges in the mesh that belong to one triangle only; all other edges, being part of two triangles, are called interior edges. A vertex is called boundary vertex if it is on a boundary edge; otherwise, it is called an interior vertex. The solid vertex in Figure 21.17 is an interior vertex.

A significant difference between 2D and 3D triangulations is their topology. Every 2D triangulation must have boundary vertices, but 3D triangulations do not have to have any. Consider the example of a tetrahedron, the simplest 3D triangle mesh. It has four vertices and four triangles, all of them interior vertices. Triangular meshes without boundaries are called closed; those that do have boundaries are called open.

Two additional examples of closed meshes are a triangulated sphere and a triangulated torus. A major difference between these is their genus, a number describing the topology of a mesh. The genus of a closed mesh is the number of holes it has. Thus a sphere has genus zero, a torus has genus one, a double torus has genus two, and so forth. If we denote the number of faces, edges, and vertices by f, e, v, respectively, then the following equation may be used to define the genus G:

(21.16)

This is known as the Euler-Poincaré formula and is valid even for meshes with polygonal faces, not just triangular ones. For example, a cube consisting of six square faces, twelve edges, and eight vertices, has genus 0. If we split each square into two triangles, we have (f, e, v) = (12, 18, 8), again resulting in genus zero. For more details, see Hoffmann [327].

21.10 Decimation

In many cases, triangulations are far too dense for an efficient representation of an object. What is called for then is a reduction in size, also known as decimation.⁵The goal is to remove as many points as possible, while still staying close to the initial triangulation.

A decimation algorithm will thus perform a check on every point and determine if it can be removed. If so, the point (and sometimes its neighbors) are removed and the resulting gap will be retriangulated. The process continues until no more data can be removed.

An important ingredient in many mesh algorithms is a test for determining if a mesh is flat in the vicinity of a vertex p. For the following, we will need the concept of the star of a vertex p_i: this is the set of all triangles having p_i as a vertex; see Figure 21.17. Thus the star of a point is itself a triangle mesh.

In order to check if the mesh is flat around p, we compute the angles between all pairs of neighboring triangles in p. If the largest of these angles is less than a given tolerance, then we label p as flat. The tolerance is naturally application dependent, but 0.1 to 1 degrees should work well. This flatness test is independent of scalings of the mesh since angles are not affected by scales.

A different flatness criterion is due to M. Garland and P. Heckbert [254]. It locally constructs a quadric that approximates the neighborhood of a vertex. If the vertex is within a prescribed tolerance to this quadric, then it is labeled removable. This test is scale dependent: if the mesh is scaled, then the tolerance has to be scaled as well.

We now discuss a decimation method that is due to M. Lounsbery [400], [401]. It checks if an edge in a triangulation can be safely removed. If so, the edge is replaced by a point on it, thereby replacing two points by one. Retriangulation is fairly trivial: Figure 21.18 gives an example. A simple choice for the edge replacement point is the midpoint of the edge; more elaborate methods place it such that the shape of the resulting triangles is optimized.

When can an edge be removed? We simply perform a flatness test on the two edge vertices. If both meet the criterion, then the edge may be removed. Before that happens, it is advisable to check if the new triangles are within a specified tolerance to the old ones. An example of a decimated mesh is shown in Figure 21.19. This decimation method lends itself well to a multiresolution analysis of a triangle mesh. If we keep track of each collapsed edge, we create a hierarchy of triangle meshes. Each vertex in that hierarchy “knows” if it was generated by an edge collapse. The inverse process—recreating an edge from a vertex—is known as vertex split. Thus a heavily decimated mesh may be refined by successively adding in more edges using vertex splits. This successive refinement lends itself to streaming data transfer. More literature on multiresolution methods: [184], [183], [331], [330], [355].

A different decimation strategy is to remove a vertex, not an edge; this is due to Schroeder, Zarge, and Lorensen [545]. If a vertex is labeled removable, it is deleted and its star is retriangulated, see Figure 21.20.

For more literature on mesh decimation, see [116], [404], [544].

21.11 Problems