detección de colisiones · 2018-09-20 · detección de colisiones • para abordar escenas...

Detección de Colisiones

Computación Gráfica AvanzadaIngeniería en Computación

Facultad de Ingeniería – Universidad de la República

Rossana Guerra

Detección de colisiones

• Temas

– Fase amplia, media y reducida o reducida de detección de colisiones.– Detección de colisiones con rayos.– Detección dinámica de colisiones con árboles BSP.– Tiempo crítico de detección de colisiones.– Modelos deformables.– Detección de colisiones contínua.– Respuesta de colisión.– Pruebas dinámicas de intersecciones.

17/09/2018 2Computación Gráfica Avanzada: Detección de Colisiones

Detección de colisiones

• Áreas donde se aplica :– Modelado 3D.– Simulaciones.– Movimiento y planificaciones de caminos.– Animación por computadora.– Juegos.– Diseño asistido por computadora.

• Área de permanente estudio.

17/09/2018 Computación Gráfica Avanzada: Detección de Colisiones 3

Detección de colisiones

• Para abordar escenas grandes es común dividir el proceso de detección de colisiones en 3 fases:– Fase amplia : encontrar pares de objetos cuyos BVs se superponen.– Fase media : detecta qué parte de los objetos se superponen.– Fase estrecha o reducida : pruebas a nivel de nodo hojas, primitivas u

objetos convexos, calcula intersecciones.

• Cada susbistema provee de datos al siguiente.

• La meta de cada fase es minimizar la cantidad de trabajo de la fase siguiente.

17/09/2018 Computación Gráfica Avanzada: Detección de Colisiones 4

Detección de colisiones

517/09/2018 Computación Gráfica Avanzada: Detección de Colisiones

Fase amplia

• Tiene como objetivo el tratamiento de los ambientes de gran escala con muchos objetos en movimiento.

• Reporta colisiones potenciales entre todos los objetos.

• La mayoría de los algoritmos de esta fase encierran un objeto en un BV, para luego encontrar pares de BVs que se superponen.

• Enfoque más simple: usar AABB para representar el BV para evitar recalcular todo la estructura jerárquica. Adjudicar dimensión suficiente para que contenga un objeto rígido en movimiento. Problema de los AABB: generar falsos positivos.

• Solución: AABB de tamaños ajustables, esferas o cápsulas.

• Las esferas representan mejor a los objetos que cambian su orientación.

17/09/2018 Computación Gráfica Avanzada: Detección de Colisiones 6

Fase amplia

• Ejemplo : falso positivo con AABB, en la última imagen solapan los AABB pero no los objetos contenidos en ellos.

17/09/2018 Computación Gráfica Avanzada: Detección de Colisiones 7

Fase amplia - Sweep and Prune

(Barrer y podar)

• Objetivo: recorre una lista ordenada de los intervalos de las aristas proyectadas (de las geometrías de la escena) sobre los ejes, descartando de la lista los que no se solapan.

• Aprovecha la coherencia temporal que está presente en aplicaciones típicas para favorecer la performance.

• Coherencia temporal o coherencia frame a frame: los cambios de posición y orientación son relativamente pequeños frame a frame.

17/09/2018 Computación Gráfica Avanzada: Detección de Colisiones 8

Fase amplia - Sweep and Prune

• Si dos AABBs se superponen, los 3 intervalos de cada eje (una dimensión) formados por el punto inicial y final en la dirección del eje, también se superponen para el transcurso de breves intervalos de tiempo.

• Esta característica nos permite abordar un problema en 3 dimensiones mediante el uso de un algoritmo en una dimensión (uno para cada uno de los ejes principales).

17/09/2018 Computación Gráfica Avanzada: Detección de Colisiones 9

Fase amplia - Sweep and Prune

• En un contexto de alta coherencia temporal sean n intervalos de proyección a lo largo de un eje, representados por si y ei

(comienzo y fin del intervalo respectivamente).

• si < ei 0 < i <= n .

• Se ordenan los intervalos en forma ascendente en una lista.

