Esercitazione sulla fisica dei videogiochi - Parte II: Rilevamento delle collisioni per oggetti solidi

Questa è la parte II della nostra serie in tre parti sulla fisica dei videogiochi. Per il resto di questa serie, vedere:

Parte I: Introduzione alla dinamica del corpo rigido
Parte III: Simulazione di corpi rigidi vincolati

Nella parte I di questa serie, abbiamo esplorato i corpi rigidi e i loro movimenti. In quella discussione, tuttavia, gli oggetti non interagivano tra loro. Senza alcun lavoro aggiuntivo, i corpi rigidi simulati possono passare l'uno attraverso l'altro o "compenetrare", il che è indesiderabile nella maggior parte dei casi.

Per simulare in modo più realistico il comportamento degli oggetti solidi, dobbiamo controllare se si scontrano tra loro ogni volta che si muovono e, se lo fanno, dobbiamo fare qualcosa al riguardo, come applicare forze che cambiano le loro velocità, quindi che si muoveranno nella direzione opposta. È qui che la comprensione della fisica delle collisioni è particolarmente importante per gli sviluppatori di giochi.

Nella parte II, tratteremo la fase di rilevamento delle collisioni, che consiste nel trovare coppie di corpi che entrano in collisione tra un numero possibilmente elevato di corpi sparsi in un mondo 2D o 3D. Nella prossima e ultima puntata parleremo di più di "risolvere" queste collisioni per eliminare le compenetazioni.

Per una rassegna dei concetti di algebra lineare a cui si fa riferimento in questo articolo, puoi fare riferimento al corso accelerato di algebra lineare nella Parte I.

Fisica delle collisioni nei videogiochi

Nel contesto delle simulazioni di corpi rigidi, si verifica una collisione quando le forme di due corpi rigidi si intersecano o quando la distanza tra queste forme scende al di sotto di una piccola tolleranza.

Se abbiamo n corpi nella nostra simulazione, la complessità computazionale del rilevamento delle collisioni con i test a coppie è O ( n 2 ) , un numero che fa rabbrividire gli informatici. Il numero di test a coppie aumenta quadraticamente con il numero di corpi e determinare se due forme, in posizioni e orientamenti arbitrari, si scontrano già non è economico. Per ottimizzare il processo di rilevamento delle collisioni, lo dividiamo generalmente in due fasi: fase ampia e fase stretta .

La fase ampia è responsabile della ricerca di coppie di corpi rigidi potenzialmente in collisione, e dell'esclusione delle coppie che non sono certamente in collisione, dall'intero insieme di corpi che sono nella simulazione. Questo passaggio deve essere in grado di scalare molto bene con il numero di corpi rigidi per essere sicuri di rimanere ben al di sotto della complessità temporale O ( n 2 ) . Per ottenere ciò, questa fase utilizza generalmente la partizione dello spazio accoppiata a volumi di delimitazione che stabiliscono un limite superiore per la collisione.

La fase stretta opera sulle coppie di corpi rigidi trovati dalla fase ampia che potrebbero entrare in collisione. È un passaggio di raffinamento in cui determiniamo se le collisioni stanno effettivamente avvenendo e, per ogni collisione trovata, calcoliamo i punti di contatto che verranno utilizzati per risolvere le collisioni in seguito.

Nelle prossime sezioni parleremo di alcuni algoritmi che possono essere utilizzati nella fase ampia e nella fase stretta.

Fase ampia

Nell'ampia fase della fisica delle collisioni per i videogiochi, dobbiamo identificare quali coppie di corpi rigidi potrebbero entrare in collisione. Questi corpi potrebbero avere forme complesse come poligoni e poliedri e ciò che possiamo fare per accelerare questo è utilizzare una forma più semplice per racchiudere l'oggetto. Se questi volumi di delimitazione non si intersecano, anche le forme effettive non si intersecano. Se si intersecano, le forme effettive potrebbero intersecarsi.

Alcuni tipi popolari di volumi di delimitazione sono i riquadri di delimitazione orientati (OBB), i cerchi in 2D e le sfere in 3D. Diamo un'occhiata a uno dei volumi di delimitazione più semplici: riquadri di delimitazione allineati agli assi (AABB) .

