Subdivision Surfaces.

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 x₁,…, x_n sharing a common central point x^c, always n segments at refinement level m form an annular piece of surface x^m, called a ring. As illustrated by Fig. 4.3/61 (top), the sequence of rings is nested, and contracts towards the central point x^c. 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 x^m = GQ^m in terms of a vector Q^m 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 x^m = GQ^m, 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⁻¹, 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]