MAILLAGES POUR LE

CALCUL SCIENTIFIQUE

ANNABELLE COLLIN
PLAN
MAILLAGE : DÉFINITIONS ET NOTIONS PRINCIPALES
I. Qu’est ce qu’un maillage ?
II. À quoi ça sert un maillage ?
III. Différents types de maillage
IV. Maillages pour la simulation numérique

GÉNÉRATION DE MAILLAGE
I. Pourquoi construire un maillage est difficile ?
II. Schéma général de construction de maillage
III. Méthode de Delaunay
IV. Méthode frontale
V. Méthode octree/quadtree
VI. Comparaison des 3 méthodes

ADAPTATION DE MAILLAGE
I. Qu’est ce que l’adaptation de maillage ?
II. Estimation d'erreur
III. Technique pratique d’adaptation de maillage
IV. Illustration sur un exemple
V. Méthode octree/quadtree
VI. Comparaison des 3 méthodes

Annabelle Collin ANNABELLE COLLIN 2

PREMIÈRE PARTIE: MAILLAGES : DÉFINITIONS ET NOTIONS PRINCIPALES

• Qu’est ce qu’un maillage ?

• À quoi ça sert un maillage ?

• Différents types de maillage

• Maillages pour la simulation numérique

Annabelle Collin ANNABELLE COLLIN 3

QU’EST-CE QU’UN MAILLAGE ?

Un maillage est une partition de l’espace ou d’un domaine en cellules

élémentaires.

Soit Ω un domaine borné de R2 et de R3 , Th est un maillage de Ω si :

(H1 ) Ω = K,
K Th

(H2 ) l’intérieur de tout élément K de Th est non vide,

(H3 ) l’intersection de l’intérieur de 2 éléments est vide.

(H1) : les éléments recouvrent Ω mais les K peuvent être de tous types

(H3) : cette hypothèse interdit les chevauchements

Non ! Oui !

Annabelle Collin MAILLAGES : DÉFINITIONS ET NOTIONS PRINCIPALES 4

QU’EST-CE QU’UN MAILLAGE ?

Un maillage est une partition de l’espace ou d’un domaine en cellules

élémentaires.

Soit Ω un domaine borné de R2 et de R3 , Th est un maillage de Ω si :

(H1 ) Ω = K,
K Th

(H2 ) l’intérieur de tout élément K de Th est non vide,

(H3 ) l’intersection de l’intérieur de 2 éléments est vide.

Un maillage est dit conforme si l’intersection de deux éléments distincts K et K’

est soit :
• l’ensemble vide
• un simplex commun à K et K’ (noeud, arête ou triangle en 3D)

Non conforme Conforme

Annabelle Collin MAILLAGES : DÉFINITIONS ET NOTIONS PRINCIPALES 5

QU’EST-CE QU’UN MAILLAGE ?

Un maillage est une partition de l’espace ou d’un domaine en cellules

élémentaires.

Soit Ω un domaine borné de R2 et de R3 , Th est un maillage de Ω si :

(H1 ) Ω = K,
K Th

(H2 ) l’intérieur de tout élément K de Th est non vide,

(H3 ) l’intersection de l’intérieur de 2 éléments est vide.

Remarque : Le h de Th correspond à la taille caractéristique de l’élément.

h h/2

Annabelle Collin MAILLAGES : DÉFINITIONS ET NOTIONS PRINCIPALES 6

À QUOI ÇA SERT UN MAILLAGE ?

Problèmes réels
Phénomènes physique ou biologique

Formulation mathématique des problèmes :

mise en équation et modélisation

Méthode de résolution numérique La méthode numérique

sur ordinateur ! dépend du choix du

maillage !

Résultats

Annabelle Collin MAILLAGES : DÉFINITIONS ET NOTIONS PRINCIPALES 7

À QUOI ÇA SERT UN MAILLAGE ?

Naïvement : une représentation discrète de la géométrie pour l’ordinateur

Géométrie

Maillage

Déplacements calculés

Maillage déformé
Annabelle Collin MAILLAGES : DÉFINITIONS ET NOTIONS PRINCIPALES 8
 À QUOI ÇA SERT UN MAILLAGE ?
4. Les scenarios pour le XXIeme siècle 5. Plus de glace de mer au pole Nord
Exemples environnementaux de simulation numérique

MODEL
Couverture de glace estivale [1980-1999] Couverture de glace estivale [2080-2099]

OBSERVATIONS
observation

D. Swingedouw, CEA Saclay Disparition de la glace de mer en été M. Rochoux, CERFACS

Site Météo France

Annabelle Collin MAILLAGES : DÉFINITIONS ET NOTIONS PRINCIPALES 9

À QUOI ÇA SERT UN MAILLAGE ?

Exemples industriels de simulation numérique

C. Dobrzynski, IMB, Inria

Site du FETES, centrale Marseille

H. Beaugendre, IMB, Inria

ESI group et ATZ worldwide

M. Bergmann, Inria

Annabelle Collin MAILLAGES : DÉFINITIONS ET NOTIONS PRINCIPALES 10

 CFDs in Scaffolded Vessels with the AbsorbTM Case 1: A Straight Coronary Arterial Segment Hemodynamics in Scaffolded C
Bioresorbable Vascular Scafolds
No Strut Zone
Scaffold:

À QUOI ÇA SERT UN MAILLAGE ?

• Elastic Material: Polymer Poly(L-lactide) (PLLA)

TAWSS (dyne/cm^2)
• Sharp and thick struts: singularity > more severe recirculation
• Strut Thickness: ~150 microns
Risks:
• In segment restenosis: greater lumen loss after 6 months
AbsorbTM Bioresorbable • Late or very late scaffold thrombosis
Vascular Scaffolds
Exemples de simulation numérique en médecine Strut
Strut
Centerline vessel (mm)
+Pi
Bioresorbable Scaffolds: Resconstruction
Flow around struts Inner
• Observations:
(pi/2)
[Link] disruption across strut
• OCT: Lumen wall and struts detections
[Link] may follow struts pattern
[Link]-automatic struts on each OCT-frame [Link] for directional
[Link] topology reconstruction of stent WSS analysis
[Link] skeleton interpolation
4.3D reconstruction by ad-hoc sweeping Outer
algorithms (pi/2)
[Link] surface meshing
Flow
-Pi
• Angiography Registration TAWSS flat mapping (with VTK/VMTK & Paraview) Impact on Wall Shear Stress
V4