• Recorremos la lista desde el comienzo hasta el final, al encontrar si se pone en una lista activa, si se encuentra su punto final se quita de la lista.

• Si se encuentra el punto inicial de un intervalo mientras hay intervalos de la lista activa, el intervalo encontrado se superpone con los intervalos de la lista activa.

17/09/2018 Computación Gráfica Avanzada: Detección de Colisiones 10

Fase amplia - Sweep and Prune

17/09/2018 Computación Gráfica Avanzada: Detección de Colisiones 11

Fase amplia - Sweep and Prune

● Antes:

– I4 es encontrado cuando I3 es activo.

– Por lo tanto, I4 debe ser testeado junto con I3.

– Cuando I2 es encontrado, I4 es activo.

– Por lo tanto, I2 debe ser testeado junto con I4.

• Después:

– El objeto que proyectado daba I2 se mueve, afectando el valor s2.

– Insertion sort lo detecta, reordenando la lista.

– I4deja de ser activo antes de llegar a I2.

– I2 no se testea más (por ahora) junto con I4 .

17/09/2018 Computación Gráfica Avanzada: Detección de Colisiones 12

Fase amplia - Sweep and Prune

• Se crea una lista ordenada para cada eje.

• Debido al uso de la coherencia temporal la modificación en el

insertion sort es de pocas modificaciones y eficiente O(n+k),

donde k es el números de pares que se superponen.

• Las listas pueden crearse dinámicamente cada vez que se realiza

un test, o los objetos pueden guardar sus índices en las listas

para poder modificar sus valores.

• Para escenas con muchos objetos estáticos, conviene modificar la

lista en vez de reconstruirla.

17/09/2018 Computación Gráfica Avanzada: Detección de Colisiones 13

Fase amplia - Grids

• Array de n celdas disjuntas que cubre el espacio total de la

escena. Las celdas tienen igual dimensión.

17/09/2018 Computación Gráfica Avanzada: Detección de Colisiones 14

Fase amplia - Grids

• Mapea los objetos de los BV a celdas de la grilla.

• Cada celda representa un índice de una tabla de hash.

• Objetos con igual índice, deben ser verificados BV/BV para ver si

existe colisión.

• La dimensión de la celda puede impactar en la performance.

• Previene mejor el movimiento de los objetos, la tabla de hash es

fácil de actualizar.

17/09/2018 Computación Gráfica Avanzada: Detección de Colisiones 15

Fase amplia - Grids

• En la grilla de la izquierda la estrella y la elipse comparten celda

pero no colisionan.

• En la grilla derecha, la estrella azul cubre muchas celdas lo que

hace costoso el procedimiento.

• También hay un agrupamiento de elipses en una misma celda.

17/09/2018 Computación Gráfica Avanzada: Detección de Colisiones 16

Fase amplia - BVH

• Aquellos BVH formados por AABB (axes aligned bounding boxes)

se adaptan mejor a la geometría en el movimiento (frame a

frame).

• Una alternativa hacer BVH vs BVH, verifica el BVH contra sí

mismo para detectar colisiones entre los BV.

17/09/2018 Computación Gráfica Avanzada: Detección de Colisiones 17

Fase amplia - BVH

• Se construye el árbol, por ejemplo con la técnica top down.

• Una vez construido el árbol, los recorremos recursivamente

comenzando en la raíz. El recorrido termina cuando dos AABB

no solapan; si hay superposición, se agrega el par a la lista.

• Dado un nodo se desciende en la recursión porque un nodo no

colisiona consigo mismo. Descendemos por B y C.

• Elegimos B y descendemos a E y D que no se superponen.

• Descendemos por C, como F y G solapan, se agrega par a la lista.

• Como B y C se superponen, verificamos si los hijos de B se

superponen con los de C.

17/09/2018 Computación Gráfica Avanzada: Detección de Colisiones 18

Fase amplia - BVH

• Encontramos que E y F se superponen, se agregan a la lista.

• Ventaja: usamos una única estructura que puede usarse en la

siguiente fase o en ray tracing, view frustrum culling, etc.

