中国科学技术大学：Non-Uniform Recursive Doo-Sabin Surfaces

Non-Uniform Recursive Doo-Sabin Surfaces Doo-Sabin NURDS,Limit point ule h Doo-Sabin es to meshe 199.Sed .Limit pe kd,iBegie时C Theofpoperoll The

Non-Uniform Recursive Doo-Sabin Surfaces Zhangjin Huanga,b,c,∗ , Guoping Wangd,e aSchool of Computer Science and Technology, University of Science and Technology of China, PR China bKey Laboratory of Software in Computing and Communication, Anhui Province, PR China cUSTC-SICT Joint Laboratory on Network and Communication, PR China dKey Laboratory of Machine Perception (MOE), Peking University, PR China eSchool of Electronic Engineering and Computer Science, Peking University, PR China Abstract This paper presents a generalization of Catmull-Clark-variant Doo-Sabin surfaces and non-uniform biquadratic B-spline sur￾faces called NURDSes (Non-Uniform Recursive Doo-Sabin Surfaces). One step of NURDS refinement can be factored into one non-uniform linear subdivision step plus one dual step. Compared to the prior non-uniform Doo-Sabin surfaces (i.e., quadratic NURSSes), NURDSes are convergent for arbitrary n-sided faces. Closed form limit point rules, which are important for applica￾tions in adaptive rendering and NC machining, are given as well. Keywords: Doo-Sabin surfaces, NURBS, Limit point rules 1. Introduction The Doo-Sabin [1] and the Catmull-Clark scheme [2] are generalizations of the subdivision rules for biquadratic and bicubic B-splines to meshes of arbitrary topology, respectively. In the same paper [2], Catmull and Clark also proposed a vari￾ant of Doo-Sabin subdivision, which could be interpreted as one linear subdivision step followed by one dual step [3, 4]. In 1998, Sederberg et al. [5] introduced non-uniform re￾cursive subdivision surfaces (NURSSes) that extended non￾uniform tensor product B-spline surfaces to control grids of arbitrary topology for the first time. Quadratic and cubic NURSSes correspond to non-uniform Doo-Sabin and Catmull￾Clark surfaces, respectively. To obtain stationary refinement rules, a restriction that opposing edges of each four-sided face have the same knot interval is placed on cubic NURSSes to generate NURCCs [6]. Limit point rules are useful for adaptive rendering of sub￾division surfaces [7]. For a stationary subdivision scheme, an eigenanalysis can be performed for each configuration of knot intervals to obtain the limit point using the method described in [8]. However, general limit point rules for NURCCs have not yet become available. Recently, M¨uller et al. presented two different approaches to extend both bicubic NURBS and Catmull-Clark surfaces. Extended Subdivision Surfaces (ES￾ubs) [9] offer limit point rules but are nonstationary. DINUS [10] is a stationary scheme which provides limit point as well as limit normal rules. Quadratic NURSSes [5] are the only subdivision surfaces that generalize both non-uniform biquadratic B-spline sur￾faces and original Doo-Sabin surfaces [1]. In Doo-Sabin like ∗Corresponding author. Tel.:+86 551 3603829 Email addresses: zhuang@ustc.edu.cn (Zhangjin Huang), wgp@pku.edu.cn (Guoping Wang) schemes, the extraordinary points are at the ”centers” of n-sided faces with n , 4. Qin et al. point out that quadratic NURSSes converge for n ≤ 12, but may diverge when n > 12 [11]. As a stationary scheme, a detailed eigenanalysis has been performed for quadratic NURSSes [12], but no closed form limit point rules are known for this scheme to date. As for the Catmull￾Clark variant of Doo-Sabin subdivision [2], no non-uniform counterpart has ever been presented to the best of our knowl￾edge. This paper introduces a non-uniform extension to the Catmull-Clark-variant Doo-Sabin surfaces (CCDSes) called NURDSes (Non-Uniform Recursive Doo-Sabin Surfaces). NURDSes are the subdivision surfaces that generalize non￾uniform biquadratic B-spline to control meshes of arbitrary topology and that generalize CCDSes to non-uniform knot vec￾tors. Just like NURSS and NURCC, ”NURDS” can as well stand for ”Non-Uniform Rational Doo-Sabin Surfaces”. By analyzing non-uniform biquadratic B-spline subdivision and the CCDS scheme, NURDSes are devised to have the anal￾ogous properties as follows: • Repeated averaging: One NURDS refinement step can be decomposed into one linear subdivision step followed by one dual step. • Convergence: The NURDS refinement is convergent for extraordinary points with arbitrary valence. • Limit point: For an n-sided face, its weighted centroid is the limit point of its associated extraordinary point. That is, an n-sided face converges to its weighted centroid which is on the limit surface. The rest of this paper is organized as follows. The next section briefly reviews the Catmull-Clark variant of Doo-Sabin Preprint submitted to Computer-Aided Design August 30, 2011

