# Maillage et adaptation par décomposition en domaines quasi-développables

Alain Rassineux, Piotr Breitkopf, Pierre Villon

► To cite this version:

Alain Rassineux, Piotr Breitkopf, Pierre Villon. Maillage et adaptation par décomposition en domaines quasi-développables. 9e Colloque national en calcul des structures, CSMA, May 2009, Giens, France. hal-01412120

HAL Id: hal-01412120

https://hal.science/hal-01412120v1

Submitted on 8 Dec 2016

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_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Maillage et adaptation par décomposition en domaines quasi-développables

A. Rassineux, P. Breitkopf, P. Villon

Laboratoire Roberval, Université de Technologie de Compiègne - CNRS UMR 6253,

Centre de Recherches de Royallieu

BP 20529 - 60205 COMPIEGNE cedex FRANCE

alain.rassineux@utc.fr, piotr.breitkopf@utc.fr, pierre.villon@utc.fr

**Résumé** – La technique que nous proposons consiste à créer une partition d'un maillage surfacique tridimensionnel en sous zones « quasi-développables » que l'on peut ensuite mailler à l'aide d'un mailleur surfacique. Le découpage en domaines utilise un algorithme frontal contrôlé par un calcul de courbure donné par approximation diffuse et par des impératifs de compacité et de distorsion. Des exemples d'adaptation de pièces industrielles montrent l'efficacité de la technique.

**Mots clés** – maillage – adaptation de maillage

## 1 Introduction

Les travaux que nous proposons entrent dans la continuité des recherches sur l'apport des méthodes sans maillage et particulièrement l'approximation diffuse pour résoudre des problèmes de maillage et d'adaptation de maillage tridimensionnels complexes

Dans un contexte industriel, les objets à modéliser sont le plus souvent représentés par un modèle CAO surfacique. Ces modèles peuvent consister en une définition sous forme de carreaux paramétrés mais on rencontre fréquemment dans l'industrie des modèles de type stéréo lithographie (STL) donnant de l'objet une représentation sous la forme d'un maillage en triangles linéaires. Le nombre de triangles nécessaires pour représenter le modèle est alors contrôlé par une erreur de corde. Ces maillages STL dont un exemple est montré Figure 1 sont de piètres modèles éléments finis mais ont néanmoins l'avantage de représenter fidèlement la géométrie. En effet, le plus souvent, le modèle est représenté par un nombre minimal de triangles, très allongés et avec des angles très faibles. La quasi-totalité des logiciels de CAO peuvent exporter ces modèles STL ce qui peut en partie expliquer pourquoi de plus en plus d'industriels souhaitent exploiter ces modèles pour en faire un maillage pour l'analyse et s'affranchir d'un modèle CAO.

L'objectif ce nos travaux est de présenter une technique de remaillage permettant de remailler, d'adapter un maillage existant et en particulier ces modèles. L'approche peut être aussi utilisée dans le cadre de remaillage suite à de grandes déformations, des propagations de fissures, des perspectives que nous comptons mettre en œuvre.
<figure><img src="image_2.png" /><figcaption>Figure 1 - Cylindre représenté par un maillage STL</figcaption></figure>

# 2 Etat de l'art

L'approche que nous proposons est intuitive et d'autres auteurs ont proposé des démarches assez proches mais d'en d'autres contextes que celui de l'adaptation de maillage.

## 2.1 Maillage par opération topologiques

Une fois que l'on sait placer de nouveaux nœuds sur la géométrie et en enlever en garantissant le contrôle de la qualité géométrique du résultat, l'étape de remaillage peut être abordée. L'approche la plus couramment utilisée[2] repose sur l'utilisation d'outils classiques de remaillage local à savoir la bascule d'arête, la subdivision d'une arête, la suppression d'une arête avec insertion, la suppression d'un point et le bougé de points. La suppression d'une arête avec insertion consiste à fusionner les deux nœuds d'une arête en un nouveau nœud situé au milieu de l'arête. La suppression d'un nœud du maillage s'obtient en remaillant le polygone formé par le contour des éléments qui partagent le nœud à supprimer. Ces outils sont utilisés d'une part dans le but de raffiner ou de grossir le maillage et d'autre part dans une phase finale afin d'améliorer la forme des éléments. Les principaux opérateurs sont montrés en Figure 2.