17/09/2018 Computación Gráfica Avanzada: Detección de Colisiones 19

Fase media

• En esta fase se determina qué parte de los objetos colisionan.

• Se presentan métodos con BVH más eficientes y que se ajustan

mejor a las geometrías existentes.

• Se busca desarrollar BVHs que representen mejor el movimiento

de los rígidos.

17/09/2018 Computación Gráfica Avanzada: Detección de Colisiones 20

Fase media - Construcción del BVH

• Hay cuatro métodos para construir el BVH– Bottom up.

– Inserción incremental en el árbol.

– Top Down.

– BVH lineal.

• Recordar siempre: usar BV que se ajusten lo más posible a la

geometría.

17/09/2018 Computación Gráfica Avanzada: Detección de Colisiones 21

Fase media - Construcción del BVH

• El modelo que representa la escena es una estructura k-aria,

cada nodo puede tener k hijos.

• El valor de k depende de la arquitectura, en las actuales es

preferible k > 2.

• Se aprovecha el ancho del registro SIMD para paralelizar el

procesamiento.

• Nodo interno, agrupa hijos del BV.

• Nodo hoja, agrupa primitivas.

17/09/2018 Computación Gráfica Avanzada: Detección de Colisiones 22

Fase media - Bottom up

• Combina varias primitivas hasta formar un BVH.

• Las primitivas que están lo suficientemente cerca (usando la

distancia entre primitivas) crean un nuevo BV, o se agrupan a

uno o más BVs existente formando uno más grande (nodo

padre).

• Se repite el procedimiento hasta que existe un solo BV, nodo

raíz.

• Las primitivas próximas siempre están ubicadas cerca en el BVH.

17/09/2018 Computación Gráfica Avanzada: Detección de Colisiones 23

Fase media - Inserción incremental

• Inserta el BV y sus primitivas de modo que el punto de inserción sea tal que el incremento del BVH sea mínimo.

• Se desciende hasta el nodo del árbol que genere el mínimo crecimiento.

17/09/2018 Computación Gráfica Avanzada: Detección de Colisiones 24

Fase media - Inserción incremental

• Se comienza con el árbol vacío.• Por ejemplo, si N está muy alejado de B, pero muy cercano a C,

agregar un volumen P que contenga a C y N es mejor porque P sería de menor tamaño.

• Usualmente toma O(n log n).

17/09/2018 Computación Gráfica Avanzada: Detección de Colisiones 25

Fase media - Top Down

• Al principio todas las primitivas se agrupan en un único BV que será la raíz.

• Luego aplicamos divide and conquer, el BV se divide en k o menos partes.

• Para cada división se crea un BV y se buscan las primitivas que le pertenecen.

• Puede haber primitivas divididas por los ejes, o bien que queden de un solo lado del mismo, por eso es vital encontrar un buen punto de división mediante probabilidad geométrica.

17/09/2018 Computación Gráfica Avanzada: Detección de Colisiones 26

Fase media - BVH lineal

• El objetivo original era crear el BVH en GPU pero el método funciona bien en CPU también.

• Primero una caja agrupa todas las primitivas, triángulos en este caso.

• Los triángulos se guardan en un array según un orden.• En este caso la curva de Morton.• Se asigna un código de Morton a cada centro del triángulo.• La lista se divide jerárquicamente y en cada paso se crea un

nodo interno en cuyos descendientes están los triángulos.• El método finaliza cuando no hay triángulos en una sub lista o

hay un número pequeño que cabe en una hoja.

17/09/2018 Computación Gráfica Avanzada: Detección de Colisiones 27

Fase media - BVH Lineal

• La curva de Morton tiene la propiedad que para valores

cercanos en un espacio de n dimensiones, genera valores

cercanos en una dimensión.• La curva de Morton define una función para codificar valores,

vértices de los triángulos en este caso.

17/09/2018 Computación Gráfica Avanzada: Detección de Colisiones 28

Fase media - BVH Lineal

• Desafíos de la DC: encontrar el BV que mejor se ajuste a los objetos de la escena y la creación de árboles balanceados.

