Detección de colisiones

Bajo el término "particionamiento espacial" se pueden agrupar varios enfoques , entre los que se incluyen octrees (para 3D), quadtrees (para 2D), particionamiento espacial binario (o árboles BSP) y otros enfoques similares. Si se divide el espacio en varias celdas simples y se puede demostrar que dos objetos no se encuentran en la misma celda, no es necesario comprobar su intersección. Las escenas dinámicas y los objetos deformables requieren actualizar el particionamiento, lo que puede generar una sobrecarga.

La jerarquía de volúmenes delimitadores (BVH) es una estructura de árbol sobre un conjunto de volúmenes delimitadores . La colisión se determina mediante un recorrido del árbol que comienza desde la raíz. Si el volumen delimitador de la raíz no interseca con el objeto de interés, el recorrido se puede detener. Sin embargo, si hay una intersección, el recorrido continúa y verifica las ramas para cada una de ellas. Las ramas que no tienen intersección con el volumen delimitador se pueden descartar de la prueba de intersección posterior. Por lo tanto, se puede determinar que varios objetos no intersecan a la vez. BVH se puede usar con objetos deformables como tela o cuerpos blandos, pero la jerarquía de volúmenes debe ajustarse a medida que la forma se deforma. Para objetos deformables, debemos considerar las autocolisiones o autointersecciones. BVH también se puede usar para este fin. La colisión entre dos objetos se calcula calculando la intersección entre los volúmenes delimitadores de la raíz del árbol; a medida que hay colisión, exploramos los subárboles que se intersecan. Las colisiones exactas entre los objetos reales, o sus partes (a menudo triángulos de una malla triangular ), deben calcularse solo entre hojas que se intersecan. ^{[ 7 ]} El mismo enfoque funciona para colisiones por pares y autocolisiones.

Durante la fase general, cuando los objetos del mundo se mueven o se deforman, es necesario actualizar las estructuras de datos utilizadas para descartar colisiones. En los casos en que los cambios entre dos fotogramas o pasos de tiempo son pequeños y los objetos se pueden aproximar bien con cuadros delimitadores alineados con los ejes , el algoritmo de barrido y poda ^{[ 5 ]} puede ser un enfoque adecuado.

Varias observaciones clave hacen que la implementación sea eficiente: Dos cuadros delimitadores se intersecan si, y solo si , hay superposición a lo largo de los tres ejes; la superposición se puede determinar, para cada eje por separado, ordenando los intervalos de todos los cuadros; y, por último, las actualizaciones entre dos fotogramas suelen ser pequeñas (lo que hace que los algoritmos de ordenación optimizados para listas casi ordenadas sean adecuados para esta aplicación). El algoritmo realiza un seguimiento de los cuadros que se intersecan actualmente, y a medida que los objetos se mueven, la reordenación de los intervalos ayuda a mantener el seguimiento del estado. ^{[ 8 ]}

Una vez que se ha seleccionado un par de cuerpos físicos para una investigación más profunda, es necesario comprobar las colisiones con mayor cuidado. Sin embargo, en muchas aplicaciones, los objetos individuales (si no son demasiado deformables) se describen mediante un conjunto de primitivas más pequeñas, principalmente triángulos. Por lo tanto, hay dos conjuntos de triángulos,${\displaystyle S={S_{1},S_{2},\dots ,S_{n}}}$y${\displaystyle T={T_{1},T_{2},\dots ,T_{n}}}$(Para simplificar, cada conjunto tiene el mismo número de triángulos).

Lo obvio es revisar todos los triángulos.${\displaystyle S_{j}}$contra todos los triángulos${\displaystyle T_{k}}$para colisiones, pero esto implica${\displaystyle n^{2}}$comparaciones, lo cual es muy ineficiente. Si es posible, es conveniente utilizar un algoritmo de poda para reducir el número de pares de triángulos que deben comprobarse.

La familia de algoritmos más utilizada se conoce como el método de volúmenes delimitadores jerárquicos . Como paso de preprocesamiento, para cada objeto (por ejemplo,${\displaystyle S}$y${\displaystyle T}$) calcula una jerarquía de volúmenes delimitadores . Luego, en cada paso de tiempo, cuando se necesitan comprobar las colisiones entre${\displaystyle S}$y${\displaystyle T}$Los volúmenes delimitadores jerárquicos se utilizan para reducir el número de pares de triángulos considerados. Para simplificar, se proporciona un ejemplo con esferas delimitadoras, aunque se ha señalado que las esferas no son deseables en muchos casos.

Si${\displaystyle E}$es un conjunto de triángulos, se precalcula una esfera delimitadora.${\displaystyle B(E)}$Hay muchas maneras de elegir${\displaystyle B(E)}$, ${\displaystyle B(E)}$es una esfera que contiene completamente${\displaystyle E}$y es lo más pequeño posible.