<figure><img src="image_3.png" /><figcaption>Figure 2 - De gauche à droite : bascule, suppression, découpage d'arête et bougé de points</figcaption></figure>

L'approche est simple à implémenter et robuste mais des difficultés subsistent :

* Le nombre d'opérations dépend du ratio entre la taille initiale et la taille cible et ainsi une grand nombre d'opérations peut être mis en œuvre pour obtenir le résultat souhaité.

* Le maillage résultat garde la trace du maillage initial dans les zones de petites tailles.

* L'ordre dans lequel les opérateurs doivent être appliqués est rarement décrit dans la littérature [1].

* Ces techniques s'avèrent inefficaces pour des maillages de très mauvaise qualité comme celui proposé sur la Figure 1.

## 2.2 Approche par paramétrage

D'autres auteurs ont proposé de mailler directement la surface par une technique de type avancée de front [3] mais l'absence de fondement théorique rend la convergence incertaine.

L'autre classe de méthode dont fait partie le maillage carreau par carreau de la CAO fait appel à un paramétrage et le maillage peut être alors effectué dans l'espace des paramètres de la surface. Le maillage dans le plan est une étape robuste, peu coûteuse et basée sur des fondements théoriques. De nombreux auteurs ont proposé des solutions pour éviter les distorsions entre l'espace réel et l'espace des paramètres[4]. En l'absence de paramétrage, ce dernier doit être crée. L'objectif est de retrouver les avantages d'une approche carreau par carreau et de contrôler la distorsion inhérente au mapping entre les coordonnées paramétriques et l'espace réel.
Parmi les méthodes dont l'objectif est de créer un paramétrage à partir d'un maillage, on distingue encore 2 classes suivant l'unicité ou la non-unicité du paramétrage. On parlera alors de segmentation en sous-domaines.

Une majeure partie de ces techniques trouvent des applications dans l'informatique graphique par exemple dans le rendu réaliste et la texture qui requièrent de minimiser le nombre de domaines et de contrôler la distorsion. Des critères basés sur une distorsion des distances, des angles ou des surfaces sont proposés et la mise à plat est obtenue par minimisation d'une fonctionnelle qui mesure l'écart entre le paramétrage proposé et le paramétrage idéal, l'isométrie qui conserve les distances entre 2 points quelconques de la surface.

Le paramétrage introduit des distorsions dans les propriétés métriques de la surface. Quand une surface est mise à plat, celles-ci interviennent dans les zones sphériques ou hyperboliques. Pour les surfaces développables (plans, cylindres, cônes par exemple), les propositions suivantes sont équivalentes

* le produit des courbures principales (courbure gaussienne) est nul

* le tenseur métrique est l'identité

* la surface peut être mise sur un plan sans distorsion

* chaque point de la surface repose sur une ligne droite

Pour les mécaniciens, le tenseur de Green-Lagrange peut être facilement utilisé pour mesurer la déformation liée au paramétrage et en particulier les distorsions en distance et en angle.

Il est clair qu'une surface fermée ne peut être mise à plat sans recouvrement et des coupes s'imposent sur le maillage à l'image de la sphère de la Figure 3(b). Le problème consiste à trouver les coupes dans le maillage qui rendent la surface modifiée topologiquement homéomorphe à un disque. Dire que deux objets sont homéomorphes revient à dire que l'on peut passer de l'un à l'autre par une déformation continue, que l'on aille dans un sens ou dans l'autre.

<figure><img src="image_4.png" /><figcaption>Figure 3 - (a) Cône déplié, (b) Mise à plat d'une sphère, des coupes doivent être opérées</figcaption></figure>