Gli AABB ottengono molto amore dai programmatori di fisica perché sono semplici e offrono buoni compromessi. Un AABB bidimensionale può essere rappresentato da una struttura come questa nel linguaggio C:

 typedef struct { float x; float y; } Vector2; typedef struct { Vector2 min; Vector2 max; } AABB;

Il campo min rappresenta la posizione dell'angolo inferiore sinistro della casella e il campo max rappresenta l'angolo superiore destro.

Per verificare se due AABB si intersecano, dobbiamo solo scoprire se le loro proiezioni si intersecano su tutti gli assi delle coordinate:

 BOOL TestAABBOverlap(AABB* a, AABB* b) { float d1x = b->min.x - a->max.x; float d1y = b->min.y - a->max.y; float d2x = a->min.x - b->max.x; float d2y = a->min.y - b->max.y; if (d1x > 0.0f || d1y > 0.0f) return FALSE; if (d2x > 0.0f || d2y > 0.0f) return FALSE; return TRUE; }

Questo codice ha la stessa logica della funzione b2TestOverlap del motore Box2D (versione 2.3.0). Calcola la differenza tra il min e il max di entrambi gli AABB, in entrambi gli assi, in entrambi gli ordini. Se uno di questi valori è maggiore di zero, gli AABB non si intersecano.

Anche se un test di sovrapposizione AABB è economico, non sarà di grande aiuto se eseguiamo ancora test a coppie per ogni possibile coppia poiché abbiamo ancora la complessità temporale O ( n 2 ) indesiderabile. Per ridurre al minimo il numero di test di sovrapposizione AABB, possiamo utilizzare una sorta di partizionamento dello spazio , che funziona secondo gli stessi principi degli indici di database che velocizzano le query. (I database geografici, come PostGIS, utilizzano effettivamente strutture di dati e algoritmi simili per i loro indici spaziali.) In questo caso, tuttavia, gli AABB si sposteranno costantemente, quindi generalmente dobbiamo ricreare gli indici dopo ogni passaggio della simulazione.

Esistono numerosi algoritmi di partizionamento dello spazio e strutture di dati che possono essere utilizzati a tale scopo, come griglie uniformi, quadtree in 2D, octres in 3D e hashing spaziale. Diamo un'occhiata più da vicino a due popolari algoritmi di partizionamento spaziale: sort and sweep e BVH (Bounding Volume Hierarchies).

L'algoritmo Sort and Sweep

Il metodo sort and sweep (in alternativa noto come sweep and prune ) è una delle scelte preferite dai programmatori di fisica per l'uso nella simulazione di corpi rigidi. Il motore Bullet Physics, ad esempio, ha un'implementazione di questo metodo nella classe btAxisSweep3 .

La proiezione di un AABB su un singolo asse di coordinate è essenzialmente un intervallo [ b , e ] (cioè inizio e fine). Nella nostra simulazione avremo molti corpi rigidi, e quindi molti AABB, e questo significa molti intervalli. Vogliamo scoprire quali intervalli si intersecano.

Nell'algoritmo di ordinamento e scansione, inseriamo tutti i valori be e in un unico elenco e lo ordiniamo in ordine crescente in base ai loro valori scalari. Quindi spostiamo o attraversiamo l'elenco. Ogni volta che viene rilevato un valore b , l'intervallo corrispondente viene archiviato in un elenco separato di intervalli attivi e ogni volta che viene rilevato un valore e , l'intervallo corrispondente viene rimosso dall'elenco degli intervalli attivi. In ogni momento, tutti gli intervalli attivi si intersecano. (Per i dettagli, consulta la tesi di dottorato di David Baraff, p. 52. Suggerisco di utilizzare questo strumento online per visualizzare il file postscript.) L'elenco degli intervalli può essere riutilizzato in ogni fase della simulazione, dove possiamo riordinare in modo efficiente questo elenco utilizza l'ordinamento per inserimento, che è utile per ordinare elenchi quasi ordinati.