[Link] bi-plane angiography Zoom V1

3

[Link] reconstruction with • Observations: aVR

3
2
1 Zoom 1
QAngioXA (Medis)
2
1
0
1
Zoom 2
3 600
I 2
[Link] OCT to derive lumen wall [Link] Time Averaged WSS on
2 0 400
1 3 200
1 0
3 600 V5

[Link] performed following top of scaffold strut

2
2 0 400
1 3 200
1 0 3
600 V2
centreline Frenet frame 0
1 [Link] Time Average WSS
2
3
0
200
aVL
400
3
2
1

5.3D Lumen Meshing proximal and distal surface to

2 600 0
400 2
3 200 1 1
0 3 600
strut due to recirculation
II 2
2 0 400
1 3 200
1 0
3
2 600 V6
2 0 400
1 3 200
1 0 3
2 600 V3
0 400 2
1 3 200 1
0 3
2 600 aVF 0
400 2
3 200 1 1
0 3 600
III 2
2 0 400
1 3 200
1 0

Bioresorbable Scaffolds: Meshing Équipe Monc, Inria Case 2: A Curved Coronary Arterial Segment
3
2
1
0
1
600
2
3
0
200
400
600

Fine Mesh with CGAL

2
0 400
1 3 200
0

Determination of the 2
3 200
400
600
• Zoom 1
Équipes Reo et M3disim, Inria
0

20000
• CGAL ([Link]): tumoral volume
Computational Geometry Algorithm Library:
+15%
1. State-of-art open-source computational geometry
library
Predicted volume (in mm3)

2. Boolean operation on polyhedra

3. Polygon
15000Mesh Processing: Isotropic Remeshing, Hole
filling, etc.
4. Novel 3D Meshing with feature preservation -15%

• Domain of interest: Lumen Volume-Stent Volume Coarse Mesh Fine Mesh

10000 Flow
Can be performed using CGAL with Nef-polyhedron: avoids round-off errors
• Importance of features (strut ridges) • Automatic struct detection by triangle
preservation dihedral angle measurement
Conclusions and Future Work
TAWSS (dyne/cm^2)

