Maillage (structure de données)
Un maillage (en anglais : mesh) est une structure de données géométriques permettant de représenter des subdivisions de surface à l'aide d'un ensemble de polygones. Les maillages sont particulièrement utilisés en infographie, pour représenter des surfaces, ou en modélisation, pour discrétiser un espace continu (par exemple pour la méthode des éléments finis ou la mécanique des fluides numérique).
Un maillage est constitué de sommets, connectés les uns aux autres par des faces ou facettes de forme polygonale. Lorsque toutes les faces sont des triangles, on parle de maillage triangulaire (trimesh), ou de triangulation selon les domaines. Les maillages par quadrilatères sont aussi très courants. En 3 dimensions, il est aussi possible d'utiliser des maillages volumiques, qui relient les sommets par des tétraèdres, des hexaèdres (cuboïdes) et des prismes.
Éléments d'un maillage
Une structure de données représentant un maillage doit stocker plusieurs types d'éléments : des sommets, des arêtes, des faces.
Les sommets sont représentés par des points du plan ou de l'espace, et peuvent être munis de propriétés additionnelles : couleur, normales pour l'affichage, par exemple. Les arêtes sont des connexions entre deux sommets, et sont situés sur la frontière d'une face. Les faces sont des polygones du plan ou de l'espace, dont les sommets et les arêtes appartiennent au maillage. Les faces peuvent aussi être pourvues de propriétés telles que leur couleur ou leur transparence pour l'affichage.
Représentation informatique des maillages
Il existe plusieurs possibilités pour représenter les maillages, ayant chacune leurs avantages et inconvénients. Le choix se fait en termes d'occupation mémoire, de requête topologique (parcourir les voisins d'un sommet...), et de facilité de modification (insertion/suppression d'éléments).
- Face-Sommets : chaque face polygonale stocke un tableau d'indices de sommets
- Quad-edges : on se focalise sur les arêtes, qui contiennent une référence vers les sommets source et destination, ainsi que vers les 2 faces adjacentes.
- Winged-edge : chaque arête contient des références vers les sommets sources et destination, ainsi que vers les winged-edge voisins sur les faces gauche et droite. On peut se passer du tableau de faces, qui peut être déduit en parcourant les winged-edges. Voir Baumgart (1975) pour plus de détails[1].
- Half-edge : assez similaires aux winged-edge, mais seule la moitié des informations est stockée, l'autre moitié étant déduite d'un half-edge jumeau
Formats de fichier
Les maillages étant une structure très répandue en infographie, on trouve de nombreux formats de fichiers pour les stocker :
Voir aussi
Liens internes
Liens externes
- Les facettes du maillage et ces surfaces qui nous entourent sur Interstices, la revue de l'INRIA.
Références
- Bruce Baumgart, Winged-Edge Polyhedron Representation for Computer Vision. National Computer Conference, May 1975. http://www.baumgart.org/winged-edge/winged-edge.html