Come si restituiscono le linee 2D spesse come poligoni?

Question

Ho un percorso composto da un elenco di punti 2D. Voglio trasformarle in una striscia di triangoli per rendere una linea strutturata con uno spessore specificato (e altre cose simili). Quindi in sostanza l'elenco di punti 2D deve diventare un elenco di vertici che specificano il contorno di un poligono che, se reso, dovrebbe rendere la linea. Il problema consiste nel gestire i join, le miters, i cappucci ecc. Il poligono risultante deve essere "perfetto" nel senso di non sovrascrivere, pulire join, ecc. In modo che possa essere facilmente estruso o altrimenti utilizzato.

Esistono semplici risorse in grado di fornire informazioni dettagliate sull'algoritmo, codice o ulteriori informazioni su come farlo in modo efficiente?

NON voglio assolutamente una libreria vettoriale 2D a tutti gli effetti (cairo, antigrain, OpenVG, ecc.) Con curve, archi, trattini e tutti i campanelli e fischietti. Ho scavato in più alberi sorgente per implementazioni OpenVG e altre cose per trovare qualche intuizione, ma è tutto terribilmente complicato.

Sono decisamente disposto a codificarlo da solo, ma ci sono molti casi degenerati (segmenti piccoli + larghezze spesse + angoli acuti) che creano tutti i tipi di problemi di join. Anche un piccolo aiuto mi avrebbe risparmiato ore di provare a trattare con tutti loro.

EDIT: Ecco un esempio di uno di quei casi degenerati che causano la bruttezza se si dovesse semplicemente passare dal vertice al vertice. Il rosso è il percorso originale I blocchi arancioni sono rettangoli disegnati con una larghezza specificata allineata e centrata su ciascun segmento.

http://www.freeimagehosting.net/uploads/52dc639727.png

Answer 1

Oh bene, ho provato a risolvere il problema da solo. Ho perso due mesi per una soluzione che ha cercato di risolvere il problema di sovrascrittura zero. Come hai già scoperto, non puoi occuparti di tutti i casi degenerati e avere un overdraw pari a zero allo stesso tempo.

È possibile comunque utilizzare un approccio ibrido:

Scrivi te una routine che controlla se i join può essere costruito dalla geometria semplice, senza problemi. Per fare ciò è necessario controllare l'angolo di unione, la larghezza della linea e la lunghezza dei segmenti di linea uniti (i segmenti di linea più brevi della loro larghezza sono un PITA). Con una certa euristica dovresti essere in grado di risolvere tutti i casi banali.

Non so come siano i vostri dati di linea medi, ma nel mio caso più del 90% delle linee non ha avuto casi degenerati.

Per tutte le altre linee:

Hai probabilmente già scoperto che se si tollerano overdraw, generando la geometria è molto più facile. Fatelo e lasciate che un algoritmo CSG del poligono e un algoritmo di tessellazione facciano il duro lavoro.

Ho valutato la maggior parte dei pacchetti di tesselazione disponibili e ho finito con il tesselator GLU. Era veloce, robusto, non si arrestava mai (a differenza della maggior parte degli altri algoritmi). Era gratuito e la licenza mi permetteva di includerlo in un programma commerciale. La qualità e la velocità della tesselation va bene. Non otterrai la qualità di triangolazione delaunay, ma dal momento che hai solo bisogno dei triangoli per il rendering non è un problema.

Poiché non mi piaceva l'API di tesselator ho sollevato il codice di tesselation dall'implementazione di riferimento OpenGL SGI gratuito, ho riscritto l'intero front-end e aggiunto pool di memoria per ottenere il numero di allocazioni verso il basso. Ci sono voluti due giorni per farlo, ma ne è valsa la pena (come il miglioramento delle prestazioni del fattore cinque). La soluzione è finita in un'implementazione OpenVG commerciale btw :-)

Se stai eseguendo il rendering con OpenGL su PC, potresti spostare il lavoro di tesselazione/CSG dalla CPU alla GPU e utilizzare il buffer di stencil o trucchetti z-buffer per rimuovere il superamento. Questo è molto più semplice e potrebbe essere persino più veloce della tesselation della CPU.

Answer 2

Penso che mi piacerebbe raggiungere per un algoritmo di tassellazione. È vero che nella maggior parte dei casi, dove vengono utilizzati, l'obiettivo è ridurre il numero di vertici per ottimizzare il rendering, ma nel tuo caso puoi parametrizzare per mantenere tutti i dettagli e la possibilità di ottimizzare può essere utile.

Ci sono numerosi algoritmi di tessellazione e codice in giro sul Web - Ho racchiuso una C pura in una DLL alcuni anni fa per l'uso con un renderer di Delphi landscape e non sono un argomento insolito per i tutorial di codifica grafica avanzata e simili.

