Search

In the last chapter, we have defined a C0k-subdivision algorithm as a pair (A, G) consisting of a subdivision matrix A and a Ck-system G of generating rings. The conditions given in Definition 4.27/80 guarantee that the generated splines are consistent at the center. Such algorithms are easy to construct, but of course, they do not live up to the demands arising in applications, where smoothness is required also at extraordinary knots. In this chapter, we consider subdivision algorithms in more detail with the goal to find conditions for normal continuity and single-sheetedness. First, in Sect. 5.1/84, we define `generic΄ sets of initial data Q. Restriction to generic data is necessary to exclude degenerate configurations which, even for impeccable algorithms, yield non-smooth surfaces. Section 5.2/84 defines standard algorithms. This class of algorithms, which is predominant in applications, is characterized by a double positive subdominant eigenvalue. Here, the characteristic ring, which is a planar ring built from the subdominant eigenfunctions, plays a key role in the analysis. With a careful generalization of terms, Sect. 5.3/89 yields a complete classification of all C1k-subdivision algorithms. Because we will mostly focus on standard algorithms throughout the book, this part, which is quite technical, may be skipped on a first reading. In Sect. 5.4/95, we consider shift invariant algorithms. Shift invari- ant algorithms have the property that the shape of the generated splines is independent of the starting point which we choose for labeling the segments xj, j ϵ ℤn. The subdivision matrix of shift invariant algorithms is block-circulant and can be transformed to block-diagonal form by means of the Discrete Fourier Transform. This process is of major importance in applications, as well as for the further development of the theory. Typically, subdivision algorithms are not only shift invariant, but also indifferent with respect to a reversal of orientation of segment labels. Such symmetric algorithms are discussed in Sect. 5.5/103. We show that symmetric algorithms necessarily have a pair of real subdominant eigenvalues, justifying our focus on such schemes. Further, we specify easy-to-verify conditions for the characteristic ring which guarantee normal continuity and single-sheetedness of the generated spline surfaces. [ABSTRACT FROM AUTHOR]

In this chapter, we formally introduce and scrutinize three of the most popular subdivision algorithms, namely the Catmull–Clark algorithm [CC78], the Doo–Sabin algorithm [DS78], and Simplest subdivision1 [PR97]. Besides the algorithms in their original form, it is instructive to consider certain variants. We selectively modify a subset of weights to obtain a variety of algorithms that is rich enough to illustrate the relevance of the theory developed so far. In particular, we show that a double subdominant eigenvalue is neither necessary nor sufficient for a C1k-algorithm: First, there are variants of the Doo-Sabin algorithm with a double subdominant eigenvalue, which provably fail to be C11 because the Jacobian determinant ×Dψ of the characteristic ring changes sign. Second, for valence n = 3, Simplest subdivision reveals an eightfold subdominant eigenvalue, but due to the appropriate structure of Jordan blocks, it is still C11. In all cases, the algorithms are symmetric so that the conditions of Theorem 5.24/105 can be used for the analysis. [ABSTRACT FROM AUTHOR]

Subdivision derives its name from a splitting of the domain. A spline x on the initial domain S is mapped to a finer domain S~ where it is represented by more, smaller pieces. This chapter focuses on such refinement, in particular near extraordinary knots. We will not yet discuss specific algorithms. Section 4.1/58 motivates the framework of subdivision by formalizing the refinement of spline domains: the basic step is to replaced each cell of the given domain by four new ones. In Sect. 4.2/59, we study a special reparametrization of splines, which is facilitated by iterated domain refinement. If exactly one of the corners of the initial square is an extraordinary knot, one of the four new cells inherits this knot while the other three, which have only ordinary knots, combine to an L-shape. Accordingly, the initial surface patch is split into a smaller patch with an extraordinary point, and an L-shaped segment. Repeating the refinement for the new extraordinary patch yields another patch and another segment of even smaller size. If this process is iterated ad infinitum, the initial patch is eventually replaced by a sequence of smaller and smaller segments, and the extraordinary point itself. If we consider a spline surface x consisting of n patches x1,…, xn sharing a common central point xc, always n segments at refinement level m form an annular piece of surface xm, called a ring. As illustrated by Fig. 4.3/61 (top), the sequence of rings is nested, and contracts towards the central point xc. The representation of a spline as the union of rings and a central point is called a spline in subdivision form. Thus, spline surfaces in subdivision form, as they are generated by many popular algorithms, can be understood by analyzing this sequence. In particular, the conditions for continuity, smoothness and single-sheetedness can all be reduced to conditions on rings. In Sect. 4.3/65, we represent a ring xm = GQm in terms of a vector Qm of coefficientsqℓm ϵ ℝd and a vector G of generating rings gℓ. Typically, we think of qℓm as points in 3-space. But qℓm can just as well represent derivative data, or color and texture information so that the setup conveniently covers a very general setting. In many practical algorithms, the generating rings are built from box-splines and form a basis. We emphasize, however, that we assume neither that the generating rings are piecewise polynomial nor that they are linearly independent. Joining the rings xm = GQm, we obtain the representation of the spline x := BQ as a linear combination of generating splines bℓ. In Sect. 4.4/67, subdivision algorithms are characterized as recursions for rings. The recursion is governed by a subdivision matrix. Since the subdivision matrix is applied over and over again, it is natural to introduce at this point notational and algebraic tools: the asymptotic equivalence of expansions in Sect. 4.5/71 and the Jordan decomposition of matrices in Sect. 4.6/72. In particular, the subdivision matrix is decomposed into A = VJV−1, where V is a matrix of eigenvectors and generalized eigenvectors. Correspondingly, we introduce eigenrings F = GV and eigensplines E = BV. In Sect. 4.7/75, we can then relate properties of the subdivision matrix to properties of the limit surface. In the process, we see examples of the insufficiency of an analysis based solely on the control points. [ABSTRACT FROM AUTHOR]

The analysis of stationary linear subdivision algorithms presented in this book summarizes and enhances the results of three decades of intense research and it combines them into a full framework. While our understanding of C1-algorithms is now almost complete, the generation and the analysis of algorithms of higher regularity still offers some challenges. Guided subdivision and the PTER-framework pave a path towards algorithms of higher regularity, that, for a long time, were considered not constructible. Various aspects of these new ideas have to be investigated, and the development is in full swing, at the time of writing. In focusing on analytical aspects of subdivision surfaces from a differential geometric point of view, we left out a number of other interesting and important topics, such as the following. Implementation issues: In many applications, subdivision is considered a recipe for mesh refinement, rather than a recursion for generating sequences of rings. The availability of simple, efficient strategies for implementation [ZSOO, SAUK04], even in the confines of the Graphics Processing Unit [BS02, SP03, SJP05a], evaluation of refinable functions at arbitrary rational parameters [CDM91] and, for polynomial subdivision, at arbitrary parameters [Sta98a, Sta98c] and their inclusion into the graphics pipeline [DeR98, DKT98] largely account for the overwhelming success of subdivision in Computer Graphics.Sharp(er) features: By using modified weights for specially `tagged΄ vertices or edges, it is possible to blend subdivision of space curves and subdivision of surfaces to deliberately sharpen features and even reduce the smoothness to represent creases or cusps [DKT98,Sch96]. In a similar way, subdivision algorithms can be adapted to match curves and boundaries [Nas91,Lev99c,Lev00,Nas03].Multiresolution: Based on the inherent hierarchy of finer and finer spaces, one can develop strategies for multiresolution editing of subdivision surfaces [LDW97]. There are close relations to the study of wavelets, but this development is still in its infancy.Applications in scientific computing: Beyond the world of Computer Graphics, subdivision surfaces can be employed for the simulation of thin shells and plates [COSOO, GKS02, Gri03, GTS02], and possibly also in the boundary element method. Many of these and other application-oriented issues are discussed in the book of Warren and Weimer [WW02]. Necessarily, the material presented here is a compromise between generality and specificity. Therefore, to conclude, we want to review the basic assumptions of our analysis framework, check applicability to the rich `zoo΄ of subdivision algorithms in current use, and discuss possible generalizations. We consider in turn function spaces, types of recursion, and the underlying combinatorial structure. [ABSTRACT FROM AUTHOR]

In the preceding chapters, we have studied first order properties of subdivision surfaces in the vicinity of an extraordinary point. Now we look at second order properties, such as the Gaussian curvature or the embedded Weingarten map, which characterize shape. To simplify the setup, we assume k ≥ 2 throughout. That is, second order partial derivatives of the patches xjm exist and satisfy the contact conditions (4.7/62) and (4.8/62) between neighboring and consecutive segments. However, most concepts are equally useful in situations where the second order partial derivatives are well defined only almost everywhere. In particular, all piecewise polynomial algorithms, such as Doo-Sabin type algorithms or Simplest subdivision, can be analyzed following the ideas to be developed now. In Sect. 7.1/126, we apply the higher-order differential geometric concepts of Chap. 2/15 to subdivision surfaces and derive asymptotic expansions for the fundamental forms, the embedded Weingarten map, and the principal curvatures. In particular, we determine limit exponents for Lp-integrability of principal curvatures in terms of the leading eigenvalues of the subdivision matrix. The central ring will play a key role, just as the characteristic ring for the study for first order properties. In Sect. 7.2/134, we can leverage the concepts to characterize fundamental shape properties. To this end, the well-known notions of ellipticity and hyperbolicity are generalized in three different ways to cover the special situation in a vicinity of the central point. Properties of the central ring reflect the local behavior, while the Fourier index F(μ) of the subsubdominant eigenvalue μ of the subdivision matrix is closely related to the variety of producible shapes. In particular, F(μ) ⊃ {0, 2, n − 2} is necessary to avoid undue restrictions. Further, we introduce shape charts as a tool for summarizing, in a single image, information about the entirety of producible shape. Conditions for C2k-algorithms are discussed in Sect. 7.3/140. Following Theorem 2.14/28, curvature continuity is equivalent to convergence of the embedded Weingarten map. This implies that the subsubdominant eigenvalue μ must be the square of the subdominant eigenvalue λ, and the subsubdominant eigenrings must be quadratic polynomials in the components of the characteristic ring. These extremely restrictive conditions explain the difficulties encountered when trying to construct C2k-algorithms. In particular, they lead to a lower bound on the degree of piecewise polynomial schemes, which rules out all schemes generalizing uniform B-spline subdivision, such as the Catmull-Clark algorithm. Section 7.4/145 presents hitherto unpublished material concerning a general principle for the construction of C2k-algorithms, called the PTER-framework. This acronym refers to the four building blocks: projection, turn-back, extension, and reparametrization. The important special case of Guided subdivision, which inspired that development, is presented in Sect. 7.5/149. [ABSTRACT FROM AUTHOR]

In this chapter, we elaborate on two aspects of subdivision which, besides smoothness, are very important for applications – convergence of sequences of so-called proxy surfaces, such as control polyhedra, and linear independence of generating splines. In Sect. 8.1/157, we consider a sequence {xŽk}k of proxy surfaces to a subdivision surface x. For example, piecewise linear proxy surfaces arise as `control polyhedra΄ in whatever sence, or as a sequence of finer and finer piecewise linear interpolants of x. The analysis to be developed is, however, sufficiently general to cover cases where the proxy surfaces consist of non-linear pieces, for instance, when approximating x by an increasing, but finite number of polynomial patches. We derive upper bounds on the parametric and geometric distance between xŽk and x, which are asymptotically sharp up to constants as k → ∞. Our results show that the rate of convergence of the geometric distance, which is crucial for applications in Computer Graphics, depends on the subsubdominant eigenvalue μ. In Sect. 8.2/169, we consider the question of local and global linear independence of the generating splines B = [b0,…, bℓ–]. This topic is closely related to the existence and uniqueness of solutions of approximation problems in spaces of subdivision surfaces, such as interpolation or fairing. We show that local linear independence cannot be expected if the valence n is high, and that even global linear independence is lost in special situation, like Catmull-Clark subdivision for a control net with the combinatorial structure of a cube. [ABSTRACT FROM AUTHOR]

