Come faccio rendo linee 2D spesse come poligoni?

StackOverflow https://stackoverflow.com/questions/687173

Domanda

Ho un percorso costituito da un elenco di punti 2D. Voglio trasformare questi in una striscia di triangoli per rendere una linea strutturata con uno spessore specificato (e altre cose). Quindi, in sostanza l'elenco dei punti 2D bisogno di diventare una lista di vertici che specificano la sagoma di un poligono che, se reso renderebbe la linea. Il problema sta gestendo l'angolo si unisce, angoli retti, tappi ecc Il poligono risultante deve essere "perfetta", nel senso di non overdraw, pulito unisce, ecc in modo che possa tenerne essere estruso o altrimenti giocato con.

Ci sono tutte le semplice le risorse intorno che possono fornire informazioni algoritmo, codice o altre informazioni a fare questo in modo efficace?

Sono assolutamente non voglio una libreria completa a tutti gli effetti 2D vettore (cairo, AntiGrain, OpenVG, ecc) con le curve, archi, trattini e tutte le campane e fischietti. Ho scavato in più alberi di origine per le implementazioni OpenVG e altre cose per trovare una certa comprensione, ma è tutto terribilmente complicata.

Sono decisamente pronto per codificare io stesso, ma ci sono molti casi degeneri (piccoli segmenti + spessore larghezze + spigoli vivi) che creano tutti i tipi di problemi di aderire. Anche un po 'di aiuto mi avrebbe risparmiare ore di provare a trattare con tutti loro.

EDIT: Ecco un esempio di uno di quei casi degeneri che causa la bruttezza se si dovesse semplicemente andare da vertice vertice. Il rosso è il percorso originale. I blocchi arancioni sono rettangoli disegnati ad una larghezza specificata allineato e centrato su ogni segmento.

È stato utile?

Soluzione

Oh bene - ho cercato di risolvere il problema io stesso. Ho sprecato due mesi su una soluzione che ha cercato di risolvere il problema a zero overdraw. Come hai già scoperto, non si può trattare con tutti i casi degenerati e hanno zero overdraw 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 in modo che controlla il join-angolo, la larghezza della linea e la lunghezza della linea-segmenti uniti (line-segmenti più brevi della loro larghezza sono una valle di lacrime). Con alcune euristiche si dovrebbe essere in grado di risolvere tutti i casi banali.

Non so come la vostra linea di dati media assomiglia, ma nel mio caso oltre il 90% delle ampie 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. Farlo, e lasciare che un algoritmo poligono CSG e un algoritmo tesselation fare il lavoro duro.

Ho valutato la maggior parte dei pacchetti Tesselation disponibili, e ho finito con il tesselator GLU. E 'stato veloce, robusto, mai caduto (a differenza di molti altri algoritmi). Era gratis e la licenza mi ha permesso di includere in un programma commerciale. La qualità e la velocità del tesselation va bene. Non sarà possibile ottenere Delaunay qualità di triangolazione, ma dal momento che è sufficiente triangoli per il rendering che non è un problema.

Dato che fastidio l'API tesselator Ho sollevato il codice tesselation dall'attuazione riferimento SGI OpenGL libera, riscritto l'intero front-end e aggiunto pool di memoria per ottenere il numero di allocazioni giù. Ci sono voluti due giorni per fare questo, ma ne è valsa la pena (come fattore di cinque miglioramento delle prestazioni). La soluzione ha causato la realizzazione OpenVG commerciale btw: -)

Se siete il rendering con OpenGL su un PC, si consiglia di spostare il tesselation / CSG-lavoro dalla CPU alla GPU e utilizzare stencil-tampone o Z-buffer trucchi per rimuovere l'overdraw. Questo è molto più facile e può essere anche più veloce di tesselation CPU.

Altri suggerimenti

Un metodo semplice fuori dalla parte superiore della mia testa.

tagliano in due l'angolo di ogni 2d Vertex, questo creerà una bella linea mitra. Poi muoversi lungo quella linea, sia verso l'interno e verso l'esterno, l'importo del vostro "spessore" (o lo spessore diviso per due?), Ora avete i vostri punti del poligono interno e quello esterno. Spostare al punto successivo, ripetere lo stesso processo, costruire i nuovi punti del poligono lungo la strada. Quindi applicare un triangualtion per ottenere i vertici di rendering-ready.

