Aole业nirpkCtatiolsaiaoe12w1o0y1-6 Extended Doo-Sabin Surfaces Zhangin Huangab.c Feng Wangabc,Guoping Wang de Abstract dification of but use th Keyuonis:Doo-Sahin surfnce;NURBS:Subdivision surfaces 1 Introduction ebie non-ationryivisole nd D (g)()
Journal of Information & Computational Science 7: 1 (2010) 1–6 Available at http://www.joics.com Extended Doo-Sabin Surfaces ? Zhangjin Huang a,b,c,∗, Feng Wang a,b,c , Guoping Wang d,e aSchool of Computer Science and Technology, University of Science and Technology of China, China bKey Laboratory of Software in Computing and Communication, Anhui Province, China cUSTC-SICT Joint Laboratory on Network and Communication, China dKey Laboratory of Machine Perception (MOE), Peking University, China eSchool of Electronic Engineering and Computer Science, Peking University, China Abstract In this paper we propose a modification of quadratic NURSSes called EDSes (Extended Doo-Sabin Surfaces). EDSes inherit the refinement rules for quadratic NURSSes for four-sided faces but use the refinement rules for Doo-Sabin surfaces for faces with other than four sides. Compared to quadratic NURSSes, if all the knot intervals are positive, EDSes always converge to G1 continuous limit surfaces with closed-form limit point as well as limit normal rules. Keywords: Doo-Sabin surfaces; NURBS; Subdivision surfaces 1 Introduction In 1978, Doo and Sabin [1] and Catmull and Clark [2] generalized the subdivision schemes for uniform biquadratic and bicubic B-splines to arbitrary topological meshes, respectively. In 1998, Sederberg et al. introduced NURSSes (Non-Uniform Recursive Subdivision Surfaces) [3] that extend non-uniform tensor product B-spline surfaces to arbitrary topologies. Quadratic and cubic NURSSes respectively correspond to non-uniform Doo-Sabin and Catmull-Clark surfaces. Later, they proposed NURCCs [4] by requiring opposing edges of each four-sided face of cubic NURSSes to have the same knot interval. NURCCs have stationary refinement rules, whereas cubic NURSSes have non-stationary subdivision rules. Limit meshes are shown to be tighter approximations to limit surfaces than corresponding control meshes [5], and are essential for adaptive rendering of subdivision surfaces [6]. For a ?Project 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). ∗Corresponding author. Email addresses: zhuang@ustc.edu.cn (Zhangjin Huang), wffrank@mail.ustc.edu.cn (Feng Wang), wgp@pku.edu.cn (Guoping Wang). 1548–7741/ Copyright © 2010 Binary Information Press January 2010
oth slbdivision scheme,an einanalysis c achs to both NURBS 一之w ark surfa ed out tha tructured as follows T 2 Quadratic NURSSes Fig.1:Doo-Sabin subdivision
2 Z. Huang et al. /Journal of Information & Computational Science 7: 1 (2010) 1–6 stationary smooth subdivision scheme, an eigenanalysis can be performed for each configuration of knot intervals to compute the limit point and corresponding limit normal vector [7]. However, explicit limit point and limit normal rules for quadratic NURSSes or NURCCs have not yet become available. M¨uller et al. recently presented two different approaches to generalize both bicubic NURBS and Catmull-Clark surfaces. ESubs (Extended Subdivision Surfaces) [8] offer limit point rules but are non-stationary. DINUS [9] is a stationary scheme and provides limit point as well as limit normal rules. Both schemes use the refinement rules for Catmull-Clark surfaces [2] near control points with valence unequal to four. Quadratic NURSSes [3] are the only subdivision surfaces that extend both non-uniform biquadratic B-spline surfaces and Doo-Sabin surfaces [1]. In Doo-Sabin like schemes, the extraordinary points are at the ”centers” of n-sided faces with n 6= 4. In [10], Qin et al. pointed out that quadratic NURSSes converge for n ≤ 12, but may diverge when n > 12. As a stationary scheme, a detailed eigenanalysis has been performed for quadratic NURSSes [11]. But no closed-form limit point or limit normal rules are known for this scheme up to now. This paper presents a modification of quadratic NURSSes called EDSes (Extended Doo-Sabin Surfaces): For four-sided faces, the quadratic NURSS refinement rules [3] are applied; for n-sided faces with n 6= 4, the Doo-Sabin refinement rules [1] are used. As a result, if the knot intervals are all positive, the EDS scheme always generate G1 continuous limit surfaces. And explicit limit point and limit normal rules are derived as well. The remainder of the paper is structured as follows. The next section briefly reviews quadratic NURSSes. Sect. 3 describes the refinement rules for EDSes, and derives limit point and limit normal rules. Several examples are given as well. Finally, we conclude the paper with some suggestions for future work. 2 Quadratic NURSSes 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 Fig. 1: Doo-Sabin subdivision. Quadratic NURSSes are non-uniform Doo-Sabin surfaces that generalize non-uniform biquadratic B-spline surfaces to meshes of arbitrary topology [3]. Quadratic NURSSes have the same topological split rules as Doo-Sabin surfaces [1]: At each subdivision step, new vertices are generated
Z.Hwung et a.Alournal of Information Computational Science 7:1 (2010)1-6 3 Fig:No-uniform Doo-Sabin refnement. 何htiP.,the P 8∑k where ce dx-1xdg+1 and v The rues for specifying new knot intervalsare given as follows o
Z. Huang et al. /Journal of Information & Computational Science 7: 1 (2010) 1–6 3 and then connected to form new faces of type F, type E and type V respectively for each face, edge and vertex of the previous mesh (see Fig. 1). Initial control meshes may consist of vertices of valence other than four, and faces with other than four sides. We call a vertex of valence four regular, otherwise, irregular. Similarly, a face with four sides is regular, otherwise, irregular. In Doo-Sabin like schemes, the extraordinary points are at the centers of irregular faces. After one subdivision step, every vertex of the refined mesh will be regular, and the number of irregular faces will remain constant. 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 Fig. 2: Non-uniform Doo-Sabin refinement. For non-uniform Doo-Sabin surfaces, each vertex is assigned a knot interval for each edge incident to it [3]. Refer to Fig. 2 for notations. di,j = d 0 i,j indicates the knot interval for edge PiPj . 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 rotating clockwise. In general, di,j 6= dj,i. For a face with n vertices P0, . . . , Pn−1, the corresponding new vertices P0, . . . , Pn−1 are computed by [3] Pi = Pi + V 2 + (ci+2 + ci−2) × −nPi + Pn−1 j=0 (1 + 2 cos( 2π|i−j| n ))Pj 8 Pn−1 k=0 ck , (1) where ck = dk−1,kdk+1,k and V = Pn−1 k=0 ckPk Pn−1 k=0 ck . The rules for specifying new knot intervals ¯d k ij are given as follows [3] ¯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 . (2) Remark 1 Different from the original form in [3], the new knot intervals are all multiplied by two, since non-uniform Doo-Sabin subdivision rules only rely on ratios of the knot intervals. This simplifies computation and leads to stationary subdivision. Unfortunately, quadratic NURSSes are not even convergent in some cases. Qin et al. [10] proved that quadratic NURSS refinement converges for n-sided faces with n ≤ 12, but may diverge when
Z.Hung ct al./of Information Compurtational Science 7:1 (20110)1-6 3 Extended Doo-Sabin Surfaces 3.1 Regular faces d P。d Fig.3:A regular face with its knot intervals F-P+V +Ba-Pi-Pe3) *-学P,+学+学P+学+学P+学P e taken modulo Let the c
4 Z. Huang et al. /Journal of Information & Computational Science 7: 1 (2010) 1–6 n > 12. On the other hand, for convergent quadratic NURSSes, no closed-form limit point or limit normal rules have been proposed so far. 3 Extended Doo-Sabin Surfaces We now present a modification of quadratic NURSSes [3] that we call EDSes (Extended DooSabin Surfaces). EDSes are identical to quadratic NURSSes, with one difference: EDSes use the refinement rules for Doo-Sabin surfaces [1] to compute new vertices created for irregular faces. It is for that reason that EDSes are always convergent for all positive knot intervals. It is also for that reason that EDSes have closed-form limit point as well as limit normal rules. 3.1 Regular faces bc bc bc bc P0 d01 d03 P1 d12 d10 P2 d23 d21 d30 P3 d32 b b b P0 b P1 P2 P3 Fig. 3: A regular face with its knot intervals. The refinement rules for regular faces for EDSes are identical to those for quadratic NURSSes. Let n = 4, it follows from Eq. (1) that Pi = Pi + V 2 + ci+2 4 P3 k=0 ck (Pi−1 + Pi+1 − Pi − Pi+2) = (1 2 + wi 2 − wi+2 4 )Pi + (wi−1 2 + wi+2 4 )Pi−1 + (wi+1 2 + wi+2 4 )Pi+1 + wi+2 4 Pi+2 where wj = cj/ Pk=3 k=0 ck, j = 0, 1, 2, 3, and indices are taken modulo 4. We now derive limit point and limit normal rules for regular faces. Let the control point vector of a regular face be M = [P0, P1, P2, P3] T and M be the corresponding control point vector after
subdivision.Then M=S M,where the subdivisionrix s amatrix [+学-导号+学 警十好3+婴一4 +j++专+u+ + =2+nX+-+-2+ -3+2a+(+s,(m+s1-2+) 与-3-4+m0o+,-1,1- m2ae0R装hMoa 3.2 Irregular faces 瓦-r
Z. Huang et al. /Journal of Information & Computational Science 7: 1 (2010) 1–6 5 subdivision. Then M = S4M, where the subdivision matrix S4 is a 4 × 4 matrix: S4 = 1 2 + w0 2 − w2 4 w1 2 + w2 4 w2 4 w3 2 + w2 4 w0 2 + w2 4 1 2 + w1 2 − w3 4 w2 2 + w3 4 w3 4 w0 4 w1 2 + w0 4 1 2 + w2 2 − w0 4 w3 2 + w0 4 w0 2 + w1 4 w1 4 w2 2 + w1 4 1 2 + w3 2 − w1 4 = l0 l1 l2 l3 −1 1 0 0 0 0 1 2 0 0 0 0 1 2 0 0 0 0 1 4 l0 l1 l2 l3 Here l0, l1, l2 and l3 are the left eigenvectors of S4 corresponding to eigenvalues λ0 = 1, λ1 = λ2 = 1 2 , and λ3 = 1 4 respectively: l0 =[w0 3 + 2 3 (w0 + w3)(w0 + w1), w1 3 + 2 3 (w0 + w1)(w1 + w2), w2 3 + 2 3 (w1 + w2)(w2 + w3), w3 3 + 2 3 (w2 + w3)(w0 + w3)] , l1 =[(w0 + w1)(1 − 2(w0 + w3)), −2(w0 + w1)(w1 + w2), (w1 + w2)(1 − 2(w2 + w3)), w0 − w2 + 2(w1 + w2)(w2 + w3)] , l2 =[−2(w0 + w1)(w0 + w3), −(w0 + w1)(1 − 2(w0 + w3)), w1 − w3 + 2(w0 + w3)(w2 + w3),(w0 + w3)(1 − 2(w2 + w3))] , l3 = 1 3 (w1 − 4(w0 + w1)(w1 + w2))[1, −1, 1, −1] . (3) Using the approach described in [7], one can get: Proposition 1 For a regular face with vertices M = [P0, P1, P2, P3] T , its center will converge to the point l0 · M on the limit surface. Proposition 2 The normal vector to an EDS at the limit point l0 ·M corresponding to a regular face with vertices M is the vector (l1 · M) × (l2 · M), here ”×” denotes vector cross product. 3.2 Irregular faces To solve the divergence problem of quadratic NURSSes, EDSes employ the same refinement rules for irregular faces as Doo-Sabin surfaces [1]. For an irregular face with n vertices P0, . . . , Pn−1 (see Fig. 4), the new vertex Pi is computed as Pi = Xn−1 j=0 ai,jPj , (4)
Z.Hung et al./lournai of Computational Scieace 7:1 (2010)1-6 P Fig.4:An irregular face. i=i: =1>==>=.=-1= etd电of。copodins t友pectivdye 6=2,1, 1 =f1.cos(2x/ni.....cos(2m(n -1)/nil 1=0,sin(2x/n)..sim2r(m-1)/n)1. Tea&eaeaentois,ebmsegmaadshcBsnaa
6 Z. Huang et al. /Journal of Information & Computational Science 7: 1 (2010) 1–6 bc bc bc bc bc b b b b b Pi Pi−1 Pi+1 Pi Fig. 4: An irregular face. where the weights suggested in [1] are aij = n+5 4n , i = j ; 3+2 cos(2π(i−j)/n) 4n , i 6= j . Let M = [P0, P1, . . . , Pn−1] T denote the control point vector of an irregular n-sided face, and M denote the corresponding control point vector after subdivision. Then it follows that M = SnM, where the subdivision matrix Sn is an n×n matrix. Using the discrete Fourier transform technique [12], the eigenvalues of Sn are λ0 = 1 > λ1 = λ2 = 1 2 > λ3 = . . . = λn−1 = 1 4 , and the left eigenvectors l0, l1 and l2 of Sn corresponding to λ0, λ1 and λ2 respectively are as follows l0 = 1 n [1, 1, . . . , 1] , l1 =[1, cos(2π/n), . . . , cos(2π(n − 1)/n)] , l2 =[0,sin(2π/n), . . . ,sin(2π(n − 1)/n)] . (5) Thus we have the following limit point and limit normal rules for irregular faces. Proposition 3 For an irregular n-sided face with vertices M = [P0, P1, . . . , Pn−1] T , its center will converge to the point l0 · M = 1 n Pn−1 i=0 Pi on the limit surface. Proposition 4 The normal vector to an EDS at the limit point l0 · M corresponding to an irregular n-sided face with vertices M is the vector (l1 · M) × (l2 · M), here ”×” denotes vector cross product. For Doo-Sabin subdivision scheme [1], Peters and Reif proved C 1 -continuity for all valences [12]. Then we get the following continuity result for EDSes. Theorem 1 If all knot intervals are positive, the limit surface generated by the EDS refinement scheme is G1 continuous everywhere
3.3 Examples es red (e) (d] 时份。oo8地te付am时 d (d) an d aa EDS with The shapes in Figs.5(d)and 6(d)camot be produced using biquadratic NURBS
Z. Huang et al. /Journal of Information & Computational Science 7: 1 (2010) 1–6 7 3.3 Examples EDSes are a generalization of non-uniform biquadratic B-spline surfaces and Doo-Sabin surfaces. If all vertices are of valence four, if all faces are four-sided, and if the knot intervals on rows and columns are equal respectively, EDSes reduce to non-uniform biquadratic B-spline surfaces. If all knot intervals are equal, EDSes degenerate to Doo-Sabin surfaces. Thus, a modeling program for EDSes can generate biquadratic NURBS sufaces and Doo-Sabin surfaces as special cases. (a) (b) (c) (d) Fig. 5: Tetrahedral mesh with holes: (a) initial control mesh, (b) Doo-Sabin surface, (c) control mesh after four rounds of EDS subdivision, (d) limit mesh of (c). Fig. 5 shows uniform and non-uniform Doo-Sabin surfaces produced from a tetrahedral mesh with holes. Fig. 5(b) depicts a Doo-Sabin surface after four refinement steps on the initial control mesh in (a). Figs. 5(c) and (d) show the control mesh and limit mesh of an EDS whose crease is formed by setting three knot intervals of certain initial vertices to zero. The limit mesh in (d) is rendered using the proposed limit point and limit normal rules. Fig. 6 is an example of a doughnut model whose initial control mesh is topologically a rectangular grid (i.e. a B-spline control net). Fig. 6(b) shows a uniform biquadratic B-spline surface. A biquadratic NURBS surface with a crease is depicted in (c) by setting one row of the knot intervals to zero. Fig. 6(d) illustrates an EDS with a dart induced by setting to zero the knot intervals of appropriate vertices. The shapes in Figs. 5(d) and 6(d) cannot be produced using biquadratic NURBS or uniform
(a) e() Doo-Sabin surfaces. 4 Conclusion Both EDSes and quadratic NURSSes are generalizations of References
8 Z. Huang et al. /Journal of Information & Computational Science 7: 1 (2010) 1–6 (a) (b) (c) (d) Fig. 6: Doughnut model: (a) initial control mesh, (b) uniform biquadratic B-spline surface, (c) biquadratic NURBS surface with a crease, (d) EDS with a dart. Doo-Sabin surfaces. 4 Conclusion This paper presents EDSes which are a modification of quadratic NURSSes [3]. EDSes retain the refinement rules for quadratic NURSSes for regular faces whereas use the refinement rules for Doo-Sabin surfaces for irregular faces. Both EDSes and quadratic NURSSes are generalizations of non-uniform biquadratic B-spline surfaces and Doo-Sabin surfaces. In comparison to quadratic NURSSes, if all the knot intervals are greater than zero, EDSes converge at extraordinary points of arbitrary valence while quadratic NURSSes may diverge for valences larger than 12. And closed-form limit point and limit normal rules are available for EDSes as well. In future work we hope to derive a parametrization for exact and efficient evaluation of EDSes following the method of Stam [13]. References [1] Doo, D., Sabin, M.: Analysis of the behaviour of recursive division surfaces near extraordinary points. Computer-Aided Design 10 (1978) 356–360. [2] Catmull, E., Clark, J.: Recursively generated B-spline surfaces on arbitrary topological meshes. Computer-Aided Design 10 (1978) 350–355
Z.Huang ct al./oural of nformation&Computational Science 7:1(2010)16 9 SIGGRAPHS.New York,NY.USA.ACM (1998)37-394 用竖,A.AT-URCC ACA 网a于gD:e p York,NY,USA.ACM (19). C,USA,IEEE Computer Sorety (1999)179-186
Z. Huang et al. /Journal of Information & Computational Science 7: 1 (2010) 1–6 9 [3] Sederberg, T.W., Zheng, J., Sewell, D., Sabin, M.: Non-uniform recursive subdivision surfaces. In: Proceedings of the 25th Annual Conference on Computer Graphics and Interactive Techniques. SIGGRAPH’98, New York, NY, USA, ACM (1998) 387–394. [4] Sederberg, T.W., Zheng, J., Bakenov, A., Nasri, A.: T-splines and T-NURCCs. ACM Trans. Graph. 22 (2003) 477–484. [5] Huang, Z., Deng, J., Wang, G.: A bound on the approximation of a Catmull-Clark subdivision surface by its limit mesh. Computer Aided Geometric Design 25 (2008) 457–469. [6] M¨uller, K., Techmann, T., Fellner, D.: Adaptive ray tracing of subdivision surfaces. Computer Graphics Forum 22 (2003) 553–562. [7] Halstead, M., Kass, M., DeRose, T.: Efficient, fair interpolation using Catmull-Clark surfaces. In: Proceedings of the 20th Annual Conference on Computer Graphics and Interactive Techniques. SIGGRAPH’93, New York, NY, USA, ACM (1993) 35–44. [8] M¨uller, K., Reusche, L., Fellner, D.: Extended subdivision surfaces: Building a bridge between NURBS and Catmull-Clark surfaces. ACM Trans. Graph. 25 (2006) 268–292. [9] M¨uller, K., Funfzig, C., Reusche, L., Hansford, D., Farin, G., Hagen, H.: Dinus: Double insertion, nonuniform, stationary subdivision surfaces. ACM Trans. Graph. 29 (2010) 25:1–25:21. [10] Qin, K., Wang, H.: Eigenanalysis and continuity of non-uniform Doo-Sabin surfaces. In: Proceedings of the 7th Pacific Conference on Computer Graphics and Applications. PG’99, Washington, DC, USA, IEEE Computer Society (1999) 179–186. [11] Wang, H., Qin, K., Sun, H.: Evaluation of non-uniform Doo-Sabin surfaces. Int. J. Comput. Geometry Appl. 15 (2005) 299–324. [12] Peters, J., Reif, U.: Analysis of generalized B-spline subdivision algorithms. SIAM Journal on Numerical Analysis 35 (1998) 728–748. [13] Stam, J.: Exact evaluation of Catmull-Clark subdivision surfaces at arbitrary parameter values. In: Proceedings of the 25th Annual Conference on Computer Graphics and Interactive Techniques. SIGGRAPH’98, New York, NY, USA, ACM (1998) 395–404