Calcolare la collisione di 2 triangoli in 3D

[IceCoder]

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

quando collido con le montange devo fermarmi.

[k0nt3]

ti serve per forza sapere se un triangolo interseca un altro triangolo oppure ti basta sapere se un punto interseca un triangolo?

[IceCoder]

Originariamente inviato da k0nt3

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]

... 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]

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?

[k0nt3]

Originariamente inviato da IceCoder

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/Co...nTutorial.html

[IceCoder]

Originariamente inviato da k0nt3

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/Co...nTutorial.html

ecco questo potrà tornarmi utile..grazie 1000 ^^

[okay]

Originariamente inviato da IceCoder

...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??

[71104]

Originariamente inviato da k0nt3

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

[k0nt3]

Originariamente inviato da 71104

perché i punti notoriamente intersecano

perchè no, se un punto è parte di una superficie allora l'intersezione tra il punto e la superficie è il punto stesso

[IceCoder]

Originariamente inviato da okay

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).

[okay]

Originariamente inviato da IceCoder

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"

[k0nt3]

Originariamente inviato da IceCoder

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/art...rticle1026.asp)

se non basta prova a cercare qualcosa qua dentro :P http://www.google.com/custom?sa=Goog...8859%2D1&hl=en

[IceCoder]

si devo fare la funzione per le collisioni tra oggetti in movimento di un videogioco

[Ufo13]

Se e` un terreno basta usare il valore dell'heightfield in quel punto...

[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.

[wingman87]

http://www.softsurfer.com/Archive/al...rithm_0105.htm

[okay]

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.

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...ng_spheres.htm

[k0nt3]

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.

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]

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 ^^