Tutorial de Física de Videojuegos - Parte II: Detección de Colisiones para Objetos Sólidos

Esta es la Parte II de nuestra serie de tres partes sobre la física de los videojuegos. Para el resto de esta serie, consulte:

Parte I: Introducción a la dinámica de cuerpos rígidos
Parte III: Simulación de cuerpo rígido restringido

En la Parte I de esta serie, exploramos los cuerpos rígidos y sus movimientos. En esa discusión, sin embargo, los objetos no interactuaron entre sí. Sin trabajo adicional, los cuerpos rígidos simulados pueden atravesarse o “interpenetrarse”, lo que no es deseable en la mayoría de los casos.

Para simular de forma más realista el comportamiento de los objetos sólidos, tenemos que comprobar si chocan entre sí cada vez que se mueven, y si lo hacen, tenemos que hacer algo al respecto, como aplicar fuerzas que cambien sus velocidades, para que que se moverán en la dirección opuesta. Aquí es donde la comprensión de la física de las colisiones es particularmente importante para los desarrolladores de juegos.

En la Parte II, cubriremos el paso de detección de colisiones, que consiste en encontrar pares de cuerpos que chocan entre una cantidad posiblemente grande de cuerpos dispersos alrededor de un mundo 2D o 3D. En la próxima y última entrega, hablaremos más sobre cómo “resolver” estas colisiones para eliminar las interpenetraciones.

Para una revisión de los conceptos de álgebra lineal a los que se hace referencia en este artículo, puede consultar el curso intensivo de álgebra lineal en la Parte I.

Física de colisiones en videojuegos

En el contexto de las simulaciones de cuerpos rígidos, ocurre una colisión cuando las formas de dos cuerpos rígidos se cruzan, o cuando la distancia entre estas formas cae por debajo de una pequeña tolerancia.

Si tenemos n cuerpos en nuestra simulación, la complejidad computacional de detectar colisiones con pruebas por pares es O ( n 2 ) , un número que hace que los científicos informáticos se estremezcan. El número de pruebas por parejas aumenta cuadráticamente con el número de cuerpos, y determinar si dos formas, en posiciones y orientaciones arbitrarias, están chocando ya no es barato. Para optimizar el proceso de detección de colisiones, generalmente lo dividimos en dos fases: fase amplia y fase estrecha .

La fase amplia se encarga de encontrar pares de cuerpos rígidos potencialmente colisionantes, y excluir pares que ciertamente no colisionen, de entre todo el conjunto de cuerpos que están en la simulación. Este paso debe poder escalar muy bien con el número de cuerpos rígidos para asegurarnos de que nos mantenemos bien por debajo de la complejidad de tiempo O ( n 2 ) . Para lograrlo, esta fase generalmente utiliza la partición del espacio junto con volúmenes delimitadores que establecen un límite superior para la colisión.

La fase estrecha opera sobre los pares de cuerpos rígidos encontrados por la fase ancha que podrían estar colisionando. Es un paso de refinamiento en el que determinamos si las colisiones realmente están ocurriendo y, para cada colisión que se encuentra, calculamos los puntos de contacto que se utilizarán para resolver las colisiones más adelante.

En las siguientes secciones, hablaremos sobre algunos algoritmos que se pueden usar en la fase amplia y la fase estrecha.

Fase amplia

En la fase amplia de la física de colisiones para videojuegos, necesitamos identificar qué pares de cuerpos rígidos podrían estar colisionando. Estos cuerpos pueden tener formas complejas como polígonos y poliedros, y lo que podemos hacer para acelerar esto es usar una forma más simple para abarcar el objeto. Si estos volúmenes delimitadores no se intersecan, las formas reales tampoco se intersecan. Si se cruzan, entonces las formas reales podrían cruzarse.

Algunos tipos populares de volúmenes delimitadores son cuadros delimitadores orientados (OBB), círculos en 2D y esferas en 3D. Veamos uno de los volúmenes delimitadores más simples: los cuadros delimitadores alineados con el eje (AABB) .