5000
• We observed:
VPredict = 2.47 + 1.04 * VObserved
1. Strong impact of mesh accuracy for r
(R = 0.9823) struts
2. Impact of curvature on WSS around s
0 3. Recirculation appears to be moderate
0 5000 10000 15000 20000 WSS proximal and distal to surface str
4. WSS on top of the struts appears to b
Without features Observed
With features mm3)View
volume (inExternal Internal View 5. Flow is highly disrupted by thick and
• Meshing with CGAL A.• Future
Lefieux,
Work
Emory Atlanta
Centerline vessel (mm)
+Pi 1. Perform post-processing on compute
2. Analyse cases with malapposed stru
Inner 3. Introduce transversal type WSS to st
Annabelle Collin (pi/2)
MAILLAGES : DÉFINITIONS ET NOTIONS PRINCIPALES
• Acknowledgement 11
DIFFÉRENTS TYPES DE MAILLAGE

La connectivité d’un élément (au sens de noeud, arête, cellule …) est la liste
des ses voisins.

Un maillage structuré est un maillage à connectivité fixe. Le maillage est alors

défini par sa seule liste de noeuds.
Rapidement :
• Structuré : grille (noeuds toujours adjacents aux mêmes éléments)
• Non-structuré : les autres

Structuré Non-structuré

Annabelle Collin MAILLAGES : DÉFINITIONS ET NOTIONS PRINCIPALES 12

DIFFÉRENTS TYPES DE MAILLAGE

Deux types de maillage :

• simpliciaux : triangles, tétraèdres

• mixtes / hybrides : différents types d’éléments (contient des éléments

structurés et non structurés)

Annabelle Collin MAILLAGES : DÉFINITIONS ET NOTIONS PRINCIPALES 13

MAILLAGES POUR LA SIMULATION NUMÉRIQUE

Pour être utilisable pour la simulation numérique, les maillages doivent :

• représenter suffisamment bien la géométrie

Annabelle Collin MAILLAGES : DÉFINITIONS ET NOTIONS PRINCIPALES 14

MAILLAGES POUR LA SIMULATION NUMÉRIQUE

Pour être utilisable pour la simulation numérique, les maillages doivent :

• représenter suffisamment bien la géométrie
• comporter suffisamment d’éléments pour calculer précisément

Annabelle Collin MAILLAGES : DÉFINITIONS ET NOTIONS PRINCIPALES 15

MAILLAGES POUR LA SIMULATION NUMÉRIQUE

Pour être utilisable pour la simulation numérique, les maillages doivent :

• représenter suffisamment bien la géométrie
• comporter suffisamment d’éléments pour calculer précisément

Annabelle Collin MAILLAGES : DÉFINITIONS ET NOTIONS PRINCIPALES 16

MAILLAGES POUR LA SIMULATION NUMÉRIQUE

Pour être utilisable pour la simulation numérique, les maillages doivent :

• représenter suffisamment bien la géométrie
• comporter suffisamment d’éléments pour calculer précisément

Annabelle Collin MAILLAGES : DÉFINITIONS ET NOTIONS PRINCIPALES 17

MAILLAGES POUR LA SIMULATION NUMÉRIQUE

Pour être utilisable pour la simulation numérique, les maillages doivent :

• représenter suffisamment bien la géométrie
• comporter suffisamment d’éléments pour calculer précisément
• avoir des éléments de bonne qualité

Quelques critères de qualité

2
V 3
(ou SICN) =
(la )2
rci
=
rcc
minT la
= ,
maxT la

Annabelle Collin MAILLAGES : DÉFINITIONS ET NOTIONS PRINCIPALES 18

DEUXIÈME PARTIE: GÉNÉRATION DE MAILLAGE

I. Pourquoi construire un maillage est difficile ?

II. Schéma général de construction de maillage

III. Méthode de Delaunay

1. Triangulation de l’enveloppe convexe d’un ensemble de points
2. Triangulation de Delaunay contrainte
3. Difficultés, avantages et inconvénients

IV. Méthode frontale

1. Méthode
2. Difficultés, avantages et inconvénients

V. Méthode octree/quadtree
1. Méthode
2. Difficultés, avantages et inconvénients

[Link] des 3 méthodes

Annabelle Collin ANNABELLE COLLIN 19

POURQUOI CONSTRUIRE UN MAILLAGE EST DIFFICILE ?

• Beaucoup de contraintes demandées par l’utilisateur :

• Tailles des éléments (comme vu précédemment)
• Qualités des éléments (comme vu précédemment)
• Respect de la géométrie (comme vu précédemment)
• Type d’éléments (pour que ce soit compatible avec le code !)

• Procédure la plus automatique possible

• Procédure la plus robuste possible (sans maillage on ne peut pas calculer !)

• Vitesse des mailleurs est importante : gros maillages demandent beaucoup

de ressources (HPC)

• Beaucoup beaucoup de cas particuliers

Annabelle Collin GÉNÉRATION DE MAILLAGE 20

SCHÉMA GÉNÉRAL DE CONSTRUCTION D’UN MAILLAGE
• Méthode générale pour les maillages structurés
• Mailler une géométrie simple
• La transformer pour obtenir une géométrie voulue

• Méthodes pour les maillages non-structurés

• Méthode de Delaunay
• Création d’une boîte englobante
• Insertion des noeuds de bord et forçage des frontières
• Suppression de la boite englobante
• Création de points intérieurs au domaine par rapport à une spécification de taille

• Méthode frontale
• Initialisation du front par les entités frontières
• Création de points intérieurs au domaine par création des éléments « idéaux » issus des
entités du front et mise à jour du front

• Méthode Quadtree - Octree

• Création d’une boîte englobante
• Création d’un arbre par rapport à un critère géométrique et/ou une spécification des
tailles requises
• Équilibrage de l’arbre
• Triangulation des cellules de l’arbre par des motifs prédéfinis

Annabelle Collin GÉNÉRATION DE MAILLAGE 21

 MÉTHODE DE DELAUNAY :
1. TRIANGULATION DE L’ENVELOPPE CONVEXE D’UN ENSEMBLE DE
POINTS

a. QU’EST CE QU’UNE TRIANGULATION DE DELAUNAY ?

b. INSERTION DE POINTS DANS UNE TRIANGULATION DE DELAUNAY

c. ALGORITHME

Annabelle Collin ANNABELLE COLLIN 22

A. QU’EST CE QU’UNE TRIANGULATION DE DELAUNAY ?

Critère de la boule vide : les boules ouvertes circonscrites aux sommets

de la triangulation ne contiennent aucun sommet de la triangulation.

Définition : une triangulation respectant le critère de la boule vide est une

triangulation de Delaunay.

Proposition : il y a unicité de la triangulation de Delaunay.

Triangulation quelconque Triangulation de Delaunay

Annabelle Collin ANNABELLE COLLIN 23

A. QU’EST CE QU’UNE TRIANGULATION DE DELAUNAY ?

Méthode du retournement : dans le cas d’un quadrilatère la méthode du

retournement (méthode flip) permet d’obtenir une triangulation de Delaunay du
quadrilatère.

Lemme : Soit T une triangulation, si le critère de la boule vide est vrai pour chaque
configuration de 2 éléments adjoints de T alors le critère est vrai partout et T est la
triangulation de Delaunay.

Annabelle Collin ANNABELLE COLLIN 24

B. INSERTION DE POINTS DANS UNE TRIANGULATION DE DELAUNAY

Soit une triangulation de Delaunay d’une

enveloppe convexe de points, l’objectif est
d’insérer le point P (sur l’exemple en vert).

Par exemple pour raffiner le maillage suivant

un critère de raffinement.

La méthode présentée ici est la méthode

incrémentale :
Ti+1 = Ti - Cp + Bp

Annabelle Collin ANNABELLE COLLIN 25

B. INSERTION DE POINTS DANS UNE TRIANGULATION DE DELAUNAY

Méthode incrémentale : Ti+1 = Ti - Cp + Bp

1) Retirer l’intérieur de la cavité Cp qui est

l'ensemble des triangles dont le cercle
circonscrit contient le point à insérer

Annabelle Collin ANNABELLE COLLIN 26

B. INSERTION DE POINTS DANS UNE TRIANGULATION DE DELAUNAY

Méthode incrémentale : Ti+1 = Ti - Cp + Bp

2) Construire la boule Bp qui est

l’ensemble des éléments formés en
joignant le point à insérer aux arêtes
externes de la cavité Cp

Annabelle Collin ANNABELLE COLLIN 27

B. INSERTION DE POINTS DANS UNE TRIANGULATION DE DELAUNAY

Méthode incrémentale : Ti+1 = Ti - Cp + Bp

Théorème : Si Ti est une triangulation de

Delaunay alors Ti+1 construit par la méthode
incrémentale est une triangulation de
Delaunay.

Annabelle Collin ANNABELLE COLLIN 28

 C. TRIANGULATION DE L’ENVELOPPE CONVEXE D’UN ENSEMBLE DE
POINTS : ALGORITHME

Etape 1 : Initialisations :
• Discrétisation de la frontière
• Construction d’une triangulation initiale τB
de la boite englobante du domaine

Annabelle Collin ANNABELLE COLLIN 29

 C. TRIANGULATION DE L’ENVELOPPE CONVEXE D’UN ENSEMBLE DE
POINTS : ALGORITHME

Etape 1 : Initialisations :
• Discrétisation de la frontière
• Construction d’une triangulation initiale τB
de la boite englobante du domaine

Etape 2 : Insertion des points frontières

dans τB (méthode incrémentale)

