Calcolare la collisione di 2 triangoli in 3D

[cionci]

Originariamente inviato da banryu79

Potresti prima, per esempio, decidere che tutti i tringoli che formano una "montagna" (triangoli la cui coordinata Y di uno dei vertici è > di un certo valore) li raggruppi calcolandoti il bounding box e su quello fai il un primo controllo di collisione, se c'è la collisione col bounding box allora passi a controllare i singoli triangoli che lo formano, sennò nisba e hai risparmiato del tempo...

Concordo con quello scritto da banryu79: la bounding box serve, ma non tanto per determinare la collisione, ma per sapere su quali triangoli applicare l'algoritmo di collisione
Ad esempio, le bounding box di due oggetti collidono...bisogna applicare l'algoritmo di collisione a tutti i triangoli di uno e dell'altro oggetto che sono nell'intersezione delle due bounding box.
L'algoritmo è preciso quanto andando ad applicare la forza bruta su tutti i triangoli.

[okay]

Originariamente inviato da k0nt3

l'algoritmo linkato da wingman87 mi sembra ottimo.. ovviamente continuo a pensare che hai bisogno del computer della NASA per farlo girare. intanto ti consiglio di non testare tutti i triangoli, un punto di partenza potrebbe essere questo http://en.wikipedia.org/wiki/Binary_space_partitioning

Le tecniche di BSP quadtree e octree non c'èntrano nulla con le collisioni.

Il BSP come il quadtree servono per partizionare le mesh statiche. Il BSP si usa in ambienti chiusi e non è adatto per ambienti aperti mentre il quadtree e l'octree trovano il massimo per ambiente aperti.

In sostanza, per esempio il terreno da renderizzare (del 3d) in spazio aperto, invece di renderizzarlo tutto, con la tecnica quadtree si fa in modo di renderizzare solo i triangoli che rientranno nella "vista" la partizione appunto es: se il terreno è di 1000 triangoli e mi citrovo in mezzo renderizzo a video solo 10/15 triangoli risparmiando il raster della scheda video avendo performance migliori.

Queste tecniche con il collision detection non hanno nulla a che fare.

Mentre le collisioni sono fondamentali e sempre sono soggette a calcolo anche quando gli oggetti non si trovano nella vista o ad altro livello del game (AI)

[okay]

Originariamente inviato da cionci

Concordo con quello scritto da banryu79: la bounding box serve, ma non tanto per determinare la collisione, ma per sapere su quali triangoli applicare l'algoritmo di collisione

ciao

il migliore è la sfera... per ora

Ad esempio, le bounding box di due oggetti collidono...bisogna applicare l'algoritmo di collisione a tutti i triangoli di uno e dell'altro oggetto che sono nell'intersezione delle due bounding box.

Non è il caso di andare a confrontare tutti i triangoli dei 2 oggetti.
AABB e sfera
http://www.toymaker.info/Games/html/collisions.html

ma si controlla solo il box non tutti i triangoli stessa cosa con la sfera.
AABB o la sfera circondano l'oggetto mesh basta controllare i loro raggi e la distanza nello spazio 3d.

Anche se fosse costituito da milioni di triangoli non ci interessa scansionarli è inutile.

Il discorso è differente per un terreno (intanto da partizionare per essere ottimizzati (quadtree)) la sfera o il box deve calcolare una ipotetica linea che punti al terreno ed estrapolare da subito il triangolo colpito (una grande ottimizzazione) in quanto il terreno non è ne in un AABB o in una sfera...

[cionci]

Originariamente inviato da okay

Non è il caso di andare a confrontare tutti i triangoli dei 2 oggetti.

Lui ha detto che voleva qualcosa di più preciso della sfera o del bounding box. L'unico modo più preciso è andare a controllare l'intersezione dei triangoli. Visto che è computazionalmente impossibile andare a controllare tutti i triangoli (visto che mi sembrano molti), mescolare la bounding box con il controllo dei triangoli permette di ridurre notevolmente il numero di triangoli fra cui fare il test di intersezione.
Quindi:

- si testa l'intersezione delle bounding box di fra tutti gli oggetti
- per tutte le bounding box che si intersecano si determinano i triangoli che intersecano o sono contenuti nell'intersezione delle bounding box (inizialmente sono pochissimi, con l'avvicinarsi degli oggetti aumentano)
- per ogni triangolo selezionato dell'oggetto A, si effettua un test di intersezione con ogni triangolo selezionato dell'oggetto B, se c'è intersezione è avvenuta la collisione allora si impedisce lo spostamento riportandosi allo stato precedente dell'oggetto

