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

Bounding the Distance between a Loop Subdivision Surface and Its Limit Mesh Zhangjin Huang Guoping Wang HCI Multimedia Lab Peking University,P.R.China

Bounding the Distance between a Loop Subdivision Surface and Its Limit Mesh Zhangjin Huang Guoping Wang HCI & Multimedia Lab Peking University, P.R. China

Loop subdivision surface 89 Loop subdivision surface (Loop 1987) a generalization of quartic three-directional box spline surface to triangular meshes of arbitrary topology C2continuous except at extraordinary points the limit of a sequence of recursively refined (triangular) control meshes initial mesh step 1 limit surface

Loop subdivision surface Loop subdivision surface (Loop 1987) „ a generalization of quartic three-directional box spline surface to triangular meshes of arbitrary topology ‡ continuous except at extraordinary points „ the limit of a sequence of recursively refined (triangular) control meshes 2 C initial mesh step 1 limit surface

U N I Linear approximations 89了 Linear approximations of a Loop surface are used in surface rendering,numerical control tool-path generation,etc Two linear approximations: control mesh (refined)control mesh limit mesh:obtained by pushing the control points of a control mesh to their limit positions It inscribes the limit surface limit mesh

Linear approximations Linear approximations of a Loop surface are used in surface rendering, numerical control tool-path generation, etc Two linear approximations: „ (refined) control mesh „ limit mesh: obtained by pushing the control points of a control mesh to their limit positions ‡ It inscribes the limit surface control mesh limit mesh

Problems of limit mesh approx. Approximation error How to estimate the error(distance) between a Loop surface and its limit mesh? Subdivision depth estimation How many steps of subdivision would be necessary to satisfy a user-specified error tolerance?

Problems of limit mesh approx. ‡ Approximation error „ How to estimate the error (distance) between a Loop surface and its limit mesh? ‡ Subdivision depth estimation „ How many steps of subdivision would be necessary to satisfy a user-specified error tolerance?

Distance (error) 89 Each surface patch S corresponds to a limit triangle F in its limit mesh F is formed by connecting the three corners of S Distance (error)between a patchs and the limit mesh is defined as maS0）-F,w S(v,w):Stam's parameterization of S F(v,w):linear parameterization ofF ■2：the unit triangle 2={(y,w)p∈[0,1，o∈[0,1-

Distance (error) Each surface patch corresponds to a limit triangle in its limit mesh „ is formed by connecting the three corners of Distance (error) between a patch and the limit mesh is defined as „ : Stam’s parameterization of „ : linear parameterization of „ : the unit triangle S(, ) v w Ω Ω = ∈ ω∈ − {( , ) [0,1], [0,1 ] vw v v } F(, ) v w S F (, ) max ( , ) ( , ) v w vw vw ∈Ω S F− S F F S S S _ F

Control mesh of a Loop patch 89 Assume:the initial control mesh has been subdivided at least once Each triangle face contains at most one extraordinary point The control mesh of a Loop patch s of valence n consists of n+6 control points 叶兴 {P,:i=1,2,,n+6} Control mesh of a Loop patch P1:the only extraordinary of valence n point of valence n

Control mesh of a Loop patch Assume: the initial control mesh has been subdivided at least once „ Each triangle face contains at most one extraordinary point The control mesh of a Loop patch of valence consists of n+6 control points „ P 1: the only extraordinary point of valence n S Control mesh of a Loop patch of valence n { Pi : 1,2, , 6 = + i n … } n

Second order norm Each interior edge P,P,in the control mesh can be associated with a mixed second difference (MSD): P,+P-P.-Pm The second order norm M of the control mesh of Loop patch s is defined as the maximum norm of n+9 MSDs: M max{P1 P2-Pn+1-Pall,{P1+P:-Pi-1-Pi+1l 3sis n}, IP1+Pn+1-Pn-P2ll,P2+Pn+1-P1-Pn+2ll, IP2+Pn+2-Pn+1-Pn+3ll,IP2+Pn+3-Pn+2-Pn+4ll, P2+Pn+4-Pn+3-P3,P2+P3-Pn+4-P1ll, IPn+1+Pn -P1 -Pn+6ll,IPn+1+Pn+6-Pn -Pn+5ll, IPn+1+Pn+5-Pn+6-Pn+2ll,Pn+1+Pn+2-Pn+5-P2ll} =max{a:i=1,,n+9}

Second order norm Each interior edge in the control mesh can be associated with a mixed second difference (MSD): The second order norm of the control mesh of Loop patch is defined as the maximum norm of n+9 MSDs: M PPP P i jkm + −− S P Pi j

Our goal 89 To derive a bound on the distance between a Loop patch s(v,w)and its limit triangleF(v,) as ma|S,n）-F(v.w)s B(n)M M:the second order norm of the control mesh of s B(n):a constant only depends on valence n

Our goal To derive a bound on the distance between a Loop patch and its limit triangle as „ : the second order norm of the control mesh of „ : a constant only depends on valence n S(, ) v w F(, ) v w (, ) max ( , ) ( , ) ( ) v w vw vw nM β ∈Ω S F− ≤ M S β ( ) n

Regular patch S(v,w)is a quartic box spline patch defined by 12 control points: S(y,w)=∑P,N,(,w),(,w)）∈2 i=1 N,(v,w):quartic box spline basis functions Control points of a quartic box spline patch S(v,w)is also a quartic tri- u Aue Guu?Auw angular Bezier patch: 4v 12uww 12wu?Avw 15 S(y,w)=∑b,B(y,w),(y,w)∈2 6e2v212a2p62w2 Au 4w B(v,w):quartic Bernstein polynomials ■b,:Bezier points of S Bezier points of a quartic triangular Bezier patch and Bernstein polynomials

Regular patch is a quartic box spline patch defined by 12 control points: „ : quartic box spline basis functions is also a quartic tri￾angular Bézier patch: „ : quartic Bernstein polynomials „ : Bézier points of S(, ) v w 12 1 ( , ) ( , ), ( , ) i i i vw N vw vw = S p = ∈ ∑ Ω S(, ) v w 15 1 ( , ) ( , ), ( , ) i i i vw B vw vw = S b = ∈ ∑ Ω Bézier points of a quartic triangular B ézier patch and Bernstein polynomials Control points of a quartic box spline patch (, ) N vw i (, ) Bi v w bi S

Regular patch Limit triangle isF=(b,bb),and its linear parameterization is F(v,w)=ub+vb+wbis,(v,w)ES (4,v,w):barycentric system of coordinates for the unit triangle,u=1-v-w By the linear precision property of the Bernstein polynomials,F(v,w)can be expressed into the quartic Bezier form: F(y,w)=∑b,B,(y,w）,(y,w)e2 ■Here, by+kH=F(任，4)

Regular patch Limit triangle is , and its linear parameterization is „ : barycentric system of coordinates for the unit triangle, By the linear precision property of the Bernstein polynomials, can be expressed into the quartic Bézier form: „ Here, 1 11 15 F bb b = {, , } u vw = 1− − 1 11 15 F bb b (, ) vw u v w vw = + + ∈Ω ,( , ) (,, ) uvw 15 1 ( , ) ( , ), ( , ) i i i vw B vw vw = F b = ∑ ∈Ω F(, ) v w ( )( 1) 2 1 4 4 (,) jk jk j k k + ++ b F + + =