• Los árboles balanceados tienen el mejor orden de ejecución en el peor caso. El tiempo de consulta a cualquier hoja será el mismo.

• Esto no es deseable en todos los casos: si una parte del modelo rara vez se consulta, es mejor que se encuentre lejos de la raíz del árbol balanceado.

• Lo que se consulta seguido es conveniente tenerlo cerca de la raíz.

17/09/2018 Computación Gráfica Avanzada: Detección de Colisiones 29

Fase media - Detectar colisiones entre BVH

• A y B son dos nodos de dos BVH distintos.• ABV y BBV accede al nodo apropiado del BV apropiado.• AC conjunto de hijos de A.• La idea consiste en abrir un volumen más grande cuando se

detecte superposición.• Recursivamente se verifica el contenido.

17/09/2018 Computación Gráfica Avanzada: Detección de Colisiones 30

Fase media - Detectar colisiones entre BVH

17/09/2018 Computación Gráfica Avanzada: Detección de Colisiones 31

Fase media - Detectar colisiones entre BVH

• El algoritmo podría mejorarse alternando hojas de A o B para evitar los cálculos de las áreas.

• Otra opción es tener las áreas pre calculadas, lo que implica otra estructura de almacenamiento para estos valores.

• Función de costo de BVH : tomarla en cuenta, evalúa el costo de evaluar colisiones en diferentes tipo de estructuras, esferas, AABB, OBB, K-DOPs.

• Cada estructura tiene ventajas y desventajas; AABB se adaptan bien a la geometría y son de tests rápidos, la esfera no se adapta demasiado. OBB se adaptan mejor que los AABB pero el test de superposición no es bueno.

17/09/2018 Computación Gráfica Avanzada: Detección de Colisiones 32

Fase media - Árbol OBB

• Esquema usado para superficies próximas y casi paralelas, se usa cuando se necesita tolerancia, para determinar qué tan separadas pueden estar las primitivas.

• Selección del BV: • Usa OBB porque converge mejor a la geometría de la escena con

respecto a los AABB o las esferas.• Sin embargo crear un AABB es más rápido, pero la performance

depende de caso en particular.

17/09/2018 Computación Gráfica Avanzada: Detección de Colisiones 33

Fase media - Árbol OBB

• Técnica de Van der Bergen para acelerar el test de superposición entre dos OBB.

• Geométricamente puede pensarse como un test de superposición entre dos AABB.

• El resto del test se hace en el sistema de coordenadas del primer OOB por ejemplo A, y el otro test se hace en el sistema de coordenadas del otro OBB, objeto B.

17/09/2018 CComputación Gráfica Avanzada: Detección de Colisiones 34

A la izquierda hay dos OBBs (A y B) que se probará si se superponen con un test OBB/OBB.

B es limitado por un AABB en el sistema de coordenadas de A, C.

C y A se superponen, la prueba continúa.

A se encierra en un AABB, D en el sistema de coordenadas de B.

Fase media - Árbol OBB

17/09/2018 Computación Gráfica Avanzada: Detección de Colisiones 35

• En caso que hubiera solapamiento en un plano de proyección, no implica que existe solapamiento entre los objetos. Para determinarlo es necesario contemplar la proyección en los demás ejes.

Fase media - Árbol OBB

17/09/2018 Computación Gráfica Avanzada: Detección de Colisiones 36

• Un método posible es utilizar el enfoque top-down.• Englobar la escena en un árbol OBB, a continuación se toma un

eje más largo y se divide el árbol OBB en dos.• Repetir recursivamente hasta obtener una primitiva.

Fase media - Construcción de la jerarquía

17/09/2018 Computación Gráfica Avanzada: Detección de Colisiones 37

● Hay dos enfoques:○ Ver si los pares de primitivas intersecan.

○ Determinar la distancia para ver la separación entre objetos.

Fase Estrecha

17/09/2018 Computación Gráfica Avanzada: Detección de Colisiones 38

• La implementación más simple: loop sobre cada primitiva de un

