MAILLAGES POUR LE

CALCUL SCIENTIFIQUE

ANNABELLE COLLIN ET CÉCILE DOBRZYNSKI

PLAN

Maillage : 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

Génération de maillage
• Pourquoi construire un maillage est difficile ?
• Schéma général de construction de maillage
• Méthode octree/quadtree
• Méthode de Delaunay
• Méthode frontale
• Comparaison des 3 méthodes

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 ET CÉCILE DOBRZYNSKI 2

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 ET CÉCILE DOBRZYNSKI 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)
1.Flow disruption across strut
• OCT: Lumen wall and struts detections
2.Flow may follow struts pattern
1.Semi-automatic struts on each OCT-frame 3.Justification for directional
2.Skeleton topology reconstruction of stent WSS analysis
3.Spline skeleton interpolation
4.3D reconstruction by ad-hoc sweeping Outer
algorithms (pi/2)
5.Stent surface meshing
Flow
-Pi
• Angiography Registration TAWSS flat mapping (with VTK/VMTK & Paraview) Impact on Wall Shear Stress
V4

1.Requires bi-plane angiography Zoom V1

3

2.Centerline reconstruction with • Observations: aVR

3
2
1 Zoom 1
QAngioXA (Medis)
2
1
0
1
Zoom 2
3 600
I 2
3.Segmented OCT to derive lumen wall 1.High Time Averaged WSS on
2 0 400
1 3 200
1 0
3 600 V5

4.Registration performed following top of scaffold strut

2
2 0 400
1 3 200
1 0 3
600 V2
centreline Frenet frame 0
1 2.Low 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 (www.cgal.org): 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

Trois 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

GÉNÉRATION DE MAILLAGE

• Pourquoi construire un maillage est difficile ?

• Schéma général de construction de maillage

• Méthode octree/quadtree

• Méthode de Delaunay

• Méthode frontale

• Comparaison des 3 méthodes

Annabelle Collin ANNABELLE COLLIN ET CÉCILE DOBRZYNSKI 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 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 d’un arbre
• Création d’un maillage à proprement parler

• Méthodes frontale et de Delaunay

• Paramétrisation du maillage
• Description géométrique
• Taille des éléments …
• Discrétisation du bord
• Création de points intérieurs au domaine

Annabelle Collin GÉNÉRATION DE MAILLAGE 21

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

Illustration de la méthode sur un exemple en 2D

Annabelle Collin GÉNÉRATION DE MAILLAGE 22

MÉTHODE DE DELAUNAY

Critère de Delaunay

Triangulation quelconque Triangulation de Delaunay

Annabelle Collin GÉNÉRATION DE MAILLAGE 23

MÉTHODE DE DELAUNAY

Retournement d'arêtes

Insertion de points

Annabelle Collin GÉNÉRATION DE MAILLAGE 24

MÉTHODE FRONTALE

Illustration de la méthode sur un exemple en 2D

etc …

Annabelle Collin GÉNÉRATION DE MAILLAGE 25

COMPARAISON DES TROIS MÉTHODES

Robuste Performance Qualité

Quadtree +

Delaunay +

Frontal +

Annabelle Collin GÉNÉRATION DE MAILLAGE 26

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 ET CÉCILE DOBRZYNSKI 27

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 28

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 29

 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 30

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 31

ILLUSTRATION SUR UN EXEMPLE

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

Annabelle Collin ADAPTATION DE MAILLAGE 32

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 33