The Simplest Subdivision Scheme for

Smoothing Polyhedra
JÖRG PETERS
Purdue University
and
ULRICH REIF
Universität Stuttgart

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.
Categories and Subject Descriptors: I.3.3 [Computer Graphics]: Picture/Image Generation—
display algorithms; I.3.5 [Computer Graphics]: Computational Geometry and Object Model-
ing—curve, surface, solid, and object representations; geometric algorithms, languages, and
systems
General Terms: Algorithms, Design
Additional Key Words and Phrases: Arbitrary topology, box-spline, characteristic map, sim-
plest smooth subdivision, surface

1. 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

J. Peters’ work was supported by NSF NYI grant 9457806-CCR. U. Reif’s work was supported
by BMBF Projekt 03-HO7STU-2.
Contact author’s current address: J. Peters, Department of Computer Sciences, Purdue
University, 1398 Computer Science Building, West Lafayette, IN 47907-1398; email:
^[email protected]&.
Permission to make digital / hard copy of part or all of this work for personal or classroom use
is granted without fee provided that the copies are not made or distributed for profit or
commercial advantage, the copyright notice, the title of the publication, and its date appear,
and notice is given that copying is by permission of the ACM, Inc. To copy otherwise, to
republish, to post on servers, or to redistribute to lists, requires prior specific permission
and / or a fee.
© 1997 ACM 0730-0301/97/1000 –0420 $03.50
ACM Transactions on Graphics, Vol. 16, No. 4, October 1997, Pages 420 –431.
 Smoothing Polyhedra • 421

Fig. 1. Midpoint subdivision at work.

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].

2. 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
ACM Transactions on Graphics, Vol. 16, No. 4, October 1997.
422 • J. Peters and U. Reif

Fig. 2. Four-direction box spline subdivision.

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 1, 2j), (2i, 2j 1 1), and (2i 1 1, 2j 1 1). Then
average in the new array first all entries i, j with i 1 1, j 1 1 and then all
entries i, j with i 2 1, j 1 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.

THEOREM 1. On a regular mesh, midedge subdivision converges to a

surface parametrized by shifts of the 4-direction box-spline.
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/4
1/ 2

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) mid-
edge subdivision mask is not parametrized by the valence n of the particu-
lar point, but is uniform for all configurations.
For later use, we note that in each coordinate any submesh of nine
coefficients B , , B9, , B0, , 5 0..3 of the 4-direction box spline control-point
mesh defines four polynomials in Bernstein-Bézier form with coefficients
b ,ijk , i 1 j 1 k 5 2, , 5 0..3. The generic layout of the coefficients and the
algebraic correspondence are shown in Figure 3. In particular, if B , 5 B9,
5 0, for , 5 0..3 and B0 5 1, we obtain the definition of a single 4-direction
box-spline in terms of the Bernstein-Bézier form (see Figure 4).

3. 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
ACM Transactions on Graphics, Vol. 16, No. 4, October 1997.
 Smoothing Polyhedra • 423

Fig. 3. Correspondence of box spline coefficients with Bernstein-Bézier coefficients.