La majorité des stratégies de décomposition ont pour objectif de minimiser le nombre d'éléments du maillage. Le maillage peut être décomposé entre autres

* en zones planes iso-normales [5]

* en bandes d'éléments dessinant des lignes géodésiques équidistantes sur le maillage[6]

* en zones quasi-développables[7]

Les algorithmes utilisés font appel essentiellement

* à des méthodes itératives de type partition de Llyod[5]

* à du partitionnement hiérarchique[8]

* à de l'analyse spectrale de surface[9]

* à des algorithmes de type avancée de front, propagation[10]
## 3 Découpage en sous domaines développables

La méthode que nous proposons repose sur une technique de décomposition en sous-domaines « quasi-développables » que l'on peut ensuite mailler à l'aide d'un mailleur surfacique. A chaque étape, la distorsion du maillage est contrôlée par un critère de Green-Lagrange traduisant la déformation entre le triangle initial et le triangle déformé lors de sa mise en plan. L'approche est intuitive et a déjà été exploitée dans d'autres contextes mais l'idée n'a jamais été exploitée dans un contexte de remaillage. De nombreuses difficultés doivent être en effet résolues pour parvenir enfin à utiliser un mailleur bidimensionnel.

### 3.1 Calcul de la courbure par approximation diffuse

L'expérience montre que le processus de découpage en sous domaines peut être amélioré en contrôlant l'expansion des domaines par un critère lié à la courbure.

Les courbures principales sont calculées par approximation diffuse au milieu des arêtes du maillage[2][10].

Les travaux précédents [2][11] que nous avons présentés dans ce contexte font l'hypothèse forte qu'il existe en chaque point un repère de projection dans lequel la surface peut être représentée localement par une surface dite de Monge du type z=f(x,y) où f est une quadrique. La détermination d'un plan de projection peut s'avérer délicate même si un tel plan existe.

L'approche que nous proposons est moins restrictive et la surface d'approximation est donnée sur la forme plus générale du système d'équations (1)

$$ egin{cases} x(u,v) = P(u,v)\{\alpha_x\} \\ y(u,v) = P(u,v)\{\alpha_y\} \\ z(u,v) = P(u,v)\{\alpha_z\} \\ \text{avec } P(u,v) = \left\langle 1, u, v, \frac{u^2}{2}, uv, \frac{v^2}{2} \right\rangle \text{ et } \{\alpha_x\}, \{\alpha_y\}, \{\alpha_z\} \text{ à déterminer} \end{cases} \quad (1) $$

où (u,v) désignent les coordonnées locales de la surface construite en développant localement le maillage à l'image de la technique que nous proposons au paragraphe 3.2. Les courbures principales peuvent se déduire des équations (1). Les performances du modèle reconstruit sont illustrées avec le remaillage d'une surface développable représentée par un maillage initial grossier à gauche de la Figure 4.

<figure><img src="image_5.png" /><figcaption>Figure 4 – Remaillage (à droite) et projection sur le modèle diffus</figcaption></figure>

L'approximation peut dégénérée, le nombre de voisins s'avérer insuffisant (il en faut au moins 6) ou une forte anisotropie du maillage (Figure 1) peut nuire au calcul de la courbure locale. Dans ces cas, le calcul de la courbure se fait par approximation diffuse en déterminant la parabole d'équation $z=<1,y,y^2>\{\alpha\}$ dans un plan (y,z) normal à l'arête AB. Ceci revient à diminuer le nombre de monômes de la base.
<figure><img src="image_6.png" /><figcaption>Figure 5 - Dégénérescence de l'approximation</figcaption></figure>

## 3.2 Détermination des domaines par avancée de front

Dans un premier temps, les faces (triangles) sont triées par courbure croissante. L'objectif est de créer d'abord les domaines plans.

Par définition, la courbure d'une arête est la plus grande valeur des valeurs propres du tenseur de courbure calculé au milieu de l'arête. La courbure en un nœud est la plus grande courbure des arêtes incidentes et la courbure d'une face est la plus grande courbure des 3 arêtes du triangle.