Annabelle Collin ANNABELLE COLLIN 30

 C. TRIANGULATION DE L’ENVELOPPE CONVEXE D’UN ENSEMBLE DE
POINTS : ALGORITHME

Etape 1 : Initialisations :
• Discrétisation de la frontière
• Construction d’une triangulation initiale τB
de la boite englobante du domaine

Etape 2 : Insertion des points frontières

dans τB (méthode incrémentale)

Annabelle Collin ANNABELLE COLLIN 31

 C. TRIANGULATION DE L’ENVELOPPE CONVEXE D’UN ENSEMBLE DE
POINTS : ALGORITHME

Etape 1 : Initialisations :
• Discrétisation de la frontière
• Construction d’une triangulation initiale τB
de la boite englobante du domaine

Etape 2 : Insertion des points frontières

dans τB (méthode incrémentale)

Annabelle Collin ANNABELLE COLLIN 32

 C. TRIANGULATION DE L’ENVELOPPE CONVEXE D’UN ENSEMBLE DE
POINTS : ALGORITHME

Etape 1 : Initialisations :
• Discrétisation de la frontière
• Construction d’une triangulation initiale τB
de la boite englobante du domaine

Etape 2 : Insertion des points frontières

dans τB (méthode incrémentale)

Annabelle Collin ANNABELLE COLLIN 33

 C. TRIANGULATION DE L’ENVELOPPE CONVEXE D’UN ENSEMBLE DE
POINTS : ALGORITHME

Etape 1 : Initialisations :
• Discrétisation de la frontière
• Construction d’une triangulation initiale τB
de la boite englobante du domaine

Etape 2 : Insertion des points frontières

dans τB (méthode incrémentale)

Annabelle Collin ANNABELLE COLLIN 34

 C. TRIANGULATION DE L’ENVELOPPE CONVEXE D’UN ENSEMBLE DE
POINTS : ALGORITHME

Etape 1 : Initialisations :
• Discrétisation de la frontière
• Construction d’une triangulation initiale τB
de la boite englobante du domaine

Etape 2 : Insertion des points frontières

dans τB (méthode incrémentale)

Annabelle Collin ANNABELLE COLLIN 35

 C. TRIANGULATION DE L’ENVELOPPE CONVEXE D’UN ENSEMBLE DE
POINTS : ALGORITHME

Etape 1 : Initialisations :
• Discrétisation de la frontière
• Construction d’une triangulation initiale τB
de la boite englobante du domaine

Etape 2 : Insertion des points frontières

dans τB (méthode incrémentale)

Annabelle Collin ANNABELLE COLLIN 36

 C. TRIANGULATION DE L’ENVELOPPE CONVEXE D’UN ENSEMBLE DE
POINTS : ALGORITHME

Etape 1 : Initialisations :
• Discrétisation de la frontière
• Construction d’une triangulation initiale τB
de la boite englobante du domaine

Etape 2 : Insertion des points frontières

dans τB (méthode incrémentale)

Annabelle Collin ANNABELLE COLLIN 37

 C. TRIANGULATION DE L’ENVELOPPE CONVEXE D’UN ENSEMBLE DE
POINTS : ALGORITHME

Etape 1 : Initialisations :
• Discrétisation de la frontière
• Construction d’une triangulation initiale τB
de la boite englobante du domaine

Etape 2 : Insertion des points frontières

dans τB (méthode incrémentale)

Annabelle Collin ANNABELLE COLLIN 38

 C. TRIANGULATION DE L’ENVELOPPE CONVEXE D’UN ENSEMBLE DE
POINTS : ALGORITHME

Etape 1 : Initialisations :
• Discrétisation de la frontière
• Construction d’une triangulation initiale τB
de la boite englobante du domaine

Etape 2 : Insertion des points frontières

dans τB (méthode incrémentale)

Annabelle Collin ANNABELLE COLLIN 39

 C. TRIANGULATION DE L’ENVELOPPE CONVEXE D’UN ENSEMBLE DE
POINTS : ALGORITHME

Etape 1 : Initialisations :
• Discrétisation de la frontière
• Construction d’une triangulation initiale τB
de la boite englobante du domaine

Etape 2 : Insertion des points frontières

dans τB (méthode incrémentale)

Annabelle Collin ANNABELLE COLLIN 40

 C. TRIANGULATION DE L’ENVELOPPE CONVEXE D’UN ENSEMBLE DE
POINTS : ALGORITHME

Etape 1 : Initialisations :
• Discrétisation de la frontière
• Construction d’une triangulation initiale τB
de la boite englobante du domaine

Etape 2 : Insertion des points frontières

dans τB (méthode incrémentale)

Annabelle Collin ANNABELLE COLLIN 41

 C. TRIANGULATION DE L’ENVELOPPE CONVEXE D’UN ENSEMBLE DE
POINTS : ALGORITHME

Etape 1 : Initialisations :
• Discrétisation de la frontière
• Construction d’une triangulation initiale τB
de la boite englobante du domaine

Etape 2 : Insertion des points frontières

dans τB (méthode incrémentale)

Annabelle Collin ANNABELLE COLLIN 42

 C. TRIANGULATION DE L’ENVELOPPE CONVEXE D’UN ENSEMBLE DE
POINTS : ALGORITHME

Etape 1 : Initialisations :
• Discrétisation de la frontière
• Construction d’une triangulation initiale τB
de la boite englobante du domaine

Etape 2 : Insertion des points frontières

dans τB (méthode incrémentale)

Annabelle Collin ANNABELLE COLLIN 43

 C. TRIANGULATION DE L’ENVELOPPE CONVEXE D’UN ENSEMBLE DE
POINTS : ALGORITHME

Etape 1 : Initialisations :
• Discrétisation de la frontière
• Construction d’une triangulation initiale τB
de la boite englobante du domaine

Etape 2 : Insertion des points frontières

dans τB (méthode incrémentale)

Annabelle Collin ANNABELLE COLLIN 44

 C. TRIANGULATION DE L’ENVELOPPE CONVEXE D’UN ENSEMBLE DE
POINTS : ALGORITHME