In S E 2.CaturulClark variant of Doo-Ssbin subdivision m e ur 'lark variand of con 巨=+k1+，+h =*六n++++云王 =0.. 1) Fig 3) Non anihrmqutintkBspiatsbdioa ThetheshCamll-Cark prepod in ->1

subdivision. Section 3 describes the decomposition of the non￾uniform quadratic subdivision into one non-uniform linear sub￾division step and one averaging (dual) step. In Section 4, we propose the refinement rules for NURDSes, discuss the con￾tinuity of this scheme and give some examples. Finally, we conclude the paper with some suggestions for future work. 2. Catmull-Clark variant of Doo-Sabin subdivision This section briefly reviews Doo-Sabin subdivision surfaces, especially the Catmull-Clark variant of Doo-Sabin subdivision. bc bc bc bc bc bc bc bc bc bc bc bc bc bc bc bc bc bc bc b b b b b b b b b b b b b b b b b b b b b b b b b V F F E Figure 1: Doo-Sabin subdivision. The Doo-Sabin subdivision algorithm is a generalization of the subdivision scheme for uniform biquadratic B-splines to control meshes of arbitrary topology [1]. The initial control mesh may consist of faces and vertices with arbitrary valence. During each Doo-Sabin subdivision step (see Figs. 1 and 2), for each face with n vertices P0, . . . , Pn−1, the corresponding new vertices P0, . . . , Pn−1 are computed by Pi = Xn−1 j=0 wi, jPj , i = 0, . . . , n − 1. (1) Then a new face of type F is created by connecting P0, . . . , Pn−1 to replace the old one. For each edge, a new four-sided face of type E is formed by connecting the images of the new points that have been generated for the faces sharing this edge. For each vertex, a new face of type V is formed by connecting the new points that have been generated for the faces surrounding the vertex. The weights in Eq. (1) have two forms. One is suggested by Doo and Sabin in [1] as follows wi j =    n+5 4n , i = j 3+2 cos(2π(i−j)/n) 4n , i , j The other is the Catmull-Clark variant proposed in [2] wi j =    1 2 + 1 4n , |i − j| = 0 1 8 + 1 4n , |i − j| = 1 1 4n , |i − j| > 1 bc bc bc bc bc b b b b b Pi Pi−1 Pi+1 Pi Ei−1 Ei F rs rs rs rs rs rs Figure 2: One linear subdivision step followed by a dual step produces the Catmull-Clark variant of Doo-Sabin subdivision. The latter one has a more intuitive geometric interpretation in terms of repeated averaging [3, 4]. As illustrated in Fig. 2, for an n-sided face, one linear subdivision step inserts a new edge point Ei at the midpoint of each edge PiPi+1 and a new face point F at the centroid of each face; then it inserts edges by connecting the face centroid with each of the surrounding edge midpoints. Applying one dual step to the linearly refined mesh, one obtains the same control mesh by performing one step of the Catmull-Clark variant of Doo-Sabin subdivision on the ini￾tial mesh. The dual of a mesh is a new mesh whose vertices are the centroids of old faces and whose edges join centroids of faces that share a common edge. Since the linearly subdi￾vided mesh consists of only quadrilateral faces, the new control vertex Pi corresponding to Pi in an n-sided face is computed as Pi = 1 4 (Pi + Ei−1 + Ei + F) = ( 1 2 + 1 4n )Pi + ( 1 8 + 1 4n )(Pi+1 + Pi−1) + 1 4n X |i−j|>1 Pj . where Ei = (Pi + Pi+1)/2 is the edge point on PiPi+1, and F = Pn−1 j=0 Pj/n is the centroid of the n-sided face. For both Doo-Sabin subdivision schemes, the extraordinary points are at the ”centers” of n-sided faces with n , 4, and their limit positions are exactly at the centroids of the faces. Fig. 3 shows the effect of applying the Catmull-Clark variant of Doo-Sabin subdivision to a cube. Fig. 3(b) is the result of linear subdivision. Fig. 3(c) is the result of next applying dual averaging and corresponds to one round of subdivision applied to the initial cube. Fig. 3(d) is the limit mesh via applying one more dual step. 3. Non-uniform quadratic B-spline subdivision In this section, we show that non-uniform quadratic B-spline subdivision schemes can be also decomposed into one non￾uniform linear subdivision step and one averaging (dual) step. Non-uniform B-spline curves are specified in terms of a set of control points, a knot vector, and a degree. A knot interval is the difference between two adjacent knots in a knot vector, 2

