| Il faut ainsi franchir les limites de l’implémentation pour voir l’idée se concrétiser au prix d’un travail parfois ingrat et fastidieux. La complexité croissante des problèmes de simulation rencontrés ne fait d’ailleurs que renforcer ce constat.
Schématiquement, on trouve 3 grandes familles de méthodes : les méthodes d'octree, les méthodes de type Delaunay et les méthodes frontales.
Les méthodes d'octree [138] n'ont pas été retenues pour les raisons suivantes :
• Les éléments de moins bonne qualité sont générés près des frontières où une plus grande précision est souvent souhaitée,
• Le découpage des parties pleines du volume ne pose pas de problème mais les intersections avec la surface frontière conduisent à de nombreux cas particuliers,
• La méthode s'applique mal aux pièces relativement plates. En effet, les vis-à-vis de faces trop proches peuvent aboutir à un raffinement de maillage trop fin.
A priori, les approches de type Delaunay reposent sur une base mathématique démontrable. Dans le plan, la triangulation de Delaunay permet d'obtenir la meilleure triangulation possible. Dans l'espace, un critère équivalent sur l'angle solide n'est pas vérifié et la triangulation de Delaunay ne conduit pas au meilleur maillage possible. En d'autres termes, le seul critère de Delaunay ne conduit pas à un maillage de qualité optimale et des éléments aplatis (désignés sous le terme anglo-saxon slivers) sont créés [32].
En France, les travaux réalisés par Paul-Louis George à l'INRIA autour des techniques de Delaunay en dimension 3 ont largement contribué au succès de cette approche. George a proposé des solutions convaincantes pour retrouver systématiquement la frontière de l'objet [61].
Le choix de la technique de maillage s'est porté sur la méthode frontale encore appelée méthode par avancée de front. Une fois de plus, l'originalité du travail ne porte pas sur la méthode en elle-même en ce sens où celle-ci était connue et utilisée par (seulement) quelques auteurs en dimension 3 [66][104]. Un des avantages indéniables de la méthode réside dans le fait que la frontière du domaine est systématiquement conservée. Un de nos objectifs à ce moment était d'utiliser la technique pour effectuer a posteriori des modifications locales du maillage pour respecter une carte de taille.
Retour haut de page
La méthode frontale et ses difficultés
Le principe de la méthode frontale [110] est itératif. Le front est initialisé sur la frontière du domaine. Dans le plan, le front désigne donc un ensemble de segments. Par la suite, le front désigne la frontière entre la zone maillée et la zone non-maillée.
L’algorithme fait appel aux étapes suivantes :
Tant que le front n'est pas vide :
1. Choisir un élément du front.
2. Rechercher les points proches de cet élément ou créer un point idéal.
3. Trier ces points en fonction de priorités à définir (qualité, convergence).
4. Créer un élément avec le premier point qui satisfait aux tests de validité.
5. Mettre à jour le front.
Dans l'espace, à notre connaissance, les premières références et solutions à ce problème sont apportées par Löhner et Parikh [104] notamment au niveau de la détection des intersections et des structures de données qui permettent un adressage rapide d'objets dans l'espace.
Le but de nos recherches était de mettre en évidence certains problèmes posés par la méthode et d'apporter des solutions adaptées. Par ailleurs, ces recherches s'effectuant dans un contexte industriel, un des objectifs sous-jacent était de réaliser un logiciel fiable et suffisamment performant.
Le principe même de la méthode fait qu'il n'y a pas "une" méthode frontale mais de nombreuses façons d'appréhender le problème. On peut par exemple choisir de construire les nœuds et les éléments simultanément ou découpler les deux étapes, jouer sur la gestion du front, le critère de sélection des nœuds candidats entre autres.
Les approches de type Delaunay reposent sur une base mathématique démontrable. Néanmoins, dès lors que l'on souhaite obtenir une triangulation qui respecte la frontière, force est de constater qu'il faut quitter cette théorie. Avec du recul, on s'aperçoit d'ailleurs que le problème de respect de frontière inhérent aux méthodes de Delaunay en dimension 3 ressemble fortement aux problèmes de convergence rencontrés par la méthode frontale.
La phase de création d'un élément à partir d'un constituant du front et d'un réseau de nœuds donné est toujours possible dans le plan. En revanche, le respect des faces et les intersections rendent cette opération souvent impossible en 3D.
Le principe de connexion de la méthode frontale est local : on cherche ou on crée un nœud pour former un tétraèdre avec une face. Les faces du tétraèdre créé ne doivent pas couper d'autres faces existantes. Une analyse par trop rapide peut conduire à penser qu'il suffit de construire un nuage de nœuds bien répartis et de connecter ces nœuds en s'assurant que les éléments ne se coupent pas pour créer un maillage de qualité.
L'exemple de la Figure suivante, pourtant très simple, illustre l'un des principaux points de blocage de la méthode frontale.
L'objet à mailler est un prisme. Cet objet fait partie des polyèdres de Schönhart [137] Les faces du volume enveloppe sont imposées. F désigne la face courante du front. Le nœud D n'est pas candidat car le tétraèdre créé est aplati. Le nœud A ne peut être choisi car l'arête BC est coupée (Figure b). De même, le nœud B ne peut être choisi car l'arête AD est coupée (Figure c). La solution consiste à créer un nœud à l'intérieur du prisme.
Configuration délicate de la méthode frontale, polyèdres de Schönhart.
Cette configuration se présente fréquemment au cours du maillage. Si le polyèdre à mailler n'est pas "étoilé" par rapport au point (le nœud généré n'est pas "vu" par toutes les faces de la coquille), une autre solution doit être envisagée. Si la coquille à mailler est aplatie, la génération d'un nœud interne donne naissance à des éléments de très mauvaise qualité. Une solution consiste alors à détruire les éléments qui empêchent la poursuite du processus de création des tétraèdres [105] ou encore à détruire les éléments qui ont donné naissance au problème.
Un autre problème des algorithmes frontaux est la non-convergence due aux phénomènes de réduction de poches et la génération intempestive de nœuds. Au cours du processus de maillage, il se peut que l'algorithme soit contraint de générer un nœud pour débloquer une situation analogue à celle du prisme de la Figure précédente. De nouvelles faces sont alors créées et de nouveaux cas de blocage peuvent apparaître.
Retour haut de page
Solutions apportées
La réussite de la méthode a reposé sur le couplage des idées suivantes :
• Les nœuds du maillage sont créés a priori à l'aide d'un arbre octal. La racine de l'arbre est un cube englobant le nuage des points de l'enveloppe du volume. L'arbre est construit par insertions successives de points pondérés. Les octants sont découpés suivant un processus récursif jusqu'au niveau où le rapport entre la taille de l'octant contenant le point et la densité imposée au point atteint une valeur choisie par l'utilisateur (par défaut, le rapport de taille est fixé à 2). Une fois que tous les points pondérés ont été introduits, l'arbre est équilibré afin que le rapport de taille entre deux octants voisins soit limité à 2. Des nœuds peuvent être néanmoins créés pendant le processus de connexion pour résoudre les configurations les plus délicates. Une fois que l'arbre octal est construit, les nœuds du maillage sont créés aux sommets des feuilles de l'arbre.
Si le mailleur est utilisé sans contrainte sur la taille des éléments, les points permettant de construire l'arbre sont les nœuds du volume-enveloppe pondérés par la moyenne de longueur d'arête au nœud. Si le mailleur est utilisé avec respect de taille dans un contexte d'adaptation de maillage, les points de découpage de l'octree sont d'une part, les nœuds du nouveau maillage adapté du volume-enveloppe (on considère que le maillage de la peau respecte la nouvelle densité prescrite par l'analyse) et d'autre part, les nœuds intérieurs du maillage volumique initial pondérés par la taille fournie par les estimateurs d'erreur.
Les nœuds, les faces de la frontière et les tétraèdres sont stockés dans les octants qui ont servi à la génération des nœuds. L'octree sert de motif à la génération des nœuds, de système de repérage et de structure de contrôle de la densité de maillage.
• Plusieurs fronts sont créés suivant l'ordre de priorité des faces actives (le front désigne la frontière entre la zone maillée et la zone non-maillée). La technique consiste à construire en priorité les tétraèdres de meilleure qualité afin d'éviter que les plus mauvais éléments ne viennent ralentir ou empêcher la convergence de l'algorithme.
Retour haut de page
Nous avons observé que l'ordre dans lequel les faces du front sont activées a une influence considérable sur la convergence et la qualité du maillage. Cependant, le point le plus négligé des méthodes par avancée de front dans l'espace est la gestion du front lui-même. Les faces du front sont traditionnellement classées par ordre de taille croissante afin que la construction des éléments les plus grands ne viennent pas perturber la création des plus petits. Hormis cette précaution essentielle, la difficulté de la méthode frontale est souvent systématiquement reportée sur la recherche du nœud candidat. La gestion du front suivant des impératifs de qualité est à notre connaissance un concept nouveau. La méthode proposée a permis d'améliorer de façon significative la qualité du maillage et la vitesse de convergence de l'algorithme.
· La recherche d'un nœud candidat privilégie la fermeture de la matière. En particulier, les nœuds candidats prioritaires sont les nœuds qui se trouvent sur les faces partageant une arête avec la face (nœuds adjacents).
· L'utilisation d'un historique de création des éléments permet d'éviter les phénomènes de réduction de poches et une génération intempestive de nœuds. En cas de non-convergence, des éléments sont détruits. Les cycles de construction/destruction sont gérés efficacement pour éviter les boucles infinies. Le processus de destruction de tétraèdres permet de corriger d'éventuelles erreurs de précision détectées a posteriori.
· Le processus d'optimisation de maillage est itératif. Son principe repose sur l'utilisation locale de l'algorithme utilisé pour mailler l'ensemble du volume. La technique d'optimisation de maillage proposée et utilisée par de nombreux auteurs [40][60][62] consiste à extraire du volume maillé en tétraèdres des sous-volumes et à remailler l'enveloppe de ces sous-volumes en essayant d'augmenter leur qualité. Les sous-volumes sont construits en déterminant l'ensemble des tétraèdres partageant un même nœud, une même arête ou une même face. La méthode ne se limite pas au remaillage de coquilles convexes à l'instar des auteurs cités précédemment.
L'étape la plus difficile du maillage frontal est de remplir le volume en tenant compte dans la mesure du possible de la densité locale imposée par la frontière du domaine et en respectant des impératifs de qualité "acceptables". En effet, une fois qu'un maillage est obtenu, des procédures d'optimisations locales peuvent améliorer le maillage dans les zones où une baisse de qualité a été consentie. Exiger des impératifs de forme ou de taille sévères pendant le maillage tend diminuer le nombre de solutions acceptables et donc à réduire les chances de convergence.
Il est important de noter que la plupart des remarques faites dans le cadre de cette Section dépendent fortement de l'implémentation de la méthode.
Retour haut de page
Exemples
En guise d'exemples, nous montrons quelques maillages réalisés avec cette technique et extraits des références [R7][R55].
Un amas polymétallique (environ 60000 éléments) est représenté en Figure a et un boîtier de direction (environ 70000 éléments) en Figure b (avec l'aimable autorisation de PSA).
Retour haut de page
|