### 3.2.1 Le schéma de progression

L'algorithme de progression est illustré en Figure 6.

<figure><img src="image_7.png" /><figcaption>Figure 6 - Progression par avancée de front</figcaption></figure>

La constitution des domaines se fait suivant un schéma itératif :

* On choisit dans la liste une face non affectée à un domaine (a) et on détermine le point de courbure minimale (b).

* On détermine les faces qui peuvent être mises à plat (b).

* Les nœuds de ces faces sont triés par courbure croissante (c)

* On choisit le nœud de courbure minimal (d) et on itère le processus

### 3.2.2 Projection autour d'un nœud

Quand le maillage est mis à plat, il est possible de conserver les distances, les angles, la surface du triangle. Dans un premier temps, nous avions intuitivement développé un algorithme d'optimisation permettant pour un nœud donné, de mettre à plat le maillage en respectant au mieux les surfaces des triangles. L'expérience a montré que cette étape ne fait que retarder les problèmes. Les meilleurs résultats ont été obtenus en conservant les distances lors de la projection. Le principe est détaillé

Figure 7.
<figure><img src="image_8.png" /><figcaption>Figure 7 – Mise à plat avec conservation des distances.</figcaption></figure>

Le maillage est mis à plat autour du nœud A. L’algorithme consiste à tourner autour du nœud A et à projeter les faces. Les figures (a) et (b) représentent le maillage dans l’espace et en figure (c) est représenté le maillage mise à plat. En

Figure 7a, la face ABC n’a pas encore été projetée. La conservation des distances se fait simplement en reportant dans le plan la projection orthogonale du nœud C. On comprend aisément que la distorsion du maillage est portée sur le dernier nœud.

### 3.2.3 Distorsion du maillage

Deux critères d’arrêt équivalents ont été utilisés. Le premier repose sur le tenseur de déformation bidimensionnel linéarisé de Green-Lagrange entre les configurations de référence et déformée. Le deuxième critère repose sur le rapport des critères de qualité du triangle dans la configuration de référence et dans la configuration déformée.

Le critère de qualité utilisé est

$$0 \le \frac{\alpha \times \rho}{L} = Q(T) \le 1 \quad (2)$$

Où ρ désigne le rayon inscrit de l’élément, L la plus grande longueur d’arête et α un coefficient de normalisation tel que la qualité d’un triangle équilatéral est 1.

### 3.2.4 Critères d’arrêt

Le processus s’arrête dès que

* La distorsion du maillage dépasse une valeur seuil (90%)

* Le rapport des courbures entre faces adjacentes dépasse une valeur seuil. L’objectif est de limiter la progression par adjacence à des zones de même courbure afin de respecter les lignes caractéristiques de la géométrie[11].

* Une surface périodique est détectée : Comme le montre la Figure 8a, le cas des surfaces périodiques est traité en limitant à 180° l’écart angulaire maximal entre les normales aux faces d’un même domaine.

* Le maillage mis à plat s’auto-intersecte Figure 8(b).

* Toutes les faces ont été affectées

Remarque : Dès qu’un des critères ci-dessus n’est pas vérifié, aucune autre face n’est introduite. Cette progression par adjacence permet à la différence de la Figure 3b d’obtenir des domaines plus compacts, de forme plus simple, un point important lors de l’étape de discrétisation des frontières des domaines. En effet, on comprend aisément que la taille du maillage dépend de la discrétisation des frontières de domaines et la création de courbes de petite taille se traduit localement par un maillage fin.

### 3.2.5 Corrections a posteriori

Pour chaque domaine, le but final est de remailler la triangulation mise à plat. Cette étape passe par l’identification des contours extérieur et éventuellement intérieurs puis par le découpage des frontières. La majorité des mailleurs bidimensionnels ne peuvent mailler que des
géométries discrètes dont les contours extérieur et intérieures n'ont pas de point commun. Dans les cas où les contours possèdent un point commun Figure 8 (c), les éléments autour du nœud commun sont exclus du domaine et réintroduit dans le processus global de détermination des domaines.

