1 Tractament de col·lisions en temps real

2 Objectius Donar un model de tractament de col·lisions independent de l’aplicació Tractar les col·lisions en menys de 20 milisegons

3 Temes tractats Model general pel tractament de col·lisions Gravetat Error de precisió Exemple d’una aplicació real

4 Components d’un sistema de tractament de col·lisions Algoritme de detecció Algoritme de reacció

5 Detecció de col·lisions

6 Un algoritme de detecció bàsic Aplicació() { per ( t = t 0 fins a t 1 en increments de t rep ) { 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 } } 1 2 3 4 5 6 7 8 9 10 11 12 13

7 Un algoritme de detecció bàsic /* La variable t ant persisteix d’una crida a l’altre. */ /* Inicialment t ant = t 0. */ detecta( t act, objectes ) { per ( t = t ant fina a t act en increments de t det ) { mou objectes a la seva posició per t per ( cada objecte O i de objectes ) { per ( cada objecte O j de {objectes – O i } ) si ( O i i O j interseccionen ) afegir O i i O j a infoCol } 14 15 16 17 18 19 20 21 22

8 Un algoritme de detecció bàsic si ( infoCol conté col·lisions ) { t ant = t retorna ( infoCol ) } } t ant = t act retorna ( infoCol ) } 23 24 25 26 27 28 29 30

9 Problemes 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)

10 Fixed-timestep weakness Problema: –Algunes col·lisions poden no detectar- se Solucions: –Increment de temps adaptable –Bounding de moviment

11 Bounding 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

12 Bounding 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

13 Bounding 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ó

14 Bounding 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

15 Bounding 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

16 All-pairs weakness Problema: –Es realitzen moltes comprovacions d’intersecció Solució: –Organització espacial –Bounding de moviment

17 Pair-processing weakness Problema: –Comprovar la intersecció entre les superfícies de dos objectes és costós Solució: –Aproximar l’objecte amb un bounding

18 Bounding d’objecte Problema: –El món visual i el de les col·lisions són diferents Solució: –Arbre de boundings

19 Sopa 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

20 Tipus de boundings més comuns

21 Boundings tractats Esfera (bounding sphere) Caixa alineada al món (axis aligned bounding box – AABB) Caixa orientada (oriented bounding box – OBB)

22 Necessitats d’un bounding de moviment Rapidesa de creació Màxima aproximació a l’espai pel que passa l’objecte Eficiència en l’algoritme d’intersecció

23 Esfera Punts forts: –Creació –Algoritme d’intersecció Punts febles: –Aproximació

24 Caixa alineada al món Punts forts: –Creació –Algoritme d’intersecció Punts febles: –Aproximació

25 Caixa orientada Punts forts: –Aproximació Punts febles: –Algoritme d’intersecció

26 Necessitats d’un bounding d’objecte Rapidesa d’actualització Màxima aproximació a la forma de l’objecte Eficiència en l’algoritme d’intersecció

27 Esfera Punts forts: –Actualització –Algoritme d’intersecció Punts febles: –Aproximació

28 Caixa alineada al món Punts forts: –Algoritme d’intersecció Punts febles: –Actualització Solució: caixa de mida fixa –Aproximació

29 Caixa orientada Punts forts: –Aproximació Punts febles: –Algoritme d’intersecció

30 Arbres 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

31 Reacció a les col·lisions

32 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 temps Com? –Aplicant lleis de la dinàmica –Simulant aquestes lleis

33 Reaccions simulades Lliscament amb fricció Rebot amb esmorteïment

34 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

35 Rebot 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

36 Gravetat

37 Simulació Com a força constant Com a vector afegit al vector de velocitat

38 Aplicació 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ó

39 Error de precisió

40 Problema Els ordinadors treballen amb números finits Algunes operacions poden donar un resultat erroni El sistema de tractament de col·lisions pot fallà

41 Exemple 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 } 12341234

42 Exemple d’una aplicació real Sistema de col·lisions de la versió beta del motor OpenDoor

