C'è un efficiente\modo facile per disegnare un poligono concavo in Direct3d

Question

Sto cercando di disegnare un poligono con c# e directx

Tutto quello che ho ottenuto è un elenco ordinato di punti da un file e ho bisogno di disegnare il poligono semplice in un mondo 3d.

Posso caricare i punti e disegnare una forma convessa utilizzando un trianglefan e drawuserprimitives.

Questo, ovviamente, porta a risultati non corretti quando il poligono è molto concavo (che può essere).

Non riesco a immaginare che io sono l'unica persona a cimentarsi con questo problema (tho io sono un gfx/directx neofita - il mio background è in gui\windows application development).

Qualcuno può indicarmi verso un semplice da seguire risorsa utorial\algoritmo che mi può aiutare?

Answer 1

Direct3D può solo disegnare triangoli (beh, è possibile disegnare linee e punti, ma oltre il punto).Quindi, se si desidera disegnare qualsiasi forma che è più complessa di un triangolo, è necessario disegnare un mucchio di toccare i triangoli uguali per forma.

Nel tuo caso, si tratta di un poligono concavo triangolazione problema.Dato un gruppo di vertici, è possibile mantenere loro, come lo è, è solo bisogno di calcolare l'indice "buffer" (nel caso più semplice, tre indici per ogni triangolo che dire che i vertici del triangolo usa).Quindi disegnare che, attraverso la messa in vertex/index buffer o utilizzando DrawUserPrimitives.

Alcuni algoritmi di triangolazione semplice (convessa o concava, ma senza auto-intersezioni o fori) poligoni sono a VTerrain sito.

Ho usato Ratcliff codice in passato;molto semplice e funziona bene.VTerrain ha un dead link ad esso;il codice può essere trovato qui.È il C++, ma il porting che oltre a C# dovrebbe essere semplice.

Oh, e non utilizzare il triangolo di fan.Essi sono di uso molto limitato, inefficiente e stanno andando via presto (ad es.Direct3D 10 non li supporta più).Basta usare il triangolo liste.

Answer 2

La triangolazione è ovvio che la risposta, ma e ' difficile scrivere una solida triangulator.A meno che non hai due mesi di tempo per rifiuti non nemmeno provare.

Ci sono un paio di codici che possono aiutare:

Il GPC Biblioteca.Molto facile da usare, ma non come licenza:

http://www.cs.man.ac.uk/~toby/alan/software/gpc.html

C'è anche un triangolo:

http://www.cs.cmu.edu/~quake/triangle.html

E il suo PUGNO:

http://www.cosy.sbg.ac.at/~held/projects/triang/triang.html

Un altro (il mio preferito) opzione sarebbe quella di utilizzare il GLU tesselator.È possibile caricare e utilizzare il GLU libreria di programmi di DirectX bene.Non ha bisogno di un contesto OpenGL di usare, e che è pre-installato su tutti i computer windows.Se si desidera sorgente si può sollevare la triangolazione codice da SGI implementazione di riferimento.L'ho fatto una volta e mi ci sono voluti solo un paio di ore.

Finora per la triangolazione.C'è un modo diverso così:È possibile utilizzare stencil trucchi.

L'algoritmo generale va come questa:

1. Disattivare colore e profondità, scrive.Attivare stencil scrive e di configurazione del vostro stencil buffer che invertire l'attuale stencil valore.Un po ' di stencil è sufficiente.Oh - stencil buffer deve essere cancellata così.

2. Scegliere un punto casuale sullo schermo.Ne farete.Chiamare questo punto di Ancoraggio.

3. Per ogni bordo del poligono costruire un triangolo dai due vertici che costruire il bordo e la vostra ancora.Disegnare un triangolo.

4. Una volta che hai estratto tutti questi triangoli, spegnere stencil scrivere, girare su stencil test e il colore di scrivere e disegnare a schermo intero quad nel colore della scelta.Questo riempie solo i pixel all'interno del vostro poligono convesso.

È una buona idea per posizionare il punto di ancoraggio al centro del poligono e disegnare un rettangolo grande come il confine del poligono.Che consente di risparmiare un po ' di fillrate.

Btw - la tecnica dello stencil opere per auto-intersezioni poligoni così.

Speranza che aiuta, Nils

Answer 3

Se siete in grado di utilizzare lo stencil buffer, non dovrebbe essere difficile da fare.Ecco un algoritmo generale:

Clear the stencil buffer to 1.
Pick an arbitrary vertex v0, probably somewhere near the polygon to reduce floating-point errors.
For each vertex v[i] of the polygon in clockwise order:
    let s be the segment v[i]->v[i+1] (where i+1 will wrap to 0 when the last vertex is reached)
    if v0 is to the "right" of s:
        draw a triangle defined by s, v[i], v[i+1] that adds 1 to the stencil buffer
    else
        draw a triangle defined by s, v[i], v[i+1] that subtracts 1 from the stencil buffer
end for
fill the screen with the desired color/texture, testing for stencil buffer values >= 2.

Da "diritto di s", intendo dalla prospettiva di qualcuno che sta in v[i] e di fronte a v[i+1].Questo può essere testato utilizzando un prodotto trasversale:

croce(v0 - v[i], v[i+1] - v[i]) > 0

Answer 4

Ho dovuto fare questo per un progetto.Il più semplice algoritmo che ho trovato è chiamato "Orecchio Ritaglio".Una grande carta su di esso è qui: TriangulationByEarClipping.pdf

Io mi ci sono voluti circa 250 righe di codice c++ e 4 ore per implementare la forza bruta versione di esso.Altri algoritmi di avere prestazioni migliori, ma questo, semplice da realizzare e capire.