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, ou des subdivisions de volume à l'aide d'un ensemble de polyèdres. 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 surfacique 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 trois 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[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.

Plus précisément :

les sommets (en anglais, vertex ou vertices) 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 (en anglais, edge) sont des connexions entre deux sommets, et sont situés sur la frontière d'une face ;
les faces (en anglais, face) 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 (en) : 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 (en) : 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.