Méthodes de génération des maillages de surfaces 3D

Cours méthodes de génération des maillages de surfaces 3D, tutoriel & guide de travaux pratiques en pdf.

Maillage triangulaire

La représentation la plus simple d’une forme est de décrire les points caractérisant cette forme. Une représentation plus complète consiste à représenter les formes par maillage.
Un maillage est un ensemble d’éléments ou mailles dont la dimension dépend du domaine à mailler et de l’espace dans lequel se trouve ce domaine :
Linéique lorsque le domaine est une courbe ou une droite ; il peut être plongé dans un espace de dimension un, deux ou trois. Les mailles sont des segments.
Plan lorsque le domaine et l’espace sont en dimension deux ; les mailles sont des polygones.
Surfacique lorsque le domaine est en dimension deux et l’espace en dimension trois ; les mailles sont des « polygones » non forcément planaires (par exemple les quadrangles).
Volumique lorsque le domaine et l’espace sont en dimension trois : les mailles sont des polyèdres, très souvent des tétraèdre4 ou des hexaèdres5. [11]

Méthodes de génération des maillages de surfaces 3D

Les surfaces d’objets tridimensionnels ont un rôle très important dans les applications graphiques actuelles. Elles sont représentées par un maillage polyédrique.
La représentation de ces surfaces par des maillages permet de faire la compression, la visualisation et le transfert des objets 3D efficacement, pour aboutir à un tel maillage triangulaire plusieurs méthodes peuvent être utilisées.

Méthode de Hoppe

A travers une série de trois articles, Hoppe et Al, développèrent la première méthode de reconstruction de surface arbitraire à partir d’un nuage de points non structuré.
Cette approche se résume en trois phases :
Reconstruction
Cette phase de reconstruction de maillage primaire à partir d’un nuage de points se découpe en deux étapes :
· Création d’une iso-surface approximant le nuage de points : pour cela un plan tangent est estimé pour chaque point selon son voisinage, et l’iso valeur calculée en tout point de l’espace est la distance signée au plan tangent du point du nuage le plus proche.
· Génération d’un maillage à partir de cette surface via une variante de l’algorithme de générations des maillages.
Optimisation du maillage
Cette phase consiste à réduire le nombre de triangles issus de la première phase ; en équilibrant le rapport entre une représentation minimale (en terme de complexité mémoire, et donc de facettes) et une bonne approximation du nuage de points en se basant sur les technique de compression.
Génération d’une surface de subdivision
Cette dernière phase consiste à générer une surface de subdivision, minimisant l’énergie avec le maillage issu de la deuxième phase .une modification du schéma de subdivision est proposée, permettant de diminuer localement l’ordre de continuité de la surface, et de représenter les arêtes vives.
Si l’angle entre deux faces adjacentes est inférieur à un seuil prédéfini, l’arête commune est marquée comme vive, et un masque spécial de subdivision sera appliqué. Cette approche constitue le point d’entrée de la reconstruction de surface à partir d’un nuage de point non structuré.

Approches basées sur le diagramme de Voronoi

Il existe toute une famille d’algorithmes générant des surfaces explicites (le plus souvent une collection de polygones structurée) à partir de nuages de points.
Afin de générer le maillage, la plupart de ces approches commencent par estimer la topologie de l’ensemble de points à l’aide de son diagramme de Voronoï.
Le diagramme de Voronoï est un partitionnement de l’espace en cellules. Soit p un point de l’ensemble P. La cellule associée à p représente l’ensemble des points de l’espace qui sont plus proches de p que de tout autre point de P.
Le diagramme de Voronoï est habituellement utilisé en deux ou trois dimensions. Il est la structure topologique d’un nuage de points, et notamment fournit la notion de voisinage d’un point : p est voisin d’un point q de P si et seulement si leur cellules de Voronoï sont adjacentes.
Une fois le diagramme de Voronoï établie, on peut construire son dual géométrique, la Triangulation de Delaunay, comme montré sur la figure II.2. Il s’agit d’un ensemble de triangles en 2D, ou de tétraèdre en 3D. [5]
Le noyau de Delaunay est une méthode permettant d’insérer un point dans une triangulation en modifiant localement la topologie de la triangulation existante tout en maintenant le critère de Delaunay. C’est pourquoi les méthodes utilisant le noyau de Delaunay sont qualifiées d’incrémentales.
Une triangulation de Delaunay a les propriétés suivantes :
le maillage de Delaunay interpole l’ensemble des points de P ;
une arête entre deux points de P existe si et seulement si leurs cellules de Voronoï sont adjacentes ;
elle maximise l’angle minimal entre deux arêtes ayant un sommet en commun (bon équilibre du maillage) ;
le cercle circonscrit d’un triangle de Delaunay ne contient aucun autre point deP.
Figure II.2 : Diagramme de Voronoi et sa triangulation de Delaunay

