Share
La capacità di dividere dinamicamente una forma convessa in due forme separate è un'abilità o uno strumento molto prezioso da avere nel proprio arsenale di gioco. Questa suddivisione consente tipi avanzati di simulazione, come partizioni binarie dello spazio per la grafica o la fisica, ambienti dinamicamente distruttivi (fragile fratturazione!), Simulazione oceano o acqua, risoluzione collisione per motori fisici, partioning spaziale binario e la lista continua. Un grande esempio è il gioco Fruit Ninja per Kinect.
Cosa significa esattamente per dividere una forma convessa? In due dimensioni, ci riferiamo a una forma come a poligono; in tre dimensioni, ci riferiamo a una forma come a poliedro. (poliedri è la parola usata per indicare più di un poliedro).
Mancia: In generale, poligoni convessi e poliedri semplificano molti aspetti della manipolazione e gestione del volume o della mesh. A causa di questa semplificazione, l'intero articolo assume poligoni convessi e poliedri convessi. Le forme concave non fanno parte di nessuna discussione qui. In generale le forme concave complicate sono simulate come una collezione di forme convesse unite.
Per dare un senso alle idee presentate in questo articolo, avrai bisogno di una conoscenza pratica di alcuni linguaggi di programmazione e una semplice comprensione del prodotto puntino.
Un ottimo modo per dividere le forme in entrambe le due e tre dimensioni consiste nell'utilizzare la routine di ritaglio Sutherland-Hodgman. Questa routine è abbastanza semplice e molto efficiente e può essere estesa anche leggermente per tenere conto della robustezza numerica. Se non hai familiarità con l'algoritmo, controlla il mio precedente articolo sull'argomento.
Anche la comprensione dei piani in due o tre dimensioni è d'obbligo. Dovrebbe essere notato che un piano bidimensionale potrebbe essere pensato come una proiezione di un piano tridimensionale in due dimensioni ?? - o, in altre parole, una linea.
Per favore, comprendi che un aereo può anche essere pensato come un semispazio. Calcolare la distanza o l'intersezione di punti in mezzo-spazi è un prerequisito richiesto: consultare l'ultima sezione di Come creare un motore di fisica 2D personalizzato: il Core Engine per informazioni su questo.
Per favore fai riferimento alla fonte dimostrativa (anche su Bitbucket) che ho creato mentre leggi questo tutorial. Ho usato questa demo per creare tutte le immagini GIF nell'articolo. Il codice sorgente è in C ++ (e dovrebbe essere compatibile multipiattaforma), ma è scritto in un modo che può essere facilmente portato su qualsiasi linguaggio di programmazione.
Prima di affrontare il problema della divisione di un intero poligono, diamo un'occhiata al problema di dividere un triangolo attraverso un piano di taglio. Ciò costituirà la base della comprensione per passare a una soluzione robusta e generalizzata.
La cosa bella della divisione delle forme è che, spesso, gli algoritmi in 2D possono essere estesi senza troppi problemi direttamente in 3D. Qui, presenterò un algoritmo di suddivisione del triangolo molto semplice sia per le due che per le tre dimensioni.
Quando un triangolo si interseca con un piano di divisione, devono essere generati tre nuovi triangoli. Ecco un'immagine che mostra un triangolo prima e dopo la divisione lungo un piano:
Dato un piano di divisione, tre nuovi triangoli vengono emessi durante l'operazione di taglio. Facciamo un po 'di codice all'aperto, supponendo che i tre vertici di un triangolo lo siano a, b, c in senso antiorario (CCW) e sappiamo che il bordo ab (il bordo dei vertici da a b) ha intersecato il piano di divisione:
// Aggancia un triangolo contro un piano sapendo che // da a b attraversa il piano di ritaglio // Riferimento: Esatto Bouyancy per Polyhedra di // Erin Catto in Game Programming Gems 6 void SliceTriangle (std :: vector & out, const Vec2 & a, // Primo punto su triangolo, ordine CCW const Vec2 & b, // Secondo punto su triangolo, CCW ordine const Vec2 & c, // Terzo punto su triangolo, CCW ordine f32 d1, // Distanza del punto a sul piano di divisione f32 d2 , // Distanza del punto b sul piano di divisione f32 d3 // Distanza del punto c sul piano di divisione) // Calcolare il punto di intersezione da a a b Vec2 ab = a + (d1 / (d1 - d2)) * (b - a); Triangolo tri; if (d1 < 0.0f) // b to c crosses the clipping plane if(d3 < 0.0f) // Calculate intersection point from b to c Vec2 bc = b + (d2 / (d2 - d3)) * (c - b); tri.Set( b, bc, ab ); out.push_back( tri ); tri.Set( bc, c, a ); out.push_back( tri ); tri.Set( ab, bc, a ); out.push_back( tri ); // c to a crosses the clipping plane else // Calculate intersection point from a to c Vec2 ac = a + (d1 / (d1 - d3)) * (c - a); tri.Set( a, ab, ac ); out.push_back( tri ); tri.Set( ab, b, c ); out.push_back( tri ); tri.Set( ac, ab, c ); out.push_back( tri ); else // c to a crosses the clipping plane if(d3 < 0.0f) // Calculate intersection point from a to c Vec2 ac = a + (d1 / (d1 - d3)) * (c - a); tri.Set( a, ab, ac ); out.push_back( tri ); tri.Set( ac, ab, b ); out.push_back( tri ); tri.Set( b, c, ac ); out.push_back( tri ); // b to c crosses the clipping plane else // Calculate intersection point from b to c Vec2 bc = b + (d2 / (d2 - d3)) * (c - b); tri.Set( b, bc, ab ); out.push_back( tri ); tri.Set( a, ab, bc ); out.push_back( tri ); tri.Set( c, a, bc ); out.push_back( tri );
Spero che il codice sopra ti abbia spaventato un po '. Ma non temere; tutto quello che stiamo facendo qui è il calcolo di alcuni punti di intersezione per sapere come generare tre nuovi triangoli. Se uno avesse esaminato attentamente l'immagine precedente, le posizioni dei punti di intersezione potrebbero essere ovvie: sono dove la linea tratteggiata incontra il piano di scissione e dove il bordo ab interseca il piano di scissione. Ecco un diagramma per comodità:
Da questo diagramma, è facile vedere che i triangoli di output dovrebbero contenere i vertici a, ac, ab, ac, c, b, e ab, ac, b. (Ma non necessariamente in questo formato esatto, per esempio, a, b, c sarebbe lo stesso triangolo di c, b, a perché i vertici sono stati semplicemente spostati a destra.)
Per determinare quali vertici contribuiscono a quale dei tre nuovi triangoli, dobbiamo determinare se il vertice un e vertice c giaceva sopra o sotto l'aereo. Dal momento che stiamo assumendo che il bordo ab è noto per essere intersecante, possiamo dedurre implicitamente questo B è sul lato opposto del piano di ritaglio da un.
Se si intende la convenzione di una distanza negativa da un piano di scissione penetrante Nel piano, possiamo formulare un predicato per determinare se un punto interseca un mezzo spazio: #define HitHalfspace (distanza) ((distanza) < 0.0f). Questo predicato è utilizzato all'interno di ciascuno Se dichiarazione per verificare se un punto si trova all'interno del mezzo spazio del piano di ritaglio.
Esistono quattro casi che esistono combinazioni di un e B colpire il mezzo spazio del piano di ritaglio:
a | T T F F ----------- b | T F T F
Poiché la nostra funzione richiede che entrambi un e B essere sui lati opposti del piano, due di questi casi sono caduti. Tutto ciò che rimane è vedere da che parte c stabilisce. Da qui, l'orientamento di tutti e tre i vertici è noto; i punti di intersezione e i vertici di uscita possono essere calcolati direttamente.
Per usare il SliceTriangle () funzione, dobbiamo trovare un bordo intersecante di un triangolo. L'implementazione di seguito è efficiente e può essere utilizzata su tutti i triangoli nella simulazione per essere potenzialmente suddivisi:
// Taglia tutti i triangoli con un vettore di triangoli. // Viene generato un nuovo elenco di triangoli di output. Il vecchio // elenco di triangoli viene scartato. // n - La normale del piano di ritaglio // d - Distanza del piano di ritaglio dall'origine // Riferimento: Esatto Bouyancy per Polyhedra di // Erin Catto in Game Programming Gems 6 void SliceAllTriangles (const Vec2 & n, f32 d) std :: vector out; per (uint32 i = 0; i < g_tris.size( ); ++i) // Grab a triangle from the global triangle list Triangle tri = g_tris[i]; // Compute distance of each triangle vertex to the clipping plane f32 d1 = Dot( tri.a, n ) - d; f32 d2 = Dot( tri.b, n ) - d; f32 d3 = Dot( tri.c, n ) - d; // a to b crosses the clipping plane if(d1 * d2 < 0.0f) SliceTriangle( out, tri.a, tri.b, tri.c, d1, d2, d3 ); // a to c crosses the clipping plane else if(d1 * d3 < 0.0f) SliceTriangle( out, tri.c, tri.a, tri.b, d3, d1, d2 ); // b to c crosses the clipping plane else if(d2 * d3 < 0.0f) SliceTriangle( out, tri.b, tri.c, tri.a, d2, d3, d1 ); // No clipping plane intersection; keep the whole triangle else out.push_back( tri ); g_tris = out;
Dopo aver calcolato la distanza segnata di ciascun vertice triangolare sul piano di scissione, è possibile utilizzare la moltiplicazione per vedere se due distinti punti si trovano sui lati opposti di un piano. Poiché le distanze saranno di un flottante positivo e negativo all'interno di una coppia, il prodotto dei due moltiplicato insieme deve essere negativo. Ciò consente l'uso di un semplice predicato per vedere se due punti si trovano su entrambi i lati di un piano: #define OnOppositeSides (distanzaA, distanzaB) ((distanzaA) * (distanzaB) < 0.0f).
Una volta qualunque il bordo si trova ad intersecare con il piano di divisione, i vertici del triangolo vengono rinominati e spostati e subito passò lungo l'interno SliceTriangle funzione. In questo modo, il primo bordo di intersezione trovato viene rinominato ab.
Ecco come può apparire un prodotto finale funzionante:
La suddivisione dei triangoli in questo modo tiene conto indipendentemente per ciascun triangolo e l'algoritmo presentato qui si estende, senza alcuna ulteriore creazione, da due a tre dimensioni. Questa forma di ritaglio triangolare è ideale quando non sono richieste informazioni di avvicinamento dei triangoli o quando i triangoli ritagliati non vengono memorizzati in nessun punto della memoria. Questo è spesso il caso quando si calcolano volumi di intersezioni, come nella simulazione dell'assetto.
L'unico problema con la suddivisione dei triangoli in isolamento è che non ci sono informazioni sui triangoli che sono adiacente ad un altro. Se esaminate attentamente la GIF sopra, potete vedere che molti triangoli condividono vertici collineari e, di conseguenza, può essere collassato in un singolo triangolo per essere reso in modo efficiente. La prossima sezione di questo articolo affronta questo problema con un altro algoritmo più complesso (che usa tutte le tattiche presenti in questa sezione).
Ora per l'argomento finale. Supponendo una comprensione operativa dell'algoritmo Sutherland-Hodgman, è abbastanza facile estendere questa comprensione per dividere una forma con un piano e produrre i vertici su tutti e due lati dell'aereo. Anche la robustezza numerica può (e dovrebbe) essere presa in considerazione.
Esaminiamo brevemente i vecchi casi di ritaglio di Sutherland-Hodgman:
// InFront = plane.Distance (point)> 0.0f // Dietro = plane.Distance (point) < 0.0f Vec2 p1, p2; ClipPlane plane; case p1 InFront and p2 InFront push p2 case p1 InFront and p2 Behind push intersection case p1 Behind and p2 InFront push intersection push p2
Questi tre casi funzionano in modo decente, ma in realtà non tengono conto dello spessore del piano di scissione. Di conseguenza, l'errore numerico può andare alla deriva quando gli oggetti si muovono, causando una bassa coerenza temporale dei fotogrammi. Questo tipo di instabilità numerica può comportare il ritaglio di un angolo di un fotogramma e non di un altro fotogramma, e questo tipo di jitter può essere piuttosto brutto visivamente o inaccettabile per la simulazione fisica.
Un altro vantaggio di questo test del piano spessa è che i punti che si trovano molto vicino al piano possono effettivamente essere considerati come tali sopra il piano, che rende leggermente più utile la geometria ritagliata. È completamente possibile che un punto di intersezione calcolato si posizioni numericamente sul lato sbagliato di un piano! Gli aerei spessi evitano tali strani problemi.
Utilizzando piani spessi per i test di intersezione, è possibile aggiungere un nuovo tipo di caso: una posa di punti direttamente su un aereo.
Sutherland-Hodgman dovrebbe essere modificato in questo modo (con un punto variabile EPSILON per tenere conto degli aerei spessi):
// InFront = plane.Distance (point)> EPSILON // Dietro = plane.Distance (point) < -EPSILON // OnPlane = !InFront( dist ) && !Behind( dist ) Vec2 p1, p2; ClipPlane plane; case p1 InFront and p2 InFront push p2 case p1 InFront and p2 Behind push intersection case p1 Behind and p2 InFront push intersection push p2 case any p1 and p2 OnPlane push p2
Tuttavia, questa forma di Sutherland-Hodgman emette solo i vertici un lato del piano di scissione. Questi cinque casi possono essere facilmente estesi a un set di nove per produrre vertici su entrambi i lati di un piano di divisione:
// InFront = plane.Distance (point)> EPSILON // Dietro = plane.Distance (point) < -EPSILON // OnPlane = !InFront( dist ) && !Behind( dist ) Vec2 p1, p2; Poly front, back; ClipPlane plane; case p1 InFront and p2 InFront front.push( p2 ) case p1 OnPlane and p2 InFront front.push( p2 ) case p1 Behind and p2 InFront front.push( intersection ) front.push( p2 ) back.push( intersection ) case p1 InFront and p2 OnPlane front.push( p2 ) case p1 OnPlane and p2 OnPlane front.push( p2 ) case p1 Behind and p2 OnPlane front.push( p2 ) back.push( p2 ) case p1 InFront and p2 Behind front.push( intersection ) back.push( intersection ) back.push( p2 ) case p1 OnPlane and p2 Behind back.push( p1 ) back.push( p2 ) case p1 Behind and p2 Behind back.push( p2 )
Un'implementazione di questi nove casi potrebbe essere simile alla seguente (derivata da Real-Time Collision Detection di Ericson):
// Divide un poligono a metà lungo un piano di divisione usando un algoritmo di ritaglio // chiama Sutherland-Hodgman clipping // Risorsa: Pagina 367 di Ericson (rilevamento collisioni in tempo reale) void SutherlandHodgman (const Vec2 & n, f32 d, const Poly * poly, std :: vector * out) Poly frontPoly; Poly backPoly; uint32 s = poly-> vertices.size (); Vec2 a = poli-> vertici [s - 1]; f32 da = Dot (n, a) - d; per (uint32 i = 0; i < s; ++i) Vec2 b = poly->vertici [i]; f32 db = Dot (n, b) - d; if (InFront (b)) if (Behind (a)) Vec2 i = Intersect (b, a, db, da); frontPoly.vertices.push_back (i); backPoly.vertices.push_back (i); frontPoly.vertices.push_back (b); else if (Behind (b)) if (InFront (a)) Vec2 i = Intersect (a, b, da, db); frontPoly.vertices.push_back (i); backPoly.vertices.push_back (i); else if (On (a)) backPoly.vertices.push_back (a); backPoly.vertices.push_back (b); else frontPoly.vertices.push_back (b); if (On (a)) backPoly.vertices.push_back (b); a = b; da = db; if (frontPoly.vertices.size ()) out-> push_back (frontPoly); if (backPoly.vertices.size ()) out-> push_back (backPoly);
Ecco un esempio di Sutherland-Hodgman in azione:
Vale la pena notare che i poligoni finali possono essere visualizzati come un elenco di vertici con il formato di una ventola a triangolo.
C'è un problema di cui dovresti essere a conoscenza: quando si calcola un punto di intersezione di ab e un piano di scissione, questo punto ne soffre quantizzazione numerica. Ciò significa che qualsiasi valore di intersezione è un'approssimazione del valore di intersezione effettivo. Significa anche che il punto di intersezione ba non è numericamente lo stesso; una piccola deriva numerica produrrà in realtà due valori diversi!
Esempio di una fessura visibile tra i triangoli a causa di un ritaglio inconsistente (immagine ispirata al libro di Rilevamento collisioni in tempo reale di Ericson). Una routine di clipping ingenuo può commettere un grosso errore di calcolo dei punti di intersezione alla cieca, il che può provocare giunzioni a T o altri spazi vuoti nella geometria. Per evitare questo problema, è necessario utilizzare un orientamento di intersezione coerente. Per convenzione, i punti devono essere ritagliati da un lato all'altro di un piano. Questo rigoroso ordine di intersezione assicura che lo stesso punto di intersezione sia calcolato e risolverà potenziali spazi vuoti nella geometria (come mostrato nell'immagine sopra, c'è un risultato di ritaglio coerente sulla destra).
Per rendere effettivamente le trame su forme divise (magari quando si dividono gli sprite), è necessario comprendere le coordinate UV. Una discussione completa sulle coordinate UV e sulla mappatura delle texture è ben oltre lo scopo di questo articolo, ma se hai già questa comprensione, dovrebbe essere facile trasformare i punti di intersezione in uno spazio UV.
Per favore, comprendi che una trasformazione dallo spazio mondiale allo spazio UV richiede un cambio di base trasformata. Lascerò le trasformazioni UV come esercizio per il lettore!
In questo tutorial, abbiamo esaminato alcune semplici tecniche di algebra lineare per affrontare il problema della divisione dinamica di forme generiche. Ho anche affrontato alcuni problemi di robustezza numerica. Ora dovresti essere in grado di implementare il tuo codice di suddivisione della forma, o utilizzare la sorgente di dimostrazione, per ottenere molti effetti o funzionalità avanzate e interessanti per la programmazione generale del gioco.
Accentsconagua