E-+ 0=B+ r 下4Aaa山ai:B-oplire cuv with】 New ed (2)F

(a) (b) (c) (d) Figure 3: Cube model: (a) initial control mesh; (b) linearly subdivided mesh; (c) refined control mesh after dual averaging on (b); and (d) limit mesh of (c). bc bc bc bc bc Pi Pi−1 Pi+1 di di−1 di+1 | | | | si−1 si si+1 si+2 knot intervals: di−1 di di+1 knots: Figure 4: A non-uniform quadratic B-spline curve with its knot intervals. i.e., the parameter length of a B-spline curve segment [5, 6]. For a quadratic B-spline curve, a knot interval di is assigned to each control point Pi , since each control point corresponds to a quadratic curve segment, as Fig. 4 shows. bc bc bc bc bc b b b b b b rs rs rs rs Pi Pi−1 Pi+1 di di−1 di+1 Ei−1 Ei Q2i−1 Q2i Q2i+1 di 2 di 2 di+1 2 | | | | si−1 si si+1 si+2 di 2 di 2 × × × knot intervals: knots: Figure 5: Refinement of a non-uniform quadratic B-spline curve. For each edge PiPi+1, non-uniform linear subdivision inserts a new edge point Ei which is a weighted average of two end￾points of the edge Ei = di+1Pi + diPi+1 di + di+1 , (2) where di and di+1 are the knot intervals associated with Pi and Pi+1, respectively. Subsequently, new control points are gener￾ated using one averaging step Q2i = 1 2 (Pi + Ei) = (di + 2di+1)Pi + diPi+1 2(di + di+1) Q2i+1 = 1 2 (Pi+1 + Ei) = di+1Pi + (2di + di+1)Pi+1 2(di + di+1) as illustrated in Fig. 5. The subdivision rules are the same as those presented in [5]. Note that each new knot interval is half as large as its parent. bc bc bc bc bc bc bc bc bc Pi, j di ej Pi+1, j Pi, j+1 Pi+1, j+1 Pi−1, j−1 | | | | si−1 si si+1 si+2 di−1 di di+1 + + + + tj−1 tj tj+1 tj+2 ej−1 ej ej+1 Figure 6: A non-uniform biquadratic B-spline surface with its knot intervals. Non-uniform biquadratic B-spline surfaces are defined in terms of a control mesh that is topologically a rectangular grid (see Fig. 6). A horizonal knot interval di and a vertical knot interval ej are assigned to each control point Pi, j , since each control point corresponds to a biquadratic surface patch. As illustrated in Fig. 7, one round of non-uniform linear sub￾division inserts one new edge point for each edge and one new face point for each quad face; and it splits each quad into four smaller quads. New edge points are computed according to Eq. (2). New face points are obtained using the tensor product form of Eq. (2). For the quad Pi, jPi+1, jPi+1, j+1Pi, j+1, its new face point is F = ej+1(di+1Pi, j + diPi+1, j) + ej(di+1Pi, j+1 + diPi+1, j+1) (di + di+1)(ej + ej+1) . 3

O-,+E,+E2+F F-Zep 下=P,+E+E+ +a+n+e +c+P+o1+fnP E.(3)p0s F-Xcr,-ZoF