Etape 1 : Initialisations :
• Discrétisation de la frontière
• Construction d’une triangulation initiale τB
de la boite englobante du domaine

Etape 2 : Insertion des points frontières

dans τB (méthode incrémentale)

Annabelle Collin ANNABELLE COLLIN 45

 C. TRIANGULATION DE L’ENVELOPPE CONVEXE D’UN ENSEMBLE DE
POINTS : ALGORITHME

Etape 1 : Initialisations :
• Discrétisation de la frontière
• Construction d’une triangulation initiale τB
de la boite englobante du domaine

Etape 2 : Insertion des points frontières

dans τB (méthode incrémentale)

Etape 3 : Construction d’un maillage bord à

bord τE à partir de τB :
• Coloration des éléments
• Suppression de la boite englobante

Annabelle Collin ANNABELLE COLLIN 46

 C. TRIANGULATION DE L’ENVELOPPE CONVEXE D’UN ENSEMBLE DE
POINTS : ALGORITHME

Etape 1 : Initialisations :
• Discrétisation de la frontière
• Construction d’une triangulation initiale τB
de la boite englobante du domaine

Etape 2 : Insertion des points frontières

dans τB (méthode incrémentale)

Etape 3 : Construction d’un maillage bord à

bord τE à partir de τB :
• Coloration des éléments
• Suppression de la boite englobante

Annabelle Collin ANNABELLE COLLIN 47

 C. TRIANGULATION DE L’ENVELOPPE CONVEXE D’UN ENSEMBLE DE
POINTS : ALGORITHME

Etape 1 : Initialisations :
• Discrétisation de la frontière
• Construction d’une triangulation initiale τB
de la boite englobante du domaine

Etape 2 : Insertion des points frontières

dans τB (méthode incrémentale)

Etape 3 : Construction d’un maillage bord à

bord τE à partir de τB :
• Coloration des éléments
• Suppression de la boite englobante
Etape 4 : Définition ou prise en compte
d’une fonction de taille

Etape 5 : Création et insertion des points

internes pour obtenir le maillage τ

Etape 6 : Optimisation de τ

Annabelle Collin ANNABELLE COLLIN 48

 MÉTHODE DE DELAUNAY :
2. TRIANGULATION DE DELAUNAY CONTRAINTE

a. PRÉSENTATION DE LA PROBLÉMATIQUE

b. FORÇAGE D’ARÊTES

c. TRIANGULATION DE DELAUNAY (CONTRAINTE) POUR UNE GÉOMÉTRIE NON CONVEXE

Annabelle Collin ANNABELLE COLLIN 49

A. PRÉSENTATION DE LA PROBLÉMATIQUE

Objectif : retrouver dans notre triangulation finale un certain nombre d’entités

Ex : on a un ensemble de segment délimitant notre domaine (formant une

géométrie non convexe)

Triangulation de Delaunay
Entité à ajouter
de l’enveloppe convexe

La triangulation finale ne sera plus de Delaunay, on parle de triangulation de Delaunay contrainte

(c’est à dire que certains éléments ne vérifient pas le critère de Delaunay).

Annabelle Collin ANNABELLE COLLIN 50

B. FORÇAGE D'ARÊTES

Tant que toutes les arêtes à intégrer ne sont pas incluses dans le maillage, parcourir chaque arête
n’appartenant pas encore au maillage.
Parcourir les quadrilatères dont la diagonale couple l’arête
• Si l’arête ne coupe pas l’autre diagonale du quadrilatère (celle qui n’appartient pas au maillage) :
Retournement de la diagonale du quadrilatère
• Si l’arête coupe l’autre diagonale du quadrilatère : Retournement de la diagonale du quadrilatère de
manière aléatoire

Théorème : l’algorithme converge et la triangulation obtenue est unique.

Annabelle Collin ANNABELLE COLLIN 51

B. FORÇAGE D'ARÊTES

Annabelle Collin ANNABELLE COLLIN 52

 C. TRIANGULATION DE DELAUNAY (CONTRAINTE) POUR UNE GÉOMÉTRIE
NON CONVEXE

Etape 1 : Initialisations :
• Discrétisation de la frontière
• Construction d’une triangulation initiale τB
de la boite englobante du domaine

Etape 2 : Insertion des points frontières

dans τB (méthode incrémentale)

Etape 3 : Forçage des frontières

Triangulation contrainte
Etape 4 : Construction d’un maillage bord à Géométrie à mailler
de Delaunay
bord τE à partir de τB :
• Coloration des éléments
• Suppression de la boite englobante
Etape 5 : Définition/prise en compte d’une
fonction de taille

Etape 6 : Création et insertion des points

internes pour obtenir le maillage τ

Etape 7 : Optimisation de τ Triangulation de Delaunay

(cas non convexe)

Annabelle Collin ANNABELLE COLLIN 53

 MÉTHODE DE DELAUNAY :
3. DIFFICULTÉS, AVANTAGES ET INCONVÉNIENTS DE LA MÉTHODE
a. DIFFICULTÉS ALGORITHMIQUES
• Implémenter une recherche rapide pour savoir à quel triangle appartient un nouveau noeud
• Forçage des frontières : dur en 3D

b. AVANTAGES
• Algorithme d’insertion performant

c. INCONVÉNIENTS
• Forçage de la frontière
• Erreurs d’arrondi (pour savoir si des points sont dans le cercle circonscrit …)

Annabelle Collin ANNABELLE COLLIN 54

 MÉTHODE FRONTALE :
1. ALGORITHME (ILLUSTRATION SUR UN EXEMPLE EN 2D)

etc …

Annabelle Collin GÉNÉRATION DE MAILLAGE 55

 MÉTHODE FRONTALE : ALGORITHME

Etape 1 : Initialisation du front :

• Discrétisation de la frontière
• Orientation consistante de chaque
composante connexe de la frontière
• Ajout des entités frontières au front

Annabelle Collin GÉNÉRATION DE MAILLAGE 56

 MÉTHODE FRONTALE : ALGORITHME

Etape 1 : Initialisation du front :

