Distance Between a Catmull-Clark Subdivision Surface and Its Limit Mesh t eggeai o the of th 肉 ea of the d.sb The Ca e 781B 2 Definition and notation 2.1 Distances a
Distance Between a Catmull-Clark Subdivision Surface and Its Limit Mesh Zhangjin Huang∗ Peking University Guoping Wang† Peking University Abstract In geometry processing a refined control mesh is often used to approximate a Catmull-Clark subdivision surface (CCSS). By pushing the control points to their limit positions, a limit mesh of the subdivision surface is obtained. We present 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. The bound shows that the limit mesh may approximate the limit surface better than the corresponding control mesh in general. Consequently, for a given error tolerance, fewer subdivision steps are needed if the refined control mesh is replaced with the corresponding limit mesh. CR Categories: I.3.5 [Computer Graphics]: Computational Geometry and Object Modeling—Curve, surface, solid and object representations Keywords: Subdivision surfaces, limit mesh, distance bound, subdivision depth 1 Introduction The Catmull-Clark subdivision surface (CCSS) was designed to generalize the bicubic B-spline surface to the 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 piecewise 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 to estimate the error (distance) between a CCSS and its approximation (for instance, the control mesh)? 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 numbers of mesh faces with successive subdivisions, one more or less step may make a great difference in mesh density. And subdivision depth (step) estimation relies on the approximation representation and its error estimate. The bounds on the maximal distance between a CCSS patch and its control mesh in terms of the maximum norm of the second order differences (called second order norm) of the control points have been studied in [Cheng and Yong 2006; Cheng et al. 2006; Chen and Cheng 2006; Huang et al. 2006]. Though some techniques such as matrix based [Chen and Cheng 2006] and optimization based [Huang et al. 2006] are adopted to improve the distance ∗e-mail: hzj@graphics.pku.edu.cn †e-mail: wgp@graphics.pku.edu.cn estimate, for an extraordinary CCSS patch, the subdivision depth for a given error tolerance is still very large. Another piecewise linear approximation to a subdivision surface, obtained by pushing the control points 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 been investigated yet. 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 of the CCSS, which inscribes the limit surface (see Figure 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 than the control mesh approximation. The paper is organized as follows. Section 2 introduces some definitions and notations. In Section 3 and Section 4, we derive bounds for regular CCSS patches and extraordinary CCSS patches, respectively. And a subdivision depth estimation method for the limit mesh approximation is presented in Section 5. In Section 6, we compare the limit mesh approximation with the control mesh approximation. Finally we conclude the paper with some future works. 2 Definition and notation Without loss of generality, we assume the initial control mesh has been subdivided at least once or twice, isolating the extraordinary vertices so that each face is a quadrilateral and contains at most one extraordinary vertex. 2.1 Distances Figure 1: A Catumull-Clark subdivision surface, its control mesh and the corresponding limit mesh
g如60aa五 2+2 1 点Isu,-fal 2.2 Second order norm ✉
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˜. Obviously, the limit face F is a quadrilateral formed by connecting the four corner points of the patch S. 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 parametrization of the corresponding limit face F over Ω. For (u, v) ∈ Ω, we denote by S(u, v) − F(u, v) 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 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) Figure 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. 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 J. Stam’s fashion [Stam 1998] (Figure 2(a)). The second order norm of Π (or S), denoted by M = M0 = M0 0 , is defined as the maximum norm of the following 2n + 10 second order differences (SODs) {αi : i = 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 as P2i −2P1 +P2((i+1)%n+1). Then the second order norm of a regular patch is defined as the maximum norm of 16 second order differences. P1 2n+13 P1 2n+12 P1 2n+11 P1 2n+10 P1 2n+9 P1 2n+5 P1 2n+4 P1 2n+3 P1 2n+2 P1 2n+14 P1 7 P1 6 P1 5 P1 2n+6 P1 2n+15 P1 8 P1 1 P1 4 P1 2n+7 P1 2n+16 P1 2 P1 3 P1 2n+8 P1 Π1 2n+17 1 Π1 3 Π1 2 v u Figure 3: Control points of the subpatches S1 1,S1 2 and S1 3 By performing a Catmull-Clark subdivision step on Π, one gets 2n+17 new vertices P1 i ,i = 1,...,2n+17 (see Figure 2(b)), 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 Figure 2(b)), 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 Figure 3. S1 0 is an extraordinary patch, but S1 1,S1 2 and S1 3 are regular patches. Following the notation in Equation (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 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 by Mk i and Mk the second order norms of Πk i and Πk, respectively.
Chm e Ch am Chn 3.1 Distance bound ,y-0-1-ha+h+(1-hs+ab u,-立5，m. 3 Regular patches 应产53e 风e-u-22y s立立y-,oj ne -- Ibia-5iall(bue-2hin+haa)+(+) 安-- sc.-). )+(bau-2ba+b +1-h11+21}+1.0-2b1,1+b12 +001-2h11+hmz}+bn0-2b1+b3j川 厨剑 +[b1D-2h2a+ba+b1-2h2+h) +(b:3-2b:3+bx3)+(bz.:+hz.) -用 0-+b]+-2h3+h
The second order norms Mk 0 and M0 satisfy the following inequality [Cheng et al. 2006; Chen and Cheng 2006; Huang et al. 2006]: 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. The expression of one-step convergence rate r1(n) was derived in [Cheng et al. 2006] with a direct decomposition method. Multistep convergence rate rk(n) was introduced and estimated in [Chen and Cheng 2006] with a matrix based technique, then improved in [Huang et al. 2006] with an optimization based approach. 3 Regular patches u v (0,0) (1,1) Ω p0,0 p0,3 p3,0 p3,3 p1,1 p1,2 p2,1 p2,2 b0,0 b3,0 b0,3 b3,3 Figure 4: An uniform bicubic B-spline surface patch with its control points and the Bezier points ´ If S is a regular CCSS patch, then S(u, v) can be expressed as an uniform 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 Bezier ´ 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 Bezier points of ´ S (see Figure 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) 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, p1,2 are b0,0, b3,0, b3,3, 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 Figure 4). The bilinear parametrization 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 Bezier form: ´ F(u, v) = 3 ∑ i=0 3 ∑ j=0 bi, jB3 i (u)B3 j(v), (6) where b¯i, j = F( i 3 , j 3 ),0 ≤ i, j ≤ 3 are the Bezier 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 Bezier ´ points of S. Then we have the following result on the pointwise distance between S(u, v) and F(u, v): 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 tha hio2amarCcSsaisamh al. w到 7 二度+ mex IS(a.v]-F(o.v)sM k 4 Extraordinary patches Then at e≤表M Prof.By (5 bpo=(Ppo+4pua+P20)+(pu1+4p1.:+Pz: n一8pa+pm+号p1+p+p2+2p Then it followst 1bo0 2b1e b:ol -l(po0 2pLo p2ok +pa-2pLn+p防m+西n-2p1P2l -司 叫- s-Fas-tW- s￥a-位，可-u,) sformtiun maps the tikonto the unitsqu 明=的-1 1-小= e
By symmetry, it follows that 3 ∑ i=0 3 ∑ j=0 bi, j −bi, jB3 i (u) ≤ Mb B3 0(u) B3 0(u) B3 0(u) B3 0(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 (7), we have S(u, v)−F(u, v) ≤ 3(u(1−u) +v(1−v))Mb. This completes the proof of the theorem. Lemma 2 For a regular CCSS patch S as defined in (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}}. Then it follows that Mb ≤ 1 6M. Proof. By (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) Then 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 Lemma 1 and 2, we obtain a bound on the pointwise distance between S(u, v) and F(u, v): Theorem 1 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). By symmetry, the maximum of B(u, v),(u, v) ∈ Ω must occur on the diagonal D(t) = B(t,t) = t(1−t),0 ≤ t ≤ 1. Since max 0≤t≤1 t(1−t) = 1 4 , we have a bound on the maximal distance between S(u, v) and F(u, v) as stated in the following theorem: Theorem 2 The distance between a regular CCSS patch S and the corresponding limit face F is bounded by max (u,v)∈Ω S(u, v)−F(u, v) ≤ 1 4 M. Remark 1 The distance between a regular patch S and its corresponding center mesh face F is bounded as [Cheng and Yong 2006]: max (u,v)∈Ω S(u, v)−F(u, v) ≤ 1 3 M. Theorem 2 shows that the limit mesh can approximate an uniform bicubic B-spline surface better than the corresponding control mesh in general. 4 Extraordinary patches Ω1 1 Ω1 Ω 2 1 3 Ω2 1 Ω2 Ω 2 2 3 Ω3 1 Ω3 2 Ω3 3 u v Figure 5: Ω-partition of the unit square. An extraordinary CCSS patch S can be partitioned into an infi- nite sequence of uniform bicubic B-spline patches {Sk m}, k ≥ 1,m = 1,2,3 [Stam 1998]. If we partition the unit square Ω into an infinite set of tiles {Ωk m}, k ≥ 1,m = 1,2,3, (see Figure 5), with Ωk 1 = 1 2k , 1 2k−1 × 0, 1 2k , Ωk 2 = 1 2k , 1 2k−1 × 1 2k , 1 2k−1 , Ωk 3 = 0, 1 2k × 1 2k , 1 2k−1 , each tile Ωk m corresponds to a B-spline patch Sk m. Sk m(u, v) is de- fined over the unit square with the form as (3). Therefore, the parametrization for S(u, v) is constructed as follows: S(u, v) |Ωk m= Sk m(u˜, v˜) = Sk m(t k m(u, v)), where the transformation t k m maps the tile Ωk m onto the unit square Ω: t k 1(u, v)=(2ku−1,2kv), t k 2(u, v)=(2ku−1,2kv−1) and t k 3(u, v)=(2ku,2k v−1). The center face of S’s control mesh is F = {P1,P6,P5,P4} (see Figure 2). The corresponding limit face is F = {P1,P6,P5,P4}
eofL P be th Consequently.it follows from(h -0--+园+1-g+ 民a,明-ga,≤aM,g∈R an是Pcan bep Fia.v)loe=P(t(m.v)). Hr&is the hilingar natch defined as 第=-I-÷a-+ where iu,∈ett=lw.lx Ivpril Th =之=123 da Dau3ncaa胖CSS a小-1≤ 13到 ≤三三k,-5,io of the 4.1 Diatance bound 1.If n=3,r)scains its n %2e y--岂4 的二 1之…2a+0m Au-5s2"时a1s2I4ls2"w nethe n(a,以，(u,∈ean e roblems with The furm
with Pi being the limit point of Pi,i = 1,4,5,6. Let F(u, v) be the bilinear parametrization of F: F(u, v)=(1−v)[(1−u)P1 +uP6] +v[(1−u)P4 +uP5], (8) where (u, v) ∈ Ω. The limit face F can be partitioned into subfaces defined over Ωk m as follows F(u, v) |Ωk m= F k m(t k m(u, v))). Here F k m is the bilinear patch defined as F k m(u, v)=(1−v)[(1−u)b0,0 +ub3,0] +v[(1−u)b0,3 +ub3,3], (9) where (u, v) ∈ Ω. Let Ωk m = [u0,u1]×[v0, v1]. Then b0,0 = F(u0, v0), b3,0 = F(u1, v0), b0,3 = F(u0, v1), b3,3 = F(u1, v1). Similar to the analysis in Section 3, we can rewrite Sk m(u, v) and F k m(u, v) into the bicubic Bezier forms as (4) and (6), respectively. ´ Thus for (u, v) ∈ Ωk m, we have S(u, v)−F(u, v) = Sk m(u˜, v˜)−F k m(u˜, v˜) ≤ 3 ∑ i=0 3 ∑ j=0 bi, j −bi, jB3 i (u˜)B3 j(v˜). (10) Notice that F k m is not the limit face of the B-spline patch Sk m but one portion of the extraordinary patch S’s limit face F. So we can not use the results for bi, j −bi, j derived in Section 3. 4.1 Distance bound Since bi, j and bi, j,0 ≤ i, j ≤ 3 are the convex combinations of the control points Pi,i = 1,2,...,2n + 8. Then bi, j − bi, j can be expressed as the linear combinations of 2n + 10 SODs αl,l = 1,2,...2n+10 defined in (1): bi, j −bi, j = 2n+10 ∑ l=1 x i, j l αl, where x i, j l ,l = 1,2,...,2n + 10 are undetermined real coefficients. It follows that bi, j −bi, j ≤ 2n+10 ∑ l=1 x i, j l αl ≤ 2n+10 ∑ l=1 |x i, j l |αl ≤ 2n+10 ∑ l=1 |x i, j l |M. Therefore, to get a tight upper bound for bi, j −bi, j, we solve the following constrained minimization problem: ci, j = min 2n+10 ∑ l=1 |x i, j l | s.t. 2n+10 ∑ l=1 x i, j l αl = bi, j −bi, j. (11) By solving 16 constrained minimization problems with the form as (11), we have bi, j −bi, j ≤ ci, jM, 0 ≤ i, j ≤ 3. Consequently, it follows from (10) that Sk m(u, v)−F k m(u, v) ≤ Bk m(u, v)M, (u, v) ∈ Ω where the bicubic Bezier function ´ Bk m(u, v) = 3 ∑ i=0 3 ∑ j=0 ci, jB3 i (u)B3 j(v), (u, v) ∈ Ω (12) is the distance bound function of Sk m(u, v) with respect to F k m(u, v). Then the distance bound function of S(u, v) with respect to F(u, v), B(u, v),(u, v) ∈ Ω, can be defined as follows: B(u, v) |Ωk m= Bk m(t k m(u, v)), k ≥ 1,m = 1,2,3. By symmetry, the maximum of B(u, v) must occur on the diagonal D(t) = B(t,t),t ∈ [0,1]. It is obvious that D(0) = D(1) = 0. Let β(n) = maxt∈[0,1] D(t), we have the following theorem on the maximal distance between S(u, v) and F(u, v): Theorem 3 The distance between an extraordinary CCSS patch S and the corresponding limit face F is bounded by max (u,v)∈Ω S(u, v)−F(u, v) ≤ β(n)M, (13) where β(n) is a constant that depends only on the valence of the extraordinary point of S. With existence of the extraordinary point, it is nearly impossible to derive an analytical expression for D(t). For 3 ≤ n ≤ 50, by plotting the graph of D(t) and analyzing D(t),t ∈ [ 1 4 ,1] (see Figure 6), we find out the following facts: 1. If n = 3, D(t) attains its maximum in the interval [ 1 4 , 1 2 ]. 2. If n ≥ 4, D(t) attains its maximum in the interval [ 1 2 ,1]. Therefore, we have the following algorithm to determine the constants β(n),n ≥ 4: Step 1. Compute the control points pi, j,0 ≤ i, j ≤ 3 of S1 2 as described in Subsection 2.2, then determine the Bezier points ´ bi, j,0 ≤ i, j ≤ 3 of S1 2 according to (5). Step 2. Calculate the limit points of P1,P4,P5,P6, and determine the expression of F 1 2 according to (8) and (9). Then compute the Bezier points ´ bi, j,0 ≤ i, j ≤ 3 of F 1 2 as explained in Subsection 3.1. Step 3. Solve 10 constrained minimization problems with the form as (11) to get the bound constants ci, j,0 ≤ i ≤ j ≤ 3. The rest 6 constants ci, j,0 ≤ j 4, β(n) < β(4) = 1 4 . And for 3 ≤ n ≤ 48, β(n) strictly decreases as n increases
2"高oam ( 二A04n6-2 母W-a,1≤4Msn(mwe1e1,23 Then it follows that n/盆 (-Fv m(B)im . 0508740=0.24312 + da-1mA10-545-2273 在920e女ine9e =s(（me）l.0sea-l2 B (n 6 Comparison 10203040504 he d Figure7:Gnph of(a以3≤n≤50 14 5 Subdivision depth estimation c-m两器得21
0.25 0.5 0.75 1 t 0.05 0.1 0.15 0.2 0.25 t 0.25 0.5 0.75 t 1 0.75 0.5 0.25 0.25 0.5 't (a) n = 3, β(3) = D(0.493683) = 0.258146 0.25 0.5 0.75 1 t 0.05 0.1 0.15 0.2 0.25 t 0.25 0.5 0.75 t 1 0.8 0.6 0.4 0.2 0.2 0.4 't (b) n = 4, β(4) = D(0.5) = 0.25 0.25 0.5 0.75 1 t 0.05 0.1 0.15 0.2 t 0.25 0.5 0.75 t 1 0.8 0.6 0.4 0.2 0.2 0.4 't (c) n = 5, β(5) = D(0.508746) = 0.243129 0.25 0.5 0.75 1 t 0.05 0.1 0.15 0.2 t 0.25 0.5 0.75 t 1 0.8 0.6 0.4 0.2 0.2 't (d) n = 10, β(10) = D(0.545068) = 0.222738 Figure 6: Graphs of D(t),t ∈ [ 1 256 ,1] and the derivatives D (t),t ∈ [ 1 4 ,1], n = 3,4,5,10. 10 20 30 40 50 n 0.2 0.21 0.22 0.23 0.24 0.25 Βn Figure 7: Graph of β(n), 3 ≤ n ≤ 50. 5 Subdivision depth estimation Given an error tolerance ε > 0, the subdivision depth of a CCSS patch S with respect to ε is a positive integer d such that if the control mesh of S is recursively subdivided d times, the distance between the resulting limit mesh and S is smaller than ε. The distance between an extraordinary CCSS patch S(u, v) and its level-1 limit mesh can be expressed as max i=0,1,2,3 max (u,v)∈Ω S1 i (u, v)−F1 i (u, v), where S1 i ,i = 0,1,2,3 are the level-1 subpatches of S as described in Subsection 2.2, and F1 i are the limit faces corresponding to S1 i ,i = 0,1,2,3, respectively. It is easy to see that max (u,v)∈Ω S1 0(u, v)−F1 0(u, v) ≤ β(n)M1 0 ≤ β(n)r1(n)M0, max (u,v)∈Ω S1 i (u, v)−F1 i (u, v) ≤ β(4)M1 i ≤ 1 4 r1(n)M0, i = 1,2,3. Then it follows that max i=0,1,2,3 max (u,v)∈Ω S1 i (u, v)−F1 i (u, v) ≤ max{β(n), 1 4 }r1(n)M0. Because of the properties of rj(n), j ≥ 0, the distance between an extraordinary CCSS patch S(u, v) and its level-k limit mesh is bounded by max i=0,1,...,4k−1 max (u,v)∈Ω Sk i (u, v)−Fk i (u, v) ≤ max{β(n), 1 4 }rk(n)M0. Similar to the derivation in [Huang et al. 2006], we have the following subdivision depth estimation theorem for CCSS patches. Theorem 4 Given a CCSS patch S and an error tolerance ε > 0, after k = min 0≤j≤a−1 alj + j steps of subdivision on the control mesh of S, the distance between S and its level-k limit mesh is smaller than ε. Here, lj = log 1 ra(n) rj(n)max{β(n), 1 4 }M ε , 0 ≤ j ≤ a−1,a ≥ 1. Especially, for regular CCSS patches, k = log4 M 4ε . For an extraordinary CCSS patch with n > 4, since β(n) < 1 4 , lj is simplified as log 1 ra(n) rj(n)M 4ε . 6 Comparison Both a control mesh and its corresponding limit mesh can be employed to approximate a CCSS in practical applications. This section compares these two approximation representations. The distance between an CCSS patch S and its control mesh is bounded as [Cheng et al. 2006; Chen and Cheng 2006; Huang et al. 2006]: max (u,v)∈Ω S(u, v)−F(u, v) ≤ Ca(n)M. (14) And Ca(n) can be unified as [Huang et al. 2006] Ca(n) = 1 min{n,8} ∑a−1 j=0 rj(n) 1−ra(n) , a ≥ 1. The case of a = 1 corresponds to the result proposed in [Cheng et al. 2006], and the case of a = 2 is exactly the result presented in [Chen and Cheng 2006]. The distance estimates (13) and (14) are both expressed in terms of M, the second order norm of S, and some constants that depend on n, the valence of the only extraordinary point of S.
于 空围 =a肥叫+五 whcrc -e克(o恤l,a<i区a-lw≥1 Acknowledgement 0<()-oe(0)=< References 之 AND C CQCA8 7 Conclusion aeeeamtganan h地C
Table 1: Comparison of β(n) and Ca(n), 3 ≤ n ≤ 10 n C1(n) C2(n) β(n) 3 1.000000 0.784314 0.784314 0.258146 4 0.333333 0.333333 0.333333 0.250000 5 0.714286 0.574890 0.574890 0.243129 6 0.705882 0.642267 0.549020 0.237454 7 0.717949 0.527357 0.527357 0.232761 8 0.695652 0.582436 0.424242 0.228848 9 0.736364 0.510181 0.510181 0.225549 10 0.757576 0.678442 0.519591 0.222738 Table 1 illustrates the comparison results of the constants β(n), C1(n), and C2(n) for 3 ≤ n ≤ 10. The values of C2(n) in the 3rd and 4th columns are computed with the techniques proposed in [Chen and Cheng 2006] and [Huang et al. 2006] respectively. It can be seen that Ca(4) = 1 3 is the smallest of Ca(n),n ≥ 3 but β(4) = 1 4 is the biggest of β(n),n ≥ 4. β(n) 0, the subdivision depth estimation formula for the control mesh approximation is expressed as follows [Huang et al. 2006]: k = min 0≤j≤a−1 alj + j, where lj = log 1 ra(n) rj(n)Ca(n)M ε , 0 ≤ j ≤ a−1, a ≥ 1. The cases of a = 1 and a = 2 correspond to the formulas derived in [Cheng et al. 2006] and [Chen and Cheng 2006], respectively. For regular patches, k = log4 M 3ε . Although β(n) is much smaller than Ca(n), the convergence rates of second order norm, rk(n),0 ≤ k ≤ a, play the major role in subdivision depth estimation. For example, 0 < log4 M 3ε −log4 M 4ε = log4 4 3 < 1 means that for regular CCSS patches, to satisfy the same error tolerance the control mesh approximation needs at most one more subdivision step than the limit mesh approximation. Notice that at each subdivision step, the number of quadrilaterals quadruples. One less step implies that the number of faces in the limit mesh approximation may be a quarter of the number in the control mesh approximation. Table 2 shows the comparison results of subdivision depthes. The error tolerance ε is set to 0.01, and the second order norm M is assumed to be 2. The first three rows are the results in the case of control mesh approximation, computed with the direct decomposition method [Cheng et al. 2006], the matrix based technique [Chen and Cheng 2006], and the optimization based approach [Huang et al. 2006], respectively. The last row is the depthes in the limit mesh approximation. As can be seen from the table, the limit mesh approximation has a 30%–50% improvement over the control mesh approximation in most of the cases. 7 Conclusion In this paper the distance (error) between a CCSS and its limit mesh is investigated. By introducing a distance bound function, we Table 2: Comparison of subdivision depthes n 3 4 5 6 7 8 9 10 [Cheng et al. 2006] 14 4 16 19 23 26 27 28 [Chen and Cheng 2006] 9 4 11 16 14 18 16 22 [Huang et al. 2006] 9 4 11 13 14 13 16 17 limit mesh approx. 6 3 8 10 11 11 12 12 present 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 on the valence of the CCSS patch’s only extraordinary point. A subdivision depth estimation formula for a CCSS patch is also proposed. In general, a limit mesh approximates the limit surface better than the corresponding control mesh. This means that, compared with the control mesh approximation, the limit mesh approximation has a smaller subdivision depth for a given error tolerance. The test results show that the limit mesh approximation improves the control mesh approximation by about 30%–50% in most of the cases. This is a considerable improvement because of the exponential nature of the subdivision process. Our analysis techniques can be extended to other spline based subdivision surfaces, such as Doo-Sabin subdivision surfaces [Doo and Sabin 1978] and Loop subdivision surfaces [Loop 1987], etc. We will explore them in a forthcoming paper. Acknowledgement We are greatly indebted to Prof. Jiansong Deng and Lily Hu for their support and suggestions. This work was supported by the 973 Program of China (2004CB719403), NSF of China (60573151), and China Postdoctoral Science Foundation (20060390359). References CATMULL, E., AND CLARK, J. 1978. Recursively generated Bspline surfaces on arbitrary topological meshes. Computer-Aided Design 10, 6, 350–355. CHEN, G., AND CHENG, F. 2006. Matrix based subdivision depth computation for extra-ordinary Catmull-Clark subdivision surface patches. In Proceedings of GMP 2006 (LNCS 4077), 545– 552. CHENG, F., AND YONG, J. 2006. Subdivision depth computation for Catmull-Clark subdivision surfaces. Computer Aided Design & Applications 3, 1–4, 485–494. CHENG, F., CHEN, G., AND YONG, J. 2006. Subdivision depth computation for extra-ordinary Catmull-Clark subdivision surface patches. In Proceedings of CGI 2006 (LNCS 4035), 404– 416. DOO, D., AND SABIN, M. A. 1978. Behaviour of recursive subdivision surfaces near extraordinary points. Computer-Aided Design 10, 6, 356–360. FARIN, G. 2002. Curves and Surfaces for Computer-Aided Geometric Design — A Practical Guide, fifth ed. Morgan Kaufmann Publishers
仁gma5tmar
HALSTEAD, M., KASS, M., AND DEROSE, T. 1993. Efficient, fair interpolation using Catmull-Clark surfaces. In Proceedings of SIGGRAPH 93, ACM, 35–44. HOPPE, H., DEROSE, T., DUCHAMP, T., HALSTEAD, M., JIN, H., MCDONALD, J., SCHWEITZER, J., AND STUETZLE, W. 1994. Piecewise smooth surface reconsruction. In Proceedings of SIGGRAPH 94, ACM, 295–302. HUANG, Z., WANG, G., AND YUE, W. 2006. Optimization based subdivision depth computation for extra-ordinary CatmullClark subdivision surface patches. Submitted, available at http://graphics.pku.edu.cn/hzj. LOOP, C. T. 1987. Smooth subdivision surfaces based on triangles. Master’s thesis, Department of Mathematics, University of Utah. STAM, J. 1998. Exact evaluation of Catmull-Clark subdivision surfaces at arbitrary parameter values. In Proceedings of SIGGRAPH 98, Annual Conference Series, ACM, 395–404
