Maillage (structure de données)

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir Maillage et Mesh (objet).

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.

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.

Éléments d'un maillage[modifier | modifier le code]

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[modifier | modifier le code]

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êtes 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[modifier | modifier le code]

Les maillages étant une structure très répandue en infographie, on trouve de nombreux formats de fichiers pour les stocker :

Voir aussi[modifier | modifier le code]

Liens internes[modifier | modifier le code]

Liens externes[modifier | modifier le code]

Références[modifier | modifier le code]

  1. Bruce Baumgart, Winged-Edge Polyhedron Representation for Computer Vision. National Computer Conference, May 1975. http://www.baumgart.org/winged-edge/winged-edge.html