• Discrétisation de la frontière
• Orientation consistante de chaque
composante connexe de la frontière
• Ajout des entités frontières au front
Etape 2 : Définition/prise en compte d’une
fonction de taille

Etape 3 : Analyse du front

Etape 4 : Sélection d’une entité de front :

• Sélection d’un point idéal P
• Recherche des sommets proches de P
pouvant-être utilisés au lieu de P a
• Vérification de l’absence d’intersections
• Màj du maillage et du front
Etape 5 : Tant que le front n’est pas vide,
retour à l’étape 3.

Annabelle Collin GÉNÉRATION DE MAILLAGE 57

 MÉTHODE FRONTALE : ALGORITHME

Etape 1 : Initialisation du front :

• Discrétisation de la frontière
• Orientation consistante de chaque
composante connexe de la frontière
• Ajout des entités frontières au front
Etape 2 : Définition/prise en compte d’une
fonction de taille

Etape 3 : Analyse du front

Etape 4 : Sélection d’une entité de front :

• Sélection d’un point idéal P
• Recherche des sommets proches de P
pouvant-être utilisés au lieu de P
• Vérification de l’absence d’intersections
• Màj du maillage et du front
Etape 5 : Tant que le front n’est pas vide,
retour à l’étape 3.

Annabelle Collin GÉNÉRATION DE MAILLAGE 58

 MÉTHODE FRONTALE : ALGORITHME

Etape 1 : Initialisation du front :

• Discrétisation de la frontière
• Orientation consistante de chaque
composante connexe de la frontière
• Ajout des entités frontières au front
Etape 2 : Définition/prise en compte d’une
fonction de taille

Etape 3 : Analyse du front

Etape 4 : Sélection d’une entité de front :

• Sélection d’un point idéal P
• Recherche des sommets proches de P
pouvant-être utilisés au lieu de P
• Vérification de l’absence d’intersections
• Màj du maillage et du front
Etape 5 : Tant que le front n’est pas vide,
retour à l’étape 3.

Annabelle Collin GÉNÉRATION DE MAILLAGE 59

 MÉTHODE FRONTALE : ALGORITHME

Etape 1 : Initialisation du front :

• Discrétisation de la frontière
• Orientation consistante de chaque
composante connexe de la frontière
• Ajout des entités frontières au front
Etape 2 : Définition/prise en compte d’une
fonction de taille

Etape 3 : Analyse du front

Etape 4 : Sélection d’une entité de front :

• Sélection d’un point idéal P
• Recherche des sommets proches de P
pouvant-être utilisés au lieu de P
• Vérification de l’absence d’intersections
• Màj du maillage et du front
Etape 5 : Tant que le front n’est pas vide,
retour à l’étape 3.

Annabelle Collin GÉNÉRATION DE MAILLAGE 60

 MÉTHODE FRONTALE : ALGORITHME

Etape 1 : Initialisation du front :

• Discrétisation de la frontière
• Orientation consistante de chaque
composante connexe de la frontière
• Ajout des entités frontières au front
Etape 2 : Définition/prise en compte d’une
fonction de taille

Etape 3 : Analyse du front

Etape 4 : Sélection d’une entité de front :

• Sélection d’un point idéal P
• Recherche des sommets proches de P
pouvant-être utilisés au lieu de P
• Vérification de l’absence d’intersections
• Màj du maillage et du front
Etape 5 : Tant que le front n’est pas vide,
retour à l’étape 3.

Annabelle Collin GÉNÉRATION DE MAILLAGE 61

 MÉTHODE FRONTALE : ALGORITHME

Etape 1 : Initialisation du front :

• Discrétisation de la frontière
• Orientation consistante de chaque
composante connexe de la frontière
• Ajout des entités frontières au front
Etape 2 : Définition/prise en compte d’une
fonction de taille

Etape 3 : Analyse du front

Etape 4 : Sélection d’une entité de front :

• Sélection d’un point idéal P
• Recherche des sommets proches de P
pouvant-être utilisés au lieu de P
• Vérification de l’absence d’intersections
• Màj du maillage et du front
Etape 5 : Tant que le front n’est pas vide,
retour à l’étape 3.

Annabelle Collin GÉNÉRATION DE MAILLAGE 62

 MÉTHODE FRONTALE : ALGORITHME

Etape 1 : Initialisation du front :

• Discrétisation de la frontière
• Orientation consistante de chaque
composante connexe de la frontière
• Ajout des entités frontières au front
Etape 2 : Définition/prise en compte d’une
fonction de taille

Etape 3 : Analyse du front

Etape 4 : Sélection d’une entité de front :

• Sélection d’un point idéal P
• Recherche des sommets proches de P
pouvant-être utilisés au lieu de P
• Vérification de l’absence d’intersections
• Màj du maillage et du front
Etape 5 : Tant que le front n’est pas vide,
retour à l’étape 3.

Annabelle Collin GÉNÉRATION DE MAILLAGE 63

 MÉTHODE FRONTALE : ALGORITHME

Etape 1 : Initialisation du front :

• Discrétisation de la frontière
• Orientation consistante de chaque
composante connexe de la frontière
• Ajout des entités frontières au front
Etape 2 : Définition/prise en compte d’une
fonction de taille

Etape 3 : Analyse du front

Etape 4 : Sélection d’une entité de front :

• Sélection d’un point idéal P
• Recherche des sommets proches de P
pouvant-être utilisés au lieu de P
• Vérification de l’absence d’intersections
• Màj du maillage et du front
Etape 5 : Tant que le front n’est pas vide,
retour à l’étape 3.

Annabelle Collin GÉNÉRATION DE MAILLAGE 64

 MÉTHODE FRONTALE : ALGORITHME

Etape 1 : Initialisation du front :

• Discrétisation de la frontière
• Orientation consistante de chaque
composante connexe de la frontière
• Ajout des entités frontières au front
Etape 2 : Définition/prise en compte d’une
Intersection
fonction de taille

Etape 3 : Analyse du front

Etape 4 : Sélection d’une entité de front :

