Triangulation d'une surface
Pour les articles homonymes, voir Triangulation (homonymie).
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.
Démarche[modifier | modifier le code]
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[modifier | modifier le code]
-
Triangulation : cylindre, surface x4 + y4 + z4 = 1 -
Triangulation : cylindre, surface x4 + y4 + z4 = 1, image POV-Ray
-
Tore triangulé par la marching method -
Tore polygonisé par la cutting cube method
Références[modifier | modifier le code]
- M. Schmidt: Cutting Cubes – visualizing implicit surfaces by adaptive polygonization. Visual Computer (1993) 10, pp. 101–115
- J. Bloomenthal: Polygonization of implicit surfaces, Computer Aided Geometric Design (1988), pp. 341–355
- E. Hartmann: Geometry and Algorithms for COMPUTER AIDED DESIGN, p. 81
- E. Hartmann: A marching method for the triangulation of surfaces, The Visual Computer (1998), 14, pp. 95–108
- S. Akkouche & E Galin: Adaptive Implicit Surface Polygonization Using Marching Triangles, COMPUTER GRAPHICS forum (2001), Vol. 20, pp. 67–80
Voir aussi[modifier | modifier le code]
Articles connexes[modifier | modifier le code]
- Conception assistée par ordinateur
- Génération de maillage
- Tessellation (infographie) (en)
- Marching cubes
- Triangulation d'un ensemble de points
Liens externes[modifier | modifier le code]
- Tasso Karkanis & A. James Stewart: Curvature-Dependent Triangulation of Implicit Surfaces [1]
