Question Triangulation robuste (avec trous), polygone complexe, bibliothèque c / c ++ avec licence permissive [fermé]


Je suis développeur du jeu open source, Bitfighter. Conformément au message SO suivant, nous avons utilisé l'excellente bibliothèque «Triangle» pour la génération de zones de maillage à utiliser avec notre IA en jeu (robots):

Triangulation polygonale avec trous

Cependant, nous avons rencontré un petit problème lorsque nous voulions emballer notre jeu pour Debian - l'utilisation de la bibliothèque «Triangle» fera que notre jeu sera considéré comme «non libre».

Nous avons été extrêmement satisfaits des performances de la bibliothèque «Triangle» et nous ne voulons pas vraiment y renoncer; Cependant, nous n'aimons pas non plus traiter les problèmes de licence. Nous nous sommes donc lancés dans une quête pour trouver un remplaçant approprié, sous licence permise, pouvant correspondre à la robustesse et à la rapidité de «Triangle».

Nous recherchons une bibliothèque C ou C ++ pour diviser des zones vastes et complexes en triangles, capables de gérer tous les types de polygones irréguliers placés ensemble de quelque manière que ce soit, ainsi que les trous. La robustesse est notre principal besoin, la vitesse étant presque aussi importante.

j'ai trouvé poly2tri, mais il souffre d'un bug dans lequel il ne peut pas gérer les polygones avec des bords coïncidents.

Nous avons trouvé plusieurs bibliothèques, mais toutes semblent souffrir d'une chose ou d'une autre: soit trop lente, soit ne pas gérer les trous, soit souffrir d'un bug. Actuellement, nous testons polypartition et nous avons de grands espoirs.

Quelles sont les meilleures alternatives à la grande bibliothèque 'Triangle', mais ont une licence permissive?


13
2018-04-16 17:03


origine


Réponses:


J'ai trouvé une solution. c'était poly2tri après tout, avec l'utilisation de l'excellent Tondeuse bibliothèque, et quelques ajouts algorithmiques mineurs aux entrées.

Notre processus est le suivant:

  1. Exécutez tous nos trous à travers Clipper en utilisant une union avec enroulement NonZero (cela signifie que les trous intérieurs sont enroulés dans la direction opposée à celle des extérieurs). Clipper garantit également de bons points d’entrée propres sans répétitions au sein d’epsilon.
  2. Filtrer nos trous dans ceux qui sont enroulés dans le sens antihoraire et dans le sens des aiguilles d'une montre. Les trous dans le sens des aiguilles d'une montre signifiaient que le trou était en circuit et qu'il y avait une autre zone concentrique à l'intérieur de laquelle il fallait trianguler
  3. En utilisant poly2tri, triangulez les limites extérieures et chaque polygone dans le sens des aiguilles d'une montre, en utilisant le reste des trous comme entrées dans poly2tri si elles se trouvaient dans l'une des limites.

Résultat:   poly2tri semble trianguler à peu près aussi vite que Triangle et a jusqu'à présent été très robuste avec tout ce que nous lui avons lancé.

Pour les intéressés, voici nos changements de code.

Mettre à jour

J'ai essayé de sortir notre code clipper-poly2tri, avec nos ajouts de robustesse, dans une bibliothèque distincte que j'ai lancée ici: clip2tri


15
2018-04-20 02:05



Vous pouvez jeter un coup d’œil au package de Triangulations 2D de CGAL. Un exemple pour trianguler un polygone avec des trous est donné ici. La licence du package est GPLv3 +.

Notez qu'il ne devrait pas être trop difficile d'extraire uniquement ce paquet si nécessaire.


1
2018-04-17 05:06



En petite note:

Récemment, j'ai dû mettre en œuvre un clipper et un triangulateur à polygones complexes pour couper les cadres de fenêtres dans les murs des maisons.

Bien que j'étais satisfait des résultats de la tondeuse Vatti, la triangulation de Delaunay utilisée dans poly2tri était trop lourde pour permettre un glissement en douceur du cadre de la fenêtre le long des coordonnées barycentriques de la face du mur. Après m'être gratté un peu la tête, j'ai fini par tromper cette triangulaire beaucoup plus simple pour travailler avec des trous:

http://wiki.unity3d.com/index.php?title=Triangulator

Ce que j'ai fait a été de subdiviser horizontalement le mur par la hauteur du plus petit poly. Dans mon cas, ils sont toujours des rectangles, mais ils ne le sont pas nécessairement. De toute façon, cela oblige le clipper à ne travailler qu'avec des polys réguliers ou concaves, ce qui vous permet de vous échapper avec une méthode de triangulation moins coûteuse.

Voici quelques captures d'écran montrant son fonctionnement:

https://www.dropbox.com/sh/zbzpvlkwj8b9gl3/sIBYCqa8ak

J'espère que cela t'aides.


1
2018-05-01 09:52