View Full Version : Calcolare la collisione di 2 triangoli in 3D
IceCoder
10-12-2007, 16:34
oggi mi sono posto questo quesito:
come posso calcolare se un triangolo si interseca con un altro nelle 3 dimensioni?
conoscete qualche tutorial di algebra a riguardo oppure avete un algoritmo, o qualunque info mi possa aiutare?
di seguito posto un'immagine per far comprendere meglio il problema
http://breakdancex.altervista.org/raw.JPG
quando collido con le montange devo fermarmi.
ti serve per forza sapere se un triangolo interseca un altro triangolo oppure ti basta sapere se un punto interseca un triangolo?
IceCoder
10-12-2007, 17:00
ti serve per forza sapere se un triangolo interseca un altro triangolo oppure ti basta sapere se un punto interseca un triangolo?
anke un punto va bene per ora
banryu79
10-12-2007, 17:04
... dipende da cosa ti serve nello specifico.
Per esempio:
a) devi effettuare un test di collisione relativamente ad un oggetto "mentre si sta muovendo" nel tuo mondo 3D?
b) oppure l'oggetto viene posizionato, rimane là dove si trova fermo, e poi con calma ti puoi permettere di calcolare con precisione la collisione rispetto ai triagoli?
Nel primo caso, nota che se i triangoli cominciano ad essere numerosi (e dall'immagine che hai postato mi pare di capire che sarà così) un eventuale algoritmo che li prendesse in esame dovrebbe al suo interno effettuare il controllo per ognuno di essi... metti che poi vuoi controllare la collisione per più di un oggetto... il ciclo di collisione comincerebbe a portarti via troppo tempo, credo.
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...
Questo per darti un'idea di massima della cosa (neanche tanto precisa, dato che non sono esperto) ma appunto, dipende da cosa devi fare di preciso.
Prova a descriverci un po' più in dettaglio che cosa dovrà fare il tuo applicativo, magari si riesce a valutare un approccio adeguato.
Ciao :)
IceCoder
10-12-2007, 17:11
beh la bounding box non è adatta al mio scopo..
immagina che insieme alla montagna io carichi un modello 3D di uno scalatore e gli faccia scalare la montagna, lo scalatore non deve entrare nella montagna ma deve comunque riuscire a toccarla, con le tecniche elementari di sfera e scatola non avrei l'effetto voluto..
pero stavo pensando.. e se invece di controllare tutti i triangoli, non creassi ogni volta un array di triangoli che contiene SOLO quelli che mi stanno vicini?
anke un punto va bene per ora
per sapere se un punto è dentro un triangolo c'è metodo abbastanza semplice da implementare.. devi calcolare gli angoli che il punto forma con i vertici del triangolo e sommarli. se la somma è minore di 360° (2*pi) allora il punto non è nel triangolo.
ecco un esempio http://www.gamespp.com/algorithms/CollisionDetectionTutorial.html
IceCoder
10-12-2007, 17:22
per sapere se un punto è dentro un triangolo c'è metodo abbastanza semplice da implementare.. devi calcolare gli angoli che il punto forma con i vertici del triangolo e sommarli. se la somma è minore di 360° (2*pi) allora il punto non è nel triangolo.
ecco un esempio http://www.gamespp.com/algorithms/CollisionDetectionTutorial.html
ecco questo potrà tornarmi utile..grazie 1000 ^^
...come posso calcolare se un triangolo si interseca con un altro nelle 3 dimensioni?...
...quando collido con le montange devo fermarmi.
che significa... quando collido con un triangolo... il tuo personaggio è un triangolo?... stai in prima persona oppure sposti un triangolo e quando questo collide vuoi eseguire un collission response?
Da quello che scrivi sembra che tu ti sposti con un triangolo e quando collidi con la massa di triangoli (terreno) segnali la collisione.
con cosa ti sposti??
Vuoi rimanere, mentre cammini (in questo caso spostando i tasti frecce up down left right) rimanere incollato al terreno???
fammi capire cosa stai facendo...
Quell'ammasso di triangoli come l'hai costruito caricando una mesh.x oppure li hai fatti a mano da codice??
ti serve per forza sapere se un triangolo interseca un altro triangolo oppure ti basta sapere se un punto interseca un triangolo? perché i punti notoriamente intersecano :fagiano:
perché i punti notoriamente intersecano :fagiano:
perchè no, se un punto è parte di una superficie allora l'intersezione tra il punto e la superficie è il punto stesso
IceCoder
11-12-2007, 14:33
che significa... quando collido con un triangolo... il tuo personaggio è un triangolo?... stai in prima persona oppure sposti un triangolo e quando questo collide vuoi eseguire un collission response?
Da quello che scrivi sembra che tu ti sposti con un triangolo e quando collidi con la massa di triangoli (terreno) segnali la collisione.
con cosa ti sposti??
Vuoi rimanere, mentre cammini (in questo caso spostando i tasti frecce up down left right) rimanere incollato al terreno???
fammi capire cosa stai facendo...
Quell'ammasso di triangoli come l'hai costruito caricando una mesh.x oppure li hai fatti a mano da codice??
la mesh non è .x, è un formato mio personale, mentre per i terreni utilizzo il formato RAW.
Comunque SOSTANZIALMENTE ho bisogno del procedimento per calcolare la collisione tra 2 mesh (o quanto meno tra 2 triangoli).
la mesh non è .x, è un formato mio personale, mentre per i terreni utilizzo il formato RAW.
Comunque SOSTANZIALMENTE ho bisogno del procedimento per calcolare la collisione tra 2 mesh (o quanto meno tra 2 triangoli).
allora il procedimento:
per le collisioni funziona così:
hai un triangolo con posizione nello spazio con un D3DXVECTOR3(0.1, 0.20, 0.15) per esempio
D3DXVECTOR3 posizioneTriangolo = D3DXVECTOR3(0.1, 0.20, 0.15);
base:
se sposti questo triangolo devi confrontare la sua posizione (attuale) e scorrere tutti i vertici della mesh ossia il terreno con un ciclo facendoti ritorna le facce totali:
esempio:
D3DXVECTOR3 v1,v2,v3;
D3DVERTEX* pVertex;
short* pIndex;
facce=Mesh->GetNumFaces();
Mesh->LockVertexBuffer(D3DLOCK_READONLY, (void**)&pVertex);
Mesh->LockIndexBuffer(D3DLOCK_READONLY, (void**)&pIndex);
for(DWORD fa=0; fa<facce; fa++){
v1 = pVertex[pIndex[fa*3]].position;
v2 = pVertex[pIndex[fa*3+1]].position;
v3 = pVertex[pIndex[fa*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;
relPos = posizioneTriangolo - v2;
float dist2 = relPos.x * relPos.x + relPos.y * relPos.y + relPos.z * relPos.z;
relPos = posizioneTriangolo - v3;
float dist3 = relPos.x * relPos.x + relPos.y * relPos.y + relPos.z * relPos.z;
if(dist1 <= minDist2 * minDist2 || dist2 <= minDist2 * minDist2 || dist3 <= minDist2 * minDist2){
Mesh->UnlockVertexBuffer();
Mesh->UnlockIndexBuffer();
return true;
}
Mesh->UnlockVertexBuffer();
Mesh->UnlockIndexBuffer();
return false;
}
in pratica questo è l'algoritmo dove se 2 sfere entrano in collisione cioè se
dist1 <= minDist2 * minDist2
significa che il raggio dist1 della sfera che circonda la posizione del vettore triangolo collide con l'altra sfera che circonda i 3 vertici scansionati della mesh terreno dal ciclo.
Poi si può ottimizzare senza scansionare la mesh infatti potrebbe essere milioni e milioni di triangoli e questo approccio non può andar bene in quanto troppo dispendioso di risorse.
Per ottimizzare allora conviene prendere il punto del triangolo della posizione nello spazio e tracciare una linea che interseca il terreno e invece del ciclo dispendioso del for di sopra che estrae tutti i vertivi del triangolo, estrae da subito la posizione del triangolo della mesh terreno colpita dalla linea.
esempio:
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. ;) ;) ;)
by okay
Edit: Il secondo algoritmo è l'algoritmo che usano i + importanti engine di videogame (il primo a farlo è karmack)
Il primo algoritmo lo usano con tutorial in inglese di default e se non capisci bene l'inglese al secondo algoritmo (quello performante) non ci arrivi mai.
L'idea te l'ho data... ciao e buon secondo algoritmo
Edit2: va bhè... per calcolare il punto che interseca un triangolo (triangolo = 1 faccia composta a sua volta da 3 vertici ovvero 9 coordinate spaziali) devi calcolare la sua "normale" che punterà come "direzione" il triangolo della mesh estraendolo come indice (senza ciclo for ma immediatamente) ora avendo la faccia colpita del triangolo non ti rimane che determinare il vertice y:
puntoTriangolo.y=AltezzaTerreno+3.0; //altezza da terreno
così da rimanere incollato al "terreno"
la mesh non è .x, è un formato mio personale, mentre per i terreni utilizzo il formato RAW.
Comunque SOSTANZIALMENTE ho bisogno del procedimento per calcolare la collisione tra 2 mesh (o quanto meno tra 2 triangoli).
cioè.. tu hai un oggetto (in movimento?) composto da tanti triangoli e vuoi testare le collisioni di questo oggetto rispetto all'ambiente composto anch'esso da tanti triangoli?
probabilmente ci sono degli algoritmi per farlo, ma a mio avviso è un calcolo troppo oneroso per applicarlo a un ambiente 3D in real time (o vuoi fare un'analisi statica?).
non puoi fare nessuna semplificazione? ad esempio potresti supporre che l'oggetto sia una sfera e quindi calcolare la collisione tra la sfera e i triangoli che è più semplice (http://www.gamedev.net/reference/articles/article1026.asp)
se non basta prova a cercare qualcosa qua dentro :P http://www.google.com/custom?sa=Google+Search&cof=GALT%3A%23444444%3BS%3Ahttp%3A%2F%2Fwww%2Egamedev%2Enet%2F%3BGL%3A0%3BVLC%3A%23001C6F%3BAH%3Acenter%3BBGC%3A%23F5F5F5%3BLC%3A%23001C6F%3BGFNT%3A%23999999%3BALC%3A%23001C6F%3BBIMG%3Ahttp%3A%2F%2Fwww%2Egamedev%2Enet%2Fpics%2Fwatermark%2Egif%3BT%3A%23000000%3BGIMP%3A%23FF0000%3BAWFID%3Acd4b390a984e8463%3B&domains=www%2Egamedev%2Enet&sitesearch=www%2Egamedev%2Enet&q=collision+detection&client=pub%2D3167291168602081&forid=1&ie=ISO%2D8859%2D1&oe=ISO%2D8859%2D1&hl=en
IceCoder
11-12-2007, 17:04
si devo fare la funzione per le collisioni tra oggetti in movimento di un videogioco
Se e` un terreno basta usare il valore dell'heightfield in quel punto...
IceCoder
11-12-2007, 22:46
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.
wingman87
11-12-2007, 23:25
http://www.softsurfer.com/Archive/algorithm_0105/algorithm_0105.htm
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.
2 aerei sono formati da triangoli... tanti triangoli.
Se fossero solo 2 triangoli che si collidono il calcolo dell'algoritmo è + oneroso di 2 aerei con 100 e + triangoli ognuno.
Per questo gli algoritmi che si adoperano in videogame o grafica 3d devono essere fluidi e quindi non impegnare la cpu.
I metodi sono: (prova a cercare con google)
- AABB dove si mette l'aereo dentro un box
- Sfera si mette l'aereo dentro un ipotetica sfera si calcolano tutti i vertici e si ottiene il raggio della sfera che è il centro dell'aereo (è l'algoritmo che ti ho postato sopra) se il raggio interseca uno dei triangoli del terreno allora c'è collisione oppure metti i 2 aerei dentro 2 ipotetiche sfere si chiama "BoundingSphere".
Verificare se due sfere intersecando è molto semplice, infatti basta controllare se la distanza tra i due oggetti è minore della somma dei raggi delle relative bounding sphere
- Ellisi si mette l'oggetto nell'ellissi e un ottimo algoritmo ma su game al chiuso "indoor" l'ellisi può avere problemi.
Il migliore è con la sfera e il raggio purchè trovi la faccia del triangolo della collisione senza scorrere tutti i vertici "ottimizzazione" è l'algoritmo che ti ho postato il secondo.
Inoltre risolto il "collision detection" ottimale devi stabilire il "collision response"
cioè di quanto devi tornare indietro dopo la collisione e ancora fare lo sliding per esempio sfera rettilineo ecc ecc.
cerca con google "collision detection" troverai svariati tut. Ottimo quello segnalato da k0nt3 ma ce ne sono moltissimi.
Mettere l'oggetto in una sfera è una tecnica proprio per non scorrere tutti i vertici dell'oggetto.
Logicamente per il terreno è differente devi scorrere i vertici in quanto non puoi mettere il terreno in una sfera non avrebbe senzo... ci sei? a meno che non vuoi far collidere 10 terreni allora li metti tutti e 10 dentro 10 sfere poi li muovi come muovi gli aerei!!!... capisci??? allora non sarebbe + un terreno?!?!?!?!?!
guarda questo tut c'è proprio un'aereo dentro la sfera e i passi con codice da fare... + di così non saprei che proporti:
http://www.mvps.org/directx/articles/using_bounding_spheres.htm
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.
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
IceCoder
12-12-2007, 15:08
beh ovviamente il brute force è decisamente dispendioso ma non è quello che avevo in mente di usare, volevo conoscerlo per comprenderne il funzionamento algebrico.
ad ogni modo tutti questi tutorial che mi avete indicato mi sono utilissimi, mi impegneranno un bel po di tempo, vi ringrazio tutti ^^
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.
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)
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...:) :)
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
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??
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:
http://img88.imageshack.us/img88/2885/immaginenw1.jpg
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.
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!!
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:
http://img88.imageshack.us/img88/2885/immaginenw1.jpg
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
13-12-2007, 06:34
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.
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
13-12-2007, 09:24
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 :D
Ciao :)
IceCoder
13-12-2007, 12:27
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.
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
13-12-2007, 13:45
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.
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
13-12-2007, 17:53
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.
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
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
13-12-2007, 18:12
beh imparando come risolvere la collisione tra 2 triangoli posso aggiungerla alle mie attuali conoscenze per risolvere anche gli altri problemi :P
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 ;)
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.
Ok, eccoti il triangle-triangle intersection:
http://www.ziggyware.com/readarticle.php?article_id=78
Occhio, che ti stai andando a ficcare in un mare di problemi.
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.
Nei Game Engine di solito in queste situazioni si raffinano i bounding box fino al livello di precisione che ti serve e si procede ad albero: parti dal bounding box della montagna, se collide passi ai bounding box al livello inferiore, se collide passi ai bounding box a livello inferiore e cosi' via fino a che non arrivi al livello di precisione desiderato.
Non serve praticamente mai andare triangolo per triangolo.
marko.fatto
13-12-2007, 18:23
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.
la stessa cosa che dice il mio prof di elettronica quando qualcuno sbaglia alla lavagna :stordita:
Nei Game Engine di solito in queste situazioni si raffinano i bounding box fino al livello di precisione che ti serve e si procede ad albero
Sì, concordo, ma non credevo volesse realizzare un game engine e credevo gli servisse di conoscere l'esatto punto di intersezione.
Per l'amore di tutto cio' che e' sacro, buono e giusto, non consigliare a nessuno di lockare un vertex buffer read only.
In sola lettura cosa c'è di meglio... managed, poll, solo lettura meno dispendio di energie. Se poi serve ad estrarre ad un solo colpo il "TRIANGOLO" senza scorrerli tutti...allora è...PERFETTO!
non ti piacciono le DX... hè... l'ho capito sai....!!!!
come vanno le distribuzioni?
E Carmack sicuramente non lockava un vertex buffer in read-only ;)
certamente... lui ha inventato, creato giochi quali wolfenstain 3d, quake e doom, dal suo celebberrimo motore grafico creando l'algoritmo ottimizzato per le ombre, luci e collisioni.
Il tutto in OpenGL... e la sfera
non ti piacciono le DX... hè... l'ho capito sai....!!!!
per la serie perle da incorniciare :asd:
In sola lettura cosa c'è di meglio... managed, poll, solo lettura meno dispendio di energie. Se poi serve ad estrarre ad un solo colpo il "TRIANGOLO" senza scorrerli tutti...allora è...PERFETTO!
Non e' PERFETTO per nulla. Se locki un qualunque buffer in sola lettura, inchiodi la CPU e chiedi una sincronizzazione fra CPU e GPU. In pratica la CPU si ferma e aspetta che la GPU abbia finito, quando la GPU di solito viaggia uno o due frame dietro.
Semplicemene non si fa. E' proprio la prima (o seconda) cosa che si impara programmando in D3D.
Per le collisioni o i ray test ci si tiene una copia ottimizzata allo scopo della mesh.
Non e' PERFETTO per nulla. Se locki un qualunque buffer in sola lettura, inchiodi la CPU e chiedi una sincronizzazione fra CPU e GPU. In pratica la CPU si ferma e aspetta che la GPU abbia finito, quando la GPU di solito viaggia uno o due frame dietro.
Semplicemene non si fa. E' proprio la prima (o seconda) cosa che si impara programmando in D3D.
Per le collisioni o i ray test ci si tiene una copia ottimizzata allo scopo della mesh.
hai ragione... è meglio non fare tali esempi se non si sà ancora delle TempMesh.
qualcuno potrebbe metterlo in pratica.
...potrebbe esplodere tutto.
hai ragione... è meglio non fare tali esempi se non si sà ancora delle TempMesh.
Ma perche' insisti e ci fai anche dell'ironia fuori luogo? Ti ho visto rispondere a domande banalissime tirando fuori pezzi di codice in D3D perfettamente inutili, che non volevano dire nulla (alcuni pure con la sintassi sbagliata).
Non ne capisco davvero il motivo. Pazienza dai. Inutile andare OT.
Ti ho visto rispondere a domande banalissime.
mi hai visto...? ma dove quì sul forum?
...uhm... devo parlarne con cionci
quando mi hai visto che rispondevo a domande banalissime?
lookkare una sola volta all'inizio
Inizializzazione:
D3DVERTEX *pVertex;
m_pMesh->LockVertexBuffer(D3DLOCK_READONLY, (VOID**)&pVertex);
for(DWORD i=0; i<NumVertex; i++){
Path[i].position = pVertex[i].position;
}
m_pMesh->UnlockVertexBuffer();
adoperare Path[i].position invece di lookkare ogni volta...se l'oggetto è statico solo all'inizializzazione se l'oggetto si trasforma (è dinamico) Path[i].position và trasformato alle nuove posizioni.
adoperare Path[i].position invece di lookkare ogni volta...se l'oggetto è statico solo all'inizializzazione se l'oggetto si trasforma (è dinamico) Path[i].position và trasformato alle nuove posizioni.
Mi spieghi perche' posti codice random D3D che non c'entra assolutamente nulla col discorso (oltre ad essere errato)?
Per far vedere che conosci D3D? No, non conosci D3D.
Falla finita, dai :)
Mi spieghi perche' posti codice random D3D che non c'entra assolutamente nulla col discorso (oltre ad essere errato)?
Per far vedere che conosci D3D? No, non conosci D3D.
Falla finita, dai :) piccolo OT nell'OT: dopo aver osservato per qualche tempo quell'individuo su questo forum posso dirti che il problema che metti in evidenza non riguarda solamente Direct3D :O
poi quella volta della "demina" semplice semplice che caricava una mesh (di cui si è visto l'eseguibile e una parte inutile di codice, palesemente copiata da un sito che è stato poi ritrovato su Google) credo che tu ti sia perso veramente qualcosa :asd:
edit: mi correggo, c'eri anche tu!! :D
71104's fans
14-12-2007, 13:19
Mi spieghi perche' posti codice random D3D che non c'entra assolutamente nulla col discorso (oltre ad essere errato)?
Per far vedere che conosci D3D? No, non conosci D3D.
Falla finita, dai :)
D3DXVECTOR3 GetNormal( D3DXVECTOR3 vTriangle[] )
{
D3DXVECTOR3 vA = D3DXVECTOR3(p1[0],p1[1],p1[2]);
D3DXVECTOR3 vB = D3DXVECTOR3(p2[0],p2[1],p2[2]);
D3DXVECTOR3 vC = D3DXVECTOR3(p3[0],p3[1],p3[2]);
D3DXVECTOR3 v1, v2;
v1 = vB-vA;
v2 = vC-vA;
D3DXVECTOR3 vN;
D3DXVec3Cross(&vN, &v1, &v2);
D3DXVec3Normalize(&vN, &vN);
return vN;
}
D3DXVECTOR3 CollisionReaction( D3DXVECTOR3 vDirection, D3DXVECTOR3 vTriangle[] )
{
D3DXVECTOR3 vNormal = GetNormal( vTriangle );
D3DXVec3Normalize(&vDirection, &vDirection);
float f = D3DXVec3Dot( &vNormal, &vDirection );
D3DXVECTOR3 vUp = D3DXVECTOR3(0.0f, 1.0f, 0.0f);
D3DXVECTOR3 vWallDirection;
D3DXVec3Cross(&vWallDirection, &vNormal, &vUp);
D3DXVec3Normalize(&vWallDirection, &vWallDirection);
float fSpeed = 1.0f;
D3DXVECTOR3 vNewDir = fSpeed * f * vWallDirection;
return vNewDir;
}
ommamma e adesso chi sarà mai :eek: :eekk:
vBulletin® v3.6.4, Copyright ©2000-2025, Jelsoft Enterprises Ltd.