Los AABB reciben mucho cariño de los programadores de física porque son simples y ofrecen buenas compensaciones. Un AABB bidimensional puede representarse mediante una estructura como esta en lenguaje C:

 typedef struct { float x; float y; } Vector2; typedef struct { Vector2 min; Vector2 max; } AABB;

El campo min representa la ubicación de la esquina inferior izquierda del cuadro y el campo max representa la esquina superior derecha.

Para probar si dos AABB se cruzan, solo tenemos que averiguar si sus proyecciones se cruzan en todos los ejes de coordenadas:

 BOOL TestAABBOverlap(AABB* a, AABB* b) { float d1x = b->min.x - a->max.x; float d1y = b->min.y - a->max.y; float d2x = a->min.x - b->max.x; float d2y = a->min.y - b->max.y; if (d1x > 0.0f || d1y > 0.0f) return FALSE; if (d2x > 0.0f || d2y > 0.0f) return FALSE; return TRUE; }

Este código tiene la misma lógica de la función b2TestOverlap del motor Box2D (versión 2.3.0). Calcula la diferencia entre el min y el max de ambos AABB, en ambos ejes, en ambos órdenes. Si alguno de estos valores es mayor que cero, los AABB no se cruzan.

Aunque una prueba de superposición de AABB es barata, no ayudará mucho si aún hacemos pruebas por pares para cada par posible, ya que todavía tenemos la indeseable complejidad de tiempo O ( n 2 ) . Para minimizar la cantidad de pruebas de superposición de AABB, podemos usar algún tipo de partición espacial , que funciona con los mismos principios que los índices de la base de datos que aceleran las consultas. (Las bases de datos geográficas, como PostGIS, en realidad usan estructuras de datos y algoritmos similares para sus índices espaciales). Sin embargo, en este caso, los AABB se moverán constantemente, por lo que, en general, debemos recrear los índices después de cada paso de la simulación.

Hay muchos algoritmos de partición de espacio y estructuras de datos que se pueden usar para esto, como cuadrículas uniformes, quadtrees en 2D, octrees en 3D y hashing espacial. Echemos un vistazo más de cerca a dos algoritmos populares de partición espacial: clasificación y barrido, y jerarquías de volumen delimitador (BVH).

El algoritmo de clasificación y barrido

El método de clasificación y barrido (también conocido como barrido y podado ) es una de las opciones favoritas entre los programadores de física para su uso en la simulación de cuerpos rígidos. El motor Bullet Physics, por ejemplo, tiene una implementación de este método en la clase btAxisSweep3 .

La proyección de un AABB en un solo eje de coordenadas es esencialmente un intervalo [ b , e ] (es decir, principio y fin). En nuestra simulación, tendremos muchos cuerpos rígidos y, por lo tanto, muchos AABB, y eso significa muchos intervalos. Queremos saber qué intervalos se intersecan.

En el algoritmo de ordenación y barrido, insertamos todos los valores b y e en una sola lista y la ordenamos de forma ascendente por sus valores escalares. Luego hacemos un barrido o recorremos la lista. Cada vez que se encuentra un valor b , su intervalo correspondiente se almacena en una lista separada de intervalos activos , y cada vez que se encuentra un valor e , su intervalo correspondiente se elimina de la lista de intervalos activos. En cualquier momento, todos los intervalos activos se cruzan. (Consulte la tesis doctoral de David Baraff, p. 52 para obtener detalles. Sugiero usar esta herramienta en línea para ver el archivo postscript). La lista de intervalos se puede reutilizar en cada paso de la simulación, donde podemos reordenar de manera eficiente esta lista usando la ordenación por inserción, que es buena para ordenar listas casi ordenadas.