• Sélection d’un point idéal P
• Recherche des sommets proches de P
pouvant-être utilisés au lieu de P
• Vérification de l’absence d’intersections
• Màj du maillage et du front
Etape 5 : Tant que le front n’est pas vide,
retour à l’étape 3.

Annabelle Collin GÉNÉRATION DE MAILLAGE 65

 MÉTHODE FRONTALE : ALGORITHME

Etape 1 : Initialisation du front :

• Discrétisation de la frontière
• Orientation consistante de chaque
composante connexe de la frontière
• Ajout des entités frontières au front
Etape 2 : Définition/prise en compte d’une
fonction de taille

Etape 3 : Analyse du front

Etape 4 : Sélection d’une entité de front :

• Sélection d’un point idéal P
• Recherche des sommets proches de P
pouvant-être utilisés au lieu de P
• Vérification de l’absence d’intersections
• Màj du maillage et du front
Etape 5 : Tant que le front n’est pas vide,
retour à l’étape 3.

Etape 6 : Optimisation du maillage

Annabelle Collin GÉNÉRATION DE MAILLAGE 66

 MÉTHODE FRONTALE:
2. DIFFICULTÉS, AVANTAGES ET INCONVÉNIENTS DE LA MÉTHODE

a. DIFFICULTÉS ALGORITHMIQUES
• Pré-requis initial : orientation des éléments du front
• Sélection d’une entité du front
• Identification des points admissibles pour créer un élément
• Validation des éléments à partir de ces points
• convergence
b. AVANTAGES
• Maillages contenant généralement beaucoup d’éléments de (très) bonne qualité
c. INCONVÉNIENTS
• Robustesse en 3D

Annabelle Collin ANNABELLE COLLIN 67

 MÉTHODE QUADTREE (2D) / OCTREE (3D) :
1. ALGORITHME (ILLUSTRATION SUR UN EXEMPLE EN 2D)

Annabelle Collin GÉNÉRATION DE MAILLAGE 68

 MÉTHODE QUADREE (2D) / OCTREE (3D) : ALGORITHME

Etape 1 : Initialisations : 1 11

• Discrétisation de la frontière 2
10
• Construction d’une boite
englobante du domaine

3
5

6
9

Annabelle Collin ANNABELLE COLLIN 69

 MÉTHODE QUADREE (2D) / OCTREE (3D) : ALGORITHME

Etape 1 : Initialisations : 1 11

• Discrétisation de la frontière 2
10
• Construction d’une boite
englobante du domaine

Etape 2 : Décomposition de l’arbre :

Subdivisions récursives jusqu’à :
• 1 seul noeud par feuille
• 1 seule arête par feuille 4

3
5

6
9

Annabelle Collin ANNABELLE COLLIN 70

 MÉTHODE QUADREE (2D) / OCTREE (3D) : ALGORITHME

Etape 1 : Initialisations : 1 11

• Discrétisation de la frontière 2
10
• Construction d’une boite
englobante du domaine

Etape 2 : Décomposition de l’arbre :

Subdivisions récursives jusqu’à :
• 1 seul noeud par feuille
• 1 seule arête par feuille 4

3
5

6
9

Annabelle Collin ANNABELLE COLLIN 71

 MÉTHODE QUADREE (2D) / OCTREE (3D) : ALGORITHME

Etape 1 : Initialisations : 1 11

• Discrétisation de la frontière 2
10
• Construction d’une boite
englobante du domaine

Etape 2 : Décomposition de l’arbre :

Subdivisions récursives jusqu’à :
• 1 seul noeud par feuille
• 1 seule arête par feuille 4

3
5

6
9

Annabelle Collin ANNABELLE COLLIN 72

 MÉTHODE QUADREE (2D) / OCTREE (3D) : ALGORITHME

Etape 1 : Initialisations : 1 11

• Discrétisation de la frontière 2
10
• Construction d’une boite
englobante du domaine

Etape 2 : Décomposition de l’arbre :

Subdivisions récursives jusqu’à :
• 1 seul noeud par feuille
• 1 seule arête par feuille 4

3
Etape 3 : Equilibrage de l’arbre
5

6
9

Annabelle Collin ANNABELLE COLLIN 73

 MÉTHODE QUADREE (2D) / OCTREE (3D) : ALGORITHME

Etape 1 : Initialisations : 1 11

• Discrétisation de la frontière 2
10
• Construction d’une boite
englobante du domaine

Etape 2 : Décomposition de l’arbre :

Subdivisions récursives jusqu’à :
• 1 seul noeud par feuille
• 1 seule arête par feuille 4

3
Etape 3 : Equilibrage de l’arbre
5

Etape 4 : Triangulation des feuilles

par des motifs prédéfinis

6
9

Annabelle Collin ANNABELLE COLLIN 74

 MÉTHODE QUADREE (2D) / OCTREE (3D) : ALGORITHME

Etape 1 : Initialisations : 1 11

• Discrétisation de la frontière 2
10
• Construction d’une boite
englobante du domaine

Etape 2 : Décomposition de l’arbre :

Subdivisions récursives jusqu’à :
• 1 seul noeud par feuille
• 1 seule arête par feuille 4

3
Etape 3 : Equilibrage de l’arbre
5

Etape 4 : Triangulation des feuilles

par des motifs prédéfinis

6
9

Annabelle Collin ANNABELLE COLLIN 75

 MÉTHODE QUADREE (2D) / OCTREE (3D) : ALGORITHME

Etape 1 : Initialisations : 1 11

• Discrétisation de la frontière 2
10
• Construction d’une boite
englobante du domaine

Etape 2 : Décomposition de l’arbre :

Subdivisions récursives jusqu’à :
• 1 seul noeud par feuille
• 1 seule arête par feuille 4

3
Etape 3 : Equilibrage de l’arbre
5

Etape 4 : Triangulation des feuilles

par des motifs prédéfinis

6
9

Annabelle Collin ANNABELLE COLLIN 76

 MÉTHODE QUADREE (2D) / OCTREE (3D) : ALGORITHME

Etape 1 : Initialisations : 1 11

• Discrétisation de la frontière 2
10
• Construction d’une boite
englobante du domaine

