Abstract
Given a polyhedron, construct a new polyhedron by connecting every edge-midpoint to its four neighboring edge-midpoints. This refinement rule yields a C 1 surface and the surface has a piecewise quadratic parametrization except at a finite number of isolated points. We analyze and improve the construction.
INTRODUCTION
Consider an input polyhedron with not necessarily planar facets. The simplest subdivision scheme connects every edge-midpoint to the four midpoints of the edges that share both a vertex and a face with the current edge. Once all midpoints are linked, the old mesh is discarded. Figure 1 shows the process. Each subdivision step can be interpreted as cutting off all vertices including with each a neighborhood that reaches out to the midpoints of the emanating edges. In general, the cuts are not planar.
Since the subdivision mask consists of only two points and there is only one rule regardless of the connectivity of the polyhedron, the subdivision scheme is as simple as it can be. It is called midedge subdivision hereafter. We show in Section 2 that it is a factored box-spline subdivision and hence a close relative of the modified box-spline subdivisions of Doo and Sabin [1978] , Catmull and Clark [1978] , and Loop [1987] . Section 3 and the Appendix establish the smoothness of the limit surface and Section 4 specifies a modified midedge subdivision with improved convergence rate. The complete analysis of the smoothness of the limit surface is remarkable because only recently, after 30 years, the smoothness (and for some parameter choices the lack of smoothness) of the subdivision surfaces defined by Doo and Sabin [1978] and Catmull and Clark [1978] was rigorously established in Peters and Reif [1997] .
QUADRATIC PARAMETRIZATION
At each step, a subdivision algorithm creates a new mesh of points from an old mesh. A desirable property of any subdivision algorithm is that it generates increasing regions whose points all have the same valence and whose facets all have the same number of edges. A submesh of points and facets with this standard valence and number of edges is called regular. Specific subdivision rules such as those of Doo and Sabin, Catmull and Clark, or Loop derive their appeal from the fact that the limit surface is explicitly known for regular meshes; the limit surfaces are, respectively, biquadratic tensor-product spline surfaces, bicubic tensor-product spline surfaces, and surfaces formed as a linear combination of shifts of a 3-direction box spline. In midedge subdivision every new nonboundary point has exactly four neighbors, and every mesh point is replaced by a quadrilateral. A regular submesh consists therefore of quadrilaterals and Smoothing Polyhedra • 4-valent points. On this mesh a surface formed as a linear combination of the shifts of the 4-direction box spline, called the Zwart-Powell element [Zwart 1973; Powell 1969] , is defined by the following subdivision process (c.f. Boor et al. [1994] and Prautzsch [1984] ).
At each step replicate each coefficient with index (i, j) in a new array at positions (2i, 2j), (2i ϩ 1, 2j), (2i, 2j ϩ 1), and (2i ϩ 1, 2j ϩ 1). Then average in the new array first all entries i, j with i ϩ 1, j ϩ 1 and then all entries i, j with i Ϫ 1, j ϩ 1. Figure 2 shows the result of the averaging process: for each quadrilateral each of four new points is obtained by taking 1 ⁄2 of one point and 1 ⁄4 of each of its two neighbors. PROOF. Two steps of the midedge subdivision equal one step of the 4-direction box-spline subdivision. (see also Sabin [1986, p. 280] ). e Since we know the limit surface for regular mesh regions, in the following we always combine two steps of midedge subdivision and refer to it as a double-step. The double-step rule is efficiently represented by the mask 1/4 1/ 2 1/4 which applies to a vertex and its two neighbors in the same facet. In contrast to the Doo-Sabin and other subdivision masks, the (double) midedge subdivision mask is not parametrized by the valence n of the particular point, but is uniform for all configurations. For later use, we note that in each coordinate any submesh of nine coefficients B ᐉ , BЈ ᐉ , BЉ, ᐉ ϭ 0..3 of the 4-direction box spline control-point mesh defines four polynomials in Bernstein-Bézier form with coefficients
The generic layout of the coefficients and the algebraic correspondence are shown in Figure 3 . In particular, if B ᐉ ϭ BЈ ᐉ ϭ 0, for ᐉ ϭ 0..3 and BЉ ϭ 1, we obtain the definition of a single 4-direction box-spline in terms of the Bernstein-Bézier form (see Figure 4 ).
SMOOTHNESS AT EXTRAORDINARY POINTS
Since each midedge subdivision double-step replaces points and edges by quadrilaterals, the new mesh at each step is regular except for a fixed number of increasingly separated non-4-sided mesh facets. We consider one 
422
• such facet (cf. Figure 5 ). At each step the polygon defining the facet contracts, converging towards the average of the points. To confirm the smoothness at this extraordinary point, we analyze the local subdivision matrix that maps k layers of old points surrounding the extraordinary point to k layers of new points. For almost all inputs, the eigenvalues and eigenvectors of the subdivision matrix determine the smoothness of the limit surface [Reif 1995] .
The conversion to the Bernstein form in the preceding section shows that three layers of control points suffice to define a complete new surface layer x m that attaches to a previous layer x mϪ1 . The union of all surface layers ഫ mʦ‫ގ‬ x m forms the midedge subdivision surface y. Each of the n segments ( j ʦ ‫ޚ‬ n ϭ {0, . . . , n Ϫ 1})
that make up the mth surface layer consists of 12 quadratic Bernstein- Smoothing Polyhedra
• Bézier patches, four corresponding to each nine-tuple of control points
The labeling used here is shown in Figure 5 . The vector of control points B m that define the mth surface layer consists of n blocks of nine elements each and the subdivision matrix A transforms PROOF. Since the scheme is symmetric (i.e., invariant under a rotation of segment labels) we can determine the eigenvalues and eigenvectors conveniently with the help of the discrete Fourier transform. Let I be the identity matrix, and W the diagonal matrix consisting of 9 ϫ 9 matrices W k defined by 
•
The transformed matrix
has the same eigenvalues as A and a block-diagonal structure Â ϭ diag(Â k ) with 9 ϫ 9 submatrices Â k , k ϭ 0, . . . , n Ϫ 1 that are nonzero only in the first four columns:
where p :ϭ 1 ⁄2, q :ϭ 1 ⁄4, and The single maximal eigenvalue 1 assures convergence to an affinely invariant surface. To verify its smoothness, it suffices to show that the eigenvectors corresponding to the two subdominant eigenvalues define a regular and injective map, namely, the characteristic map that parametrizes the tangent plane in the limit point. Since this proof is of a technical nature its details are relegated to the Appendix.
In the extreme case, setting ␥ ϭ 1 at a vertex results in a sharp point and setting ␥ ϭ 1 for the two vertices of an edge results in a sharp edge. Conversely, setting ␥ ϭ 0.5 at a point smooths maximally. The checker pattern on the objects in Figure 9 highlights individual triangles on the surfaces.
CONVERGENCE IMPROVEMENT AT IRREGULAR POINTS
The need for an improvement in the convergence of the midedge subdivision is illustrated by Figure 6 . The input data form a cylinder by extruding a 16-gon that is regular except that one of the vertices has been moved above the plane to form a peak. Convergence of the central 16-edge facet is slow. The subdominant eigenvalue ϭ (1 ϩ cos(2/16))/2 Ϸ .962 implies that the distance of a vertex to the centroid of the facet shrinks by less than 4%. Conversely the convergence at the peak is so fast that it seems pointed. This fast convergence of triangular facets is already apparent in Figure 1 
426
• where the central triangle shrinks almost to a point in just three doublesteps. To even out the speed of convergence, we modify the subdivision mask for n-sided facets to have weights
Ϫi , i ϭ 0. .n with ␣ n/ 2 ϭ 0 for n even, consistent with the regular case. Regularity and injectivity of the characteristic map (cf., Appendix) are evident from the coefficients displayed in Figure 8 . We conclude with three examples of modified midedge subdivision (see Figure 9 ). To distribute the change of normal and keep some features sharp, we parametrize the mask in the first subdivision double-step only as follows using (cf. Peters [1993] Smoothing Polyhedra
Appendix: Regularity and Injectivity of the Characteristic Map
This section completes the proof, started in Section 3, of smoothness of the limit surface at extraordinary points. 
428
• Two eigenvalues of the subdivision matrix are subdominant if they are either strictly larger in modulus than any eigenvalue other than the unique largest ␣ 0 ϭ 1 or, if equal to the fourth largest eigenvalue, their eigenspaces have a strictly higher dimension than those of any other eigenvalue of the same absolute value (c.f. Peters and Reif [1997] ). In the case of midedge subdivision the subdominant eigenvalues belong to Â 1 and Â nϪ1 and have the value with Ն 1 ⁄2 Ͼ 1 ⁄4 for n Ͼ 3 since ␣ i Ͼ ␣ j for i Ͻ j Ͻ n/ 2. If n ϭ 3, then ϭ 1 ⁄4 is an eight-fold eigenvalue but the Jordan decomposition of the matrix shows eigenspaces of multiplicity three for each of Â 1 and Â nϪ1 .
It remains to show regularity and injectivity of the characteristic map. This task is generically proportional to the size of the subdivision mask. Fortunately this is minimal for midedge subdivision. Only recently, in conjunction with the analysis of midedge subdivision, have techniques been developed to prove sharp results for generalized biquadratic and bicubic subdivision schemes [Peters and Reif 1997] . Smoothing Polyhedra
• By arranging the entries of the eigenvector according to the labeling in Figure 5 and interpreting the real part as x and the imaginary part as the y component, we obtain the box-spline control points B 0,k with coordinates x ϩ iy ϭ 6 ϩ 4c 8 ϩ 3c 10 ϩ 4c 4 ϩ 2c 6 ϩ 2c 8 ϩ 3c 2 4ϩ 2c 6 ϩ 4c ϩ is
The control points are symmetric with respect to the diagonal since midedge subdivision is invariant under reflection. The remaining control points are obtained by multiplication with n i , that is, rotation by 2/n. To further analyze the map we transform from box spline to Bernstein form. Figure 10 shows one-half of one segment of the characteristic map, namely, the Bernstein coefficients of six C 1 -connected quadratic pieces. The Jacobian consists, therefore, of six C 0 -connected quadratics. Figure 11 displays the evidently positive coefficients of the Jacobian proving that the characteristic map is regular.
To show injectivity it therefore suffices to show that the boundary of the half-segment is injective. The boundary of a half-segment consists of the images l 1 , l 2 , l 3 , and l 4 of the segments (1, 0), (2, 0), (2, 0), (2, 2), (2, 2), (1, 1), and (1, 1), (1, 0) under the characteristic map. Both l 1 and l 3 are regular line segments along the x-axis and the ray with slope (1 ϩ c, Ϫs), respectively, whereas l 2 is a Ϫ1 -scaled subdivided copy of the regular parabolic segment l 4 . Regular parabolas do not self-intersect. Hence we need only check for pairwise intersections of the boundary curves. Since all other segments are confined to the negative y-halfplane l 3 does not intersect them. Since the middle coefficient of l 4 lies on the ray (3(1 ϩ c), Ϫs) through the origin between the rays of l 1 and l 3 neither l 2 nor l 4 can intersect either l 1 or l 3 . Lastly, l 2 and l 4 do not intersect because 1. e

{'paper_id': '4512405', 'title': 'The simplest subdivision scheme for smoothing polyhedra', 's2_url': 'https://api.semanticscholar.org/CorpusID:4512405', 'source': 'S2ORC'}