En dos y tres dimensiones, ejecutar la ordenación y el barrido, como se describió anteriormente, sobre un único eje de coordenadas reducirá el número de pruebas de intersección AABB directas que se deben realizar, pero el resultado puede ser mejor sobre un eje de coordenadas que sobre otro. Por lo tanto, se implementan variaciones más sofisticadas del algoritmo de clasificación y barrido. En su libro Detección de colisiones en tiempo real (página 336), Christer Ericson presenta una variación eficiente en la que almacena todos los AABB en una sola matriz, y para cada ejecución de ordenación y barrido, se elige un eje de coordenadas y la matriz se ordena por el valor min de los AABB en el eje elegido, usando quicksort. Luego, se atraviesa la matriz y se realizan pruebas de superposición AABB. Para determinar el siguiente eje que debe usarse para clasificar, se calcula la varianza del centro de los AABB y se elige el eje con mayor varianza para el siguiente paso.

Árboles de volumen delimitadores dinámicos

Otro método útil de partición espacial es el árbol de volumen delimitador dinámico , también conocido como Dbvt . Este es un tipo de jerarquía de volumen límite .

El Dbvt es un árbol binario en el que cada nodo tiene un AABB que delimita todos los AABB de sus hijos. Los AABB de los propios cuerpos rígidos se encuentran en los nodos de hoja. Por lo general, un Dbvt se "consulta" proporcionando el AABB para el que nos gustaría detectar intersecciones. Esta operación es eficiente porque los hijos de los nodos que no se cruzan con el AABB consultado no necesitan ser probados para la superposición. Como tal, una consulta de colisión AABB comienza desde la raíz y continúa recursivamente a través del árbol solo para los nodos AABB que se cruzan con el AABB consultado. El árbol se puede equilibrar mediante rotaciones de árboles, como en un árbol AVL.

Box2D tiene una implementación sofisticada de Dbvt en la clase b2DynamicTree . La clase b2BroadPhase es responsable de realizar la fase amplia y utiliza una instancia de b2DynamicTree para realizar consultas AABB.

Fase estrecha

Después de la amplia fase de la física de colisión de los videojuegos, tenemos un conjunto de pares de cuerpos rígidos que potencialmente colisionan. Así, para cada par, dada la forma, posición y orientación de ambos cuerpos, necesitamos averiguar si, de hecho, están chocando; si se cruzan o si su distancia cae por debajo de un valor de tolerancia pequeño. También necesitamos saber qué puntos de contacto hay entre los cuerpos que chocan, ya que esto es necesario para resolver las colisiones más adelante.

Formas convexas y cóncavas

Como regla general de la física de los videojuegos, no es trivial determinar si dos formas arbitrarias se intersecan o calcular la distancia entre ellas. Sin embargo, una propiedad que es de importancia crítica para determinar qué tan duro es, es la convexidad de la forma. Las formas pueden ser convexas o cóncavas y las formas cóncavas son más difíciles de trabajar, por lo que necesitamos algunas estrategias para manejarlas.

En una forma convexa, un segmento de línea entre dos puntos dentro de la forma siempre cae completamente dentro de la forma. Sin embargo, para una forma cóncava (o “no convexa”), no ocurre lo mismo con todos los posibles segmentos de línea que conectan puntos en la forma. Si puede encontrar al menos un segmento de línea que quede fuera de la forma, entonces la forma es cóncava.

Desde el punto de vista computacional, es deseable que todas las formas sean convexas en una simulación, ya que tenemos muchos algoritmos potentes de prueba de distancia e intersección que funcionan con formas convexas. Sin embargo, no todos los objetos serán convexos y, por lo general, trabajamos alrededor de ellos de dos maneras: casco convexo y descomposición convexa.

El casco convexo de una forma es la forma convexa más pequeña que la contiene por completo. Para un polígono cóncavo en dos dimensiones, sería como martillar un clavo en cada vértice y envolver todos los clavos con una banda elástica. Para calcular la envolvente convexa de un polígono o poliedro, o más generalmente, de un conjunto de puntos, un buen algoritmo para usar es el algoritmo de envolvente rápida , que tiene una complejidad de tiempo promedio de O ( n log n ) .