[okay]

Originariamente inviato da cionci

mescolare la bounding box con il controllo dei triangoli permette di ridurre notevolmente il numero di triangoli fra cui fare il test di intersezione.

Ragionaci un attimo:
_ _
|_| |_| queste sono 2 scatole dove dentro ci sono 2 oggetto ognuno con tantissimi triangoli:

Il trucco è controllare gli 8 vertici della box1 con gli 8 vertici della box2 se questi collidono (e non coi triangoli delle mesh che sono "dentro" le box ) e verificare solo gli 8 vertici allora si c'è la collisione. In sostanza si controlla se collidono i box sui loro 8 vertici, dove dentro c'è la mesh (migliaia di triangoli) i triangoli degli oggetti non devono essere scansionati questo è il trucco...

Stessa cosa con la sfera che è meglio della box in quanto si ha la lunghezza del raggio per ogni oggetto molto meno ancora da verificare in confronto agli 8 vertici della box


jhon carmack ci ha fatto i miliardi... il tutto è + che preciso.

hai capito il trucco??

[cionci]

Ma io questo l'avevo capito. Il problema è che adottando solo la bounding box le collisioni non sono precise come le vuole IceCoder

Ad esempio:


Sfruttando solo le bounding box questa sarebbe una collisione. Secondo quanto vuole ottenere IceCoder questa non deve essere una collisione.
Con quello che dicevo io intendevo sfruttare l'intersezione delle bounding box per individuare i triangoli che potevano generare collisione ed effettuare il controllo solo su quelli.

[71104]

Originariamente inviato da okay

Ragionaci un attimo:
_ _
|_| |_| queste sono 2 scatole dove dentro ci sono 2 oggetto ognuno con tantissimi triangoli:

Il trucco è controllare gli 8 vertici della box1 con gli 8 vertici della box2 se questi collidono (e non coi triangoli delle mesh che sono "dentro" le box ) e verificare solo gli 8 vertici allora si c'è la collisione. In sostanza si controlla se collidono i box sui loro 8 vertici, dove dentro c'è la mesh (migliaia di triangoli) i triangoli degli oggetti non devono essere scansionati questo è il trucco...

Stessa cosa con la sfera che è meglio della box in quanto si ha la lunghezza del raggio per ogni oggetto molto meno ancora da verificare in confronto agli 8 vertici della box


jhon carmack ci ha fatto i miliardi... il tutto è + che preciso.

hai capito il trucco??

mio Dio... questo Fry deve essere un genio delle biotecnologie!!

[okay]

Originariamente inviato da cionci

Ma io questo l'avevo capito. Il problema è che adottando solo la bounding box le collisioni non sono precise come le vuole IceCoder

Ad esempio:


Sfruttando solo le bounding box questa sarebbe una collisione. Secondo quanto vuole ottenere IceCoder questa non deve essere una collisione.
Con quello che dicevo io intendevo sfruttare l'intersezione delle bounding box per individuare i triangoli che potevano generare collisione ed effettuare il controllo solo su quelli.

perfetto... allora ok.

Però per quanto riguarda i videogame si usa il tipo di collisioni (box o sfera) come hai postato nel grafico per gli oggetti dinamici.

Immagina 2 guerrieri che si scontrano... non vengono mai a contatto in quanto stanno ho dentro sfere o box.

Quello che vorrei capire (ma lui ha parlato di 2 aerei) e 2 aerei devono esere racchiusi dentro a "sfere"

Il discorso invece è differente, l'ho scritto nel post postando lo pseudo code, dove se si tratta di calpestare un terreno, una stanza, in sostanza essere un "character", "non si deve" usare ne il box ne la sfera per l'oggetto statico "LA MAPPA" per intenderci.

Edit: per cercare la precisione quello da fare è controllare i triangoli coinvolti nella collsione di tutti e 2 gli oggetti...ma non è un discorso per videogame ma + una soluzione "didattica" di studio personale.

[IceCoder]

Originariamente inviato da okay

perfetto... allora ok.

Però per quanto riguarda i videogame si usa il tipo di collisioni (box o sfera) come hai postato nel grafico per gli oggetti dinamici.

