Conversione forme basate Tile 2D poligoni semplificate

Question

Come si vede nell'immagine sopra, ho un array 2D di piastrelle, ciascuna con 4 punti nel mio mondo di gioco. Sto cercando un metodo per convertire queste forme costruite da singole tessere in forme poligonali semplificate (senza inutili vertici, solo quelle necessarie per formare il contorno).

Mi sono guardato intorno, qui e altrove e ho avuto pochissima fortuna. Ma forse non conosco la terminologia corretta da cercare. Qualsiasi aiuto è apprezzato.

Ulteriori informazioni: Sto cercando di utilizzarlo per ottimizzare l'illuminazione dinamica. Se qualcuno ha un approccio diverso per realizzare ombre dinamiche veloci in un mondo basato su piastrelle, risponderà anche alla domanda.

Answer 1

suggerisco seguente algoritmo:

1. memorizzazione di tutte le posizioni di bordo in array 2D (posizione del bordo è centro del bordo).
2. Contando i bordi duplicati in questo array (1 non è duplicato, 2 si interseca con un altro bordo. Altri valori sono implossibili).
3. Selezionare il primo margine non contrassegnato dall'array con il numero di duplicati 1 (senza duplicati) e applicare l'algoritmo di riempimento ricorsivo semplice nella direzione di rilevamento (ad esempio in senso orario) fino al primo spigolo. Tutti questi bordi formeranno un poligono semplificato. Se il fronte non segnato non è stato trovato, GOTO 5.
4. Contrassegnare tutti questi bordi del passaggio 3 come utilizzato. VAI A passaggio 3.
5. Fine.

Per una rappresentazione più intuitiva dell'algoritmo, ho pubblicato un'immagine qui sotto.

Answer 2

L'approccio ingenuo sarebbe semplicemente di passare attraverso ogni singola piastrella e contrassegnare eventuali spigoli di transizione in un poligono, ma è possibile riutilizzare una normale routine edge detection per prestazioni migliori.

Dopodiché probabilmente ti interesserebbe tassellare quei poligoni in modo da convertirli in raccolte di triangoli (rendendo la più tarda ombra/illuminazione/intersezione matematica molto più semplice), l'unico problema in questo caso è se finisci con un poligono concavo, ma un tessellatore decente dovrebbe permetterti di suddividerlo in poligoni convessi. Non penso che XNA abbia qualcosa di costruito per la tassellazione, quindi potrebbe essere necessario trovare una libreria di utilità per farlo per te.