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 triangular 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 + + =