Immagina 2 guerrieri che si scontrano... non vengono mai a contatto in quanto stanno ho dentro sfere o box.

Quello che vorrei capire (ma lui ha parlato di 2 aerei) e 2 aerei devono esere racchiusi dentro a "sfere"

Il discorso invece è differente, l'ho scritto nel post postando lo pseudo code, dove se si tratta di calpestare un terreno, una stanza, in sostanza essere un "character", "non si deve" usare ne il box ne la sfera per l'oggetto statico "LA MAPPA" per intenderci.

Edit: per cercare la precisione quello da fare è controllare i triangoli coinvolti nella collsione di tutti e 2 gli oggetti...ma non è un discorso per videogame ma + una soluzione "didattica" di studio personale.

qui ti sbagli. il metodo illustrato da cionci (al quale non avevo pensato) è usato piu spesso di quanto immagini.

Pensa a 2 mesh: "uomo" e "proiettile".

se uomo sta fermo in piedi e proiettile lo sfiora al collo, uomo e proiettile collidono anche se effettivamente non si scontrano.

quindi ci sono 2 possibilità: o la bounding box + brute force
o dividere ogni mesh in pezzi e poi assemblarla durante il gioco (e questo è inutile) usando SOLO bounding box o sphere in base alla forma.

quindi uomo dovrebbe essere composto non da 1 mesh ma almeno da 7:

braccioD, braccioS, gambaS, gambaD, torso, collo, testa.

e questo non avrebbe senso.

[okay]

Originariamente inviato da IceCoder

qui ti sbagli. il metodo illustrato da cionci (al quale non avevo pensato) è usato piu spesso di quanto immagini.

Pensa a 2 mesh: "uomo" e "proiettile".

se uomo sta fermo in piedi e proiettile lo sfiora al collo, uomo e proiettile collidono anche se effettivamente non si scontrano.

quindi ci sono 2 possibilità: o la bounding box + brute force
o dividere ogni mesh in pezzi e poi assemblarla durante il gioco (e questo è inutile) usando SOLO bounding box o sphere in base alla forma.

quindi uomo dovrebbe essere composto non da 1 mesh ma almeno da 7:

braccioD, braccioS, gambaS, gambaD, torso, collo, testa.

e questo non avrebbe senso.

infatti è proprio così il procedimento:

un oggetto mesh tipo uomo è formato da + mesh.x ognuna delle quali è circondata dal suo box.

Più precisamente da box fisici che possono essere box, sfere o cilindri

[banryu79]

Scusatemi, io avevo capito che a IceCoder serviva un sistema per determinare la collisione tra questi due tipi di oggetti:

a) Montagna (terreno, sta ferma)

b) Scalatore (manichino antropomorfo, si muove)

Per cui proponevo il "raggruppamento" dei triangoli costituenti la Montagna in un BoundingBox (a mio avviso più adatto di una BoundingSphere per via della tipica forma con cui si sviluppa una Montagna).

Per lo Scalatore andrebbe anche bene una BoundingSphere: con questo semplice incapsulamento (Montagna->BBox & Scalatore-> BSphere) si realizza un "primo livello" di controllo.

Algoritmo Zero
- raggruppa tutti i triangoli di una "Montagna" in una BBox. Colleziona tutte le BBox Montagna in un vettore/array.

Algoritmo Collisione Uno
- testa la BSphere dello Scalatore cercando una collisione con ogni BBox Montagna: se ne trova una si ferma :: Scalatore è nella "zona attiva" di quella Montagna

A questo punto si potrebbe lanciare un altro Algoritmo, ad esempio:

Algoritmo Collisione Due
parametro uno -> "Punti Attivi" Scalatore
parametro due -> vettore triangoli della montagna

I "Punti Attivi" potrebbero essere delle piccole BBox o piccole BSphere definite attorno ai punti sensibili del modello Scalatore.
Scegliere questi punti sensibili credo dipenda dalle animazioni che il modello Scalatore può avere.

Definisco questi "punti Sensibili" a mo' di esempio:
a. PiedeDx
b. PiedeSnx
c. GinocchioDx
d. GinocchioSnx
e. Bacino
f. Sterno
g. ManoDx
h. ManoSnx
i. GomitoDx
l. GomitoSnx
m. Testa

Li "incapsulerei" in altrettante BoundigSphere (il controllo del solo raggio è veloce) e solo se il risultato fosse poco preciso rispetto a quello che si vuol e ottenere userei le BoundigBox.


