Motivation et contexte

MEC6212 : Génération de maillages Concepts de base et historique

Modélisation géométrique
Maillages structurés :
TRIANGULATION de DELAUNAY Méthodes algébriques : maillages
conformes, transfinis ;
Ricardo Camarero Méthodes EDP : Elliptiques
Département de génie mécanique (Winslow), hyperboliques.
24 mars 2021 Maillages non-structurés :
Triangulation de Delaunay
Maillages Delaunay contraints
Méthode d’avance de front
Maillages hybrides :
décomposition spatiale :
multiblocs, hiérarchique.

c Ricardo Camarero 2019 2 / 76

Historique

Table des matières Sur le plan fondamental

1 Historique Peter Gustav Lejeune-Dirichlet, 1805–1859, a

montré qu’en 2D 1 , à partir d’un nuage de points, on peut
partitionner le plan en cellules convexes en se basant sur
2 Le diagramme de Voronoı̈
des critères de proximité.
3 Triangulation de Delaunay
George Voronoı̈ 1868–1908, a étendu les travaux de
4 Propriétés des triangulations de Delaunay en ND Dirichlet en ND et traduit la notion de proximité en celle
de cellule polygonale 2 ou diagramme de Voronoı̈.
5 Diagramme de Voronoı̈ dans la nature

6 Le noyau de Delaunay
1. ӆber die reduction der positiven quadartischen formen mit drei understimm-
7 Mise en oeuvre ten ganzen zahlen”, Z. Angnew Math. Mech., Vol 40, no 3, pp. 209–227, 1850.
2. ”Nouvelles applications des paramètres continus à la théorie des formes qua-
dratiques. Recherches sur les parallélloèdes primitifs”. Journal Reine Angew. Math,
Vol 134, 1908.
c Ricardo Camarero 2019 3 / 76 c Ricardo Camarero 2019 4 / 76
Le diagramme de Voronoı̈ Le diagramme de Voronoı̈

La médiatrice
1 Historique
Soit,
2 Le diagramme de Voronoı̈ S1 et S2 , deux sommets dans R2 . d(P,S )
1
P
S
S1 S2 , le segment de droite reliant 1
d(P,S )
3 Triangulation de Delaunay S1 et S2 . 2

d(·, ·), la distance Euclidienne entre

4 Propriétés des triangulations de Delaunay en ND deux points de l’espace. S
2

5 Diagramme de Voronoı̈ dans la nature Ü La médiatrice M(S1 , S2 ) est le lieu des points équidistants de S1
et S2 .
6 Le noyau de Delaunay M(S1 , S2 ) = {P ∈ R2 | d(P, S1 ) = d(P, S2 )},

7 Mise en oeuvre Ü Géométriquement, il s’agit de la bissectrice perpendiculaire du

segment entre deux sommets.

c Ricardo Camarero 2019 5 / 76 c Ricardo Camarero 2019 7 / 76

Le diagramme de Voronoı̈ Le diagramme de Voronoı̈

Partition du plan Une distribution régulière de sommets

Soit S = {Si }i=1,...,N , un nuage de N sommets.

1. La médiatrice sépare les points du plan en deux régions.
S S
2 11
La première comprend les points qui sont plus proche de S1 ,
S S
et la seconde, ceux qui sont le plus proche de S2 . 6 10

Ceci permet d’associer une région de l’espace à un noeud en

particulier.
S
R Ü Sommet 3

Tous les points du plan sont associés à l’un ou l’autre des deux S
1 S
7 S
noeuds, soit S1 ou S2 . 8
S
5
Cette association découle de la notion de proximité qui dépend S
12
de la façon de calculer les distances.
2. Cette partition s’applique également en dimension 3.
S S
4 9

c Ricardo Camarero 2019 8 / 76 c Ricardo Camarero 2019 9 / 76

Le diagramme de Voronoı̈ Le diagramme de Voronoı̈

Cellule de Voronoı̈
Une distribution régulière de sommets suppose qu’il n’y a ni l’une,
Définition : La cellule de Voronoı̈ 3 C(Si ) associée au sommet Si , est le
ni l’autre des configurations suivantes :
lieu des points de l’espace qui sont plus proche de Si que de tout autre
quatre sommets cocycliques sommet :
trois sommets colinéaires
C(Si ) = {P ∈ R2 | d(P, Si ) ≤ d(P, Sj ), ∀j 6= i}.
S S S S
2 11 2 11
S S S S
6 10 6 10

