Upload
juliendompierre
View
4.054
Download
3
Embed Size (px)
DESCRIPTION
Les critères de forme, qui fournissent un moyen quantitatif efficace decomparaison de la forme des éléments d'un maillage, sont de grandeimportance dans beaucoup de domaines liés à l'analyse éléments finis, et enparticulier, dans l'adaptation de maillage. Alors que les travaux les plussérieux dans le domaine de l'adaptation de maillage se servent directementdes critères de forme, très peu de travaux ont été consacrés à lacomparaison réelle des critères de forme, à l'exception notable de Liu et deJoe (1994) qui ont analysé un ensemble choisi de quelques critères. Tandis que les travaux publiés utilisent des critères de forme courammentconnus, de nouveau critères de forme apparaissent dans la littératurerécente pour lesquels il n'y a pas eu d'analyse. En outre, aucun schéma declassification n'a été proposé et la validité des nouveaux critères n'estpas souvent évaluée. Cet exposé vise à examiner un éventail de critères deforme généralement utilisés, à définir des critères de validité pour cescritères de forme et ensuite à les classifier dans de larges catégories, enparticulier, les critères de forme valides versus les non valides. L'exposéaborde également des questions concernant l'utilisation des critères deforme dans des espaces non-euclidiens, telles que l'utilisation des critèresde forme dans les espaces Riemanniens pour l'adaptation anisotrope demaillages.L'exposé récapitule les propriétés importantes des simplexes et introduitune classification des dégénérescences en deux et trois dimensions. L'exposéprésente une revue des critères de forme, des critères sur la validité desdifférents critères de forme ainsi qu'une méthode de visualisation descritères de forme qui aide la comparaison entre eux. Les critères de formesont alors classifiés, et des conclusions sont tirées sur la pertinence dedévelopper de nouveaux critères de forme ou d'en choisir un parmi ceuxactuellement existants.L'adaptation de maillage est un processus qui produit des maillages et dessolutions numériques sur ces maillages tels que maillages et solutionsconvergent ensemble vers un certain but, qui est habituellementl'équirépartition de l'erreur. Pour les maillages non structurés, leprocessus d'adaptation de maillage peut être décomposé en deux étapes:d'abord, une carte de taille est spécifiée en analysant la solutionnumérique; en second lieu, on construit un maillage qui satisfait cettecarte de de taille.Le sujet de cet exposé est une méthode pour quantifier combien un maillagesatisfait une carte de taille spécifiée.Il y a plus de dix ans, Marie-Gabrielle Vallet (1990, 1991, 1992) a montréqu'une carte de taille représentée par un champ de tenseurs métriquesfacilite la génération des maillages adaptés et anisotropes en combinant lataille et l'étirement désirés dans un seul concept mathématique simple. Lestenseurs métriques modifient la manière dont les distances sont mesurées.Le maillage adapté et anisotrope dans l'espace euclidien est construit enétablissant un maillage régulier, isotrope et unitaire dans l'espacemétrique du tenseur.L'utilisation d'un champ de tenseurs métriques pour la carte de taille estmaintenant un outil largement répandu pour la génération et l'adaptation demaillages anisotropes. Elle a été employée en deux et trois dimensions, pourdifférentes simulations d'équations aux dérivées partielles avec lesméthodes d'éléments finis et de volumes finis, pour la discrétisationextérieure (?), la représentation graphique, etc... Les références les pluscomplètes sont George et Borouchaki (1997), Frey et George (1999), et lesréférences incluses.Cependant, la question de la conformité d'un maillage à un champ de tenseursmétriques n'est toujours pas claire. Il n'y a pas de méthode pour mesurer ledegré auquel un maillage satisfait une carte de
Citation preview
Qualité desmaillagesJulien Dompierre
Centre de Recherche en Calcul Applique (CERCA)
Ecole Polytechnique de Montreal
Qualite des maillages – p.1/329
Auteurs
Professionnels de rechercheJulien DompierrePaul LabbéMarie-Gabrielle Vallet
ProfesseursFrançois GuibaultJean-Yves TrépanierRicardo Camarero
Qualite des maillages – p.2/329
Références– 1
J. DOMPIERRE, P. LABBÉ,M.-G. VALLET, F. GUIBAULTET R. CAMARERO, Critèresde qualité pour les maillagessimpliciaux. Dans Maillage etadaptation, Hermès, octobre2001, Paris, pages 311–348.
Qualite des maillages – p.3/329
Références– 2
A. LIU et B. JOE, Relationship betweenTetrahedr on Shape Measures , Bit, Vol. 34,pages 268–287, (1994).
Qualite des maillages – p.4/329
Références– 3
P. LABBÉ, J. DOMPIERRE, M.-G. VALLET, F.GUIBAULT et J.-Y. TRÉPANIER, A Univer salMeasure of the Conf ormity of a Mesh withRespect to an Anisotr opic Metric Field ,Submitted to Int. J. for Numer. Meth. in Engng,(2003).
Qualite des maillages – p.5/329
Références– 4
P. LABBÉ, J. DOMPIERRE, M.-G. VALLET, F.GUIBAULT et J.-Y. TRÉPANIER, A Measure ofthe Conf ormity of a Mesh to an Anisotr opicMetric , Tenth International Meshing Roundtable,Newport Beach, CA, pages 319–326, (2001).
Qualite des maillages – p.6/329
Références– 5
P.-L. GEORGE ET H. BOROU-CHAKI, Triangulation de De-launay et maillage, applica-tions aux éléments finis. Her-mès, 1997, Paris.
Qualite des maillages – p.7/329
Références– 6
P. J. FREY AND P.-L.GEORGE, Maillages. Ap-plications aux éléments finis.Hermès, 1999, Paris.
Qualite des maillages – p.8/329
Tabledesmatières
1. Introduction2. Définition d’un sim-
plexe3. Dégénérescence des
simplexes4. Qualité de forme des
simplexes5. Formules pour les
simplexes6. Voronoï, Delaunay et
Riemann7. Critères de formes et
de Delaunay
8. Éléments non simpli-ciaux
9. Représentation descritères de forme
10. Équivalence des cri-tères de forme
11. Qualité globale etoptimisation
12. Qualité en taille dessimplexes
13. Qualité universelle14. Conclusions
Qualite des maillages – p.9/329
Intr oduction et justifications
On travaille sur la génération, l’adaptation etl’optimisation de maillages.
Comment choisir la configuration qui donne lesplus beaux triangles ? Il faut un critère de qualitédes triangles.
Qualite des maillages – p.10/329
Retournementd’une face
Comment choisir la configuration qui donne lesplus beaux tétraèdres ? Il faut un critère dequalité des tétraèdres.
Qualite des maillages – p.11/329
Retournementd’une arête
BA A
B
2
S3S3
S
S1S1
S2
S
5
4 S4
S5S
Comment choisir la configuration qui donne lesplus beaux tétraèdres ? Il faut un critère dequalité des tétraèdres.
Qualite des maillages – p.12/329
Optimisation de maillages
Soit et , deux ptimiseurs de maillagestridimensionnels tétraédriques non structurés.
Quelle est la norme d’un optimiseur demaillage ?Comment peut-on affirmer que ?
Qualite des maillages – p.13/329
Optimisation de maillages
Soit et , deux ptimiseurs de maillagestridimensionnels tétraédriques non structurés.Quelle est la norme d’un optimiseur demaillage ?
Comment peut-on affirmer que ?
Qualite des maillages – p.13/329
Optimisation de maillages
Soit et , deux ptimiseurs de maillagestridimensionnels tétraédriques non structurés.Quelle est la norme d’un optimiseur demaillage ?Comment peut-on affirmer que ?
Qualite des maillages – p.13/329
Mais c’est très simple!
Soit , un banc d’essai (un benchmark).
Soit , le maillage optimisé obtenuavec l’optimiseur .Soit , le maillage optimisé obtenuavec l’optimiseur .La sagesse populaire dit : “On juge un arbre àses fruits”.Si alors .
Qualite des maillages – p.14/329
Mais c’est très simple!
Soit , un banc d’essai (un benchmark).Soit , le maillage optimisé obtenuavec l’optimiseur .
Soit , le maillage optimisé obtenuavec l’optimiseur .La sagesse populaire dit : “On juge un arbre àses fruits”.Si alors .
Qualite des maillages – p.14/329
Mais c’est très simple!
Soit , un banc d’essai (un benchmark).Soit , le maillage optimisé obtenuavec l’optimiseur .Soit , le maillage optimisé obtenuavec l’optimiseur .
La sagesse populaire dit : “On juge un arbre àses fruits”.Si alors .
Qualite des maillages – p.14/329
Mais c’est très simple!
Soit , un banc d’essai (un benchmark).Soit , le maillage optimisé obtenuavec l’optimiseur .Soit , le maillage optimisé obtenuavec l’optimiseur .La sagesse populaire dit : “On juge un arbre àses fruits”.
Si alors .
Qualite des maillages – p.14/329
Mais c’est très simple!
Soit , un banc d’essai (un benchmark).Soit , le maillage optimisé obtenuavec l’optimiseur .Soit , le maillage optimisé obtenuavec l’optimiseur .La sagesse populaire dit : “On juge un arbre àses fruits”.Si alors .
Qualite des maillages – p.14/329
Bancsd’essaisd’optimisation de maillages
J. DOMPIERRE, P. LABBÉ, F. GUIBAULT etR. CAMARERO.
Proposal of Benchmarks for 3D UnstructuredTetrahedral Mesh Optimization.
7th International Meshing Roundtable, Dearborn,MI, octobre 1998, pages 459–478.
Qualite des maillages – p.15/329
Le piège...
Parce qu’on ne connaît pas la norme d’unoptimiseur, on a remplacé la comparaison dedeux optimiseurs par la comparaison de deuxmaillages.
Quelle est la norme d’un maillage ?Comment peut-on affirmer que ?
C’est ce que vous saurez bientôt, ou vousserez remboursés !
Qualite des maillages – p.16/329
Le piège...
Parce qu’on ne connaît pas la norme d’unoptimiseur, on a remplacé la comparaison dedeux optimiseurs par la comparaison de deuxmaillages.Quelle est la norme d’un maillage ?
Comment peut-on affirmer que ?
C’est ce que vous saurez bientôt, ou vousserez remboursés !
Qualite des maillages – p.16/329
Le piège...
Parce qu’on ne connaît pas la norme d’unoptimiseur, on a remplacé la comparaison dedeux optimiseurs par la comparaison de deuxmaillages.Quelle est la norme d’un maillage ?Comment peut-on affirmer que ?
C’est ce que vous saurez bientôt, ou vousserez remboursés !
Qualite des maillages – p.16/329
Le piège...
Parce qu’on ne connaît pas la norme d’unoptimiseur, on a remplacé la comparaison dedeux optimiseurs par la comparaison de deuxmaillages.Quelle est la norme d’un maillage ?Comment peut-on affirmer que ?C’est ce que vous saurez bientôt, ou vousserez remboursés !
Qualite des maillages – p.16/329
Cequ’il faut retenir
Cet exposé portera sur les notions de qualitédes éléments d’un maillage et sur la qualité detout un maillage.
La notion de qualité des éléments estnécessaire pour les algorithmes deretournement d’arêtes et de faces.La notion de qualité de tout un maillage estnécessaire dans la recherche sur l’optimisationdes maillages.
Qualite des maillages – p.17/329
Cequ’il faut retenir
Cet exposé portera sur les notions de qualitédes éléments d’un maillage et sur la qualité detout un maillage.La notion de qualité des éléments estnécessaire pour les algorithmes deretournement d’arêtes et de faces.
La notion de qualité de tout un maillage estnécessaire dans la recherche sur l’optimisationdes maillages.
Qualite des maillages – p.17/329
Cequ’il faut retenir
Cet exposé portera sur les notions de qualitédes éléments d’un maillage et sur la qualité detout un maillage.La notion de qualité des éléments estnécessaire pour les algorithmes deretournement d’arêtes et de faces.La notion de qualité de tout un maillage estnécessaire dans la recherche sur l’optimisationdes maillages.
Qualite des maillages – p.17/329
Table des matières
1. Introduction2. Définition d’un simplexe3. Dégénérescence des sim-
plexes4. Qualité de forme des sim-
plexes5. Formules pour les sim-
plexes6. Voronoï, Delaunay et Rie-
mann7. Critères de formes et de
Delaunay
8. Éléments non simpliciaux9. Représentation des cri-
tères de forme10. Équivalence des critères
de forme11. Qualité globale et optimi-
sation12. Qualité en taille des sim-
plexes13. Qualité universelle14. Conclusions
Qualite des maillages – p.18/329
Définition d’un simple xe
Les maillages en deux et trois dimensions sontconstitués de polygones ou de polyèdres appeléséléments.
Les plus simples d’entre eux, les simplexes, sont ceuxqui ont le nombre minimal de sommets.Le segment en une dimension.Le triangle en deux dimensions.Le tétraèdre en trois dimensions.Le hypertétraèdre en quatre dimensions.Les quadrilatères, les pyramides, les prismes, les
hexaèdres et autres bizarreries sont des éléments nonsimpliciaux.
Qualite des maillages – p.19/329
Définition d’un simple xe
Les maillages en deux et trois dimensions sontconstitués de polygones ou de polyèdres appeléséléments.Les plus simples d’entre eux, les simplexes, sont ceux
qui ont le nombre minimal de sommets.
Le segment en une dimension.Le triangle en deux dimensions.Le tétraèdre en trois dimensions.Le hypertétraèdre en quatre dimensions.Les quadrilatères, les pyramides, les prismes, les
hexaèdres et autres bizarreries sont des éléments nonsimpliciaux.
Qualite des maillages – p.19/329
Définition d’un simple xe
Les maillages en deux et trois dimensions sontconstitués de polygones ou de polyèdres appeléséléments.Les plus simples d’entre eux, les simplexes, sont ceux
qui ont le nombre minimal de sommets.Le segment en une dimension.
Le triangle en deux dimensions.Le tétraèdre en trois dimensions.Le hypertétraèdre en quatre dimensions.Les quadrilatères, les pyramides, les prismes, les
hexaèdres et autres bizarreries sont des éléments nonsimpliciaux.
Qualite des maillages – p.19/329
Définition d’un simple xe
Les maillages en deux et trois dimensions sontconstitués de polygones ou de polyèdres appeléséléments.Les plus simples d’entre eux, les simplexes, sont ceux
qui ont le nombre minimal de sommets.Le segment en une dimension.Le triangle en deux dimensions.
Le tétraèdre en trois dimensions.Le hypertétraèdre en quatre dimensions.Les quadrilatères, les pyramides, les prismes, les
hexaèdres et autres bizarreries sont des éléments nonsimpliciaux.
Qualite des maillages – p.19/329
Définition d’un simple xe
Les maillages en deux et trois dimensions sontconstitués de polygones ou de polyèdres appeléséléments.Les plus simples d’entre eux, les simplexes, sont ceux
qui ont le nombre minimal de sommets.Le segment en une dimension.Le triangle en deux dimensions.Le tétraèdre en trois dimensions.
Le hypertétraèdre en quatre dimensions.Les quadrilatères, les pyramides, les prismes, les
hexaèdres et autres bizarreries sont des éléments nonsimpliciaux.
Qualite des maillages – p.19/329
Définition d’un simple xe
Les maillages en deux et trois dimensions sontconstitués de polygones ou de polyèdres appeléséléments.Les plus simples d’entre eux, les simplexes, sont ceux
qui ont le nombre minimal de sommets.Le segment en une dimension.Le triangle en deux dimensions.Le tétraèdre en trois dimensions.Le hypertétraèdre en quatre dimensions.
Les quadrilatères, les pyramides, les prismes, leshexaèdres et autres bizarreries sont des éléments nonsimpliciaux.
Qualite des maillages – p.19/329
Définition d’un simple xe
Les maillages en deux et trois dimensions sontconstitués de polygones ou de polyèdres appeléséléments.Les plus simples d’entre eux, les simplexes, sont ceux
qui ont le nombre minimal de sommets.Le segment en une dimension.Le triangle en deux dimensions.Le tétraèdre en trois dimensions.Le hypertétraèdre en quatre dimensions.Les quadrilatères, les pyramides, les prismes, les
hexaèdres et autres bizarreries sont des éléments nonsimpliciaux.
Qualite des maillages – p.19/329
Définition d’un -simple xe dans
Soient points � � � � � � � �,
, non situés dans le même hyperplan,c’est-à-dire tel que la matrice d’ordre ,
� � � � ��� � � �
� � � � �� � � �
......
. . ....
� � � � �� � � �
soit inversible. On appelle -simplexe des points � ,l’enveloppe convexe des points � .
Qualite des maillages – p.20/329
Un simple xe engendre
Tout point
�
, de coordonnées cartésiennes � ��� �
est caractérisé par la donnée des scalaires
� � définis comme solution du système linéaire
� � �� � �
� � � � pour
� � �� � �
�dont la matrice est .
Qualite des maillages – p.21/329
Ce qu’il faut retenir
En deux dimensions, le simplexe est le triangle.
En trois dimensions, le simplexe est le tétraèdre.Les sommets d’un simplexe dans engendrent
vecteurs qui forment une base de .Les coordonnées d’un point dans la base
engendrée par le simplexe sont les coordonnéesbarycentriques.
Qualite des maillages – p.22/329
Ce qu’il faut retenir
En deux dimensions, le simplexe est le triangle.En trois dimensions, le simplexe est le tétraèdre.
Les sommets d’un simplexe dans engendrentvecteurs qui forment une base de .Les coordonnées d’un point dans la base
engendrée par le simplexe sont les coordonnéesbarycentriques.
Qualite des maillages – p.22/329
Ce qu’il faut retenir
En deux dimensions, le simplexe est le triangle.En trois dimensions, le simplexe est le tétraèdre.Les sommets d’un simplexe dans
�engendrent
vecteurs qui forment une base de�
.
Les coordonnées d’un point dans la baseengendrée par le simplexe sont les coordonnéesbarycentriques.
Qualite des maillages – p.22/329
Ce qu’il faut retenir
En deux dimensions, le simplexe est le triangle.En trois dimensions, le simplexe est le tétraèdre.Les sommets d’un simplexe dans
�engendrent
vecteurs qui forment une base de�
.Les coordonnées � d’un point
�
dans la baseengendrée par le simplexe sont les coordonnéesbarycentriques.
Qualite des maillages – p.22/329
Table des matières
1. Introduction2. Définition d’un simplexe3. Dégénérescence des sim-
plexes4. Qualité de forme des sim-
plexes5. Formules pour les sim-
plexes6. Voronoï, Delaunay et Rie-
mann7. Critères de formes et de
Delaunay
8. Éléments non simpliciaux9. Représentation des cri-
tères de forme10. Équivalence des critères
de forme11. Qualité globale et optimi-
sation12. Qualité en taille des sim-
plexes13. Qualité universelle14. Conclusions
Qualite des maillages – p.23/329
Dégénérescence des simple xes
Un -simplexe formé de sommets � est dégénéré sises sommets sont situés dans le même hyperplan,c’est-à-dire, si la matrice est non inversible.
Qualite des maillages – p.24/329
Dégénérescence des simple xes
Un -simplexe est dégénéré si ses sommetsn’engendrent pas l’espace
�
.
C’est le cas si les sommets sont contenus dansun espace de dimension inférieure à .Un triangle est dégénéré si ses sommets sont
colinéaires ou confondus.Un tétraèdre est dégénéré si ses sommets sont
coplanaires, colinéaires ou confondus.Notez qu’à strictement parler, un simplexe dégénéré
n’est plus un simplexe au sens de la définition.
Qualite des maillages – p.25/329
Dégénérescence des simple xes
Un -simplexe est dégénéré si ses sommetsn’engendrent pas l’espace
�
.C’est le cas si les sommets sont contenus dans
un espace de dimension inférieure à .
Un triangle est dégénéré si ses sommets sontcolinéaires ou confondus.Un tétraèdre est dégénéré si ses sommets sont
coplanaires, colinéaires ou confondus.Notez qu’à strictement parler, un simplexe dégénéré
n’est plus un simplexe au sens de la définition.
Qualite des maillages – p.25/329
Dégénérescence des simple xes
Un -simplexe est dégénéré si ses sommetsn’engendrent pas l’espace
�
.C’est le cas si les sommets sont contenus dans
un espace de dimension inférieure à .Un triangle est dégénéré si ses sommets sont
colinéaires ou confondus.
Un tétraèdre est dégénéré si ses sommets sontcoplanaires, colinéaires ou confondus.Notez qu’à strictement parler, un simplexe dégénéré
n’est plus un simplexe au sens de la définition.
Qualite des maillages – p.25/329
Dégénérescence des simple xes
Un -simplexe est dégénéré si ses sommetsn’engendrent pas l’espace
�
.C’est le cas si les sommets sont contenus dans
un espace de dimension inférieure à .Un triangle est dégénéré si ses sommets sont
colinéaires ou confondus.Un tétraèdre est dégénéré si ses sommets sont
coplanaires, colinéaires ou confondus.
Notez qu’à strictement parler, un simplexe dégénérén’est plus un simplexe au sens de la définition.
Qualite des maillages – p.25/329
Dégénérescence des simple xes
Un -simplexe est dégénéré si ses sommetsn’engendrent pas l’espace
�
.C’est le cas si les sommets sont contenus dans
un espace de dimension inférieure à .Un triangle est dégénéré si ses sommets sont
colinéaires ou confondus.Un tétraèdre est dégénéré si ses sommets sont
coplanaires, colinéaires ou confondus.Notez qu’à strictement parler, un simplexe dégénéré
n’est plus un simplexe au sens de la définition.
Qualite des maillages – p.25/329
Critère de dégénérescence
Un -simplexe est dégénéré si la matrice est noninversible. Une matrice est non inversible si sondéterminant est nul.
La mesure d’un simplexe est son aire en deuxdimensions et son volume en trois dimensions.La mesure d’un -simplexe formé de
sommets est donnée par
Un triangle est dégénéré si son aire est nulle.Un tétraèdre est dégénéré si son volume est nul.
Qualite des maillages – p.26/329
Critère de dégénérescence
Un -simplexe est dégénéré si la matrice est noninversible. Une matrice est non inversible si sondéterminant est nul.La mesure d’un simplexe est son aire en deux
dimensions et son volume en trois dimensions.
La mesure d’un -simplexe formé desommets est donnée par
Un triangle est dégénéré si son aire est nulle.Un tétraèdre est dégénéré si son volume est nul.
Qualite des maillages – p.26/329
Critère de dégénérescence
Un -simplexe est dégénéré si la matrice est noninversible. Une matrice est non inversible si sondéterminant est nul.La mesure d’un simplexe est son aire en deux
dimensions et son volume en trois dimensions.La mesure d’un -simplexe formé de
sommets � est donnée par
Un triangle est dégénéré si son aire est nulle.Un tétraèdre est dégénéré si son volume est nul.
Qualite des maillages – p.26/329
Critère de dégénérescence
Un -simplexe est dégénéré si la matrice est noninversible. Une matrice est non inversible si sondéterminant est nul.La mesure d’un simplexe est son aire en deux
dimensions et son volume en trois dimensions.La mesure d’un -simplexe formé de
sommets � est donnée par
Un triangle est dégénéré si son aire est nulle.
Un tétraèdre est dégénéré si son volume est nul.
Qualite des maillages – p.26/329
Critère de dégénérescence
Un -simplexe est dégénéré si la matrice est noninversible. Une matrice est non inversible si sondéterminant est nul.La mesure d’un simplexe est son aire en deux
dimensions et son volume en trois dimensions.La mesure d’un -simplexe formé de
sommets � est donnée par
Un triangle est dégénéré si son aire est nulle.Un tétraèdre est dégénéré si son volume est nul.
Qualite des maillages – p.26/329
Taxonomie des simple xes dégénérés
Cette taxonomique repose sur les différents étatsdégénérés possib les des simplexes.
Il y a trois cas de triangles dégénérés.Il y a dix cas de tétraèdres dégénérés.Dans ce catalogue, les quatre symboles, , et représentent des sommets de
multiplicité simple, double, triple et quadruplerespectivement.
Qualite des maillages – p.27/329
Taxonomie des simple xes dégénérés
Cette taxonomique repose sur les différents étatsdégénérés possib les des simplexes.Il y a trois cas de triangles dégénérés.
Il y a dix cas de tétraèdres dégénérés.Dans ce catalogue, les quatre symboles, , et représentent des sommets de
multiplicité simple, double, triple et quadruplerespectivement.
Qualite des maillages – p.27/329
Taxonomie des simple xes dégénérés
Cette taxonomique repose sur les différents étatsdégénérés possib les des simplexes.Il y a trois cas de triangles dégénérés.Il y a dix cas de tétraèdres dégénérés.
Dans ce catalogue, les quatre symboles, , et représentent des sommets de
multiplicité simple, double, triple et quadruplerespectivement.
Qualite des maillages – p.27/329
Taxonomie des simple xes dégénérés
Cette taxonomique repose sur les différents étatsdégénérés possib les des simplexes.Il y a trois cas de triangles dégénérés.Il y a dix cas de tétraèdres dégénérés.Dans ce catalogue, les quatre symboles, , et représentent des sommets de
multiplicité simple, double, triple et quadruplerespectivement.
Qualite des maillages – p.27/329
1 – Le chapeau
Nom
Chapeau(cap)
Arêtes dégénérées : AucuneRayon du plus petit cercle circonscrit :
Qualite des maillages – p.28/329
2 – L’aiguille
Nom
Aiguille(needle)
,
Arêtes dégénérées :Rayon du plus petit cercle circonscrit : � �
Qualite des maillages – p.29/329
3 – Le Big Crunc h
Nom
BigCrunch
, ,
Arêtes dégénérées : ToutesRayon du plus petit cercle circonscrit :Le Big Crunch est la théorie inverse du Big Bang.
Qualite des maillages – p.30/329
Dégénérescence des tétraèdres
Il y a un cas de dégénérescence en quatre sommetsconfondus.Il y a cinq cas de dégénérescence en quatre sommets
colinéaires.Il y a quatre cas de dégénérescence en quatre
sommets coplanaires.
c
d
ba
Qualite des maillages – p.31/329
1 – L’ailer on
Nom
Aileron
Arêtes dégénérées : AucuneFaces dégénérées : Un chapeauRayon de la plus petite sphère circonscrite :
Qualite des maillages – p.32/329
2 – Le chapeau
Nom
Chapeau(Cap)
Arêtes dégénérées : AucuneFaces dégénérées : AucuneRayon de la plus petite sphère circonscrite :
Qualite des maillages – p.33/329
3 – Le cerf-v olant
Nom
Cerf-volant(sliver)
Arêtes dégénérées : AucuneFaces dégénérées : AucuneRayon de la plus petite sphère circonscrite : � � ou
Qualite des maillages – p.34/329
4 – Le coin
Nom
Coin(Wedge)
Arêtes dégénérées :Faces dégénérées : Deux aiguillesRayon de la plus petite sphère circonscrite : � �
Qualite des maillages – p.35/329
5 – La paillette
Nom
Paillette
Arêtes dégénérées : AucuneFaces dégénérées : Quatre chapeauxRayon de la plus petite sphère circonscrite :
Qualite des maillages – p.36/329
6 – Le fuseau
Nom
Fuseau
Arêtes dégénérées :Faces dégénérées : Deux chapeaux et deux aiguillesRayon de la plus petite sphère circonscrite :
Qualite des maillages – p.37/329
7 – Le ciseau
Nom
Ciseau
Arêtes dégénérées :Faces dégénérées : Deux chapeaux et deux aiguillesRayon de la plus petite sphère circonscrite :
Qualite des maillages – p.38/329
8 – Le berlingot
Nom
Berlingot
Arêtes dégénérées : etFaces dégénérées : Quatre aiguillesRayon de la plus petite sphère circonscrite : � �
Qualite des maillages – p.39/329
9 – L’aiguille
Nom
Aiguille(needle)
Arêtes dégénérées : , etFaces dégénérées : Trois aiguilles et un Big CrunchRayon de la plus petite sphère circonscrite : � �
Qualite des maillages – p.40/329
10 – Le Big Crunc h
Nom
BigCrunch
Arêtes dégénérées : ToutesFaces dégénérées : Quatre Big CrunchsRayon de la plus petite sphère circonscrite :
Qualite des maillages – p.41/329
Ce qu’il faut retenir
Un triangle est dégénéré si ses sommets sontcolinéaires ou confondus, et donc si son aire est nulle.
Il y a trois cas de dégénérescence des triangles.Un tétraèdre est dégénéré si ses sommets sont
coplanaires, colinéaires ou confondus, et donc si sonvolume est nul.Il y a dix cas de dégénérescence des tétraèdres.
Qualite des maillages – p.42/329
Ce qu’il faut retenir
Un triangle est dégénéré si ses sommets sontcolinéaires ou confondus, et donc si son aire est nulle.Il y a trois cas de dégénérescence des triangles.
Un tétraèdre est dégénéré si ses sommets sontcoplanaires, colinéaires ou confondus, et donc si sonvolume est nul.Il y a dix cas de dégénérescence des tétraèdres.
Qualite des maillages – p.42/329
Ce qu’il faut retenir
Un triangle est dégénéré si ses sommets sontcolinéaires ou confondus, et donc si son aire est nulle.Il y a trois cas de dégénérescence des triangles.Un tétraèdre est dégénéré si ses sommets sont
coplanaires, colinéaires ou confondus, et donc si sonvolume est nul.
Il y a dix cas de dégénérescence des tétraèdres.
Qualite des maillages – p.42/329
Ce qu’il faut retenir
Un triangle est dégénéré si ses sommets sontcolinéaires ou confondus, et donc si son aire est nulle.Il y a trois cas de dégénérescence des triangles.Un tétraèdre est dégénéré si ses sommets sont
coplanaires, colinéaires ou confondus, et donc si sonvolume est nul.Il y a dix cas de dégénérescence des tétraèdres.
Qualite des maillages – p.42/329
Table des matières
1. Introduction2. Définition d’un simplexe3. Dégénérescence des sim-
plexes4. Qualité de forme des sim-
plexes5. Formules pour les sim-
plexes6. Voronoï, Delaunay et Rie-
mann7. Critères de formes et de
Delaunay
8. Éléments non simpliciaux9. Représentation des cri-
tères de forme10. Équivalence des critères
de forme11. Qualité globale et optimi-
sation12. Qualité en taille des sim-
plexes13. Qualité universelle14. Conclusions
Qualite des maillages – p.43/329
Qualité en forme des simple xes
Une façon habituelle de quantifier la qualité d’unmaillage est faite par le biais de la qualité des élémentsqui le composent.
Un critère de qualité couramment utilisé pour quantifierla qualité d’un élément est le critère de forme.Cette section fait le tour des différents critères de forme
utilisés pour les simplexes.
Qualite des maillages – p.44/329
Qualité en forme des simple xes
Une façon habituelle de quantifier la qualité d’unmaillage est faite par le biais de la qualité des élémentsqui le composent.Un critère de qualité couramment utilisé pour quantifier
la qualité d’un élément est le critère de forme.
Cette section fait le tour des différents critères de formeutilisés pour les simplexes.
Qualite des maillages – p.44/329
Qualité en forme des simple xes
Une façon habituelle de quantifier la qualité d’unmaillage est faite par le biais de la qualité des élémentsqui le composent.Un critère de qualité couramment utilisé pour quantifier
la qualité d’un élément est le critère de forme.Cette section fait le tour des différents critères de forme
utilisés pour les simplexes.
Qualite des maillages – p.44/329
Le simple x régulier
Définition : Un élément simplicial est régulier s’ilmaximise sa mesure pour une mesure donnée de safrontière.
Le triangle équilatéral est régulier car c’est celui qui al’aire optimale pour un périmètre donné.Le tétraèdre équilatéral est régulier car c’est celui qui a
le volume optimal pour une surface donnée de sesfaces.
Qualite des maillages – p.45/329
Le simple x régulier
Définition : Un élément simplicial est régulier s’ilmaximise sa mesure pour une mesure donnée de safrontière.Le triangle équilatéral est régulier car c’est celui qui a
l’aire optimale pour un périmètre donné.
Le tétraèdre équilatéral est régulier car c’est celui qui ale volume optimal pour une surface donnée de sesfaces.
Qualite des maillages – p.45/329
Le simple x régulier
Définition : Un élément simplicial est régulier s’ilmaximise sa mesure pour une mesure donnée de safrontière.Le triangle équilatéral est régulier car c’est celui qui a
l’aire optimale pour un périmètre donné.Le tétraèdre équilatéral est régulier car c’est celui qui a
le volume optimal pour une surface donnée de sesfaces.
Qualite des maillages – p.45/329
Critère de forme simplicial
Définition A : Un critère de forme simplicial est unefonction continue qui évalue la forme d’un simplexe, et quiest invariante par translation, rotation, réflexion ethomothétie du simplexe. Il est dit valide s’il est maximaluniquement pour le simplexe régulier et s’il est minimalpour tous les simplexes dégénérés. Les critères de formesimpliciaux sont normalisés dans l’intervalle , avecpour le simplexe régulier et pour tous les simplexesdégénérés.
Qualite des maillages – p.46/329
Remarques
L’invariance par translation, rotation et réflexion signifieque les critères de forme simpliciaux doivent êtreindépendants du système de coordonnées.
L’invariance par une homothétie valide signifie qu’ilsdoivent être adimensionnels (indépendants du systèmed’unités).La continuité signifie que les critères de forme varient
continûment en fonction de la position des sommets dusimplexe.
Qualite des maillages – p.47/329
Remarques
L’invariance par translation, rotation et réflexion signifieque les critères de forme simpliciaux doivent êtreindépendants du système de coordonnées.L’invariance par une homothétie valide signifie qu’ils
doivent être adimensionnels (indépendants du systèmed’unités).
La continuité signifie que les critères de forme varientcontinûment en fonction de la position des sommets dusimplexe.
Qualite des maillages – p.47/329
Remarques
L’invariance par translation, rotation et réflexion signifieque les critères de forme simpliciaux doivent êtreindépendants du système de coordonnées.L’invariance par une homothétie valide signifie qu’ils
doivent être adimensionnels (indépendants du systèmed’unités).La continuité signifie que les critères de forme varient
continûment en fonction de la position des sommets dusimplexe.
Qualite des maillages – p.47/329
Le rappor t des rayons
Le rapport des rayons d’un simplexe est un critère deforme défini par � �, où � et � sont les rayonsdes cercles (sphères en 3D) inscrit et circonscrit à , etest la dimension de l’espace.
�
�
Qualite des maillages – p.48/329
La rappor t des moyennes
Soit � � � � , un simplexe équilatéral ayant lemême [aire|volume] que le simplexe � � � � . Soit
, la matrice de la transformation affine de vers , i.e.
� � , , où est un vecteur detranslation.
Qualite des maillages – p.49/329
La rappor t des moyennes
Alors, le rapport des moyennes d’un simplexe est lerapport de la moyenne géométrique sur la moyennealgébrique des valeurs propres � , � [, �] de la matrice�
.
� ��� �
�
��
��� �
�
� � �
� �
�
� �� � � �� � en D
� � � �
� � �
� � �
� �� � � �� � en D
Qualite des maillages – p.50/329
Le conditionnement
FORMAGGIA et PEROTTO (2000) utilisent l’inverse duconditionnement de la matrice.
� �
� �
��
si les valeurs propres sont ordonnées en ordre croissant.
Qualite des maillages – p.51/329
Le norme de Frobenius
Freitag et Knupp (1999) utilise la norme de Frobenius de lamatrice
�
pour définir un critère de forme.
� � � ��� �
�
��� �
��
où les � sont les valeurs propres du tenseur
�
.
Qualite des maillages – p.52/329
Le minim um des angles solides
Le critère de forme simplicial ��� basé sur le minimum desangles solides du -simplexe est défini par
���
�� � � � � �
Le coefficient est la valeur de chaque angle solide du-simplexe régulier, soit en deux dimensions
et en trois dimensions.
Qualite des maillages – p.53/329
Le sin us de
Un critère de forme simplicial moins coûteux du point devue numérique est le sinus minimum. On évite ainsi lecalcul de la fonction dans le calcul de � en 2D etde � en 3D.
���
�� � � � � �
où � � en 2D et � � en 3D. est la valeurde � pour tous les angles solides du simplexe régulier,soit en 2D et en3D.
Qualite des maillages – p.54/329
Angles des faces
On pourrait définir un critère de forme basé sur le minimumdes douze angles des quatre faces du tétraèdre. Cet angleest de pour le tétraèdre régulier.Mais ce n’est pas un critère de forme valide au sens de laDéfinition A car il ne détecte pas les tétraèdres dégénérésqui n’ont pas de faces dégénérées (le cerf-volant et lechapeau).
Qualite des maillages – p.55/329
Angles dièdres
L’angle dièdre est l’angle entre l’intersection des deux facesadjacentes à l’arête avec le plan perpendiculaire à l’arête.
� ��
�
Le minimum des six angles dièdres ��� est utilisé commecritère de forme.
Qualite des maillages – p.56/329
Angles dièdres
��� � �� � � � � � �� � � � � � � � �
où � � � et � � � sont les normales aux deux faces adjacentesà l’arête � � , et où est la valeur dessix angles dièdres du tétraèdre régulier.Ce n’est pas un critère de forme valide au sens de laDéfinition A. Le plus petit angle dièdre de l’aiguille, dufuseau et de la paillette peut être aussi grand que .
Qualite des maillages – p.57/329
Le coefficient de l’erreurd’interpolation
En éléments finis, l’erreur d’interpolation d’une fonction surun élément est bornée par un coefficient fois lasemi-norme de la fonction. Ce coefficient est lerapport � � où � est le diamètre de l’élément et �
est la rondeur de l’élément .
�� � en D
�� � en D
Qualite des maillages – p.58/329
Le rappor t des arêtes
Rapport de la plus petite arête sur la plus grande
��� � �Le rapport des arêtes est un critère de forme non valideselon la Définition A, car il est non-nul pour certainssimplexes dégénérés. En 2D, il peut être aussi grandque pour le chapeau. En 3D, il peut valoir pour lecerf-volant, pour l’aileron, pour le chapeau etpour la paillette.
Qualite des maillages – p.59/329
Autres critères de forme – 1
� � �, le rapport du diamètre du tétraèdre sur lerayon de la sphère circonscrite, dans BAKER, (1989). Cecritère de forme est non valide.
��� �, le rapport de la plus petite arête du tétraèdresur le rayon de la sphère circonscrite, dans MILLER et al(1996). Ce critère de forme est non valide.
� � �
, le rapport entre le volume du tétraèdre et lerayon de la sphère circonscrite, dans MARCUM etWEATHERILL, (1995).
Qualite des maillages – p.60/329
Autres critères de forme – 2
� � ��� � ��
�
, le rapport entre le volume du tétraèdreet l’aire de ses faces, dans DECOUGNY et al (1990).L’évaluation de ce critère de forme, ainsi que sa validité,sont assez problématiques pour les tétraèdresdégénérés en quatre sommets colinéaires.
� � �� � � � ��
, le rapport entre le volume du
tétraèdre et la moyenne de ses six arêtes, dansDANNELONGUE et TANGUY (1991), ZAVATTIERI et al(1996) et WEATHERILL et al (1993).
Qualite des maillages – p.61/329
Autres critères de forme – 3
�
� �� � �� �
�
� � � � � � � �
� � � �� �� � �
�� �
� � �
le rapport entre le volume du tétraèdre et une somme, à lapuissance trois demis, de plusieurs termes homogènes àdes carrés de longueurs d’arêtes, dans BERZINS (1998).
Qualite des maillages – p.62/329
Autres critères de forme – 4
� � �� � � �� ��
, le rapport entre le volume du
tétraèdre et la moyenne quadratique de ses six arêtes,dans GRAICHEN et al (1991).Etc... Cette liste n’est pas exhaustive.
Qualite des maillages – p.63/329
Il y a une infinité de critères de forme
Si et sont deux critères de forme valides, si
�
,alors �
,�� � � � �
avec ,� �
avec ,
� �
sont aussi des critères de forme simpliciaux valides.
Qualite des maillages – p.64/329
Ce qu’il faut retenir
Un simplexe régulier est un simplexe équilatéral, ie,dont toutes les arêtes sont de même longueur.
Un critère de forme mesure le rapport à l’équilatéralité.Les critères de forme non valides ne sont pas nuls pour
tous les simplexes dégénérés.Il existe des zillions de critères de formes valides.Le but de la recherche n’est pas d’en trouver un autre
bien meilleur que les autres.
Qualite des maillages – p.65/329
Ce qu’il faut retenir
Un simplexe régulier est un simplexe équilatéral, ie,dont toutes les arêtes sont de même longueur.Un critère de forme mesure le rapport à l’équilatéralité.
Les critères de forme non valides ne sont pas nuls pourtous les simplexes dégénérés.Il existe des zillions de critères de formes valides.Le but de la recherche n’est pas d’en trouver un autre
bien meilleur que les autres.
Qualite des maillages – p.65/329
Ce qu’il faut retenir
Un simplexe régulier est un simplexe équilatéral, ie,dont toutes les arêtes sont de même longueur.Un critère de forme mesure le rapport à l’équilatéralité.Les critères de forme non valides ne sont pas nuls pour
tous les simplexes dégénérés.
Il existe des zillions de critères de formes valides.Le but de la recherche n’est pas d’en trouver un autre
bien meilleur que les autres.
Qualite des maillages – p.65/329
Ce qu’il faut retenir
Un simplexe régulier est un simplexe équilatéral, ie,dont toutes les arêtes sont de même longueur.Un critère de forme mesure le rapport à l’équilatéralité.Les critères de forme non valides ne sont pas nuls pour
tous les simplexes dégénérés.Il existe des zillions de critères de formes valides.
Le but de la recherche n’est pas d’en trouver un autrebien meilleur que les autres.
Qualite des maillages – p.65/329
Ce qu’il faut retenir
Un simplexe régulier est un simplexe équilatéral, ie,dont toutes les arêtes sont de même longueur.Un critère de forme mesure le rapport à l’équilatéralité.Les critères de forme non valides ne sont pas nuls pour
tous les simplexes dégénérés.Il existe des zillions de critères de formes valides.Le but de la recherche n’est pas d’en trouver un autre
bien meilleur que les autres.
Qualite des maillages – p.65/329
Table des matières
1. Introduction2. Définition d’un simplexe3. Dégénérescence des sim-
plexes4. Qualité de forme des sim-
plexes5. Formules pour les sim-
plexes6. Voronoï, Delaunay et Rie-
mann7. Critères de formes et de
Delaunay
8. Éléments non simpliciaux9. Représentation des cri-
tères de forme10. Équivalence des critères
de forme11. Qualité globale et optimi-
sation12. Qualité en taille des sim-
plexes13. Qualité universelle14. Conclusions
Qualite des maillages – p.66/329
Form ules pour le triangle
La donnée de la longueur des trois arêtes d’un triangle ledétermine entièrement.
Donc, les grandeurs mesurables telles les rayons descercles inscrit et circonscrit, les angles, la surface, etc,peuvent s’écrire en fonction de la longueur des trois arêtesd’un triangle.
Soit un triangle non dégénéré de sommets � , � et �.Les longueurs des arêtes � � de sontnotées � � � � , .
Qualite des maillages – p.67/329
Le demi-périmètre
Le demi-périmètre � est donné par
�
� � � � � �
Qualite des maillages – p.68/329
Form ule de Héron
L’aire � d’un triangle peut aussi s’exprimer en terme delongueurs d’arête, à l’aide de la formule de Héron :
� � � � � � � � � � � �
Qualite des maillages – p.69/329
Rayon du cercle inscrit
Le rayon � du cercle inscrit au triangle est donné par
�
��
Qualite des maillages – p.70/329
Rayon du cercle cir conscrit
Le rayon � du cercle circonscrit au triangle est donnépar
�
� � � � � ��
Qualite des maillages – p.71/329
Diamètre de l’élément
Le diamètre d’un élément est la plus grande distanceeuclidienne entre deux points de l’élément. Pour untriangle, c’est aussi la longueur de la plus grandearête � �
� � � � � � � �
La longueur de la plus petite arête est notée ���
��� � � � � � �
Qualite des maillages – p.72/329
Angle solide
L’angle � au sommet � du triangle est la longueur del’arc de cercle obtenu en projetant l’arête du triangleopposée à � sur un cercle unitaire de centre �. Ils’exprime en terme de longueurs d’arête comme
� �
�! "#%$ &' ( �) " ( �� � �*
�
Qualite des maillages – p.73/329
Form ules pour le tétraèdre
La donnée de la longueur des six arêtes d’un tétraèdre ledétermine entièrement.
Donc, les grandeurs mesurables telles les rayons dessphères inscrite et circonscrite, les angles, le volume, etc,peuvent s’écrire en fonction de la longueur des six arêtesd’un tétraèdre.
Qualite des maillages – p.74/329
Form ules pour le tétraèdre
Soit un tétraèdre non dégénéré de sommets � , �, �
et �. Les longueurs des arêtes � � de sont notées
� � � � , . Les aires des faces dutétraèdre, � � �, � � �, � � � et � � �, sontdésignées par � , �, � et �. Enfin, � est le volume dutétraèdre .
Qualite des maillages – p.75/329
Form ule de “Hér on” 3D
Soit , , , , et , les longueurs des six arêtes dutétraèdre de manière à ce que les arêtes , et soientconnectées à un même sommet, soit l’arête opposée à ,
l’arête opposée à et l’arête opposée à . Alors levolume � est
� � � � �
� � � � � � � � �
� � � � � � � � � �
� � � � �
Qualite des maillages – p.76/329
Rayon de la sphère inscrite
Le rayon � de la sphère inscrite au tétraèdre est donnépar
�
�
� � � �
Qualite des maillages – p.77/329
Rayon de la sphère cir conscrite
Le rayon � de la sphère circonscrite au tétraèdre estdonné par
�
�où � � � �, � � � � et � � � � sont les produitsdes longueurs des arêtes opposées de (deux arêtessont opposées si elles n’ont pas de sommet commun).
Qualite des maillages – p.78/329
Diamètre de l’élément
Le diamètre d’un élément est la plus grande distanceeuclidienne entre deux points de l’élément. Pour untétraèdre, c’est aussi la longueur de la plus grandearête � �
� � � � � � � � � � � � � �
La longueur de la plus petite arête est notée ���
��� � � � � � � � � � � � �
Qualite des maillages – p.79/329
Angle solide
L’angle solide � au sommet � d’un tétraèdre, est l’aire dusecteur sphérique obtenue en projetant la face opposéeà � sur la sphère unitaire centrée en �.
��
� ��
Qualite des maillages – p.80/329
Angle solide
LIU et JOE (1994) donnent la formule pour calculer l’anglesolide en fonction de la longueur des arêtes :
� ��! "#%$ &' ( �) " (+
� � �* � �� *
� � �
Qualite des maillages – p.81/329
Tabledesmatières
1. Introduction2. Définition d’un sim-
plexe3. Dégénérescence des
simplexes4. Qualité de forme des
simplexes5. Formules pour les
simplexes6. Voronoï, Delaunay et
Riemann7. Critères de formes et
de Delaunay
8. Éléments non simpli-ciaux
9. Représentation descritères de forme
10. Équivalence des cri-tères de forme
11. Qualité globale etoptimisation
12. Qualité en taille dessimplexes
13. Qualité universelle14. Conclusions
Qualite des maillages – p.82/329
Quel estle plus beautriangle ?
A B
Qualite des maillages – p.83/329
Quel estle plus beautriangle ?
A
B
Qualite des maillages – p.83/329
Quel estle plus beautriangle ?
A B
Qualite des maillages – p.83/329
Si vousavezchoisi le triangle A...
AVous avez tort !
Qualite des maillages – p.84/329
Si vousavezchoisi le triangle A...
AVous avez tort !
Qualite des maillages – p.84/329
Si vousavezchoisi le triangle B...
BVous avez encore tort !
Qualite des maillages – p.85/329
Si vousavezchoisi le triangle B...
BVous avez encore tort !
Qualite des maillages – p.85/329
Quel estle plus beautriangle ?
A BAucune de ces réponses !
Qualite des maillages – p.86/329
Quelleestla plus belle femme?
A B
Qualite des maillages – p.87/329
Quelleestla plus belle femme?
A
B
Qualite des maillages – p.87/329
Quelleestla plus belle femme?
A B
Qualite des maillages – p.87/329
Vousavezprobablementchoisi...
A BLa femme A.
Qualite des maillages – p.88/329
Vousavezprobablementchoisi...
A BLa femme A.
Qualite des maillages – p.88/329
Et si on demandait à cesmessieurs...
Qualite des maillages – p.89/329
Et si on demandait à cesmessieurs...
Qualite des maillages – p.89/329
Cesmessieurschoisiraient...
A BLa femme B.
Qualite des maillages – p.90/329
Cesmessieurschoisiraient...
A BLa femme B.
Qualite des maillages – p.90/329
Quelleestla plus belle femme...
Il n’y a pas de réponse dans l’absolue car laquestion est incomplète.
On n’a pas spécifié qui allait juger lescandidates, quel était le barême d’évaluation,quelles étaient les mesures utilisées, etc.
Qualite des maillages – p.91/329
Quel estle plus beautriangle ?
A BLa question est incomplète. Il manque une façonde mesurer la qualité d’un triangle.
Qualite des maillages – p.92/329
Quel estle plus beautriangle ?
A B
La question est incomplète. Il manque une façonde mesurer la qualité d’un triangle.
Qualite des maillages – p.92/329
Quel estle plus beautriangle ?
A BLa question est incomplète. Il manque une façonde mesurer la qualité d’un triangle.
Qualite des maillages – p.92/329
DiagrammedeVoronoï
Georgy Fedoseevich VORO-NOÏ. 28 avril 1868, Ukraine– 20 novembre 1908, Var-sovie. Nouvelles applicationsdes paramètres continus àla théorie des formes qua-dratiques. Recherches surles parallélloèdes primitifs.Journal Reine Angew. Math,Vol 134, 1908.
Qualite des maillages – p.93/329
La médiatrice
Soit et , deux som-mets dans . La mé-diatrice est lelieu des points équi-distants de et .
où est la distanceeuclidienne entre deuxpoints de l’espace.
Qualite des maillages – p.94/329
Un nuagedesommets
Soit , un nuage de sommets.
Qualite des maillages – p.95/329
Cellule de Voronoï
Définition : La cellule de Voronoï associéeau sommet est le lieu des points de l’espacequi sont plus proche de que de tout autresommet :
Qualite des maillages – p.96/329
DiagrammedeVoronoï
L’ensemble des cellules de Voronoï associées àtous les sommets du nuage de sommets formele diagramme de Voronoï.
Qualite des maillages – p.97/329
Propriétésdesdiagrammesde Voronoï
Les cellules de Voronoï sont des polygones en2D, des polyèdres en 3D, des -polytopes en
D.Les cellules de Voronoï sont convexes.Les cellules de Voronoï recouvrent l’espacesans chevauchement.
Qualite des maillages – p.98/329
Cequ’il faut retenir
Les diagrammes de Voronoï sont despar titions de l’espace en cellules basées surla notion de distance .
Qualite des maillages – p.99/329
Triangulation deDelaunay
Boris Nikolaevich DELONE ouDELAUNAY. 15 mars 1890,Saint Petersbourg — 1980.Sur la sphère vide. À la mé-moire de Georges Voronoi,Bulletin de l’Académie desSciences de l’URSS, Vol. 7,pp. 793–800, 1934.
Qualite des maillages – p.100/329
Triangulation d’un nuagedepoints
Le même nuage de points peut se trianguler debeaucoup de façons différentes.
. . .
Qualite des maillages – p.101/329
Triangulation d’un nuagedepoints
. . .
. . .
Qualite des maillages – p.102/329
Triangulation d’un nuagedepoints
. . .
. . .
Qualite des maillages – p.103/329
Triangulation deDelaunay
Parmi toutes ces façons, il y en a une (ou parfoisplusieurs) triangulation de l’enveloppe convexedu nuage de point qui est dite de Delaunay.
Qualite des maillages – p.104/329
Critèr ede la sphèrevide de Delaunay
Critère de la sphère vide : Un simplexesatisfait le critère de la sphère vide si la bouleouverte circonscrite au simplexe est vide (ie,ne contient aucun sommet de la triangulation).
Qualite des maillages – p.105/329
Critèr ede la sphèrevide violé
Un simplexe ne satisfait pas le critère de lasphère vide si la boule ouverte circonscrite ausimplexe n’est pas vide (ie, contient un ouplusieurs sommets de la triangulation).
Qualite des maillages – p.106/329
Triangulation deDelaunay
Triangulation de Delauna y : Si tous leséléments d’une triangulation satisfont lecritère de la sphère vide, alors la triangulation estdite de Delaunay.
Qualite des maillages – p.107/329
Algorithme deDelaunay
Il faut trouver lasphère circonscriteà un simplexe.Cela revient àtrouver son centre.Le centre est lepoint à égale dis-tance des som-mets du simplexe.
Qualite des maillages – p.108/329
Algorithme deDelaunay
Comment savoir si un point viol le critère de lasphère vide d’un simplexe ?
Il faut trouver le centre et le rayon de lasphère circonscrite au simplexe .Il faut trouver la distance entre le point etle centre .Si la distance est supérieure au rayon , lepoint n’est pas dans la sphère circonscriteau simplexe .
Qualite des maillages – p.109/329
Cequ’il faut retenir
Le diagramme de Voronoï d’un nuage depoints est une par tition de l’espace encellules basée sur la notion de distance .
Une triangulation de Delauna y d’un nuage depoints est une triangulation basée sur lanotion de distance .
Qualite des maillages – p.110/329
Dualité Delaunay-Voronoï
Le diagramme de Voronoï est le dual de latriangulation de Delaunay et vice versa.
Qualite des maillages – p.111/329
Voronoïet Delaunaydansla nature
Les diagrammes de Voronoï et les triangulationsde Delaunay ne sont pas juste un trip dematheux, ce sont des structures qu’on retrouvedans la nature.
Qualite des maillages – p.112/329
Voronoïet Delaunaydansla nature
Qualite des maillages – p.113/329
Une tortue
Qualite des maillages – p.114/329
Un ananas
Qualite des maillages – p.115/329
La Tour Du Diable
Qualite des maillages – p.116/329
Boueséchée
Qualite des maillages – p.117/329
Nids d’abeilles
Qualite des maillages – p.118/329
Ailes de libellule
Qualite des maillages – p.119/329
Maïs soufflé
Qualite des maillages – p.120/329
Yeuxdemouches
Qualite des maillages – p.121/329
Nanotubesde carbone
Qualite des maillages – p.122/329
Bullesdesavon
Qualite des maillages – p.123/329
Un dômegeodésique
Qualite des maillages – p.124/329
Biosphèrede Montréal
Qualite des maillages – p.125/329
RuedeParis
Qualite des maillages – p.126/329
Routesde la Sarthe
Qualite des maillages – p.127/329
Routesdansla Loir e
Qualite des maillages – p.128/329
Où s’enva le garsenavant ?
Un critère de forme d’un simplexe mesure lerapport à l’équilatéralité.
Le diagramme de Voronoï d’un nuage depoints est une partition de l’espace en cellulesbasée sur la notion de distance.Une triangulation de Delaunay d’un nuage depoints est une triangulation basée sur la notionde distance.On généralise la notion de distance.On généralise ainsi les notions de critère deforme, de diagramme de Voronoï et detriangulation de Delaunay.
Qualite des maillages – p.129/329
Où s’enva le garsenavant ?
Un critère de forme d’un simplexe mesure lerapport à l’équilatéralité.Le diagramme de Voronoï d’un nuage depoints est une partition de l’espace en cellulesbasée sur la notion de distance.
Une triangulation de Delaunay d’un nuage depoints est une triangulation basée sur la notionde distance.On généralise la notion de distance.On généralise ainsi les notions de critère deforme, de diagramme de Voronoï et detriangulation de Delaunay.
Qualite des maillages – p.129/329
Où s’enva le garsenavant ?
Un critère de forme d’un simplexe mesure lerapport à l’équilatéralité.Le diagramme de Voronoï d’un nuage depoints est une partition de l’espace en cellulesbasée sur la notion de distance.Une triangulation de Delaunay d’un nuage depoints est une triangulation basée sur la notionde distance.
On généralise la notion de distance.On généralise ainsi les notions de critère deforme, de diagramme de Voronoï et detriangulation de Delaunay.
Qualite des maillages – p.129/329
Où s’enva le garsenavant ?
Un critère de forme d’un simplexe mesure lerapport à l’équilatéralité.Le diagramme de Voronoï d’un nuage depoints est une partition de l’espace en cellulesbasée sur la notion de distance.Une triangulation de Delaunay d’un nuage depoints est une triangulation basée sur la notionde distance.On généralise la notion de distance.
On généralise ainsi les notions de critère deforme, de diagramme de Voronoï et detriangulation de Delaunay.
Qualite des maillages – p.129/329
Où s’enva le garsenavant ?
Un critère de forme d’un simplexe mesure lerapport à l’équilatéralité.Le diagramme de Voronoï d’un nuage depoints est une partition de l’espace en cellulesbasée sur la notion de distance.Une triangulation de Delaunay d’un nuage depoints est une triangulation basée sur la notionde distance.On généralise la notion de distance.On généralise ainsi les notions de critère deforme, de diagramme de Voronoï et detriangulation de Delaunay.
Qualite des maillages – p.129/329
Nikolai Ivanovich Lobachevsky
NIKOLAI IVANOVICHLOBACHEVSKY, 1décembre 1792, NizhnyNovgorod — 24 février1856, Kazan.
Qualite des maillages – p.130/329
JánosBolyai
JÁNOS BOLYAI, 15 dé-cembre 1802 à Kolozsvár,Empire Austrichien (Cluj,Roumanie) — 27 janvier1860 à Marosvásárhely,Empire Austrichien (Tirgu-Mures, Roumanie).
Qualite des maillages – p.131/329
Bernhard RIEMANN
GEORG FRIEDRICH BERN-HARD RIEMANN, 7 sep-tembre 1826, Hanovre — 20juillet 1866, Selasca. Über dieHypothesen welche der Geo-metrie zu Grunde liegen. 10juin 1854.
Qualite des maillages – p.132/329
Géométrienon euclidienne
Riemann a généralisé la géométrie euclidiennesur le plan à la géométrie riemannienne sur unesurface.
Il a définit la distance entre deux points sur unesurface comme étant la longueur du plus courtchemin entre ces deux points (géodésique).
Il a introduit le métrique riemannienne qui définitla courbure de l’espace.
Qualite des maillages – p.133/329
Définition d’une métrique
Soit un ensemble quelconque, alors la fonction
est appelée une métrique sur si elle satisfait(i) pour tous , dans ;(ii) si et seulement si ;(iii) pour tous , dans ;(iv) pour tous , ,
dans .
Qualite des maillages – p.134/329
La distanceeuclidienneestunemétrique
Dans la définition précédente de la métrique,supposons que soit , alors la fonction
est une métrique sur .
Qualite des maillages – p.135/329
Le produit scalaireestunemétrique
Soit un espace vectoriel muni d’un produitscalaire . Alors la norme du produit scalairede la différence de deux éléments de l’espacevectoriel est une métrique.
Qualite des maillages – p.136/329
Le produit scalaireestunemétrique
Si l’espace vectoriel est , alors la norme duproduit scalaire du vecteur est la distanceeuclidienne.
Qualite des maillages – p.137/329
Tenseurmétrique
Un tenseur métrique est une matricesymétrique définie positive
en 2D,
en 3D.
Qualite des maillages – p.138/329
Longueur dansla métrique
La longueur d’une arête entre lessommets et dans la métrique est donnéepar
Qualite des maillages – p.139/329
Longueur euclidienneavec
Qualite des maillages – p.140/329
Longueur métrique avec
Qualite des maillages – p.141/329
Longueur dansunemétrique variable
D’une façon générale, la métrique n’est pasconstante mais varie continûment en tout pointde l’espace. La longueur d’une courbeparamétréeest évaluée dans la métrique par
où est un point de la courbe et est levecteur tangent à la courbe en ce point.
Qualite des maillages – p.142/329
Air eet volumedansunemétrique
Aire du triangle dans la métrique :
Volume du tétraèdre dans la métrique :
Qualite des maillages – p.143/329
Métrique et maillagedeDelaunay
Qualite des maillages – p.144/329
Quel estle plus beautriangle ?
A BLa question est incomplète. Il manque une façonde mesurer la qualité d’un triangle.
Qualite des maillages – p.145/329
Quel estle plus beautriangle ?
A B
Qualite des maillages – p.146/329
Quel estle plus beautriangle ?
A B
Qualite des maillages – p.147/329
Exempled’un maillageadapté
Maillage adapté et solution pour un écoulementcompressible visqueux transonique à Mach 0.85et Reynolds = 5 000.
Qualite des maillages – p.148/329
Zoom couchelimite–choc
Qualite des maillages – p.149/329
Cequ’il faut retenir
La beauté, la qualité, la forme , est unenotion toute relative .
Il faut d’abord être capable de définir qu’est-cequ’on veut pour pouvoir juger ce qu’on aobtenu.“Qu’est-ce qu’on veut” s’écrit sous formed’une métrique.Un critère de forme est une mesure del’équilatéralité d’un simplexe dans la métrique.
Qualite des maillages – p.150/329
Cequ’il faut retenir
La beauté, la qualité, la forme , est unenotion toute relative .Il faut d’abord être capable de définir qu’est-cequ’on veut pour pouvoir juger ce qu’on aobtenu.
“Qu’est-ce qu’on veut” s’écrit sous formed’une métrique.Un critère de forme est une mesure del’équilatéralité d’un simplexe dans la métrique.
Qualite des maillages – p.150/329
Cequ’il faut retenir
La beauté, la qualité, la forme , est unenotion toute relative .Il faut d’abord être capable de définir qu’est-cequ’on veut pour pouvoir juger ce qu’on aobtenu.“Qu’est-ce qu’on veut” s’écrit sous formed’une métrique.
Un critère de forme est une mesure del’équilatéralité d’un simplexe dans la métrique.
Qualite des maillages – p.150/329
Cequ’il faut retenir
La beauté, la qualité, la forme , est unenotion toute relative .Il faut d’abord être capable de définir qu’est-cequ’on veut pour pouvoir juger ce qu’on aobtenu.“Qu’est-ce qu’on veut” s’écrit sous formed’une métrique.Un critère de forme est une mesure del’équilatéralité d’un simplexe dans la métrique.
Qualite des maillages – p.150/329
Critèr ede forme dansla métrique
Première méthode (métrique constante)
Sur le simplexe , évaluer la métrique enplusieurs points (de Gauss) et trouver unemétrique moyenne.
Supposer que cette métrique moyenne estconstante sur tout le simplexe et évaluer lecritère de forme avec cette métrique.
Qualite des maillages – p.151/329
Critèr ede forme dansla métrique
Deuxième méthode (métrique constante)
Sur le simplexe , évaluer la métrique en unpoint (de Gauss), supposer que cette métriqueest constante sur tout le simplexe et évaluer lecritère de forme en ce point avec cette métrique.
Répéter cette opération en plusieurs points etfaire la moyenne des critères de forme.
C’est ce qui est fait à l’INRIA.
Qualite des maillages – p.152/329
Critèr ede forme dansla métrique
Troisième méthode (métrique variable)
Exprimer le critère de forme en fonctionseulement de longueurs d’arêtes.
Évaluer les longueurs d’arêtes dans la métrique.
C’est ce qui est fait dans OORT.
Qualite des maillages – p.153/329
Critèr ede forme dansla métrique
Quatrième méthode (métrique variable)
Exprimer le critère de forme en fonction delongueurs d’arêtes, d’aire et de volume.
Évaluer longueurs, aire et volume dans lamétrique.
Qualite des maillages – p.154/329
Critèr ede forme dansla métrique
Cinquième méthode (métrique variable)
Savoir évaluer des quantités telles le rayon ducercle inscrit, du cercle circonscrit, un anglesolide, etc, dans une métrique variable.
D’une façon générale, la métrique variable nesatisfait pas l’inégalité triangulaire, la somme desangles n’est pas 180 degrés, etc.
L’évaluation d’un critère de forme dans unemétrique variable, dans toutes sa généralité, estun problème ouvert. Dans l’immédiat, on secontente d’approximations.
Qualite des maillages – p.155/329
Tabledesmatières
1. Introduction2. Définition d’un sim-
plexe3. Dégénérescence des
simplexes4. Qualité de forme des
simplexes5. Formules pour les
simplexes6. Voronoï, Delaunay et
Riemann7. Critères de formes et
de Delaunay
8. Éléments non simpli-ciaux
9. Représentation descritères de forme
10. Équivalence des cri-tères de forme
11. Qualité globale etoptimisation
12. Qualité en taille dessimplexes
13. Qualité universelle14. Conclusions
Qualite des maillages – p.156/329
Critèr esde formeset de Delaunay
Les maillages de Delaunay ont plusieurspropriétés de régularité.
Le maximum des rayons des sphères minimalesassociées aux éléments de la triangulation est minimumsi la triangulation est de Delaunay.Si tous les simplexes d’une triangulation contiennent le
centre de leur sphère circonscrite, alors cettetriangulation est de Delaunay.Dans une triangulation de Delaunay, la somme des
carrés des longueurs d’arêtes pondérées par le volumedes éléments partageant ces arêtes est minimal.
Qualite des maillages – p.157/329
Delaunay3D et dégénérescence
En trois dimensions, il est bien connu que lesmaillages de Delaunay peuvent contenir deéléments dégénérés du type cerf-volant.
Pourquoi ?
Comment y remédier ?
Qualite des maillages – p.158/329
Critèr ede la sphèrevide de Delaunay
Le critères de la sphère vide de Delaunay n’estpas un critère de forme, mais il peut être utilisécomme un critère de forme dans un algorithmede retournement d’arêtes.
Qualite des maillages – p.159/329
Retournementd’arêteset critèr e
Dans le retournement d’arêtes, appliquer lecritère de la sphère vide (critère de Delaunay)
Appliquer le critère (maximiser le minimumdes angles).
Qualite des maillages – p.160/329
Cequ’il faut comprendre
Le critère de la sphère vide de Delaunay n’estpas un critère de forme mais il peut être utilisécomme un critère de forme.
En deux dimensions, dans l’algorithme deretournement d’arêtes (méthode de Lawson),le critère de la sphère vide de Delaunay estéquivalent au critère de forme .Il y une multitude de critères de forme valides,et donc une multitude de généralisations dumaillage de Delaunay.
Qualite des maillages – p.161/329
Cequ’il faut comprendre
Le critère de la sphère vide de Delaunay n’estpas un critère de forme mais il peut être utilisécomme un critère de forme.En deux dimensions, dans l’algorithme deretournement d’arêtes (méthode de Lawson),le critère de la sphère vide de Delaunay estéquivalent au critère de forme .
Il y une multitude de critères de forme valides,et donc une multitude de généralisations dumaillage de Delaunay.
Qualite des maillages – p.161/329
Cequ’il faut comprendre
Le critère de la sphère vide de Delaunay n’estpas un critère de forme mais il peut être utilisécomme un critère de forme.En deux dimensions, dans l’algorithme deretournement d’arêtes (méthode de Lawson),le critère de la sphère vide de Delaunay estéquivalent au critère de forme .Il y une multitude de critères de forme valides,et donc une multitude de généralisations dumaillage de Delaunay.
Qualite des maillages – p.161/329
Delaunayet sphèrecirconscrite
Plus la sphère circonscrite d’un tétraèdre estgrande , plus il a de chance qu’un autre sommetdu maillage soit dans cette sphère, et moins il y ade chance que ce tétraèdre et le maillagesatisfasse le critère de Delaunay.
Plus la sphère circonscrite d’un tétraèdre estpetite , moins il a de chance qu’un autre sommetdu maillage soit dans cette sphère, et plus il y ade chance que ce tétraèdre et le maillagesatisfasse le critère de Delaunay.
Qualite des maillages – p.162/329
Sphèrecirconscritede rayon infini
Les tétraèdres qui dégénèrent en aileron, enchapeau, en paillette, en fuseau et en ciseau
ont une sphère circonscrite de rayon infini .
Qualite des maillages – p.163/329
Sphèrecirconscritede rayon borné
Les tétraèdres qui dégénèrent en cerf-volant, encoin, en berlingot, en aiguille et en Big Crunch
ont une sphère circonscrite de rayon borné .
Qualite des maillages – p.164/329
Cequ’il faut comprendre
Le critère de la sphère vide deDelauna y n’est pas un critère deforme valide sensib le à tous les casde dégénérescence des tétraèdres.
Qualite des maillages – p.165/329
Sphèrecirconscritede rayon borné
Parmi les tétraèdres dégénérés qui ont unesphère circonscrite de rayon borné , on peutéliminer le coin, le berlingot, l’aiguille et leBig Crunch
car ils ont plusieurs sommets conf ondus .
Qualite des maillages – p.166/329
Le cerf-volant
Or, il reste le cerf-volant,
un tétraèdre dégénéré, dont les quatre sommetssont disjoints, dont la sphère circonscrite est derayon bornée, et qui est donc“Delaunay-admissible”.
Qualite des maillages – p.167/329
Quadrilatèr enon convexe
Il est interdit de retourner une arête d’unquadrilatère non convexe.
Qualite des maillages – p.168/329
Quadrilatèr enon convexe
Deux triangles adja-cents qui forment unquadrilatère concavesatisfont nécessaire-ment le critère de lasphère vide de Delau-nay.
Qualite des maillages – p.169/329
Perte de la propriété de convexitéen 3D
Qualite des maillages – p.170/329
Cequ’il faut retenir
Le critère de la sphère vide de Delaunay estplus ou moins un critère de forme simplicial.
Le critère de la sphère vide de Delaunay n’estpas sensible à tous les cas dedégénérescence des tétraèdres en 3D.Un critère de forme valide, et donc sensible àtous les cas de dégénérescence destétraèdres, dans un algorithme deretournement d’arêtes et de faces, devraitmener à un maillage qui n’est pas deDelaunay, mais qui est de meilleure qualité.
Qualite des maillages – p.171/329
Cequ’il faut retenir
Le critère de la sphère vide de Delaunay estplus ou moins un critère de forme simplicial.Le critère de la sphère vide de Delaunay n’estpas sensible à tous les cas dedégénérescence des tétraèdres en 3D.
Un critère de forme valide, et donc sensible àtous les cas de dégénérescence destétraèdres, dans un algorithme deretournement d’arêtes et de faces, devraitmener à un maillage qui n’est pas deDelaunay, mais qui est de meilleure qualité.
Qualite des maillages – p.171/329
Cequ’il faut retenir
Le critère de la sphère vide de Delaunay estplus ou moins un critère de forme simplicial.Le critère de la sphère vide de Delaunay n’estpas sensible à tous les cas dedégénérescence des tétraèdres en 3D.Un critère de forme valide, et donc sensible àtous les cas de dégénérescence destétraèdres, dans un algorithme deretournement d’arêtes et de faces, devraitmener à un maillage qui n’est pas deDelaunay, mais qui est de meilleure qualité.
Qualite des maillages – p.171/329
Tabledesmatières
1. Introduction2. Définition d’un sim-
plexe3. Dégénérescence des
simplexes4. Qualité de forme des
simplexes5. Formules pour les
simplexes6. Voronoï, Delaunay et
Riemann7. Critères de formes et
de Delaunay
8. Éléments non simpli-ciaux
9. Représentation descritères de forme
10. Équivalence des cri-tères de forme
11. Qualité globale etoptimisation
12. Qualité en taille dessimplexes
13. Qualité universelle14. Conclusions
Qualite des maillages – p.172/329
Élémentsnon simpliciaux
Cette section propose une façon de généraliserles notions de régularité, dégénérescence etcritère de forme des simplexes aux éléments nonsimpliciaux, les quadrilatères en deuxdimensions, les prismes et les hexaèdres en troisdimensions.
Qualite des maillages – p.173/329
Élémentsnon simpliciaux
On Element Shape Measures for MeshOptimization
PAUL LABBÉ, JULIEN DOMPIERRE, FRANÇOISGUIBAULT ET RICARDO CAMARERO
Presenté à la 2nd Symposium on Trends inUnstructured Mesh Generation, Fifth US NationalCongress on Computational Mechanics, 4–6août 1999 University du Colorado à Boulder.
Qualite des maillages – p.174/329
Généralisationde la régularité
Un quadrilatère équilatéral, ie ayant quatrearêtes de même longueur, n’est pasnécessairement un carré...
Définition : Un élément, simplicial ou non,est régulier s’il maximise sa mesure pour unemesure donnée de sa frontière.Le triangle équilatéral est régulier car c’estcelui qui a l’aire optimale pour un périmètredonné.Le tétraèdre équilatéral est régulier car c’estcelui qui a le volume optimal pour une surfacedonnée de ses faces.
Qualite des maillages – p.175/329
Généralisationde la régularité
Un quadrilatère équilatéral, ie ayant quatrearêtes de même longueur, n’est pasnécessairement un carré...Définition : Un élément, simplicial ou non,est régulier s’il maximise sa mesure pour unemesure donnée de sa frontière.
Le triangle équilatéral est régulier car c’estcelui qui a l’aire optimale pour un périmètredonné.Le tétraèdre équilatéral est régulier car c’estcelui qui a le volume optimal pour une surfacedonnée de ses faces.
Qualite des maillages – p.175/329
Généralisationde la régularité
Un quadrilatère équilatéral, ie ayant quatrearêtes de même longueur, n’est pasnécessairement un carré...Définition : Un élément, simplicial ou non,est régulier s’il maximise sa mesure pour unemesure donnée de sa frontière.Le triangle équilatéral est régulier car c’estcelui qui a l’aire optimale pour un périmètredonné.
Le tétraèdre équilatéral est régulier car c’estcelui qui a le volume optimal pour une surfacedonnée de ses faces.
Qualite des maillages – p.175/329
Généralisationde la régularité
Un quadrilatère équilatéral, ie ayant quatrearêtes de même longueur, n’est pasnécessairement un carré...Définition : Un élément, simplicial ou non,est régulier s’il maximise sa mesure pour unemesure donnée de sa frontière.Le triangle équilatéral est régulier car c’estcelui qui a l’aire optimale pour un périmètredonné.Le tétraèdre équilatéral est régulier car c’estcelui qui a le volume optimal pour une surfacedonnée de ses faces.
Qualite des maillages – p.175/329
Élémentsnon simpliciaux réguliers
Le quadrilatère régulier est le carré.L’hexaèdre régulier est le cube.Le prisme régulier est ... Le prisme régulier !Les deux faces triangulaires du prisme réguliersont équilatérales avec des arêtes de longueurnotée . Les trois faces quadrilatérales duprisme régulier sont des rectangles plansayant une base de longueur et une hauteurde longueur .
Qualite des maillages – p.176/329
Qualité desélémentsnon simpliciaux
Définition : Le critère de forme d’un élément nonsimplicial est donné par le minimum du critère deforme des simplexes construits à partir dechaque sommet de l’élément non simplicial et deses sommets voisins.
Qualite des maillages – p.177/329
Critèr ede forme d’un quadrilatèr e
Le critère de forme d’un quadrilatère est leminimum du critère de forme des quatre trianglesde coin construits à partir de ses quatresommets.
Qualite des maillages – p.178/329
Critèr ede forme d’un prisme
Le critère de forme d’un prisme est le minimumdu critère de forme des six tétraèdres de coinconstruits à partir de ses six sommets.
Qualite des maillages – p.179/329
Critèr ede forme d’un hexaèdre
Le critère de forme d’un hexaèdre est leminimum du critère de forme des huit tétraèdresde coin construits à partir de ses huit sommets.
Qualite des maillages – p.180/329
Forme du simplexede coin
Les simplexes de coin construits sur leséléments non simpliciaux réguliers ne sont pasdes simplexes réguliers.Pour le carré, les quatre triangles de coin sontdes triangles rectangles isocèles.Pour le cube, les huit tétraèdres de coin sontdes tétraèdres rectangles et isocèles.Pour le prisme régulier, les six tétraèdres decoin sont des tétraèdres avec une base faited’un triangle équilatéral de côté , avec unequatrième arête perpendiculaire à la base etde longueur .
Qualite des maillages – p.181/329
Forme du simplexede coin
Chaque critère de forme doit être normalisé pourobtenir un critère de forme égal à l’unité pour leséléments non simpliciaux réguliers.
Carré
Prisme ,
Cube
,
Qualite des maillages – p.182/329
Élémentsnon simpliciaux dégénérés
Définition :Un élément non simplicial estdégénéré si au moins un de ses simplexes decoin est dégénéré.
Si au moins un des simplexes de coin est plusque dégénéré, c’est-à-dire qu’il est devenuinversé (de mesure négative), alors l’élémentnon simplicial est concave et est aussi considérédégénéré.
Qualite des maillages – p.183/329
Élémentsnon simpliciaux tordus
En trois dimensions, la définition du critère deforme des éléments non simpliciaux a un défaut :elle est peu sensible à la torsion des éléments.
Qualite des maillages – p.184/329
Torsion desfacesquadrilatérales
Un critère utilisé pour mesurer la torsion d’uneface quadrilatérale est de considérerl’angle dièdre entre les triangles etd’une part, et les triangles et d’autrepart.
Si ces angles dièdres sont de , alors la facequadrilatérale est plane (non tordue). Plus cesangles s’éloignent de , plus la facequadrilatérale est tordue.
Qualite des maillages – p.185/329
Torsion desfacesquadrilatérales
Définition :Étant donné un critère de formesimplicial valide, la torsion d’une facequadrilatérale est égale à la valeur de ce critèrepour le tétraèdre engendré par les quatresommets de la face quadrilatérale.
Ainsi, une face plane a une torsion nulle car les quatresommets forment un tétraèdre dégénéré et tous lescritères de forme valides sont nuls.
Plus une face quadrilatérale est tordue, plus ses sommetss’éloignent de la coplanarité, plus le critère de forme dutétraèdre engendré est grand.
Qualite des maillages – p.186/329
Cequ’il faut retenir
La forme , la dégénérescence , la convexité, laconca vité et la tor sion peuvent se réécrire enfonction de simple xes.
Un avantage de cette approche est qu’une foisque la mesure et les critères de forme pour lessimplexes sont programmés, en euclidiencomme avec une métrique riemannienne,l’extension aux éléments non simpliciaux estdirecte.
Qualite des maillages – p.187/329
Tabledesmatières
1. Introduction2. Définition d’un sim-
plexe3. Dégénérescence des
simplexes4. Qualité de forme des
simplexes5. Formules pour les
simplexes6. Voronoï, Delaunay et
Riemann7. Critères de formes et
de Delaunay
8. Éléments non simpli-ciaux
9. Représentation descritères de forme
10. Équivalence des cri-tères de forme
11. Qualité globale etoptimisation
12. Qualité en taille dessimplexes
13. Qualité universelle14. Conclusions
Qualite des maillages – p.188/329
Représentation des critères deforme
1
0.5
y
2
1
0
-1
-2 x
32
10
Position des trois sommets , et dutriangle pour construire le graphe d’un critèrede forme triangulaire.
Qualite des maillages – p.189/329
Représentation des critères deforme
x 3210
y
1
0
-1
x 3210
y
1
0
-1
x 3210
y
1
0
-1
Le rapport des arêtes à gauche. Le minimumdes angles solides au centre. Le coefficientd’erreur d’interpolation à droite.
Qualite des maillages – p.190/329
Représentation des critères deforme
x 3210
y
1
0
-1
x 3210
y
1
0
-1
Le rapport des rayons à gauche et le rapportdes moyennes à droite.
Qualite des maillages – p.191/329
Quelcritèredeformeestle meilleur
x 3210
y
1
0
-1
n’est pas un critère deforme valide.
et sont continusmais non différentiables.
et sont continus et dif-férentiables.
est instable numérique-ment.
est le moins coûteux.a des isovaleurs circu-
laires.
Qualite des maillages – p.192/329
Représentationentroisdimensions
En 3D, 5 paramètres sont nécessaires. On enfixe 2 et on voit l’influence des 3 autres.
Qualite des maillages – p.193/329
Représentationavecunemétrique
x 3210
y
1
0
-1
Rapport des moyennes
Qualite des maillages – p.194/329
Représentationavecunemétrique
x 210
y
1
0
-1
Rapport des moyennes
Qualite des maillages – p.195/329
Représentationavecunemétrique
x 3210
y
1
0
-1
Rapport des moyennes
Qualite des maillages – p.196/329
Représentationavecunemétrique
x 3210
y
1
0
-1
Rapport des moyennes
Qualite des maillages – p.197/329
Cequ’il fautretenir
Rapport des moyennes est le critère deforme privilégié.
Des cercles en euclidien deviennent desellipses dans le cas général.La forme d’un triangle est un critère de qualitérelatif.Un beau triangle pour une métrique n’est pasbeau pour une autre.On ne peut juger la qualité d’un triangle que sion a défini une métrique.
Qualite des maillages – p.198/329
Cequ’il fautretenir
Rapport des moyennes est le critère deforme privilégié.Des cercles en euclidien deviennent desellipses dans le cas général.
La forme d’un triangle est un critère de qualitérelatif.Un beau triangle pour une métrique n’est pasbeau pour une autre.On ne peut juger la qualité d’un triangle que sion a défini une métrique.
Qualite des maillages – p.198/329
Cequ’il fautretenir
Rapport des moyennes est le critère deforme privilégié.Des cercles en euclidien deviennent desellipses dans le cas général.La forme d’un triangle est un critère de qualitérelatif.
Un beau triangle pour une métrique n’est pasbeau pour une autre.On ne peut juger la qualité d’un triangle que sion a défini une métrique.
Qualite des maillages – p.198/329
Cequ’il fautretenir
Rapport des moyennes est le critère deforme privilégié.Des cercles en euclidien deviennent desellipses dans le cas général.La forme d’un triangle est un critère de qualitérelatif.Un beau triangle pour une métrique n’est pasbeau pour une autre.
On ne peut juger la qualité d’un triangle que sion a défini une métrique.
Qualite des maillages – p.198/329
Cequ’il fautretenir
Rapport des moyennes est le critère deforme privilégié.Des cercles en euclidien deviennent desellipses dans le cas général.La forme d’un triangle est un critère de qualitérelatif.Un beau triangle pour une métrique n’est pasbeau pour une autre.On ne peut juger la qualité d’un triangle que sion a défini une métrique.
Qualite des maillages – p.198/329
Tabledesmatières
1. Introduction2. Définition d’un sim-
plexe3. Dégénérescence des
simplexes4. Qualité de forme des
simplexes5. Formules pour les
simplexes6. Voronoï, Delaunay et
Riemann7. Critères de formes et
de Delaunay
8. Éléments non simpli-ciaux
9. Représentation descritères de forme
10. Équivalence des cri-tères de forme
11. Qualité globale etoptimisation
12. Qualité en taille dessimplexes
13. Qualité universelle14. Conclusions
Qualite des maillages – p.199/329
Équivalencedescritèresdeforme
Qualite des maillages – p.200/329
Équivalencedescritèresdeforme
x 3210
y
1
0
-1
Superposition desisolignes des critèresde forme triangu-laires , , et
.
Qualite des maillages – p.201/329
ÉquivalencedescritèresdeformeDéfinition B (de LIU et JOE, 1994) : Soientet , deux critères de forme simpliciaux différentsayant des valeurs dans l’intervalle . On ditque est équiv alent à s’il existe desconstantes positives , , et telles que
- .
Qualite des maillages – p.202/329
Bornesoptimales
Dans l’équation d’équivalence des critères deforme
la borne inférieure est dite optimale si est leplus petit exposant possible,et la borne supérieure est dite optimale si estle plus grand exposant possible.
Qualite des maillages – p.203/329
Bornesoptimales
Dans l’équation d’équivalence des critères deforme
la borne inférieure est dite optimale si est leplus petit exposant possible,
et la borne supérieure est dite optimale si estle plus grand exposant possible.
Qualite des maillages – p.203/329
Bornesoptimales
Dans l’équation d’équivalence des critères deforme
la borne inférieure est dite optimale si est leplus petit exposant possible,
et la borne supérieure est dite optimale si estle plus grand exposant possible.
Qualite des maillages – p.203/329
BornesserréesDans l’équation d’équivalence des critères deforme
- .
la borne inférieure est dite serrée si est la plusgrande constante possible,et la borne supérieure est dite serrée si est laplus petite constante possible.
Qualite des maillages – p.204/329
BornesserréesDans l’équation d’équivalence des critères deforme
- .la borne inférieure est dite serrée si est la plusgrande constante possible,
et la borne supérieure est dite serrée si est laplus petite constante possible.
Qualite des maillages – p.204/329
BornesserréesDans l’équation d’équivalence des critères deforme
- .la borne inférieure est dite serrée si est la plusgrande constante possible,et la borne supérieure est dite serrée si est laplus petite constante possible.
Qualite des maillages – p.204/329
Relationd’équivalence
Il s’agit effectivement d’une relationd’équivalence, c’est-à-dire une relation
réflexive,symétrique,transitive.
Qualite des maillages – p.205/329
Relationsymétrique
Si est équivalent à avec
- .
alors est équivalent à avec
/ ,
où
.
, ,
-
et .
Qualite des maillages – p.206/329
RelationtransitiveSi est équivalent à et si est équivalent àavec
- . / ,
alors est équivalent à avec
0 1
où
-
, ,
.
et .
Qualite des maillages – p.207/329
Équivalenceentre , etL’équivalence entre les critères de formetétraédriques , et a été prouvée dans LIUet JOE, 1994, avec une conjecture sur troisbornes supérieures serrées
Qualite des maillages – p.208/329
Équivalenceentre , , etOn peut encore démontrer que les critères deforme , , et font partie de la même classed’équivalence, du moins en deux dimensionspour .
en D
en D
en Den D
en D
Qualite des maillages – p.209/329
Classesd’équivalencedes critèresdeforme
La relation d’équivalence Définition B définitdes classes d’équivalence.
Tous les critères de forme satisfaisant laDéfinition A et couramment utilisés sontéquivalents entre eux suivant la Définition B.La classe d’équivalence de la relation
d’équivalence Définition B est-elle formée detous les critères de forme simpliciaux quisatisfont la Définition A ? ? ?Non ! LIU m’a donné un contre-exemple.
Qualite des maillages – p.210/329
Classesd’équivalencedes critèresdeforme
La relation d’équivalence Définition B définitdes classes d’équivalence.Tous les critères de forme satisfaisant laDéfinition A et couramment utilisés sontéquivalents entre eux suivant la Définition B.
La classe d’équivalence de la relationd’équivalence Définition B est-elle formée detous les critères de forme simpliciaux quisatisfont la Définition A ? ? ?Non ! LIU m’a donné un contre-exemple.
Qualite des maillages – p.210/329
Classesd’équivalencedes critèresdeforme
La relation d’équivalence Définition B définitdes classes d’équivalence.Tous les critères de forme satisfaisant laDéfinition A et couramment utilisés sontéquivalents entre eux suivant la Définition B.La classe d’équivalence de la relation
d’équivalence Définition B est-elle formée detous les critères de forme simpliciaux quisatisfont la Définition A ? ? ?
Non ! LIU m’a donné un contre-exemple.
Qualite des maillages – p.210/329
Classesd’équivalencedes critèresdeforme
La relation d’équivalence Définition B définitdes classes d’équivalence.Tous les critères de forme satisfaisant laDéfinition A et couramment utilisés sontéquivalents entre eux suivant la Définition B.La classe d’équivalence de la relation
d’équivalence Définition B est-elle formée detous les critères de forme simpliciaux quisatisfont la Définition A ? ? ?Non ! LIU m’a donné un contre-exemple.
Qualite des maillages – p.210/329
Contre-exemple
Soit , un critère de forme qui satisfaitDéfinition A, alors
est aussi un critère de forme. Cependant, on nepeut pas prouver que et sont équivalents ausens de la Définition B car il n’y a pas deconstantes et telles que 2 quandtend vers zéro car le comportementasymptotique exponentiel de tend vers zéroplus vite que n’importe quel comportementasymptotique polynômial.
Qualite des maillages – p.211/329
Cequ’il fautretenir
Tous les critères de forme satisfaisant laDéfinition A et couramment utilisés sontéquivalents entre eux suivant la Définition B.
Ils sont tous sensibles à tous les cas dedégénérescence des simplexes.De ce point de vue, il n’y en a pas un meilleurque les autres.
Qualite des maillages – p.212/329
Cequ’il fautretenir
Tous les critères de forme satisfaisant laDéfinition A et couramment utilisés sontéquivalents entre eux suivant la Définition B.Ils sont tous sensibles à tous les cas dedégénérescence des simplexes.
De ce point de vue, il n’y en a pas un meilleurque les autres.
Qualite des maillages – p.212/329
Cequ’il fautretenir
Tous les critères de forme satisfaisant laDéfinition A et couramment utilisés sontéquivalents entre eux suivant la Définition B.Ils sont tous sensibles à tous les cas dedégénérescence des simplexes.De ce point de vue, il n’y en a pas un meilleurque les autres.
Qualite des maillages – p.212/329
Table des matières
1. Introduction2. Définition d’un simplexe3. Dégénérescence des sim-
plexes4. Qualité de forme des sim-
plexes5. Formules pour les sim-
plexes6. Voronoï, Delaunay et Rie-
mann7. Critères de formes et de
Delaunay
8. Éléments non simpliciaux9. Représentation des cri-
tères de forme10. Équivalence des critères
de forme11. Qualité globale et optimi-
sation12. Qualité en taille des sim-
plexes13. Qualité universelle14. Conclusions
Qualite des maillages – p.213/329
Qualité globale et optimisation
On évalue la qualité globale de tout un maillage par le biaisde la qualité de chacun des éléments qui le composent.
En pratique, la comparaison entre des maillages issus dedifférentes publications est souvent impossible : lesstatistiques présentées, les critères de forme et leséchelles utilisées varient d’une publication à l’autre. Il fautdéfinir des bancs d’essai avec des sorties standards.
Qualite des maillages – p.214/329
Banc d’essai
Cube unitaire avec unecarte de taille uniformeet isotrope de .
Qualite des maillages – p.215/329
Histogramme
0
5
10
15
20
25
30
0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
Critère de forme des tétraèdres
Pou
rcen
tage
des
tétr
aèdr
es
3
Rapport des moyennesRapport des rayons
Histogramme du rap-port des moyennes etdu rapport des rayons.
Qualite des maillages – p.216/329
Histogramme
0
5
10
15
20
25
30
0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
Critère de forme des tétraèdres
Angle solide minimumAngle dièdre minimum
Histogramme du mini-mum des angles so-lides ��� et du mi-nimum des angles di-èdres ��� .
Qualite des maillages – p.217/329
Histogramme
0
5
10
15
20
25
30
0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
Critère de forme des tétraèdres
Coefficient d’erreurRapport des arêtes
Histogramme du rap-port des arêtes etdu coefficient de l’er-reur d’interpolation .
Qualite des maillages – p.218/329
Statistiques sur tous les tétraèdres
min maxRap. rayons 0.5151 0.9067 0.9978 0.0602Rap. moyennes 0.6559 0.9222 0.9979 0.0468Rap. arêtes 0.5696 0.7375 0.9504 0.0641Erreur d’inter. 0.4862 0.8058 0.9741 0.0709
solide ��� 0.2962 0.7115 0.9697 0.0996dièdre ��� 0.4207 0.7657 0.9768 0.0852
Qualite des maillages – p.219/329
Moyenne des critères de forme
Pour un maillage donné, la moyenne dépend beaucoup ducritère de forme utilisé. LIU et JOE (1994) ont constaté que
���
On a constaté numériquement sur plusieurs maillages que
��� ���
Qualite des maillages – p.220/329
Moyenne des critères de forme
La moyenne, sur tous les tétraèdres du maillage, d’uncritère de forme semble être un indice assez significatif dela qualité globale du maillage.
En effet, si on prend plusieurs maillages de différentequalité et si on les classe en fonction de la moyenne d’uncritère de forme, on obtient le même classement, àquelques permutations près, quelque soit le critère deforme utilisé.
Qualite des maillages – p.221/329
Maxim um des critères de forme
C’est une donnée non significative car quelque soit lemaillage ou le critère de forme utilisé, le maximum estpresque toujours 1.
C’est significatif seulement si c’est loin de l’unité ce quidémarque un très mauvais maillage.
Qualite des maillages – p.222/329
Minim um des critères de forme
C’est une donnée peu significative. C’est significatifseulement si c’est près de zéro ce qui démarque un trèsmauvais maillage.
Sur une série de tests, le classement de maillages enfonction du minimum du critère de forme donne unclassement chaotique. Il n’est pas bon de caractériser toutun maillage par la valeur d’un seul de ses éléments.
Qualite des maillages – p.223/329
Écar t type des critères de forme
C’est une donnée assez significative. Plus l’écart type estpetit, plus le maillage est de qualité.
Sur une série de test, le classement de maillages enfonction de l’écart type donne un classement significatifmais un peu chaotique.
Qualite des maillages – p.224/329
Ce qu’il faut retenir
Des statistiques sur la forme des éléments d’unmaillage sont des données significatives sur la qualitédu maillage.
N’importe quel critère de forme valide semble fairel’affaire.Il n’y a pas un seul chiffre unique qui semble pouvoir
caractériser entièrement la qualité d’un maillage.La moyenne semble être le chiffre le plus significatif.La quantification de la qualité d’un maillage par le biais
de statistiques sur la qualité en forme des éléments dumaillage n’est pas une solution pleinement satisfaisante.
Qualite des maillages – p.225/329
Ce qu’il faut retenir
Des statistiques sur la forme des éléments d’unmaillage sont des données significatives sur la qualitédu maillage.N’importe quel critère de forme valide semble faire
l’affaire.
Il n’y a pas un seul chiffre unique qui semble pouvoircaractériser entièrement la qualité d’un maillage.La moyenne semble être le chiffre le plus significatif.La quantification de la qualité d’un maillage par le biais
de statistiques sur la qualité en forme des éléments dumaillage n’est pas une solution pleinement satisfaisante.
Qualite des maillages – p.225/329
Ce qu’il faut retenir
Des statistiques sur la forme des éléments d’unmaillage sont des données significatives sur la qualitédu maillage.N’importe quel critère de forme valide semble faire
l’affaire.Il n’y a pas un seul chiffre unique qui semble pouvoir
caractériser entièrement la qualité d’un maillage.
La moyenne semble être le chiffre le plus significatif.La quantification de la qualité d’un maillage par le biais
de statistiques sur la qualité en forme des éléments dumaillage n’est pas une solution pleinement satisfaisante.
Qualite des maillages – p.225/329
Ce qu’il faut retenir
Des statistiques sur la forme des éléments d’unmaillage sont des données significatives sur la qualitédu maillage.N’importe quel critère de forme valide semble faire
l’affaire.Il n’y a pas un seul chiffre unique qui semble pouvoir
caractériser entièrement la qualité d’un maillage.La moyenne semble être le chiffre le plus significatif.
La quantification de la qualité d’un maillage par le biaisde statistiques sur la qualité en forme des éléments dumaillage n’est pas une solution pleinement satisfaisante.
Qualite des maillages – p.225/329
Optimisation de mailla ges
Un maillage peut être décrit par l’ensemble
� �� � � � � � �
où est le nombre de sommets du maillage,
� � � � � � � sont les coordonnées dans
�
duème sommet, est le nombre de simplexes du maillage,
et � � � � � � � � � ��� � est la connectivité du èmesimplexe du maillage composé de pointeurs vers dessommets du maillage
Qualite des maillages – p.226/329
Optimisation et critères de forme
Quelle est l’influence de choix d’un critère de forme dansl’optimisation d’un maillage ?
Le banc d’essai est un domaineen forme de triangle équilatéralavec une métrique uniforme et iso-trope qui spécifie une taille d’arêtede de la longueur du côté dudomaine. Le maillage optimal existedans ce cas particulier.
Qualite des maillages – p.227/329
Influence du critère de forme
���
Qualite des maillages – p.228/329
Optimisation et critères de forme
Quelle est l’influence de choix d’un critère de forme dansl’optimisation d’un maillage ?
Le banc d’essai est un domaine enforme de carré équilatéral avec unemétrique uniforme et isotrope quispécifie une taille d’arête de dela longueur du côté du domaine. Lemaillage optimal n’existe pas dansce cas.
Qualite des maillages – p.229/329
Influence du critère de forme
���
Qualite des maillages – p.230/329
Influence de l’algorithme
On enlève le déplacement de sommets dans l’algorithmed’optimisation de maillages.
Le banc d’essai est un domaineen forme de triangle équilatéralavec une métrique uniforme et iso-trope qui spécifie une taille d’arêtede de la longueur du côté dudomaine. Le maillage optimal existedans ce cas.
Qualite des maillages – p.231/329
Influence de l’algorithme
���
Qualite des maillages – p.232/329
Ce qu’il faut retenir
Si le maillage optimal existe, l’optimiseur converge versle maillage optimal quel que soit le critère de forme.
Si le maillage optimal n’existe pas, des critères deforme différents donnent des maillages différents. Maisplus le maillage est optimisé, moins la différence dequalité est grande statistiquement.Si le maillage est mauvais, ce n’est pas en changeant
le critère de forme qu’on l’améliore, mais en changeantl’algorithme d’optimisation.
Qualite des maillages – p.233/329
Ce qu’il faut retenir
Si le maillage optimal existe, l’optimiseur converge versle maillage optimal quel que soit le critère de forme.Si le maillage optimal n’existe pas, des critères de
forme différents donnent des maillages différents. Maisplus le maillage est optimisé, moins la différence dequalité est grande statistiquement.
Si le maillage est mauvais, ce n’est pas en changeantle critère de forme qu’on l’améliore, mais en changeantl’algorithme d’optimisation.
Qualite des maillages – p.233/329
Ce qu’il faut retenir
Si le maillage optimal existe, l’optimiseur converge versle maillage optimal quel que soit le critère de forme.Si le maillage optimal n’existe pas, des critères de
forme différents donnent des maillages différents. Maisplus le maillage est optimisé, moins la différence dequalité est grande statistiquement.Si le maillage est mauvais, ce n’est pas en changeant
le critère de forme qu’on l’améliore, mais en changeantl’algorithme d’optimisation.
Qualite des maillages – p.233/329
Table des matières
1. Introduction2. Définition d’un simplexe3. Dégénérescence des sim-
plexes4. Qualité de forme des sim-
plexes5. Formules pour les sim-
plexes6. Voronoï, Delaunay et Rie-
mann7. Critères de formes et de
Delaunay
8. Éléments non simpliciaux9. Représentation des cri-
tères de forme10. Équivalence des critères
de forme11. Qualité globale et optimi-
sation12. Qualité en taille des sim-
plexes13. Qualité universelle14. Conclusions
Qualite des maillages – p.234/329
Qualité en taille des simle xes
Les critères de forme servent à mesurer la forme deséléments du maillage.
Les critères de forme sont adimensionnels.La forme n’est qu’un aspect de la qualité d’un maillage.
On recherche un maillage qui respecte aussi, du mieuxpossible, la taille spécifiée des éléments.Cette section va présenter trois critères de taille.
Qualite des maillages – p.235/329
Qualité en taille des simle xes
Les critères de forme servent à mesurer la forme deséléments du maillage.Les critères de forme sont adimensionnels.
La forme n’est qu’un aspect de la qualité d’un maillage.
On recherche un maillage qui respecte aussi, du mieuxpossible, la taille spécifiée des éléments.Cette section va présenter trois critères de taille.
Qualite des maillages – p.235/329
Qualité en taille des simle xes
Les critères de forme servent à mesurer la forme deséléments du maillage.Les critères de forme sont adimensionnels.La forme n’est qu’un aspect de la qualité d’un maillage.
On recherche un maillage qui respecte aussi, du mieuxpossible, la taille spécifiée des éléments.Cette section va présenter trois critères de taille.
Qualite des maillages – p.235/329
Qualité en taille des simle xes
Les critères de forme servent à mesurer la forme deséléments du maillage.Les critères de forme sont adimensionnels.La forme n’est qu’un aspect de la qualité d’un maillage.On recherche un maillage qui respecte aussi, du mieux
possible, la taille spécifiée des éléments.
Cette section va présenter trois critères de taille.
Qualite des maillages – p.235/329
Qualité en taille des simle xes
Les critères de forme servent à mesurer la forme deséléments du maillage.Les critères de forme sont adimensionnels.La forme n’est qu’un aspect de la qualité d’un maillage.On recherche un maillage qui respecte aussi, du mieux
possible, la taille spécifiée des éléments.Cette section va présenter trois critères de taille.
Qualite des maillages – p.235/329
Taille cib le des simple xes
Dans CUILLIÈRE (1998), on compare la taille dessimplexes avec la taille cible.La taille cible locale d’un simplexe est celle qu’aurait un
simplexe régulier de côté unitaire.Pour un triangle, l’aire cible est de .Pour un tétraèdre, le volume cible est de .
�
�
en 2D,en 3D.
Qualite des maillages – p.236/329
Critère de taille
Le critère de taille � du simplexe s’écrit comme suit :
�
� �
où est une constante de mise à l’échelle globale pourtout le maillage.Si un simplexe est de bonne taille dans la métrique,alors son critère de taille � sera unitaire.
Qualite des maillages – p.237/329
Indice d’efficacité
Un autre critère pour évaluer la conformité d’un maillage àune métrique est proposé par FREY et GEORGE (1999).
Ce critère, contrairement au précédent qui évaluait lesaires ou les volumes des éléments, est basé sur leslongueurs d’arêtes dans la métrique.
Qualite des maillages – p.238/329
Indice d’efficacité
On note � � les longueurs dans la métriquedes � arêtes d’un maillage.La longueur optimale des arêtes dans la métrique est ,et une longueur de signifie que l’arête est deux fois plusgrande que la longueur spécifiée.Une mesure globale de la conformité du maillage à la taillespécifiée est l’indice d’efficacité
�� 4
�� �
� � �
Qualite des maillages – p.239/329
Indice d’efficacité
Considérons la distribution, sur toutes les arêtes dumaillage, de la variable � � � .Notons � � 4�� � � sa valeur moyenneNotons
�
� � 4�� � � �
son écart-type.Alors � �
L’indice d’efficacité mesure à la fois la dispersion deslongueurs d’arêtes et leur proximité à la valeur cible.
Qualite des maillages – p.240/329
Indice d’efficacité
� �Cette égalité montre que maximiser implique à la foisminimiser l’écart-type de la distribution, et rapprocher samoyenne de la valeur . La valeur optimale est obtenuelorsque et . Cela n’est possible que si toutes lesarêtes sont de longueur exactement égale à la longueurlocale spécifiée.Ainsi, l’indice d’efficacité est une bonne mesure globale dela conformité des longueurs d’arêtes avec les longueursspécifiées.
Qualite des maillages – p.241/329
Table des matières
1. Introduction2. Définition d’un simplexe3. Dégénérescence des sim-
plexes4. Qualité de forme des sim-
plexes5. Formules pour les sim-
plexes6. Voronoï, Delaunay et Rie-
mann7. Critères de formes et de
Delaunay
8. Éléments non simpliciaux9. Représentation des cri-
tères de forme10. Équivalence des critères
de forme11. Qualité globale et optimi-
sation12. Qualité en taille des sim-
plexes13. Qualité universelle14. Conclusions
Qualite des maillages – p.242/329
Un critère univer sel de qualité demailla ge
Attac he ta tuque avec de la broche...
Qualite des maillages – p.243/329
Un critère univer sel de qualité demailla ge
Table des matières1. Introduction2. La métrique � du simplexe3. La métrique spécifiée4. La non conformité � d’un simplexe5. La non conformité d’un maillage6. Généralisation des critères de taille7. Extension aux éléments non simpliciaux8. Interrogation orale9. Ce qu’il faut retenir
Qualite des maillages – p.244/329
Intr oduction
Les simplexes peuvent être de la bonne forme sanspour autant être de la bonne taille.
Il existe des critères de qualité en taille des simplexeset des maillages.En principe, un simplexe dont toutes les arêtes sont de
longueur unité dans la métrique, est aussi de formeparfaite dans la métrique.En pratique, les maillages construits ne sont pas
parfaitement de la bonne taille et les simplexes sontcomposés d’arêtes plus ou moins trop courtes ou troplongues.
Qualite des maillages – p.245/329
Intr oduction
Les simplexes peuvent être de la bonne forme sanspour autant être de la bonne taille.Il existe des critères de qualité en taille des simplexes
et des maillages.
En principe, un simplexe dont toutes les arêtes sont delongueur unité dans la métrique, est aussi de formeparfaite dans la métrique.En pratique, les maillages construits ne sont pas
parfaitement de la bonne taille et les simplexes sontcomposés d’arêtes plus ou moins trop courtes ou troplongues.
Qualite des maillages – p.245/329
Intr oduction
Les simplexes peuvent être de la bonne forme sanspour autant être de la bonne taille.Il existe des critères de qualité en taille des simplexes
et des maillages.En principe, un simplexe dont toutes les arêtes sont de
longueur unité dans la métrique, est aussi de formeparfaite dans la métrique.
En pratique, les maillages construits ne sont pasparfaitement de la bonne taille et les simplexes sontcomposés d’arêtes plus ou moins trop courtes ou troplongues.
Qualite des maillages – p.245/329
Intr oduction
Les simplexes peuvent être de la bonne forme sanspour autant être de la bonne taille.Il existe des critères de qualité en taille des simplexes
et des maillages.En principe, un simplexe dont toutes les arêtes sont de
longueur unité dans la métrique, est aussi de formeparfaite dans la métrique.En pratique, les maillages construits ne sont pas
parfaitement de la bonne taille et les simplexes sontcomposés d’arêtes plus ou moins trop courtes ou troplongues.
Qualite des maillages – p.245/329
Critères de forme et de taille
Or, le rapport de la plus petite arête sur la plus grandepeut être aussi grand que pour qu’untétraèdre dégénère en cerf-volant.
Cela signifie qu’un simplexe ayant des arêtes de tailleconvenable n’implique pas que ce simplexe est aussiforme convenable car il peut être totalement dégénéré.
Qualite des maillages – p.246/329
Critères de forme et de taille
Or, le rapport de la plus petite arête sur la plus grandepeut être aussi grand que pour qu’untétraèdre dégénère en cerf-volant.Cela signifie qu’un simplexe ayant des arêtes de taille
convenable n’implique pas que ce simplexe est aussiforme convenable car il peut être totalement dégénéré.
Qualite des maillages – p.246/329
Critères de forme et de taille
On peut faire une combinaison linéaire d’un critère deforme et d’un critère de taille, mais c’est assez arbitraire.
Le but de cet exposé est d’introduire un critère universelqui mesure la taille et la forme en même temps.
Qualite des maillages – p.247/329
Critères de forme et de taille
On peut faire une combinaison linéaire d’un critère deforme et d’un critère de taille, mais c’est assez arbitraire.Le but de cet exposé est d’introduire un critère universel
qui mesure la taille et la forme en même temps.
Qualite des maillages – p.247/329
Un critère univer sel de qualité demailla ge
Table des matières1. Introduction2. La métrique � du simplexe3. La métrique spécifiée4. La non conformité � d’un simplexe5. La non conformité d’un maillage6. Généralisation des critères de taille7. Extension aux éléments non simpliciaux8. Interrogation orale9. Ce qu’il faut retenir
Qualite des maillages – p.248/329
The Metric of a Simple x
How to compute the metric � of the transformation thattransforms a simplex into a unit equilateral element ?
Let � , �, �[, �], the vertices of the simplexin
�
.
Let � � , , the edges of the simplex.
Qualite des maillages – p.249/329
The Metric of a Simple x
In
�
, or , the components of the metricare found by solving the following system of Eqs :
� � � � � � for
which yields one equation per edge of the simplex.
All the edges of measure 1 in �.
Qualite des maillages – p.250/329
The Metric of a Simple x
For example in two dimensions, if the vertices of triangleare located at �
, � � �and � � �
, then this system of Eqs gives :
� � � � � � � � � � � �
� � � � � � � � � � � �
� � � � � � � � � � � � � � � �
which has a unique solution for all non-degeneratetriangles.
Qualite des maillages – p.251/329
The Metric of a Simple x
For instance, recall the triangle where vertices and arelocated at
�
,
�
and where thevertex
�
free to move in the half-plane .The system of Eqs. reduces to the system
� ��
��
�
� ��
��
�
� �� �
� �
Qualite des maillages – p.252/329
The Metric of a Simple x
which yields :
�
��
This metric � becomes identity when the vertex�
, which corresponds to the unitequilateral triangle.
Qualite des maillages – p.253/329
Visualization of the Metric
It is usual to visualize the metric tensor as an ellipse.Indeed, the metric tensor can be written as
� �
, where the matrix is the diagonalmatrix of the eigenvalues of �, i.e., � � � .The eigenvalues � are the length of the axes of the ellipseand is the rotation matrix of the ellipse about the origin.
Qualite des maillages – p.254/329
Visualization of the Metric
However, it is more telling to draw ellipses of size ,this ellipse will go through the vertices of the triangle.
Qualite des maillages – p.255/329
Visualization of the Metric
Ellipses of a selectedgroup of elements. Note inthis figure that the ellipsespass through the verticesof the triangle.
Qualite des maillages – p.256/329
Visualization of the Metric
Ellipses of a selectedgroup of elements. Note inthis figure that the ellipsespass through the verticesof the triangle.
Qualite des maillages – p.257/329
Visualization of the Metric
Ellipses of a selectedgroup of elements. Note inthis figure that the ellipsespass through the verticesof the triangle.
Qualite des maillages – p.258/329
Un critère univer sel de qualité demailla ge
Table des matières1. Introduction2. La métrique � du simplexe3. La métrique spécifiée4. La non conformité � d’un simplexe5. La non conformité d’un maillage6. Généralisation des critères de taille7. Extension aux éléments non simpliciaux8. Interrogation orale9. Ce qu’il faut retenir
Qualite des maillages – p.259/329
The Specified Metric
A size specification map can be constructed from aposteriori error estimators, from geometrical properties ofthe domain (e.g. curvature), from user defined inputs, etc.
Isotropic size specification map ( size of the elements)can be constructed by making the metrics diagonalmatrices whose diagonal terms are
�
.
Qualite des maillages – p.260/329
The Specified Metric
Whatever its origin, the size specification map contains theinformation of the prescribed size and stretching of themesh to be built as an anisotropic metric field.
An anisotr opic metric field 5 is given as input .
Qualite des maillages – p.261/329
The Average Specified Metric
Let 5 be the specified Riemannian metric value atpoint . Let 5 be the averaged specifiedRiemannian metric over a simplex as computed by :
5
�
5
�
This integral can be approximated by a numericalquadrature.
Qualite des maillages – p.262/329
Visualization of
The specified metric is de-fined in GEORGE and BO-ROUCHAKI (1997). It is ananalytical function that de-fines an isotropic metric.Note that the triangles donot fit exactly the specifiedmetric.
Qualite des maillages – p.263/329
Visualization of
The specified metric is de-fined in GEORGE and BO-ROUCHAKI (1997). It is ananalytical function that de-fines an anisotropic metric.Note that the triangles donot fit exactly the specifiedmetric.
Qualite des maillages – p.264/329
Visualization of
Supersonic laminar vs-cous air flow aroundNACA 0012. The specifiedanisotropic metric is basedon the interpolation error(second derivatives) of thespeed field.Note that the triangles donot fit exactly the specifiedmetric.
Qualite des maillages – p.265/329
Un critère univer sel de qualité demailla ge
Table des matières1. Introduction2. La métrique � du simplexe3. La métrique spécifiée4. La non conformité � d’un simplexe5. La non conformité d’un maillage6. Généralisation des critères de taille7. Extension aux éléments non simpliciaux8. Interrogation orale9. Ce qu’il faut retenir
Qualite des maillages – p.266/329
Simple x Conf ormity
When the metric � of the simplex corresponds exactlyto the averaged specified Riemannian metric 5 forthat simplex, the following equality holds :
� 5However, in practice, there is usually some discrepancybetween these two metrics and this section presents amethod to measure this discrepancy.
Qualite des maillages – p.267/329
Simple x Conf ormity
This equality of metrics can be rewritten in the twofollowing ways :
5 � �
and
� � 5where is the identity matrix.
Qualite des maillages – p.268/329
Simple x Residuals
When a perfect match between what is specified and whatis realized does not happen, a residual for each of the twoprevious equations yields the two following tensors :
6 5 � �and
7 � � 5
where 6 will detect the degeneration of the simplex asit’s volume tends to zero and 7 as it’s volume tends toinfinity.
Qualite des maillages – p.269/329
Example – Triangle
Recall the triangle with two fixed vertices, oneat
�
and one at
�, and that the
third vertex was free to move. Furthermore, if the specifiedtriangle is the unit equilateral triangle, then the averagedspecified Riemannian metric is equal to the identity matrix,ie :
5 5 �
Qualite des maillages – p.270/329
Example – Triangle
The residuals 6 and 7 can be written as
6
��
��
7
�
�
�
�
Qualite des maillages – p.271/329
Example – with
If the third vertex is restricted to the axis , then allbut the first term of these tensors vanish.The two curves intersect at , where the residualsbecome null.
0
5
10
15
20
1
Res
idua
l
8x2 30.5
Rs Rb
Qualite des maillages – p.272/329
Total Residual
The total residual 9 is defined to be the sum of the tworesiduals 6 and 7, ie,
9 6 7 5 � � � � 5
Qualite des maillages – p.273/329
The Non-Conf ormity of aSimple x
Définition : The non-conformity � of a simplex withrespect to the averaged specified Riemannian metric isdefined to be the Euclidean norm of the total residual 9,
� 9 9 � 9
The Euclidean norm of a matrix amounts to the squareroot of the sum of each term of the matrix individuallysquared.
Qualite des maillages – p.274/329
Example – Triangle
For the triangle described above with two fixed verticesand a free vertex and for which the specified Riemannianmetric was the identity matrix, the coefficient ofnon-conformity is expressed as,
�
��
� � � �
Qualite des maillages – p.275/329
Example – Triangle
Logarithm base of
� when the targetmetric is the identitymatrix. It is minimumand equal to zero forthe equilateral triangle,and increases very ra-pidly as the third vertexmoves away from theoptimal position. It is in-finite for all degeneratetriangles.
x 3210
y
1
0
-1
5 �:
:� , ;< =
�
Qualite des maillages – p.276/329
Visualization of
The specified metric isdefined in GEORGE andBOROUCHAKI (1997). Itis an analytical functionthat defines an isotropicmetric.
Qualite des maillages – p.277/329
Visualization of
The specified metric isdefined in GEORGE andBOROUCHAKI (1997). Itis an analytical functionthat define an anisotro-pic metric.
Qualite des maillages – p.278/329
Visualization of
Supersonic laminar vs-cous air flow aroundNACA 0012. The spe-cified anisotropic metricis based on interpola-tion error (second deri-vatives) of speed field.
Qualite des maillages – p.279/329
Un critère univer sel de qualité demailla ge
Table des matières1. Introduction2. La métrique � du simplexe3. La métrique spécifiée4. La non conformité � d’un simplexe5. La non conformité d’un maillage6. Généralisation des critères de taille7. Extension aux éléments non simpliciaux8. Interrogation orale9. Ce qu’il faut retenir
Qualite des maillages – p.280/329
The Non-Conf ormity of a Mesh
Définition : The coefficient of non-conformity of amesh is defined as :
�� >
�� �� &
which is the average value of the coefficient ofnon-conformity of the � simplices of the mesh.
Qualite des maillages – p.281/329
Proper ties of
The perfect mesh is obtained when the coefficient ofnon-conformity of the mesh vanishes.And if one simplex of the mesh degenerates, then
tends to infinity.The coefficient of non-conformity of a mesh is
insensitive to compatible scaling of both the mesh andthe specified Riemannian metric.
Qualite des maillages – p.282/329
Symmetr y in Size of
() Coarse mesh () Perfect mesh () Fine mesh
If the target mesh is the middle mesh, the coefficient ofnon-conformity of the first and last meshes are equivalent.
Qualite des maillages – p.283/329
Proper ties of
It is possible to compare the quality of the mesh of twovastly different domains, such as the mesh of a galaxy andthe mesh of a micro-circuit. In both cases, the measuregives a comparable number that reflects the degree towhich each mesh satisfies its size specification map.
This coefficient therefore poses itself as a unique anddimensionless measure of the non-conformity of a meshwith respect to a size specification map given in the form ofa Riemannian metric, be it isotropic or anisotropic.
Qualite des maillages – p.284/329
Un critère univer sel de qualité demailla ge
Table des matières1. Introduction2. La métrique � du simplexe3. La métrique spécifiée4. La non conformité � d’un simplexe5. La non conformité d’un maillage6. Généralisation des critères de taille7. Extension aux éléments non simpliciaux8. Interrogation orale9. Ce qu’il faut retenir
Qualite des maillages – p.285/329
Generalisation of Size QualityMeasures
The non-conformity between the metric � of a simplicialelement and the specified metric 5, ie,
� 5is a generalisation of the size criterion � and theefficiency index .
Qualite des maillages – p.286/329
Generalisation of the SizeCriterion
� 5
�
�
�
�
5
and then
�
� �
5
� is an integral form of the conformity between themetric � of the simplex and the specified metric 5.
Qualite des maillages – p.287/329
Generalisation of Efficienc y Index
Let , a simplex and , an edge of this simplex. Thenthe pointwise conformity between the metric � of thesimplex and the specified metric 5
� 5can be evaluated in an integral form over the edge of thesimplex as
�
� �
�
� 5
5
Qualite des maillages – p.288/329
Generalisation of Efficienc y Index
This relation
5
can be rewritten as two residual :
� 5 or � 5
which is the efficiency index . This index is an integralform of the conformity between the metric � of thesimplex and the specified metric 5 evaluated over theedges of the mesh.
Qualite des maillages – p.289/329
Un critère univer sel de qualité demailla ge
Table des matières1. Introduction2. La métrique � du simplexe3. La métrique spécifiée4. La non conformité � d’un simplexe5. La non conformité d’un maillage6. Généralisation des critères de taille7. Extension aux éléments non simpliciaux8. Interrogation orale9. Ce qu’il faut retenir
Qualite des maillages – p.290/329
Extension to Non-SimplicialElements
Non-Simplicial elements are quadrilaterals in twodimensions and prisms and hexahedra in threedimensions.
In order to extend this measure to non-simplicial elements,it has to be understood that the metric tensor ofnon-simplicial elements is not a constant and varies forevery point of space.
In other words, the Jacobian of a simplex is constant butthe Jacobian of a non-simplicial element depends of thepoint of evaluation.
Qualite des maillages – p.291/329
Non-Simplicial Element Conf ormity
The conformity between the metric � of a non-simplicialelement and the specified metric 5 takes on a pointwisenature can be rewritten as :
� 5
Qualite des maillages – p.292/329
Non-Simplicial Element Conf ormityResidue
The total residue 9 become a pointwise value
9 �5 � �� 5
Then the non-conformity � of an element with respectto the specified Riemannian metric is defined to beaveraged over the element by an integration of theEuclidean norm of the total residue 9 :
� �
�5 � �� 5
�
Qualite des maillages – p.293/329
Un critère univer sel de qualité demailla ge
Table des matières1. Introduction2. La métrique � du simplexe3. La métrique spécifiée4. La non conformité � d’un simplexe5. La non conformité d’un maillage6. Généralisation des critères de taille7. Extension aux éléments non simpliciaux8. Interrogation orale9. Ce qu’il faut retenir
Qualite des maillages – p.294/329
Test 1
The domain is a unit regular tri-angle.The size specification map is uni-
form and isotropic.The target edge length is .
Qualite des maillages – p.295/329
Test 1 – Unif orm Mesh
A B C
Qualite des maillages – p.296/329
Test 1 – Unif orm Mesh
A B C
Qualite des maillages – p.296/329
Test 2 – Isotr opic Mesh
This test case is defined in GEORGE and BOROUCHAKI(1997).
The domain is a rectangle.
This test case has an isotropic Riemannian metric definedby :
5
�� ��
Qualite des maillages – p.297/329
Test 2 – Isotr opic Mesh
where � � is given by :
if� ��? @ � �A
if� @ �? � �A
if�A
�A ? B�
�if
Qualite des maillages – p.298/329
Test 2 – Isotr opic Mesh
View of the size specification map as a field of tensormetrics and view of a mesh that fits rather well thesetensor metrics.
Qualite des maillages – p.299/329
Test 2a – Isotr opic Mesh
A B C
Qualite des maillages – p.300/329
Test 2a – Isotr opic Mesh
A B C
Qualite des maillages – p.300/329
Test 2b – Isotr opic Mesh
A B C
Qualite des maillages – p.301/329
Test 2b – Isotr opic Mesh
A B C
Qualite des maillages – p.301/329
Test 3 – Anisotr opic Mesh
This test case is defined in GEORGE and BOROUCHAKI(1997).
The domain is a rectangle.
This test case has an anisotropic Riemannian metricdefined by :
5
�� ��
Qualite des maillages – p.302/329
Test 3 – Anisotr opic Mesh
where � is given by :
�
if
� � � B � � �
if
� B � � � � �
if
�A
�A � A�
�if
Qualite des maillages – p.303/329
Test 3 – Anisotr opic Mesh
and � is given by :
�
if
� �? @ � �A
if
� @ ��? � �A
if
�A
�A ? B�
�if
Qualite des maillages – p.304/329
Test 3 – Anisotr opic Mesh
View of the size specification map as a field of tensormetrics and view of a mesh that fits rather well thesetensor metrics.
Qualite des maillages – p.305/329
Test 3 – Anisotr opic Mesh
A B C
Qualite des maillages – p.306/329
Test 3 – Anisotr opic Mesh
A B C
Qualite des maillages – p.306/329
Test 4 – Bernhar d Riemann
The size specification map isdeduced from an error esti-mator based on the secondderivatives of the grey level ofthe picture.
Qualite des maillages – p.307/329
Test 4 – Bernhar d Riemann
A B C
Qualite des maillages – p.308/329
Test 4 – Bernhar d Riemann
A B C
Qualite des maillages – p.308/329
Test 5 – Flow over a Naca 0012
Supersonic laminar flow at Mach 2.0, Reynolds 1000 andan angle of attack of 10 degrees. An a posteriori errorestimator is deduced from this solution.
Qualite des maillages – p.309/329
Test 5a – Flow over a Naca 0012
A B C
Specified Metric
Qualite des maillages – p.310/329
Test 5a – Flow over a Naca 0012
A B CSpecified Metric 5
Qualite des maillages – p.310/329
Test 5b – Flow over a Naca 0012
A B C
Specified Metric
Qualite des maillages – p.311/329
Test 5b – Flow over a Naca 0012
A B CSpecified Metric 5
Qualite des maillages – p.311/329
Test 5c – Flow over a Naca 0012
A B C
Specified Metric
Qualite des maillages – p.312/329
Test 5c – Flow over a Naca 0012
A B CSpecified Metric 5
Qualite des maillages – p.312/329
Un critère univer sel de qualité demailla ge
Table des matières1. Introduction2. La métrique � du simplexe3. La métrique spécifiée4. La non conformité � d’un simplexe5. La non conformité d’un maillage6. Généralisation des critères de taille7. Extension aux éléments non simpliciaux8. Interrogation orale9. Ce qu’il faut retenir
Qualite des maillages – p.313/329
What to Retain
This lecture presented a method to measure thenon-conformity of a simplex and of a whole mesh withrespect to a size specification map given in the form of aRiemannian metric.
This measure is sensitive to discrepancies in both size andshape with respect to what is specified.
Analytical examples of the behavior were presented andnumerical examples were provided.
Qualite des maillages – p.314/329
The Non-Conf ormity is Univer sal
The coefficient of non-conformity of a mesh, , is auniversal measure in the following sense :
It is defined in two and three dimensions.
It is sensitive to all simplex degeneracies.It takes into account an Euclidean or Riemannian
metric, isotropic or anisotropic.It is sensitive to discrepancies in shape and in size.It is also defined for non-simplicial elements.It gives a unique number for the whole mesh.It characterizes a whole mesh, coarse or fine, in a small
or a big domain.
Qualite des maillages – p.315/329
The Non-Conf ormity is Univer sal
The coefficient of non-conformity of a mesh, , is auniversal measure in the following sense :
It is defined in two and three dimensions.It is sensitive to all simplex degeneracies.
It takes into account an Euclidean or Riemannianmetric, isotropic or anisotropic.It is sensitive to discrepancies in shape and in size.It is also defined for non-simplicial elements.It gives a unique number for the whole mesh.It characterizes a whole mesh, coarse or fine, in a small
or a big domain.
Qualite des maillages – p.315/329
The Non-Conf ormity is Univer sal
The coefficient of non-conformity of a mesh, , is auniversal measure in the following sense :
It is defined in two and three dimensions.It is sensitive to all simplex degeneracies.It takes into account an Euclidean or Riemannian
metric, isotropic or anisotropic.
It is sensitive to discrepancies in shape and in size.It is also defined for non-simplicial elements.It gives a unique number for the whole mesh.It characterizes a whole mesh, coarse or fine, in a small
or a big domain.
Qualite des maillages – p.315/329
The Non-Conf ormity is Univer sal
The coefficient of non-conformity of a mesh, , is auniversal measure in the following sense :
It is defined in two and three dimensions.It is sensitive to all simplex degeneracies.It takes into account an Euclidean or Riemannian
metric, isotropic or anisotropic.It is sensitive to discrepancies in shape and in size.
It is also defined for non-simplicial elements.It gives a unique number for the whole mesh.It characterizes a whole mesh, coarse or fine, in a small
or a big domain.
Qualite des maillages – p.315/329
The Non-Conf ormity is Univer sal
The coefficient of non-conformity of a mesh, , is auniversal measure in the following sense :
It is defined in two and three dimensions.It is sensitive to all simplex degeneracies.It takes into account an Euclidean or Riemannian
metric, isotropic or anisotropic.It is sensitive to discrepancies in shape and in size.It is also defined for non-simplicial elements.
It gives a unique number for the whole mesh.It characterizes a whole mesh, coarse or fine, in a small
or a big domain.
Qualite des maillages – p.315/329
The Non-Conf ormity is Univer sal
The coefficient of non-conformity of a mesh, , is auniversal measure in the following sense :
It is defined in two and three dimensions.It is sensitive to all simplex degeneracies.It takes into account an Euclidean or Riemannian
metric, isotropic or anisotropic.It is sensitive to discrepancies in shape and in size.It is also defined for non-simplicial elements.It gives a unique number for the whole mesh.
It characterizes a whole mesh, coarse or fine, in a smallor a big domain.
Qualite des maillages – p.315/329
The Non-Conf ormity is Univer sal
The coefficient of non-conformity of a mesh, , is auniversal measure in the following sense :
It is defined in two and three dimensions.It is sensitive to all simplex degeneracies.It takes into account an Euclidean or Riemannian
metric, isotropic or anisotropic.It is sensitive to discrepancies in shape and in size.It is also defined for non-simplicial elements.It gives a unique number for the whole mesh.It characterizes a whole mesh, coarse or fine, in a small
or a big domain.
Qualite des maillages – p.315/329
Mesh Optimization
This measure poses itself as a natural measure to use inthe benchmarking process. Indeed, since the measure isable to compare two different meshes, it can help tocompare the algorithms used to produce the meshes.
This measure of the non-conformity of a mesh seems to bean adequate cost function for mesh generation, meshoptimization and mesh adaptation. This measure could beused for each step such that each step minimizes thesame cost function.
Qualite des maillages – p.316/329
Table des matières
1. Introduction2. Définition d’un simplexe3. Dégénérescence des sim-
plexes4. Qualité de forme des sim-
plexes5. Formules pour les sim-
plexes6. Voronoï, Delaunay et Rie-
mann7. Critères de formes et de
Delaunay
8. Éléments non simpliciaux9. Représentation des cri-
tères de forme10. Équivalence des critères
de forme11. Qualité globale et optimi-
sation12. Qualité en taille des sim-
plexes13. Qualité universelle14. Conclusions
Qualite des maillages – p.317/329
Conc lusions
Enfin, il achève ! ! !
Qualite des maillages – p.318/329
Simple xes dégénérés
Un simplexe est dégénéré si sa mesure est nulle.
La dégénérescence est indépendante de la métrique.Un critère de forme est valide s’il est sensible à tous les
cas de dégénérescence.Un critère de forme est non valide s’il est non-nul pour
certain simplexes dégénérés.
Qualite des maillages – p.319/329
Simple xes dégénérés
Un simplexe est dégénéré si sa mesure est nulle.La dégénérescence est indépendante de la métrique.
Un critère de forme est valide s’il est sensible à tous lescas de dégénérescence.Un critère de forme est non valide s’il est non-nul pour
certain simplexes dégénérés.
Qualite des maillages – p.319/329
Simple xes dégénérés
Un simplexe est dégénéré si sa mesure est nulle.La dégénérescence est indépendante de la métrique.Un critère de forme est valide s’il est sensible à tous les
cas de dégénérescence.
Un critère de forme est non valide s’il est non-nul pourcertain simplexes dégénérés.
Qualite des maillages – p.319/329
Simple xes dégénérés
Un simplexe est dégénéré si sa mesure est nulle.La dégénérescence est indépendante de la métrique.Un critère de forme est valide s’il est sensible à tous les
cas de dégénérescence.Un critère de forme est non valide s’il est non-nul pour
certain simplexes dégénérés.
Qualite des maillages – p.319/329
Critères de forme
La beauté, la qualité, la forme , est une notion touterelative .
Il faut d’abord être capable de définir qu’est-ce qu’onveut pour pouvoir juger ce qu’on a obtenu.“Qu’est-ce qu’on veut” s’écrit sous forme d’une
métrique.Un critère de forme est une mesure de l’équilatéralité
d’un simplexe dans la métrique.
Qualite des maillages – p.320/329
Critères de forme
La beauté, la qualité, la forme , est une notion touterelative .Il faut d’abord être capable de définir qu’est-ce qu’on
veut pour pouvoir juger ce qu’on a obtenu.
“Qu’est-ce qu’on veut” s’écrit sous forme d’unemétrique.Un critère de forme est une mesure de l’équilatéralité
d’un simplexe dans la métrique.
Qualite des maillages – p.320/329
Critères de forme
La beauté, la qualité, la forme , est une notion touterelative .Il faut d’abord être capable de définir qu’est-ce qu’on
veut pour pouvoir juger ce qu’on a obtenu.“Qu’est-ce qu’on veut” s’écrit sous forme d’une
métrique.
Un critère de forme est une mesure de l’équilatéralitéd’un simplexe dans la métrique.
Qualite des maillages – p.320/329
Critères de forme
La beauté, la qualité, la forme , est une notion touterelative .Il faut d’abord être capable de définir qu’est-ce qu’on
veut pour pouvoir juger ce qu’on a obtenu.“Qu’est-ce qu’on veut” s’écrit sous forme d’une
métrique.Un critère de forme est une mesure de l’équilatéralité
d’un simplexe dans la métrique.
Qualite des maillages – p.320/329
Critères de forme
La moyenne d’un critère de forme valide sur tous lessimplexes du maillage est un critère de qualitésignificatif.
Les critères de forme sont plus ou moins équivalentsdans la caractérisation d’un maillage.Les critères de forme sont plus ou moins équivalents
dans l’optimisation d’un maillage.
Qualite des maillages – p.321/329
Critères de forme
La moyenne d’un critère de forme valide sur tous lessimplexes du maillage est un critère de qualitésignificatif.Les critères de forme sont plus ou moins équivalents
dans la caractérisation d’un maillage.
Les critères de forme sont plus ou moins équivalentsdans l’optimisation d’un maillage.
Qualite des maillages – p.321/329
Critères de forme
La moyenne d’un critère de forme valide sur tous lessimplexes du maillage est un critère de qualitésignificatif.Les critères de forme sont plus ou moins équivalents
dans la caractérisation d’un maillage.Les critères de forme sont plus ou moins équivalents
dans l’optimisation d’un maillage.
Qualite des maillages – p.321/329
Critères de taille
Les simplexes peuvent être de la bonne forme sanspour autant être de la bonne taille.
Il existe des critères de qualité en taille des simplexeset des maillages.En principe, un simplexe dont toutes les arêtes sont de
longueur unité dans la métrique, est aussi de formeparfaite dans la métrique.En pratique, les maillages construits ne sont pas
parfaitement de la bonne taille et les simplexes sontcomposés d’arêtes plus ou moins trop courtes ou troplongues.
Qualite des maillages – p.322/329
Critères de taille
Les simplexes peuvent être de la bonne forme sanspour autant être de la bonne taille.Il existe des critères de qualité en taille des simplexes
et des maillages.
En principe, un simplexe dont toutes les arêtes sont delongueur unité dans la métrique, est aussi de formeparfaite dans la métrique.En pratique, les maillages construits ne sont pas
parfaitement de la bonne taille et les simplexes sontcomposés d’arêtes plus ou moins trop courtes ou troplongues.
Qualite des maillages – p.322/329
Critères de taille
Les simplexes peuvent être de la bonne forme sanspour autant être de la bonne taille.Il existe des critères de qualité en taille des simplexes
et des maillages.En principe, un simplexe dont toutes les arêtes sont de
longueur unité dans la métrique, est aussi de formeparfaite dans la métrique.
En pratique, les maillages construits ne sont pasparfaitement de la bonne taille et les simplexes sontcomposés d’arêtes plus ou moins trop courtes ou troplongues.
Qualite des maillages – p.322/329
Critères de taille
Les simplexes peuvent être de la bonne forme sanspour autant être de la bonne taille.Il existe des critères de qualité en taille des simplexes
et des maillages.En principe, un simplexe dont toutes les arêtes sont de
longueur unité dans la métrique, est aussi de formeparfaite dans la métrique.En pratique, les maillages construits ne sont pas
parfaitement de la bonne taille et les simplexes sontcomposés d’arêtes plus ou moins trop courtes ou troplongues.
Qualite des maillages – p.322/329
Critères de taille
Or, le rapport de la plus petite arête sur la plus grandepeut être aussi grand que pour qu’un tétraèdredégénère en cerf-volant.
Cela signifie qu’un simplexe ayant des arêtes de tailleconvenable n’implique pas que ce simplexe est aussiforme convenable car il peut être totalement dégénéré.
Qualite des maillages – p.323/329
Critères de taille
Or, le rapport de la plus petite arête sur la plus grandepeut être aussi grand que pour qu’un tétraèdredégénère en cerf-volant.Cela signifie qu’un simplexe ayant des arêtes de taille
convenable n’implique pas que ce simplexe est aussiforme convenable car il peut être totalement dégénéré.
Qualite des maillages – p.323/329
Critère univer sel
Ceci amène naturellement le problème dans toute sagénéralité :
Quelle serait un critère de qualité simplicial qui mesuraitsim ultanément taille et forme , qui serait sensible à tousles cas de dégénérescence des simplexes, qui seraitoptimal pour le simplexe régulier et unitaire, dans unemétrique euclidienne ou riemannienne, isotrope ouanisotrope, en deux et en trois dimensions.
Qualite des maillages – p.324/329
Prochainement sur vos écrans
P. LABBÉ, J. DOMPIERRE, M.-G. VALLET, F. GUIBAULT etJ.-Y. TRÉPANIER. A Measure of the Conformity of a Meshto an Anisotropic Metric, Tenth International MeshingRoundtable, Newport Beach, CA, octobre 2001, pages319–326,
proposent un tel critère qui mesure la conformité en tailleet forme entre le maillage qui a été construit et le maillagequi avait été spécifié par la métrique.
Qualite des maillages – p.325/329
The Non-Conf ormity of a Mesh
A method to measure the non-conformity of a simplex andof a whole mesh with respect to a size specification mapgiven in the form of a Riemannian metric was given.
This measure is sensitive to discrepancies in both size andshape with respect to what is specified.
Analytical examples of the behavior were presented andnumerical examples were provided.
Qualite des maillages – p.326/329
The Non-Conf ormity is Univer sal
The coefficient of non-conformity of a mesh, , is auniversal measure in the following sense :
It is defined in two and three dimensions.
It is sensitive to all simplex degeneracies.It takes into account an Euclidean or Riemannian
metric, isotropic or anisotropic.It is sensitive to discrepancies in shape and in size.It is also defined for non-simplicial elements.It gives a unique number for the whole mesh.It characterizes a whole mesh, coarse or fine, in a small
or a big domain.
Qualite des maillages – p.327/329
The Non-Conf ormity is Univer sal
The coefficient of non-conformity of a mesh, , is auniversal measure in the following sense :
It is defined in two and three dimensions.It is sensitive to all simplex degeneracies.
It takes into account an Euclidean or Riemannianmetric, isotropic or anisotropic.It is sensitive to discrepancies in shape and in size.It is also defined for non-simplicial elements.It gives a unique number for the whole mesh.It characterizes a whole mesh, coarse or fine, in a small
or a big domain.
Qualite des maillages – p.327/329
The Non-Conf ormity is Univer sal
The coefficient of non-conformity of a mesh, , is auniversal measure in the following sense :
It is defined in two and three dimensions.It is sensitive to all simplex degeneracies.It takes into account an Euclidean or Riemannian
metric, isotropic or anisotropic.
It is sensitive to discrepancies in shape and in size.It is also defined for non-simplicial elements.It gives a unique number for the whole mesh.It characterizes a whole mesh, coarse or fine, in a small
or a big domain.
Qualite des maillages – p.327/329
The Non-Conf ormity is Univer sal
The coefficient of non-conformity of a mesh, , is auniversal measure in the following sense :
It is defined in two and three dimensions.It is sensitive to all simplex degeneracies.It takes into account an Euclidean or Riemannian
metric, isotropic or anisotropic.It is sensitive to discrepancies in shape and in size.
It is also defined for non-simplicial elements.It gives a unique number for the whole mesh.It characterizes a whole mesh, coarse or fine, in a small
or a big domain.
Qualite des maillages – p.327/329
The Non-Conf ormity is Univer sal
The coefficient of non-conformity of a mesh, , is auniversal measure in the following sense :
It is defined in two and three dimensions.It is sensitive to all simplex degeneracies.It takes into account an Euclidean or Riemannian
metric, isotropic or anisotropic.It is sensitive to discrepancies in shape and in size.It is also defined for non-simplicial elements.
It gives a unique number for the whole mesh.It characterizes a whole mesh, coarse or fine, in a small
or a big domain.
Qualite des maillages – p.327/329
The Non-Conf ormity is Univer sal
The coefficient of non-conformity of a mesh, , is auniversal measure in the following sense :
It is defined in two and three dimensions.It is sensitive to all simplex degeneracies.It takes into account an Euclidean or Riemannian
metric, isotropic or anisotropic.It is sensitive to discrepancies in shape and in size.It is also defined for non-simplicial elements.It gives a unique number for the whole mesh.
It characterizes a whole mesh, coarse or fine, in a smallor a big domain.
Qualite des maillages – p.327/329
The Non-Conf ormity is Univer sal
The coefficient of non-conformity of a mesh, , is auniversal measure in the following sense :
It is defined in two and three dimensions.It is sensitive to all simplex degeneracies.It takes into account an Euclidean or Riemannian
metric, isotropic or anisotropic.It is sensitive to discrepancies in shape and in size.It is also defined for non-simplicial elements.It gives a unique number for the whole mesh.It characterizes a whole mesh, coarse or fine, in a small
or a big domain.
Qualite des maillages – p.327/329
Mesh Optimization
This measure poses itself as a natural measure to use inthe benchmarking process. Indeed, since the measure isable to compare two different meshes, it can help tocompare the algorithms used to produce the meshes.
This measure of the non-conformity of a mesh seems to bean adequate cost function for mesh generation, meshoptimization and mesh adaptation. This measure could beused for each step such that each step minimizes thesame cost function.
Qualite des maillages – p.328/329
La fin
Qualite des maillages – p.329/329
La fin
Qualite des maillages – p.329/329