nodo hoja y verificar si interseca con las primitivas de otro nodo

hoja.

• Podemos ordenar la lista de acuerdo a un criterio de adyacencia

o sacar ventaja de una implementación basada en su

arquitectura (SIMD).

Fase estrecha - Primitiva vs Primitiva

17/09/2018 Computación Gráfica Avanzada: Detección de Colisiones 39

• Esta técnica se aplica en sistemas donde los objetos deben estar

separados una cierta distancia entre sí. Ej.: asientos de un auto.

• Planificación de caminos: determinar el camino por donde un

objeto puede transitar sin colisionar.

• A esa distancia mínima, se le llama tolerancia.

• Dada la aceleración, velocidad de un objeto y el tiempo entre

frames, podemos determinar la tolerancia para que el objeto no

colisione con otro.

Fase estrecha - Consulta de Distancias

17/09/2018 Computación Gráfica Avanzada: Detección de Colisiones 40

• Enfoque práctico para calcular la distancia mínima entre dos poliedros : algoritmo GJK (Gilbert, Johnson, Keerthi):

• Primero calcula la diferencia entre dos objetos mediante la suma de Minkowski.

• Diferencia de Minkowski: el objeto diferencia de dos objetos convexos A y B.

A - B = {x - y : x ∈ A; y ∈ B}

• También conocida como suma de Minkowksi: A + B reflejado (son equivalentes).

• Relación: A - B = (AC + (-B))C.

Fase estrecha - Consulta de Distancias

17/09/2018 Computación Gráfica Avanzada: Detección de Colisiones 41

• Esos puntos de la diferencia forman un objeto convexo.• Calcular la distancia entre A - B y el origen, equivale a la

distancia entre A y B (el origen es un vértice de B).• En la figura de abajo vemos el cálculo del polígono de Minkowski

al que llamaremos M.

Fase estrecha - Consulta de Distancias

17/09/2018 Computación Gráfica Avanzada: Detección de Colisiones 42

A-B: se toma el origen relativo a A. Se refleja B, y el punto elegido como referencia se pone sobre la superficie de A.

Luego B se mueve a lo largo de todos los vértices (sentido antihorario) de A para obtener el polígono al que se le calculará la distancia mínima.

Fase estrecha - Consulta de Distancias

17/09/2018 Computación Gráfica Avanzada: Detección de Colisiones 43

• Algoritmo GJK– Dado el origen y una diferencia (polígono) de Minkowski M.– Tomar una primitiva (triángulo) más simple respecto a su

dimensión (simplex) con los vértices de M.– Tomar la línea desde el origen al vértice más cercano de la

primitiva.– Proyectar todos los vértices de M sobre la línea.– Reemplazar el vértice proyectado más lejano del triángulo, con

el vértice proyectado más cercano de M al centro. Actualizar el simplex.

– Repetir proceso con el nuevo triángulo hasta que no se puedan reemplazar más vértices.

– La distancia al vértice más cercano del triángulo final es la distancia mínima al objeto.

Fase estrecha - Consulta de Distancias

17/09/2018 Computación Gráfica Avanzada: Detección de Colisiones 44

Fase estrecha - Consulta de Distancias

17/09/2018 Computación Gráfica Avanzada: Detección de Colisiones 45

● A veces no es necesario involucrar primitivas (costoso) para detectar colisiones. El modelo se puede simplificar a un conjunto de rayos en los objetos que tendrán contacto.

● El origen se toma donde hay contacto, y se traza un rayo hacia el objeto a verificar.

● Si la distancia es 0, entonces hay contacto.● Si la distancia es mayor que 0, entonces no hay contacto, el

objeto está por encima de la superficie.● Si la distancia es menor que 0, entonces parte del objeto se ha

incrustado con el objeto que colisiona.● Este método tiene sentido si la cantidad de superficies en

contacto no se modifica demasiado en la escena.

Detección de colisiones por rayos

17/09/2018 CComputación Gráfica Avanzada: Detección de Colisiones 46

• Hay que tener en cuenta el origen del rayo y la dirección hacia la que se proyecta.

