ACCEPTED MANUSCRIPT of a Catmull a surface by its limi mesh Zhangjin Huang Jiansong Deng,Guoping Wang CCSS. nd on CCSS a eaa.Pt epth csti 1ga1the.T:+861062765819 29Mg20
ACCEPTED MANUSCRIPT ACCEPTED MANUSCRIPT A bound on the approximation of a Catmull-Clark subdivision surface by its limit mesh Zhangjin Huang a,b,∗, Jiansong Deng c , Guoping Wang a aSchool of Electronics Engineering and Computer Science, Peking University, Beijing 100871, China bDepartment of Computer Science and Technology, University of Science and Technology of China, Hefei, Anhui 230027, China cDepartment of Mathematics, University of Science and Technology of China, Hefei, Anhui 230026, China Abstract A Catmull-Clark subdivision surface (CCSS) is a smooth surface generated by recursively refining its control meshes, which are often used as linear approximations to the limit surface in geometry processing. For a given control mesh of a CCSS, by pushing the control points to their limit positions, another linear approximation – a limit mesh of the CCSS is obtained. In general a limit mesh might approximate a CCSS better than the corresponding control mesh. We derive a bound on the distance between a CCSS patch and its limit face in terms of the maximum norm of the second order differences of the control points and a constant that depends only on the valence of the patch. A subdivision depth estimation formula for the limit mesh approximation is also proposed. For a given error tolerance, fewer subdivision steps are needed if the refined control mesh is replaced with the corresponding limit mesh. Key words: Catmull-Clark subdivision surfaces, Limit mesh, Distance bound, Subdivision depth ∗ Corresponding author. Tel.: +86 10 62765819; fax: +86 10 62755798. Email addresses: zhangjin.huang@gmail.com (Zhangjin Huang), dengjs@ustc.edu.cn (Jiansong Deng), gwang@graphics.pku.edu.cn (Guoping Wang). Preprint submitted to Elsevier 29 May 2008
ACCEPTED MANUSCRIPT 1 Introduction car ap aeinappicl its app dtusalsd ea出 1 n repres ired by 206 exte it nd Qin2004.tsm hCCsand ed bounds f cd a e.Then Chen a(2006)im
ACCEPTED MANUSCRIPT ACCEPTED MANUSCRIPT 1 Introduction The Catmull-Clark subdivision surface (CCSS) was designed to generalize the bicubic uniform B-spline surface to meshes of arbitrary topology (Catmull and Clark, 1978). Because a CCSS is defined as the limit of a sequence of recursively subdivided control meshes, a linear approximation (for example, a refined control mesh after several steps of subdivision) is often used to approximate the limit surface in applications such as surface rendering, surface trimming, and surface/surface intersection. It is natural to ask the following questions: ”How does one estimate the error (distance) between a CCSS and its approximation (for instance, the control mesh)?” and ”How many (as small as possible) steps of subdivision are needed to satisfy a user-specified error tolerance?”. Because of the exponential growth in the number of mesh faces with successive subdivisions, one step, more or one less, can mean a great difference in mesh density. Also, subdivision depth (step) estimation relies on the approximation representation and its error estimate. Inspired by ideas for computing the bounds on the approximation of polynomials and splines by their control structure (Nairn et al., 1999; Reif, 2000; Lutterkort and Peters, 2001), many efforts have been devoted to estimating error bounds and subdivision depths for subdivision surfaces. Mustafa et al. derived error bounds for general binary and ternary subdivision curves/surfaces in terms of the maximal first order differences of the control points (Mustafa et al., 2006; Mustafa and Deng, 2007). Their bounds work for regular tensor product subdivision surfaces, and, to some extent, have only theoretical values. As one of the most widely used subdivision surfaces, the CCSS receives more attention than others. The first attempt to derive bounds on the approximation of the CCSS by its control mesh was made by Wang and Qin (2004). Using the distance between the control points and their limits to describe how the control mesh approximates to the limit surface, they derived bounds for the distance between a CCSS and its control mesh and a corresponding subdivision depth estimation method. Their work is based on the assumption that the distance between a CCSS and its control mesh reaches a maximum value at some vertex. But this is not always true. Being aware of this, Cheng and Yong (2006) estimated the distance between a CCSS and its control mesh patch by patch. For a regular patch, the bound is given in terms of the maximum norm of the second order differences (called the second order norm) of the control points; whereas for an extraordinary patch, the bound is expressed in terms of the first order norm of the control points. They also derived a new subdivision depth estimation technique. Then Cheng et al. (2006) improved the error estimate and subdivision depth estimation for an extraordinary CCSS patch by introducing the second order norm into its control mesh. Furthermore, Chen 2
ACCEPTED MANUSCRIPT 2007c e the fzACatmiLcCarkaubiwianurt and the coeresponding the limit andin edein CC petches.rep
ACCEPTED MANUSCRIPT ACCEPTED MANUSCRIPT and Cheng (2006) presented another improvement by using a matrix representation of the second order norm, in the estimate of the convergence rate of the second order norm of an extraordinary CCSS patch. Most recently, Huang and Wang (2007) evaluated the optimal convergence rate of the second order norm by solving constrained minimization problems. Nevertheless, for an extraordinary CCSS patch, the subdivision depth for a given error tolerance is still very large. Since the prior works all focus on the approximation of a CCSS with its control mesh, we turn our attention to other linear approximations. Fig. 1. A Catmull-Clark subdivision surface, its control mesh and the corresponding limit mesh. Another known linear approximation to a subdivision surface, obtained by pushing the control points of a control mesh to their limit positions, has been applied in surface interpolation (Halstead et al., 1993) and fitting (Hoppe et al., 1994). But the approximation error has not yet been investigated. We reformulate this approximation representation as follows. Extracting a submesh consisting of all interior control points from the control mesh of a CCSS, then pushing the control points to their limit positions, we get a limit mesh for the CCSS, which inscribes the limit surface (see Fig. 1). For a closed CCSS, submesh extraction is not needed since its control points are all interior. To bound the distance between a CCSS patch and its limit face, we introduce a distance bound function, and develop a way to find the maximum of the distance bound function for extraordinary cases. The bound reveals that the limit mesh may approximate the limit surface better than the corresponding control mesh in general. Given an error tolerance, the limit mesh approximation needs fewer subdivision steps and fewer mesh faces than the control mesh approximation. This paper is organized as follows. Section 2 introduces some definitions and notation. In Sections 3 and 4, we derive distance bounds for regular CCSS patches and extraordinary CCSS patches, respectively. And a subdivision depth estimation method for limit mesh approximation is presented in Section 5. In Section 6, we compare limit mesh with control mesh approximation. 3
ACCEPTED MANUSCRIPT Finally we conclude the paper with discussion of future work 2 Deflnition and notation ● 2.1 Distances of the natch s (sre Fis. e Is-Fu训 2 Second order norm
ACCEPTED MANUSCRIPT ACCEPTED MANUSCRIPT Finally we conclude the paper with discussion of future work. 2 Definition and notation Without loss of generality, we assume the initial control mesh has been subdivided at least twice, isolating the extraordinary vertices so that each face is a quadrilateral and contains at most one extraordinary vertex. 2.1 Distances Given a control mesh and the corresponding limit mesh of a Catmull-Clark subdivision surface S˜, for each interior mesh face F in the control mesh, there is a corresponding limit face F in the limit mesh, and a corresponding surface patch S in the limit surface S˜. The limit face F is a quadrilateral formed by connecting the four corner points of the patch S. 2n+8 control points in the 1-neighborhood of F form S’s control mesh, where n is the valence of F’s only extraordinary vertex (if it has one and n = 4 if not) and called the valence of the patch S (see Fig. 2a). A CCSS patch S can be parameterized over the unit square Ω = [0, 1] × [0, 1] as S(u, v) (Stam, 1998). Let F(u, v) be the bilinear parameterization of the corresponding limit face F over Ω. For (u, v) ∈ Ω, we denote S(u, v) − F(u, v) as the distance between the points S(u, v) and F(u, v). The distance between a CCSS patch S and the corresponding limit face F is defined as the maximum distance between S(u, v) and F(u, v), that is, max (u,v)∈Ω S(u, v) − F(u, v) , which is also called the distance between the patch S and the limit mesh of the surface S˜. 2.2 Second order norms Let Π = {Pi : i = 1, 2,..., 2n + 8} be the control mesh of an extraordinary patch S = S0 0, with P1 being an extraordinary vertex of valence n. The control points are ordered following Stam’s method (Stam, 1998) (Fig. 2a). The second order norm of Π (or S), denoted M = M0 = M0 0 , is defined as the maximum norm of the following 2n + 10 second order differences (SODs) {αi : i = 4
ACCEPTED MANUSCRIPT 2+8 2+ 1.+10)of the control points (Cheng006) 2P+P +P 2+7 ( spect y(Fig)
ACCEPTED MANUSCRIPT ACCEPTED MANUSCRIPT 2n + 1 2 3 2n + 8 8 1 4 2n + 7 7 6 5 2n + 6 2n + 5 2n +4 2n +3 2n + 2 9 S = S0 0 (a) 2n+1 2 3 2n+8 2n+17 9 8 1 4 2n+7 2n+16 7 6 5 2n+6 2n+15 2n+5 2n+4 2n+3 2n+2 2n+14 2n+13 2n+12 2n+11 2n+10 2n+9 S1 0 S1 3 S1 1 S1 2 (b) Fig. 2. (a) Ordering of the control points of an extraordinary patch. (b) Ordering of the new control points (solid dots) after a Catmull-Clark subdivision. 1,..., 2n + 10} of the control points (Cheng et al., 2006): M = max{{P2i − 2P1 + P2((i+1)%n+1) : 1 ≤ i ≤ n} ∪{P2i+1 − 2P2(i%n)+2 + P2(i%n)+3 : 1 ≤ i ≤ n} ∪{P2 − 2P3 + P2n+8, P1 − 2P4 + P2n+7, P6 − 2P5 + P2n+6, P4 − 2P5 + P2n+3, P1 − 2P6 + P2n+4, P8 − 2P7 + P2n+5, P2n+6 − 2P2n+7 + P2n+8, P2n+2 − 2P2n+6 + P2n+7, P2n+2 − 2P2n+3 + P2n+4, P2n+3 − 2P2n+4 + P2n+5}} = max{αi : i = 1,..., 2n + 10} . (1) For a regular patch (n = 4), there are only two second order differences with the form P2i − 2P1 + P2((i+1)%n+1). Thus, the second order norm of a regular patch is defined as the maximum norm of 16 second order differences. By performing a Catmull-Clark subdivision on Π, one gets 2n+17 new vertices P1 i , i = 1,..., 2n + 17 (see Fig. 2b), which are called the level-1 control points of S. All these level-1 control points compose the level-1 control mesh of S: Π1 = {P1 i : i = 1, 2,..., 2n + 17}. We use Pk i and Πk to represent the level-k control points and level-k control mesh of S, respectively, after applying k subdivision steps to Π. The level-1 control points form four control point sets Π1 0, Π1 1, Π1 2 and Π1 3, corresponding to the control meshes of the subpatches S1 0, S1 1, S1 2 and S1 3, respectively (see Fig.2b), where Π1 0 = {P1 i : 1 ≤ i ≤ 2n + 8}, and the other three control point sets Π1 1, Π1 2 and Π1 3 are shown in Fig. 3. The subpatch S1 0 is an extraordinary patch, but S1 1, S1 2 and S1 3 are regular patches. Following the notation in Eq. (1), one can define the second order norms M1 i for S1 i , i = 0, 1, 2, 3, respectively. M1 = max{M1 i : i = 0, 1, 2, 3} is defined as the 5
ACCEPTED MANUSCRIPT P时P时PP吗 P吗PaPPinppin p以gaga+Paa中 FigControl pots of the bte ≤(a),k≥0 M*≤rm)ir,k≥0 derived by Cheu 3 Regular patches Isreguar CCSS patch.then S()can be expressed asafo
ACCEPTED MANUSCRIPT ACCEPTED MANUSCRIPT P1 2n+13P1 2n+12P1 2n+11P1 2n+10P1 2n+9 P1 2n+5P1 2n+4P1 2n+3P1 2n+2P1 2n+14 P1 7 P1 6 P1 5 P1 2n+6P1 2n+15 P1 8 P1 1 P1 4 P1 2n+7P1 2n+16 P1 2 P1 3 P1 2n+8P1 Π1 2n+17 1 Π1 3 Π1 2 v u Fig. 3. Control points of the subpatches S1 1, S1 2 and S1 3. second order norm of the level-1 control mesh Π1. After k steps of subdivision on Π, one gets 4k control point sets Πk i : i = 0, 1,..., 4k − 1 corresponding to the 4k subpatches Sk i : i = 0, 1,..., 4k − 1 of S, with Sk 0 being the only level-k extraordinary patch (if n = 4). We denote the second order norms of Πk i and Πk as Mk i and Mk, respectively. The second order norms Mk 0 and M0 satisfy the following inequality (Cheng et al., 2006; Chen and Cheng, 2006; Huang and Wang, 2007): Mk 0 ≤ rk(n)M0 , k ≥ 0 , (2) where rk(n) is called the k-step convergence rate of second order norm, which depends on n, the valence of the extraordinary vertex, and r0(n) ≡ 1. Furthermore, it follows that Mk ≤ rk(n)M0 , k ≥ 0 . An expression for the one-step convergence rate r1(n) was derived by Cheng et al. (2006) with a direct decomposition method. The multi-step convergence rate rk(n) was introduced and estimated by Chen and Cheng (2006) with a matrix based technique, then improved by Huang and Wang (2007) with an optimization based approach. 3 Regular patches In this section, we first express a regular CCSS patch S and its corresponding limit face F in bicubic B´ezier form. Then we bound the distance between S and F by bounding the distances between their corresponding B´ezier points. If S is a regular CCSS patch, then S(u, v) can be expressed as a uniform 6
ACCEPTED MANUSCRIPT deglrCsprhnihtscoatralpoiatsaddot,theBaicrpo pounts P.follo s.)=广b,o回 (4 Po.Po,1 P0.2 P0. P20P2,P2,2P2 bio bi.:bi.z bi.s Pao Pi Pa2 Pa3 7
ACCEPTED MANUSCRIPT ACCEPTED MANUSCRIPT p3,0 F _ b3,0 p2,1 b0,0 p2,2 S p b 1,1 0,3 p0,0 F p1,2 p0,3 p0,0 p0,3 p3,0 p3,3 p1,1 p1,2 p2,1 p2,2 b0,0 b3,0 b0,3 b3,3 Fig. 4. A regular CCSS patch with its control points (solid dots), the B´ezier points (hollow dots) and the limit face. bicubic B-spline surface patch defined over the unit square Ω with control points pi,j , 0 ≤ i, j ≤ 3 as follows: S(u, v) = 3 i=0 3 j=0 pi,jN3 i (u)N3 j (v) , (3) where N3 i (u), 0 ≤ i ≤ 3 are the uniform cubic B-spline basis functions. S(u, v) can be converted into the following bicubic B´ezier form (Farin, 2002): S(u, v) = 3 i=0 3 j=0 bi,jB3 i (u)B3 j (v) , (4) where bi,j , 0 ≤ i, j ≤ 3 are the B´ezier points of S (see Fig. 4), and B3 i (u), 0 ≤ i ≤ 3 are the cubic Bernstein polynomials. The relationship between (bi,j ) and (pi,j ) is as follows: ⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ b0,0 b0,1 b0,2 b0,3 b1,0 b1,1 b1,2 b1,3 b2,0 b2,1 b2,2 b2,3 b3,0 b3,1 b3,2 b3,3 ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ = T ⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ p0,0 p0,1 p0,2 p0,3 p1,0 p1,1 p1,2 p1,3 p2,0 p2,1 p2,2 p2,3 p3,0 p3,1 p3,2 p3,3 ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ Tt , (5) 7
ACCEPTED MANUSCRIPT 1 T- andithe traspee ofT. 兰生 P2P22p} F(u.v)=(1-c)((1-w)bun+uba.ol+o[(1-u)boa+ubss F,=上上b,, eEE0二长ptha 1s可-pFal-上主u-i间l ≤，-cu)侧 Let
ACCEPTED MANUSCRIPT ACCEPTED MANUSCRIPT where T = 1 6 ⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ 1410 0420 0240 0141 ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ , and Tt is the transpose of T. 3.1 Distance bound Note that the limit points corresponding to p1,1, p2,1, p2,2 and p1,2 are b0,0, b3,0, b3,3 and b0,3, respectively. F = {b0,0, b3,0, b3,3, b0,3} is the limit face corresponding to the center mesh face F = {p1,1, p2,1, p2,2, p1,2} (see Fig. 4). The bilinear parameterization of F is F(u, v) = (1 − v)[(1 − u)b0,0 + ub3,0] + v[(1 − u)b0,3 + ub3,3] , where (u, v) ∈ Ω. Since 1 3 3 i=0 iB3 i (t) = t, we can express F(u, v) as the following bicubic B´ezier form: F(u, v) = 3 i=0 3 j=0 bi,jB3 i (u)B3 j (v) , (6) where bi,j = F(i 3 , j 3 ), 0 ≤ i, j ≤ 3 are the B´ezier points. It is obvious that b0,0 = b0,0, b3,0 = b3,0, b0,3 = b0,3, b3,3 = b3,3. Hence, for (u, v) ∈ Ω, it follows that: S(u, v) − F(u, v) = 3 i=0 3 j=0 (bi,j − bi,j )B3 i (u)B3 j (v) ≤ 3 i=0 3 j=0 bi,j − bi,jB3 i (u)B3 j (v) . (7) Let Mb = max{{bi−1,j − 2bi,j + bi+1,j : 1 ≤ i ≤ 2, 0 ≤ j ≤ 3} ∪{bi,j−1 − 2bi,j + bi,j+1 : 0 ≤ i ≤ 3, 1 ≤ j ≤ 2}} be the maximal norm of 16 second order differences of the B´ezier points of S. Then we have the following result for the pointwise distance between S(u, v) and F(u, v): 8
ACCEPTED MANUSCRIPT Lemma1Frtu.e】∈.2eae S(u.v)-F(w.o)lls 3(u(1-u)+(1-) PROOF.By direct computation.we obtain: Ib:o-5ll-(boo -2b:n+bzo)+b.-2ba+ban) +(boa-2b1+ba)+(bip-2b1 ba)] H(b03-2b1+b2)+(ban-2b21+) +a-n+bo+-g+h训 l(b:a-2ba2+baz)+(bai-2bz+ba3 )(h+bea) y-5 011d「Bgel ≤路aa 1221 e 1221 0110 B(c) Subetitung te aboveqtynto Eq.(7).webave l(u.v)-F(u.o)ll s 3(u(1-u)+o(1-v))M
ACCEPTED MANUSCRIPT ACCEPTED MANUSCRIPT Lemma 1 For (u, v) ∈ Ω, we have S(u, v) − F(u, v) ≤ 3(u(1 − u) + v(1 − v))Mb . PROOF. By direct computation, we obtain: b1,0 − b1,0 = 2 3 (b0,0 − 2b1,0 + b2,0) + 1 3 (b1,0 − 2b2,0 + b3,0) ≤ 1 3 (2(b0,0 − 2b1,0 + b2,0) + (b1,0 − 2b2,0 + b3,0)) ≤ Mb , and b1,1 − b1,1 = 2 9 [(b0,0 − 2b1,0 + b2,0)+(b0,0 − 2b0,1 + b0,2)] + 1 4 [(b0,1 − 2b1,1 + b2,1)+(b1,0 − 2b1,1 + b1,2)] + 1 6 [(b0,2 − 2b1,2 + b2,2)+(b2,0 − 2b2,1 + b2,2)] + 7 36[(b1,0 − 2b2,0 + b3,0)+(b0,1 − 2b0,2 + b0,3)] + 1 12[(b1,2 − 2b2,2 + b3,2)+(b2,1 − 2b2,2 + b2,3)] + 1 36[(b3,0 − 2b3,1 + b3,2)+(b0,3 − 2b1,3 + b2,3)] + 1 18[(b3,1 − 2b3,2 + b3,3)+(b1,3 − 2b2,3 + b3,3)] ≤ 2Mb . By symmetry, it follows that: 3 i=0 3 j=0 bi,j − bi,jB3 i (u)B3 j (v) ≤ Mb B3 0(u) B3 1(u) B3 2(u) B3 3 (u) ⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ 0110 1221 1221 0110 ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ ⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ B3 0(v) B3 1(v) B3 2(v) B3 3(v) ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ = Mb(B3 1(u) + B3 2(u) + B3 1(v) + B3 2 (v)) = 3(u(1 − u) + v(1 − v))Mb . Substituting the above inequality into Eq. (7), we have: S(u, v) − F(u, v) ≤ 3(u(1 − u) + v(1 − v))Mb . 9
ACCEPTED MANUSCRIPT This completes the proof of the lemma. :0≤t≤3,1≤1≤2 follows that。≤M. PROOF.By Eq.(5).w hae +(w,a+p1o十pz)， b=忘p++pu+pu+), bu-pa+p+号n+2p小+D+pa tfocmsthnt Iboo-2b+=(Pu-2PLa+P2o) )( ≤M e一b+bas专，te Ed子aithep金tae Theorem 3 For(,)we hve IS(a.uy-F(w.e)l5(u(1-w)+o(1-) ma8u-85分-， anb6lgthnednsaadFu,o)s
ACCEPTED MANUSCRIPT ACCEPTED MANUSCRIPT This completes the proof of the lemma. ✷ Lemma 2 For a regular CCSS patch S as defined in Eq. (3), the second order norm is M = max{{pi−1,j − 2pi,j + pi+1,j : 1 ≤ i ≤ 2, 0 ≤ j ≤ 3} ∪{pi,j−1 − 2pi,j + pi,j+1 : 0 ≤ i ≤ 3, 1 ≤ j ≤ 2}} . It follows that Mb ≤ 1 6M. PROOF. By Eq. (5), we have: b0,0 = 1 36(p0,0 + 4p1,0 + p2,0) + 1 9 (p0,1 + 4p1,1 + p2,1) + 1 36(p0,0 + 4p1,0 + p2,0) , b1,0 = 1 18(2p1,0 + p2,0) + 2 9 (2p1,1 + p2,1) + 1 18(2p1,2 + p2,2) , b2,0 = 1 18(p1,0 + 2p2,0) + 2 9 (p1,1 + 2p2,1) + 1 18(p1,2 + 2p2,2) . It follows that: b0,0 − 2b1,0 + b2,0 = 1 36(p0,0 − 2p1,0 + p2,0) +4(p0,0 − 2p1,0 + p2,0)+(p0,0 − 2p1,0 + p2,0) ≤ 1 6 M . Similarly, we have b1,0 − 2b1,1 + b1,2 ≤ 1 6M. By symmetry, the result follows. ✷ Combining Lemmas 1 and 2, we obtain a bound on the pointwise distance between S(u, v) and F(u, v): Theorem 3 For (u, v) ∈ Ω, we have S(u, v) − F(u, v) ≤ 1 2 (u(1 − u) + v(1 − v))M . In the above theorem, B(u, v) = 1 2 (u(1 − u) + v(1 − v)) is called the distance bound function of S(u, v) with respect to F(u, v). Since max (u,v)∈Ω B(u, v) = B( 1 2 , 1 2 ) = 1 4 , we have a bound on the maximal distance between S(u, v) and F(u, v) as stated in the following theorem: 10