Triangolazione di poligono (con fori) complessa, veloce e complessa C/C++ con licenza permissiva

Question

Sono uno sviluppatore del gioco open-source, Bitfighter. Come per il seguente post SO, abbiamo usato l'eccellente libreria 'Triangolo' per la generazione di mesh-zone per l'uso con il nostro in-game AI (robot):

Polygon Triangulation with Holes

Tuttavia, ci siamo imbattuti in un piccolo intoppo quando vogliamo impacchettare il nostro gioco per Debian, l'uso della libreria "Triangolo" renderà il nostro gioco considerato "non libero".

Siamo stati estremamente soddisfatti delle prestazioni della libreria "Triangolo" e non vogliamo davvero rinunciarci; tuttavia, non ci piace gestire anche i problemi di licenza. Pertanto, abbiamo intrapreso una ricerca per trovare un sostituto adatto e concesso in licenza che possa eguagliare "Triangolo" nella sua robustezza e velocità.

Stiamo cercando una libreria C o C++ per dividere aree grandi e complesse in triangoli, in grado di gestire qualsiasi tipo di poligoni irregolari posizionati insieme in qualsiasi modo, così come i fori. La robustezza è il nostro bisogno primario, con una velocità quasi altrettanto importante.

Ho trovato poly2tri, ma soffre di un bug in cui non è possibile gestire poligoni con bordi coincidenti.

Abbiamo trovato diverse librerie, ma tutte sembrano soffrire di una cosa o di un'altra: o troppo lente, o non gestire buchi, o soffrire di qualche bug. Attualmente stiamo testando polypartition e abbiamo grandi speranze.

Quali sono le migliori alternative alla grande libreria "Triangolo", ma hanno una licenza permissiva?

Answer 1

Ho trovato una soluzione. Dopotutto era il poly2tri, con l'uso dell'eccellente libreria Clipper e alcune aggiunte secondarie algoritmiche agli input.

nostro processo è il seguente:

1. eseguire tutti i nostri fori attraverso Clipper utilizzando un'unione con avvolgimento diverso da zero (ciò significa che fori interni sono avvolti direzione opposta, come quelle esterne). Clipper garantisce anche punti di input puliti e senza ripetizioni all'interno di epsilon.
2. Filtra i nostri fori in quelli che sono avvolti in senso antiorario e orario. I fori in senso orario significavano che il foro era tortuoso e che all'interno c'era un'altra area concentrica che doveva essere triangolata
3. Utilizzando poly2tri, triangolare i limiti esterni e ogni poligono in senso orario trovato, utilizzando il resto dei fori come input per poly2tri se sono stati trovati all'interno di uno dei limiti.

Risultato: poly2tri sembra triangolare quasi veloce come Triangolo e finora è stata molto robusto, con tutto quello che abbiamo buttato a questo.

Per chi è interessato, here are our code changes.

Aggiornamento

ho cercato di tirare fuori il nostro tagliatore-to-poly2tri codice, con le nostre aggiunte di robustezza, in una libreria separata che ho iniziato qui: clip2tri

Answer 2

Si può dare un'occhiata al pacchetto di triangolazioni 2D di CGAL. Un esempio per triangolare un poligono con buchi è dato here. La licenza del pacchetto è GPLv3 +.

Si noti che non dovrebbe essere troppo difficile estrarre solo questo pacchetto se necessario.

Answer 3

Come un piccolo side-nota :

Recentemente ho dovuto implementare un triangolatore di poligoni complesso & triangolatore per tagliare i telai delle finestre nei muri di casa.

Mentre ero soddisfatto dei risultati del clipper Vatti, la triangolazione di Delaunay utilizzata in poly2tri era troppo pesante per consentire il trascinamento morbido del telaio della finestra lungo le coordinate baricentriche della parete. Dopo graffiare la mia testa un po ', ho finito per ingannare questa forma triangolare molto più semplice lavorare con i fori:

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

Quello che ho fatto è stato in orizzontale suddividere la faccia muro per l'altezza dei più brevi poli di ritaglio. Nel mio caso sono sempre rettangoli, ma non è necessario. In ogni caso, costringe il clipper a lavorare solo con poligoni regolari o concavi, e quindi consente di cavarsela con un metodo di triangolazione più economico.

Ecco alcuni screenshot che mostrano funzionare:

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

Spero che questo aiuti.