Con antelación,${\displaystyle B(S)}$y${\displaystyle B(T)}$se puede calcular. Claramente, si estas dos esferas no se intersecan (y eso es muy fácil de comprobar), entonces tampoco${\displaystyle S}$y${\displaystyle T}$Sin embargo , esto no es mucho mejor que un algoritmo de poda de n cuerpos.

Si${\displaystyle E={E_{1},E_{2},\dots,E_{m}}}$es un conjunto de triángulos, luego divídelo en dos mitades${\displaystyle L(E):={E_{1},E_{2},\dots,E_{m/2}}}$y${\displaystyle R(E):={E_{m/2+1},\dots ,E_{m-1},E_{m}}}$. Aplique esto a${\displaystyle S}$y${\displaystyle T}$y calcular (con antelación) las esferas delimitadoras${\displaystyle B(L(S)),B(R(S))}$y${\displaystyle B(L(T)),B(R(T))}$La esperanza aquí es que estas esferas delimitadoras sean mucho más pequeñas que${\displaystyle B(S)}$y${\displaystyle B(T)}$. Y, si, por ejemplo,${\displaystyle B(S)}$y${\displaystyle B(L(T))}$no se intersecan, entonces no tiene sentido comprobar ningún triángulo en${\displaystyle S}$contra cualquier triángulo en${\displaystyle L(T)}$.

Como preprocesamiento , tome cada cuerpo físico (representado por un conjunto de triángulos) y descompóngalo recursivamente en un árbol binario , donde cada nodo${\displaystyle N}$representa un conjunto de triángulos, y sus dos hijos representan${\displaystyle L(N)}$y${\displaystyle R(N)}$En cada nodo del árbol, precalcule la esfera delimitadora.${\displaystyle B(N)}$.

Cuando llega el momento de probar si un par de objetos colisionan, su árbol de esferas delimitadoras puede utilizarse para eliminar muchos pares de triángulos.

Muchas variantes de los algoritmos se obtienen eligiendo algo distinto a una esfera para${\displaystyle B(T)}$Si se eligen cuadros delimitadores alineados con los ejes , se obtienen árboles AABBTrees. Los árboles de cuadros delimitadores orientados se denominan árboles OBBTrees. Algunos árboles son más fáciles de actualizar si el objeto subyacente cambia. Algunos árboles pueden admitir primitivas de orden superior, como splines, en lugar de triángulos simples.

Dado que comprobar si dos objetos se intersecan puede ser una operación relativamente costosa, una forma rápida de evitar potencialmente el cálculo es comprobar si los volúmenes delimitadores que encierran los dos objetos se intersecan. Los volúmenes delimitadores se utilizan normalmente en la etapa inicial (de poda) de la detección de colisiones, de modo que solo los objetos con volúmenes superpuestos necesitan compararse en detalle. ^{[ 9 ]} Si no se superponen, no hay necesidad de comprobar los objetos reales. Calcular la superposición o la colisión entre volúmenes delimitadores implica cálculos adicionales, por lo que para que la prueba del volumen delimitador aporte valor: a) el coste de intersecar el volumen delimitador debe ser bajo y b) el volumen delimitador debe ser lo suficientemente ajustado como para que el número de intersecciones "falsas positivas" sea bajo. Una intersección falsa positiva en este caso significa que los volúmenes delimitadores se intersecan, pero los objetos reales no. Los diferentes tipos de volúmenes delimitadores ofrecen diferentes ventajas y desventajas para estas propiedades.

Las cajas delimitadoras alineadas con los ejes (AABB) y los cuboides son populares debido a su simplicidad y a las rápidas pruebas de intersección. ^{[ 10 ]} Los volúmenes delimitadores, como las cajas delimitadoras orientadas (OBB) , los K-DOP y las envolturas convexas, ofrecen una aproximación más precisa de la forma encerrada a costa de una prueba de intersección más elaborada.

Los objetos para los que los métodos de poda no pudieron descartar la posibilidad de una colisión deben someterse a un cálculo exacto de detección de colisiones.

Cuando la mayoría de los objetos involucrados son fijos, como suele ocurrir en los videojuegos, se pueden utilizar métodos a priori que emplean precomputación para acelerar la ejecución.

En este caso, también es deseable realizar una poda, tanto la poda de n cuerpos como la poda por pares, pero los algoritmos deben tener en cuenta el tiempo y los tipos de movimientos utilizados en el sistema físico subyacente .

En lo que respecta a la detección exacta de colisiones por pares, esta depende en gran medida de la trayectoria, y prácticamente es necesario utilizar un algoritmo numérico de búsqueda de raíces para calcular el instante del impacto.

