中国科学技术大学：Bounding the Distance between a Loop Subdivision Surface and Its Limit Mesh

in KeealoopatdthaauaesLntncod.Erebod.Sab个 1 Introduction

Bounding the Distance between a Loop Subdivision Surface and Its Limit Mesh Zhangjin Huang and Guoping Wang School of Electronic Engineering and Computer Science, Peking University, Beijing 100871, China zhangjin.huang@gmail.com http://www.graphics.pku.edu.cn Abstract. Given a control mesh of a Loop subdivision surface, by push￾ing the control vertices to their limit positions, a limit mesh of the Loop surface is obtained. Compared with the control mesh, the limit mesh is a tighter linear approximation in general, which inscribes the limit surface. We derive an upper bound on the distance between a Loop subdivision surface patch and its limit triangle in terms of the maximum norm of the mixed second differences of the initial control vertices and a constant that depends only on the valence of the patch’s extraordinary vertex. A subdivision depth estimation formula for the limit mesh approximation is also proposed. Key words: Loop subdivision surfaces, Limit mesh, Error bound, Sub￾division depth 1 Introduction A subdivision surface is defined as the limit of a sequence of successively refined control meshes. In practice such as surface rendering, surface trimming and sur￾face intersection, a linear approximation (for example, a refined control mesh) is used to substitute the smooth surface. It is natural to ask the following ques￾tions: How does one estimate the error (distance) between a limit surface and its linear approximation (for instance, the control mesh)? How many steps of subdivision would be necessary to satify a user-specified error tolerance? Loop subdivision surfaces generalize the quartic three-directional box spline surfaces to triangular meshes of arbitrary topology [1]. Several works have been devoted to studying the distance between a Loop surface and its control mesh approximation [2–6]. These error estimation techniques can be classified into two classes. One is the vertex based method [2, 3], which measures the distance between the control vertices and their limit positions. In [2], Lanquetin et al. derived a wrong exponential bound which resulted in a improper subdivision depth for￾mula. In [3], Wang et al. proposed a proper exponential bound with an awkward subdivision depth estimation technique. The vertex based bounds all suffer from

2 r be of the patch's d in 5e 2 Definition and Notation the initis 2.1 Distane (.)-F(e.l

2 Z. Huang and G. Wang one problem as pointed out in [3]: they may be smaller than the actual maxi￾mal distance between the limit surface and its control mesh in some cases. The other is the patch based method [4–6], which estimates the parametric distance between a Loop surface patch and its control mesh. Wu et al. presented an ac￾curate error measure for adaptive subdivision and interference detection [4, 5]. But their estimate is dependent on recursive subdivision, thus can not be used to pre-compute the error bound after n steps of subdivision or predict the re￾cursion depth within a user-specified tolerance. In [6], Huang derived a bound in terms of the maximum norm of the mixed second differences of the initial control vertices, and a subdivision depth estimation approach. The limit mesh of a Loop surface, obtained by pushing the control vertices of its control mesh to their limit positions, has been applied in surface reconstruc￾tion [8]. The limit mesh is usually considered a better linear approximation than the corresponding control mesh. But the approximation error for Loop surfaces has not been investigated yet. Recently, an effective approach has been proposed to bound the error of the limit mesh approximation to a Catmull-Clark subdivi￾sion surface [7]. With an analogous technique, in this paper we derive a bound on the maximum distance between a Loop surface patch and its limit triangle. The bound is expressed in terms of the maximum norm of the mixed second differences of the Loop patch’s initial control mesh and a constant that depends only on the valence of the patch’s extraordinary vertex. The paper is organized as follows. Section 2 introduces some definitions and notations. In Sections 3 and 4, we derive distance bounds for regular Loop patches and extraordinary Loop 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 suggestions for future work. 2 Definition and Notation Without loss of generality, we assume the initial control mesh has been subdi￾vided at least once, isolating the extraordinary vertices so that each face is a triangle and contains at most one extraordinary vertex. 2.1 Distance Given a control mesh of a Loop subdivision surface S˜, for each interior triangle F in the control mesh, there is a corresponding limit triangle F in the limit mesh, and a corresponding surface patch S in the limit surface S˜. Obviously, the limit triangle F is the triangle formed by connecting the three corner points of S. The distance between a Loop patch S and the corresponding limit 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

2.2 Sccond Order Norm D +Pa-P P.IP.+P2-P-P✉ e+12nmwmkaP