S S
3 3
S S
1 S S 1 S
7 8 7 S
8
S S
5 5
S S
12 12

S S S S
4 9 4 9

3. Aussi appelée cellule de Wigner-Seitz

c Ricardo Camarero 2019 10 / 76 c Ricardo Camarero 2019 11 / 76

Le diagramme de Voronoı̈ Le diagramme de Voronoı̈

Construction de la Cellule de Voronoı̈ Construction de la Cellule de Voronoı̈

Portion du plan limitée par les médiatrices M(Si , Sj ) entre le Portion du plan limitée par les médiatrices M(Si , Sj ) entre le
sommet Si et chacun des sommets Sj qui l’entourent. sommet Si et chacun des sommets Sj qui l’entourent.

Ü Ce concept permet d’associer une portion de l’espace à un noeud

donné.

c Ricardo Camarero 2019 17 / 76 c Ricardo Camarero 2019 18 / 76

Le diagramme de Voronoı̈ Le diagramme de Voronoı̈

Diagramme de Voronoı̈ Est-ce un diagramme de Voronoı̈ ?

L’ensemble des cellules de Voronoı̈ associées à tous les sommets du

nuage de sommets forme le diagramme de Voronoı̈,

c Ricardo Camarero 2019 19 / 76 c Ricardo Camarero 2019 20 / 76

Le diagramme de Voronoı̈ Le diagramme de Voronoı̈

Les cellules de Voronoı̈

De par sa construction, il en découle les propriétés suivantes :
sont des polygones en 2D, des les éléments sont des simplexes ;
polyèdres en 3D, des
les éléments sont un recouvrement de l’espace et ne se chevauchent
N-polytopes en ND ;
pas ;
sont convexes ;
les éléments respectent la propriété max-min : qui maximize l’angle le
recouvrent l’espace sans plus petit.
chevauchement ;
En corollaire, trois propriétés sont dérivées qui seront importantes
sont fermées si elles sont
dans le dévelopement d’algorithmes de génération de maillages :
entourées de sommets, sinon
elles peuvent être ouvertes. Dualité entre le polygone de Voronoı̈ et la triangulation de Delaunay.

1. Les sommets du polygone de Voronoı̈ se trouvent à l’intersection de Triangulation ”équilatérale” ;

trois médiatrices ; Critère de la sphère vide ;
2. Les points qui ont servis à la construction du diagramme de
Voronoı̈ se trouvent au barycentre de ces cellules.

c Ricardo Camarero 2019 21 / 76 c Ricardo Camarero 2019 22 / 76

Le diagramme de Voronoı̈ Le diagramme de Voronoı̈

Voronoı̈ Ü Triangulation de Delaunay.

La triangulation, basée sur le diagramme de Voronoı̈, construite en
reliant le centroı̈de de chaque cellule avec celui de chaque voisin au
travers du coté correspondant du polygone. De cette dualité découle
les éléments sont des simplexes ;
les éléments respectent la propriété max-min : qui maximize l’angle le
plus petit.
Triangulation ”équilatérale” ;
Critère de la sphère vide ;

c Ricardo Camarero 2019 23 / 76 c Ricardo Camarero 2019 24 / 76

Le diagramme de Voronoı̈ Le diagramme de Voronoı̈

Sur le plan pratique Mise en oeuvre informatique

F. Hermeline 6 , A. Bowyer 7 , D. F. Watson 8 , introduisent des méthodes

constructives ainsi que des algorithmes de triangulations de Delaunay en
C. L. Lawson 4 a proposé une méthode constructive d’une triangulation de ND à l’aide du noyau de Delaunay.
Delaunay avec le retournement d’arêtes.
M.-G. Vallet 9 , réalise une extension de ces travaux pour un maillage
P. Green et R. Sibson 5 ont montré que la triangulation de Delaunay adapté comme une triangulation de Delaunay dans un espace déformé par
maximise le minimum des angles pour tous les triangles de la triangulation. une métrique.