43 Què suporta el motor Un món estàtic de polígons Un personatge explorant el món

44 Decisions 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

45 Algoritme de tractament de col·lisions Joc() { per ( t = t 0 fins a  en increments de t rep ) { 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 } } 1 2 3 4 5 6 7 8 9 10 11

46 Algoritme de tractament de col·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 ) } 12 13 14 15 16 17 18 19 20

47 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 ) } 123456789123456789

48 Generació del bounding de moviment 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

49 Generació del bounding de moviment genera_bound_mov( esfera, velocitat ) { origen = posició de esfera destí = origen + velocitat radi = radi de esfera caixa.x mín = mínim( origen.x, destí.x ) – radi caixa.x màx = màxim( origen.x, destí.x ) + radi caixa.y mín = mínim( origen.y, destí.y ) – radi caixa.y màx = màxim( origen.y, destí.y ) + radi caixa.z mín = mínim( origen.z, destí.z ) – radi caixa.z màx = màxim( origen.z, destí.z ) + radi } 1 2 3 4 5 6 7 8 9 10 11 12

50 Obtenció 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

51 Obtenció 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

52 Obtenció 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

53 Obtenció dels polígons potencials obté_pols_potencials( esfera, boundMov ) { habsOcupades = habitacions que interseccionen amb boundMov per ( cada habitació H i de habsOcupades ) { per ( cada polígon Pj dels polígons que conté H i ) { boundPol = bounding de P j si ( boundMov i boundPol interseccionen ) si ( boundMov i P j interserccionen ) ) afegeix P j a polsPot } } retorna ( polsPot ) } 1 2 3 4 5 6 7 8 9 10 11 12 13

54 Cà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ït Sempre hi ha un sol punt de contacte entre una esfera i un polígon

55 Cà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

56 Cà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 (ptCol e )

57 Càlcul de les col·lisions Des de ptCol e es traça un raig paral·lel al vector de velocitat Es troba el punt d’intersecció amb el pla del polígon (ptCol p )

58 Càlcul de les col·lisions El punt ptCol p pot estar fora del polígon Es troba el punt del polígon més proper al ptCol p (nou ptCol p )

59 Càlcul de les col·lisions Des del nou ptCol p 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 ptCol e Si el raig no intersecciona tampoc es produeix col·lisió

60 Càlcul de les col·lisions troba_col·lisions( esfera, velocitat, polígons ) { origen = posició de l’esfera vel u = velocitat normalitzada per ( cada polígon P i de polígons ) { norm = normal de P i si ( norm * vel u < 0 ) { ptCol e = punt d’intersecció del raig definit per origen i -norm amb esfera ptCol p = punt d’intersecció del raig definit per ptCol e i vel u amb el pla que defineix P i 123456789123456789

61 Càlcul de les col·lisions si ( ptCol p no està dins P i ) { ptCol p = punt de P i més proper a ptCol p ptCol e = primer punt d’intersecció del raig definit per ptCol p i -vel u amb l’esfera si ( no existeix ptCol e ) continuar amb la següent iteració } 10 11 12 13 14 15

62 Càlcul de les col·lisions distCol = mòdul de ptCol p – ptCol e si ( distCol

63 Elecció de la col·lisió més immediata Després de la primera col·lisió es varia el vector de velocitat Només és vàlida la primera col·lisió

64 Elecció de la col·lisió més immediata primera_col·lisió( col·lisions ) { si ( col·lisions no conté cap col·lisió ) retorna (  ) dist mín =  per ( cada col·lisió C i de col·lisions ) { dist = distància de col·lisió de C i si ( dist < dist mín ) { dist mín = dist pol = polígon de C i } } 1 2 3 4 5 6 7 8 9 10 11 12

65 Elecció de la col·lisió més immediata afegeix dist mín i pol a infoCol retorna ( infoCol ) } 13 14 15

66 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

67 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ó

68 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 ) } 1 2 3 4 5 6 7 8 9 10

69 Adreces d’interès

70 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]@salleurl.edu (Carles Ros Martínez – CITeM)