A questo Punto "Algoritmo Collisione Due" testa tutti i "Punti Sensibili" del modello Scalatore contro i triangoli della Montagna.

Se controllare tutti i tirangoli della Montagna risulta ancora troppo dispendioso basta suddividerla ulteriormente come abbiamo fatto per il modello Scalatore, si procede come se fosse una spece di binary search, credo.

Nota:
Il modello Scalatore probabilmente viene generato in maniera "statica": resta da vedere se il terreno è definito, come modello, nello stesso modo oppure se è "ogni volta diverso" perchè i suoi dati sono generati da mesh che cambiano da istanza ad istanza....

Non sono esperto in materia e quindi non so se su quest'ultimo punto sono riuscito a spiegarmi...
Ne, tra l'altro, se quello che ho scritto è una fesseria

Ciao

[IceCoder]

Originariamente inviato da okay

infatti è proprio così il procedimento:

un oggetto mesh tipo uomo è formato da + mesh.x ognuna delle quali è circondata dal suo box.

Più precisamente da box fisici che possono essere box, sfere o cilindri

si ma dividendo una mesh in tante mesh dovrei calcolare molte piu collisioni bounding-box e poi alla fine non avrebbe la precisione che vorrei raggiungere, a meno che non raggruppassi le bounding box in un unica bounding box e poi controllassi prima la grande, e nel caso ci fosse collisione, anke le piu piccole e in fine quei pochi triangoli del "pezzo di modello"..mh...visto in questo modo non è poi cosi illogico.

[okay]

Originariamente inviato da IceCoder

si ma dividendo una mesh in tante mesh dovrei calcolare molte piu collisioni bounding-box e poi alla fine non avrebbe la precisione che vorrei raggiungere, a meno che non raggruppassi le bounding box in un unica bounding box e poi controllassi prima la grande, e nel caso ci fosse collisione, anke le piu piccole e in fine quei pochi triangoli del "pezzo di modello"..mh...visto in questo modo non è poi cosi illogico.

Non è che devi dividere una mesh in tante mesh...

Le mesh sono già divise... ti spiego:

Se un modellatore costruisce una moto la fà a pezzi di mesh: manubrio, ruote 2, ammortizzatori, ecc ecc.

Il programmatore prende le 8/10 mesh della moto e le ricostruisce joinandole insieme ognuna con una proprio box fisico.

Adesso per la moto, fatta a pezzi di mesh, il programmatore può usare per le collisioni racchiudendo tuttte le mesh della moto ricostruita semplicemente in una sfera o box... come c'è collisione al box la moto cade, avviene un incidente ecc ecc.

se vuoi fare un uomo costruito da testa busto gambe e arti (sup e inf) ed essere preciso nelle collisioni non devi far altro che mettere la testa in una sfera, gli arti (sup e inf) in 4 cilindri, il busto in una sfera e le gambe in 2/4 cilindri poi si controlla la collisione sui box fisici... è così che funziona.

Oppure metti tutta la mesh "uomo" in un box o cilindro con meno precisione.

Mentre lo ripeto ancora una volta per la "MAPPA.x" non si mette in nessun box o sfera perchè è da calpestare quindi bisogna sapere su che triangolo ci si trova per sapere il vertice y di detto triangolo per calcolare ed essere incollati alla "MAPPA.x" (oggetto statico)

[IceCoder]

Originariamente inviato da okay

Non è che devi dividere una mesh in tante mesh...

Le mesh sono già divise... ti spiego:

Se un modellatore costruisce una moto la fà a pezzi di mesh: manubrio, ruote 2, ammortizzatori, ecc ecc.

Il programmatore prende le 8/10 mesh della moto e le ricostruisce joinandole insieme ognuna con una proprio box fisico.

Adesso per la moto, fatta a pezzi di mesh, il programmatore può usare per le collisioni racchiudendo tuttte le mesh della moto ricostruita semplicemente in una sfera o box... come c'è collisione al box la moto cade, avviene un incidente ecc ecc.

se vuoi fare un uomo costruito da testa busto gambe e arti (sup e inf) ed essere preciso nelle collisioni non devi far altro che mettere la testa in una sfera, gli arti (sup e inf) in 4 cilindri, il busto in una sfera e le gambe in 2/4 cilindri poi si controlla la collisione sui box fisici... è così che funziona.