bc bc bc bc bc bc bc bc bc rs rs rs rs rs rs rs rs rs rs rs rs rs rs rs rs b b b b b b b b b b b b b b b b b E1 E2 F Pi, j Pi+1, j Pi, j+1 Pi+1, j+1 Pi−1, j−1 Q2i,2 j | | | | × × × si−1 si si+1 si+2 di−1 2 di 2 di 2 di+1 2 + + + + × × × tj−1 tj tj+1 tj+2 ej−1 2 ej 2 ej 2 ej+1 2 Figure 7: Refinement of a non-uniform biquadratic B-spline surface. The subsequent dual (averaging) step yields the non￾uniform biquadratic B-spine subdivision. For the quad face Pi, jPi+1, jPi+1, j+1Pi, j+1, the new control point Q2i,2 j correspond￾ing to Pi, j is computed as Q2i,2 j = 1 4 (Pi, j + E1 + E2 + F) = Pi, j + F 2 + diej(Pi+1, j + Pi, j+1 − Pi, j − Pi+1, j+1) 4(di + di+1)(ej + ej+1) , where F is the face point of the quad, and E1 and E2 are the two edge points on the edges adjacent to the vertex Pi, j in the face. Again, one obtains the subdivision rules proposed in [5]. Notice that non-uniform biquadratic B-spline surfaces interpolate the face points of all quad faces in their control meshes. 4. NURDSes We now present new non-uniform Doo-Sabin subdivision surfaces called NURDSes (Non-Uniform Recursive Doo-Sabin Surfaces). NURDSes are a generalization of non-uniform bi￾quadratic B-spline surfaces and Catmull-Clark-variant Doo￾Sabin Surfaces. The refinement rules for NURDSes are derived by following the ideas described in Sections 2 and 3. 4.1. Refinement rules For a non-uniform Doo-Sabin surface, each vertex is as￾signed a knot interval (possibly different) for each edge inci￾dent to it. Referring to Fig. 8, the notation d 0 i, j indicates the knot interval for edge PiPj . The notation d m i, j , m ≥ 1 denotes the knot interval for the m-th edge encountered when rotating the edge PiPj counter-clockwise about Pi . And a −m refers to ro￾tating clockwise. After subdivision, new knot intervals d¯k i j can be specified as follows [5] d¯0 i,i+1 = d¯−1 i,i−1 = d 0 i,i+1 d¯0 i,i−1 = d¯1 i,i+1 = d 0 i,i−1 . bc bc bc bc bc b b b b b Pi d 0 i,i+1 d 0 i,i−1 Pi−1 d 0 i−1,i d 0 i−1,i−2 Pi+1 d 0 i+1,i d 0 i+1,i+2 Pi d¯0 i,i+1 d¯0 i,i−1 d¯1 i,i+1 d¯−1 i,i−1 Figure 8: Non-uniform Doo-Sabin refinement. Note that differently from the original form presented in [5], the new knot intervals are scaled by a factor of two, since non￾uniform Doo-Sabin subdivision rules only rely on ratios of the knot intervals. This simplifies computation and leads to station￾ary subdivision. Referring to Fig. 2, since the edge point rule of Eq. (2) is still applicable for arbitrary meshes, all we need to do is to devise a face point rule for n-sided faces for the non-uniform linear subdivision: F = Xn−1 j=0 cjPj , (3) where cj , j = 0, . . . , n − 1 are unknown weights. Then after one dual step on the linearly refined control mesh, we obtain a vertex refinement rule Pi = 1 4 (Pi + Ei−1 + Ei + F) = 1 4 (1 + ci + qi+1 pi + qi+1 + pi−1 pi−1 + qi )Pi + 1 4 X |i−j|>1 cjPj + 1 4 (ci−1 + qi pi−1 + qi )Pi−1 + 1 4 (ci+1 + pi pi + qi+1 )Pi+1. (4) Here we let pi = d 0 i,i+1 and qi = d 0 i,i−1 for the sake of simplicity. That is to say that for a vertex of a face, the corresponding new vertex is the average of four points: the vertex, two edge points on the edges incident on this vertex in the face, and the face point of the face. In both the Catmull-Clark variant of Doo-Sabin subdivision and non-uniform biquadratic B-spline subdivision, face points are the (weighted) centroids of the corresponding faces and ap￾pear on the limit surface, namely, face points are the limit points corresponding to the centers of the faces. Requiring the rule of Eq. (3) possesses the same property, we have F = Xn−1 j=0 cjPj = Xn−1 j=0 cjPj . With the aid of a computer algebra system such as Mathemat￾ica, by solving a system of linear equations with respect to 4