Etape 2 : Décomposition de l’arbre :

Subdivisions récursives jusqu’à :
• 1 seul noeud par feuille
• 1 seule arête par feuille 4

3
Etape 3 : Equilibrage de l’arbre
5

Etape 4 : Triangulation des feuilles

par des motifs prédéfinis

6
9

Annabelle Collin ANNABELLE COLLIN 77

 MÉTHODE QUADREE (2D) / OCTREE (3D) : ALGORITHME

Etape 1 : Initialisations : 1 11

• Discrétisation de la frontière 2
10
• Construction d’une boite
englobante du domaine

Etape 2 : Décomposition de l’arbre :

Subdivisions récursives jusqu’à :
• 1 seul noeud par feuille
• 1 seule arête par feuille 4

3
Etape 3 : Equilibrage de l’arbre
5

Etape 4 : Triangulation des feuilles

par des motifs prédéfinis

Etape 5 : Suppression de la boite

englobante
7

Etape 6 : Optimisation du maillage 6

9

Annabelle Collin ANNABELLE COLLIN 78

 MÉTHODE QUADREE (2D) / OCTREE (3D) :
2. DIFFICULTÉS, AVANTAGES ET INCONVÉNIENTS DE LA MÉTHODE

a. DIFFICULTÉS ALGORITHMIQUES
• Calcul d’intersection de la géométrie avec l’arbre
• Procédures de recherche dans l’arbre
b. AVANTAGES
• Robustesse
• Convergence
c. INCONVÉNIENTS
• On ne retrouve pas la frontière initiale
• Dépendance aux transformations géométriques
• Maillages à optimiser : aucun critère de qualité n’est pris en compte lors de la construction

Annabelle Collin ANNABELLE COLLIN 79

COMPARAISON DES TROIS MÉTHODES

Qualité Préservation
Robustesse Performance des
frontières
Moy Min Max

++
Quadtree ++ ++ ++ - Non
O(n)

+
Delaunay + + + + Oui
O(n log(n))

-
Frontal - - - ++ Oui
O(n log(n))

Annabelle Collin GÉNÉRATION DE MAILLAGE 80

TROISIÈME PARTIE: ADAPTATION DE MAILLAGE

• Qu’est ce que l’adaptation de maillage ?

• Estimation d’erreur

• Technique pratique d’adaptation de maillage

• Illustration sur un exemple

Annabelle Collin ANNABELLE COLLIN 81

QU’EST-CE QUE L’ADAPTATION DE MAILLAGE ?

• Erreur de discrétisation spatiale dans les modèles numériques

• Adaptation du maillage afin de minimiser et / ou contrôler cette erreur

• Rappel : la qualité du maillage est cruciale pour la qualité du résultat

• Trouver des estimations a posteriori en utilisant les solutions approchées

pour permettre l'adaptation des maillages en pratique

• Deux stratégies :
• Raffiner uniformément le maillage jusqu'à l'obtention d'une solution
indépendante du maillage (ou convergée) : coût de calcul très important
• Rechercher un maillage non-uniforme :
• Raffinements locaux là où c'est nécessaire
• Faible nombre de noeuds dans les zones où la solution varie peu

• Maillage adaptatif anisotrope doit tenir compte des variations locales de la

solution selon leurs directions principales

Annabelle Collin ADAPTATION DE MAILLAGE 82

ESTIMATION D’ERREUR

• Problème étudié :
Trouver u V telle que a(u, v) = l(v), v V.

• Majoration d’erreur a priori en majorant l’erreur d’approximation de la solution

exacte par l’erreur d’interpolation
1
2 2
u Ph u H1 = u Ph u H1
T T

• Théorème
Dans le cas d’éléments finis de degré k et d’une solution exacte u du
problème elliptique suffisamment régulière. On a les majorations suivantes :
u Ph u L2 Ch k+1 |u|H k+1

u Ph u H1 Chk |u|H k+1

où h est la longueur du plus grand côté du maillage et C une constante

indépendante de h.

Annabelle Collin ADAPTATION DE MAILLAGE 83

 TECHNIQUE PRATIQUE D’ADAPTATION DE MAILLAGE

• Il est possible d’obtenir une formulation anisotrope de l’erreur d’interpolation

sur chaque triangle :

u Ph u ,T cd max max e, |Hu (x)|e

x T e ET

Hessienne
2 2 2
x12
u x1 x 2 u ··· x1 x n u
Maximum sur les 2 2
··· 2
Maximum sur les arêtes x2 x 1 u x22
u x2 x n u
coordonnées du triangle Hu = .. .. .. ..
. . . .
2 2 2
xn x 1 u xn x2 u ··· xn2
u

Annabelle Collin ADAPTATION DE MAILLAGE 84

TECHNIQUE PRATIQUE D’ADAPTATION DE MAILLAGE

• Formulation anisotrope de l’erreur d’interpolation sur chaque triangle :

u Ph u ,T cd max max e, |Hu (x)|e
x T e ET

En pratique, le maximum de la Hessienne n’est pas connu …

• Pour y rémédier, on suppose que l’on sache exhiber sur le triangle T un

tenseur de métrique M(T) vérifiant :

max e, |Hu (x)|e e, M(T )e , pour tout e ET

x T

• Du coup, l’erreur d’interpolation commise sur un élément T est estimée par la

formule suivante :
ε T = cd max e, M(T )e
e ET

Cette relation signifie que l’erreur d’interpolation est proportionnelle au carré de

la plus grande longueur des arêtes de K dans la métrique M(K).

Annabelle Collin ADAPTATION DE MAILLAGE 85

ILLUSTRATION SUR UN EXEMPLE

Écoulement supersonique autour d'un prisme (L. Nouveau)

Annabelle Collin ADAPTATION DE MAILLAGE 86

ILLUSTRATION SUR UN EXEMPLE

Écoulement supersonique autour d'un prisme (L. Nouveau)

Zoom autour du prisme du maillage initial Nouveau maillage

Solution obtenue Nouvelle solution

Annabelle Collin ADAPTATION DE MAILLAGE 87