Maillage polygonal - Polygon mesh

Exemple de maillage triangulaire low poly représentant un dauphin

En infographie 3D et en modélisation solide , un maillage polygonal est un ensemble de sommets ,bord setface squi définit la forme d'unobjetpolyédrique. Les faces sont généralement constituées detriangles(triangle mesh), dequadrilatères(quads), ou d'autrespolygones convexessimples(n-gons), puisque cela simplifie lerendu, mais peuvent aussi être plus généralement composées depolygones concaves, voire de polygones troués.

L'étude des maillages polygonaux est un vaste sous-domaine de l'infographie (en particulier de l'infographie 3D) et de la modélisation géométrique . Différentes représentations de maillages polygonaux sont utilisées pour différentes applications et objectifs. La variété d'opérations effectuées sur les maillages peut inclure : la logique booléenne , le lissage , la simplification et bien d'autres. Des algorithmes existent également pour le lancer de rayons , la détection de collision et la dynamique des corps rigides avec des maillages polygonaux. Si les bords du maillage sont rendus à la place des faces, le modèle devient un modèle filaire .

Les maillages volumétriques se distinguent des maillages polygonaux en ce qu'ils représentent explicitement à la fois la surface et le volume d'une structure, tandis que les maillages polygonaux ne représentent explicitement que la surface (le volume est implicite).

Plusieurs méthodes existent pour la génération de maillage , dont l' algorithme des cubes de marche .

Éléments

Éléments de modélisation de maillage polygonal.

Les objets créés avec des maillages polygonaux doivent stocker différents types d'éléments. Ceux-ci incluent les sommets, les arêtes, les faces, les polygones et les surfaces. Dans de nombreuses applications, seuls les sommets, les arêtes et les faces ou les polygones sont stockés. Un moteur de rendu peut prendre en charge uniquement les faces à 3 côtés, les polygones doivent donc être construits à partir de plusieurs d'entre eux, comme indiqué ci-dessus. Cependant, de nombreux moteurs de rendu prennent en charge les quads et les polygones à bords supérieurs, ou sont capables de convertir des polygones en triangles à la volée, ce qui rend inutile le stockage d'un maillage sous une forme triangulée .

sommet
Une position (généralement dans l'espace 3D) ainsi que d'autres informations telles que la couleur, le vecteur normal et les coordonnées de texture.
bord
Une connexion entre deux sommets.
visage
Un ensemble fermé d'arêtes, dans lequel une face triangulaire a trois arêtes et une face quadruple a quatre arêtes. Un polygone est un ensemble coplanaire de faces. Dans les systèmes qui prennent en charge les faces multi-faces, les polygones et les faces sont équivalents. Cependant, la plupart du matériel de rendu ne prend en charge que les faces à 3 ou 4 côtés, les polygones sont donc représentés comme plusieurs faces. Mathématiquement, un maillage polygonal peut être considéré comme une grille non structurée ou un graphe non orienté, avec des propriétés supplémentaires de géométrie, de forme et de topologie.
surfaces
Plus souvent appelés groupes de lissage , ils sont utiles, mais pas obligatoires pour regrouper les régions lissées. Considérez un cylindre avec des bouchons, comme une canette de soda. Pour un ombrage régulier des côtés, toutes les normales de surface doivent pointer horizontalement à l'opposé du centre, tandis que les normales des capuchons doivent pointer vers le haut et vers le bas. Rendus sous la forme d'une seule surface ombrée de Phong , les sommets de pli auraient des normales incorrectes. Ainsi, un moyen de déterminer où arrêter le lissage est nécessaire pour grouper les parties lisses d'un maillage, tout comme les polygones groupent les faces à 3 côtés. Au lieu de fournir des surfaces/groupes de lissage, un maillage peut contenir d'autres données pour calculer les mêmes données, telles qu'un angle de division (les polygones avec des normales au-dessus de ce seuil sont automatiquement traités comme des groupes de lissage séparés ou une technique telle que la division ou le chanfreinage est automatiquement appliqué au bord entre eux). De plus, les maillages à très haute résolution sont moins sujets aux problèmes qui nécessiteraient des groupes de lissage, car leurs polygones sont si petits qu'ils n'en ont pas besoin. De plus, une autre alternative existe dans la possibilité de détacher simplement les surfaces elles-mêmes du reste du maillage. Les moteurs de rendu n'essaient pas de lisser les bords des polygones non contigus.
groupes
Certains formats de maillage contiennent des groupes , qui définissent des éléments distincts du maillage et sont utiles pour déterminer des sous-objets distincts pour l' animation squelettique ou des acteurs distincts pour l'animation non squelettique.
matériaux
En général, les matériaux seront définis, permettant à différentes parties du maillage d'utiliser différents shaders lors du rendu.
Coordonnées UV
La plupart des formats de maillage prennent également en charge une certaine forme de coordonnées UV qui sont une représentation 2D distincte du maillage "déplié" pour montrer quelle partie d'une carte de texture bidimensionnelle appliquer aux différents polygones du maillage. Il est également possible que les maillages contiennent d'autres informations d' attribut de sommet telles que la couleur, les vecteurs tangents, les cartes de poids pour contrôler l' animation , etc. (parfois également appelées canaux ).

Représentations

Les maillages de polygones peuvent être représentés de différentes manières, en utilisant différentes méthodes pour stocker les données de sommet, d'arête et de face. Ceux-ci inclus:

Maillages face-sommet
Une simple liste de sommets et un ensemble de polygones qui pointent vers les sommets qu'il utilise.
Bord ailé
dans lequel chaque arête pointe vers deux sommets, deux faces et les quatre arêtes (dans le sens horaire et antihoraire) qui les touchent. Les mailles à bords ailés permettent une traversée dans le temps constante de la surface, mais avec des exigences de stockage plus élevées.
Maillages demi-bords
Similaire aux maillages à bords ailés, sauf que seule la moitié des informations de traversée des bords sont utilisées. (voir OpenMesh )
Maillages à quatre bords
qui stockent les arêtes, les demi-arêtes et les sommets sans aucune référence aux polygones. Les polygones sont implicites dans la représentation, et peuvent être trouvés en parcourant la structure. Les besoins en mémoire sont similaires aux maillages demi-arête.
Tables d'angle
qui stockent les sommets dans une table prédéfinie, de sorte que la traversée de la table définit implicitement des polygones. Il s'agit essentiellement du ventilateur triangulaire utilisé dans le rendu graphique matériel. La représentation est plus compacte et plus efficace pour récupérer des polygones, mais les opérations de changement de polygones sont lentes. De plus, les tables de coins ne représentent pas complètement les maillages. Plusieurs tables d'angle (éventails triangulaires) sont nécessaires pour représenter la plupart des maillages.
Maillages sommet-sommet
Un maillage " VV " ne représente que des sommets, qui pointent vers d'autres sommets. Les informations de bord et de face sont implicites dans la représentation. Cependant, la simplicité de la représentation ne permet pas d'effectuer de nombreuses opérations efficaces sur les maillages.

Chacune des représentations ci-dessus a des avantages et des inconvénients particuliers, discutés plus en détail dans Smith (2006). Le choix de la structure des données est régi par l'application, les performances requises, la taille des données et les opérations à effectuer. Par exemple, il est plus facile de traiter des triangles que des polygones généraux, en particulier en géométrie computationnelle . Pour certaines opérations il est nécessaire d'avoir un accès rapide à des informations topologiques telles que des arêtes ou des faces voisines ; cela nécessite des structures plus complexes telles que la représentation du bord ailé. Pour le rendu matériel, des structures simples et compactes sont nécessaires ; ainsi, la table d'angle (ventilateur triangulaire) est généralement intégrée dans les API de rendu de bas niveau telles que DirectX et OpenGL .

Maillages sommet-sommet

Figure 2. Maillages sommet-sommet

Les maillages sommet-sommet représentent un objet comme un ensemble de sommets connectés à d'autres sommets. C'est la représentation la plus simple, mais elle n'est pas largement utilisée car les informations de face et de bord sont implicites. Ainsi, il est nécessaire de parcourir les données afin de générer une liste de faces pour le rendu. De plus, les opérations sur les arêtes et les faces ne sont pas faciles à réaliser.

Cependant, les maillages VV bénéficient d'un petit espace de stockage et d'un morphing efficace de la forme. La figure ci-dessus montre une boîte à quatre côtés représentée par un maillage VV. Chaque sommet indexe ses sommets voisins. Notez que les deux derniers sommets, 8 et 9 en haut et en bas au centre de la "boîte-cylindre", ont quatre sommets connectés au lieu de cinq. Un système général doit être capable de gérer un nombre arbitraire de sommets connectés à un sommet donné.

Pour une description complète des maillages VV, voir Smith (2006).

Maillages face-sommet

Figure 3. Maillages face-sommet

Les maillages face-sommet représentent un objet comme un ensemble de faces et un ensemble de sommets. Il s'agit de la représentation maillée la plus largement utilisée, étant l'entrée généralement acceptée par le matériel graphique moderne.

Les maillages face-sommet améliorent le maillage VV pour la modélisation en ce sens qu'ils permettent une recherche explicite des sommets d'un visage et des faces entourant un sommet. La figure ci-dessus montre l'exemple "box-cylindre" en tant que maillage FV. Vertex v5 est mis en surbrillance pour montrer les faces qui l'entourent. Notez que, dans cet exemple, chaque face doit avoir exactement 3 sommets. Cependant, cela ne signifie pas que chaque sommet a le même nombre de faces environnantes.

Pour le rendu, la liste des visages est généralement transmise au GPU sous la forme d'un ensemble d'indices de sommets, et les sommets sont envoyés sous forme de structures position/couleur/normales (dans la figure, seule la position est donnée). Cela présente l'avantage que les changements de forme, mais pas de géométrie, peuvent être mis à jour dynamiquement en renvoyant simplement les données de sommet sans mettre à jour la connectivité des faces.

La modélisation nécessite une traversée facile de toutes les structures. Avec les maillages face-sommet, il est facile de trouver les sommets d'une face. De plus, la liste des sommets contient une liste des faces connectées à chaque sommet. Contrairement aux maillages VV, les faces et les sommets sont explicites, donc la localisation des faces et des sommets voisins est un temps constant. Cependant, les arêtes sont implicites, donc une recherche est toujours nécessaire pour trouver toutes les faces entourant une face donnée. D'autres opérations dynamiques, telles que le fractionnement ou la fusion d'une face, sont également difficiles avec les maillages face-sommet.

Maille ailée

Figure 4. Maillages à bords ailés

Introduits par Baumgart en 1975, les maillages à arêtes ailées représentent explicitement les sommets, les faces et les arêtes d'un maillage. Cette représentation est largement utilisée dans les programmes de modélisation pour offrir la plus grande flexibilité dans la modification dynamique de la géométrie du maillage, car les opérations de division et de fusion peuvent être effectuées rapidement. Leur principal inconvénient réside dans les besoins de stockage importants et la complexité accrue en raison du maintien de nombreux index. Une bonne discussion sur les problèmes de mise en œuvre des maillages Winged-edge peut être trouvée dans le livre Graphics Gems II .

Les maillages à arêtes ailées résolvent le problème de la traversée d'un bord à l'autre et fournissent un ensemble ordonné de faces autour d'un bord. Pour tout front donné, le nombre de fronts sortants peut être arbitraire. Pour simplifier cela, les maillages à bords ailés ne fournissent que quatre bords, les plus proches dans le sens des aiguilles d'une montre et dans le sens inverse à chaque extrémité. Les autres arêtes peuvent être parcourues de manière incrémentale. L'information pour chaque bord ressemble donc à un papillon, d'où des maillages "à bord ailé". La figure ci-dessus montre le "cylindre-boîte" sous la forme d'un maillage à bord ailé. Les données totales pour une arête se composent de 2 sommets (extrémités), 2 faces (de chaque côté) et 4 arêtes (arête ailée).

Le rendu des maillages à bords ailés pour le matériel graphique nécessite la génération d'une liste d'index de visage. Cela n'est généralement effectué que lorsque la géométrie change. Les maillages à arêtes ailées sont parfaitement adaptés à la géométrie dynamique, telle que les surfaces de subdivision et la modélisation interactive, car des modifications du maillage peuvent se produire localement. La traversée à travers le maillage, comme cela pourrait être nécessaire pour la détection de collision, peut être accomplie efficacement.

Voir Baumgart (1975) pour plus de détails.

Rendu des maillages dynamiques

Les maillages à arêtes ailées ne sont pas la seule représentation qui permet des modifications dynamiques de la géométrie. Une nouvelle représentation qui combine des maillages à arêtes ailées et des maillages face-sommet est le maillage dynamique de rendu , qui stocke explicitement à la fois les sommets d'une face et les faces d'un sommet (comme les maillages FV) et les faces et sommets d'une arête ( comme bord ailé).

Les maillages dynamiques de rendu nécessitent un peu moins d'espace de stockage que les maillages à bord ailé standard et peuvent être directement rendus par le matériel graphique puisque la liste des faces contient un index de sommets. De plus, le parcours de sommet à face est explicite (temps constant), tout comme de face à sommet. Les maillages RD ne nécessitent pas les quatre arêtes sortantes puisque celles-ci peuvent être trouvées en parcourant d'arête à face, puis de face à arête voisine.

Les maillages RD bénéficient des fonctionnalités des maillages à bords ailés en permettant la mise à jour dynamique de la géométrie.

Voir Tobler & Maierhofer ( WSCG 2006) pour plus de détails.

Résumé de la représentation du maillage

Opération Sommet-sommet Face-sommet Bord ailé Rendu dynamique
VV Tous les sommets autour du sommet Explicite V → f1, f2, f3, ... → v1, v2, v3, ... V → e1, e2, e3, ... → v1, v2, v3, ... V → e1, e2, e3, ... → v1, v2, v3, ...
EF Toutes les arêtes d'un visage F(a,b,c) → {a,b}, {b,c}, {a,c} F → {a,b}, {b,c}, {a,c} Explicite Explicite
VF Tous les sommets d'une face F(a,b,c) → {a,b,c} Explicite F → e1, e2, e3 → a, b, c Explicite
VF Toutes les faces autour d'un sommet Recherche de paires Explicite V → e1, e2, e3 → f1, f2, f3, ... Explicite
VE Toutes les arêtes autour d'un sommet V → {v,v1}, {v,v2}, {v,v3}, ... V → f1, f2, f3, ... → v1, v2, v3, ... Explicite Explicite
EF Les deux faces d'une arête Comparer la liste Comparer la liste Explicite Explicite
VE Les deux sommets d'une arête E(a,b) → {a,b} E(a,b) → {a,b} Explicite Explicite
Flook Trouver un visage avec des sommets donnés F(a,b,c) → {a,b,c} Définir l'intersection de v1,v2,v3 Définir l'intersection de v1,v2,v3 Définir l'intersection de v1,v2,v3
Taille de stockage V*moy(V,V) 3F + V*moy (F,V) 3F + 8E + V*moy (E,V) 6F + 4E + V*moy (E,V)
Exemple avec 10 sommets, 16 faces, 24 arêtes :
10 * 5 = 50 3*16 + 10*5 = 98 3*16 + 8*24 + 10*5 = 290 6*16 + 4*24 + 10*5 = 242
Figure 6 : résumé des opérations de représentation du maillage

Dans le tableau ci-dessus, explicite indique que l'opération peut être effectuée en temps constant, car les données sont directement stockées ; list compare indique qu'une comparaison de liste entre deux listes doit être effectuée pour accomplir l'opération ; et la recherche par paire indique qu'une recherche doit être effectuée sur deux indices. La notation avg(V,V) signifie le nombre moyen de sommets connectés à un sommet donné ; avg(E,V) signifie le nombre moyen d'arêtes connectées à un sommet donné, et avg(F,V) est le nombre moyen de faces connectées à un sommet donné.

La notation "V → f1, f2, f3, ... → v1, v2, v3, ..." décrit qu'un parcours à travers plusieurs éléments est nécessaire pour effectuer l'opération. Par exemple, pour obtenir "tous les sommets autour d'un sommet V donné" en utilisant le maillage face-sommet, il faut d'abord trouver les faces autour du sommet V donné en utilisant la liste des sommets. Ensuite, à partir de ces faces, utilisez la liste des faces pour trouver les sommets qui les entourent. Notez que les maillages à bord ailé stockent explicitement presque toutes les informations et que les autres opérations parcourent toujours le bord en premier pour obtenir des informations supplémentaires. Les maillages sommet-sommet sont la seule représentation qui stocke explicitement les sommets voisins d'un sommet donné.

Au fur et à mesure que les représentations du maillage deviennent plus complexes (de gauche à droite dans le résumé), la quantité d'informations explicitement stockées augmente. Cela donne un temps plus direct et constant, un accès à la traversée et à la topologie de divers éléments, mais au prix d'une surcharge et d'un espace accrus pour maintenir correctement les indices.

La figure 7 montre les informations de connectivité pour chacune des quatre techniques décrites dans cet article. D'autres représentations existent également, telles que les demi-tables et les tables d'angle. Ce sont toutes des variantes de la façon dont les sommets, les faces et les arêtes s'indexent les uns les autres.

En règle générale, les maillages face-sommet sont utilisés chaque fois qu'un objet doit être rendu sur du matériel graphique qui ne modifie pas la géométrie (connectivité), mais peut se déformer ou modifier la forme (positions des sommets) comme le rendu en temps réel d'objets statiques ou de morphing . Les maillages à arêtes ailées ou dynamiques de rendu sont utilisés lorsque la géométrie change, comme dans les packages de modélisation interactifs ou pour le calcul des surfaces de subdivision. Les maillages sommet-sommet sont idéaux pour des changements efficaces et complexes de géométrie ou de topologie tant que le rendu matériel n'est pas un problème.

Autres représentations

Maillages de streaming
stocker les faces de manière ordonnée, mais indépendante, afin que le maillage puisse être transmis par morceaux. L'ordre des faces peut être spatial, spectral ou basé sur d'autres propriétés du maillage. Les maillages de streaming permettent de rendre un très grand maillage même lorsqu'il est encore en cours de chargement.
Maillages progressifs
transmettre les données de sommet et de face avec des niveaux de détail croissants. Contrairement aux maillages en continu , les maillages progressifs donnent la forme globale de l'objet entier, mais à un faible niveau de détail. Des données supplémentaires, de nouvelles arêtes et faces, augmentent progressivement le détail du maillage.
Maillages normaux
transmettre des changements progressifs à un maillage sous la forme d'un ensemble de déplacements normaux à partir d'un maillage de base. Avec cette technique, une série de textures représentent les modifications incrémentales souhaitées. Les maillages normaux sont compacts, car une seule valeur scalaire est nécessaire pour exprimer le déplacement. Cependant, la technique nécessite une série complexe de transformations pour créer les textures de déplacement.

Formats de fichiers

Il existe de nombreux formats de fichiers différents pour stocker les données de maillage polygonal. Chaque format est plus efficace lorsqu'il est utilisé aux fins prévues par son créateur. Certains de ces formats sont présentés ci-dessous :

Suffixe de fichier Nom du format Organisation(s) Programmes) La description
.cru Maille brute Inconnu Divers Format ouvert, ASCII uniquement. Chaque ligne contient 3 sommets, séparés par des espaces, pour former un triangle, comme ceci : X1 Y1 Z1 X2 Y2 Z2 X3 Y3 Z3
.mélange Format de fichier de mélangeur Fond de teint Blender Mélangeur 3D Open source, format binaire uniquement
.fbx Format Autodesk FBX Autodesk Divers Propriétaire. Des spécifications binaires et ASCII existent.
.3ds Fichier 3ds Max Autodesk 3ds Max Un format commun mais obsolète avec des limites strictes de 16 bits sur le nombre de sommets et de faces. Ni standardisé ni bien documenté, mais était autrefois une "norme de facto" pour l'échange de données.
.dae Échange d'actifs numériques (COLLADA) Sony Computer Entertainment , Groupe Khronos N / A Stands pour " COLLA borative D esign A ctivité". Un format universel conçu pour éviter les incompatibilités.
.dgn Fichier MicroStation Systèmes Bentley MicroStation Il existe deux formats de fichiers dgn : pré-version 8 et version 8 (V8)
.3dm Fichier Rhinocéros Robert McNeel & Associés Rhinocéros 3D
.dxf , .dwg Format d'échange de dessin Autodesk AutoCAD
.obj Front d'onde OBJ Technologies de front d'onde Divers Format ASCII décrivant la géométrie 3D. Les sommets de toutes les faces sont ordonnés dans le sens inverse des aiguilles d'une montre, ce qui rend implicites les normales de facette. Les normales lisses sont spécifiées par sommet.
.pli Format de fichier polygone Université de Stanford Divers Binaire et ASCII
.pmd Données Polygon Movie Maker Yu Higuchi MikuMikuDanse Format de fichier binaire propriétaire pour stocker la géométrie du modèle humanoïde avec des informations sur le gréement, les matériaux et la physique.
.stl Format de stéréolithographie Systèmes 3D Beaucoup Format binaire et ASCII conçu à l'origine pour aider à la CNC .
.amf Format de fichier de fabrication additive ASTM International N / A Comme le format STL, mais avec une prise en charge native supplémentaire des couleurs, des matériaux et des constellations.
.wrl Langage de modélisation de réalité virtuelle Consortium Web3D Navigateurs Web Norme ISO 14772-1:1997
.wrz VRML compressé Consortium Web3D Navigateurs Web
.x3d, .x3db, .x3dv 3D extensible Consortium Web3D Navigateurs Web Basé sur XML, open source, libre de droits, extensible et interopérable ; prend également en charge les informations sur la couleur, la texture et la scène. Norme ISO 19775/19776/19777
.x3dz, .x3dbz, .x3dvz Binaire compressé X3D Consortium Web3D Navigateurs Web
.c4d Fichier cinéma 4D MAXON CINÉMA 4D
.lwo Fichier objet 3D LightWave NewTek LightWave 3D
.smb SCOREC apf SCORE RPI PUMI Maillages 3D non structurés adaptatifs parallèles open source pour les flux de travail de simulation basés sur PDE.
.msh Maillage Gmsh Développeurs GMsh Projet GMsh Open source, fournissant une description de maillage ASCII pour les éléments linéaires et polynomialement interpolés en 1 à 3 dimensions.
.engrener OGRE XML Équipe de développement OGRE OGRE, purebase Open source. Format binaire (.mesh) et ASCII (.mesh.xml) disponible. Inclut des données pour l'animation de sommet et l' animation de cible Morph (blendshape). Données d' animation squelettique dans un fichier séparé (.squelette).
.veg Maillage tétraédrique Vega FEM Jernej Barbic Véga FEM Open source. Stocke un maillage tétraédrique et ses propriétés matérielles pour la simulation FEM. Formats ASCII (.veg) et binaire (.vegb) disponibles.
. z3d Z3d Oleg Melachenko Modeleur Zanoza -
.vtk maillage VTK VTK , Kitware VTK , Paraview Format ouvert, ASCII ou binaire contenant de nombreux champs de données différents, notamment des données ponctuelles, des données de cellule et des données de champ.
.l4d dessin LAI4D Laboratoire d'Intelligence Artificielle pour le Design LAI4D Format de données ASCII qui décrit une arborescence hiérarchique d'entités.

Voir également

Les références

Liens externes