Then fo. 9-m where ieahd6eomegsoisacep g=0p-jwr2e-ie… eod For cample.( dine a type Fto -n4n2,ppM+An+M -P产Pa+AP+nP片+I9R d.2.Comerge -2+6+--+9 +C+1-n of ue ee 工-3+np+2-njP4 ++E+-re Froof By Ed.()or-1.we have 瓦aP+2-nP1+En+2-nEe C=p,+3北+3a+C I--r+,+时+)-r -1+n+- M=...EE. Te光eon物m

cj , j = 0, . . . , n − 1, it follows that cj = αj Pn−1 k=0 αk , where αj = 1 2 ( Yn−1 k=0 pj+k + Yn−1 k=0 qj−k) + Xn−1 m=1 ( Ym k=1 qj+k Yn−1 k=m pj+k). Here indices are taken modulo n. For example, if n = 4 (see Fig. 9), we have bc bc bc bc rsF P0 p0 q0 P1 p1 q1 P2 p2 q2 P3 p3 q3 Figure 9: A four-sided face with its knot intervals. α0 = p0 p1 p2 p3 + q0q1q2q3 2 + q1 p1 p2 p3 + q1q2 p2 p3 + q1q2q3 p3 α1 = p0 p1 p2 p3 + q0q1q2q3 2 + q2 p2 p3 p0 + q2q3 p3 p0 + q2q3q0 p0 α2 = p0 p1 p2 p3 + q0q1q2q3 2 + q3 p3 p0 p1 + q3q0 p0 p1 + q3q0q1 p1 α3 = p0 p1 p2 p3 + q0q1q2q3 2 + q0 p0 p1 p2 + q0q1 p1 p2 + q0q1q2 p2 4.2. Convergence and continuity analysis For an n-sided face at subdivision level k with vertices P k 0 , . . . , P k n−1 , its face point F and new vertices P k+1 i , i = 0, . . . , n − 1 are all linear combinations of old vertices. The construction in previous section guarantees that F is the limit point corresponding to the extraordinary point (i.e. the center) of the face. Theorem 1. The NURDS scheme is convergent at extraordi￾nary points of arbitrary valence. Proof. By Eq. (4), for i = 0, . . . , n − 1, we have: kP k+1 i − Fk = 1 4 (P k i + E k i−1 + E k i + F) − F = 1 4 (1 + qi+1 pi + qi+1 + pi−1 pi−1 + qi )(P k i − F) + qi pi−1 + qi (P k i−1 − F) + pi pi + qi+1 (P k i+1 − F) ≤ 3 4 max 0≤j≤n−1 kP k j − Fk ≤ ( 3 4 ) k+1 max 0≤j≤n−1 kP 0 j − Fk , Then for i = 0, . . . , n − 1, lim k→∞ P k i = F . As a consequence, each n-sided face converges to its face point on the limit surface. Ci Ei−1,2 Ei1 Ei2 Pi Pi−1 Pi+1 bc bc bc bc bc bc bc bc bc bc bc bc bc bc bc bc bc bc bc bc Figure 10: Configuration surrounding a type F face. Like the analysis for quadratic NURSSes in [5], only type F faces are needed to be analyzed for G 1 continuity. After at most two steps of subdivision, the configuration surrounding a type F face may be represented as in Fig. 10. In the center lies the face (of type F) P0P1 . . .Pn−1. Each edge of this face (for example PiPi+1) is adjacent to a four-sided face of type E with vertices PiPi+1Ei2Ei1. The neighborhood of each vertex Pi is completed by a four-sided face of type V with vertices PiEi1CiE(i−1)2. The refinement formulas are as follows: Pi = 1 4 (2 + ci + ri − ri−1)Pi + 1 4 X |i−j|>1 cjPj + 1 4 (ci−1 + ri−1)Pi−1 + 1 4 (1 + ci+1 − ri)Pi+1, Ei1 = 3 8 (1 + ri)Pi + 3 8 (1 − ri)Pi+1 + 1 8 (1 + ri)Ej1 + 1 8 (1 − ri)Ej2, Ei2 = 3 8 riPi + 3 8 (2 − ri)Pi+1 + 1 8 riEj1 + 1 8 (2 − ri)Ej2, Ci = 1 16 (9Pi + 3Ei1 + 3Ei−1,2 + Ci). where rj = qj+1/(pj + qj+1), j = 0, . . . , n − 1, and indices are taken modulo n. For positive knot intervals, it follows that 0 < rj < 1, j = 0, . . . , n − 1. Let the control point vector around this type F be represented by M = [P0, . . . , Pn−1, E01, E02, . . . , En−1,1En−1,2, C0 . . . , Cn−1] and M be the corresponding control point vector after subdivi￾sion. Then M = SnM, where Sn is a 4n × 4n matrix called the 5