Fig. 4. Bernstein-Bézier coefficients and graph of the four-direction box spline.

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
xm that attaches to a previous layer xm21 . The union of all surface layers
ø m[N xm forms the midedge subdivision surface y. Each of the n segments
( j [ Z n 5 {0, . . . , n 2 1})

x jm : @ 0, 2 # 2\ @ 0, 1 ! 2 3 R 3

that make up the mth surface layer consists of 12 quadratic Bernstein-

ACM Transactions on Graphics, Vol. 16, No. 4, October 1997.
424 • J. Peters and U. Reif

Fig. 5. Union of surface layers at an extraordinary point and labeling of control points.

Bézier patches, four corresponding to each nine-tuple of control points

m , k 5 1 : 9,
B j,k

m , k 5 1 : 4, 8, 9,
B j,k B j11,k
m , k 5 1, 2, 5,

m , k 5 1 : 6,
B j,k B j21,k
m , k 5 1, 4, 9.
The labeling used here is shown in Figure 5. The vector of control points
Bm that define the mth surface layer consists of n blocks of nine elements
each and the subdivision matrix A transforms

B m11 5 AB m 5 A m11B 0 .
LEMMA 3.1 The eigenvalues of the subdivision matrix A are real-valued
and form a decreasing sequence starting with

1 1 cos ~ 2 p /n !
1, l , l , where l :5 .
2
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 3 9 matrices W k
defined by

W 5 diag ~ W k! , W k :5 v knI 939 , v n :5 exp SÎ 21

2p
n
D .
ACM Transactions on Graphics, Vol. 16, No. 4, October 1997.
 Smoothing Polyhedra • 425

Fig. 6. Fast convergence of the midedge subdivision for three-sided facets and slow conver-
gence for large facets.

The transformed matrix

 5 W 21AW,

has the same eigenvalues as A and a block-diagonal structure  5 diag( k )

with 9 3 9 submatrices  k , k 5 0, . . . , n 2 1 that are nonzero only in the
first four columns:

1 2
â k 0 0 0
p 1 v# nq q 0 0
p q 0 q
p 1 v nq 0 0 q
 k~ 1 : 4, : ! 5 q p 0 v# nq , (3.1)
q p q 0
0 q p q
q 0 q p
q v nq 0 p

where p :5 1 ⁄ 2 , q :5 1 ⁄ 4 , and

O v a 5 1 1 cos~2k ~ 2 p /n !! .
n21

â k 5 ik
n i
i50

ACM Transactions on Graphics, Vol. 16, No. 4, October 1997.

426 • J. Peters and U. Reif

Fig. 7. Balanced convergence of the modified midedge subdivision.

Evidently the nine eigenvalues of each submatrix  k are

1 1
â k , , , 0, 0, 0, 0, 0, 0
4 4

and the combined list of eigenvalues of all submatrices ordered by decreas-

ing modulus starts with the eigenvalues â0 5 1, â1 5 â n21 5 l as claimed.
e
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 parame-
trizes the tangent plane in the limit point. Since this proof is of a technical
nature its details are relegated to the Appendix.

4. CONVERGENCE IMPROVEMENT AT IRREGULAR POINTS

The need for an improvement in the convergence of the midedge subdivi-
sion 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 l 5 (1 1 cos(2p/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
ACM Transactions on Graphics, Vol. 16, No. 4, October 1997.
 Smoothing Polyhedra • 427

where the central triangle shrinks almost to a point in just three double-
steps.
To even out the speed of convergence, we modify the subdivision mask for
n-sided facets to have weights

aj 5 2 O2
n#

i50
2i
S D
cos ji
2p
n
where n# :5
 
n21
2

resulting in eigenvalues

â i 5 â n2i 5 2 2i, i 5 0. .n#

with â n/ 2 5 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]): g[[0.5, 1].

12g
2
12g
g
2

Fig. 8. Characteristic map (left) and its scaled Jacobian (right).

ACM Transactions on Graphics, Vol. 16, No. 4, October 1997.

428 • J. Peters and U. Reif

Fig. 9. Modified midedge subdivision.

Fig. 10. Characteristic map of midedge subdivision.

In the extreme case, setting g 5 1 at a vertex results in a sharp point and

setting g 5 1 for the two vertices of an edge results in a sharp edge.
Conversely, setting g 5 0.5 at a point smooths maximally. The checker pattern
on the objects in Figure 9 highlights individual triangles on the surfaces.

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.
ACM Transactions on Graphics, Vol. 16, No. 4, October 1997.
 Smoothing Polyhedra • 429

Fig. 11. Scaled Jacobian of the characteristic map of midedge subdivision.

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 5 1 or, if equal to the fourth largest eigenvalue, their eigen-
spaces 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  n21
and have the value l with l $ 1⁄2 . 1⁄4 for n . 3 since a i . aj for i , j ,
n/ 2. If n 5 3, then l 5 1⁄4 is an eight-fold eigenvalue but the Jordan
decomposition of the matrix shows eigenspaces of multiplicity three for
each of  1 and  n21 .
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].
LEMMA 4.1 The characteristic map of midedge subdivision is regular and
injective.
PROOF. The eigenvector corresponding to the subdominant eigenvalues
l is

1 2 12
2 0
4 1 2c 22
6 1 2c 0
S D
1 2
v 0nv 2p
4 1 2c 2 c :5 cos
v 1nv n

S D
v l :5 · where v :5 6 1 4c 1 is 24 , .
· 2p
· 8 1 3c 22 s :5 sin
v n21
n v n
10 1 4c 0
8 1 3c 2
6 1 4c 4
ACM Transactions on Graphics, Vol. 16, No. 4, October 1997.
430 • J. Peters and U. Reif

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 B0,k with coordinates

1 2 1 2
6 1 4c 8 1 3c 10 1 4c 4 2 0
x 1 iy 5 4 1 2c 6 1 2c 8 1 3c 1 is 2 0 22 .
2 4 1 2c 6 1 4c 0 22 24

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 v in , that is, rotation by 2 p /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 Jaco-
bian consists, therefore, of six C 0 -connected quadratics. Figure 11 displays
the evidently positive coefficients of the Jacobian proving that the charac-
teristic 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 1 c, 2s),
respectively, whereas l 2 is a l21-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 inter-
sect them. Since the middle coefficient of l 4 lies on the ray (3(1 1 c), 2s)
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 l Þ 1. e

REFERENCES

BOOR, C. D., HÖLLIG, K., AND RIEMENSCHNEIDER, S. 1994. Box Splines. Springer Verlag, New
York, NY.
CATMULL, E. AND CLARK, J. 1978. Recursively generated B-spline surfaces on arbitrary
topological meshes. Comput. Aided Des. 10, 350 –355.
DOO, D. AND SABIN, M. A. 1978. Behaviour of recursive subdivision surfaces near extraordi-
nary points. Comput. Aided Des. 10, 356 –360.
LOOP, C. 1987. Smooth subdivision for surfaces based on triangles. Master’s thesis, Univer-
sity of Utah.
PETERS, J. 1993. Smooth free-form surfaces over irregular meshes generalizing quadratic
splines. Comput. Aided Geom. Des. 10, 347–361.
PETERS, J. AND REIF, U. 1997. Analysis of generalized B-spline subdivision algorithms.
SIAM J. Numer. Anal. (to appear).
POWELL, M. 1969. Piecewise quadratic surface fitting for contour plotting. In Software for
Numerical Mathematics, D. Evans, Ed., Academic Press, Boston, MA.
PRAUTZSCH, H. 1984. Unterteilungsalgorithmen für multivariante Splines. Ph.D. thesis,
Tech. Universität Braunschweig.

ACM Transactions on Graphics, Vol. 16, No. 4, October 1997.

 Smoothing Polyhedra • 431

REIF, U. 1995. A unified approach to subdivision algorithms near extraordinary vertices.

Comput. Aided Geom. Des. 12, 153–174.
SABIN, M. 1986. Recursive subdivision. In The Mathematics of Surfaces, Clarendon Press,
Oxford, England, 269 –282.
ZWART, P. 1973. Multivariate splines with non-degenerate partitions. SIAM J. Numer.
Anal. 10, 665– 673.

Received June 1996; revised January 1997; accepted February 1997

ACM Transactions on Graphics, Vol. 16, No. 4, October 1997.