中国科学技术大学：Estimating Error Bounds and Subdivision Depths for Loop Subdivision Surfaces

Estimating Error Bounds and Subdivision Depths for Loop Subdivision Surfaces Zhangjin Huang Scbool of Electronic Engineering and Computer Science, Peking University,Beijing 100871,China 0ct,2007 Abstract We derive a bound on the maximal distanoe betwreen a Loop sub- division surfnce patch and its control mesh in terms of the maximum norm of the tnixed second dilferenoes of the control points and a con- stant that pemb only on the lenx of the pateh.A sulxlivisim dopth formmla is also proposed Keywords:Loop subdivision surface,control mesh.error bound,sub- division depth 1 Introduction A subdivision surfaoc is defined as the limit of a finer and finer control mesh by subdividing the mesh recursively.The Loop subdivision surface geteral izes the quartic three-directional box spline surface to triangular meshes of arbitrary topology [1]. Previons erroe estimation techniques for Loop suhdivision surfnces can be clasified into two classes. One is the vertex hnsed method 2,3,which measures the distance between the vertloes and their limit positions.Lanquetin et al.derived a wrong exponential bound and consequently a wrong subdivision depth formula [2].Wang et al.propoeed a proper exponential bound with an inefficient subdivision depth estimation technique 3 As pointed out in 3, the vertex basei bounds all sulfer Irom one proble:they iay be sanaller than the nctnnl distance in some enses. The other is the patch based method [4.5].which estimates the para- metric distanoe between a Loop surfnce patch and its control mesh.Wu ct aL.presented an accurate error measure [4,5].But their estimate is de- pendent on recursive subdivision,thus can not be used to pre-compute the

Estimating Error Bounds and Subdivision Depths for Loop Subdivision Surfaces Zhangjin Huang School of Electronic Engineering and Computer Science, Peking University, Beijing 100871, China Oct., 2007 Abstract We derive a bound on the maximal distance between a Loop sub￾division surface patch and its control mesh in terms of the maximum norm of the mixed second differences of the control points and a con￾stant that depends only on the valence of the patch. A subdivision depth formula is also proposed. Keywords: Loop subdivision surface, control mesh, error bound, sub￾division depth 1 Introduction A subdivision surface is defined as the limit of a finer and finer control mesh by subdividing the mesh recursively. The Loop subdivision surface general￾izes the quartic three-directional box spline surface to triangular meshes of arbitrary topology [1]. Previous error estimation techniques for Loop subdivision surfaces can be classified into two classes. One is the vertex based method [2, 3], which measures the distance between the vertices and their limit positions. Lanquetin et al. derived a wrong exponential bound and consequently a wrong subdivision depth formula [2]. Wang et al. proposed a proper exponential bound with an inefficient subdivision depth estimation technique [3]. As pointed out in [3], the vertex based bounds all suffer from one problem: they may be smaller than the actual distance in some cases. The other is the patch based method [4, 5], which estimates the para￾metric distance between a Loop surface patch and its control mesh. Wu et al. presented an accurate error measure [4, 5]. But their estimate is de￾pendent on recursive subdivision, thus can not be used to pre-compute the 1

error bound after several steps of subdivision or predict the recursion depth within a user-specified tolerance. Our tochniqc helongs to the latter.Based on Stam's parametrizntion 6):we derive a conservative but safe bound on the maximum distance be- tween a Loop surface patch and its control mesh.An cificient subdivision depth formula is abo given 2 Second Order Norm and Convergence Rate Without loss of grnerality,we nssume the initial trianpular control mesh has been subdivided at least once,isolating the extraordinary vertioes so that cach face is n trinngle and contains at most one ctraordinary vertex. 2.1 Distance and Second Order Norm Given a ooutrol mesh of a Loop subdivision surface S.for each interior trinngle face F in the control mesh,there is a corresponding surface patch snt山e limit surface S. 4中 4中 + (a (b) Figure 1:(a)Ordering of the coutrol vertices of an extraordinary patch S of valence n.(b)Ordering of the new control vertices (solid dots)after one step of Loop subdivision. The distence between a Loop patch S and the corresponding triangle F is definexl as the maximnun distance between S(c,w)and F(v,w),that is, max lIS(t,w)-F(v,w), le.u)cn where is the unit triangle !{(e,w)e [0,1]and w e 0.1), S(e,w)is the Stam's parametrization of S over 52,and F(e,w)is the linear pxarametrization of E over 2

