Triangulation polygonale avec trous
https://stackoverflow.com/questions/406301
-
03-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Je cherche un algorithme ou une bibliothèque (mieux) pour décomposer un polygone en triangles. Je vais utiliser ces triangles dans une application Direct3D. Quelles sont les meilleures options disponibles?
Voici ce que j'ai trouvé jusqu'à présent:
- Notes de Ben Discoe
- FIST: Triangulation rapide de polygones à la puissance industrielle
- Je sais que la CGAL fournit une triangulation, mais je ne suis pas sûr qu'elle prenne en charge les trous.
J'apprécierais vraiment l'opinion de personnes ayant une expérience préalable dans ce domaine.
Modifier: il s’agit d’un polygone 2D.
La solution
Autres conseils
Pour vous donner davantage de choix de bibliothèques:
Polybooléen. Je n'ai jamais essayé celui-ci, mais cela semble prometteur: http: //www.complex-a5. ru / polybooléen / index.html
Général Polygon Clipper. Celui-ci fonctionne très bien dans la pratique et fait la triangulation ainsi que le découpage et les trous: http://www.cs.man.ac.uk/~toby/alan/software/
Ma recommandation personnelle: Utilisez le tesselation de GLU (OpenGL Utility Library). Le code est solide, plus rapide que GPC et génère moins de triangles. Vous n'avez pas besoin d'un OpenGL-Handle initialisé ni de quoi que ce soit pour utiliser lib.
Si vous n’aimez pas l’idée d’inclure des bibliothèques système OpenGL dans une application DirectX, il existe également une solution: il suffit de télécharger le code d’implémentation de référence SGI OpenGL et d’enlever le triangulateur. Il utilise simplement les noms OpenGL-Typedef et une main pleine d’énums. C'est tout. Vous pouvez extraire le code et créer une bibliothèque autonome en une heure ou deux.
En général, je vous conseillerais d'utiliser quelque chose qui fonctionne déjà et de ne pas commencer à écrire votre propre triangulation.
Il est tentant de lancer le vôtre si vous avez lu quelque chose à propos de l'algorithme d'écrêtage d'oreille ou de ligne de balayage, mais le fait est que les algorithmes de géométrie algorithmique sont incroyablement difficiles à écrire de manière à rester stables, à ne jamais planter et à toujours revenir un résultat significatif. Les erreurs d'arrondi numériques vont s'accumuler et vous tuer à la fin.
J'ai écrit un algorithme de triangulation en C pour la société avec laquelle je travaille. Faire fonctionner l'algorithme de base a pris deux jours. Le faire fonctionner avec toutes sortes d'entrées dégénérées prenait encore deux ans (je ne travaillais pas à plein temps dessus, mais croyez-moi, j'y ai passé plus de temps que je n'aurais dû).
CGAL a l'outil dont vous avez besoin: Triangulations en contrainte
Vous pouvez simplement indiquer les limites de votre polygone (y compris les limites des trous) en tant que contraintes (le mieux serait d'insérer tous les sommets, puis de spécifier les contraintes sous forme de paires de Vertex_handles).
Vous pouvez ensuite baliser les triangles de la triangulation avec n’importe quel algorithme de parcours: commencez par un triangle incident au sommet infini et marquez-le comme étant à l’extérieur, puis passez à l’étiquette opposée (à marquait auparavant les triangles comme outsider, à l'extérieur si vous marquiez des triangles comme initié auparavant).
J'ai trouvé que la bibliothèque poly2tri était exactement ce dont j'avais besoin pour la triangulation. Il produit un maillage beaucoup plus net que les autres bibliothèques que j'ai essayées (y compris libtess) et supporte également les trous. Cela a été converti en un tas de langues. La licence est New BSD , vous permettant ainsi de l'utiliser dans tous les projets.
Vous pouvez ajouter les trous relativement facilement vous-même. Fondamentalement, triangulez sur la coque convexe des points d’entrée, conformément à CGAL, puis supprimez tout triangle dont le centre est situé à l’intérieur de l’un des polygones de trous (ou de l’extérieur des limites extérieures). Lorsque vous manipulez de nombreux trous dans un grand jeu de données, vous pouvez utiliser des techniques de masquage pour accélérer considérablement ce processus.
edit: Une extension courante de cette technique consiste à désherber des triangles faibles sur la coque, où le bord le plus long ou le plus petit angle interne dépasse une valeur donnée. Cela formera une meilleure coque concave.
essayez libtess2
https://code.google.com/p/libtess2/downloads/list
basé sur le tesselator SGI GLU original (avec licence libérale). Résout certains problèmes de gestion de la mémoire liés à de nombreux petits mallocs.
Il s'agit d'un problème courant dans l'analyse par éléments finis. C'est ce qu'on appelle la "génération automatique de maillage". Google a trouvé ce site avec des liens vers des sources commerciales et open source Logiciel. Ils supposent généralement qu’une sorte de représentation CAO de la géométrie commence.
Une autre option (avec une licence très flexible) consiste à porter l'algorithme de VTK:
Cet algorithme fonctionne assez bien. Son utilisation directe est possible, mais nécessite des liens vers VTK, ce qui peut engendrer plus de surcharge que vous ne le souhaitez (bien qu'il comporte également de nombreuses autres fonctionnalités intéressantes).
Il prend en charge les contraintes (trous / limites / etc.), ainsi que la triangulation d'une surface qui n'est pas nécessairement dans le plan XY. Il prend également en charge certaines fonctionnalités que je n’avais pas vues ailleurs (voir les notes sur les valeurs alpha).
J'ai implémenté un triangulateur en polygone 3D en utilisant la méthode de l'écrêtage des oreilles. Il est facile à utiliser, prend en charge les trous, est robuste numériquement et prend en charge les polygones convexes / non convexes aribtrary (non auto-sécants).