Bounding the Distance between a Loop Surface and Its Limit Mesh 3 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 5 6 n b b b b b 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 S1 0 S1 1 S1 2 S1 3 (b) Fig. 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. where Ω is the unit triangle, S(v, w) is the Stam’s parametrization [9] of S over Ω, and F(v, w) is the linear parametrization of F over Ω. 2.2 Second Order Norm 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 extraordinary 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 : 1 ≤ i ≤ n + 9} of the n + 6 vertices of Π: M = max{kP1 + P2 − Pn+1 − P3k, {kP1 + Pi − Pi−1 − Pi+1k : 3 ≤ i ≤ n}, kP1 + Pn+1 − Pn − P2k, 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 + 9} . (1) M is also called 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 vertices 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

4 3 Regular Patch Quartie Triangular Form pSa物sR罗ata 2 我k ((.)v0]and

4 Z. Huang and G. Wang respectively (see Figure 1b), where Π1 0 = {P 1 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 regular triangular patches [9]. Following the definition in Equation (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 control 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. 3 Regular Patch In this section, both the regular Loop patch S and its corresponding limit tri￾angle F are first expressed in quartic triangular B´ezier form. Then we bound the distance between S and F by measuring the deviations between their corre￾sponding B´ezier points. 3.1 Quartic Triangular B´ezier Form 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 b b b Ω (0,0) u=1 (0,1) (1,0) w=1 v=1 Fig. 2. Control vertices of a quartic box spline patch and their ordering. If S is a regular Loop patch, then S(u, v) can be expressed as a quartic box spline patch defined by 12 control vertices pi , 1 ≤ i ≤ 12 (see Figure 2): S(v, w) = X 12 i=1 piNi(v, w), (v, w) ∈ Ω , (2) where Ni(v, w), 1 ≤ i ≤ 12 are the quartic box spline basis functions. The expressions of Ni(v, w) refer to [9]. The surface is defined over the unit triangle: Ω = {(v, w)| v ∈ [0, 1] and w ∈ [0, 1 − v]}

in 12uw Caaa创 su=∑bae.een 3) 是 o程 F(c.w)=uba hearpa F,=∑5成c回 0 ,tL-F子，》，，k之0,0≤j+≤4 are the Rzir points. sic.)-Fc.)1-)s-1(c.).8

Bounding the Distance between a Loop Surface and Its Limit Mesh 5 b b b b b b b b b b b b b b b 1 3 6 10 15 5 9 14 8 13 12 11 7 4 2 (a) u 4 4u 3 v 4u 3w 6u 2 v 2 12u 2 vw 6u 2w 2 4uv3 12uv2w 12uvw2 4uw3 v 4 4v 3w 6v 2w 2 4vw3 w 4 (b) Fig. 3. (a) Ordering of the B´ezier points of a quartic triangular B´ezier patch. (b) Quartic Bernstein polynomials corresponding to the B´ezier points. We introduce the third parameter u = 1 − v − w such that (u, v, w) forms a barycentric system of coordinates for the unit triangle. S is a quartic triangular B´ezier patch, thus S(u, v) can be written in terms of Bernstein polynomials [11]: S(u, v) = X 15 i=1 biBi(v, w), (v, w) ∈ Ω , (3) 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 between the standard representation B4 ijk(u, v, w) = 4! i!j!k! u iv jw k , i, j, k ≥ 0, i+j +k = 4 and Bi(v, w), 1 ≤ i ≤ 15 is (i, j, k) 7→ (j+k)(j+k+1) 2 + k + 1. With the algorithm developed in [10], we can get the 15 × 12 matrix T which converts from the 12 control vertices (pi) to the 15 B´ezier points (bi) (see Appendix 1). Note that F = {b1, b11, b15} is the limit triangle corresponding to the center triangle F = {p4, p7, p8} (see Figures 2 and 3). The linear parametrization of F is F(v, w) = ub1 + vb11 + wb15 , where u = 1−v−w. By the linear precision property of the Bernstein polynomials [11], we can express F(v, w) as the following quartic B´ezier form: F(v, w) = X 15 i=1 biBi(v, w) , (4) where b(j+k)(j+k+1) 2 +k+1 = F( j 4 , k 4 ), j, k ≥ 0, 0 ≤ j + k ≤ 4 are the B´ezier points. 3.2 Bounding the Distance According to the previous analysis, for (v, w) ∈ Ω, it follows that kS(v, w) − F(v, w)k = X 15 i=1 (bi − bi)Bi(v, w) ≤ X 15 i=1 kbi − bikBi(v, w) . (5)