<figure><img src="image_1.png" /></figure>

HAL
open science

# Maillage hexaédrique par octree: avancées et limites

Loïc Maréchal

► To cite this version:

Loïc Maréchal. Maillage hexaédrique par octree: avancées et limites. IPSI 2004, Mar 2004, Paris, France. hal-05469646

HAL Id: hal-05469646

https://inria.hal.science/hal-05469646v1

Submitted on 21 Jan 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Maillage hexaédrique par *octree* : avancées et limites

Loïc MARÉCHAL

INRIA, Projet Gamma,
Domaine de Voluceau, Rocquencourt,
BP 105, 78153 Le Chesnay Cedex, France.
Email : loic.marechal@inria.fr

## Résumé

La méthode *octree* est l'une des rares techniques pouvant produire automatiquement des maillages hexaédriques. Les contraintes inhérentes à cette méthode ajoutées à celles de l'hexaèdre la restreignent à la création de maillages soit mixtes et représentant assez fidèlement l'objet à mailler, soit purement hexaédriques et conformes mais au prix d'une approximation très grossière de la géométrie. Ce papier propose un petit état de l'art en la matière ainsi qu'une extension de la méthode *octree* afin d'en tirer le meilleur parti pour la génération automatique de maillages purement hexaédriques et conformes.

Mots clefs : Maillage automatique, Hexaèdre, Non-structuré, Octree.

## 1 Qu'est ce qu'un maillage hexaédrique ?

### 1.1 Définitions

Un maillage hexaédrique peut être definis par trois critères :

**Mixte ou pur** : Un maillage est dit mixte si il comporte des tétraèdres, prismes et pyramides en plus des hexaèdres. On parle aussi de maillage "hex-dominant" lorsque ces derniers représentent plus de 90% du maillage. Un maillage est strictement ou purement hexaédrique si il ne contient rien d'autre que des hexaèdres. En général le choix entre mixte et pur relève du pragmatisme : si l'on ne parvient pas à créer un maillage purement hexaédrique, on est prêt à tolérer d'autres types d'éléments pour peu que leur nombre reste faible au regard de celui des hexaèdres. Notons qu'un maillage strictement hexaédrique peut être utilisé par un solveur prévu pour effectuer ses calculs sur des maillages mixtes ou purs alors qu'un maillage mixte ne peut être utlisé que par un solveur adéquat. Le maillage purement hexaédrique offre donc une plus grande généricité que le mixte.

**Conforme ou non** : Un maillage est dit non-conforme si certains de ses nœuds se trouvent au milieu d'arêtes ou de faces sans être reliés aux autres éléments. Le maillage est conforme dans le cas contraire. Là encore le choix est de nature pragmatique, un maillage non-conforme étant supposé plus simple à créer. De même, un maillage conforme peut être utilisé par des solveurs prévus pour gêrer des maillages conformes ou non alors qu'un maillage non-conforme ne peut être utilisé que par un solveur adéquat.
**Structuré ou non :** Un maillage est dit structuré si le nombre d'éléments partageant un même nœud est constant sur tout le maillage. Il est non structuré dans le cas contraire. On parle aussi de semi-structuré ou structuré par blocs dans le cas où le maillage est composé de grandes zones à structure constante séparées entre elles par des zones de transition non-structurées. Là encore un maillage structuré est plus polyvalent qu'un maillage non-structuré.

**Combinaisons de critères :** Toutes les combinaisons de ces trois attributs sont possibles : on rencontre couramment des maillages strictements hexaédriques, conformes et structurés ou bien mixtes, conformes et non-structurés. Les combinaisons ne sont pas toutes équivalentes, les maillages structurés, conformes et purement hexaédriques étant les plus génériques alors que les maillages mixtes, non-conformes et non-structurés sont restreints à un plus petit nombre d'applications. La combinaison la plus générique est bien evidemment le "saint graal" de l'hexaèdre mais elle est aussi la plus complexe à créer. J'ai donc décidé de relacher une contrainte, la strucure constante, qui me semblait la plus dure à respecter afin de me donner une chance raisonnable de réussir ma recherche. La présente étude porte donc sur le maillage strictement hexaédrique, conforme et non-structuré.