Answer 3

Sono interessato anche a questo, poiché desidero perfezionare il disegno delle strade della mia applicazione di mappatura (Kosmos). Una soluzione alternativa che ho usato è disegnare la polilinea due volte, una volta con una linea più spessa e una volta con una più sottile, con un colore diverso. Ma questo non è proprio un poligono, è solo un modo veloce per simularne uno. Guarda alcuni esempi qui: http://wiki.openstreetmap.org/wiki/Kosmos_Rendering_Help#Rendering_Options

Non sono sicuro se questo è quello che ti serve.

Answer 4

Vedere se Delaunay triangulation può essere d'aiuto.

Answer 5

Un metodo semplice dalla parte superiore della mia testa.

Bisect l'angolo di ogni vertice 2d, questo creerà una bella linea di mitra. Quindi spostati lungo quella linea, sia verso l'interno che verso l'esterno, la quantità del tuo "spessore" (o spessore diviso per due?), Ora hai i tuoi punti poligono interno ed esterno. Passa al punto successivo, ripeti lo stesso processo, costruendo i tuoi nuovi punti poligono lungo la strada. Quindi applica una triangolazione per ottenere i vertici pronti per il rendering.

Answer 6

Nel mio caso potrei permettermi di superare. Ho appena disegnato cerchi con raggio = larghezza/2 centrati su ciascuno dei vertici della polilinea.

Gli artefatti sono mascherati in questo modo, ed è molto facile da implementare, se si riesce a convivere con angoli "arrotondati" e qualche rovesciamento.

Answer 7

Dalla tua immagine sembra che stai disegnando un rettangolo attorno ai segmenti di linea con FILL acceso e usando il colore arancione. In questo modo, creerai sicuramente dei sopralluoghi negativi. Quindi, la prima cosa da fare sarebbe non rendere il bordo nero e il colore di riempimento può essere opaco.

Perché non puoi usare la primitiva GL_LINES per fare ciò che intendi fare? È possibile specificare larghezza, filtraggio, levigatezza, trama qualsiasi. È possibile eseguire il rendering di tutti i vertici utilizzando glDrawArrays(). So che questo non è qualcosa che hai in mente ma, mentre ti concentri sul disegno 2D, questo potrebbe essere un approccio più semplice. (ricerca per linee tratteggiate ecc.)

Answer 8

Alla fine ho dovuto sporcarmi le mani e scrivere un piccolo ribbonizer per risolvere un problema simile.

Per me il problema era che volevo linee grasse in OpenGL che non avessero il tipo di artefatti che stavo vedendo con OpenGL su iPhone. Dopo aver esaminato varie soluzioni; curve bezier e simili - ho deciso che probabilmente era più facile fare solo il mio. Ci sono un paio di approcci diversi.

Un approccio consiste nel trovare l'angolo di intersezione tra due segmenti e quindi spostarsi lungo quella linea di intersezione a una certa distanza dalla superficie e trattarla come un vertice del nastro. L'ho provato e non sembrava intuitivo; la larghezza del nastro potrebbe variare.

Un altro approccio consiste nel calcolare effettivamente un normale alla superficie dei segmenti di linea e utilizzarlo per calcolare il bordo del nastro ideale per quel segmento e per eseguire test di intersezione effettivi tra i segmenti del nastro. Ciò ha funzionato bene, tranne che per gli angoli acuti le intersezioni dei segmenti della linea del nastro erano troppo lontane (se l'angolo tra i segmenti si avvicina a 180 ').

Ho lavorato intorno al problema dell'angolo acuto con due approcci. L'algoritmo di intersezione della linea di Paul Bourke (che ho usato in modo non ottimizzato) suggeriva di rilevare se l'intersezione era all'interno dei segmenti. Poiché entrambi i segmenti sono identici, ho solo bisogno di testare uno dei segmenti per l'intersezione. Potrei quindi arbitrare come risolvere questo; o confondendo un punto migliore tra le due estremità o indossando un cappuccio di chiusura - entrambi gli approcci sembrano buoni - l'approccio del cappuccio di estremità può eliminare il poligono anteriore/posteriore di fronte all'ordine per l'opengl.

Vedi http://paulbourke.net/geometry/lineline2d/

Vedi il mio codice sorgente qui: https://gist.github.com/1474156

Answer 9

Ho appena trovato questo straordinario lavoro:

http://www.codeproject.com/Articles/226569/Drawing-polylines-by-tessellation

Sembra di fare esattamente quello che vuoi, e la sua licenza permette usarlo anche in applicazioni commerciali. Inoltre, l'autore ha fatto un ottimo lavoro per dettagliare il suo metodo. Probabilmente darò una possibilità a un certo punto di sostituire la mia implementazione non quasi perfetta.