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 < i ≤ 3 can be determined by symmetry. Then the distance bound function B1 2(u, v),(u, v) ∈ Ω can be obtained from (12). Step 4. Finally, β(n) is determined as the maximum of D1 2 (t) = B1 2(t,t),t ∈ [0,1]. Note that during the computation process of the first three steps, control points Pi,i = 1,2,...,2n+8 act as symbols and can be cancelled in the constraints of Step 3. In general, D1 2 (t) is a polynomial of degree 6, except for n = 4, D1 2 (t) = 1 4 (1−t 2). β(3) can be determined with a similar procedure. The values of β(n),3 ≤ n ≤ 50 are plotted in Figure 7. For n > 4, β(n) < β(4) = 1 4 . And for 3 ≤ n ≤ 48, β(n) strictly decreases as n increases