## 1.2 Problèmes

Pourquoi le maillage hexaédrique est-il plus complexe que le tétraédrique ? La réponse tient essentiellement dans la rigidité topologique de l'hexaèdre. Les algorithmes de maillage se basent sur des opérations élémentaires de type géométriques (déplacement des nœuds pour améliorer la qualité d'un élément par exemple) ou topologiques (basculer l'arête commune à deux triangles, insérer un point au milieu d'un tétraèdre). Ces derniers opérateurs, nombreux pour les simplexes (triangles et tétraèdres) sont par contre très rares et très contraignants pour les autres type d'éléments et surtout pour les hexaèdres.

**Conservation topologique :** Au cour des opérations topologiques, il faut s'assurer que le type des éléments est préservé, c'est à dire que les éléments crées à la suite de l'insertion d'un nœud au milieu d'un tétraèdre par exemple, seront eux aussi des tétraèdres. Cette conservation, très simple dans le cas des simplexes, devient cauchemardesque pour les hexaèdres. L'insertion ou le retrait d'un nœud entraine l'apparition de polyèdres quelconques. Il s'agit au mieux d'éléments connus dans le domaine des éléments-finis comme le tétraèdre ou le prisme et au pire de drôles d'oiseaux non commestibles pour la plupart des solveurs !

**Quelques opérateurs usuels en tétraèdres et inexistants en hexaèdres :**

- découpe d'une arête en deux en insérant un nœud au milieu,

- découpe d'un triangle en trois en insérant un nœud au milieu,

- découpe d'un tétraèdre en quatre en insérant un nœud au milieu,

- suppression d'une arête en fusionnant les deux nœuds entre eux,

- bascule de l'arête commune à plusieurs tétraèdres.

Tous ces opérateurs ne conservent pas la topologie dans le cas des quadrangles ou des hexaèdres (cf. fig. 1 pour quelques exemples illustrés).

**Courte liste des opérateurs sur les hexaèdres :**

- le déplacement d'un nœud, est possible et partage les mêmes limitations que les simplexes (respect de la forme de l'élément et de sa taille) mais ajoute une contrainte supplémentaire : la torsion des faces quadrangles,
<figure><img src="image_3.png" /><figcaption>FIG. 1 – Quelques opérateurs usuels sur les simplexes, (figures de dessus) et leurs équivalents sur les quadrangles (figures de dessous). (A) : insertion d'un nœud au milieu d'un élément, (B) : insertion d'un nœud au milieu d'une arête, (C) : fusion de deux nœuds.</figcaption></figure>

- l'insertion de jeux de découpe (patterns) dans un ensemble d'éléments voisins permet d'insérer des points au milieu d'arêtes ou de faces tout en propageant cette modification dans les voisins. Cette opération est contraignante si l'on veut conserver la topologie hexaédrique mais plus libre dans le cas mixte (cf. fig. 2).