error bound after several steps of subdivision or predict the recursion depth within a user-specified tolerance. Our technique belongs to the latter. Based on Stam’s parametrization [6], we derive a conservative but safe bound on the maximum distance be￾tween a Loop surface patch and its control mesh. An efficient subdivision depth formula is also given. 2 Second Order Norm and Convergence Rate Without loss of generality, we assume the initial triangular control mesh has been subdivided at least once, isolating the extraordinary vertices so that each face is a triangle and contains at most one extraordinary vertex. 2.1 Distance and Second Order Norm Given a control mesh of a Loop subdivision surface S˜, for each interior triangle face F in the control mesh, there is a corresponding surface patch S in the limit surface S˜. bc bc bc bc bc bc bc bc bc bc bc bc bc 5 6 n n+6 4 1 n+1 n+5 3 2 n+2 n+4 n+3 S = S 0 0 (a) 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 5 6 n n+6 n+12 4 1 n+1 n+5 n+11 3 2 n+2 n+10 n+4 n+3 n+7 n+9 n+8 S 1 0 S 1 1 S 1 2 S 1 3 (b) Figure 1: (a) Ordering of the control vertices of an extraordinary patch S of valence n. (b) Ordering of the new control vertices (solid dots) after one step of Loop subdivision. The distance between a Loop patch S and the corresponding triangle F is defined as the maximum distance between S(v, w) and F(v, w), that is, max (v,w)∈Ω kS(v, w) − F(v, w)k , where Ω is the unit triangle Ω = {(v, w)|v ∈ [0, 1] and w ∈ [0, 1 − v]} , S(v, w) is the Stam’s parametrization of S over Ω, and F(v, w) is the linear parametrization of F over Ω. 2

+12 rtires P!=1. he level-l coutro or of th f subdivis as the 2.2 Convergence Rate edoderoeashMgaadhfsihgyteolowitgeureeete 哈≤r,j≥0 3

The control mesh Π of a Loop patch S consists of n + 6 control vertices Π = {Pi : i = 1, 2, . . . , n + 6}, where n is the valence of F’s only extraordi￾nary vertex (if has, otherwise n = 6) and called the valence of the patch S (see Figure 1(a)). The second order norm of Π, denoted M = M0 = M0 0 , is defined as the maximum norm of the following n + 9 mixed second differences (MSDs) {αi : i ≤ i ≤ n + 9} of the n + 6 vertices of Π: M = max{kP1 + P2 − Pn+1 − P3k, {kP1 + Pi − Pi−1 − P(i−1)%n+2k : 3 ≤ i ≤ n + 1}, kP2 + Pn+1 − P1 − Pn+2k, kP2 + Pn+2 − Pn+1 − Pn+3k, kP2 + Pn+3 − Pn+2 − Pn+4k, kP2 + Pn+4 − Pn+3 − P3k, kP2 + P3 − Pn+4 − P1k, kPn+1 + Pn − P1 − Pn+6k, kPn+1 + Pn+6 − Pn − Pn+5k, kPn+1 + Pn+5 − Pn+6 − Pn+2k, kPn+1 + Pn+2 − Pn+5 − P2k} = max{kαik : i = 1, . . . , n + 6} . (1) M is also called as the (level-0) second order norm of the patch S. For a regular patch (n = 6), there are 15 mixed second differences. Through subdivision we can generate n+12 new vertices P1 i , i = 1, . . . , n+ 12 (see Figure 1(b)), which are called the level-1 control vertices of S. All these level-1 control vertices compose S’s level-1 control mesh Π1 = {P1 i : i = 1, 2, . . . , n + 12}. We use Pk i and Πk to represent the level-k control ver￾tices and level-k control mesh of S, respectively, after k steps of subdivision on Π. The level-1 control vertices form four control vertex sets Π1 0 , Π1 1 , Π1 2 and Π1 3 , corresponding to the control meshes of the subpatches S 1 0 , S 1 1 , S 1 2 and S 1 3 , respectively (see Figure 1b), where Π1 0 = {P1 i : 1 ≤ i ≤ n + 6}. The subpatch S 1 0 is an extraordinary patch, but S 1 1 , S 1 2 and S 1 3 are reg￾ular triangular patches [6]. Following the definition in Euatioin (1), one can define the second order norms M1 i for S 1 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 con￾trol point sets Πk i : i = 0, 1, . . . , 4 k − 1 corresponding to the 4k subpatches S k i : i = 0, 1, . . . , 4 k − 1 of S, with S k 0 being the only level-k extraordinary patch (if n 6= 6). We denote Mk i and Mk as the second order norms of Πk i and Πk , respectively. 2.2 Convergence Rate If second order norms Mk+j 0 and Mj 0 satisfy the following recurrence in￾equality Mk+j 0 ≤ rj (n)Mk 0 , j ≥ 0 , (2) 3