Como ejemplo, consideremos dos triángulos que se mueven en el tiempo.${\displaystyle {v_{1}(t),v_{2}(t),v_{3}(t)}}$y${\displaystyle {v_{4}(t),v_{5}(t),v_{6}(t)}}$En cualquier momento, se puede comprobar la intersección de los dos triángulos utilizando los veinte planos mencionados anteriormente. Si${\displaystyle P(u,v,w)}$¿El avión está pasando por puntos?${\displaystyle u,v,w}$en${\displaystyle \mathbb {R} ^{3}}$Entonces hay veinte aviones${\displaystyle P(v_{i}(t),v_{j}(t),v_{k}(t))}$para rastrear. Cada plano necesita ser rastreado contra tres vértices, esto da sesenta valores para rastrear. Usando un buscador de raíces en estas sesenta funciones produce los tiempos de colisión exactos para los dos triángulos dados y las dos trayectorias dadas. Si se supone que las trayectorias de los vértices son polinomios lineales en${\displaystyle t}$Entonces, las últimas sesenta funciones son, de hecho, polinomios cúbicos, y en este caso excepcional, es posible determinar el tiempo exacto de colisión utilizando la fórmula para las raíces cúbicas. Algunos analistas numéricos sugieren que usar la fórmula para las raíces cúbicas no es tan numéricamente estable como usar un buscador de raíces para polinomios.

Un objeto de malla triangular se usa comúnmente en el modelado de cuerpos 3D. Normalmente, la función de colisión es una intersección de triángulo a triángulo o una forma delimitadora asociada a la malla. El centroide de un triángulo es la ubicación de su centro de masa, de modo que se equilibraría sobre la punta de un lápiz. La simulación solo necesita agregar la dimensión del centroide a los parámetros físicos. Conociendo los puntos del centroide tanto del objeto como del objetivo, es posible definir el segmento de línea que conecta estos dos puntos.

El vector de posición del centroide de un triángulo es el promedio de los vectores de posición de sus vértices. Por lo tanto, si sus vértices tienen coordenadas cartesianas${\ Displaystyle (x_ {1}, y_ {1}, z_ {1})}$,${\ Displaystyle (x_ {2}, y_ {2}, z_ {2})}$y${\ Displaystyle (x_ {3}, y_ {3}, z_ {3})}$entonces el centroide es${\displaystyle \left({\frac {(x_{1}+x_{2}+x_{3})}{3}},{\frac {(y_{1}+y_{2}+y_{3})}{3}},{\frac {(z_{1}+z_{2}+z_{3})}{3}}\right)}$.

Aquí está la función para calcular la distancia entre segmentos de línea entre dos puntos 3D.${\displaystyle \mathrm {distancia} ={\sqrt {(z_{2}-z_{1})^{2}+(x_{2}-x_{1})^{2}+(y_{2}-y_{1})^{2}}}}$

Aquí, la longitud/distancia del segmento es un criterio de detección ajustable. A medida que los objetos se aproximan, la longitud disminuye hasta el valor umbral. Una esfera triangular se convierte en la prueba geométrica efectiva. Una esfera centrada en el centroide puede dimensionarse para abarcar todos los vértices del triángulo.

Los simuladores físicos difieren en la forma en que reaccionan ante una colisión. Algunos utilizan la suavidad del material para calcular una fuerza, lo que permite resolver la colisión en los siguientes pasos de tiempo como si fuera en la realidad. Esto consume muchos recursos de la CPU para materiales de baja suavidad. Otros simuladores estiman el tiempo de colisión mediante interpolación lineal , revierten la simulación y calculan la colisión mediante los métodos más abstractos de las leyes de conservación .

Algunos métodos iteran la interpolación lineal ( método de Newton ) para calcular el tiempo de colisión con una precisión mucho mayor que el resto de la simulación. La detección de colisiones utiliza la coherencia temporal para permitir pasos de tiempo aún más finos sin aumentar demasiado la demanda de CPU, como en el control del tráfico aéreo .

Tras una colisión inelástica , pueden producirse estados especiales de deslizamiento y reposo. Por ejemplo, el motor Open Dynamics Engine utiliza restricciones para simularlos. Las restricciones evitan la inercia y, por lo tanto, la inestabilidad. La implementación del reposo mediante un grafo de escena evita la deriva.

En otras palabras, los simuladores físicos suelen funcionar de dos maneras: detectando la colisión a posteriori (después de que ocurra) o a priori (antes de que ocurra). Además de la distinción entre a posteriori y a priori , casi todos los algoritmos modernos de detección de colisiones se dividen en una jerarquía de algoritmos. A menudo se utilizan los términos "discreto" y "continuo" en lugar de a posteriori y a priori .

Los videojuegos deben distribuir su limitado tiempo de procesamiento entre varias tareas. A pesar de esta limitación de recursos y del uso de algoritmos de detección de colisiones relativamente primitivos, los programadores han logrado crear sistemas creíbles, aunque inexactos, para su uso en videojuegos.