In due e tre dimensioni, l'esecuzione dell'ordinamento e dello sweep, come descritto sopra, su un singolo asse di coordinate ridurrà il numero di test di intersezione AABB diretti che devono essere eseguiti, ma il guadagno potrebbe essere migliore su un asse di coordinate rispetto a un altro. Pertanto, vengono implementate variazioni più sofisticate dell'algoritmo di ordinamento e scansione. Nel suo libro Real-Time Collision Detection (pagina 336), Christer Ericson presenta una variazione efficiente in cui memorizza tutti gli AABB in un unico array e per ogni esecuzione dell'ordinamento e dello sweep, viene scelto un asse di coordinate e l'array viene ordinato per il valore min degli AABB nell'asse scelto, utilizzando quicksort. Quindi, l'array viene attraversato e vengono eseguiti i test di sovrapposizione AABB. Per determinare l'asse successivo che dovrebbe essere utilizzato per l'ordinamento, viene calcolata la varianza del centro degli AABB e viene scelto l'asse con la varianza maggiore per il passaggio successivo.

Alberi dinamici del volume di delimitazione

Un altro utile metodo di partizionamento spaziale è l' albero del volume di delimitazione dinamico , noto anche come Dbvt . Questo è un tipo di gerarchia del volume di delimitazione .

Il Dbvt è un albero binario in cui ogni nodo ha un AABB che delimita tutti gli AABB dei suoi figli. Gli AABB dei corpi rigidi stessi si trovano nei nodi foglia. Tipicamente, un Dbvt viene "interrogato" fornendo l'AABB per il quale vorremmo rilevare le intersezioni. Questa operazione è efficiente perché i figli dei nodi che non intersecano l'AABB interrogato non devono essere testati per la sovrapposizione. In quanto tale, una query di collisione AABB inizia dalla radice e continua ricorsivamente attraverso l'albero solo per i nodi AABB che si intersecano con l'AABB richiesto. L'albero può essere bilanciato attraverso le rotazioni dell'albero, come in un albero AVL.

Box2D ha una sofisticata implementazione di Dbvt nella classe b2DynamicTree . La classe b2BroadPhase è responsabile dell'esecuzione della fase ampia e utilizza un'istanza di b2DynamicTree per eseguire query AABB.

Fase stretta

Dopo l'ampia fase della fisica delle collisioni dei videogiochi, abbiamo un insieme di coppie di corpi rigidi potenzialmente in collisione. Pertanto, per ciascuna coppia, data la forma, la posizione e l'orientamento di entrambi i corpi, è necessario scoprire se sono effettivamente in collisione; se si intersecano o se la loro distanza scende al di sotto di un piccolo valore di tolleranza. Abbiamo anche bisogno di sapere quali sono i punti di contatto tra i corpi in collisione, poiché ciò è necessario per risolvere le collisioni in un secondo momento.

Forme convesse e concave

Come regola generale della fisica dei videogiochi, non è banale determinare se due forme arbitrarie si intersecano o calcolare la distanza tra di loro. Tuttavia, una proprietà che è di fondamentale importanza nel determinare quanto sia difficile è la convessità della forma. Le forme possono essere convesse o concave e le forme concave sono più difficili da lavorare, quindi abbiamo bisogno di alcune strategie per affrontarle.

In una forma convessa, un segmento di linea tra due punti qualsiasi all'interno della forma cade sempre completamente all'interno della forma. Tuttavia, per una forma concava (o "non convessa"), lo stesso non vale per tutti i possibili segmenti di linea che collegano i punti nella forma. Se riesci a trovare almeno un segmento di linea che non rientra nella forma, allora la forma è concava.

Dal punto di vista computazionale, è auspicabile che tutte le forme siano convesse in una simulazione, poiché abbiamo molti potenti algoritmi di test di distanza e intersezione che funzionano con forme convesse. Tuttavia, non tutti gli oggetti saranno convessi e di solito li aggiriamo in due modi: scafo convesso e decomposizione convessa.

Lo scafo convesso di una forma è la più piccola forma convessa che la contiene completamente. Per un poligono concavo in due dimensioni, sarebbe come piantare un chiodo su ciascun vertice e avvolgere un elastico attorno a tutti i chiodi. Per calcolare lo scafo convesso per un poligono o poliedro, o più in generale, per un insieme di punti, un buon algoritmo da utilizzare è l'algoritmo quickhull , che ha una complessità temporale media di O ( n log n ) .