Ho appena trovato questo straordinario lavoro:

http://www.codeproject.com/Articles/226569/ Illustrazione-polilinee-by-tassellazione

Sembra di fare esattamente quello che vuoi, e la sua licenza permette di utilizzarlo anche in applicazioni commerciali. Inoltre, l'autore ha fatto un grande lavoro veramente ai dettagli il suo metodo. Io probabilmente dare un colpo ad un certo punto per sostituire il mio propria implementazione non-quasi-come-perfetto.

Ho finito per dover mettere le mani sporche e scrivere un piccolo ribbonizer per risolvere un problema simile.

Per me il problema era che volevo linee di grasso in OpenGL che non hanno i tipi di artefatti che stavo vedendo con OpenGL su iPhone. Dopo aver esaminato diverse soluzioni; curve di Bezier e simili - ho deciso che era probabilmente più semplice per fare solo la mia. Ci sono un paio di approcci diversi.

Un approccio è quello di trovare l'angolo di intersezione tra due segmenti e poi muoversi lungo quella linea intersezione una certa distanza dalla superficie e trattare che come un vertice nastro. Ho provato e che non sembrava intuitiva; la larghezza del nastro varierebbe.

Un altro approccio è quello di calcolare in realtà una normale alla superficie dei segmenti di linea e utilizzarlo per calcolare il bordo del nastro ideale per quel segmento e fare test intersezioni effettive tra i segmenti di nastro. Questo ha funzionato bene, tranne che per spigoli vivi delle intersezioni segmento di linea del nastro erano troppo lontano (se l'angolo tra segmenti avvicinato 180' ).

Ho lavorato intorno alla questione angolo acuto con due approcci. L'algoritmo linea di intersezione Paul Bourke (che ho usato in modo non ottimizzato) suggeriva rileva se l'intersezione era all'interno dei segmenti. Poiché entrambi i segmenti sono identiche ho solo bisogno di testare uno dei segmenti di intersezione. Potrei allora arbitrare come risolvere questo; sia da un punto fudging migliore tra le due estremità o mettendo su una testata - entrambi gli approcci sembrano buone - l'approccio cappuccio terminale può buttare fuori la parte anteriore del poligono / schiena rivolta verso l'ordinazione per OpenGL

.

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

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

Penso che mi piacerebbe raggiungere per un algoritmo di tassellazione. E 'vero che nella maggior parte dei casi in cui questi vengono utilizzati l'obiettivo è di ridurre il numero di vertici per ottimizzare il rendering, ma nel tuo caso si potrebbe parametrizzare per mantenere tutti i dettagli -. E la possibilità di ottimizzare possono venire in utile

Ci sono numerosi algoritmi di tassellazione e il codice in giro sul web - ho avvolto un puro C su in una DLL di qualche anno fa per l'uso con un paesaggio renderer Delphi, e non sono un soggetto non comune per la grafica avanzata di codifica tutorial e ecc.

Vedere se Delaunay triangolazione può aiutare.

Nel mio caso ho potuto permettersi di overdraw. I soli cerchi drow con raggio = larghezza / 2 centrata su ciascuno dei vertici della polilinea.

Gli artefatti sono mascherati in questo modo, ed è molto facile da implementare, se si può vivere con gli angoli arrotondati "" e alcuni overdrawing.

Dalla vostra immagine sembra che si sta casella intorno segmenti di linea disegno con FILL su e usando il colore arancione. In questo modo sta andando a creare cattive amplifica di sicuro. Quindi, prima cosa da fare sarebbe quella di non rendere bordo nero e il colore di riempimento può essere opaco.

Perché non si può utilizzare GL_LINES primitiva di fare quello che l'intenzione di fare? È possibile specificare la larghezza, il filtraggio, la scorrevolezza, la consistenza nulla. È possibile eseguire il rendering utilizzando tutti i vertici glDrawArrays (). So che questo non è qualcosa che avete in mente, ma come si stanno concentrando su disegno 2D, questo potrebbe essere l'approccio più facile. (Cercare strutturati linee ecc.)

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top