=-e-a--款 -}+如± (a) ce:(bi k=7+m+力T0+n立 女-顺 上s Se叫 val 1.F (b)isn hsopolage Form>15,al 1.the subdivision process is divergent

subdivision matrix. We index the eigenvalues of Sn in order of decreasing modulus as λi , i = 0, 1, . . . , 4n − 1. Note that four-sided faces are not always regular cases, since non-uniform Doo-Sabin surfaces permit arbitrary knot inter￾vals. For n = 4, the characteristic polynomial of S4 has the form C4(λ) = (λ − 1)(λ − 1 4 ) 5 (λ − 1 8 ) 4 (λ − 1 16 ) 4 ((λ − 1 2 ) 2 + (r0 + r2 − 1)(r1 + r3 − 1) 16 ). If (r0 + r2 − 1)(r1 + r3 − 1) ≤ 0, we get two real subdominant eigenvalues λ1 = 1 2 + √ −(r0 + r2 − 1)(r1 + r3 − 1) 4 , λ2 = 1 2 − √ −(r0 + r2 − 1)(r1 + r3 − 1) 4 . Since |(r0 + r2 − 1)(r1 + r3 − 1)| λ1 > λ2 > λ3 = 1 4 . If (r0 + r2 − 1)(r1 + r3 − 1) > 0, one obtains two conjugate complex subdominant eigenvalues λ1 = 1 2 + √ (r0 + r2 − 1)(r1 + r3 − 1) 4 I, λ2 = 1 2 − √ (r0 + r2 − 1)(r1 + r3 − 1) 4 I. It is easy to know that λ0 = 1 > |λ1| = |λ2| > λ3 = 1 4 . Us￾ing the analysis techniques in [13], we prove that the proposed subdivision scheme is G 1 in both cases. For valence n = 3, similar results hold. Because the sub￾division matrix Sn has no obvious symmetries, it is difficult to perform an eigenanalysis for extraordinary points with valence n ≥ 5. Being analogous to Sederberg et al. [5], numerical ex￾periments and examples show that limit surfaces are G 1 at these points. 4.3. Examples Since NURDSes generalize biquadratic NURBS and Catmull-Clark-variant Doo-Sabin surfaces, a modeling pro￾gram based on NURDSes can handle any NURBS or Doo￾Sabin model as a special case. Fig. 11 shows uniform and non-uniform Doo-Sabin surfaces generated from a tetrahedron with holes. Fig. 11(a) depicts a uniform Catmull-Clark-variant Doo-Sabin surface after four refinement steps on the initial control mesh. Fig. 11(b) is an example of a NURDS in which three knot intervals along cer￾tain edges have been set to zero (as labeled), thereby creating a crease along the oval edge on the right. Fig. 12 is an example of a doughnut model whose initial con￾trol mesh is topologically a rectangular grid. Fig. 12(b) shows a uniform biquadratic B-spline surface. Fig. 12(c) is a biquadratic NURBS surface with a crease created by setting one row of the knot intervals to zero. Fig. 12(d) depicts a NURDS with a dart formed by setting to zero the knot intervals of appropriate ver￾tices. (a) (b) Figure 11: (a) A uniform Catmull-Clark-variant Doo-Sabin surface; (b) a NURDS with a crease. (a) (b) (c) (d) Figure 12: Doughnut model: (a) initial control mesh; (b) uniform biquadratic B-spline surface; (c) biquadratic NURBS surface with a crease; (d) NURDS with a dart. The shapes in Fig. 11(b) and Fig. 12(d) cannot be obtained using biquadratic NURBS or uniform Doo-Sabin surfaces. We next consider the configuration surrounding a type F face of valence n as illustrated in Fig. 10. Just like [11], we as￾sume that p0 = 1000 and all other knot intervals equal 1. For valence 3 ≤ n ≤ 30, we construct subdivision matrices for quadratic NURSSes and NURDSes respectively, and then in￾vestigate eigenstructure and continuity using the approaches de￾scribed in [13] with the help of a computer algebra system such as Mathematica. Fig. 13 plots absolute values of the first four eigenvalues of the subdivision matrix for quadratic NURSSes for 3 ≤ n ≤ 30. Concerning spectrum and continuity, we have the following results. • For 3 ≤ n ≤ 30, λ0, λ1 and λ2 may be negative, while λ3 is always positive. • For n ≥ 15, |λ0| > 1, the subdivision process is divergent. • For 3 ≤ n ≤ 14, λ0 = 1 > |λ1|, the subdivision process is convergent. 6

25 1.5 0.5 。8◆◆-◆-08000099000000000000 10 20 2 Fipure 13:Absolute values of the first four eigemnlues for qundratie NURSSes for 3sws 30. vertices. · and the CamullCark varamt o Do vision and th ]when all knot inte ls ar urthermore,whe ·For3≤m≤30，o.d4,andare all positive. ordinary P nts of arbitrary valene e while quadrat ·For3≤n≤30.o=1>Al.the subdivision process is convergent. notor high ploitTotat 5.Conclusion 31 In future work we hope variant Doo