En outre, à l'issue du processus de constitution de l'ensemble des domaines, il peut s'avérer nécessaire de fusionner des domaines de petites tailles avec des domaines adjacents pour éviter qu'une petite taille de domaine n'impose localement la taille de maille.

<figure><img src="image_9.png" /><figcaption>Figure 8 – Configurations singulières - surfaces périodiques (a)– intersections (b) – géométrie non conforme (c)</figcaption></figure>

# 4 Remaillage dans le plan

## 4.1 Lissage des frontières

La première étape consiste à identifier sur le maillage les lignes caractéristiques de la géométrie.

On distingue sur la Figure 9

* les arêtes externes constituées d'arêtes du maillage reliées à un seul triangle, facilement identifiables, par exemple toutes les arêtes de la courbe (C),

* Les arêtes vives et les arêtes internes imposées par l'utilisateur : les arêtes vives peuvent être identifiées par un critère d'angle entre faces adjacentes ou par une analyse de la courbure [11],

* les arêtes entre domaines : par exemple toutes les arêtes de la courbe K entre A et B.

Des points singuliers sont déterminés par des critères d'angle entre arêtes sur les arêtes frontières, externes, imposées et vives (par exemple le point O) et à l'intersection de plus de 3 domaines (par exemple le point A).

<figure><img src="image_10.png" /><figcaption>Figure 9 – Constitution des courbes frontières</figcaption></figure>

Les courbes constituées d'arêtes externes, imposées et vives sont des splines cubiques.

En revanche, les courbes frontières des domaines peuvent avoir une allure en dents de scie comme l'illustrent Figure 10(a) et Figure 10(c) et il convient de les lisser pour éviter que la taille des arêtes n'impose localement la taille des éléments du maillage. Des courbes de Bézier[12] sont alors créées. Dans le cas de la sphère de la Figure 10 (a), toutes les courbes
créées ont ce type. On voit sur Figure 10 (b)et(d) que les courbes de Bézier corrigent parfaitement cet effet car la courbe reste dans le polygone convexe des pôles (Figure 10 (b)et(d)). Cette propriété est exploitée par la suite.

<figure><img src="image_11.png" /><figcaption>Figure 10 – Lissage des frontières par des courbes de Bézier</figcaption></figure>

## 4.2 Découpage des courbes

Les courbes sont ensuite découpées suivant une carte de taille fournie par l'utilisateur ou par l'analyse si on couple cette approche à des estimateurs d'erreurs. La carte de taille sur l'ensemble du maillage est ensuite lissée. Cette étape ne présente pas de difficultés particulières néanmoins, il arrive fréquemment que les contours s'intersectent après découpage et un contrôle s'impose. Un tel exemple est fourni sur la Figure 11(b). Le contour initial est représenté Figure 11(a). Les courbes après lissage et discrétisation sont représentées sur le maillage initial Figure 11(c).

<figure><img src="image_12.png" /><figcaption>Figure 11-Découpage des courbes de domaines</figcaption></figure>

## 4.3 Maillage dans le plan et retour à l'espace réel

Les domaines plans dont les frontières ont été découpées sont triangulés. L'étape suivante consiste à revenir aux coordonnées dans l'espace 3D. Cette étape est détaillée sur la figure 12. Un maillage dans le plan a été obtenu à partir de la mise en plan d'un ensemble de triangles dans l'espace figure 12c. Le remaillage dans le plan figure 12 (a) a été obtenu à partir du découpage des frontières du maillage mis à plat (figure 12b). Par conséquent les 2 maillages (figure 12a et figure 12b) dans le plan se superposent et un nœud du nouveau maillage plan est nécessairement dans un triangle de l'ancien maillage. A un triangle dans le plan correspond un triangle dans l'espace réel 3D. Il suffit alors de reporter les coordonnées barycentriques du point du maillage plan vers le maillage 3D pour obtenir les coordonnées du nouveau nœud.

