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