6. ”Une méthode automatique de maillage en dimension n”, Thèse de l’Univer-

sité Pierre et Marie Curie, Paris VI, 1980.
7. ”Computing Dirichlet Tessellations”, Computer Journal, Vol 24, no 2,
pp. 162–167, 1981.
4. C. L. Lawson. “Generation of a Triangular Grid with Application to Contour 8. ”Computing the n-dimensional Delaunay Tessellation with Application to Vo-
Plotting”, California Institute of Technology, JPL–299, 1972. ronoı̈ Polytopes”, Computer Journal, Vol 24, no 2, pp. 167–172, 1981.
5. ”Computing Dirichlet Tesselations in the Plane”, Computer Journal, Vol 21, 9. ”Génération de maillages éléments finis anisotropes et adaptatifs”, Thèse de
pp. 168–173, 1978. l’Université Pierre et Marie Curie, Paris VI, 1992.
c Ricardo Camarero 2019 27 / 76 c Ricardo Camarero 2019 28 / 76
Triangulation de Delaunay Triangulation de Delaunay

Triangulations diverses
1 Historique
Le même nuage de points peut se trianguler de plusieurs façons
différentes.
2 Le diagramme de Voronoı̈

3 Triangulation de Delaunay

4 Propriétés des triangulations de Delaunay en ND

5 Diagramme de Voronoı̈ dans la nature

6 Le noyau de Delaunay

7 Mise en oeuvre

Laquelle choisir ?
c Ricardo Camarero 2019 30 / 76 c Ricardo Camarero 2019 31 / 76

Triangulation de Delaunay Triangulation de Delaunay

Parmi toutes ces façons, il y a une triangulation qui est basée sur le Cellules de Voronoı̈ et triangulation
diagramme de Voronoı̈, et construite en reliant le centroı̈de de chaque
cellule avec celui de chaque voisin au travers du coté correspondant du
polygone. Delaunay a montré comment obtenir une trianglation comme le
dual des diagrammes de Voronoı̈.

Boris Nikolaevich Delone ou Delaunay,

1890–1980 ”Sur la sphère vide”, Bulletin de
l’Académie des Sciences de l’URSS, 1934.

Cette triangulation, dite de Delaunay, est unique, et donne l’enveloppe Cette triangulation est unique et vérifie le critère de la sphère vide.
convexe du nuage de points.
c Ricardo Camarero 2019 32 / 76 c Ricardo Camarero 2019 33 / 76
Triangulation de Delaunay Triangulation de Delaunay

Critère de la sphère vide Critère de la sphère vide violé

Soit, Un simplexe K ne satisfait pas le critère de la sphère vide si la boule
T , une triangulation d’un ensemble ouverte circonscrite au simplexe K n’est pas vide (c-à-d contient un
de noeuds ; ou plusieurs sommets de la triangulation), ou encore, si la boule
K fermée circonscrite au simplexe K contient d’autres sommets que
K , un simplexe en ND (triangle en
ceux du simplexe K .
2D, tétraèdre en 3D) de cette
triangulation ;
B, la boule (disque en 2D, sphère B
en 3D, boule en ND) passant par
les N + 1 sommets du simplexe K .

Ü Un simplexe K vérifie le critère de la sphère vide, si la boule

ouverte circonscrite au simplexe K est vide (i.e., ne contient aucun
sommet de la triangulation).
(Si on considère la boule fermée circonscrite au simplexe K , elle contient
uniquement les sommets du simplexe K .)
c Ricardo Camarero 2019 34 / 76 c Ricardo Camarero 2019 37 / 76

Triangulation de Delaunay Triangulation de Delaunay

Triangulation de Delaunay Dualité Delaunay-Voronoı̈

Si tous les éléments, K , d’une triangulation, T , vérifient le critère Le diagramme de Voronoı̈ est le dual de la triangulation de Delaunay et
de la sphère vide, alors la triangulation est dite de Delaunay. vice versa, c’est-à-dire qu’on peut déduire le diagramme de Voronoı̈ de la
triangulation de Delaunay ou encore déduire la triangulation de Delaunay
du diagramme de Voronoı̈.

c Ricardo Camarero 2019 39 / 76 c Ricardo Camarero 2019 40 / 76