In this chapter, we define bivariate splines. The term spline is often used synonymous with linear combinations of B-splines and hence piecewise polynomials. We will define splines in a less restrictive fashion to include, for example, trigonometric splines and functions generated by interpolating refinement algorithms. This will allow us to cover the shared underlying fundamentals once and for all. Specifically, splines are defined as continuous functions on a domain that is a topological space. This domain is the result of gluing together indexed copies of the unit square, and is locally homeomorphic to the domain of standard bivariate tensor product spline spaces – except at extraordinary knots where more or fewer than four unit squares join up. Consequently, we can focus on characterizing analytical and differential-geometric properties of such splines at and near these isolated singularities. [ABSTRACT FROM AUTHOR]

Subdivision surfaces can be viewed from at least three different vantage points. A designer may focus on the increasingly smooth shape of refined polyhedra. The programmer sees local operators applied to a graph data structure. This book views subdivision surfaces as spline surfaces with singularities and it will focus on these singularities to reveal the analytic nature of subdivision surfaces. Leveraging the rich interplay of linear algebra, analysis and differential geometry that the spline approach affords, we will, in particular, be able to clarify the necessary and sufficient constraints on subdivision algorithms to generate smooth surfaces. Viewing subdivision surfaces as spline surfaces with singularities is, at present, an unconventional point of view. Visualizing a sequence of polyhedra or tracking a sequence of control nets appears to be more intuitive. Ultimately, however, both views fail to capture the properties of subdivision surfaces due to their discrete nature and lack of attention to the underlying function space. In Sects. 1.1/1 and 1.2/2, we now briefly discuss the two points of view not taken in this book while in Sect. 1.3/4 the analytic view of subdivision surfaces as splines with singularities is sketched out. Section 1.4/6 delineates the focus and scope and Sect. 1.5/7 gives an overview over the topics covered in the book. A useful section to read is Sect. 1.6/7 on notation. The trailing two sections are special. We felt a need to recall the state of the art in subdivision in the regular, shift invariant setting, and to give an overview on the historical development of the topic discussed in this book. In view of our own, limited expertise in these fields, we decided to seek prominent help. Nira Dyn and Malcolm Sabin, two pioneers and leading researchers in the subdivision community agreed to contribute, and their insightful overviews form Sects. 1.7/8 and 1.8/11. [ABSTRACT FROM AUTHOR]

