Analysis of Algorithms Generalizing B-Spline Subdivision.
A new set of tools for verifying smoothness of surfaces generated by stationary subdivision algorithms is presented. The main challenge here is the verification of injectivity of the characteristic map. The tools are sufficiently versatile and easy to wield to allow, as an application, a full analysis of algorithms generalizing biquadratic and bicubic B-spline subdivision. In the case of generalized biquadratic subdivision the analysis yields a hitherto unknown sharp bound strictly less than 1 on the second largest eigenvalue of any smoothly converging subdivision.
Introduction
The idea of generating smooth free-form surfaces of arbitrary topology by iterated mesh
refinement dates back to 1978, when two papers [CC78], [DS78] appeared back to back in
the same issue of Computer Aided Design. Named after their inventors, the Doo-Sabin
and the Catmull-Clark algorithm represent generalizations of the subdivision schemes for
biquadratic and bicubic B-splines, respectively. By combining a construction principle
of striking simplicity with high fairness of the generated surfaces, both algorithms have
since become standard tools in Computer Aided Geometric Design. However, despite
a number of attempts [DS78], [BS86], [BS88], the convergence to smooth limit surfaces
could not be proven rigorously so far.
NSF National Young Investigator Award 9457806-CCR
y BMBF Projekt 03-HO7STU-2
The proof techniques and actual proofs to be presented here are based on the concept
of the characteristic map as introduced in [Rei95a]. The characteristic map is a smooth
map from some compact domain U to R 2 which can be assigned to stationary linear
subdivision schemes. It depends only on the structure of the algorithm and not on the
data. If this map is both regular and injective, then the corresponding algorithm generates
surfaces. It is shown in this paper that on the other hand non-injectivity
at an interior point of the map implies non-smoothness of the limit surfaces. Further, we
establish two sufficient conditions for regularity and injectivity of the characteristic map
which allow a straightforward verification. The stronger one, however still applicable
in many cases, only requires the sign of one partial derivative of one segment of the
characteristic map to be positive.
A careful analysis of the Doo-Sabin and the Catmull Clark algorithm yields the
following results:
ffl The Doo-Sabin algorithm in its general form uses weights
for computing a new n-gon from an old one. Affine invariance and symmetry,
i.e.
imply that the discrete Fourier
transform of ff is real and of the form -
ff 1 is
greater in modulus than the other entries except for 1 and if
for certain values - then the limit surface is smooth. The bound - max (n)
can be computed explicitly, see Table 1. If 1 ? - max (n), then the limit is a
continuous, yet non-smooth surface.
ffl In particular, the Doo-Sabin algorithm in its original form (5.1) complies with the
conditions, hence generates smooth limit surfaces.
ffl The Catmull-Clark algorithm in its general form uses three weights ff; fi; fl summing
up to one for computing the new location of an extraordinary vertex from
its predecessor and the centers of its neighbors. Iffi fi fi fi
with c n := cos(2-=n), then the limit surface is smooth. If one of the two values
on the left hand side exceeds the right hand side, then the limit surface is not
smooth.
ffl In particular, the Catmull-Clark algorithm in its original form (6.2) complies with
the conditions and generates smooth limit surfaces.
Generalized subdivision and the characteristic map
In this section we briefly outline the results of subdivision analysis as developed in
[Rei95a], and establish a new necessary condition for C 1 -subdivision schemes.
Generalized B-spline subdivision generates a sequence Cm of finer and finer control
polyhedra converging to some limit surface y. On the regular part of the mesh, standard
B-spline subdivision is used for refinement, whereas special rules apply near extraordinary
mesh points. Since all subdivision masks considered here are of fixed finite size,
we can restrict ourselves to analyzing meshes with a single extraordinary mesh point of
valence 4. The regular parts of the control polygons Cm correspond to B-spline
surfaces ym which form an ascending sequence
converging to the limit surface,
With the prolongation of ym defined by
xm := closure (ym+1nym
the limit surface is the essentially disjoint 1 union
The xm are ring-shaped surface layers which can be parametrized conveniently over a
common domain U \Theta Z n ; Z n := Z mod n, consisting of n copies of the compact set
see

Figure

1. Each surface layer xm can be parametrized in terms of control points
polynomial functions N ' according to
Without loss of generality, we may assume that the functions N ' are linearly inde-
pendent. Otherwise, the setup can be reduced without altering the properties of the
scheme. The n parts x 0
forming xm are referred to as segments. Collecting
1 The intersection consists exclusively of points on the common boundary curve, which are identified.
uvU
x

Figure

1: Domain U (left) and structure of surface layers xm (right).
the functions N ' in the columns of a row matrix N and the control points in the rows
of a column matrix Bm yields the vector notation
xm (u; v;
The schemes to be considered here are linear and stationary, i.e. there exists a square
subdivision matrix A with
Definition 2.1 Let the eigenvalues - of A be ordered by modulus,
and denote by / the corresponding generalized real eigenvectors. If
then the characteristic map of the subdivision algorithm is defined by
or in complex form by
Following (2.7), the segments \Psi j and \Psi j
of the characteristic map are the restriction of
\Psi and \Psi   to U \Theta j, respectively.

Figure

2: Injective (left) and non-injective (right) characteristic map
Remark is a (L+ 1) \Theta 2-matrix. Its rows play the role of 2D control points.
ii) Throughout, the subscript   will indicate that we refer to the complexification of
a two-dimensional real variable or function. We will switch between complex and real
representation without further notice.
On the left hand side, Figure 2 shows a typical example of a characteristic map for
obtained for example by the Doo-Sabin algorithm. In order to guarantee affine
invariance of the algorithm, the rows of A must sum to 1. Thus,
an eigenvector of A to the eigenvalue 1. The following theorem establishes a sufficient
condition for subdivision algorithms to generate smooth limit surfaces.
Theorem 2.1 If - is a real eigenvalue with geometric
multiplicity 2, and if the characteristic map is regular and injective, then the limit surface
y is a regular C 1 -manifold for almost every choice of initial data B 0 .
A proof of this theorem can be found in [Rei95a]. Generalizations, though not required
here, are provided in [Rei95b] and [PR97]. Subsequently, it will be assumed that the
eigenvalues of A satisfy the assumptions of Theorem 2.1, and - will be referred to as
the subdominant eigenvalue.
The following theorem states a necessary condition for the convergence of a subdivision
scheme to smooth limit surfaces.
Theorem 2.2 If the characteristic map of a subdivision scheme is non-injective, i.e.
there exist (u; v;
and if \Psi(u; v; j) is an interior point of \Psi(U; Z n ), then the limit surface y is not a regular
-manifold for almost every choice of initial data B 0 .
Proof Choose an "-neighborhood
Then there exist neighborhoods V and V 0 of (u; v; respectively, with
\Psi is a continuous map sufficiently close to \Psi, i.e.
\Psi is also not injective. Now, express Bm
in terms of the generalized eigenvectors / ' ,
Then for almost every choice of initial data B 0 , the coefficients b 1 and b 2 are linearly
independent, and we can choose coordinates such that b is the origin and b
are the first two unit vectors. A rescaling of the surface layers yields
Now, assume that y is a regular C 1 -manifold. Then the latter equation implies that the
tangent plane at the origin is the xy-plane. The projection ~
/m of ~ xm on the xy-plane
is converging to \Psi, so ~
/m is non-injective for m sufficiently large. Consequently, the
projection of the layers xm to the xy-plane are non-injective near the origin for almost
all m. This contradicts the assumption since the projection of a regular C 1 -manifold on
its tangent plane is locally injective. 2
Finally, we state two basic properties of characteristic maps. The first one is derived
from the fact that \Psi and smoothly,
The second one expresses continuity between segments,
3 Symmetry and Fourier Analysis
This section examines the special structure of the characteristic map for subdivision
schemes obeying generic symmetry assumptions, namely that subdivision is independent
of the particular labeling of control points used for refining the control mesh. According
to the split of xm into n segments, the vectors Bm of control points can be divided into
equally structured blocks,
and A is partitioned into n \Theta n square blocks A j;j 0
Definition 3.1 A subdivision algorithm is called symmetric if it is invariant both under
a shift S and a reflection R of the labeling of the vector Bm of control points. S and R
are permutation matrices characterized by
Symmetry of the subdivision algorithm means that the subdivision matrix A commutes
both with R and S, i.e.
the segments of S and E the identity matrix of the same size as S j;j 0
, the
shift matrix S is given by
Comparison of SA and AS shows that the subdivision matrix of a symmetric scheme is
block-cyclic, i.e.
Thus, (2.8) becomes
With
define the discrete Fourier transform by
is an n-vector in the generalized sense that its entries p j can
be either scalars, or vectors, or matrices. It will always become clear from the context,
what is meant. Applying the discrete Fourier transform to (3.7) yields
see [Lip81] for a comprehensive introduction to the Fourier analysis of cyclic systems.
Theorem 3.1 The characteristic map for a symmetric scheme is non-injective unless
the subdominant eigenvalue - is an eigenvalue of -
A 1 and -
A
Proof - is an eigenvalue of A if and only if it is an eigenvalue of -
A k for some k 2
1g. If - is an eigenvalue of -
A k then it is also an eigenvalue of -
A n\Gammak since A
is real and -
A k . Let -
/, then
is a complex eigenvector of A. Consequently, the segments \Psi j
of the complex characteristic
map satisfy
Now, the winding number of the closed curve
is either k or the curve ff   has self-intersections implying
that \Psi   is not injective. 2
The effect of the subdominant eigenvalue - stemming from the wrong Fourier component
is depicted in Figure 2 on the right hand side. It shows the non-injective characteristic
map for the Doo-Sabin algorithm for weights chosen such that - is an
eigenvalue of -
A 2 and -
A 4 . As a consequence of Theorem 3.1, it will be assumed that - is
an eigenvalue of -
A 1 and -
A n\Gamma1 from now on. So, (3.12) becomes
The following lemma is the key to reducing the analysis of the characteristic map \Psi to
the examination of a single segment, say \Psi . \Psi is called normalized if -
/ is scaled such
that \Psi 0 (2; that normalization is always possible if \Psi is
injective since then \Psi 0 (2;
Lemma 3.1 If \Psi   is a normalized characteristic map of a symmetric scheme, then
and in particular
Proof (3.2) and (3.3) yield N(u; v; j)S implying that
S
since the functions forming N are assumed to be linearly independent. From (3.4) one
concludes that R/   is an eigenvector of A to the eigenvalue -, i.e. it can be written as
R/
On using S/  one obtains from the latter two equations
Since /   and /   are linearly independent, this implies a = 0, hence R/  . In order
to determine b, consider \Psi
(2; 2). By (3.3),
thus Finally, we obtain
Conditions for regularity and injectivity
In this section we derive a sequence of lemmas resulting in two sufficient conditions for
the regularity and injectivity of the characteristic map that can be verified efficiently.
Throughout, it will be assumed that \Psi is a normalized characteristic map of a symmetric
subdivision scheme.
The first lemma states that for regular functions injectivity is equivalent to injectivity
at the boundary.
Lemma 4.1 Denote by @U the boundary of U and by \Psi 0
@ the restriction of \Psi 0 to @U .
If
then \Psi 0 is injective if and only if \Psi 0
@ is injective.
Proof Assume that \Psi 0 is regular and \Psi 0
@ is injective. By the Inverse Function Theorem
(IFT), points in the interior
U of U are mapped to points in the interior of \Psi 0 (U ), i.e.
Define the function - assigning the number of pre-images to the points in \Psi 0 (U ),
Injectivity of \Psi 0
@ and (4.2) imply -(@ \Psi 0 1. - is upper semi-continuous by the
IFT, hence -(\Psi 0
The second lemma gives a sufficient condition for \Psi 0
(U) being located in a sector of
angle 2-=n in the complex plane.
Lemma 4.2 If \Psi 0 is regular and
for all t 2 [0; 1], then
for all (u; v) 2 U .
Proof By Lemma 3.1, we have
and in particular \Psi 0
then p 2 is monotonically increasing because \Psi 0
we obtain for t 2 [1; 2]
This implies either arg \Psi 0
-=n. The second case
contradicts (4.7), thus
-=n







Figure

3: Curves p 1
.
This means that \Psi 0 (t; 0) is a part of the straight half line
monotonically increasing in both real and imaginary part, it has no
intersections with h except for p   (0), hence
Using the scaling property (2.15) and symmetry with respect to the real axis, the latter
two inequations imply that (4.5) holds for all (u; v) 2 @U . By the IFT, we have
is compact, this
implies \Gamma-=n - arg \Psi 0 (U) -=n as asserted. 2
The third lemma provides a condition on the partial derivatives of \Psi 0 that implies
injectivity.
Lemma 4.3 If \Psi 0 is regular and \Psi 0
Proof By Lemma 4.1 it suffices to show that the restriction \Psi 0
@ of \Psi 0 to the boundary
of U is injective. Let
(2t;
for t 2 [0; 1], see Figure 3. Then
with defined as in the proof of Lemma 4.2. p 2
and p 5
do not intersect since
by (4.9). Both curves also do not have self-intersections since they are parametrized
regularly and parts of straight lines. Next, we show that arg p   (t) is monotonically
increasing in t. By (4.7) and (4.9),
By assumption, p 1 and p 2 are monotone increasing, thus This implies
d
dt
as claimed. Monotonicity of arg p  6 has the following
consequences: First, it guarantees that p 1
do not have self-intersections.
Second, it excludes intersections of p 1
and p 3
since
Analogously, p 4
and
are disjoint. Third, the only intersections of p 1
and p 3
with
are
and analogously for p 4
. Fourth, the only intersections of p 1
and p 4

are
and the proof is complete. 2
The following theorem establishes a sufficient condition on the partial derivatives of \Psi 0
that guarantees regularity and injectivity of the characteristic map. Its usefulness is due
to the fact that it requires only estimates for the partial derivatives of the single segment
\Psi 0 . Since for generalized B-spline subdivision schemes the functions in questions are
piecewise polynomial, the condition can be verified numerically or even analytically
using B-spline representations and the convex hull property.
Theorem 4.1 If \Psi 0 is regular and \Psi 0
then the characteristic
map \Psi is regular and injective.

Figure

4: Mesh refinement by the Doo-Sabin algorithm.
Proof By Lemma 4.3, \Psi 0 is regular and injective. (3.14) says that \Psi j is obtained from
\Psi 0 by a 2-j=n-rotation about the origin. So, each \Psi is regular and injective.
Further, the segments \Psi j do not overlap since Lemma 4.2 yields
(4.22)The assumptions of the following Corollary are stronger than those of Theorem 4.1, but
can be verified with less effort since no products of partial derivatives are involved in
verifying that \Psi 0 is regular.
Corollary 4.1 If \Psi 0
then the characteristic
map \Psi is regular and injective.
Proof The symmetry relation (4.6) yields
so the determinant J 0 is positive if \Psi 0
5 The Doo-Sabin algorithm
5.1 Algorithm
The Doo-Sabin algorithm is a generalization of the subdivision scheme for biquadratic
tensor product B-splines. For each n-gon of the original mesh, a new, smaller n-gon
is created and connected suitably with its neighbors, see Figure 4. Figure 5 shows the
ff n\Gamma2
ff

Figure

5: Masks for the Doo-Sabin algorithm.
mask for generating a new n-gon from an old one for the regular case
the general case (right). The weights suggested by Doo and Sabin in [DS78] are
Below we analyze more general schemes assuming beforehand nothing but affine invariance
and symmetry,
5.2 Characteristic map
Each of the n segments x j
of the surface layers generated by the Doo-Sabin
algorithm consists of 3 biquadratic B-spline patches. Accordingly, the n blocks
forming the vector of control points Bm consist of 9 elements, each. The labeling is
shown in Figure 6. The 9 \Theta 9-matrices -
introduced in (3.10) have the
following structure,
A k =B @

Figure

Labeling of control points for the Doo-Sabin algorithm
1=16, the sub-matrices are given by
r
r q p
The matrix A k
1;1 has eigenvalues 1=4; 1=8; 1=16, hence each of them is an n-fold eigenvalue
of the subdivision matrix A. Further, A has a 5n-fold eigenvalue 0 stemming from the
5 \Theta 5-zero submatrix of -
A k . Due to their high multiplicity, these eigenvalues cannot
be playing the role of the subdominant eigenvalue -. The only eigenvalues left are the
upper left entries -
A k obtained by applying the discrete Fourier transform
to the vector (ff of weights for the n-gon. Since the ff j sum up to 1, we have
1. Due to symmetry, the remaining eigenvalues are real and occur in pairs
according to -
ff n\Gammak
. From the theory developed in the preceding sections we know
that
ff
must satisfy
ff n\Gamma2
The eigenvector of the matrix -
A 1 corresponding to - is
Note that the characteristic map depends only on - and n. That is, all masks ff with
identical first Fourier component yield the same characteristic map.
5.3 Verification
We start with briefly discussing the case as obtained in particular for the
weights in (5.1). Rearranging the entries of the eigenvector /   in the more convenient
matrix form for tensor product B-spline coefficients, see Figure 6, yields
The segment \Psi 0
of the characteristic map consists of three bi-quadratic patches, which
can be expressed in Bernstein-B'ezier form with the following coefficients,2

28 s n
28
\Gamma7 s n
\Gamma7 s n
\Gamma14 s n
\Gamma7 s n
28
\Gamma14 s n
\Gamma14 s n
28 28 c n
\Gamma28 s n (5.9)
Computing the partial derivative \Psi 0
2;v with respect to v yields three
quadratic-linear patches with coefficients2
Both the real and the imaginary part of the coefficients are positive. So, by the convex
hull property and Corollary 4.1 the algorithm is verified to generate smooth limit
surfaces.
The situation for general - is more subtle, in particular as - ! 1. First, Corollary 4.1
turns out to be insufficient. Second, there exists a limit value - depending
on n such that even the assumptions of Theorem 4.1 are not fulfilled for 1
- max . It will be shown in the next subsection that this is due to an actual loss of
smoothness as - passes the bound. All formulas required here were derived using a
computer algebra system. They are partially rather lengthy and will not be stated
explicitly unless necessary. Rather, we depict the crucial results graphically.
In order to apply Theorem 4.1, we have to compute J 0 , i.e. the determinant of the
Jacobian of \Psi 0 . J 0 is a continuous, piecewise bi-cubic function over U which can be
expressed in Bernstein-B'ezier form with 3 \Theta 16 coefficients J 0
depending
on n and -. Explicit calculation shows that all coefficients J 0
- are of the form
with polynomials of degree - 6 in -. We give the coefficient corresponding to
The polynomials P 1 and Q 1 are
In order to apply analytic tools, it is convenient to consider c n as a free variable varying
in the interval c n 2 [\Gamma1=2; 1], which covers all possible values obtained for n - 3. For
fixed there is at most one value ~ c n where J 0
- changes sign,

Figure

7: Feasible set   and functions R -).

Figure

7 shows a plot of all these functions as well as a magnification of the significant
region. From the analysis of the case we know that J 0
Thus, J 0 is positive as long as (-; c n ) lies in the shaded region, which is bounded by
precisely, the feasible set for (-; c n ) providing positivity of J 0 is
For the verification of the assumptions of Theorem 4.1 it remains to show that \Psi 0
. Note that both functions are linear in t. So,
it suffices to check positivity for t 2 f0; 1g, which follows immediately from
Finally, we summarize the results derived in this section.
Theorem 5.1 Let ff 0
n be symmetric weights for the Doo-Sabin algorithm. If
ff
ff n\Gamma2
then the limit surface y is a regular C 1 -manifold for almost every choice of initial data

Figure

8: Characteristic map for
5.4 Failure beyond the bound
In contrast to the lower bound - ? 1=4, which appears naturally, the existence of an
upper bound for - may come as a surprise. It is not an artifact of the particular type of
sufficient conditions in Theorem 4.1, but a sharp bound beyond which the Doo-Sabin
algorithm provably fails. If J 0
Consider the curve [g 1 (t); g 2 (t)] := \Psi 0 (t; t). Symmetry with respect to the x-axis implies
For the first component we obtain
hence for each sufficiently small " ? 0 there exists an "
This implies the non-injectivity of the characteristic map \Psi,
Moreover, for " sufficiently small, J 0 (1+ "; 1+ ") ! 0 by continuity. So, \Psi 0 (1+ "; 1+ ") is
an interior point of \Psi(U; Z n ) by the IFT, and the assumptions of Theorem 2.2 are fulfilled
proving sharpness of the bound. Figure 8 shows a magnification of the characteristic map
in the vicinity of \Psi 0 (1; 1) for (right). The latter
case corresponds to weights ff layers of a subdivision

Figure

9: Non-smooth surface generated by the Doo-Sabin algorithm with
surface generated by these weights are shown in Figure 9. The magnification on the right
hand side is non-proportional, i.e. the 'height' of the surface has been expanded in order
to depict its wavy shape. We conclude the discussion of the Doo-Sabin algorithm with
a brief description of the qualitative and quantitative behavior of - max (n). As n !1,
increasing monotonically towards 1. The asymptotic behavior for large n is
The lowest bound occurs for namely
cos
arctan

Table

1 lists the values of - max for
6 The Catmull-Clark algorithm
6.1 Algorithm
The Catmull-Clark algorithm is a generalization of the subdivision scheme for bicubic
tensor product B-splines. Each n-gon of the original mesh is subdivided into n quadrilaterals
thus generating a purely quadrilateral mesh after the first step. There are three
masks for subdividing such a mesh, namely one for computing a new centroid, one for
9 0.9829902941

Table

1: Values of the bound - max (n) for

Figure

10: Mesh refinement by the Catmull-Clark algorithm.
1=4
1=4
1=4
1=4
1=32
fi=n
fl=n
fi=n
fl=n
fi=n
fl=n
fi=n
fl=n
fi=n
fl=n

Figure

11: Masks for the Catmull-Clark algorithm.

Figure

12: Labeling of control points for the Catmull-Clark algorithm.
a new edge point, and one for the new location of a former vertex, see Figure 11. So,
the variables at our disposal are the weights
In [CC78], Catmull and Clark suggest
6.2 Characteristic map
Each of the n segments x j
of the surface layers generated by the Catmull-Clark
algorithm consists of 3 bicubic B-spline patches. Accordingly, the n blocks
forming
the vector of control points Bm consist of 13 elements, each. The labeling used here is
shown in Figure 12. Note that the centroid
is replaced by n identical copies in order to achieve the desired periodic structure. For
all masks involving Mm we substitute
Mm =n
The 13 \Theta 13-matrices -
turn out to have the following structure,
With
the sub-matrices are given by
The eigenvalues 1=8; 1=16; 1=32; 1=64 of the sub-matrix -
are n-fold eigenvalues of A.
Other non-zero eigenvalues come only from -
0;0 . For we obtain the obligatory
eigenvalue letting
which might be either both real or complex conjugate. For k 6= 0, the non-zero eigen-values
of -
are
where c n;k := cos(2-k=n). Let
then straightforward calculus shows that for all n
Consequently, - is subdominant if ff; fi; fl are chosen such that
In particular, this inequality holds for the original weights of Catmull-Clark (6.2), as
can be verified by inspection. A characterization of feasible positive weights can be
found in [BS88] 2 . For computing the characteristic map, the eigenvector -
/ of -
A 1 is
partitioned into three blocks, -
according to the special structure of -
A 1 .
/ is equivalent to
/ can be computed conveniently starting from
which solves the first eigenvector equation. Note that the characteristic map depends
only on n, and not on the particular choice of weights ff; fi; fl provided that (6.11) holds.
6.3 Verification
Corollary 4.1 is sufficient for verifying the algorithm. One proceeds as follows:
1. For given n - 3, compute the subdominant eigenvalue - according to (6.11) and
the corresponding eigenvector -
/ according to (6.15).
2. Express the three patches of the segment \Psi 0 of the characteristic map in Bernstein-
B'ezier form.
3. Compute the forward differences of B'ezier coefficients corresponding
to the partial derivative with respect to v.
4. If all are positive in both components, then by the convex hull
property of the Bernstein-B'ezier form the assumptions of Corollary 4.1 are fulfilled
and the characteristic map is regular and injective.
2 The result in the reference is incorrect for yielding complex eigenvalues - 0

Figure

13: B'ezier coefficients of the partial derivatives \Delta - .
This procedure can be run on a computer algebra system, but the resulting expressions
are rather lengthy, and discussing them is not very instructive. A numerical treatment is
more convenient and yields equally reliable results since only a finite number of quantities
has to be checked for sign. The findings are summarized on Figure 13. The left and
right hand side correspond to the two components of \Delta - . The top row shows the values
of all \Delta - for 20. The bottom row shows the minimum of the \Delta - on a doubly-
logarithmic scale for should cover most cases of practical
relevance. The positivity of all differences is evident. By Corollary 4.1, this proves
smooth convergence of the Catmull-Clark algorithm provided that the inequality (6.14)
holds.



--R

A matrix approach to the analysis of recursively generated b-spline surfaces
Conditions for tangent plane continuity over recursively generated b-spline surfaces
Recursively generated B-spline surfaces on arbitrary topological meshes
Behaviour of recursive subdivision surfaces near extraordinary points
Elements of algebra and algebraic computing
Necessary conditions for subdivision surfaces
A unified approach to sudivision algorithms near extraordinary ver- tices
Some new results on subdivision algorithms for meshes of arbitrary topology
--TR

--CTR
Jorg Peters, Smooth patching of refined triangulations, ACM Transactions on Graphics (TOG), v.20 n.1, p.1-9, Jan. 2001
Jos Stam, Exact evaluation of Catmull-Clark subdivision surfaces at arbitrary parameter values, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.395-404, July 1998
K. Kariauskas , J. Peters, Concentric tessellation maps and curvature continuous guided surfaces, Computer Aided Geometric Design, v.24 n.2, p.99-111, February, 2007
Jrg Peters , Ulrich Reif, Shape characterization of subdivision surfaces: basic principles, Computer Aided Geometric Design, v.21 n.6, p.585-599, July 2004
Jrg Peters , Ulrich Reif, The simplest subdivision scheme for smoothing polyhedra, ACM Transactions on Graphics (TOG), v.16 n.4, p.420-431, Oct. 1997
K. Kariauskas , Jrg Peters , U. Reif, Shape characterization of subdivision surfaces: case studies, Computer Aided Geometric Design, v.21 n.6, p.601-614, July 2004
M. K. Jena , P. Shunmugaraj , P. C. Das, A non-stationary subdivision scheme for generalizing trigonometric spline surfaces to arbitrary meshes, Computer Aided Geometric Design, v.20 n.2, p.61-77, May
Jrg Peters, Patching Catmull-Clark meshes, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.255-258, July 2000
Evelyne Vanraes , Adhemar Bultheel, A tangent subdivision scheme, ACM Transactions on Graphics (TOG), v.25 n.2, p.340-355, April 2006
I. P. Ivrissimtzis , H.-P. Seidel, Evolutions of polygons in the study of subdivision surfaces, Computing, v.72 n.1-2, p.93-103, April 2004
Barthe , Leif Kobbelt, Subdivision scheme tuning around extraordinary vertices, Computer Aided Geometric Design, v.21 n.6, p.561-583, July 2004
Henning Biermann , Adi Levin , Denis Zorin, Piecewise smooth subdivision surfaces with normal control, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.113-120, July 2000
Ioana Boier-Martin , Denis Zorin, Differentiable parameterization of Catmull-Clark subdivision surfaces, Proceedings of the 2004 Eurographics/ACM SIGGRAPH symposium on Geometry processing, July 08-10, 2004, Nice, France
Chhandomay Mandal , Hong Qin , Baba C. Vemuri, A novel FEM-based dynamic framework for subdivision surfaces, Proceedings of the fifth ACM symposium on Solid modeling and applications, p.191-202, June 08-11, 1999, Ann Arbor, Michigan, United States
Georg Umlauf, Analysis and tuning of subdivision algorithms, Proceedings of the 21st spring conference on Computer graphics, May 12-14, 2005, Budmerice, Slovakia
Yonggang Xue , Thomas P.-Y. Yu , Tom Duchamp, Jet subdivision schemes on the k-regular complex, Computer Aided Geometric Design, v.23 n.4, p.361-396, May 2006
Hong Qin , Chhandomay Mandal , Baba C. Vemuri, Dynamic Catmull-Clark Subdivision Surfaces, IEEE Transactions on Visualization and Computer Graphics, v.4 n.3, p.215-229, July 1998
Jrg Peters , Le-Jeng Shiue, Combining 4- and 3-direction subdivision, ACM Transactions on Graphics (TOG), v.23 n.4, p.980-1003, October 2004
Chhandomay Mandal , Hong Qin , Baba C. Vemuri, Dynamic Modeling of Butterfly Subdivision Surfaces, IEEE Transactions on Visualization and Computer Graphics, v.6 n.3, p.265-287, July 2000
Peter Oswald, Designing composite triangular subdivision schemes, Computer Aided Geometric Design, v.22 n.7, p.659-679, October 2005
Martin Bertram, Biorthogonal wavelets for subdivision volumes, Proceedings of the seventh ACM symposium on Solid modeling and applications, June 17-21, 2002, Saarbrcken, Germany
Charles K. Chui , Qingtang Jiang, Matrix-valued subdivision schemes for generating surfaces with extraordinary vertices, Computer Aided Geometric Design, v.23 n.5, p.419-438, July 2006
Martin Bertram , Mark A. Duchaineau , Bernd Hamann , Kenneth I. Joy, Bicubic subdivision-surface wavelets for large-scale isosurface representation and visualization, Proceedings of the conference on Visualization '00, p.389-396, October 2000, Salt Lake City, Utah, United States
Martin Bertram , Mark A. Duchaineau , Bernd Hamann , Kenneth I. Joy, Generalized B-Spline Subdivision-Surface Wavelets for Geometry Compression, IEEE Transactions on Visualization and Computer Graphics, v.10 n.3, p.326-338, May 2004
arbitrary topology;b-spline;doo-sabin algorithm;characteristic map;catmull-clark algorithm;subdivision