ned ini e=h2.Rt9 tee折ata花6nm 4m=ia艺hl d芝a=t =a创.n>3 rder no 4

where rj (n) is a constant which depends on n, the valence of the extraor￾dinary vertex, and r0(n) ≡ 1. We call rj (n) the j-step convergence rate of second order norm. In the following, we estimate rj (n), j ≥ 1 by solving constrained min￾imization problems. Let α k i , i = 1, 2, . . . , n + 9 be the MSDs of Πk 0 , k ≥ 0 defined as in Equation (1). For each l = 1, 2, . . . , n + 9, we can express α k+1 l as a linear combination of α k i : α k+1 l = nX +9 i=1 x l iα k i , where x l i , i = 1, 2, . . . , n + 9 are undetermined real coefficients. It follows that kα k+1 l k ≤ nX +9 i=1 kx l iα k i k ≤ nX +9 i=1 |x l i |kα k i k ≤ nX +9 i=1 |x l i |Mk 0 . Then we can bound kα k+1 l k by cl(n)Mk 0 , where cl(n) is the solution of the following constrained minimization problem: cl(n) = min nX +9 i=1 |x l i | , s.t. nX +9 i=1 x l iα k i = α k+1 l . (3) Since Mk+1 0 = max{kα k+1 l k : 1 ≤ l ≤ n + 9}, we get an estimate for r1(n) as follows: r1(n) = max 1≤l≤n+9 cl(n) . By symmetry, we only need to solve at most four constrained mini￾mization problems corresponding to α k+1 1 = P k+1 1 + P k+1 2 − P k+1 n+1 − P k+1 3 , α k+1 n+1 = P2 + Pn+1 − P1 − Pn+2, α k+1 n+2 = P2 + Pn+2 − Pn+1 − Pn+3, and α k+1 n+3 = P2 + Pn+3 − Pn+2 − Pn+4, respectively. Since P k+1 1 is the extraor￾dinary vertex, it is not surprising to find out that c1(n) is the maximum for n > 3. The special case is r1(3) = c4(3) = 0.4375 > c1(3) = 0.3125. Then it follows that r1(n) = c1(n), n > 3 . Similarly, we can estimate rj (n), n ≥ 3, j > 1 by solving only one constrained minimization problem (3) with α k+1 1 replaced by α k+j 1 . Table 1 shows the convergence rates of the second order norm for 3 ≤ n ≤ 10. The convergence rate rj (6) = ( 1 4 ) j is sharp for regular patches. 4

Table 1:Comvergeace rates r)12.3 8 0 3 Distance Bound 3.1 Regular Patch (a} b e quartic box spline basis functions.The 5,-∑h,m (5

Table 1: Convergence rates ri(n), i = 1, 2, 3 n 3 4 5 6 7 8 9 10 r1(n) 0.437500 0.382813 0.540907 0.250000 0.674025 0.705136 0.726355 0.741711 r2(n) 0.082031 0.142700 0.258367 0.062500 0.372582 0.402608 0.424000 0.439960 r3(n) 0.020752 0.053148 0.118899 0.015625 0.197695 0.219995 0.236377 0.248872 3 Distance Bound 3.1 Regular Patch b b b b b b b b b 2 5 9 b b b 1 4 8 12 3 7 11 6 10 S (a) b b b Ω (0,0) u=1 (0,1) (1,0) w=1 v=1 (b) Figure 2: (a) Control vertices of a quartic box spline patch and their order￾ing. (b) Parameter domain Ω = {(v, w)|v ∈ [0, 1] and w ∈ [0, 1 − v]} with the third parameter u = 1 − v − w. If S is a regular Loop patch, then S(v, w) can be expressed as a quartic box spline patch defined over the unit triangle Ω with control vertices pi , 1 ≤ i ≤ 12 (see Figure 2) as follows: S(v, w) = X 12 i=1 piNi(v, w) , (4) where Ni(v, w), 1 ≤ i ≤ 12 are the quartic box spline basis functions. The expressions of Ni(v, w) refer to [6]. S is also a quartic triangular B´ezier patch, thus S(v, w) can be written in terms of Bernstein polynomials [8]: S(v, w) = X 15 i=1 biBi(v, w) , (5) where bi , 1 ≤ i ≤ 15 are the B´ezier points of S, and Bi(v, w), 1 ≤ i ≤ 15 are the quartic Bernstein polynomials (see Figure 3). The correspondence 5