Obviamente, si usamos un casco convexo para representar un objeto cóncavo, perderá sus propiedades cóncavas. El comportamiento indeseable, como las colisiones "fantasmas", puede volverse evidente, ya que el objeto seguirá teniendo una representación gráfica cóncava. Por ejemplo, un automóvil generalmente tiene una forma cóncava, y si usamos un casco convexo para representarlo físicamente y luego le colocamos una caja, la caja podría parecer que está flotando en el espacio de arriba.

En general, los cascos convexos suelen ser lo suficientemente buenos para representar objetos cóncavos, ya sea porque las colisiones poco realistas no son muy perceptibles o porque sus propiedades cóncavas no son esenciales para lo que se está simulando. En algunos casos, sin embargo, es posible que queramos que el objeto cóncavo se comporte físicamente como una forma cóncava. Por ejemplo, si usamos un casco convexo para representar físicamente un cuenco, no podremos poner nada dentro de él. Los objetos simplemente flotarán encima de él. En este caso, podemos usar una descomposición convexa de la forma cóncava.

Los algoritmos de descomposición convexa reciben una forma cóncava y devuelven un conjunto de formas convexas cuya unión es idéntica a la forma cóncava original. Algunas formas cóncavas solo se pueden representar mediante una gran cantidad de formas convexas, y estas pueden volverse prohibitivamente costosas de calcular y usar. Sin embargo, una aproximación suele ser lo suficientemente buena y, por lo tanto, algoritmos como V-HACD producen un pequeño conjunto de poliedros convexos a partir de un poliedro cóncavo.

Sin embargo, en muchos casos de física de colisiones, un artista puede hacer la descomposición convexa a mano. Esto elimina la necesidad de gravar el rendimiento con algoritmos de descomposición. Dado que el rendimiento es uno de los aspectos más importantes en las simulaciones en tiempo real, generalmente es una buena idea crear representaciones físicas muy simples para objetos gráficos complejos. La siguiente imagen muestra una posible descomposición convexa de un automóvil 2D usando nueve formas convexas.

Prueba de intersecciones: el teorema del eje de separación

El teorema del eje de separación (SAT) establece que dos formas convexas no se intersecan si y solo si existe al menos un eje donde las proyecciones ortogonales de las formas en este eje no se intersecan.

Sin embargo, por lo general es visualmente más intuitivo encontrar una línea en 2D o un plano en 3D que separe las dos formas, que es efectivamente el mismo principio. Como “eje de separación” se puede utilizar un vector ortogonal a la línea en 2D, o el vector normal del plano en 3D.