Ovviamente, se utilizziamo uno scafo convesso per rappresentare un oggetto concavo, perderà le sue proprietà concave. Comportamenti indesiderati, come collisioni "fantasma", possono diventare evidenti, poiché l'oggetto avrà ancora una rappresentazione grafica concava. Ad esempio, un'auto di solito ha una forma concava e se usiamo uno scafo convesso per rappresentarla fisicamente e poi mettiamo una scatola su di essa, la scatola potrebbe sembrare fluttuare nello spazio sopra.

In generale, gli scafi convessi sono spesso abbastanza buoni da rappresentare oggetti concavi, sia perché le collisioni irrealistiche non sono molto evidenti, sia perché le loro proprietà concave non sono essenziali per qualsiasi cosa venga simulata. In alcuni casi, tuttavia, potremmo voler fare in modo che l'oggetto concavo si comporti fisicamente come una forma concava. Ad esempio, se utilizziamo uno scafo convesso per rappresentare fisicamente una ciotola, non saremo in grado di metterci nulla al suo interno. Gli oggetti galleggeranno sopra di esso. In questo caso, possiamo utilizzare una scomposizione convessa della forma concava.

Gli algoritmi di decomposizione convessa ricevono una forma concava e restituiscono un insieme di forme convesse la cui unione è identica alla forma concava originale. Alcune forme concave possono essere rappresentate solo da un gran numero di forme convesse e queste potrebbero diventare proibitivamente costose da calcolare e utilizzare. Tuttavia, un'approssimazione è spesso abbastanza buona e quindi algoritmi come V-HACD producono un piccolo insieme di poliedri convessi da un poliedro concavo.

In molti casi di fisica delle collisioni, tuttavia, la scomposizione convessa può essere eseguita a mano, da un artista. Ciò elimina la necessità di tassare le prestazioni con algoritmi di scomposizione. Poiché le prestazioni sono uno degli aspetti più importanti nelle simulazioni in tempo reale, è generalmente una buona idea creare rappresentazioni fisiche molto semplici per oggetti grafici complessi. L'immagine seguente mostra una possibile scomposizione convessa di un'auto 2D utilizzando nove forme convesse.

Test per le intersezioni - Il teorema dell'asse di separazione

Il teorema dell'asse di separazione (SAT) afferma che due forme convesse non si intersecano se e solo se esiste almeno un asse in cui le proiezioni ortogonali delle forme su questo asse non si intersecano.

Di solito è visivamente più intuitivo trovare una linea in 2D o un piano in 3D che separi le due forme, il che è effettivamente lo stesso principio. Un vettore ortogonale alla linea in 2D, o il vettore normale del piano in 3D, può essere utilizzato come "asse di separazione".

