tractament de col·lisions en temps real. objectius donar un model de tractament de col·lisions...
TRANSCRIPT
![Page 1: Tractament de col·lisions en temps real. Objectius Donar un model de tractament de col·lisions independent de l’aplicació Tractar les col·lisions en menys](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4961a28abb57c927001/html5/thumbnails/1.jpg)
Tractament de col·lisions en Tractament de col·lisions en temps realtemps real
![Page 2: Tractament de col·lisions en temps real. Objectius Donar un model de tractament de col·lisions independent de l’aplicació Tractar les col·lisions en menys](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4961a28abb57c927001/html5/thumbnails/2.jpg)
ObjectiusObjectius
Donar un model de tractament de col·lisions independent de l’aplicació
Tractar les col·lisions en menys de 20 milisegons
![Page 3: Tractament de col·lisions en temps real. Objectius Donar un model de tractament de col·lisions independent de l’aplicació Tractar les col·lisions en menys](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4961a28abb57c927001/html5/thumbnails/3.jpg)
Temes tractatsTemes tractats
Model general pel tractament de col·lisions
GravetatError de precisióExemple d’una aplicació real
![Page 4: Tractament de col·lisions en temps real. Objectius Donar un model de tractament de col·lisions independent de l’aplicació Tractar les col·lisions en menys](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4961a28abb57c927001/html5/thumbnails/4.jpg)
Components d’un sistema de Components d’un sistema de tractament de col·lisionstractament de col·lisionsAlgoritme de deteccióAlgoritme de reacció
![Page 5: Tractament de col·lisions en temps real. Objectius Donar un model de tractament de col·lisions independent de l’aplicació Tractar les col·lisions en menys](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4961a28abb57c927001/html5/thumbnails/5.jpg)
Detecció de col·lisionsDetecció de col·lisions
![Page 6: Tractament de col·lisions en temps real. Objectius Donar un model de tractament de col·lisions independent de l’aplicació Tractar les col·lisions en menys](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4961a28abb57c927001/html5/thumbnails/6.jpg)
Un algoritme de detecció bàsicUn algoritme de detecció bàsic
Aplicació(){ per ( t = t0 fins a t1 en increments de trep ) {
obté dades dels dispositius d’entrada actualitza el comportament dels objectes per t fes { infoCol = detecta( t, objectes ) si ( infoCol conté col·lisions ) resposta a les col·lisions } mentre ( infoCol contingui col·lisions ) representa cada objecte de objectes per t }}
123456789
10111213
![Page 7: Tractament de col·lisions en temps real. Objectius Donar un model de tractament de col·lisions independent de l’aplicació Tractar les col·lisions en menys](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4961a28abb57c927001/html5/thumbnails/7.jpg)
Un algoritme de detecció bàsicUn algoritme de detecció bàsic
/* La variable tant persisteix d’una crida a l’altre. */
/* Inicialment tant = t0. */
detecta( tact, objectes )
{ per ( t = tant fina a tact en increments de tdet ) {
mou objectes a la seva posició per t per ( cada objecte Oi de objectes ) {
per ( cada objecte Oj de {objectes – Oi} )
si ( Oi i Oj interseccionen )
afegir Oi i Oj a infoCol
}
141516171819202122
![Page 8: Tractament de col·lisions en temps real. Objectius Donar un model de tractament de col·lisions independent de l’aplicació Tractar les col·lisions en menys](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4961a28abb57c927001/html5/thumbnails/8.jpg)
Un algoritme de detecció bàsicUn algoritme de detecció bàsic
si ( infoCol conté col·lisions ) { tant = t
retorna ( infoCol ) } } tant = tact
retorna ( infoCol )}
2324252627282930
![Page 9: Tractament de col·lisions en temps real. Objectius Donar un model de tractament de col·lisions independent de l’aplicació Tractar les col·lisions en menys](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4961a28abb57c927001/html5/thumbnails/9.jpg)
Problemes de l’algoritme bàsicProblemes de l’algoritme bàsic
Comprovar les col·lisions a només certs instants de l’interval de temps (fixed-timestep weakness)
Comprovar les interseccions entre totes les parelles d’objectes (all-pairs weakness)
Determinar si les superfícies de dos objectes interseccionen (pair-processing weakness)
![Page 10: Tractament de col·lisions en temps real. Objectius Donar un model de tractament de col·lisions independent de l’aplicació Tractar les col·lisions en menys](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4961a28abb57c927001/html5/thumbnails/10.jpg)
Fixed-timestep weaknessFixed-timestep weakness
Problema:– Algunes col·lisions
poden no detectar-se
Solucions:– Increment de temps
adaptable– Bounding de
moviment
![Page 11: Tractament de col·lisions en temps real. Objectius Donar un model de tractament de col·lisions independent de l’aplicació Tractar les col·lisions en menys](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4961a28abb57c927001/html5/thumbnails/11.jpg)
Bounding de movimentBounding de moviment
Engloba tot l’espai pel que passa l’objecte durant l’interval de temps
Si dos objectes col·lisionen els seus boundings de moviment interseccionaran
![Page 12: Tractament de col·lisions en temps real. Objectius Donar un model de tractament de col·lisions independent de l’aplicació Tractar les col·lisions en menys](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4961a28abb57c927001/html5/thumbnails/12.jpg)
Bounding de movimentBounding de moviment
Avantatges:– Es detecten col·lisions en tot l’interval de
temps– Amb una sola iteració es comprova tot
l’interval de temps
Requeriments:– S’ha de generar ràpidament– El test d’intersecció entre boundings ha de ser
ràpid
![Page 13: Tractament de col·lisions en temps real. Objectius Donar un model de tractament de col·lisions independent de l’aplicació Tractar les col·lisions en menys](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4961a28abb57c927001/html5/thumbnails/13.jpg)
Bounding de movimentBounding de moviment
Conté regions que no corresponen a l’espai pel que passa l’objecte– Problema:
• Es pot detectar una falsa col·lisió
– Solució:• Posterior càlcul
exacte de la col·lisió
![Page 14: Tractament de col·lisions en temps real. Objectius Donar un model de tractament de col·lisions independent de l’aplicació Tractar les col·lisions en menys](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4961a28abb57c927001/html5/thumbnails/14.jpg)
Bounding de movimentBounding de moviment
No guarda la informació temporal– Problema:
• Es pot detectar una falsa col·lisió
– Solucions:• Posterior càlcul
exacte de la col·lisió• Bounding espacio-
temporal
![Page 15: Tractament de col·lisions en temps real. Objectius Donar un model de tractament de col·lisions independent de l’aplicació Tractar les col·lisions en menys](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4961a28abb57c927001/html5/thumbnails/15.jpg)
Bounding de movimentBounding de moviment
Un objecte varia el seu comportament en col·lisionar– Problema:
• No es detecten les possibles noves col·lisions
– Solució:• Recalcular el
bounding de moviment
![Page 16: Tractament de col·lisions en temps real. Objectius Donar un model de tractament de col·lisions independent de l’aplicació Tractar les col·lisions en menys](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4961a28abb57c927001/html5/thumbnails/16.jpg)
All-pairs weaknessAll-pairs weakness
Problema:– Es realitzen moltes comprovacions
d’intersecció
Solució:– Organització espacial– Bounding de moviment
![Page 17: Tractament de col·lisions en temps real. Objectius Donar un model de tractament de col·lisions independent de l’aplicació Tractar les col·lisions en menys](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4961a28abb57c927001/html5/thumbnails/17.jpg)
Pair-processing weaknessPair-processing weakness
Problema:– Comprovar la intersecció entre les
superfícies de dos objectes és costós
Solució:– Aproximar l’objecte amb un bounding
![Page 18: Tractament de col·lisions en temps real. Objectius Donar un model de tractament de col·lisions independent de l’aplicació Tractar les col·lisions en menys](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4961a28abb57c927001/html5/thumbnails/18.jpg)
Bounding d’objecteBounding d’objecte
Problema:– El món visual i el
de les col·lisions són diferents
Solució:– Arbre de
boundings
![Page 19: Tractament de col·lisions en temps real. Objectius Donar un model de tractament de col·lisions independent de l’aplicació Tractar les col·lisions en menys](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4961a28abb57c927001/html5/thumbnails/19.jpg)
Sopa de polígonsSopa de polígons
Algunes aplicacions consten d’un món estàtic de polígons
Cada polígon es considera com un objecte estàtic
El bounding d’objecte d’un polígon és el mateix polígon
![Page 20: Tractament de col·lisions en temps real. Objectius Donar un model de tractament de col·lisions independent de l’aplicació Tractar les col·lisions en menys](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4961a28abb57c927001/html5/thumbnails/20.jpg)
Tipus de boundings més comunsTipus de boundings més comuns
![Page 21: Tractament de col·lisions en temps real. Objectius Donar un model de tractament de col·lisions independent de l’aplicació Tractar les col·lisions en menys](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4961a28abb57c927001/html5/thumbnails/21.jpg)
Boundings tractatsBoundings tractats
Esfera (bounding sphere)Caixa alineada al món (axis aligned
bounding box – AABB)Caixa orientada (oriented bounding
box – OBB)
![Page 22: Tractament de col·lisions en temps real. Objectius Donar un model de tractament de col·lisions independent de l’aplicació Tractar les col·lisions en menys](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4961a28abb57c927001/html5/thumbnails/22.jpg)
Necessitats d’un bounding de Necessitats d’un bounding de movimentmovimentRapidesa de creacióMàxima aproximació a l’espai pel que
passa l’objecteEficiència en l’algoritme
d’intersecció
![Page 23: Tractament de col·lisions en temps real. Objectius Donar un model de tractament de col·lisions independent de l’aplicació Tractar les col·lisions en menys](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4961a28abb57c927001/html5/thumbnails/23.jpg)
EsferaEsfera
Punts forts:– Creació– Algoritme
d’intersecció
Punts febles:– Aproximació
![Page 24: Tractament de col·lisions en temps real. Objectius Donar un model de tractament de col·lisions independent de l’aplicació Tractar les col·lisions en menys](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4961a28abb57c927001/html5/thumbnails/24.jpg)
Caixa alineada al mónCaixa alineada al món
Punts forts:– Creació– Algoritme
d’intersecció
Punts febles:– Aproximació
![Page 25: Tractament de col·lisions en temps real. Objectius Donar un model de tractament de col·lisions independent de l’aplicació Tractar les col·lisions en menys](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4961a28abb57c927001/html5/thumbnails/25.jpg)
Caixa orientadaCaixa orientada
Punts forts:– Aproximació
Punts febles:– Algoritme
d’intersecció
![Page 26: Tractament de col·lisions en temps real. Objectius Donar un model de tractament de col·lisions independent de l’aplicació Tractar les col·lisions en menys](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4961a28abb57c927001/html5/thumbnails/26.jpg)
Necessitats d’un bounding Necessitats d’un bounding d’objected’objecteRapidesa d’actualitzacióMàxima aproximació a la forma de
l’objecteEficiència en l’algoritme
d’intersecció
![Page 27: Tractament de col·lisions en temps real. Objectius Donar un model de tractament de col·lisions independent de l’aplicació Tractar les col·lisions en menys](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4961a28abb57c927001/html5/thumbnails/27.jpg)
EsferaEsfera
Punts forts:– Actualització– Algoritme
d’intersecció
Punts febles:– Aproximació
![Page 28: Tractament de col·lisions en temps real. Objectius Donar un model de tractament de col·lisions independent de l’aplicació Tractar les col·lisions en menys](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4961a28abb57c927001/html5/thumbnails/28.jpg)
Caixa alineada al mónCaixa alineada al món
Punts forts:– Algoritme
d’intersecció
Punts febles:– Actualització
• Solució: caixa de mida fixa
– Aproximació
![Page 29: Tractament de col·lisions en temps real. Objectius Donar un model de tractament de col·lisions independent de l’aplicació Tractar les col·lisions en menys](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4961a28abb57c927001/html5/thumbnails/29.jpg)
Caixa orientadaCaixa orientada
Punts forts:– Aproximació
Punts febles:– Algoritme
d’intersecció
![Page 30: Tractament de col·lisions en temps real. Objectius Donar un model de tractament de col·lisions independent de l’aplicació Tractar les col·lisions en menys](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4961a28abb57c927001/html5/thumbnails/30.jpg)
Arbres de boundingsArbres de boundings
Aproximen millor la forma de l’objecte
Es pot interrompre l’algoritme d’intersecció en funció del temps de càlcul disponible
Dos tipus:– El mateix bounding per tots els nivells– Un bounding més senzill a l’arrel
![Page 31: Tractament de col·lisions en temps real. Objectius Donar un model de tractament de col·lisions independent de l’aplicació Tractar les col·lisions en menys](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4961a28abb57c927001/html5/thumbnails/31.jpg)
Reacció a les col·lisionsReacció a les col·lisions
![Page 32: Tractament de col·lisions en temps real. Objectius Donar un model de tractament de col·lisions independent de l’aplicació Tractar les col·lisions en menys](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4961a28abb57c927001/html5/thumbnails/32.jpg)
Procediment de la reaccióProcediment de la reacció
Què cal fer en detectar una col·lisió?– Variar el comportament de l’objecte– Detectar noves col·lisions per la resta
de l’interval de tempsCom?– Aplicant lleis de la dinàmica– Simulant aquestes lleis
![Page 33: Tractament de col·lisions en temps real. Objectius Donar un model de tractament de col·lisions independent de l’aplicació Tractar les col·lisions en menys](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4961a28abb57c927001/html5/thumbnails/33.jpg)
Reaccions simuladesReaccions simulades
Lliscament amb friccióRebot amb esmorteïment
![Page 34: Tractament de col·lisions en temps real. Objectius Donar un model de tractament de col·lisions independent de l’aplicació Tractar les col·lisions en menys](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4961a28abb57c927001/html5/thumbnails/34.jpg)
Lliscament amb friccióLliscament amb fricció
1. Trobar el pla de col·lisió
2. Projectar la velocitat excedent sobre el pla de col·lisió
3. Escurçar el vector projectat per un factor de fricció
4. Vector resultant = vector de lliscament
![Page 35: Tractament de col·lisions en temps real. Objectius Donar un model de tractament de col·lisions independent de l’aplicació Tractar les col·lisions en menys](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4961a28abb57c927001/html5/thumbnails/35.jpg)
Rebot amb esmorteïmentRebot amb esmorteïment
1. Trobar el pla de col·lisió
2. Reflectir la velocitat excedent sobre el pla de col·lisió
3. Escurçar el vector reflectit per un factor d’esmorteïment
4. Vector resultant = vector de rebot
![Page 36: Tractament de col·lisions en temps real. Objectius Donar un model de tractament de col·lisions independent de l’aplicació Tractar les col·lisions en menys](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4961a28abb57c927001/html5/thumbnails/36.jpg)
GravetatGravetat
![Page 37: Tractament de col·lisions en temps real. Objectius Donar un model de tractament de col·lisions independent de l’aplicació Tractar les col·lisions en menys](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4961a28abb57c927001/html5/thumbnails/37.jpg)
SimulacióSimulació
Com a força constantCom a vector afegit al vector de
velocitat
![Page 38: Tractament de col·lisions en temps real. Objectius Donar un model de tractament de col·lisions independent de l’aplicació Tractar les col·lisions en menys](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4961a28abb57c927001/html5/thumbnails/38.jpg)
Aplicació del vector de gravetatAplicació del vector de gravetat
Dos mètodes:– Aplicar la gravetat sobre el vector de velocitat– Aplicar la gravetat com a vector de velocitat en
una segona iteració
![Page 39: Tractament de col·lisions en temps real. Objectius Donar un model de tractament de col·lisions independent de l’aplicació Tractar les col·lisions en menys](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4961a28abb57c927001/html5/thumbnails/39.jpg)
Error de precisióError de precisió
![Page 40: Tractament de col·lisions en temps real. Objectius Donar un model de tractament de col·lisions independent de l’aplicació Tractar les col·lisions en menys](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4961a28abb57c927001/html5/thumbnails/40.jpg)
ProblemaProblema
Els ordinadors treballen amb números finits
Algunes operacions poden donar un resultat erroni
El sistema de tractament de col·lisions pot fallà
![Page 41: Tractament de col·lisions en temps real. Objectius Donar un model de tractament de col·lisions independent de l’aplicació Tractar les col·lisions en menys](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4961a28abb57c927001/html5/thumbnails/41.jpg)
Exemple d’operació erròniaExemple d’operació errònia
Situació:– Límit de precisió = 3 decimals; a = 0.012; b = 0.025
Resultat de l’operació c = a·b:– Sobre el paper: c = 0.0003– En l’ordinador: c = 0
Solució:– Comparar a i b amb un valor EPSILON proper al zero
si ( a > 0 i b > 0 ) { c = a · b d = 1 / c}
1234
![Page 42: Tractament de col·lisions en temps real. Objectius Donar un model de tractament de col·lisions independent de l’aplicació Tractar les col·lisions en menys](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4961a28abb57c927001/html5/thumbnails/42.jpg)
Exemple d’una aplicació realExemple d’una aplicació real
Sistema de col·lisions de la versió beta del motor OpenDoor
![Page 43: Tractament de col·lisions en temps real. Objectius Donar un model de tractament de col·lisions independent de l’aplicació Tractar les col·lisions en menys](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4961a28abb57c927001/html5/thumbnails/43.jpg)
Què suporta el motorQuè suporta el motor
Un món estàtic de polígonsUn personatge explorant el món
![Page 44: Tractament de col·lisions en temps real. Objectius Donar un model de tractament de col·lisions independent de l’aplicació Tractar les col·lisions en menys](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4961a28abb57c927001/html5/thumbnails/44.jpg)
Decisions presesDecisions preses
Sistema de visualització basat en el portal rendering:– Organització de la geometria en habitacions
Impera la rapidesa del tractament de col·lisions en front de la precisió:– Personatge aproximat amb una esfera
Pocs objectes en un mateix lloc:– Caixa alineada al món com a bounding de
moviment
![Page 45: Tractament de col·lisions en temps real. Objectius Donar un model de tractament de col·lisions independent de l’aplicació Tractar les col·lisions en menys](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4961a28abb57c927001/html5/thumbnails/45.jpg)
Algoritme de tractament de Algoritme de tractament de col·lisionscol·lisions
Joc(){ per ( t = t0 fins a en increments de trep ) {
obté dades dels dispositius d’entrada actualitza el comportament del personatge per t velocitat = velocitat del personatge per t tracta( personatge, velocitat ) tracta( personatge, gravetat ) representa el món per t }}
123456789
1011
![Page 46: Tractament de col·lisions en temps real. Objectius Donar un model de tractament de col·lisions independent de l’aplicació Tractar les col·lisions en menys](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4961a28abb57c927001/html5/thumbnails/46.jpg)
Algoritme de tractament de Algoritme de tractament de col·lisionscol·lisions
tracta( objecte, velocitat ){ fes { infoCol = detecta( objecte, velocitat ) actualitza la posició de objecte segons infoCol si ( infoCol conté col·lisions ) velocitat = respon( infoCol, objecte, velocitat ) } mentre ( infoCol contingui col·lisions )}
121314151617181920
![Page 47: Tractament de col·lisions en temps real. Objectius Donar un model de tractament de col·lisions independent de l’aplicació Tractar les col·lisions en menys](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4961a28abb57c927001/html5/thumbnails/47.jpg)
Algoritme de deteccióAlgoritme de detecció
detecta( objecte, velocitat ){ boundObj = bounding de objecte boundMov = genera_bound_mov( boundObj, velocitat ) polsPot = obté_pols_potencials( boundObj, boundMov ) cols = troba_col·lisions( boundObj, velocitat, polsPot ) infoCol = primera_col·lisió( cols ) retorna ( infoCol )}
123456789
![Page 48: Tractament de col·lisions en temps real. Objectius Donar un model de tractament de col·lisions independent de l’aplicació Tractar les col·lisions en menys](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4961a28abb57c927001/html5/thumbnails/48.jpg)
Generació del bounding de Generació del bounding de movimentmoviment Cal trobar els 6
plans que formen la caixa:– Es resta el radi a
les components x, y i z més petites dels punts origen i destí
– Es suma el radi a les components majors
![Page 49: Tractament de col·lisions en temps real. Objectius Donar un model de tractament de col·lisions independent de l’aplicació Tractar les col·lisions en menys](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4961a28abb57c927001/html5/thumbnails/49.jpg)
Generació del bounding de Generació del bounding de movimentmoviment
genera_bound_mov( esfera, velocitat ){ origen = posició de esfera destí = origen + velocitat radi = radi de esfera caixa.xmín = mínim( origen.x, destí.x ) – radi
caixa.xmàx = màxim( origen.x, destí.x ) + radi
caixa.ymín = mínim( origen.y, destí.y ) – radi
caixa.ymàx = màxim( origen.y, destí.y ) + radi
caixa.zmín = mínim( origen.z, destí.z ) – radi
caixa.zmàx = màxim( origen.z, destí.z ) + radi
}
123456789
101112
![Page 50: Tractament de col·lisions en temps real. Objectius Donar un model de tractament de col·lisions independent de l’aplicació Tractar les col·lisions en menys](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4961a28abb57c927001/html5/thumbnails/50.jpg)
Obtenció dels polígons potencialsObtenció dels polígons potencials
S’aprofita l’organització en habitacions:– Només es comproven interseccions
amb els polígons de les habitacions per on passa el personatge
Bounding de moviment:– Es descarten ràpidament la majoria dels
polígons
![Page 51: Tractament de col·lisions en temps real. Objectius Donar un model de tractament de col·lisions independent de l’aplicació Tractar les col·lisions en menys](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4961a28abb57c927001/html5/thumbnails/51.jpg)
Obtenció dels polígons potencialsObtenció dels polígons potencials
Quan un objecte canvia d’habitació forçosament ha de travessar un portal
Llavors el portal intersecciona amb el bounding de moviment
![Page 52: Tractament de col·lisions en temps real. Objectius Donar un model de tractament de col·lisions independent de l’aplicació Tractar les col·lisions en menys](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4961a28abb57c927001/html5/thumbnails/52.jpg)
Obtenció dels polígons potencialsObtenció dels polígons potencials
Si els boundings de moviment no interseccionen ja es pot descartar el polígon
Un posterior clipping pot ajudar a descartar més polígons
![Page 53: Tractament de col·lisions en temps real. Objectius Donar un model de tractament de col·lisions independent de l’aplicació Tractar les col·lisions en menys](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4961a28abb57c927001/html5/thumbnails/53.jpg)
Obtenció dels polígons potencialsObtenció dels polígons potencials
obté_pols_potencials( esfera, boundMov ){ habsOcupades = habitacions que interseccionen amb boundMov per ( cada habitació Hi de habsOcupades ) {
per ( cada polígon Pj dels polígons que conté Hi ) {
boundPol = bounding de Pj
si ( boundMov i boundPol interseccionen ) si ( boundMov i Pj interserccionen ) )
afegeix Pj a polsPot
} } retorna ( polsPot )}
123456789
10111213
![Page 54: Tractament de col·lisions en temps real. Objectius Donar un model de tractament de col·lisions independent de l’aplicació Tractar les col·lisions en menys](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4961a28abb57c927001/html5/thumbnails/54.jpg)
Càlcul de les col·lisionsCàlcul de les col·lisions
L’esfera només pot col·lisionar amb un polígon si hi fa cap
Els polígons només consten de cara frontal
Se suposa un món ben construïtSempre hi ha un sol punt de contacte
entre una esfera i un polígon
![Page 55: Tractament de col·lisions en temps real. Objectius Donar un model de tractament de col·lisions independent de l’aplicació Tractar les col·lisions en menys](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4961a28abb57c927001/html5/thumbnails/55.jpg)
Càlcul de les col·lisionsCàlcul de les col·lisions
Un objecte s’acosta a un polígon si el seu vector de velocitat i la normal del polígon són de sentits oposats
En un món ben construït un objecte mai s’aproparà a un polígon per darrera
![Page 56: Tractament de col·lisions en temps real. Objectius Donar un model de tractament de col·lisions independent de l’aplicació Tractar les col·lisions en menys](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4961a28abb57c927001/html5/thumbnails/56.jpg)
Càlcul de les col·lisionsCàlcul de les col·lisions
Es mou el pla del polígon fins a tocar l’esfera
Es troba el punt de col·lisió de l’esfera en la seva posició inicial (ptCole)
![Page 57: Tractament de col·lisions en temps real. Objectius Donar un model de tractament de col·lisions independent de l’aplicació Tractar les col·lisions en menys](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4961a28abb57c927001/html5/thumbnails/57.jpg)
Càlcul de les col·lisionsCàlcul de les col·lisions
Des de ptCole es traça un raig paral·lel al vector de velocitat
Es troba el punt d’intersecció amb el pla del polígon (ptColp)
![Page 58: Tractament de col·lisions en temps real. Objectius Donar un model de tractament de col·lisions independent de l’aplicació Tractar les col·lisions en menys](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4961a28abb57c927001/html5/thumbnails/58.jpg)
Càlcul de les col·lisionsCàlcul de les col·lisions
El punt ptColp pot estar fora del polígon
Es troba el punt del polígon més proper al ptColp (nou ptColp)
![Page 59: Tractament de col·lisions en temps real. Objectius Donar un model de tractament de col·lisions independent de l’aplicació Tractar les col·lisions en menys](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4961a28abb57c927001/html5/thumbnails/59.jpg)
Càlcul de les col·lisionsCàlcul de les col·lisions
Des del nou ptColp es traça un raig paral·lel i de sentit invers al vector de velocitat.
El primer punt d’intersecció amb l’esfera serà el nou ptCole
Si el raig no intersecciona tampoc es produeix col·lisió
![Page 60: Tractament de col·lisions en temps real. Objectius Donar un model de tractament de col·lisions independent de l’aplicació Tractar les col·lisions en menys](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4961a28abb57c927001/html5/thumbnails/60.jpg)
Càlcul de les col·lisionsCàlcul de les col·lisions
troba_col·lisions( esfera, velocitat, polígons ){ origen = posició de l’esfera velu = velocitat normalitzada
per ( cada polígon Pi de polígons ) {
norm = normal de Pi
si ( norm * velu < 0 ) {
ptCole = punt d’intersecció del raig definit per origen i
-norm amb esfera ptColp = punt d’intersecció del raig definit per ptCole i velu
amb el pla que defineix Pi
12345678
9
![Page 61: Tractament de col·lisions en temps real. Objectius Donar un model de tractament de col·lisions independent de l’aplicació Tractar les col·lisions en menys](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4961a28abb57c927001/html5/thumbnails/61.jpg)
Càlcul de les col·lisionsCàlcul de les col·lisions
si ( ptColp no està dins Pi ) {
ptColp = punt de Pi més proper a ptColp
ptCole = primer punt d’intersecció del raig definit per
ptColp i -velu amb l’esfera
si ( no existeix ptCole )
continuar amb la següent iteració }
101112
131415
![Page 62: Tractament de col·lisions en temps real. Objectius Donar un model de tractament de col·lisions independent de l’aplicació Tractar les col·lisions en menys](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4961a28abb57c927001/html5/thumbnails/62.jpg)
Càlcul de les col·lisionsCàlcul de les col·lisions
distCol = mòdul de ptColp – ptCole
si ( distCol <= mòdul de velocitat ) afegeix distCol i Pi a col·lisions
} } retorna ( col·lisions )}
16171819202122
![Page 63: Tractament de col·lisions en temps real. Objectius Donar un model de tractament de col·lisions independent de l’aplicació Tractar les col·lisions en menys](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4961a28abb57c927001/html5/thumbnails/63.jpg)
Elecció de la col·lisió més Elecció de la col·lisió més immediataimmediataDesprés de la primera col·lisió es
varia el vector de velocitatNomés és vàlida la primera col·lisió
![Page 64: Tractament de col·lisions en temps real. Objectius Donar un model de tractament de col·lisions independent de l’aplicació Tractar les col·lisions en menys](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4961a28abb57c927001/html5/thumbnails/64.jpg)
Elecció de la col·lisió més Elecció de la col·lisió més immediataimmediata
primera_col·lisió( col·lisions ){ si ( col·lisions no conté cap col·lisió ) retorna ( ) distmín = per ( cada col·lisió Ci de col·lisions ) {
dist = distància de col·lisió de Ci
si ( dist < distmín ) {
distmín = dist
pol = polígon de Ci
} }
123456789
101112
![Page 65: Tractament de col·lisions en temps real. Objectius Donar un model de tractament de col·lisions independent de l’aplicació Tractar les col·lisions en menys](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4961a28abb57c927001/html5/thumbnails/65.jpg)
Elecció de la col·lisió més Elecció de la col·lisió més immediataimmediata
afegeix distmín i pol a infoCol
retorna ( infoCol )}
131415
![Page 66: Tractament de col·lisions en temps real. Objectius Donar un model de tractament de col·lisions independent de l’aplicació Tractar les col·lisions en menys](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4961a28abb57c927001/html5/thumbnails/66.jpg)
Algoritme de reaccióAlgoritme de reacció
El personatge ha de lliscar per la superfície amb la que col·lisiona– El personatge no s’atura al més mínim contacte– Es pugen automàticament rampes i obstacles
baixos La intensitat del lliscament ha de ser funció
de la textura i angle de col·lisió– Es roman quiet en rampes de poc pendent– Superfícies com el gel o la sorra generen
diferents comportaments
![Page 67: Tractament de col·lisions en temps real. Objectius Donar un model de tractament de col·lisions independent de l’aplicació Tractar les col·lisions en menys](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4961a28abb57c927001/html5/thumbnails/67.jpg)
Algoritme de reaccióAlgoritme de reacció
El pla de col·lisió és el pla tangent a l’esfera en el punt de col·lisió
Perquè l’esfera es mogui el mòdul de la projecció de la velocitat ha de ser major que el factor de fricció
![Page 68: Tractament de col·lisions en temps real. Objectius Donar un model de tractament de col·lisions independent de l’aplicació Tractar les col·lisions en menys](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4961a28abb57c927001/html5/thumbnails/68.jpg)
Algoritme de reaccióAlgoritme de reacció
respon( infoCol, objecte, velocitat ){ esfera = bounding de objecte pol = polígon que conté infoCol velExcedent = tros del vector velocitat després del punt de col·lisió plaCol = pla tangent a esfera en el punt de col·lisió lliscament = projecció de velExcedent sobre plaCol lliscament = lliscament escurçat pel factor de fricció de pol retorna ( lliscament )}
12345
6789
10
![Page 69: Tractament de col·lisions en temps real. Objectius Donar un model de tractament de col·lisions independent de l’aplicació Tractar les col·lisions en menys](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4961a28abb57c927001/html5/thumbnails/69.jpg)
Adreces d’interèsAdreces d’interès
![Page 70: Tractament de col·lisions en temps real. Objectius Donar un model de tractament de col·lisions independent de l’aplicació Tractar les col·lisions en menys](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4961a28abb57c927001/html5/thumbnails/70.jpg)
Adreces d’interèsAdreces d’interès
Codi de tests d’intersecció:– http://www.magic-software.com/Source/
Intersection3D/Intersection3D.html
Generació i utilització d’arbres d’esferes:– http://www.cs.wustl.edu/~pmh/research.html
Articles sobre la detecció de col·lisions– http://www.stanford.edu/~jgao/collision-detection.html
Articles sobre el motor OpenDoor:– http://www.macedoniamagazine.com
PER MÉS INFORMACIÓ...
[email protected] (Carles Ros Martínez – CITeM)