Detección de colisiones por rayos

17/09/2018 Computación Gráfica Avanzada: Detección de Colisiones 47

• Hermann: cuando 2 objetos se superponen, a los vértices pertenecientes a la zona de solapamiento se le trazan rayos según sus normales negativas.

• Si los rayos de cada objeto impactan en el parte del otro objeto, entonces colisionan.

Detección de colisiones por rayos

17/09/2018 Computación Gráfica Avanzada: Detección de Colisiones 48

• Escena representada por un árbol BSP colisiona con objetos representados por esferas, cilindros o una envolvente convexa.

• Sirven para testear objetos en movimiento.• Para representar personajes, es mejor usar un cilindro o

envolvente convexa.• Método: en vez de intersecar un segmento con el objeto,

traslada el objeto una distancia r, según la dirección de la normal del otro objeto.

Detección de colisiones con árboles BSP

17/09/2018 Computación Gráfica Avanzada: Detección de Colisiones 49

• Para intersecar esferas, se mueve el plano una distancia

equivalente al radio de la esfera en dirección de la normal del

plano, hacia afuera. Evita realizar cálculos cuadráticos y se buscaría la pertenencia de un punto en un plano.

• El BSP no está alineado a los ejes, sino a la superficie de la escena.

• Se hace un ajuste del plano π.• Signo de r depende de qué lado del plano se hace el test.

Detección de colisiones con árboles BSP

17/09/2018 Computación Gráfica Avanzada: Detección de Colisiones 50

Detección de colisiones con árboles BSP

17/09/2018 Computación Gráfica Avanzada: Detección de Colisiones 51

• Cilindro contra un plano, se tome un punto conveniente del cilindro, por ejemplo p0.

• Se acerca el plano a un punto de contacto con el cilindro en dirección normal al plano.

• Se proyecta p0 sobre el nuevo plano, si la proyección pertenece

al semiespacio positivo, no hay colisión.

Detección de colisiones con árboles BSP

17/09/2018 Computación Gráfica Avanzada: Detección de Colisiones 52

• Si la normal no está en el sentido del eje z, se proyecta la misma sobre el plano Oxy.

Detección de colisiones con árboles BSP

17/09/2018 Computación Gráfica Avanzada: Detección de Colisiones 53

• Problemas de este enfoque se presenta al verificar intersección entre esferas y planos adyacentes que forman más de 90 grados.

• Para solucionarlo se agregan planos oblicuos.• Estos planos no forman parte de la escena pero hay que

agregarlos al árbol BSP, por lo tanto también modifica el algoritmo.

Detección de colisiones con árboles BSP

17/09/2018 Computación Gráfica Avanzada: Detección de Colisiones 54

Detección de colisiones con árboles BSP

17/09/2018 Computación Gráfica Avanzada: Detección de Colisiones 55

• El algoritmo de detección de colisiones tiene un tiempo límite para realizar la tarea.

• Se usa al algoritmo de Hubbard: recorre el BVH por amplitud.• Se debe a que BV adyacentes pueden contener partes de un

mismo objeto, y de esta forma se visitan rápidamente.• Algoritmo de Hubbard:

– Encontrar los BVs que se superponen y poner el par en una cola.– Desencolar un par de BVs para ver si sus hijos se superponen, si hay

pares que se superponen se ponen al final de la cola.– El proceso termina si la cola es vacía o se llegó al tiempo límite.– Mejora del algoritmo : usar colas de prioridad (por distancia,

visibilidad).

Detección de colisiones en tiempo crítico

17/09/2018 Computación Gráfica Avanzada: Detección de Colisiones 56

Detección de colisiones en tiempo crítico

17/09/2018 Computación Gráfica Avanzada: Detección de Colisiones 57

• Se aplican a modelos cuyos objetos cambian de forma como el agua, telas siendo deformadas por el movimiento del viento, etc.

• No podemos aplicar cuerpos rígidos para su representación, sino que cada vértice se trata como un vector en función del tiempo.

