La detección de colisiones es el problema computacional de detectar una intersección de dos o más objetos espaciales , comúnmente objetos de gráficos de computadora. Tiene aplicaciones en varios campos de la computación, principalmente en gráficos de computadora , juegos de computadora , simulaciones de computadora , robótica y física computacional . La detección de colisiones es un problema clásico de la geometría computacional . Los algoritmos de detección de colisiones se pueden dividir en que operan sobre objetos espaciales 2D o 3D. [1]
En la simulación física se realizan experimentos como el de jugar al billar . [2] La física del rebote de las bolas de billar se entiende bajo el paraguas del movimiento del cuerpo rígido y las colisiones elásticas . [3] Se daría una descripción inicial de la situación, con una descripción física muy precisa de la mesa de billar y las bolas, así como las posiciones iniciales de todas las bolas. [4] Basándose en una fuerza aplicada a la bola blanca, el programa informático calcularía las trayectorias, el movimiento preciso y los lugares de reposo finales de todas las bolas. Un programa para simular este juego constaría de varias partes, una de las cuales sería responsable de calcular los impactos precisos entre las bolas de billar. Este ejemplo en particular también resulta estar mal condicionado : ya que un pequeño error en cualquier cálculo provocará cambios drásticos en la posición final de las bolas de billar.
Los videojuegos tienen requisitos similares, con algunas diferencias cruciales. Mientras que algunas simulaciones por computadora necesitan simular la física del mundo real con la mayor precisión posible, los juegos de computadora necesitan simular la física del mundo real de una manera aceptable , en tiempo real y de manera robusta. Se permiten concesiones, siempre que la simulación resultante sea satisfactoria para los jugadores.
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, que resolverá la colisión en los siguientes pasos de tiempo como si fuera real. Esto requiere un uso intensivo de la CPU para materiales de baja suavidad. Algunos simuladores estiman el tiempo de colisión mediante interpolación lineal , revierten la simulación y calculan la colisión mediante métodos más abstractos de leyes de conservación .
Algunos 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 precisos sin aumentar mucho la demanda de CPU, como en el control del tráfico aéreo .
Después de una colisión inelástica, pueden producirse estados especiales de deslizamiento y reposo y, 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 gráfico de escenas evita la deriva.
En otras palabras, los simuladores físicos suelen funcionar de una de dos maneras: cuando la colisión se detecta a posteriori (después de que se produce la colisión) o a priori (antes de que se produzca la colisión). Además de la distinción entre a posteriori y a priori , casi todos los algoritmos de detección de colisiones modernos 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 .
En el caso a posteriori , la simulación física avanza un pequeño paso y luego se verifica si hay objetos que se intersecan o se considera que se intersecan visiblemente. En cada paso de la simulación, se crea una lista de todos los cuerpos que se intersecan y se "fijan" las posiciones y trayectorias de estos objetos para tener en cuenta la colisión. Este método se denomina a posteriori porque normalmente no detecta el instante real de la colisión y solo la detecta después de que realmente ha ocurrido.
En los métodos a priori , existe un algoritmo de detección de colisiones que podrá predecir con gran precisión las trayectorias de los cuerpos físicos. Los instantes de colisión se calculan con gran precisión y los cuerpos físicos nunca se interpenetran. Esto se denomina a priori porque el algoritmo de detección de colisiones calcula los instantes de colisión antes de actualizar la configuración de los cuerpos físicos.
Los principales beneficios de los métodos a posteriori son los siguientes. En este caso, el algoritmo de detección de colisiones no necesita conocer la gran cantidad de variables físicas; se le suministra al algoritmo una lista simple de cuerpos físicos y el programa devuelve una lista de cuerpos que se intersecan. El algoritmo de detección de colisiones no necesita comprender la fricción, las colisiones elásticas o, peor aún, las colisiones no elásticas y los cuerpos deformables. Además, los algoritmos a posteriori son, en efecto, una dimensión más simples que los algoritmos a priori . Un algoritmo a priori debe tratar la variable tiempo, que está ausente en el problema a posteriori .
Por otro lado, los algoritmos a posteriori causan problemas en el paso de "corrección", donde es necesario corregir las intersecciones (que no son físicamente correctas). Además, si el paso discreto es demasiado grande, la colisión podría pasar desapercibida, lo que daría como resultado un objeto que atravesara a otro si es lo suficientemente rápido o pequeño.
Los beneficios de los algoritmos a priori son una mayor fidelidad y estabilidad. Es difícil (pero no completamente imposible) separar la simulación física del algoritmo de detección de colisiones. Sin embargo, en todos los casos, salvo en los más simples, el problema de determinar de antemano cuándo chocarán dos cuerpos (dados algunos datos iniciales) no tiene una solución cerrada; normalmente se utiliza un buscador de raíces numéricas .
Algunos objetos están en contacto en reposo , es decir, en colisión, pero no rebotan ni se interpenetran, como un jarrón que reposa sobre una mesa. En todos los casos, el contacto en reposo requiere un tratamiento especial: si dos objetos chocan ( a posteriori ) o se deslizan ( a priori ) y su movimiento relativo está por debajo de un umbral, la fricción se convierte en fricción estática y ambos objetos se disponen en la misma rama del grafo de escena .
Los métodos obvios para detectar colisiones de varios objetos son muy lentos. Por supuesto, comparar cada objeto con todos los demás funcionará, pero es demasiado ineficiente para usarlo cuando el número de objetos es grande. Comparar objetos con geometría compleja entre sí de la manera obvia, comparando cada cara con cada una de las demás caras, es en sí mismo bastante lento. Por lo tanto, se han realizado muchas investigaciones para acelerar el problema.
En muchas aplicaciones, la configuración de los cuerpos físicos de un paso de tiempo al siguiente cambia muy poco. Muchos de los objetos pueden no moverse en absoluto. Los algoritmos se han diseñado de modo que los cálculos realizados en un paso de tiempo anterior se puedan reutilizar en el paso de tiempo actual, lo que da como resultado una finalización más rápida del cálculo.
En el nivel básico de detección de colisiones, el objetivo es encontrar pares de objetos que podrían potencialmente intersecarse. Esos pares requerirán un análisis más profundo. Ming C. Lin, de la Universidad de California, Berkeley [1], desarrolló un algoritmo de alto rendimiento inicial para esto y sugirió usar cuadros delimitadores alineados con los ejes para todos los n cuerpos en la escena.
Cada caja está representada por el producto de tres intervalos (es decir, una caja sería ). Un algoritmo común para la detección de colisiones de cajas delimitadoras es sweep and prune . Observe que dos de estas cajas, y se intersecan si, y solo si , se interseca , se interseca y se interseca . Se supone que, de un paso de tiempo al siguiente, si y se intersecan, entonces es muy probable que en el siguiente paso de tiempo sigan interseccionando. Del mismo modo, si no se intersecaron en el paso de tiempo anterior, entonces es muy probable que sigan sin hacerlo.
Así que reducimos el problema al de rastrear, de cuadro a cuadro, qué intervalos se intersecan. Tenemos tres listas de intervalos (una para cada eje) y todas las listas tienen la misma longitud (ya que cada lista tiene longitud , el número de cuadros delimitadores). En cada lista, se permite que cada intervalo interseque a todos los demás intervalos de la lista. Entonces, para cada lista, tendremos una matriz de ceros y unos: es 1 si los intervalos y se intersecan, y 0 si no se intersecan.
Según nuestra suposición, la matriz asociada a una lista de intervalos permanecerá esencialmente sin cambios de un paso de tiempo al siguiente. Para aprovechar esto, la lista de intervalos se mantiene como una lista de puntos finales etiquetados. Cada elemento de la lista tiene la coordenada de un punto final de un intervalo, así como un entero único que identifica ese intervalo. Luego, ordenamos la lista por coordenadas y actualizamos la matriz a medida que avanzamos. No es tan difícil creer que este algoritmo funcionará relativamente rápido si, de hecho, la configuración de los cuadros delimitadores no cambia significativamente de un paso de tiempo al siguiente.
En el caso de cuerpos deformables, como la simulación de tela, puede que no sea posible utilizar un algoritmo de poda por pares más específico como el que se analiza a continuación, y un algoritmo de poda de n cuerpos es lo mejor que se puede hacer.
Si se puede establecer un límite superior para la velocidad de los cuerpos físicos en una escena, entonces se pueden podar pares de objetos en función de su distancia inicial y el tamaño del paso de tiempo.
Una vez que hemos seleccionado un par de cuerpos físicos para investigar más a fondo, necesitamos comprobar si hay colisiones con más 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. Así que ahora tenemos dos conjuntos de triángulos y (para simplificar, supondremos que cada conjunto tiene la misma cantidad de triángulos).
Lo más obvio es comparar todos los triángulos entre sí para ver si hay colisiones, pero esto implica comparaciones, lo que es muy ineficiente. Si es posible, es conveniente utilizar un algoritmo de poda para reducir la cantidad de pares de triángulos que debemos comprobar.
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 (en nuestro ejemplo, y ) calcularemos una jerarquía de volúmenes delimitadores . Luego, en cada paso de tiempo, cuando necesitemos verificar colisiones entre y , se utilizan los volúmenes delimitadores jerárquicos para reducir la cantidad de pares de triángulos en consideración. Para simplificar, daremos un ejemplo utilizando esferas delimitadoras, aunque se ha observado que las esferas no son deseables en muchos casos. [ cita requerida ]
Si es un conjunto de triángulos, podemos calcular previamente una esfera delimitadora . Hay muchas formas de elegir , solo suponemos que es una esfera que contiene completamente y es lo más pequeña posible.
De antemano, podemos calcular y . Claramente, si estas dos esferas no se intersecan (y eso es muy fácil de comprobar), entonces tampoco lo hacen y . Sin embargo, esto no es mucho mejor que un algoritmo de poda de n cuerpos.
Si es un conjunto de triángulos, entonces podemos dividirlo en dos mitades y . Podemos hacer esto con y , y podemos calcular (con anticipación) las esferas delimitadoras y . La esperanza aquí es que estas esferas delimitadoras sean mucho más pequeñas que y . Y, si, por ejemplo, y no se intersecan, entonces no tiene sentido comparar cualquier triángulo en con cualquier triángulo en .
Como cálculo previo , podemos tomar cada cuerpo físico (representado por un conjunto de triángulos) y descomponerlo recursivamente en un árbol binario , donde cada nodo representa un conjunto de triángulos y sus dos hijos representan y . En cada nodo del árbol, podemos calcular previamente la esfera delimitadora .
Cuando llega el momento de probar un par de objetos para detectar colisiones, su árbol de esfera delimitante se puede utilizar para eliminar muchos pares de triángulos.
Muchas variantes de los algoritmos se obtienen eligiendo algo distinto a una esfera para . Si se eligen cuadros delimitadores alineados con el eje , se obtienen árboles AABBTrees. Los árboles de cuadros delimitadores orientados se denominan árboles OBBTrees. Algunos árboles son más fáciles de actualizar si cambia el objeto subyacente. Algunos árboles pueden acomodar primitivas de orden superior, como splines, en lugar de triángulos simples.
Una vez que terminamos de podar, nos quedamos con una serie de pares candidatos para verificar la detección de colisiones exacta.
Una observación básica es que para dos objetos convexos cualesquiera que estén disjuntos, se puede encontrar un plano en el espacio de modo que un objeto se encuentre completamente en un lado de ese plano y el otro objeto se encuentre en el lado opuesto de ese plano. Esto permite el desarrollo de algoritmos de detección de colisiones muy rápidos para objetos convexos.
Los primeros trabajos en esta área implicaban métodos de " planos de separación ". Dos triángulos chocan esencialmente solo cuando no pueden separarse por un plano que pase por tres vértices. Es decir, si los triángulos son y donde cada uno es un vector en , entonces podemos tomar tres vértices, , encontrar un plano que pase por los tres vértices y verificar si este es un plano de separación. Si alguno de esos planos es un plano de separación, entonces se considera que los triángulos están disjuntos. Por otro lado, si ninguno de estos planos es un plano de separación, entonces se considera que los triángulos se intersecan. Hay veinte planos de ese tipo.
Si los triángulos son coplanares, esta prueba no es del todo satisfactoria. Se pueden añadir algunos planos adicionales, por ejemplo, planos que sean normales a las aristas del triángulo, para solucionar el problema por completo. En otros casos, los objetos que se encuentran en una cara plana deben necesariamente encontrarse también en un ángulo en otro lugar, por lo que la detección de colisiones general podrá encontrar la colisión.
Desde entonces se han desarrollado mejores métodos. Hay algoritmos muy rápidos disponibles para encontrar los puntos más cercanos en la superficie de dos objetos poliédricos convexos. El trabajo inicial de Ming C. Lin [5] utilizó una variación del algoritmo símplex de programación lineal . El algoritmo de distancia Gilbert-Johnson-Keerthi ha reemplazado ese enfoque. Estos algoritmos se acercan al tiempo constante cuando se aplican repetidamente a pares de objetos estacionarios o de movimiento lento, cuando se utilizan con puntos de inicio de la comprobación de colisión anterior.
El resultado final de todo este trabajo algorítmico es que la detección de colisiones se puede realizar de manera eficiente para miles de objetos en movimiento en tiempo real en computadoras personales y consolas de juegos típicas.
Cuando la mayoría de los objetos involucrados son fijos, como es típico en los videojuegos, se pueden utilizar métodos a priori que utilizan precomputación para acelerar la ejecución.
La poda también es deseable aquí, 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, esto depende en gran medida de la trayectoria y casi es necesario utilizar un algoritmo numérico de búsqueda de raíces para calcular el instante del impacto.
Como ejemplo, considere dos triángulos que se mueven en el tiempo y . En cualquier punto del tiempo, los dos triángulos pueden ser verificados para la intersección usando los veinte planos mencionados anteriormente. Sin embargo, podemos hacerlo mejor, ya que estos veinte planos pueden ser rastreados en el tiempo. Si es el plano que pasa por los puntos en entonces hay veinte planos para rastrear. Cada plano necesita ser rastreado contra tres vértices, esto da sesenta valores para rastrear. El uso de 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. Notamos aquí que si se supone que las trayectorias de los vértices son polinomios lineales en entonces las sesenta funciones finales son de hecho polinomios cúbicos, y en este caso excepcional, es posible localizar el tiempo de colisión exacto usando la fórmula para las raíces del cúbico. Algunos analistas numéricos sugieren que usar la fórmula para las raíces del cúbico no es tan numéricamente estable como usar un buscador de raíces para polinomios. [ cita requerida ]
Los algoritmos alternativos se agrupan bajo el paraguas de la partición espacial , que incluye octrees , partición binaria del espacio (o árboles BSP) y otros enfoques similares. Si uno divide el espacio en una serie de celdas simples, y si se puede demostrar que dos objetos no están en la misma celda, entonces no es necesario verificar su intersección. Dado que los árboles BSP se pueden calcular previamente, ese enfoque es muy adecuado para manejar paredes y obstáculos fijos en juegos. Estos algoritmos son generalmente más antiguos que los algoritmos descritos anteriormente.
Para acelerar el cálculo de detección de colisiones, se pueden utilizar volúmenes delimitadores . Un volumen delimitador es una forma que encierra el objeto de interés, pero es más sencillo calcular las colisiones.
Los cuadros delimitadores alineados con el eje (AABB) y los cuboides son populares debido a su simplicidad. [6] A un cuadro delimitador en un videojuego a veces se lo llama Hitbox. Otros volúmenes delimitadores que se usan comúnmente para la detección de colisiones incluyen la envoltura convexa y los cuadros delimitadores orientados (OBB) .
Los volúmenes delimitadores se utilizan normalmente en la etapa temprana (poda) de detección de colisiones, de modo que solo los objetos con volúmenes delimitadores superpuestos necesitan compararse en detalle. [7] Calcular la colisión o superposición entre volúmenes delimitadores implica cálculos adicionales, por lo tanto, para que sea beneficioso necesitamos que el volumen delimitador sea relativamente ajustado y que la sobrecarga computacional debida a las colisiones sea baja.
Cuando el espacio de los objetos para los que estamos calculando la colisión es complejo, un único volumen delimitador puede no proporcionar una aproximación lo suficientemente ajustada como para reducir considerablemente la cantidad de detecciones de colisión exactas que tenemos que realizar. En tales casos, se puede utilizar la Jerarquía de Volumen Delimitador (BVH). Una BVH es una estructura de árbol sobre un conjunto de volúmenes delimitadores. BVH se puede utilizar con objetos deformables, como tela o cuerpos blandos, pero la jerarquía de volumen se debe ajustar a medida que la forma se deforma. Para los objetos deformables, debemos preocuparnos por las autocolisiones o autointersecciones. BVH también se puede utilizar para ese fin. La colisión entre dos objetos se calcula calculando la intersección entre los volúmenes delimitadores de la raíz del árbol, ya que hay colisiones en las que nos sumergimos en los subárboles que se intersecan. Las colisiones exactas entre los objetos reales, o sus partes (a menudo triángulos de una malla de triángulos ), solo deben calcularse entre las hojas que se intersecan [8] . El mismo enfoque funciona para las colisiones por pares y las autocolisiones.
Un objeto de malla de triángulos se utiliza comúnmente en el modelado de cuerpos en 3D. Normalmente, la función de colisión es una intersección de triángulo a triángulo o una forma delimitadora asociada con la malla. Un centroide de triángulo es una ubicación del centro de masa tal que se equilibraría sobre la punta de un lápiz. La simulación solo necesita agregar una dimensión de centroide a los parámetros físicos. Dados los puntos de centroide tanto en el objeto como en el 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 , entonces el centroide es .
Aquí está la función para la distancia de un segmento de línea entre dos puntos 3D.
Aquí, la longitud/distancia del segmento es un criterio de "acierto" ajustable. A medida que los objetos se acercan, la longitud disminuye hasta el valor umbral. Una esfera triangular se convierte en la prueba de geometría efectiva. Una esfera centrada en el centroide puede dimensionarse para abarcar todos los vértices del triángulo.
Los videojuegos tienen que dividir su muy limitado tiempo de computación 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 podido crear sistemas creíbles, aunque inexactos, para su uso en juegos. [ cita requerida ]
Durante mucho tiempo, los videojuegos tenían un número muy limitado de objetos a tratar, por lo que comprobar todos los pares no era un problema. En los juegos bidimensionales, en algunos casos, el hardware pudo detectar y reportar eficientemente píxeles superpuestos entre sprites en la pantalla. [9] En otros casos, simplemente agrupar la pantalla y unir cada sprite en los mosaicos que superpone proporciona una poda suficiente, y para las comprobaciones por pares, se utilizan rectángulos o círculos delimitadores llamados hitboxes y se consideran suficientemente precisos.
Los juegos tridimensionales han utilizado métodos de partición espacial para la poda de cuerpos y durante mucho tiempo han utilizado una o varias esferas por objeto 3D real para las comprobaciones por pares. Las comprobaciones exactas son muy poco frecuentes, excepto en los juegos que intentan simular la realidad de forma precisa. Incluso en ese caso, las comprobaciones exactas no se utilizan necesariamente en todos los casos.
Como los juegos no necesitan imitar la física real, la estabilidad no es un problema tan grande. Casi todos los juegos utilizan la detección de colisiones a posteriori, y las colisiones suelen resolverse mediante reglas muy simples. Por ejemplo, si un personaje se incrusta en una pared, es posible que simplemente se lo mueva de regreso a su última ubicación conocida. Algunos juegos calcularán la distancia que puede moverse el personaje antes de incrustarse en una pared y solo le permitirán moverse esa distancia.
En muchos casos de videojuegos, aproximar los personajes mediante un punto es suficiente para detectar colisiones con el entorno. En este caso, los árboles binarios de partición del espacio proporcionan un algoritmo viable, eficiente y simple para verificar si un punto está incrustado en el escenario o no. Esta estructura de datos también se puede utilizar para gestionar con elegancia 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 peligros se tratan por separado.
Un simulador robusto es aquel que reaccionará a cualquier entrada de una manera razonable. Por ejemplo, si imaginamos un videojuego de carreras de autos de alta velocidad , de un paso de simulación al siguiente, es concebible que los autos avancen una distancia sustancial a lo largo de la pista de carreras. Si hay un obstáculo poco profundo en la pista (como una pared de ladrillos), no es del todo improbable que el auto lo salte por completo, y esto es muy indeseable. En otros casos, la "corrección" que requieren los algoritmos a posteriori no se implementa correctamente, lo que da como resultado errores que pueden atrapar a los personajes en las paredes o permitirles pasar a través de ellas y caer en un vacío infinito donde puede haber o no un pozo sin fondo mortal , a veces denominado "infierno negro", "infierno azul" o "infierno verde", según el color predominante. Estos son los sellos distintivos de un sistema de detección de colisiones y simulación física fallidos. Big Rigs: Over the Road Racing es un ejemplo infame de un juego con un sistema de detección de colisiones defectuoso o posiblemente inexistente.
Un hitbox es una forma invisible que se usa comúnmente en los videojuegos para la detección de colisiones en tiempo real; es un tipo de cuadro delimitador. Suele ser un rectángulo (en juegos 2D) o un cuboide (en 3D) que se une 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 todavía se las suele llamar "cajas". Es común que los objetos animados tengan hitboxes unidos a cada parte móvil para garantizar la precisión durante el movimiento. [10] [ ¿ Fuente poco fiable? ]
Los hitboxes se utilizan para detectar colisiones "unidireccionales", como cuando un personaje recibe un puñetazo o una bala. No son adecuados 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 las ubicaciones cambiantes de un hitbox; este tipo de colisiones se suelen gestionar con cuadros delimitadores alineados con ejes mucho más simples . Los jugadores pueden utilizar el término "hitbox" para referirse a este tipo de interacciones de todos modos.
Un hurtbox es un hitbox que se utiliza para detectar fuentes de daño entrantes. En este contexto, el término hitbox se reserva normalmente para aquellos que infligen daño. Por ejemplo, un ataque solo puede acertar si el hitbox que rodea el puñetazo de un atacante conecta con uno de los hurtboxes del oponente en su cuerpo, mientras que la colisión de los hitboxes opuestos puede provocar que los jugadores intercambien o cancelen golpes, y los hurtboxes opuestos no interactúan entre sí. El término no está estandarizado en toda la industria; algunos juegos invierten sus definiciones de hitbox y hurtbox , mientras que otros solo usan "hitbox" para ambos lados.
Además, puede utilizar el hardware del sistema para detectar colisiones entre objetos y hacer que su programa reaccione ante dichas colisiones.
![{\displaystyle I_{1}\times I_{2}\times I_{3}=[a_{1},b_{1}]\times [a_{2},b_{2}]\times [a_{3},b_{3}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/450c59ef778cb75d1ea83e0aed119f8d988cab8c)