De nouveaux points sont introduits sur les courbes. Près des frontières, les points peuvent être créés à l'extérieur du domaine triangulé notamment à cause de l'effet dent de scie. Afin de positionner ces points dans l'espace 3D à l'aide de la même technique, on détermine et on maille le polygone convexe du domaine plan[13]. La création de courbes Bézier sur les bords permet de garantir que ces nouveaux points appartiennent au convexe.
<figure><img src="image_13.png" /><figcaption>Figure 12-Mapping inverse par report des coordonnées barycentriques</figcaption></figure>

**5 Exemples**

<figure><img src="image_14.png" /><figcaption>Figure 13 – Tube cylindrique</figcaption></figure>

<figure><img src="image_15.png" /><figcaption>Figure 14 – Pièce industrielle importée au format STL</figcaption></figure>
<figure><img src="image_16.png" /><figcaption>Figure 15-Pièces industrielles importées au format STL</figcaption></figure>

Le test académique Figure 13 illustre les performances de la méthode. Le maillage initial contient exclusivement des éléments très allongés avec des rapports d'élongation supérieurs à 100. Un maillage de taille constante très régulier a été obtenu. Les pièces industrielles importées d'un format STL

Figure 14 et Figure 15 comportent de nombreux détails complexes. Cette approche a permis de mailler ces structures alors que les techniques classiques de remaillage locale par opérateurs topologiques ont échoué.

Références

[1] D.Wang1, O.Hassan, K. Morgan, N. Weatheril, Enhanced remeshing from STL files with applications to surface grid generation, Commun. Numer. Meth. Engng, 23, 227–239, 2007

[2] A. Rassineux, P. Villon, J.-M. Savignat, O. Stab, Surface remeshing by local hermite diffuse interpolation, Internat. J. Numer. Methods Eng. 49 (2000)

[3] Löhner R., Regridding surface triangulation. Journal of Computational Physics, 126, 1–10, 1996.

[4] H. Borouchaki, P.J Frey, Adaptive Triangular Quadrilateral Mesh Generation International Journal of Numerical Methods in Engineering, 41, 915-934, 1998

[5] D. Cohen-Steiner, P. Alliez, M. Desbrun. Variational shape approximation. ACM, Transactions on Graphics, 23(3), 905–914, 2004.

[6] Sifri, O., A. Sheffer, C. Gotsman, Geodesic-based Surface Remeshing. Proc. 12th International Meshing Roundtable, 189–199, 2003

[7] D Julius, V. Kraevoy, A. Sheffer, D-Charts: Quasi-Developable Mesh Segmentation, Computer Graphics Forum (Proc Eurographics 2005), 24(3), 981-990, 2005

[8] P. Sander, J. Snyder, S.J. Gortler, and H. Hoppe, “Texture Mapping Progressive Meshes,”
Proc. of SIGGRAPH 2001, 409–416, 2001

[9] K Zhou, K., Snyder J., Guo B., Shum H.-Y.: “Isocharts:. Stretch-driven mesh parametrization using spectral analysis”. In Proc. Symp. Geom. Proc.,2004.

[10] O. Sorkine, D. Cohen-Or, R. Goldenthal, D. Lischinsky, “Bounded distortion Piecewise Mesh Parameterization,” Proc. of IEEE Visualization 2002 (Vis02), IEEE Press, 355-362, 2002.

[11] C. Chappuis, A Rassineux, P. Breitkopf, P. Villon: Improving surface meshing from discrete data by feature recognition. Eng. Comput. (Lond.) 20(3), 202-209, 2004

[12] Bartels R.H., Beaty J.C., Barsky B.A., "B-Splines", Mathématiques et CAO, 6, Ed. Hermès, Paris, 1988.

[13] T. Cormen, C. Leiserson, R.Rivest, C. Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001