A new procedure to smooth and untangle meshes on parameterized surfaces

Eu opean Cong ess on Compu a ional Me hods in Applied Sciences and Enginee ing (ECCOMAS 2012) J. Ebe ha ds eine e .al. (eds.) Vienna, Aus ia, Sep embe 10-14, 2012 A NEW PROCEDURE TO SMOOTH AND UNTANGLE MESHES ON PARAMETERIZED SURFACES Abel Ga gallo-Pei ´ o1, Xe i Roca2, Josep Sa a e1 1Labo a o i de C` alcul Num` e ic (LaC` aN), Uni e si a Poli ` ecnica de Ca alunya, Ba celona 08034, Spain {abel.ga gallo,jose.sa a e}@upc.edu 2Depa men o Ae onau ics and As onau ics Massachuse s Ins i u e o Technology, Camb idge, MA 02139, USA {xe i oca}@mi .edu Keywo ds: mesh quali y, mesh op imiza ion, smoo hing and un angling, CAD su aces Abs ac . We p esen a echnique o ex end any dis o ion (quali y) measu e o plana meshes o meshes on pa ame e ized su aces. The esul ing dis o ion (quali y) measu e is exp essed in e ms o he pa ame ic coo dina es o he nodes. This ex ended dis o ion (quali y) measu e can be used o check he quali y and alidi y o bo h iangle and quad ila e al su ace meshes. We also apply i o simul aneously smoo h and un angle su ace meshes by minimizing he ex ended dis o ion measu e. The minimiza ion is pe o med in e ms o he pa ame ic coo dina es o he nodes and he e o e, he nodes always lie on he su ace. Finally, we include se e al examples o illus a e he applicabili y o he p oposed echnique. Speci ically, we ex end se e al Jacobian- based measu es, and we us hem o smoo h and un angle iangle and quad ila e al meshes on CAD su aces. Abel Ga gallo-Pei ´ o, Xe i Roca, and Josep Sa a e 1 INTRODUCTION Du ing he las decades, he Fini e Elemen Me hod (FEM) has become one o he mos - used echniques in applied sciences and enginee ing. The applica ion o he me hod equi es a p e ious disc e iza ion o he geome y. Mo eo e , he accu acy o he FEM simula ions depends on he quali y o his disc e iza ion. On he one hand, his disc e iza ion has o be composed by elemen s o he co ec size o cap u e p ope ly he geome y de ails. On he o he hand, his disc e iza ion has o be composed by well-shaped elemen s ha sa is y ce ain geome ical equi emen s. One o he mos -succes ul echniques o imp o e he quali y o a gi en mesh is o eloca e inne nodes while main aining he connec i i y o he mesh ( o smoo h he mesh). Howe e , in p ac ical applica ions, some smoo hing me hods can lead o inal meshes ha con ain in e ed elemen s. This issue is usually igge ed when he mesh bounda y con ains conca e ea u es. I ha is he case, ew smoo hing me hods can epai he in e ed elemen s (un angle) and he e o e, he mesh is no alid. To add ess his issue, he e a e se e al me hods specialized o un angle he mesh. No e ha he p ope combina ion o an un angling me hod wi h a smoo hing echnique would p o ide he desi ed alid and high-quali y mesh. A wide ange o smoo hing algo i hms based on a geome ic easoning ha e been de el- oped o smoo h plana meshes, e.g., see [1, 2]. Howe e , hese algo i hms a e no designed o maximize a gi en quali y measu e. A amily o quali y measu es placed wi hin an algeb aic amewo k has been in oduced in [3, 4, 5]. They a e based on an a ine mapping be ween an ideal elemen and he physical one. Hence, he Jacobian ma ix o he de ined a ine map- ping con ains he dis o ion in o ma ion o he physical elemen . La e , in e e ence [6], i was p oposed a smoo hing me hod based on an op imiza ion o hese measu es. In ac , his op- imiza ion p ocedu e is ans o med in o a con inuous minimiza ion p oblem. Howe e , hese op imiza ion me hods a e s ill no able o un angle in e ed elemen s. A e wa ds, [7] in o- duced a modi ica ion o he p ocedu es de eloped in [6], in which he un angling o he mesh is achie ed oge he wi h he smoo hing p ocedu e. The op imiza ion o he new objec i e unc- ion can simul aneously un angle and smoo h a mesh, sa ing ime and e o in o de o ob ain he inal mesh. These ideas a e o he majo impo ance o su ace meshes. Tha is, since mos o he meshing algo i hms a e hie a chic p ocedu es, he quali y o he inal 3D mesh is di ec ly ela ed o he quali y o he p e iously gene a ed su ace mesh. The e o e, special a en ion is equi ed on epai ing and imp o ing he quali y o su ace meshes. I is also impo an o highligh , ha he o mula ion o a smoo hing o un angling echnique on a su ace is mo e complex han on a olume, because i equi es o deal wi h he cons ain o mo ing he nodes on he su ace. To ensu e ha he nodes mo e on he su ace, i is equi ed o selec a ep esen a ion o he su ace geome y. F om all he possible su ace ep esen a ions, CAD models a e he p e e ed ep esen a ion o indus ial applica ions. In addi ion, CAD en i ies can p o ide some ad an- ages o o mula ing a eloca ion echnique. Fo ins ance, in CAD models, he ep esen a ion is ob ained by a su ace pa ame e iza ion. Thus, using he pa ame e iza ion, we can ensu e ha he nodes o he smoo hed mesh a e on he su ace. Speci ically, we can mo e he nodes on he pa ame e space and hen use he pa ame e iza ion o map hem on he su ace, a oiding any p ojec ion p ocess. Two main app oaches ha e been p oposed o eloca e nodes on su ace meshes. On he one hand, se e al me hods compu e an ideal loca ion o he op imized node, ha can be o he su ace, and hen eloca e he nodes on he su ace [8, 9, 10, 11, 12]. On he o he hand, he e also exis se e al me hods ha ob ain an ideal loca ion o he nodes di ec ly on he su ace 2 Abel Ga gallo-Pei ´ o, Xe i Roca, and Josep Sa a e [13, 14, 15]. These me hods, exp ess he op imiza ion p ocedu e in e ms o he pa ame ic coo dina es o an app oxima ed ep esen a ion o he o iginal su ace. We also compu e he op- imal loca ion di ec ly on he su ace. Howe e , we p opose o quan i y he dis o ion (quali y) o he elemen in e ms o he coo dina es on he pa ame ic space o he CAD su ace. An op imiza ion app oach based on he p oposed dis o ion ensu es ha he nodes always lie on he su ace, since he whole p ocess is de eloped in he pa ame ic space o he o iginal su ace. 2 DISTORTION AND QUALITY FOR ELEMENTS ON PARAMETERIZED SUR- FACES In his sec ion, we i s de elop an analy ical o mula ion o ex end any quali y measu e o plana iangles o iangula meshes on a pa ame e ized su ace. As a esul , we ob ain a quali y measu e exp essed in he wo coo dina es o he pa ame ic space o he su ace. Then, we ex end his echnique o quad ila e al elemen s. 2.1 P elimina ies on plana quali y measu es Le ηbe a dis o ion measu e o plana elemen s, wi h image [1,∞), aking alue 1 o an ideal con igu a ion o he elemen , and alue ∞when i is degene a ed o angled. Le qbe he co esponding quali y measu e, de ined as q=1 η.(1) The image o he quali y measu e qis [0,1], aking alue 1 o ideal con igu a ions and 0 o degene a ed o angled ones. These measu es o plana elemen s p esen ed can be exp essed as he mappings η:R2×R2×R2−→ [1,∞)⊂R,(2) q:R2×R2×R2−→ [0,1] ⊂R.(3) In his wo k we conside wo Jacobian-based quali y measu es, namely he shape and he Oddy quali y measu es [3, 4, 5]. Le φbe he mapping be ween he ideal (equila e al o ian- gles and squa e o quad ila e al elemen s) and he physical elemen , see Figu e 1. This mapping can be exp essed as: φ: I ψ−1 0 −→ R ψ −→ . whe e ψ0is he mapping be ween he e e ence and he ideal elemen and ψis he mapping be ween he e e ence and he physical elelemn . The Jacobian o he a ine mapping φcon ains in o ma ion abou he de ia ion o he phys- ical elemen wi h espec o he ideal. Hence, he dis o ion measu e o he physical elemen is de ined in e ms o S(y0,y1,y2) = Dφ. Using hese mappings he Shape dis o ion measu e is de ined as: ηsh(y0,y1,y2) = kS(y0,y1,y2)k2 2|σ(y0,y1,y2)|,(4) whe e k·kis he F obenius no m, and σ(y0,y1,y2) = de (S(y0,y1,y2)). This dis o ion measu e quan i ies he de ia ion o he shape o he physical iangle wi h espec o he ideal 3 Abel Ga gallo-Pei ´ o, Xe i Roca, and Josep Sa a e Figu e 1: Mappings be ween he e e ence, he ideal and he physical elemen s. shape. To inco po a e he un angling capabili y o he op imiza ion me hod, see Sec ion 3 we eplace σin (4) by σ∗(σ;δ) = 1 2σ+√σ2+ 4δ2,(5) whe e δis a nume ical pa ame e ha has o be de e mined [7]. Simila ly, he Oddy measu e is de ined as: ηod(y0,y1,y2) = 3 2σ−2kSTSk2−1 3kSk4,(6) whe e analogously o han o he shape dis o ion measu e, we can eplace σby σ∗ o op imize angled meshes. 2.2 Measu es o iangles on pa ame ic coo dina es Gi en a dis o ion and i s associa ed quali y measu e o iangles in he plane, ou goal is o ex end hese measu e o iangles wi h he e ices on a pa ame e ized su ace, Σ. Assume ha he su ace Σis pa ame e ized by a con inuously di e en iable and in e ible mapping ϕ:U ⊂ R2−→ Σ⊂R3 u= (u, )7−→ x=ϕ(u).(7) To e alua e he quali y o a iangle Σwi h e ices on a su ace Σ, we i s exp ess he e ices as he image by he pa ame e iza ion ϕo he co esponding pa ame ic coo dina es in U. Since Σis plana , bu i is imme sed in R3, we de ine he quali y o he physical iangle as he quali y o a geome ically equi alen iangle on R2. Once in R2, he p oposed o mula ion allows o ex end any exis en dis o ion and quali y measu e o plana elemen s. In o de o de ine a quali y measu e in e ms o he pa ame ic coo dina es o he h ee e - ices o he iangle, we de ine he mapping ˜ϕ:U ×U ×U −→ Σ×Σ×Σ (u0,u1,u2)7−→ (x0,x1,x2)=(ϕ(u0), ϕ(u1), ϕ(u2)).(8) This mapping ans o ms a iangle U= (u0,u1,u2)in he pa ame ic space U, o a iangle Σ= (x0,x1,x2)wi h he nodes on he su ace Σde e mined by ϕ, see Figu e 2. Since Σ de ines a plane in R3, we can map Σ o a geome ically equi alen iangle in R2. Tha is, 4 Abel Ga gallo-Pei ´ o, Xe i Roca, and Josep Sa a e Figu e 2: Diag am o mappings in ol ed in he de ini ion o he quali y measu e. we can de ine a mapping ˜ T om Σ×Σ×Σ o R2×R2×R2. To de ine ˜ T, we conside an auxilia y linea mapping T om R3 o he plane. The domain o his mapping is exp essed in he canonical basis o R3, and he image is exp essed in e ms o a new 2D o hogonal basis de e mined by a combina ion o wo edges o he iangle. Le e1:= x2−x1,(9) e2:= x0−x1, be he ec o s de e mined by wo edges o he iangle. Then, we de ine ˜ e1:= e1 ke1k, ˜ e2:= γ˜ e2,0,wi h ˜ e2,0:= e2−(eT 2·˜ e1)˜ e1 ke2−(eT 2·˜ e1)˜ e1k, as he wo o hono mal ec o s o he new basis, whe e γis de ined o ensu e a well o ien ed o hono mal basis. Speci ically, we de ine γas: γ:= (˜ e1ט e2,0)·n |(˜ e1ט e2,0)·n|=de (˜ e1,˜ e2,0,n) |de (˜ e1,˜ e2,0,n)|, whe e n≡n(x1) = ∂ϕ ∂u (u1, 1)×∂ϕ ∂ (u1, 1)is he no mal o he su ace a x1=ϕ(u1, 1). No e ha γ=±1, being 1 o coun e -clockwise o ien ed iangles, and −1 o clockwise o ien ed ones. Now, we can de ine Tas T:R3−→ R2 x7−→ M·(x−x1),(10) whe e M= (˜ e1˜ e2)Tis a 2×3ma ix. In addi ion, we de ine ˜ Tas: ˜ T: Σ ×Σ×Σ−→ R2×R2×R2 Σ= (x0,x1,x2)7−→ = (y0,y1,y2) = (T(x0),T(x1),T(x2)),(11) 5 Abel Ga gallo-Pei ´ o, Xe i Roca, and Josep Sa a e Figu e 3: Vec o edges e1and e2 o a iangle Σ= (x0,x1,x2)on a su ace Σ, and diag am o unc ion ˜ T. see Figu e 3. Hence, we can exp ess he dis o ion measu e o a iangle Σon he su ace as: ηΣ: Σ ×Σ×Σ˜ T −→ R2×R2×R2η −→ R (x0,x1,x2)7−→ ˜ T(x0,x1,x2)7−→ η(˜ T(x0,x1,x2)). Tha is, as he composi ion ηΣ=η◦˜ T: Σ ×Σ×Σ−→ [1,∞).(12) No e ha ηΣis a dis o ion measu e on Σ, since i is he composi ion o a plana dis o ion measu e η, and a change o a iable o he plane whe e Σlies. Mo eo e , he ecip ocal o ηΣ, qΣ:= 1 ηΣ : Σ ×Σ×Σ−→ [0,1], is also a quali y measu e, in he sense o [3]. I is impo an o poin ou ha his quali y measu e holds he same p ope ies o he co esponding o iginal plana quali y measu e q. Finally, we use he exp ession o he dis o ion ηΣ, Equa ion (12), o de ine he dis o ion measu e o iangles on pa ame ic coo dina es as: ηU:= ηΣ◦˜ϕ=η◦˜ T◦˜ϕ:U ×U ×U −→ [1,∞).(13) Acco dingly, he quali y measu e o iangles on pa ame ic coo dina es is: qU:= 1 ηU :U ×U ×U −→ [0,1].(14) 2.3 Ex ension o quad ila e als on pa ame ic coo dina es Acco ding o [4], he dis o ion measu e o a plana quad ila e al is e alua ed h ough he decomposi ion o he quad ila e al in o ou iangles, see Figu e 4. In his wo k, we also com- pu e he dis o ion measu e o a quad ila e al elemen on a pa ame e ized su ace as he mean alue o he dis o ion measu e o he ou co ne iangles. To his end, le (x0,x1,x2,x3)be he e ices o a quad ila e al elemen o a mesh wi h he nodes on a pa ame e ized su ace, and le (u0,u1,u2,u3)be hei pa ame ic coo dina es. The dis o ion measu e o quad ila e als on pa ame ic coo dina es is: ηU(u0,u1,u2,u3) := ηU(u0,u1,u2) + ηU(u0,u1,u3) + ηU(u0,u2,u3) + ηU(u1,u2,u3) 4,(15) whe e ηU(ui,uj,uk)is he dis o ion on pa ame ic coo dina es o he iangle (ui,uj,uk), see Equa ion 13. Acco dingly, he quali y measu e o quad ila e als on pa ame ic coo dina es is: qU(u0,u1,u2,u3) := 1 ηU(u0,u1,u2,u3).(16) 6 Abel Ga gallo-Pei ´ o, Xe i Roca, and Josep Sa a e Figu e 4: Decomposi ion o a plana quad ila e al in o ou iangles. 3 OPTIMIZATION OF SURFACE MESH QUALITY The main goal o a simul aneous smoo hing and un angling me hod is o ob ain high-quali y meshes composed by alid (non-in e ed) elemen s. No e ha he bes possible esul , can be cha ac e ized in e ms o he dis o ion measu e. Tha is, gi en a dis o ion measu e ηUand a mesh Mon a pa ame e ized su ace composed by nNnodes and nEelemen s, he node loca ion is ideal i ηU( j U)=1 j= 1, . . . , nE,(17) whe e j U= (uj1,uj2,uj3)is he j h elemen exp essed on pa ame ic coo dina es. Howe e , o a ixed mesh opology he node loca ion ha leads o an ideal mesh dis o ion is no in gene al achie able. Tha is, he cons ain s in Equa ion (17) canno be imposed s ongly and he e o e, we jus en o ce he ideal mesh dis o ion in he leas -squa es sense. Fo a gi en mesh opology and a se o ixed nodes (nodes on he su ace bounda y), we o mula e he leas -squa es p oblem in e ms o he pa ame ic coo dina es o a se o ee nodes (inne nodes on he su ace). To his end, we eo de he pa ame ic coo dina es o he nodes, ui, in such a way ha i= 1, . . . , nFa e he indices co esponding o he ee nodes, and i= nF+ 1, . . . , nNco espond o he ixed nodes. Thus, we can o mula e he mesh op imiza ion p oblem as min u1,...,unF (u1,...,unF;unF+1,...,unN),(18) whe e (u1,...,unF;unF+1,...,unN) := 1 2 nE X j=1 (ηU( j U)−1)2 deno es he objec i e unc ion. Finally, he op imal con igu a ion is ound be ween he candida es o he minimiza ion o (18). The candida es a e he c i ical pa ame ic coo dina es (u1,...,unF)o . They a e cha - ac e ized by ensu ing, o i= 1, . . . , nF, ∂ ∂ui (u1,...,unF;unF+1,...,unN) = nE X j=1 (ηU( j U)−1) ∂ηU ∂ui ( j U) = 0.(19) To sol e he op imiza ion p oblem in Equa ion (18), we ha e o ind he op imum be ween he candida e con igu a ions. These con igu a ions a e cha ac e ized by he global non-linea cons ain s in Equa ion (19). To sol e hese cons ain s, we choose a non-linea i e a i e me hod ha : exploi s he locali y o he p oblem, a oids sol ing la ge linea sys ems, and is well sui ed 7 Abel Ga gallo-Pei ´ o, Xe i Roca, and Josep Sa a e (a) (b) (c) (d) Figu e 5: Meshes o a o us. Meshes colo ed acco ding o he shape quali y measu e: (a) ini ial mesh, and (b) smoo hed and un angled mesh. Meshes colo ed acco ding o he Oddy quali y measu e: (c) ini ial mesh, and (d) smoo hed and un angled mesh. o pa alleliza ion (by colo ing he mesh nodes). Speci ically, we use a non-linea i e a i e Gauss-Seidel me hod de e mined by he i e a ion uk+1 i=uk i−αk i[∇2 ii (wk i)]−1∇i (wk i)i= 1, . . . , nF,(20) whe e αk iis he s ep leng h, and wk i= (uk+1 1,...,uk+1 i−1,uk i,uk i+1,...,uk nF;u0 nF+1,...,u0 nN) is he ec o o upda ed node loca ions o he i−1 i s nodes. No e ha ∇iand ∇2 ii deno e he g adien and he Hessian wi h espec o he pa ame ic coo dina es uio node i. 4 NUMERICAL EXAMPLES In his sec ion, we p esen se e al examples in o de o illus a e he beha io o he p o- posed me hod. To his end we p esen se e al examples and we analyze he minimum, he maximum, he mean, he s anda d de ia ion o he quali y o he elemen s, and he numbe o angled elemen s. We highligh ha in all cases, he smoo hed mesh inc eases he minimum and mean alues o he mesh quali y and dec eases i s s anda d de ia ion. All algo i hms ha e been implemen ed in C++ in he meshing en i onmen EZ4U[16, 17, 18]. The goal o he i s example is o show ha any plana dis o ion measu e can be ex ended o pa ame e ized su aces. Fi s , we gene a e a iangula mesh on a o us composed by 1600 nodes and 3002 elemen s. In Figu es 5(a) and 5(c) we show he ini ial mesh, colo ing he elemen s wi h espec o he wo di e en selec ed measu es. No e ha he mesh con ains 73 in e ed elemen s. Then, in Figu es 5(b) and 5(d) we p esen he wo esul ing op imized meshes. 8 Abel Ga gallo-Pei ´ o, Xe i Roca, and Josep Sa a e Table 1: Shape and Oddy quali y s a is ics o he meshes on he o us. Measu e Mesh Figu e Min. Q. Max. Q. Mean Q. S d. De . Tang. el. Shape Tangled 5(a) 0.00 1.00 0.72 0.24 73 Smoo hed 5(a) 0.79 0.92 0.86 0.02 0 Oddy Tangled 5(c) 0.00 1.00 0.34 0.26 73 Smoo hed 5(d) 0.31 0.59 0.42 0.03 0 S . Mesh Fig. Min.Q. Max.Q. Mean Q. S d.De . Tang. Re ol. Ini ial 6(a) 0.44 0.88 0.79 0.10 0 Tangled 6(b) 0.00 0.99 0.30 0.32 664 Smoo hed 6(c) 0.65 1.00 0.83 0.03 0 Tubula Ini ial 6(d) 0.37 1.00 0.81 0.19 0 Tangled 6(e) 0.00 0.97 0.15 0.26 786 Smoo hed 6( ) 0.52 1.00 0.84 0.08 0 Table 2: Shape quali y s a is ics o he meshes on he e olu ion and ubula su aces. Table 1 summa izes he quali y s a is ics o he meshes p esen ed in Figu e 5. No e ha he p oposed algo i hm un angles an inpu mesh wi h in e ed elemen s. In addi ion, o bo h cases, he p oposed me hod imp o es he quali y o he ini ial su ace meshes. No e ha he Oddy measu e is mo e es ic i e. Tha is, Oddy measu e quan i ies as low quali y he ec angula iangles ( he ideal iangle is he equila e al). Ne e heless, bo h measu es p ope ly de ec he degene a ed and he alid elemen s. The goal o he second example is o illus a e he obus ness o he de eloped smoo hing and un angling me hod. To his end, we use he shape dis o ion measu e, Equa ion (4), and we conside wo NURBS su aces. The i s one is meshed using iangula elemen s, and he second one is meshed wi h quad ila e al elemen s (see Figu e 6). Fo each su ace, h ee igu es a e p esen ed. Fi s , we display an ini ial mesh gene a ed on he NURBS su ace. Second, we show a mesh wi h he same opology han he ini ial one, bu wi h a la ge numbe o angled elemen s. This angled mesh is he inpu o he smoo hing and un angling algo i hm. Thi d, we p esen he op imized mesh. Figu e 6(a) p esen s a iangula mesh gene a ed on a e olu ion su ace. This mesh is com- posed by 800 nodes and 1482 elemen s. Figu e 6(b) shows a mesh wi h 664 angled elemen s, ob ained by a andom pe u ba ion o he ini ial mesh. Figu e 6(c) p esen s he op imized mesh ob ained using he p oposed me hod. Analogously, Figu es 6(d), 6(e) and 6( ), p esen he same scheme o a quad ila e al mesh on a ubula su ace. The mesh is composed by 1200 nodes and 1121 elemen s, and he pe u bed con igu a ion has 786 angled elemen s. Table 2 summa izes he shape quali y s a is ics o he meshes p esen ed in Figu e 6. No e ha he p oposed algo i hm un angles an inpu mesh composed by a la ge numbe o angled elemen s. In addi ion, o bo h cases, he p oposed me hod imp o es he quali y o he ini ial su ace meshes. In he hi d example we apply he smoo hing and un angling p ocedu e using he shape dis- o ion measu e, Equa ion (4), o wo CAD models composed by mul iple pa ches: a knob and a c ank a m. Figu e 7(a) shows he ini ial mesh on he knob. I is composed by 15137 nodes and 14521 quad ila e al elemen s. The ini ial mesh has in en ionally been gene a ed wi h 497 an- gled elemen s. Figu e 7(b) p esen s he smoo hed mesh, whe e all he in e ed and degene a ed elemen s ha e been un angled. Then, Figu e 8(a) p esen s he ini ial mesh on he c ank a m. 9