Subdivision surfaces have to be analyzed in the terms of differential geometry. This chapter summarizes well-known concepts, such as the Gauss map, the principal curvatures and the fundamental forms, but also develops material that is not found in standard text books, such as the embedded Weingarten map, that is crucial to understanding subdivision surfaces. Parametric singularities in the form of isolated `extraordinary points΄ are a key feature of subdivision surfaces. The analysis of such singularities requires a separate assessment of parametric and geometric continuity. Accordingly, we will define function spaces Crk where k indicates the smoothness of the parametrization, except at isolated points, and r measures the smoothness of the resulting surface in the geometric sense. After providing special notations for dot and cross products in Sect. 2.1/16, we consider basic concepts from the differential geometry of regularly parametrized surfaces in Sect. 2.2/17. In particular, the embedded Weingarten map, which is given by a (3 × 3)-matrix, is introduced as a geometric invariant for the study of curvature properties. Unlike the principal directions, it is uniquely defined and continuous even at umbillic points. This property is crucial for our subsequent considerations of limit properties of subdivision surfaces at singular points. In Sect. 2.3/23, the standard requirement on the regularity of the parametrization is suspended at an isolated point to allow for the structural conditions of subdivision surfaces. To establish geometric continuity, we first introduce the concept of `normal continuity΄. That is, we require that the normal map can be continuously extended from the regular neighborhood to the singular point. This unique normal is used to define a differential-geometric notion of smoothness. If and only if the projection of the surface to the tangent plane is injective, the surface is single-sheeted and meets the requirements of a two-dimensional manifold. Then, the surface can be viewed as the graph of a scalar-valued function in a local coordinate system: the parameters are associated with the tangent plane, and function values are measured in the normal direction. To capture both analytic and geometric smoothness, we call a single-sheeted surface Crk if its parametrization is Ck and the local height function is Cr. In case of single-sheetedness, we can use continuity of the Gauss map and the embedded Weingarten map to decide membership in C1k and C2k, respectively. This approach circumvents an explicit construction of the local height function. Using the embedded Weingarten map avoids having to select consistent coordinate systems in the set of tangent planes, as is necessary when working with the standard Weingarten map. [ABSTRACT FROM AUTHOR]