- l'étoilement de polyèdre permet de transformer un maillage de polyèdres quelconques en hexaèdres à condition que les éléments du maillage d'origine soient convexes, conformes et que le degré de leurs nœuds soit de trois (si l'on considère chaque polyèdre séparément, tout nœud doit avoir trois arêtes et trois faces incidentes, cf. fig. 3). Cette méthode a été présentée par Armstrong, Li et McKeag dans [1].

## 1.3 Motivations :

Pourquoi un maillage hexaédrique plutôt que tétraédrique ? Ce débat passionnel est aussi vieux que les éléments-finis et dure encore aujourd'hui. Tous les arguments ont été avancés en faveur de l'hexaèdre (nombre d'éléments moindre, meilleur qualité du calcul, visualisation simplifiée, etc...) et contredit par leur opposants ! Les partisants campent sur leurs positions et le débat a largement tourné à la querelle de chapelles. Certaines équipes (éditeurs de logiciels, industriels ou laboratoires de recherches) sont pro-hexaèdres et il ne fait pas bon y parler de tétraèdres et réciproquement. C'est pourquoi je me placerai dans la position prudente (couarde ?) du chercheur désireux de répondre à un besoin industriel récurrent.

De nombreuses méthodes et codes reposants sur des maillages hexaédriques conformes ont été développés depuis de nombreuses années et il existe une forte demande en génération automatique de tels maillages afin de préserver l'existant. Cette demande n'étant toujours pas pleinement satisfaite (loin s'en faut), il me paraît encore d'actualité d'effec-
<figure><img src="image_4.png" /><figcaption>FIG. 2 – À gauche : découpe d'une arête et insertion de patterns afin de garantir la conformité du maillage. Si l'on veut conserver uniquement des quadrangles, on doit découper l'arête en trois. En maillage mixte, on peut la découper en deux (moins d'éléments et moindre choc de taille). À droite : insertion de patterns dans un groupe d'éléments : ici les arêtes ont été découpées en deux en n'utilisant que des quadrangles mais le nombre d'éléments affectés est plus grand.</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>FIG. 3 – Tous les polygones du maillage de gauche ont été étoilés. Un nœud a été inséré en leur barycentre et a été relié au milieu de chaque arête produisant le maillage purement quadrangulaire de droite. Cette propriété est valable en deux dimensions si les polygones ont des nœuds de degré deux et de degré trois en dimension trois.</figcaption></figure>
tuer des recherches dans ce domaine.

# 2 État de l'art

Cette section présente un bref aperçu des algorithmes en cours de recherche ou déja implémentés dans des produits commerciaux à l'heure actuelle (cf. [3] pour une étude plus complète).

## 2.1 Maillage structuré par blocs :

Il consiste à découper la surface à mailler en super-hexaèdres contenant chacun une portion de la géométrie relativement triviale à mailler avec une méthode algébrique (par exemple une grille régulière qui sera déformée afin de représenter le contour de la surface), plus la portion de surface intersectée par le super-bloc est simple et plus la déformation sera aisée et produira des éléments de bonne qualité. Ces méthodes donnent les meilleurs résultats depuis fort longtemps mais la découpe en super-blocs demande toujours un temps utilisateur important (cf. [22]). Des algorithmes permettent de l'automatiser dans des cas assez simples ou pour des géométries particulière (pales d'hélices ou ailes d'avions par exemple). L'utilisation de la surface médiane déduite d'un maillage de Delaunay peut être utilisée pour construire le maillage supers-blocs.

<figure><img src="image_6.png" /><figcaption>FIG. 4 – Maillage structuré par blocs.</figcaption></figure>

## 2.2 Intersection octree ou grille avec une surface

De nombreuses méthodes de ce type sont actuellement développées ou disponibles sur le marché car elles permettent une automatisation quasi totale (cf. [18], [20], [21], [5] et [11]). Le principe est le suivant :

1. un maillage de fond en hexaèdres englobant tout l'espace de l'objet à mailler est crée, il s'agit d'une grille régulière pour le plus simple ou bien d'un maillage avec des variations de tailles, afin de mieux respecter certains détails de la géométrie, généralement issu d'un arbre octree.

2. l'intersection entre les triangles de la surface et ce maillage de fond est calculée et on ne conserve que les hexaèdres intersectés ainsi que l'intérieur du domaine.

3. les hexaèdres intersectés sont soit déformés, soit découpés, afin de représenter au mieux l'objet initial.

Il existe aujourd'hui de nombreux logiciels produisant des maillages mixtes ou non-conformes, et représentant à peu près correctement la frontière avec une adaptation de tailles des éléments aux détails géométriques. Par contre peu de méthodes génèrent uniquement des hexaèdres conformes. Et les rares produits disponibles de ce type ne proposent pas de variations de tailles et représentent mal les détails (géométries "moles" sans angles vifs).
<figure><img src="image_7.png" /><figcaption>FIG. 5 – Intersection grille/surface.</figcaption></figure>

## 2.3 Méthodes frontales

Il existe une grande variété de méthodes s'apparentant au maillage par avancée de front. Toutes sont à l'état de recherche et sont actuellement peu utilisées dans des produits finis.

On y trouve des méthodes s'appuyant sur un maillage tétraédrique initial dont la position des nœuds est régulière et tentant de former des hexaèdres à l'aide de ces nœuds, certains tétraèdres restant dans le maillage final en cas de blocage (cf. [13]).

D'autres méthodes utilisent l'avancée de front de manière plus classique ou maillent dans l'espace dual afin de simplifier les problèmes topologiques (cf. [7]). Aucunes de ces méthodes n'est vraiment opérationnelle à ma connaissance.

## 2.4 Extrusion et révolution

Ce sont historiquement les premières méthodes à avoir été utilisées car elles sont issues de la C.A.O. Elles ont été améliorées par l'apport d'outils de détection automatique d'extrusions et de volumes de révolution possibles, dans des configurations géométriques assez simples toutefois. Des outils permettant le recollement de différentes parties maillées séparément ont aussi été développés. Ces méthodes requièrent un certain savoir-faire de la part de l'utilisateur et sont aussi grandes consommatrices d'heures-ingénieurs. Elles permettent en contrepartie de contrôler assez finement la taille et la qualité du maillage (cf. [10]).

## 2.5 L'heure du choix

Ce tour d'horizon amène deux constatations :

- si l'utilisateur est prêt à passer un temps conséquent, il peut obtenir le maillage qu'il désire à l'aide de méthodes semi-automatiques,

- si il peut se contenter d'un maillage plus grossier il peut l'obtenir de manière automatique à l'aide de méthodes grille/octree à condition toutefois de travailler avec des maillages mixtes (et rarement hex-dominants dans les faits...), les produits maillant uniquement en hexaèdres conformes étant pour l'instant très limités.

Il m'a semblé qu'un mailleur purement hexaédrique et conforme basé sur octree pourrait compléter l'offre actuelle.

L'utilisateur ayant besoin d'un maillage purement hexaédrique (ou en quasi totalité) pourrait alors procéder de la manière suivante : toujours commencer par réaliser un premier maillage avec une telle méthode (à un moindre coût) et n'utiliser une méthode semi-automatique qu'en dernier recours au cas où la qualité du premier maillage serait insuffisante.
# 3 Le projet Hexotic : présentation schématique

## 3.1 Schéma simplifié

L'algorithme d'hexotic repose sur les trois opérations réalisables en hexaèdres vues à la première section : insertion de patterns, étoilement de polyèdres et déplacement de nœuds. La méthode se déroule en sept étapes :

1. Création d'un arbre octree autour de l'objet en subdivisant les octants en fonction de divers critères comme la courbure de la surface ou encore une taille préscrite par un résultat de calcul ou par l'utilisateur.

2. Transformation de l'octree non-conforme en maillage mixte (prismes et hexaèdres) conforme par l'insertion d'éléments de transition adéquats. Ce maillage est dit de "fond".

3. Calcul des intersections entre les arêtes du maillage hexaédrique et les triangles de la surface.

4. Un parcours par voisinage permet de "colorier" les nœuds du maillage selon leur sous-domaine délimité par les arêtes intersectées.

5. Découpe des hexaèdres et prismes selon les sous-domaines de leurs nœuds. On obtient alors un maillage en polyèdres quelconques (mais respectant les contraintes de convexité et de degrés des nœuds nécessaires à l'étoilement).

6. Maillage des polyèdres par étoilement, on obtient alors un maillage purement hexaédrique et conforme.

7. Projection des nœuds de la frontière du maillage hexaédrique sur les triangles de la surface et optimisation de la qualité des éléments par régularisation des nœuds du volume pour obtenir le maillage final.

## 3.2 Analyse de la surface à mailler

Préalablement à la construction de l'octree, la surface en triangles est analysée afin notamment de retrouver les arêtes vives selon un critère d'angle et de traiter certains problèmes comme les triangles dégénérés (surface quasi-nule) conduisant à des instabilités numériques (vecteur normal indéfini, équation de plan instable, etc...).

La taille et la position du cube englobant l'objet sont aussi calculées afin de servir d'octant (élément hexaédrique constituant les feuilles de l'arbre octree, cf. [16] et [17] pour les bases de la méthode octree) "racine".

## 3.3 Construction de l'octree

L'arbre octree est initialisé avec l'octant racine, puis récursivement subdivisé pour respecter un ensemble de critères. Tout octant est subdivisé en huit "fils" si l'un des critères le souhaîte. Ces critères sont de nature géométrique (courbure de la surface ou épaisseur locale de l'objet), physique (résultat d'un estimateur d'erreur *a posteriori* issu d'un calcul) ou bien directement indiqués par l'utilisateur qui peut spécifier une certaine taille minimale ou maximale de maille pour l'ensemble de l'objet.

Cet octree n'est en rien différent de ceux utilisés pour le maillage tétraédrique. Les arêtes sont découpées en deux et l'arbre est équilibré de telle sorte qu'un octant ne peut jamais être plus de deux fois plus grand ou plus de deux fois plus petit que ses voisins (partageant une face ou une arête).
<figure><img src="image_8.png" /><figcaption>FIG. 6 – Schéma de l’algorithme : (a) frontière à mailler, (b) construction de l’octree, (c) conformisation de l’octree, (d) intersection du maillage mixte et de la frontière et coloriage des nœuds internes (en gras), (e) découpe du maillage mixte en polyèdres (polygones en 2D) afin de représenter la frontière (les intersections sont positionnées au milieu des arêtes afin de garantir la qualité des éléments), (f) retrait des éléments extérieurs, (g) étoilement par insertion des nœuds milieux pour obtenir un maillage purement hexaédrique (quadrangulaire en 2D), (h) projection de la frontière du maillage volumique sur celle de l’objet réel et régularisation du maillage final.</figcaption></figure>
## 3.4 Conformisation de l'octree

L'octree constitue bien un maillage hexaédrique mais non-conforme. Cette phase in-
sère des patterns de conformisation afin de relier les nœuds pendants dans les éléments
non conformes. Les éléments insérés sont des hexaèdres et des prismes, c'est à dire des
polyèdres convexes dont les nœuds sont de degré trois, ce qui permet de respecter les pro-
priétés nécessaires à l'étoilement par la méthode des points milieux présentée à la section
précédente.

Un octant est non-conforme si au moins l'une de ses arêtes a été découpée en deux
par un élément voisin, ce qui introduit un nœud pendant. Comme l'octant à douze arêtes,
il existe donc $2^{12} = 4096$ combinaisons d'octants non-conformes ce qui nécessite autant
de patterns différents ! Notons qu'en plus de ce nombre élevé, il faut impérativement que
les polyèdres utilisés dans tous ces patterns respectent les conditions de la méthode des
points milieux ce qui est loin d'être trivial.

Il est possible de résoudre ce problème en subdivisant d'une manière appropriée les
octants non-conformes afin d'en réduire le nombre de combinaisons. Cette méthode a été
présentée dans [11], la figure 7 montre deux des patterns les plus couramment utilisés.

<figure><img src="image_9.png" /><figcaption>FIG. 7 – Patterns à insérer dans un octant ayant un nœud pendant au milieu d'un face et de ses quatre arêtes (à gauche) ou un seul au milieu d'une arête (à droite).</figcaption></figure>

## 3.5 Intersection avec la frontière

Les triangles et arêtes vives de la frontière sont "plongés" dans le maillage de fond (mixte à ce moment) afin d'en calculer les intersections. On recherche plus précisément les intersections entre les arêtes des éléments volumiques et les triangles de la surface ainsi que celles entre les faces des éléments volumiques et les arêtes vives de la surface.

Les associations intersecté-intersectant, sont mémorisées dans une table de hashage afin d'être facilement retrouvées à la phase finale où les nœuds issues de la découpe par la frontière seront projetés sur les triangles ou arêtes vives ayant intersecté le volume.

## 3.6 Recherche des sous-domaines

À ce niveau, nous n'avons encore qu'un maillage de fond du cube englobant l'objet. Il s'agit donc de rechercher quels sont les nœuds se trouvant dans l'objet et ceux à l'extérieur. On emploie pour ce faire un simple algorithme de coloriage par voisinage basé sur une pile (souvent appelé "inside-out") qui se déroule de la manière suivante :

1. Mettre tous les nœuds se trouvant sur le bord du cube englobant au sommet de la pile et leur attribuer l'étiquette extérieur.

2. Dépiler le nœud du sommet de la pile et empiler tous les nœuds reliés directement à celui-ci par une arête à condition qu'ils ne soient pas déja empilés et que l'arête en question ne soit pas intersectée par un triangle de la surface.
3. Si la pile n'est pas vide, retourner en 2.

4. Lorsque tous les nœuds externes ont été coloriés, ceux restant sont les nœuds internes à conserver (dans le cas de multiples sous-domaines, on peut réitérer l'algorithme).

Cet algorithme a pour effet pervers de supprimer tous les détails plus petits que les mailles (ce qui est plutôt logique) ainsi que tous les angles aigus, ce qui est beaucoup plus gênant. Ce point est une des principales limites de la méthode. Si l'on veut absolument respecter les angles aigus il faut alors utiliser des tétraèdres dans ces zones et des pyramides comme transistion vers le reste du maillage hexaédrique.

## 3.7 Découpe en polyèdres

À ce niveau les éléments du volume (hexaèdres et prismes) ont des nœuds de différentes étiquettes, internes ou externes, ce qui va permettre de les découper afin de retouver la frontière de l'objet à mailler.

Comme un hexaèdre à huit nœuds, il existe donc $2^8 = 256$ découpes différentes et $2^6 = 64$ dans le cas du prisme. Le nombre de combinaisons distinctes est en réalité plus faible du fait des équivalence par rotations ou symétries. La figure 8 en donne quelques exemples. Cette méthode à été présentée par G. Dhont dans [6] dans le cas de maillages hexaédriques purs et non-conformes. Je l'ai adaptée à mes maillages mixtes et conformes.

Les hexaèdres et prismes étants intersectés par un seul plan (il ne peut y avoir plusieurs sous-domaines dans un seul élément), les polyèdres résultants sont toujours convexes et leurs nœuds sont toujours de degré trois. Il n'y a donc aucun problème pour enchaîner sur la seconde phase de découpe qui insère un nœud au milieu de tous les polyèdres, de toutes les faces polygonales et de toutes les arêtes du maillage afin d'appliquer l'étoilement par nœuds milieux et d'obtenir un maillage purement hexaédrique et conforme (cf. fig. 9).

<figure><img src="image_10.png" /><figcaption>FIG. 8 – En haut, un hexaèdre avec trois nœuds internes conduit à ne conserver qu'un polyèdre à deux faces triangles, deux quadrangles et deux pentagones. En bas, un prisme avec cinq nœuds internes produit le même genre de polyèdre mais avec une connectivité différente.</figcaption></figure>

## 3.8 Projection des nœuds sur la frontière et régularisation

Le résultat de l'étape précédente est un maillage ressemblant grossièrement à l'objet à mailler, souvent appelé maillage en marches d'escalier car toutes les faces voisines forment des angles de 45° ou 90°. Il ne reste plus qu'à projeter cette surface sur la surface réelle.

Mais auparavant il reste à assigner un "objectif" à chaque nœud de surface du maillage volumique, c'est à dire, un triangle ou une arête vive sur lequel il sera projeté. Pour cela on fait appel à la table de hashage stockant toutes les intersections. On utilise alors une propriété intéressante des éléments issus de l'étoilement : les nœuds des polyèdres d'origine sont obligatoirement projetés sur des triangles et seuls les nœuds milieux des faces et des arêtes peuvent être projetés sur les arêtes vives de l'objet. La figure 10 illustre la découpe de la surface et l'attribution des objectifs à chaque nœud.
<figure><img src="image_11.png" /><figcaption>FIG. 9 – Étoilement par les points milieux. Le barycentre du polyèdre est relié aux barycentres des faces et des arêtes, le résultat étant composé uniquement d'hexaèdres.</figcaption></figure>

<figure><img src="image_12.png" /><figcaption>FIG. 10 – Deux plans P1 et P2 intersectent un hexaèdre laissant cinq nœuds à l'intérieur et trois à l'extérieur (à gauche). L'étoilement est appliqué et les nœuds de la nouvelle surface ainsi créés reçoivent leur objectif : un des plans ou l'arête selon la nature de leur intersection génératrice (au centre). Enfin ces nœuds sont projetés sur la surface réelle (à droite).</figcaption></figure>
## 3.9 L'implémentation

L'implémentation de la méthode se présente sous la forme d'une simple commande en ligne à laquelle l'utilisateur doit fournir le nom du fichier à mailler et optionnellement les tailles minimales et maximales des mailles ainsi que le seuil angulaire au delà duquel une arête sera considérée comme vive. Le fonctionnement est donc totalement automatisé et aucune connaissance en maillage n'est donc requise.

Comme la plupart des algorithmes basés sur octree, la consommation des ressources mémoire et temps processeur est assez faible. La vitesse globale (toutes les phases y compris les entrées-sorties) est d'environ 700.000 hexaèdres par minute sur un Pentium4 à 2,8 ghz et l'occupation mémoire est de 200 octets par élément (1 go = 5 milions d'hexaèdres).

## 3.10 Conclusion

La méthode proposée permet de générer automatiquement des maillages purement hexaédriques et conformes dont les tailles sont adaptées à la géométrie. Par contre le respect des angles vifs laisse encore à désirer. Les pièces étudées en mecanique des structures comportant souvent des angles droits sont assez bien représentées, mais les géométries issues de la mecanique des fluides (ailes et pales) sont mal maillées et nécessitent l'usage de maillages mixtes, quoique hex-dominant. Une avancée a été réalisée dans le domaine du maillage automatique mais le "saint graal" est encore loin !

# 4 Exemples
<figure><img src="image_13.png" /></figure>

<figure><img src="image_14.png" /><figcaption>FIG. 11 – Pièce blech maillée en 74.610 éléments. Les petites grappes d'éléments près des arêtes vives servent à résoudre le problème posé par certains quadrangles de surface ayant trois points alignés car projetés sur la même arête vive ce qui entrainerait un élément dégénéré.</figcaption></figure>
<figure><img src="image_15.png" /></figure>

<figure><img src="image_16.png" /><figcaption>FIG. 12 – Maillage de la pièce shuttle en 864.960 éléments du fait de la très faible épaisseur de certains détails (agrandissement sur la figure du bas).</figcaption></figure>
<figure><img src="image_17.png" /><figcaption>FIG. 13 – Agrandissements de la tête d'un dragon maillée à des résolutions différentes (à l'aide des paramètres spécifiants les tailles minimales et maximales). Les trois versions contiennent respectivement 147.880, 664.480 et 2.386.308 éléments.</figcaption></figure>
<figure><img src="image_18.png" /><figcaption>FIG. 14 – Bloc moteur (origine Honda Motor Japan) maillé avec une taille constante ce qui améliore la qualité mais augmente le nombre d'éléments : 1.727.200.</figcaption></figure>
<figure><img src="image_19.png" /><figcaption>FIG. 15 – Vue en coupe des patterns permettant de résoudre le problème des trois points alignés (en haut). La présente solution est loin d’être satisfaisante et d’autres sont envisagées. Vue en coupe des éléments de transition de tailles crées par l’étape de conformisation (en bas).</figcaption></figure>
Références

[1] C.G. ARMSTRONG, T.S. Li & R.M. MCKEAG, Hexahedral meshing using midpoint subdivision and integer programming, *Comp. Meth. Appl. Mech. Engng*, Vol. 124, pp. 171-193, 1995.

[2] C.G. ARMSTRONG & M.A. PRICE, Mat and associated technologies for structured meshing, *ECCOMAS*, 2000.

[3] T. BLACKER, Meeting the challenge for automated conformal hexahedral meshing, *IMR 9*, pp. 11-19, 2000.

[4] N.A. CALVO & S.R. IDELSOHN, All-hexahedral element meshing : Generation of the dual mesh by recurrent subdivision, *Comp. Meth. Appl. Mech. Engng*, Vol. 182, pp. 371-378, 2000.

[5] M. DELANAYE, A. OATEL, B. LÉONARD & CH. HIRSH, Automatic unstructured hexahedral grid generation and flow simulation, *ECCOMAS*, 2001.

[6] G. DHONT, A new automatic hexahedral mesher based on cutting, *Int Jour Numer Meth Eng*, Vol 50, pp 2109-2126, 2001.

[7] N.T. FOLWELL & S.A. MITCHELL, Reliable whisker weaving via curve contraction, *IMR 7*, pp. 365-378, 1998.

[8] P.J. FREY & L. MARÉCHAL, Fast adaptive quadtree mesh generation, *IMR 7*, pp. 211-224, 1998.

[9] P.J. FREY & P.L. GEORGE, Mesh Generation, *Hermes Science publishing*, chapter 5, 1999.

[10] M. LAI, S. BENZLEY & D. WHITE, Automated hexahedral mesh generation by generalized multiple source to multiple target sweeping, *Int. J. Numer. Meth. Engng*, Vol. 49, pp. 261-275, 2000.

[11] L. MARÉCHAL, A new approach to octree hexahedral meshing, *IMR 10*, pp. 209-221, 2001.

[12] M. MÜLLER-HANNEMANN, Hexahedral mesh generation by successive dual cycle elimination, *IMR 7*, pp. 379-393, 1998.

[13] S.J. OWEN & S. SAIGAL, H-Morph an indirect approach to advancing front hex meshing, *Int. J. Numer. Meth. Engng*, Vol. 49, pp. 289-312, 2000.

[14] A. SHEFFER, A. RAPPOPORT & M. BERCOVIER, Hexahedral mesh generation using the embedded Voronoï graph, *IMR 7*, pp. 348-364, 1998.

[15] A. SHEFFER & M. BERCOVIER, Hexahedral meshing of non-linear volumes using Voronoï faces and edges, *Int. J. Numer. Meth. Engng*, Vol. 49, pp. 329-351, 2000.

[16] M.A. YERRY & M.S.SHEPHARD, A modified-quadtree approach to finite element mesh generation, *IEEE Computer Graphics Appl.*, Vol. 3, pp. 39-46, 1983.

[17] M.S. SHEPHARD & M.K. GEORGES, Automatic three-dimensional mesh generation by the finite octree technique, *SCOREC Report n° 1*, 1991.

[18] R. SCHNEIDERS & R. BÜNTEN, Automatic generation of hexahedral finite element meshes, *Computer Aided Geometric Design*, Vol. 12, pp. 693-707, 1995.

[19] R. SCHNEIDERS, Octree-based hexahedral mesh generation, *Int. J. of Comp. Geom. & Applications*, Vol. 10, n° 4, pp. 383-398, 2000.

[20] R. TAGHAVI, Automatic, parallel and fault tolerant mesh generation from CAD, *Engng. Comp*, Vol. 12, pp. 178-185, 1996.

[21] K-F. TCHON, Octree-based hexahedral mesh generation for viscous flow simulation, *American Institute of Aeronautics and Astronautics*, 1997.

[22] J.C. VASSBERG, Multi-block mesh extrusion driven by a globally elliptic system, *Int. J. Numer. Meth. Engng*, Vol. 49, pp. 3-15, 2000.