Propriétés des triangulations de Delaunay en ND Propriétés des triangulations de Delaunay en ND

1 Historique
• La triangulation de Delaunay est obtenue à partir du diagramme de
2 Le diagramme de Voronoı̈ Voronoı̈ en joignant les sommets dont les cellules de Voronoı̈ partagent un
côté.
3 Triangulation de Delaunay • Les cellules de Voronoı̈ sont obtenues à partir de la triangulation de
Delaunay en intersectant les médiatrices des arêtes de la triangulation.
4 Propriétés des triangulations de Delaunay en ND • Les sommets du diagramme de Voronoı̈ sont au centre des cercles
circonscrits aux simplexes de la triangulation de Delaunay.
• Les arêtes de la triangulation de Delaunay sont perpendiculaires aux
5 Diagramme de Voronoı̈ dans la nature
côtés des cellules de Voronoı̈.
• Les côtés des cellules de Voronoı̈ sont les médiatrices des arêtes de la
6 Le noyau de Delaunay triangulation de Delaunay.

7 Mise en oeuvre

c Ricardo Camarero 2019 41 / 76 c Ricardo Camarero 2019 42 / 76

Propriétés des triangulations de Delaunay en ND Propriétés des triangulations de Delaunay en ND

Propriété maxmin Unicité en ND

La triangulation de Delaunay T d’un nuage de points S est unique.

• Sauf s’il y a quatre points cocycliques en 2D.
En 2D, la triangulation de Delaunay : • Sauf s’il y a cinq points cosphériques en 3D.
1. maximise le minimum des angles formés par les arêtes de la Ceci est illustré par le fait que les quatre sommets cocycliques peuvent
triangulation. être reliés de deux façons.
S S
2. minimise le maximum des rayons des cercles circonscrits aux éléments 2
S
11
S
6 10
de la triangulation.
S’il existe une triangulation du nuage de sommets telle que tous les angles
S
soient aigus, alors c’est la triangulation de Delaunay. 3

S
• Ces propriétés sont fausses en 3D. 1 S
7 S
8
S
5
S
12

S S
4 9

c Ricardo Camarero 2019 43 / 76 c Ricardo Camarero 2019 44 / 76

Diagramme de Voronoı̈ dans la nature Le noyau de Delaunay

1 Historique 1 Historique

2 Le diagramme de Voronoı̈ 2 Le diagramme de Voronoı̈

3 Triangulation de Delaunay 3 Triangulation de Delaunay

4 Propriétés des triangulations de Delaunay en ND 4 Propriétés des triangulations de Delaunay en ND

5 Diagramme de Voronoı̈ dans la nature 5 Diagramme de Voronoı̈ dans la nature

6 Le noyau de Delaunay 6 Le noyau de Delaunay

7 Mise en oeuvre 7 Mise en oeuvre

c Ricardo Camarero 2019 47 / 76 c Ricardo Camarero 2019 50 / 76

Le noyau de Delaunay Le noyau de Delaunay

Le noyau de Delaunay Insertion d’un point

Soit,
On modifie Ti , une triangulation de Delaunay existante, en y
S = {Sj }j=1,...,N , un nuage de N sommets ;
insérant un nouveau sommet, P :
Ti , la triangulation de Delaunay de l’enveloppe convexe
des i premiers sommets de S.
Ü On construit Ti+1 à partir de Ti en ajoutant le sommet P = Si+1 :
Ti+1 = Ti − CP + BP
où CP , la cavité, est l’ensemble des éléments qui violent le critère
de la sphère vide. P
On retire CP , et on relie P aux sommets du polygone de la cavité ;
On construit la boule, BP , les éléments ayant P comme sommet.
On insère BP dans la triangulation, donnant Ti+1 .

Ü alors, Ti+1 , la triangulation obtenue avec le noyau de Delaunay en

insérant le point P comme (i + 1)ième sommet, est une
triangulation de Delaunay.
c Ricardo Camarero 2019 51 / 76 c Ricardo Camarero 2019 52 / 76
Le noyau de Delaunay Le noyau de Delaunay

