Triangulation d'une surface

La triangulation d'une surface peut signifier :

• un réseau de triangles, qui recouvre une surface donnée partiellement ou totalement,
• la procédure de génération des points et des triangles d'un tel réseau de triangles.

Triangulation d'une surface implicite de genre 3

Triangulation de la surface paramétrique appelée selle de singe

Démarche

Cet article décrit la génération d'un réseau de triangles. Dans la bibliographie, il existe des articles qui concernent l'optimisation d'un réseau donné.

La triangulation d'une surface est importante, notamment pour :

• visualiser des surfaces, en infographie ;
• l'application de la méthode des éléments finis.

La triangulation d'une surface définie paramétriquement est réalisée simplement en triangulant la surface de définition (voir la deuxième figure, décrivant la selle de singe). Cependant, les triangles peuvent être de forme et de taille variable dans l'espace objet, posant un problème potentiel. Ceci peut être minimisé par des méthodes adaptatives qui considèrent des largeurs de pas lors de la triangulation de la surface paramétrique.

La triangulation d'une surface implicite (définie par une ou plusieurs équations) est plus difficile. Il existe essentiellement deux méthodes.

• La première méthode divise la région tridimensionnelle considérée en cubes et détermine les intersections de la surface avec les arêtes des cubes de façon à obtenir des polygones sur la surface, qui doivent être ensuite triangulés (cutting cube method)^[1],[2]. Le coût pour traiter les données est considérable.
• Le second concept, plus simple, est la marching method^[3],[4],[5]. La triangulation démarre avec un hexagone triangulé en un point de départ. Cet hexagone est ensuite entouré par de nouveaux triangles, suivant des règles données, jusqu'à ce que la surface considérée soit triangulée. Si la surface est constituée de plusieurs parties, l'algorithme doit être redémarré plusieurs fois en utilisant des points de départ appropriés.

L'algorithme du cutting cube détermine en même temps toutes les composantes de la surface au sein du cube de départ, selon les paramètres limites prescrits. Un avantage de la marching method est la possibilité de définir des boundaries (voir image).

Polygoniser une surface signifie générer un maillage polygonal.

La triangulation d'une surface ne doit pas être confondue avec la triangulation d'un plan prescrit de manière discrète par un ensemble de points. Voir triangulation de Delaunay.

Illustrations

• 
  Triangulation : cylindre, surface x⁴ + y⁴ + z⁴ = 1
• 
  Triangulation : cylindre, surface x⁴ + y⁴ + z⁴ = 1, image POV-Ray

• 
  Tore triangulé par la marching method
• 
  Tore polygonisé par la cutting cube method