I motori della fisica di gioco hanno diverse classi di forme, come cerchi (sfere in 3D), bordi (un singolo segmento di linea) e poligoni convessi (poliedri in 3D). Per ogni coppia di tipo di forma, hanno uno specifico algoritmo di rilevamento delle collisioni. Il più semplice di questi è probabilmente l'algoritmo cerchio-cerchio:

 typedef struct { float centerX; float centerY; float radius; } Circle; bool CollideCircles(Circle *cA, Circle *cB) { float x = cA->centerX - cB->centerX; float y = cA->centerY - cB->centerY; float centerDistanceSq = x * x + y * y; // squared distance float radius = cA->radius + cB->radius; float radiusSq = radius * radius; return centerDistanceSq <= radiusSq; }

Anche se il SAT si applica ai cerchi, è molto più semplice controllare se la distanza tra i loro centri è inferiore alla somma dei loro raggi. Per questo motivo, il SAT viene utilizzato nell'algoritmo di rilevamento delle collisioni per coppie specifiche di classi di forme, come poligoni convessi contro poligoni convessi (o poliedri in 3D).

Per ogni coppia di forme, c'è un numero infinito di assi che possiamo testare per la separazione. Pertanto, determinare quale asse testare per primo è fondamentale per un'implementazione SAT efficiente. Fortunatamente, quando si verifica una collisione di una coppia di poligoni convessi, è possibile utilizzare le normali agli spigoli come potenziali assi di separazione. Il vettore normale n di uno spigolo è perpendicolare al vettore spigolo e punta al di fuori del poligono. Per ogni spigolo di ogni poligono, dobbiamo solo scoprire se tutti i vertici dell'altro poligono sono davanti allo spigolo.

Se un test ha esito positivo, ovvero se, per qualsiasi spigolo, tutti i vertici dell'altro poligono sono davanti ad esso, i poligoni non si intersecano. L'algebra lineare fornisce una formula semplice per questo test: dato un bordo sulla prima forma con i vertici aeb e un vertice v sull'altra forma, se ( v - a ) · n è maggiore di zero, allora il vertice è davanti del bordo.

Per i poliedri, possiamo usare le normali delle facce e anche il prodotto incrociato di tutte le combinazioni di spigoli di ciascuna forma. Sembrano molte cose da testare; tuttavia, per velocizzare le cose, possiamo memorizzare nella cache l'ultimo asse di separazione che abbiamo utilizzato e provare a riutilizzarlo nei passaggi successivi della simulazione. Se l'asse di separazione memorizzato nella cache non separa più le forme, possiamo cercare un nuovo asse partendo da facce o bordi adiacenti alla faccia o al bordo precedente. Funziona perché i corpi spesso non si muovono o ruotano molto tra i passaggi.

Box2D utilizza SAT per verificare se due poligoni convessi si intersecano nel suo algoritmo di rilevamento delle collisioni poligono-poligono in b2CollidePolygon.cpp.

Distanza di calcolo - L'algoritmo Gilbert-Johnson-Keerthi

In molti casi di fisica delle collisioni, vogliamo considerare gli oggetti in collisione non solo se si intersecano effettivamente, ma anche se sono molto vicini tra loro, il che richiede di conoscere la distanza tra loro. L'algoritmo Gilbert-Johnson-Keerthi (GJK) calcola la distanza tra due forme convesse e anche i loro punti più vicini. È un algoritmo elegante che funziona con una rappresentazione implicita di forme convesse attraverso funzioni di supporto, somme di Minkowski e semplici, come spiegato di seguito.

Funzioni di supporto

Una funzione di supporto s A ( d ) restituisce un punto sul confine della forma A che ha la proiezione più alta sul vettore d . Matematicamente, ha il prodotto punto più alto con d . Questo è chiamato punto di supporto e questa operazione è anche nota come mappatura del supporto . Geometricamente, questo punto è il punto più lontano della forma nella direzione di d .

Trovare un punto di appoggio su un poligono è relativamente facile. Per un punto di supporto per il vettore d , devi solo scorrere i suoi vertici e trovare quello che ha il prodotto scalare più alto con d , in questo modo:

 Vector2 GetSupport(Vector2 *vertices, int count, Vector2 d) { float highest = -FLT_MAX; Vector2 support = (Vector2){0, 0}; for (int i = 0; i < count; ++i) { Vector2 v = vertices[i]; float dot = vx * dx + vy * dy; if (dot > highest) { highest = dot; support = v; } } return support; }

Tuttavia, il vero potere di una funzione di supporto è che rende facile lavorare con forme come coni, cilindri ed ellissi, tra le altre. È piuttosto difficile calcolare direttamente la distanza tra tali forme e senza un algoritmo come GJK di solito dovresti discretizzarle in un poligono o poliedro per semplificare le cose. Tuttavia, ciò potrebbe causare ulteriori problemi perché la superficie di un poliedro non è liscia come la superficie, ad esempio, di una sfera, a meno che il poliedro non sia molto dettagliato, il che può portare a scarse prestazioni durante il rilevamento delle collisioni. Potrebbero manifestarsi anche altri effetti collaterali indesiderati; ad esempio, una sfera "poliedrica" ​​potrebbe non rotolare uniformemente.

Per ottenere un punto di appoggio per una sfera centrata sull'origine, dobbiamo solo normalizzare d (ovvero calcolare d / || d || , che è un vettore di lunghezza 1 (lunghezza unitaria) che punta ancora nella stessa direzione di d ) e poi lo moltiplichiamo per il raggio della sfera.

Dai un'occhiata all'articolo di Gino van den Bergen per trovare altri esempi di funzioni di supporto per cilindri e coni, tra le altre forme.

I nostri oggetti, ovviamente, verranno spostati e ruotati dall'origine nello spazio di simulazione, quindi dobbiamo essere in grado di calcolare i punti di supporto per una forma trasformata. Usiamo una trasformazione affine T ( x ) = R x + c per spostare e ruotare i nostri oggetti, dove c è il vettore di spostamento e R è la matrice di rotazione . Questa trasformazione prima ruota l'oggetto attorno all'origine, quindi lo traduce. La funzione di supporto per una forma trasformata A è:

Somme Minkowski

La somma Minkowski di due forme A e B è definita come:

Ciò significa che calcoliamo la somma di tutti i punti contenuti in A e B . Il risultato è come gonfiare A con B .

Allo stesso modo, definiamo la differenza di Minkowski come:

che possiamo anche scrivere come somma Minkowski di A con -B :

Per A e B convessi, anche A⊕B è convesso.

Una proprietà utile della differenza di Minkowski è che se contiene l'origine dello spazio, le forme si intersecano, come si può vedere nell'immagine precedente. Perché? Perché se due forme si intersecano, hanno almeno un punto in comune, che si trova nella stessa posizione nello spazio, e la loro differenza è il vettore zero, che in realtà è l'origine.

Un'altra caratteristica interessante della differenza di Minkowski è che se non contiene l'origine, la distanza minima tra l'origine e la differenza di Minkowski è la distanza tra le forme.

La distanza tra due forme è definita come:

In altre parole, la distanza tra A e B è la lunghezza del vettore più corto che va da A a B . Questo vettore è contenuto in A⊖B ed è quello di lunghezza minore, che di conseguenza è quello più vicino all'origine.

In genere non è semplice costruire esplicitamente la somma di Minkowski di due forme. Fortunatamente, possiamo usare anche la mappatura del supporto qui, poiché:

Simplex

L'algoritmo GJK ricerca iterativamente il punto sulla differenza di Minkowski più vicino all'origine. Lo fa costruendo una serie di simplessi più vicini all'origine in ogni iterazione. Un simplesso – o più specificamente, un k-simplex per un intero k – è lo scafo convesso di k + 1 punti affinemente indipendenti in uno spazio k-dimensionale. Cioè, se per due punti non devono coincidere, per tre punti inoltre non devono giacere sulla stessa linea, e se abbiamo quattro punti anche loro non devono giacere sullo stesso piano. Quindi, il 0-simplex è un punto, il 1-simplex è un segmento di linea, il 2-simplex è un triangolo e il 3-simplex è un tetraedro. Se rimuoviamo un punto da un simplex ne decrementiamo la dimensionalità di uno, e se aggiungiamo un punto a un simplex incrementiamo la sua dimensionalità di uno.

GJK in azione

Mettiamo tutto insieme per vedere come funziona GJK. Per determinare la distanza tra due forme A e B , iniziamo prendendo la loro differenza di Minkowski A⊖B . Stiamo cercando il punto più vicino all'origine sulla forma risultante, poiché la distanza da questo punto è la distanza tra le due forme originali. Scegliamo un punto v in A⊖B , che sarà la nostra approssimazione della distanza. Definiamo anche un insieme di punti vuoto W , che conterrà i punti nel simplesso del test corrente.

Quindi entriamo in un ciclo. Iniziamo ottenendo il punto di appoggio w = s A⊖B (- v ) , il punto su A⊖B la cui proiezione su v è più vicina all'origine.

Se || w || non è molto diverso da || v || e l'angolo tra loro non è cambiato molto (secondo alcune tolleranze predefinite), significa che l'algoritmo è convergente e possiamo restituire || v || come la distanza.

Altrimenti, aggiungiamo w a W . Se lo scafo convesso di W (cioè il simplesso) contiene l'origine, le forme si intersecano, e questo significa anche che abbiamo finito. Altrimenti, troviamo il punto nel simplesso più vicino all'origine e quindi reimpostamo v come questa nuova approssimazione più vicina. Infine, rimuoviamo tutti i punti in W che non contribuiscono al calcolo del punto più vicino. (Ad esempio, se abbiamo un triangolo e il punto più vicino all'origine si trova in uno dei suoi bordi, possiamo rimuovere il punto da W che non è un vertice di questo bordo.) Quindi ripetiamo questi stessi passaggi fino a quando l'algoritmo converge.

L'immagine successiva mostra un esempio di quattro iterazioni dell'algoritmo GJK. L'oggetto blu rappresenta la differenza di Minkowski A⊖B e il vettore verde è v . Puoi vedere qui come v si concentra sul punto più vicino all'origine.

Per una spiegazione dettagliata e approfondita dell'algoritmo GJK, consulta il documento A Fast and Robust GJK Implementation for Collision Detection of Convex Objects , di Gino van den Bergen. Il blog per il motore fisico dyn4j ha anche un ottimo post su GJK.

Box2D ha un'implementazione dell'algoritmo GJK in b2Distance.cpp, nella funzione b2Distance . Utilizza GJK solo durante il calcolo dell'impatto nel suo algoritmo per il rilevamento continuo delle collisioni (un argomento che discuteremo più avanti).

Il motore fisico Chimpunk utilizza GJK per tutto il rilevamento delle collisioni e la sua implementazione è in cpCollision.c, nella funzione GJK . Se l'algoritmo GJK segnala l'intersezione, deve comunque sapere quali sono i punti di contatto, insieme alla profondità di penetrazione. Per fare ciò, utilizza l'algoritmo Expanding Polytope, che esploreremo in seguito.

Determinazione della profondità di penetrazione - L'algoritmo del politopo in espansione

Come detto sopra, se le forme A e B si intersecano, GJK genererà un simplesso W che contiene l'origine, all'interno della differenza di Minkowski A⊖B . In questa fase, sappiamo solo che le forme si intersecano, ma nella progettazione di molti sistemi di rilevamento delle collisioni, è desiderabile essere in grado di calcolare quanta intersezione abbiamo e quali punti possiamo usare come punti di contatto, in modo che gestiamo la collisione in modo realistico. L' Expanding Polytope Algorithm (EPA) ci consente di ottenere quell'informazione, partendo da dove GJK si era interrotto: con un simplex che contiene l'origine.

La profondità di penetrazione è la lunghezza del vettore di traslazione minima (MTV), che è il vettore più piccolo lungo il quale possiamo traslare una forma intersecante per separarla dall'altra forma.

Quando due forme si intersecano, la loro differenza di Minkowski contiene l'origine e il punto sul confine della differenza di Minkowski che è più vicino all'origine è l'MTV. L'algoritmo EPA trova quel punto espandendo il simplesso che GJK ci ha fornito in un poligono; suddividendo successivamente i suoi bordi con nuovi vertici.

Per prima cosa, troviamo il bordo del simplesso più vicino all'origine e calcoliamo il punto di supporto nella differenza di Minkowski in una direzione che è normale al bordo (cioè perpendicolare ad esso e che punta al di fuori del poligono). Quindi dividiamo questo bordo aggiungendo questo punto di supporto. Ripetiamo questi passaggi finché la lunghezza e la direzione del vettore non cambiano molto. Una volta che l'algoritmo converge, abbiamo l'MTV e la profondità di penetrazione.

Usando GJK in combinazione con EPA, otteniamo una descrizione dettagliata della collisione, non importa se gli oggetti si stanno già intersecando o semplicemente abbastanza vicini da essere considerata una collisione.

L'algoritmo EPA è descritto nel documento Proximity Query and Penetration Depth Computation on 3D Game Objects , scritto anche da Gino van den Bergen. Il blog dyn4j ha anche un post sull'EPA.

Rilevamento continuo delle collisioni

Le tecniche di fisica dei videogiochi presentate finora eseguono il rilevamento delle collisioni per un'istantanea statica della simulazione. Questo è chiamato rilevamento di collisione discreto e ignora ciò che accade tra i passaggi precedenti e correnti. Per questo motivo, alcune collisioni potrebbero non essere rilevate, soprattutto per oggetti in rapido movimento. Questo problema è noto come tunneling .

Le tecniche di rilevamento continuo delle collisioni tentano di scoprire quando due corpi si sono scontrati tra la fase precedente e quella corrente della simulazione. Calcolano il tempo dell'impatto , quindi possiamo tornare indietro nel tempo ed elaborare la collisione in quel punto.

Il tempo di impatto (o tempo di contatto) t c è l'istante in cui la distanza tra due corpi è zero. Se possiamo scrivere una funzione per la distanza tra due corpi nel tempo, ciò che vogliamo trovare è la radice più piccola di questa funzione. Pertanto, il tempo di calcolo dell'impatto è un problema di ricerca delle radici .

Per il calcolo dell'impatto, consideriamo lo stato (posizione e orientamento) del corpo nella fase precedente all'istante t i -1 e nella fase corrente all'istante t i . Per semplificare le cose, assumiamo un movimento lineare tra i passaggi.

Semplifichiamo il problema assumendo che le forme siano dei cerchi. Per due cerchi C 1 e C 2 , di raggio r 1 e r 2 , dove il loro centro di massa x 1 e x 2 coincidono con il loro baricentro (cioè ruotano naturalmente attorno al loro centro di massa), possiamo scrivere la funzione distanza come:

Considerando il moto lineare tra passi, possiamo scrivere la seguente funzione per la posizione di C 1 da t i -1 a t i

È un'interpolazione lineare da x 1 ( t i -1 ) a x 1 ( t i ) . Lo stesso può essere fatto per x 2 . Per questo intervallo possiamo scrivere un'altra funzione di distanza:

Imposta questa espressione uguale a zero e ottieni un'equazione quadratica su t . Le radici possono essere trovate direttamente usando la formula quadratica. Se i cerchi non si intersecano, la formula quadratica non avrà una soluzione. Se lo fanno, potrebbe risultare in una o due radici. Se ha solo una radice, quel valore è il tempo di impatto. Se ha due radici, la più piccola è il momento dell'impatto e l'altra è il momento in cui i cerchi si separano. Si noti che il tempo di impatto qui è un numero compreso tra 0 e 1. Non è un tempo espresso in secondi; è solo un numero che possiamo usare per interpolare lo stato dei corpi nel luogo preciso in cui è avvenuta la collisione.

Rilevamento continuo delle collisioni per non cerchi

Scrivere una funzione di distanza per altri tipi di forme è difficile, principalmente perché la loro distanza dipende dal loro orientamento. Per questo motivo, generalmente utilizziamo algoritmi iterativi che spostano gli oggetti sempre più vicini a ogni iterazione fino a quando non sono abbastanza vicini da essere considerati in collisione.

L'algoritmo di avanzamento conservativo sposta i corpi in avanti (e li ruota) in modo iterativo. In ogni iterazione calcola un limite superiore per lo spostamento. L'algoritmo originale è presentato nella tesi di dottorato di Brian Mirtich (sezione 2.3.2), che considera il movimento balistico dei corpi. Questo articolo di Erwin Coumans (l'autore del Bullet Physics Engine) presenta una versione più semplice che utilizza velocità lineari e angolari costanti.

L'algoritmo calcola i punti più vicini tra le forme A e B , disegna un vettore da un punto all'altro e proietta la velocità su questo vettore per calcolare un limite superiore per il movimento. Garantisce che nessun punto del corpo si sposti oltre questa proiezione. Quindi fa avanzare i corpi di questa quantità e si ripete finché la distanza non scende sotto un piccolo valore di tolleranza.

Potrebbero essere necessarie troppe iterazioni per convergere in alcuni casi, ad esempio, quando la velocità angolare di uno dei corpi è troppo alta.

Risoluzione delle collisioni

Una volta rilevata una collisione, è necessario modificare i movimenti degli oggetti in collisione in modo realistico, ad esempio facendoli rimbalzare l'uno sull'altro. Nella prossima e ultima puntata di queste teorie, discuteremo alcuni metodi popolari per risolvere le collisioni nei videogiochi.

Riferimenti

Se sei interessato ad ottenere una comprensione più profonda della fisica delle collisioni come algoritmi e tecniche di rilevamento delle collisioni, il libro Real-Time Collision Detection , di Christer Ericson, è un must.

Poiché il rilevamento delle collisioni si basa fortemente sulla geometria, l'articolo di Toptal Geometria computazionale in Python: dalla teoria all'applicazione è un'eccellente introduzione all'argomento.