Los motores de física de juegos tienen varias clases diferentes de formas, como círculos (esferas en 3D), bordes (un segmento de una sola línea) y polígonos convexos (poliedros en 3D). Para cada par de tipos de forma, tienen un algoritmo de detección de colisión específico. El más simple de ellos es probablemente el algoritmo círculo-círculo:

 typedef struct { float centerX; float centerY; float radius; } Circle; bool CollideCircles(Circle *cA, Circle *cB) { float x = cA->centerX - cB->centerX; float y = cA->centerY - cB->centerY; float centerDistanceSq = x * x + y * y; // squared distance float radius = cA->radius + cB->radius; float radiusSq = radius * radius; return centerDistanceSq <= radiusSq; }

Aunque el SAT se aplica a los círculos, es mucho más sencillo comprobar si la distancia entre sus centros es menor que la suma de sus radios. Por esa razón, el SAT se usa en el algoritmo de detección de colisiones para pares específicos de clases de forma, como polígono convexo contra polígono convexo (o poliedros en 3D).

Para cualquier par de formas, hay un número infinito de ejes que podemos probar para la separación. Por lo tanto, determinar qué eje probar primero es crucial para una implementación eficiente del SAT. Afortunadamente, cuando probamos si un par de polígonos convexos chocan, podemos usar los bordes normales como posibles ejes de separación. El vector normal n de un borde es perpendicular al vector borde y apunta fuera del polígono. Para cada borde de cada polígono, solo necesitamos averiguar si todos los vértices del otro polígono están frente al borde.

Si pasa cualquier prueba, es decir, si, para cualquier borde, todos los vértices del otro polígono están frente a él, entonces los polígonos no se intersecan. El álgebra lineal proporciona una fórmula fácil para esta prueba: dada una arista en la primera forma con vértices a y b y un vértice v en la otra forma, si ( v - a ) · n es mayor que cero, entonces el vértice está al frente del borde

Para los poliedros, podemos usar las caras normales y también el producto vectorial de todas las combinaciones de aristas de cada forma. Eso suena como un montón de cosas para probar; sin embargo, para acelerar las cosas, podemos almacenar en caché el último eje de separación que usamos e intentar usarlo nuevamente en los siguientes pasos de la simulación. Si el eje de separación almacenado en caché ya no separa las formas, podemos buscar un nuevo eje a partir de las caras o aristas que son adyacentes a la cara o arista anterior. Eso funciona porque los cuerpos a menudo no se mueven ni giran mucho entre los pasos.

Box2D usa SAT para probar si dos polígonos convexos se cruzan en su algoritmo de detección de colisiones polígono-polígono en b2CollidePolygon.cpp.

Distancia de cálculo: el algoritmo de Gilbert-Johnson-Keerthi

En muchos casos de física de colisiones, queremos considerar que los objetos colisionan no solo si realmente se cruzan, sino también si están muy cerca uno del otro, lo que requiere que conozcamos la distancia entre ellos. El algoritmo Gilbert-Johnson-Keerthi (GJK) calcula la distancia entre dos formas convexas y también sus puntos más cercanos. Es un algoritmo elegante que trabaja con una representación implícita de formas convexas a través de funciones de soporte, sumas de Minkowski y símplex, como se explica a continuación.

Funciones de apoyo

Una función de soporte s A ( d ) devuelve un punto en el límite de la forma A que tiene la proyección más alta en el vector d . Matemáticamente, tiene el producto escalar más alto con d . Esto se denomina punto de apoyo , y esta operación también se conoce como mapeo de apoyo . Geométricamente, este punto es el punto más lejano de la forma en la dirección de d .

Encontrar un punto de apoyo en un polígono es relativamente fácil. Para un punto de apoyo para el vector d , solo tienes que recorrer sus vértices y encontrar el que tiene el producto escalar más alto con d , así:

 Vector2 GetSupport(Vector2 *vertices, int count, Vector2 d) { float highest = -FLT_MAX; Vector2 support = (Vector2){0, 0}; for (int i = 0; i < count; ++i) { Vector2 v = vertices[i]; float dot = vx * dx + vy * dy; if (dot > highest) { highest = dot; support = v; } } return support; }

Sin embargo, el verdadero poder de una función de soporte es que facilita el trabajo con formas como conos, cilindros y elipses, entre otras. Es bastante difícil calcular la distancia entre tales formas directamente, y sin un algoritmo como GJK normalmente tendrías que discretizarlas en un polígono o poliedro para simplificar las cosas. Sin embargo, eso podría generar más problemas porque la superficie de un poliedro no es tan suave como la superficie de, por ejemplo, una esfera, a menos que el poliedro esté muy detallado, lo que puede provocar un rendimiento deficiente durante la detección de colisiones. También pueden aparecer otros efectos secundarios indeseables; por ejemplo, una esfera "poliédrica" ​​podría no rodar suavemente.

Para obtener un punto de apoyo para una esfera centrada en el origen, solo tenemos que normalizar d (es decir, calcular d / || d || , que es un vector con longitud 1 (unidad de longitud) que todavía apunta en la misma dirección de d ) y luego lo multiplicamos por el radio de la esfera.

Consulte el artículo de Gino van den Bergen para encontrar más ejemplos de funciones de soporte para cilindros y conos, entre otras formas.

Nuestros objetos, por supuesto, se desplazarán y rotarán desde el origen en el espacio de simulación, por lo que debemos poder calcular los puntos de apoyo para una forma transformada. Usamos una transformación afín T ( x ) = R x + c para desplazar y rotar nuestros objetos, donde c es el vector de desplazamiento y R es la matriz de rotación . Esta transformación primero gira el objeto sobre el origen y luego lo traslada. La función de soporte para una forma transformada A es:

Sumas de Minkowski

La suma de Minkowski de dos formas A y B se define como:

Eso significa que calculamos la suma de todos los puntos contenidos en A y B. El resultado es como inflar A con B.

Del mismo modo, definimos la diferencia de Minkowski como:

que también podemos escribir como la suma de Minkowski de A con -B :

Para A y B convexos, A⊕B también es convexo.

Una propiedad útil de la diferencia de Minkowski es que si contiene el origen del espacio, las formas se cruzan, como se puede ver en la imagen anterior. ¿Porqué es eso? Porque si dos formas se cruzan, tienen al menos un punto en común, que se encuentran en la misma ubicación en el espacio, y su diferencia es el vector cero, que en realidad es el origen.

Otra buena característica de la diferencia de Minkowski es que si no contiene el origen, la distancia mínima entre el origen y la diferencia de Minkowski es la distancia entre las formas.

La distancia entre dos formas se define como:

En otras palabras, la distancia entre A y B es la longitud del vector más corto que va de A a B. Este vector está contenido en A⊖B y es el de menor longitud, por lo que es el más cercano al origen.

Por lo general, no es simple construir explícitamente la suma de Minkowski de dos formas. Afortunadamente, también podemos usar el mapeo de soporte aquí, ya que:

simples

El algoritmo GJK busca iterativamente el punto de la diferencia de Minkowski más cercano al origen. Lo hace construyendo una serie de simplexes que están más cerca del origen en cada iteración. Un simplex, o más específicamente, un k-simplex para un entero k , es la envolvente convexa de k + 1 puntos afinemente independientes en un espacio k-dimensional. Es decir, si para dos puntos no deben coincidir, para tres puntos tampoco deben estar en la misma recta, y si tenemos cuatro puntos tampoco deben estar en el mismo plano. Por lo tanto, el 0-simple es un punto, el 1-simple es un segmento de línea, el 2-simple es un triángulo y el 3-simple es un tetraedro. Si quitamos un punto de un simplex, decrementamos su dimensionalidad en uno, y si agregamos un punto a un simplex, incrementamos su dimensionalidad en uno.

GJK en acción

Pongamos todo esto junto para ver cómo funciona GJK. Para determinar la distancia entre dos formas A y B , comenzamos tomando su diferencia de Minkowski A⊖B . Estamos buscando el punto más cercano al origen de la forma resultante, ya que la distancia a este punto es la distancia entre las dos formas originales. Elegimos algún punto v en A⊖B , que será nuestra aproximación de distancia. También definimos un conjunto de puntos vacío W , que contendrá los puntos en el simplex de prueba actual.

Entonces entramos en un bucle. Empezamos por obtener el punto de apoyo w = s A⊖B (- v ) , el punto en A⊖B cuya proyección sobre v es la más cercana al origen.

Si || w || no es muy diferente a || v || y el ángulo entre ellos no cambió mucho (según algunas tolerancias predefinidas), significa que el algoritmo ha convergido y podemos regresar || v || como la distancia.

De lo contrario, sumamos w a W . Si el casco convexo de W (es decir, el símplex) contiene el origen, las formas se intersecan, y esto también significa que hemos terminado. De lo contrario, buscamos el punto en el símplex más cercano al origen y luego restablecemos v para que sea esta nueva aproximación más cercana. Finalmente, eliminamos cualquier punto en W que no contribuya al cálculo del punto más cercano. (Por ejemplo, si tenemos un triángulo y el punto más cercano al origen se encuentra en una de sus aristas, podemos eliminar el punto de W que no es un vértice de esta arista). Luego repetimos estos mismos pasos hasta que el algoritmo converge

La siguiente imagen muestra un ejemplo de cuatro iteraciones del algoritmo GJK. El objeto azul representa la diferencia de Minkowski A⊖B y el vector verde es v . Puede ver aquí cómo v se afina en el punto más cercano al origen.

Para obtener una explicación detallada y detallada del algoritmo GJK, consulte el artículo Una implementación GJK rápida y robusta para la detección de colisiones de objetos convexos , de Gino van den Bergen. El blog del motor de física dyn4j también tiene una excelente publicación sobre GJK.

Box2D tiene una implementación del algoritmo GJK en b2Distance.cpp, en la función b2Distance . Solo usa GJK durante el cálculo del tiempo de impacto en su algoritmo para la detección continua de colisiones (un tema que discutiremos más adelante).

El motor de física Chimpunk usa GJK para todas las detecciones de colisión, y su implementación está en cpCollision.c, en la función GJK . Si el algoritmo GJK informa de intersección, aún necesita saber cuáles son los puntos de contacto, junto con la profundidad de penetración. Para hacer eso, utiliza el Algoritmo de Politopo en Expansión, que exploraremos a continuación.

Determinación de la profundidad de penetración: el algoritmo del politopo en expansión

Como se indicó anteriormente, si las formas A y B se intersecan, GJK generará un simplex W que contiene el origen, dentro de la diferencia de Minkowski A⊖B . En esta etapa, solo sabemos que las formas se intersecan, pero en el diseño de muchos sistemas de detección de colisiones, es deseable poder calcular cuánta intersección tenemos y qué puntos podemos usar como puntos de contacto, de modo que manejamos la colisión de una manera realista. El Algoritmo de Expansión de Politopos (EPA) nos permite obtener esa información, comenzando donde lo dejó GJK: con un símplex que contiene el origen.

La profundidad de penetración es la longitud del vector de traslación mínimo (MTV), que es el vector más pequeño a lo largo del cual podemos trasladar una forma que se cruza para separarla de la otra forma.

Cuando dos formas se intersecan, su diferencia de Minkowski contiene el origen, y el punto en el límite de la diferencia de Minkowski que está más cerca del origen es el MTV. El algoritmo de la EPA encuentra ese punto expandiendo el símplex que nos dio GJK en un polígono; subdividiendo sucesivamente sus aristas con nuevos vértices.

Primero, encontramos el borde del símplex más cercano al origen y calculamos el punto de apoyo en la diferencia de Minkowski en una dirección que es normal al borde (es decir, perpendicular a él y apuntando fuera del polígono). Luego dividimos este borde añadiéndole este punto de apoyo. Repetimos estos pasos hasta que la longitud y la dirección del vector no cambien mucho. Una vez que el algoritmo converge, tenemos el MTV y la profundidad de penetración.

Usando GJK en combinación con EPA, obtenemos una descripción detallada de la colisión, sin importar si los objetos ya se están cruzando o si están lo suficientemente cerca como para considerar una colisión.

El algoritmo EPA se describe en el artículo Proximity Queries and Penetration Depth Computation on 3D Game Objects , también escrito por Gino van den Bergen. El blog dyn4j también tiene una publicación sobre la EPA.

Detección continua de colisiones

Las técnicas de física de videojuegos presentadas hasta ahora realizan la detección de colisiones para una instantánea estática de la simulación. Esto se denomina detección de colisión discreta e ignora lo que sucede entre los pasos anterior y actual. Por esta razón, es posible que no se detecten algunas colisiones, especialmente para objetos que se mueven rápidamente. Este problema se conoce como tunelización .

Las técnicas de detección de colisión continua intentan encontrar cuándo chocaron dos cuerpos entre el paso anterior y el actual de la simulación. Calculan el momento del impacto , por lo que podemos retroceder en el tiempo y procesar la colisión en ese punto.

El tiempo de impacto (o tiempo de contacto) t c es el instante de tiempo en que la distancia entre dos cuerpos es cero. Si podemos escribir una función para la distancia entre dos cuerpos a lo largo del tiempo, lo que queremos encontrar es la raíz más pequeña de esta función. Por lo tanto, el cálculo del tiempo de impacto es un problema de búsqueda de raíces .

Para el cálculo del tiempo de impacto, consideramos el estado (posición y orientación) del cuerpo en el paso anterior en el tiempo ti -1 , y en el paso actual en el tiempo ti . Para simplificar las cosas, asumimos un movimiento lineal entre los pasos.

Simplifiquemos el problema asumiendo que las formas son círculos. Para dos círculos C 1 y C 2 , con radio r 1 y r 2 , donde su centro de masa x 1 y x 2 coinciden con su centroide (es decir, naturalmente giran alrededor de su centro de masa), podemos escribir la función de distancia como:

Considerando el movimiento lineal entre pasos, podemos escribir la siguiente función para la posición de C 1 desde ti -1 hasta ti

Es una interpolación lineal de x 1 ( t i -1 ) a x 1 ( t i ) . Lo mismo se puede hacer para x 2 . Para este intervalo podemos escribir otra función de distancia:

Iguale esta expresión a cero y obtendrá una ecuación cuadrática en t . Las raíces se pueden encontrar directamente usando la fórmula cuadrática. Si los círculos no se cortan, la fórmula cuadrática no tendrá solución. Si lo hacen, podría resultar en una o dos raíces. Si tiene una sola raíz, ese valor es el tiempo de impacto. Si tiene dos raíces, la más pequeña es el momento del impacto y la otra es el momento en que los círculos se separan. Tenga en cuenta que el tiempo de impacto aquí es un número de 0 a 1. No es un tiempo en segundos; es solo un número que podemos usar para interpolar el estado de los cuerpos a la ubicación precisa donde ocurrió la colisión.

Detección continua de colisiones para no círculos

Escribir una función de distancia para otros tipos de formas es difícil, principalmente porque su distancia depende de sus orientaciones. Por esta razón, generalmente usamos algoritmos iterativos que mueven los objetos más y más cerca en cada iteración hasta que están lo suficientemente cerca como para considerarlos en colisión.

El algoritmo de avance conservador mueve los cuerpos hacia adelante (y los rota) iterativamente. En cada iteración calcula un límite superior para el desplazamiento. El algoritmo original se presenta en la tesis doctoral de Brian Mirtich (sección 2.3.2), que considera el movimiento balístico de los cuerpos. Este artículo de Erwin Coumans (el autor de Bullet Physics Engine) presenta una versión más simple que utiliza velocidades lineales y angulares constantes.

El algoritmo calcula los puntos más cercanos entre las formas A y B , dibuja un vector de un punto al otro y proyecta la velocidad en este vector para calcular un límite superior para el movimiento. Garantiza que ningún punto del cuerpo se moverá más allá de esta proyección. Luego avanza los cuerpos hacia adelante en esta cantidad y repite hasta que la distancia cae por debajo de un pequeño valor de tolerancia.

Puede tomar demasiadas iteraciones para converger en algunos casos, por ejemplo, cuando la velocidad angular de uno de los cuerpos es demasiado alta.

Resolución de colisiones

Una vez que se ha detectado una colisión, es necesario cambiar los movimientos de los objetos que chocan de una manera realista, como hacer que reboten entre sí. En la próxima y última entrega de estas teorías, discutiremos algunos métodos populares para resolver colisiones en los videojuegos.

Referencias

Si está interesado en obtener una comprensión más profunda de la física de las colisiones, como los algoritmos y las técnicas de detección de colisiones, el libro Detección de colisiones en tiempo real , de Christer Ericson, es imprescindible.

Dado que la detección de colisiones depende en gran medida de la geometría, el artículo Geometría computacional en Python: de la teoría a la aplicación de Toptal es una excelente introducción al tema.