La cavité La boule
La boule BP associée à un point P est :
La cavité CP associée au sommet P, intérieur à Ti , est l’ensemble
constituée de l’ensemble des éléments de la triangulation T ayant P
des éléments de cette triangulation dont la boule circonscrite
comme sommet.
contient ce point.
construite en connectant le point P aux sommets du périmètre de la
cavité. Ce qui donne la nouvelle triangulation Ti+1 .

P P

c Ricardo Camarero 2019 53 / 76 c Ricardo Camarero 2019 54 / 76

Le noyau de Delaunay Le noyau de Delaunay

Ti+1 = Ti − CP + BP La triangulation initiale

On utilisera comme triangulation de Delaunay initiale T0 , la boite
englobant le nuage de sommets S = {Sj }j=1,...,N .
P P

P P

Ceci nécessite l’ajout de quatre sommets, avec lesquels on construit le

Les modifications apportées à une triangulation de Delaunay lors de maillage initial, T0 , composé de deux éléments.
l’insertion d’un sommet se limitent à la cavité associée à celui-ci. Par inspection, on note que ces deux triangles vérifient le critère de la
Le noyau de Delaunay est donc assez localisé. sphère vide.
Cette procédure incrémentale nécessite au départ un maillage Ce premier maillage est effectivement un maillage Delaunay !.
qui doit être Delaunay. A la fin du procédé, il faudra retirer cet échafaudage ! ! ! !
c Ricardo Camarero 2019 55 / 76 c Ricardo Camarero 2019 56 / 76
Le noyau de Delaunay Le noyau de Delaunay

Insertion des points : cavité + boule

On insère séquentiellement les points Pj de la liste S = {Sj }j=1,...,N ,
et on créé la cavité CP suivie de BP

c Ricardo Camarero 2019 57 / 76 c Ricardo Camarero 2019 58 / 76

Le noyau de Delaunay Mise en oeuvre

1 Historique
Après l’insertion de tous les points du nuage, on obtient la
triangulation du nuage plus la boite. 2 Le diagramme de Voronoı̈

3 Triangulation de Delaunay

4 Propriétés des triangulations de Delaunay en ND

En retranchant les éléments reliés la constuction de la boite, on
obtient la triangulation convexe du nuage. 5 Diagramme de Voronoı̈ dans la nature
Quel est l’impact du choix de la boite ?
Le résultat est-il un maillage ? 6 Le noyau de Delaunay

7 Mise en oeuvre

c Ricardo Camarero 2019 59 / 76 c Ricardo Camarero 2019 63 / 76

Mise en oeuvre Mise en oeuvre

iNOD=boiteConstr(hObject, handles,auto,’EvS’) iNOD=boiteConstr(hObject, handles,auto,’EvS’)

SOMMETS ELM SOMMETS ELM

x y S1 S2 S3 x y S1 S2 S3
1 1
2 2
3 3
4 4
5 5
Nuage 6 Nuage 6
7 7
8 8
9 9
nbTSOM nbTSOM
nbTSOM+1
nbTSOM+2
Boite
nbTSOM+3
nbTSOM+4

c Ricardo Camarero 2019 64 / 76 c Ricardo Camarero 2019 65 / 76

Mise en oeuvre Mise en oeuvre

iNOD=boiteConstr(hObject, handles,auto,’EvS’) iNOD=boiteConstr(hObject, handles,auto,’EvS’)

SOMMETS ELM SOMMETS ELM

x y S1 S2 S3 x y S1 S2 S3
1 1
2 2
3 3
4 4
5 5
Nuage 6 Nuage 6
7 7
8 8
9 9
nbTSOM iNOD nbTSOM iNOD
nbTSOM+1 nbTSOM+1
nbTSOM+2 nbTSOM+2
Boite Boite
nbTSOM+3 nbTSOM+3
nbTSOM+4 nbTSOM+4

c Ricardo Camarero 2019 66 / 76 c Ricardo Camarero 2019 67 / 76

Mise en oeuvre Mise en oeuvre

caviteEvS SOM(iNOD) caviteEvS SOM(iNOD)

[CaviteELM,nbELMcavite,CaviteSOM,nbSOMcavite]=caviteEvS SOM(iNOD) [CaviteELM,nbELMcavite,CaviteSOM,nbSOMcavite]=caviteEvS SOM(iNOD)

