Maillage polygonal - Polygon mesh
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
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 .
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:
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
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
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
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
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
- B-rep
- Opérateur d'Euler
- Hypergraphe
- Manifold (un maillage peut être multiple ou non multiple)
- Subdivision de maillage (une technique pour ajouter des détails à un maillage polygonal)
- Modélisation de polygones
- Polygoniseur
- recto
- T-spline
- Triangulation (géométrie)
- Modèle filaire
Les références
Liens externes
- Weisstein, Eric W. "Complexe simplicial" . MathWorld .
- Weisstein, Eric W. "Triangulation" . MathWorld .
- Représentation de maillage demi-arête open source OpenMesh .
- Bibliothèque de traitement de maillage de polygones