0 5 10 15 20 25 30 0 0.5 1 1.5 2 2.5 3 3.5 n λ i |λ 0 | |λ 1 | |λ 2 | λ 3 Figure 13: Absolute values of the first four eigenvalues for quadratic NURSSes for 3 ≤ n ≤ 30. • For 3 ≤ n ≤ 10 and n = 12, λ0 = 1 > |λ1| = |λ2| > λ3, quadratic NURSSes are G 1 continuous at the extraordinary vertices. • For n = 13 and 14, λ0 = 1 > |λ1| > |λ2| > λ3, quadratic NURSSes are G 1 continuous at the extraordinary vertices. • For n = 11, λ0 = 1 > |λ1| > λ2 = λ3, quadratic NURSSes are only G 0 continuous at the extraordinary vertices. Fig. 14 depicts values of the first four eigenvalues of the sub￾division matrix for NURDSes for 3 ≤ n ≤ 30. It follows that • For 3 ≤ n ≤ 30, λ0, λ1, λ2 and λ3 are all positive. • For 3 ≤ n ≤ 30, λ0 = 1 > |λ1|, the subdivision process is convergent. • For 3 ≤ n ≤ 30, λ0 = 1 > λ1 = λ2 > λ3, NURDSes are G 1 continuous at the extraordinary vertices. 5. Conclusion In this paper we have introduced new non-uniform Doo￾Sabin surfaces – NURDSes. Both non-uniform biquadratic B￾spline surfaces and Catmull-Clark-variant Doo-Sabin surfaces can be represented with this surface type. In addition, the new subdivision scheme can be factored into one linear subdivision step and one dual step just like biquadratic non-uniform B￾spline subdivision and the Catmull-Clark variant of Doo-Sabin subdivision. In comparison to quadratic NURSSes [5], the NURDSes re￾duce to Catmull-Clark-variant Doo-Sabin surfaces [2] whereas quadratic NURSSes degenerate to original Doo-Sabin surfaces [1] when all knot intervals are equal. Furthermore, when all knot intervals are positive, the NURDSes are convergent at extraordinary points of arbitrary valence while quadratic NURSSes may diverge for valences larger than 12. And closed form limit point rules are available for NURDSes as well. Although the refinement rules for NURDSes are stationary, it is not easy to analyze the eigenstructure of the subdivision ma￾trix for high valence. Standard analysis techniques usually ex￾ploit rotational symmetry to transform a large subdivision ma￾trix into a block diagonal matrix [13]. However, the NURDS scheme is not rotationally symmetric. In future work we hope to derive efficient approaches to deal with such schemes. Rig￾orous analysis for G 1 continuity for valence n > 5 remains to be investigated. 7