SOMMETS CaviteELM CaviteSOM ELM SOMMETS CaviteELM CaviteSOM ELM

x y iELM Si Sj S1 S2 S3 x y iELM Si Sj S1 S2 S3
1 1 1 Cote1
2 2 2 Cote2
3 iNOD 3 iNOD nbELMcavite Cote3
4 4 Cote4
5 5 Cote5
Nuage 6 Nuage 6 Cote6
7 7 Cote7
8 nbELM 8 Cote8 nbELM
9 9 nbSOMcavite
nbTSOM nbTSOM
nbTSOM+1 nbTSOM+1
nbTSOM+2 nbTSOM+2
Boite Boite
nbTSOM+3 nbTSOM+3
nbTSOM+4 nbTSOM+4

c Ricardo Camarero 2019 68 / 76 c Ricardo Camarero 2019 69 / 76

Mise en oeuvre Mise en oeuvre

caviteEvS SOM(iNOD) caviteEvS SOM(iNOD)

[CaviteELM,nbELMcavite,CaviteSOM,nbSOMcavite]=caviteEvS SOM(iNOD) [CaviteELM,nbELMcavite,CaviteSOM,nbSOMcavite]=caviteEvS SOM(iNOD)

SOMMETS CaviteELM CaviteSOM ELM SOMMETS CaviteELM CaviteSOM ELM

x y iELM Si Sj S1 S2 S3 x y iELM Si Sj S1 S2 S3
1 1 Cote1 1 1 Cote1
2 2 Cote2 2 2 Cote2
3 iNOD nbELMcavite Cote3 3 iNOD nbELMcavite Cote3
4 Cote4 Doublons
4 Cote4
5 Cote5 5 nbSOMcavite
Nuage 6 Cote6 Nuage 6
7 Cote7 7
8 Cote8 nbELM 8 nbELM
9 nbSOMcavite 9
nbTSOM nbTSOM
nbTSOM+1 nbTSOM+1
nbTSOM+2 nbTSOM+2
Boite Boite
nbTSOM+3 nbTSOM+3
nbTSOM+4 nbTSOM+4

c Ricardo Camarero 2019 70 / 76 c Ricardo Camarero 2019 71 / 76

Mise en oeuvre Mise en oeuvre

bouleEvS boiteEnleve(’EvS’)
bouleEvS(iNOD,CaviteSOM,nbSOMcavite,CaviteELM,nbELMcavite)

SOMMETS ELM
SOMMETS CaviteELM CaviteSOM ELM
x y S1 S2 S3
x y iELM Si Sj S1 S2 S3 1 iNOD

1 1 Cote1 2
2 2 Cote2 3
3 iNOD nbELMcavite Cote3 4
4 Cote4 5
Nuage 6
5 nbSOMcavite
Nuage 6 7
7 8
9
8 nbELM nbTSOM
9
nbTSOM nbTSOM+1
nbTSOM+2
nbTSOM+1 Boite
nbTSOM+3
nbTSOM+2 nbELM
Boite nbTSOM+4
nbTSOM+3
nbTSOM+4

c Ricardo Camarero 2019 72 / 76 c Ricardo Camarero 2019 73 / 76

Mise en oeuvre Mise en oeuvre

boiteEnleve(’EvS’) boiteEnleve(’EvS’)

SOMMETS ELM SOMMETS ELM

x y S1 S2 S3 x y S1 S2 S3
1 1
2 2
3 3
4 4
5 5
Nuage 6 Nuage 6
7 7
8 8
9 9
nbTSOM nbTSOM
nbTSOM+1 nbTSOM+1
nbTSOM+2 nbTSOM+2
Boite Boite nbELM=nbELM−1
nbTSOM+3 nbTSOM+3
nbTSOM+4 iCOIN
nbELM nbTSOM+4 iCOIN
nbELM

c Ricardo Camarero 2019 74 / 76 c Ricardo Camarero 2019 75 / 76

Mise en oeuvre

boiteEnleve(’EvS’)

SOMMETS ELM
x y S1 S2 S3
1
2
3
4
5
Nuage 6
7
8
9
nbTSOM nbELM

c Ricardo Camarero 2019 76 / 76