Oppure metti tutta la mesh "uomo" in un box o cilindro con meno precisione.

Mentre lo ripeto ancora una volta per la "MAPPA.x" non si mette in nessun box o sfera perchè è da calpestare quindi bisogna sapere su che triangolo ci si trova per sapere il vertice y di detto triangolo per calcolare ed essere incollati alla "MAPPA.x" (oggetto statico)

riguardo alla mappa sto studiando un metodo alternativo basato su bounding-box.

in pratica oltre alla mappa, si affianca un file di "scatole invisibili" che si sovrappone alla mappa, queste scatole rappresentano le altezze. quando collidi, la tua altezza aumenta o diminuisce in base a come viene settato lo script.

[okay]

Originariamente inviato da IceCoder

riguardo alla mappa sto studiando un metodo alternativo basato su bounding-box.

in pratica oltre alla mappa, si affianca un file di "scatole invisibili" che si sovrappone alla mappa, queste scatole rappresentano le altezze. quando collidi, la tua altezza aumenta o diminuisce in base a come viene settato lo script.

usi LUA?... io si ma non per fare quello che hai scritto lo adopero per il sound al verificarsi di un evento mi lancia il sound lo script...cmq fai un pò tu?

[IceCoder]

Originariamente inviato da okay

usi LUA?... io si ma non per fare quello che hai scritto lo adopero per il sound al verificarsi di un evento mi lancia il sound lo script...cmq fai un pò tu?

io non uso LUA (anzi non so neanke cosa sia) però mi è venuto in mente e ho voglia di tentare l implementazione di questo metodo.

[okay]

Originariamente inviato da IceCoder

riguardo alla mappa sto studiando un metodo alternativo basato su bounding-box.

in pratica oltre alla mappa, si affianca un file di "scatole invisibili" che si sovrappone alla mappa, queste scatole rappresentano le altezze. quando collidi, la tua altezza aumenta o diminuisce in base a come viene settato lo script.

Non ho capito cosa vuoi fare.

il 3d che hai aperto parla di collisione di 2 triangoli poi hai detto di collisione di 2 aerei ora parli della collisione sulla mappa...

Quale è il problema che vuoi risolvere dei 3 perchè gli algoritmi da adottare sono differenti

[fek]

Originariamente inviato da IceCoder

e se fossero due aerei che si scontrano?

ripeto che ho bisogno di un calcolo preciso, non mi servono bounding box o sphere.

le mesh sono in movimento quindi ad ogni movimento dovranno essere ricalcolate le collisioni.

Non hai bisogno di un calcolo preciso, usa boundoing box e bounding sphere

Poi, se scopri velocemente che due oggetti collidono, puoi, eventualmente, provare a calcolarti il punto esatto di collisione triangolo per triangolo, ma nel 99.99% dei casi non ti serve. No, ti assicuro, non ti serve.

Keep It Simple (perche' le collisioni sono gia' un argomento complesso di per se').

La cosa importante e' tenerti una copia delle mesh (semplificata) in memoria centrale per il calcolo delle collisioni. Eventualmente prendi un qualunque engine di fisica, e ci pensa lui cosi' ti risolvi il problema in un pomeriggio. Funzionano anche con gli heightfield.

[IceCoder]

beh imparando come risolvere la collisione tra 2 triangoli posso aggiungerla alle mie attuali conoscenze per risolvere anche gli altri problemi :P

[fek]

Originariamente inviato da okay

Mesh->LockVertexBuffer(D3DLOCK_READONLY, (void**)&pVertex);
Mesh->LockIndexBuffer(D3DLOCK_READONLY, (void**)&pIndex);
v1 = pVertex[pIndex[LineaCheIntersecaLaMesh*3]].position;
v2 = pVertex[pIndex[LineaCheIntersecaLaMesh*3+1]].position;
v3 = pVertex[pIndex[LineaCheIntersecaLaMesh*3+2]].position;

D3DVECTOR relPos = posizioneTriangolo - v1;
float dist1 = relPos.x * relPos.x + relPos.y * relPos.y + relPos.z * relPos.z;
float minDist2 = 10.0f;

ecc ecc.

Per l'amore di tutto cio' che e' sacro, buono e giusto, non consigliare a nessuno di lockare un vertex buffer read only. Siamo a natale, gesu' bambino piange a dirotto per queste cose.

E Carmack sicuramente non lockava un vertex buffer in read-only