• Se tratan con mallas, asumiendo que no cambia durante su deformación. Se usa esta propiedad para no reconstruir el BVH, sino sólo los BV se recalculan usando AABB porque convergen mejor a la geometría que contienen y son rápidos de re calcular.

Modelos deformables

17/09/2018 Computación Gráfica Avanzada: Detección de Colisiones 58

• Enfoque bottom up, el árbol se organiza en un array donde los índices de los padres son mayores que los índices de los hijos.

• Se actualiza el árbol recorriendo el array de atrás hacia adelante, las hojas se recalculan primero.

• Cada BV se actualiza a partir de información reciente.• Se observó que es un algoritmo 10 veces más rápido que

comenzar a reconstruir el BVH desde el inicio.

Modelos deformables

17/09/2018 Computación Gráfica Avanzada: Detección de Colisiones 59

• Enfoque híbrido, el enfoque anterior implica actualizar todos los BVs. Muchas veces sólo alguna parte de los objetos se han movido, por lo cual se aplica un enfoque híbrido como mejora.

• Los primeros niveles incluyendo la raíz se actualizan mediante bottom up en cada frame.

• Se eligen los niveles superiores, porque descartan parte de la geometría en las consultas.

• Para verificar que esa BVH se superpone con elementos de otra, usamos los niveles de la jerarquía que están actualizados.

• Si hay superposición se aplica técnica top down para actualizar los BVs hijos.

Modelos deformables

17/09/2018 Computación Gráfica Avanzada: Detección de Colisiones 60

Modelos deformables

17/09/2018 Computación Gráfica Avanzada: Detección de Colisiones 61

Detección de colisiones contínua

• Se calcula el tiempo de impacto entre los objetos para evitar artefactos extraños en la imagen.

• Ej. de artefacto extraño: una pelota que va hacia una pared, y en el siguiente frame ya está de regreso sin mostrar el rebote.

• El siguiente algoritmo se usa en videojuegos para verificar si dos objetos colisionan.

• La distancia d se determina mediante el algoritmo GJK.

17/09/2018 Computación Gráfica Avanzada: Detección de Colisiones 62

Detección de colisiones contínua

17/09/2018 Computación Gráfica Avanzada: Detección de Colisiones 63

Detección de colisiones contínua

• VA y VB velocidad a la que se mueven los objetos A y B respectivamente.

• ωA y ωB son las velocidades angulares respectivas.• rA y rB el radio desde su centro al punto más lejano.• Si ωA y ωB son nulas (no hay rotación), entonces tenemos

c = (VB - VA). d/||d|| velocidad relativa entre los objetos proyectada a lo largo de d.

• La máxima cantidad de tiempo sin colisión es: Δt= ||d||/c.• Si Δt es mayor al tiempo entre frames no hay colisión.

17/09/2018 Computación Gráfica Avanzada: Detección de Colisiones 64

Respuesta a las colisiones

• Son técnicas que permiten tomar acciones adecuadas cuando sucede una colisión.

• Por ejemplo, si una pelota apenas deformable se lanza contra una pared lisa, no debe incrustarse, sino rebotar.

• Se aplican leyes físicas, como la conservación de energía cinética, coeficiente de restitución, gravedad, etc para determinar las acciones correctas en cada caso.

• Es un campo que aún se encuentra en investigación.

17/09/2018 Computación Gráfica Avanzada: Detección de Colisiones 65

Respuesta a las colisiones

• Cambio de la velocidad en un choque completamente elástico (vn no se modifica).

17/09/2018 Computación Gráfica Avanzada: Detección de Colisiones 66

Test de intersección dinámica

• Esfera - Plano

• Test de esfera de centro c que se mueve con velocidad v.• Δt duración del frame. • Próxima posición de la esfera e = c+Δtv. • sc - distancia desde el centro al plano.• π: nx + d = 0, ecuación del plano.• π: nc + d = sc.• sc - r = distancia de la esfera al plano.• Se vuelve a calcular la distancia para el punto final e.

17/09/2018 Computación Gráfica Avanzada: Detección de Colisiones 67