1.2 0.8 <0.7 06 0.s 0.4 10 20 Figure 14:Values of the frst four eigenvaues for NURDSes for Acknowledgments uCs.SIGGRAPH 98.ACM (20 。0 USA.1993. 2092X07028.002-003.00 velopment Program of China (N References h2932010,251-252 .U.Re etry and Comput

0 5 10 15 20 25 30 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 1.1 1.2 n λ i λ 0 λ 1 λ 2 λ 3 Figure 14: Values of the first four eigenvalues for NURDSes for 3 ≤ n ≤ 30. Acknowledgments We would like to thank Dr. J¨org Peters (University of Florida) for valuable discussions, and the anonymous review￾ers for their useful comments. This work was supported by the National Natural Science Foundation of China (Nos. 60803066, 60925007, 60903148, 10901149), the National Basic Research Program of China (No. 2010CB328002) and the National High Technology Research and Development Program of China (No. 2009ZX01028-002-003-005). References [1] D. Doo, M. Sabin, Analysis of the behaviour of recursive division surfaces near extraordinary points, Computer-Aided Design 10 (6) (1978) 356– 360. [2] E. Catmull, J. Clark, Recursively generated B-spline surfaces on arbitrary topological meshes, Computer-Aided Design 10 (6) (1978) 350–355. [3] J. Stam, On subdivision schemes generalizing uniform B-spline surfaces of arbitrary degree, Computer Aided Geometric Design 18 (5) (2001) 383 – 396. [4] D. Zorin, P. Schr¨oder, A unified framework for primal/dual quadrilateral subdivision schemes, Computer Aided Geometric Design 18 (5) (2001) 429 – 454. [5] T. W. Sederberg, J. Zheng, D. Sewell, M. Sabin, Non-uniform recursive subdivision surfaces, in: Proceedings of the 25th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH ’98, ACM, New York, NY, USA, 1998, pp. 387–394. [6] T. W. Sederberg, J. Zheng, A. Bakenov, A. Nasri, T-splines and T￾NURCCs, ACM Trans. Graph. 22 (3) (2003) 477–484. [7] K. M¨uller, T. Techmann, D. Fellner, Adaptive ray tracing of subdivision surfaces, Computer Graphics Forum 22 (3) (2003) 553–562. [8] M. Halstead, M. Kass, T. DeRose, Efficient, fair interpolation using Catmull-Clark surfaces, in: Proceedings of the 20th Annual Confer￾ence on Computer Graphics and Interactive Techniques, SIGGRAPH ’93, ACM, New York, NY, USA, 1993, pp. 35–44. [9] K. M¨uller, L. Reusche, D. Fellner, Extended subdivision surfaces: Build￾ing a bridge between NURBS and Catmull-Clark surfaces, ACM Trans. Graph. 25 (2) (2006) 268–292. [10] K. M¨uller, C. F¨unfzig, L. Reusche, D. Hansford, G. Farin, H. Hagen, Di￾nus: Double insertion, nonuniform, stationary subdivision surfaces, ACM Trans. Graph. 29 (3) (2010) 25:1–25:21. [11] K. Qin, H. Wang, Eigenanalysis and continuity of non-uniform Doo￾Sabin surfaces, in: Proceedings of the 7th Pacific Conference on Com￾puter Graphics and Applications, PG ’99, IEEE Computer Society, Wash￾ington, DC, USA, 1999, pp. 179–186. [12] H. Wang, K. Qin, H. Sun, Evaluation of non-uniform Doo-Sabin surfaces, Int. J. Comput. Geometry Appl. 15 (3) (2005) 299–324. [13] J. Peters, U. Reif, Subdivision Surfaces, Vol. 3 of Geometry and Comput￾ing, Springer-Verlag, New York, 2008. 8