Adaptation de maillages

Il arrive qu’on ne sache pas construire un maillage avec les propriétés optimales ou qu’on souhaite réutiliser un maillage dans un autre contexte que celui prévu au départ.
Dans ces cas, une adaptation est appliquée au maillage existant de manière à améliorer ses propriétés.
Il peut s’agir d’affiner le maillage là où une concentration de noeuds donnée est nécessaire, de le simplifier, par exemple pour l’adapter au point de vue, ou de modifier la position des noeuds pour améliorer la forme des éléments.

Raffinement

Le raffinement de maillage n’est autre que l’ajout de noeuds dans le maillage de manière à rendre le traitement sur le maillage plus précis.
Pour les maillages triangulaires, les méthodes de raffinement les plus connues et les plus utilisées dans le domaine de la simulation exploitent le noyau de Delaunay.

Déplacements de noeuds

La construction et le raffinement d’un maillage nécessitent la plupart du temps un post traitement car les algorithmes produisent malgré tous des défauts que les méthodes d’optimisation réduisent considérablement en peu de temps.
Ces défauts proviennent le plus souvent de la difficulté à construire de nouveaux points de manière à satisfaire au mieux des propriétés parfois contradictoires sur le maillage.
Pour améliorer le maillage, un déplacement des noeuds est alors appliqué de manière à rendre plus régulières la répartition des noeuds et, par suite, la forme des éléments.
La méthode la plus simple pour rendre la forme des éléments plus régulière, est de chercher à placer chaque sommet au barycentre de ses voisins. Chaque sommet est traité une fois, puis le processus recommence jusqu’à ce que le déplacement de chaque sommet soit inférieur à un seuil donné ou qu’un nombre d’itérations fixé à l’avance soit atteint. Le plus souvent, les points ne sont déplacés que d’une fraction de la distance entre la position actuelle et le barycentre.
Cette méthode dite du Laplacien, possède des inconvénients, dont celui de produire des éléments de mauvaise qualité voire des éléments inversés dans les régions concaves.

Simplification de maillage

Les travaux de simplification de maillage concernent majoritairement le domaine de la visualisation, où les scènes peuvent comporter de nombreux objets plus ou moins complexes.
Pour afficher rapidement une scène et permettre de s’y déplacer, le maillage est simplifié par réduction du nombre de triangles. Il existe différentes manières de simplifier un maillage. La plupart dégradent la précision d’approximation du maillage afin de réduire significativement le nombre de triangles.
Ces méthodes d’adaptation de maillage ont pour vocation de modifier un maillage existant pour qu’il satisfasse mieux un certain nombre de contraintes.

Format d’objets 3D

Pour représenter un objet 3D il faut au minimum une description :
De la topologie de l’objet, sa forme, sa taille et sa complexité.
Des attributs de représentation : couleurs, textures (nature et position), qualité photométrique de sa surface, transparence.
De ses attributs dynamiques s’il est animé : capacité de collision avec d’autres objets, articulations et contraintes, etc.
Les premiers formats standard de fait ont été des formats adaptés à la CAO6 : l’objet est défini à l’aide de facettes ou de surfaces analytiques. Il suffit de définir son origine puis les coordonnées caractéristiques des éléments dans l’espace à trois dimensions.
Actuellement, dans le monde professionnel, il n’y a pas de format unique mais plutôt des formats plus ou moins utilisés selon le type d’application.

Les différents formats des objets 3D

La plupart des modeleurs 3D savent plus ou moins bien lire (Import) et créer (Export) plusieurs formats : c’est un critère de choix important. On va citer dans ce qui suit les formats les plus répandus.

DXF (Drawing eXchange Format)

Il a été créé par la société Autodesk servant à échanger des fichiers DAO7 ou CAO entre systèmes CAO n’utilisant pas le même format de fichier natif. Il a été conçu à l’origine pour représenter les modèles 3D créés avec AutoCAD.
DXF est un format de fichier utilisé pour le transfert de données du type vecteur. Il contient de l’information pour la visualisation des données graphiques et est supporté par presque tous les logiciels graphiques. Il y a beaucoup de méthodes pour enregistrer les données des attributs des objets graphiques par le format DXF et aussi pour lier des objets DXF à des attributs externes. [17]
Dans ce format, un objet est une suite d’entités nommées et constituées de liste de points X, Y, Z. Par indexation, on constitue des facettes triangles ou des lignes qui s’appuient sur ces points.