Test de intersección dinámica

• Si sc > se, están del mismo lado del plano y |sc| > r, |se| > r, no hubo colisión, y la esfera llegó al punto e.

• Caso contrario, hubo colisión.

• Si hubo colisión el tiempo es

• c + tv, ubicación del centro después de la colisión.• (1- t)r velocidad de la reflexión, r dirección de la reflexión.• (1- t) tiempo que falta para el frame siguiente.

17/09/2018 Computación Gráfica Avanzada: Detección de Colisiones 68

Test de intersección dinámica

• La esfera punteada está donde ocurre la colisión.• sc y se son distancias con signo.

17/09/2018 Computación Gráfica Avanzada: Detección de Colisiones 69

Test de intersección dinámica

• Esfera - Esfera

• Usamos el principio del movimiento relativo, haciendo de la esfera B estática, la esfera A es la que se mueve con velocidad relativa VAB = VA - VB.

• Se agranda la esfera B con el radio de la esfera A.• La esfera A se toma como un punto que se mueve a lo largo de

la recta.

17/09/2018 Computación Gráfica Avanzada: Detección de Colisiones 70

Test de intersección dinámica

• Surge de la ecuación de intersecar un segmento con una esfera.

• cA y cB son los respectivos centros de las esferas A y B.• Se forma una ecuación de 2do grado en t, cuya raíz de menor

valor (positiva) es el tiempo de intersección.

17/09/2018 Computación Gráfica Avanzada: Detección de Colisiones 71

Test de intersección dinámica

• Esfera - Polígono

• Le aplicamos la suma de Minkowski a dos objetos.• De esa forma calculamos la intersección de un rayo con la suma

de Minkowski de la esfera con el polígono.• Resultado:

– vértices, se transforman en esferas de radio r.– bordes, en cilindros de radio r.– el polígono se duplica para sellar el objeto.

17/09/2018 Computación Gráfica Avanzada: Detección de Colisiones 72

Test de intersección dinámica

• El algoritmo de ambos casos son equivalentes.

17/09/2018 Computación Gráfica Avanzada: Detección de Colisiones 73

Test de intersección dinámica

• Se aplican los métodos de acuerdo al menor costo computacional, de ese modo si existe colisión, finalizamos la prueba, evitando aplicar los algoritmos más costosos primero.

• El primer algoritmo a usar es el que verifica la intersección de la esfera con los polígonos. Ya que como el área no está cubierta por esferas o cilindros, si la esfera está frente a la esfera, nos da la distancia mínima a la que hubo impacto con el objeto.

• Si no hubo, se verifica la intersección con la parte exterior del cilindro, que si existe, siempre estará más cerca que la intersección con la esfera más cercana.

• Si no hubo intersección con el cilindro, se hace la prueba de intersección de la esfera con los vértices.

17/09/2018 Computación Gráfica Avanzada: Detección de Colisiones 74

Método dinámico del eje de separación

• En las consultas dinámicas se aplica el método Separating Axis Test (SAT) en todos los intervalos de tiempo en los cuales el movimiento de los objetos ocurre.

• SAT : se proyectan los polígonos de los objetos de la escena sobre todos los ejes. Si hay superposición de las proyecciones para todos los ejes, hay colisión. De lo contrario, no.

• La idea es hacer SAT a los intervalos proyectados que se mueven a lo largo del tiempo y verificar si hay superposición.

17/09/2018 Computación Gráfica Avanzada: Detección de Colisiones 75

Referencias

• Real Time Rendering 4ta edición Collision Detection. Haines, Hoffman, Möller.

• Jeroen Baert, curvas de Morton.• Gamasutra, BSP Collision Detection As Used In MDK2 and

NeverWinter Nights.

• Partículas– Real-Time Simulation and Rendering of 3D Fluids - GPU Gems (Nvidia)– Ejemplos (framework Processing)

• sistemas de partículas• simulación

17/09/2018 Computación Gráfica Avanzada: Detección de Colisiones 76

Gracias por su atención

Rossana Guerra

rossana.guerra@fing.edu.uy