中国科学技术大学：Distance Between a Catmull-Clark Subdivision Surface and Its Limit Mesh

Distance Between a Catmull- Clark Subdivision Surface and Its Limit Mesh Zhangjin Huang,Guoping Wang Peking University,China

Distance Between a Catmull￾Clark Subdivision Surface and Its Limit Mesh Zhangjin Huang, Guoping Wang Peking University, China

Catmull-Clark subdivision surface (CCSS Generalization of uniform bicubic B-spline surface C2 continuous except at extraordinary points The limit of a sequence of recursively refined control meshes initial mesh step 1 limit surface

 Generalization of uniform bicubic B-spline surface ◼ continuous except at extraordinary points  The limit of a sequence of recursively refined control meshes Catmull-Clark subdivision surface (CCSS) initial mesh step 1 limit surface 2 C

CCSS patch:regular vs.extraordinary Blue:regular Red:extraordinary Control mesh Limit surface Assume each mesh face in the control mesh ■a quadrilateral at most one extraordinary point (valence n is not 4) An interior mesh face F in the control mesh-a surface patch S in the limit surface Regular patch:bicubic B-spline patches,16 control points Extraordinary patch:not B-spline patches,2n+8 control points

CCSS patch: regular vs. extraordinary  Assume each mesh face in the control mesh ◼ a quadrilateral ◼ at most one extraordinary point (valence n is not 4)  An interior mesh face in the control mesh → a surface patch in the limit surface ◼ Regular patch: bicubic B-spline patches, 16 control points ◼ Extraordinary patch: not B-spline patches, 2n+8 control points Control mesh Limit surface S F Blue: regular Red: extraordinary

Control mesh approximation and error 无法显示该图片 Control mesh is a piecewise linear approximation to a CCSS Approximation error:the maximal distance between a CCSS and the control mesh Distance between a CCSS patch S and its mesh face F(or control mesh)is defined as ()-Fu is unit square =[0,1]x[0,1] S(u,v)is Stam's parametrization of S over F(u,v)is bilinear parametrization of F over

Control mesh approximation and error  Control mesh is a piecewise linear approximation to a CCSS  Approximation error: the maximal distance between a CCSS and the control mesh  Distance between a CCSS patch and its mesh face (or control mesh) is defined as ◼ is unit square ◼ is Stam’s parametrization of over ◼ is bilinear parametrization of over S( , ) u v S F(,) u v S F F ( , ) max ( , ) ( , ) u v u v u v  S F−   =  [0,1] [0,1]  

Distance bound for control mesh approximation The distance between a CCSS patch S and its control mesh is bounded as Cheng et al.2006] maxS(u,)-F(w,v)‖≤C(n)M (u,v)EQ C(n)is a constant that only depends on valence n M is thethe second order norm of 2n+8 control points of S 2n+1 2m+8 ■For regular patches, C(4)=1 3 n+6 2n+3 2n+2

Distance bound for control mesh approximation  The distance between a CCSS patch and its control mesh is bounded as [Cheng et al. 2006] ◼ is a constant that only depends on valence n ◼ is the the second order norm of 2n+8 control points of ◼ For regular patches, S C n( ) M S (4) 1 3 C = ( , ) max ( , ) ( , ) ( ) u v u v u v C n M  S F− 

Limit mesh approximation 口Limit mesh:push the control points to their limit positions. It inscribes the limit surface 口An interior mesh face F→a limit face F→a surface patch S We derive a bound on the distance between a patch S and its limit face F(or limit mesh)as max S(u,v)-F(u,v)<B(n)M (u.)e B(n)<C(n)means that the limit mesh approximates a CCSS better than the control mesh

Limit mesh approximation  An interior mesh face → a limit face → a surface patch  We derive a bound on the distance between a patch and its limit face (or limit mesh) as ◼ means that the limit mesh approximates a CCSS better than the control mesh F F S  Limit mesh : push the control points to their limit positions.  It inscribes the limit surface ( ) ( ) n C n  S F ( , ) max ( , ) ( , ) ( ) u v u v u v n M   S F− 

Regular patches:how to estimate S(4,y)-F(u,v) D. P2. P12 Regular patch S is a bicubic B-spline patch: Su,)=∑∑pN(0)w(,(u,)e2 1=0j-0 Limit face F={PuP2P22,P2),then F(,)=(1-v)[(1-)p+up2]+v[1-0)P22+up12] It is not easy to estimate S(u,v)-F(u,v)directly!

Regular patches: how to estimate  Regular patch is a bicubic B-spline patch:  Limit face , then  It is not easy to estimate directly! S 3 3 3 3 , 0 0 ( , ) ( ) ( ), ( , ) i j i j i j u v N u N v u v = = S p =    S F ( , ) ( , ) u v u v − 1,1 2,1 2,2 1,2 F p p p p ={ , , , } 1,1 2,1 2,2 1,2 F p p p p ( , ) (1 )[(1 ) ] [(1 ) ] u v v u u v u u = − − + + − + S F ( , ) ( , ) u v u v − S F p1,1 p1,2 p2,1 p2,2 p1,1 p2,1 p1,2

Transformation into bicubic Bezier forms 0,p Both S(u,v)and F(4,v)can be transformed into bicubic Bezier form: S4,)=∑∑bB(0B() i=0j=0 33 F(u,)=∑∑bB(0B() i=0j=0

Transformation into bicubic Bézier forms  Both and can be transformed into bicubic Bézier form: 3 3 3 3 , 0 0 ( , ) ( ) ( ) i j i j i j u v B u B v = = S b =   S S( , ) u v F( , ) u v 3 3 3 3 , 0 0 ( , ) ( ) ( ) i j i j i j u v B u B v = = F b =   S F

Regular patches:distance bound NuW-a叭-交，，goro -B.6() Core idea:Measure S(u.)-F(4.)through measuring b,.,-bi

Regular patches: distance bound  Core idea: Measure through measuring S F b1,2 b1,2 3 3 3 3 , , 0 0 ( , ) ( , ) ( ) ( ) ( ) i j i j i j i j u v u v B u B v = = S F b b − = −   3 3 3 3 , , 0 0 i j ( ) ( ) i j i j i j B u B v = =  −   b b S F ( , ) ( , ) u v u v − , , i j b b i j −

Regular patches:distance bound (cont.) Boundb,,b.with the second order norm M,it follows'that 小su,W-Fu,s1-w+1-M Distance bound function of s(4,v)with respect to F(u,v) 9 B(4,W=2u1-0+W1-v.(,)e2 ■Diagonal D(t)=B(t,t)=t(l-t),0≤t≤1 By symmetry, max B(u,v)=max D(t)= (u,v)EQ 0≤1≤1 4

Regular patches: distance bound (cont.)  Bound with the second order norm , it follows that  Distance bound function of with respect to is ◼ Diagonal  By symmetry, , , i j b b i j − M 1 ( , ) ( , ) ( (1 ) (1 )) 2 S F u v u v u u v v M −  − + − S( , ) u v F( , ) u v 1 B( , ) ( (1 ) (1 )), ( , ) 2 u v u u v v u v = − + −  ( , ) 0 1 1 max B( , ) max D( ) u v t 4 u v t    = = D( ) B( , ) (1 ),0 1 t t t t t t = = −  