Durante mucho tiempo, los videojuegos tenían un número muy limitado de objetos que procesar, por lo que comprobar todos los pares no era un problema. En los juegos bidimensionales, en algunos casos, el hardware podía detectar y reportar eficientemente los píxeles superpuestos entre los sprites en la pantalla. ^{[ 13 ]} En otros casos, simplemente dividir la pantalla en mosaicos y vincular cada sprite a los mosaicos con los que se superpone proporciona una poda suficiente, y para las comprobaciones por pares, se utilizan rectángulos o círculos delimitadores llamados hitboxes , que se consideran suficientemente precisos.

Los juegos tridimensionales han utilizado métodos de partición espacial para${\displaystyle n}$-poda corporal, y durante mucho tiempo se utilizó una o varias esferas por objeto 3D real para comprobaciones por pares. Las comprobaciones exactas son muy raras, excepto en juegos que intentan simular la realidad con precisión. Incluso en esos casos, las comprobaciones exactas no se utilizan necesariamente en todos.

Dado que los videojuegos no necesitan imitar la física real, la estabilidad no suele ser un problema. Casi todos los juegos utilizan detección de colisiones a posteriori , y estas se resuelven mediante reglas muy sencillas. Por ejemplo, si un personaje queda incrustado en una pared, simplemente se le puede devolver a su última posición segura. Algunos juegos calculan la distancia máxima que el personaje puede recorrer antes de quedar incrustado en una pared y solo le permiten moverse hasta esa distancia.

En muchos videojuegos, aproximar la posición de los personajes mediante un punto es suficiente para detectar colisiones con el entorno. En este caso, los árboles de partición binaria del espacio proporcionan un algoritmo viable, eficiente y sencillo para comprobar si un punto está integrado en el escenario. Esta estructura de datos también puede utilizarse para gestionar adecuadamente la situación de "posición de reposo" cuando un personaje corre por el suelo. Las colisiones entre personajes y las colisiones con proyectiles y obstáculos se tratan por separado.

Un simulador robusto es aquel que reacciona a cualquier entrada de forma razonable. Por ejemplo, en un videojuego de carreras de coches de alta velocidad , es concebible que los coches avancen una distancia considerable por la pista entre un paso de simulación y el siguiente. Si hay un obstáculo poco profundo en la pista (como un muro de ladrillos), es muy probable que el coche lo salte por completo, lo cual es muy indeseable. En otros casos, la corrección que requieren los algoritmos a posteriori no se implementa correctamente, lo que provoca errores que pueden atrapar a los personajes en las paredes o permitirles atravesarlas y caer en un abismo sin fondo donde puede haber o no un pozo mortal , a veces denominado "infierno negro", "infierno azul" o "infierno verde", según el color predominante. Estas son las características de un sistema de detección de colisiones y simulación física defectuoso. Big Rigs: Over the Road Racing es un ejemplo tristemente célebre de un juego con un sistema de detección de colisiones defectuoso o posiblemente inexistente.

Hitbox

Una hitbox es una forma invisible que se usa comúnmente en videojuegos para la detección de colisiones en tiempo real; es un tipo de caja delimitadora. Suele ser un rectángulo (en juegos 2D) o un cuboide (en 3D) que se adjunta a un punto de un objeto visible (como un modelo o un sprite) y lo sigue. Las formas circulares o esferoidales también son comunes, aunque se las suele llamar "cajas". Es habitual que los objetos animados tengan hitboxes adjuntas a cada parte móvil para garantizar la precisión durante el movimiento. ^{[ 14 ]}

Las cajas de colisión se utilizan para detectar colisiones unidireccionales, como cuando un personaje recibe un puñetazo o un disparo. No son adecuadas para detectar colisiones con retroalimentación (por ejemplo, chocar contra una pared) debido a la dificultad que experimentan tanto los humanos como la IA para gestionar la ubicación cambiante de una caja de colisión; este tipo de colisiones se suelen gestionar con cajas delimitadoras alineadas con los ejes, mucho más sencillas . Los jugadores pueden usar el término "caja de colisión" para referirse a este tipo de interacciones.

Una hitbox es una zona de impacto que se utiliza para detectar las fuentes de daño entrantes. En este contexto, el término hitbox se suele reservar para aquellas que infligen daño. Por ejemplo, un ataque solo puede impactar si la hitbox que rodea el puñetazo del atacante conecta con una de las hitboxes del oponente en su cuerpo, mientras que la colisión de hitboxes opuestas puede resultar en que los jugadores intercambien o cancelen golpes, y las hitboxes opuestas no interactúan entre sí. El término no está estandarizado en la industria; algunos juegos invierten sus definiciones de hitbox y hurtbox , mientras que otros solo usan "hitbox" para ambos lados.