Triangolazione poligonale con fori

Question

Sto cercando un algoritmo o una libreria (meglio) per scomporre un poligono in triangoli. Userò questi triangoli in un'applicazione Direct3D. Quali sono le migliori opzioni disponibili?

Ecco cosa ho trovato finora:

1. Note di Ben Discoe
2. FIST: triangolazione veloce dei poligoni a livello industriale
3. So che CGAL fornisce triangolazione ma non sono sicuro che supporti i buchi.

Gradirei davvero alcune opinioni di persone con precedenti esperienze in questo settore.

Modifica: questo è un poligono 2D.

Answer 1

La Biblioteca del triangolo di Jonathan Shewchuk è fenomenale; L'ho usato per automatizzare la triangolazione in passato. Puoi chiedergli di tentare di evitare triangoli piccoli / stretti, ecc., Quindi ti viene in mente "buono". triangolazioni invece di qualsiasi triangolazione.

Answer 2

Per darti qualche altra scelta di librerie là fuori:

Polyboolean. Non l'ho mai provato, ma sembra promettente: http: //www.complex-a5. ru / polyboolean / index.html

General Polygon Clipper. Questo funziona molto bene in pratica e fa triangolazione, nonché fori di ritaglio e fori: http://www.cs.man.ac.uk/~toby/alan/software/

Il mio consiglio personale: utilizzare la tassellatura dalla GLU (OpenGL Utility Library). Il codice è solido, più veloce di GPC e genera meno triangoli. Non è necessario un OpenGL-Handle inizializzato o qualcosa del genere per usare la lib.

Se non ti piace l'idea di includere le librerie di sistema OpenGL in un'applicazione DirectX, esiste anche una soluzione: basta scaricare il codice di implementazione del riferimento OpenGL SGI e sollevare il triangolatore da esso. Usa solo i nomi OpenGL-Typedef e una mano piena di enumerazioni. Questo è tutto. Puoi estrarre il codice e creare una libreria autonoma in un'ora o due.

---

In generale, il mio consiglio sarebbe di usare qualcosa che funzioni alreay e di non iniziare a scrivere la tua triangolazione.

Se hai letto dell'algoritmo ear-clipping o sweep-line, sei tentato di lanciarti da solo, ma è un dato di fatto che gli algoritmi di geometria computazionale sono incredibilmente difficili da scrivere in modo da funzionare in modo stabile, non andare mai in crash e restituire sempre un risultato significativo. Gli errori numerici di arrotondamento si accumuleranno e ti uccideranno alla fine.

Ho scritto un algoritmo di triangolazione in C per l'azienda con cui lavoro. Far funzionare l'algoritmo di base ha impiegato due giorni. Per farlo funzionare con tutti i tipi di input degenerati ci sono voluti altri due anni (non ci stavo lavorando a tempo pieno, ma fidati di me - ci ho passato più tempo di quanto avrei dovuto).

Answer 3

CGAL ha lo strumento che ti serve: Triangolazioni vincolate

Puoi semplicemente fornire i confini del tuo poligono (includendo i confini dei fori) come vincoli (il migliore sarebbe che tu inserisca tutti i vertici, e quindi specifichi i vincoli come coppie di Vertex_handles).

È quindi possibile contrassegnare i triangoli della triangolazione con qualsiasi algoritmo di attraversamento: iniziare con un triangolo incidente al vertice infinito e contrassegnarlo come esterno, e ogni volta che si attraversa un vincolo, passare al tag opposto (all'interno se si in precedenza stavi tag i triangoli come outsider, all'esterno se prima stavi tag i triangoli come insider).

Answer 4

Ho trovato la libreria poly2tri esattamente ciò di cui avevo bisogno per la triangolazione. Produce una mesh molto più pulita rispetto ad altre librerie che ho provato (incluso libtess) e supporta anche buchi. È stato convertito in un sacco di lingue. La licenza è New BSD , quindi puoi usarla in qualsiasi progetto.

Libreria Poly2tri su codice Google

Answer 5

Puoi aggiungere i buchi relativamente facilmente da solo. Fondamentalmente triangolare sullo scafo convesso dei punti di input, come da CGAL, quindi eliminare qualsiasi triangolo il cui incentivo risiede all'interno di uno qualsiasi dei poligoni del foro (o al di fuori di qualsiasi limite esterno). Quando si affrontano molti buchi in un set di dati di grandi dimensioni, è possibile utilizzare tecniche di mascheramento per accelerare significativamente questo processo.

modifica: un'estensione comune a questa tecnica è quella di estirpare i triangoli deboli sullo scafo, dove il bordo più lungo o l'angolo interno più piccolo supera un dato valore. Ciò formerà uno scafo concavo migliore.

Answer 6

prova libtess2

https://code.google.com/p/libtess2/downloads/list

basato sul tesselator SGI GLU originale (con licenza liberale). Risolve alcuni problemi di gestione della memoria relativi a molti piccoli malloc.

Answer 7

Questo è un problema comune nell'analisi degli elementi finiti. Si chiama "generazione automatica di mesh". Google ha trovato questo sito con collegamenti a commerciali e open source Software. Di solito presumono l'avvio di una sorta di rappresentazione CAD della geometria.

Answer 8

Un'altra opzione (con una licenza molto flessibile) è il porting dell'algoritmo da VTK:

vtkDelaunay2D

Questo algoritmo funziona abbastanza bene. Usarlo direttamente è possibile, ma richiede collegamenti a VTK, che potrebbe avere un overhead maggiore di quello che desideri (anche se ha anche molte altre belle funzioni).

Supporta vincoli (buchi / confini / ecc.), oltre a triangolare una superficie che non è necessariamente nel piano XY. Supporta anche alcune funzionalità che non ho visto altrove (vedi le note sui valori Alpha).

Answer 9

Ho implementato un poligono 3D triangulator in C # usando il metodo del clipping dell'orecchio. È facile da usare, supporta buchi, è numericamente robusto e supporta poligoni convessi / non convessi aribtrari (non autointersecanti).