La detección de colisiones es el problema computacional de detectar una intersección de dos o más objetos espaciales , comúnmente objetos gráficos por computadora. Tiene aplicaciones en diversos campos de la informática, principalmente en gráficos por computadora , juegos de computadora , simulaciones por 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 objetos espaciales 2D o 3D. [1]
En la simulación física se llevan a cabo experimentos como jugar al billar . La física del rebote de las bolas de billar se comprende bien, bajo el paraguas del movimiento de cuerpos rígidos y las colisiones elásticas . 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 posiciones iniciales de todas las bolas. Dada una fuerza aplicada a la bola blanca (probablemente resultante de que un jugador golpee la bola con su taco), queremos calcular las trayectorias, el movimiento preciso y los eventuales lugares de descanso de todas las bolas con un programa de computadora . Un programa para simular este juego constaría de varias partes, una de las cuales se encargaría de calcular los impactos precisos entre las bolas de billar. Este ejemplo concreto también resulta estar mal condicionado : 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. Si bien algunas simulaciones por computadora deben simular la física del mundo real con la mayor precisión posible, los juegos de computadora deben simular la física del mundo real de una manera aceptable , en tiempo real y de manera sólida. Se permiten compromisos, siempre y cuando la simulación resultante sea satisfactoria para los jugadores.
Los simuladores físicos se diferencian en la forma en que reaccionan ante una colisión. Algunos usan la suavidad del material para calcular una fuerza, que resolverá la colisión en los siguientes pasos de tiempo como es en la realidad. Esto consume mucha 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 coherencia temporal para permitir intervalos de tiempo aún más precisos sin aumentar mucho la demanda de CPU, como en el control de tráfico aéreo .
Después de una colisión inelástica, pueden ocurrir estados especiales de deslizamiento y reposo y, por ejemplo, Open Dynamics Engine utiliza restricciones para simularlos. Las restricciones evitan la inercia y, por tanto, la inestabilidad. La implementación del descanso mediante un gráfico de escena evita la deriva.
En otras palabras, los simuladores físicos suelen funcionar de dos maneras: donde la colisión se detecta a posteriori (después de que ocurra la colisión) o a priori (antes de que ocurra la colisión). Además de la distinción 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 .
En el caso a posteriori , la simulación física avanza un pequeño paso y luego se verifica para ver si algún objeto se cruza o se considera visiblemente que se cruza. En cada paso de la simulación, se crea una lista de todos los cuerpos que se cruzan y las posiciones y trayectorias de estos objetos se "fijan" para tener en cuenta la colisión. Este método se denomina a posteriori porque normalmente omite el instante real de la colisión y sólo detecta la colisión 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 mucha 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 llama 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 tener en cuenta la gran cantidad de variables físicas; Se alimenta al algoritmo una lista simple de cuerpos físicos y el programa devuelve una lista de cuerpos que se cruzan. 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, de hecho, una dimensión más simples que los algoritmos a priori . Un algoritmo a priori debe abordar la variable tiempo, que está ausente en el problema a posteriori .
Por otro lado, los algoritmos a posteriori causan problemas en el paso de "reparació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 que un objeto atraviese 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 del todo imposible) separar la simulación física del algoritmo de detección de colisiones. Sin embargo, en todos los casos, excepto en los más simples, el problema de determinar de antemano cuándo colisionarán dos cuerpos (dados algunos datos iniciales) no tiene una solución de forma cerrada; generalmente se trata de un buscador numérico de raíces .
Algunos objetos están en contacto de reposo , es decir, en colisión, pero sin rebotar ni interpenetrar, como por ejemplo un jarrón apoyado 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 y ambos objetos se organizan en la misma rama del gráfico de escena .
Los enfoques obvios para la detección de colisiones de múltiples 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 la otra, es en sí mismo bastante lento. Por lo tanto, se han realizado considerables investigaciones para acelerar el problema. [2]
En muchas aplicaciones, la configuración de los cuerpos físicos de un paso de tiempo al siguiente cambia muy poco. Es posible que muchos de los objetos no se muevan en absoluto. Los algoritmos se han diseñado para que los cálculos realizados en un paso de tiempo anterior puedan reutilizarse en el paso de tiempo actual, lo que resulta en una finalización más rápida del cálculo.
En el nivel aproximado de detección de colisiones, el objetivo es encontrar pares de objetos que potencialmente podrían cruzarse. Esos pares requerirán un análisis más detallado. Ming C. Lin, de la Universidad de California, Berkeley [1], desarrolló uno de los primeros algoritmos de alto rendimiento para esto , y sugirió utilizar cuadros delimitadores alineados con ejes para los n cuerpos de la escena.
Cada cuadro está representado por el producto de tres intervalos (es decir, un cuadro sería ). Un algoritmo común para la detección de colisiones de cuadros delimitadores es barrer y podar . Observe que dos de esos cuadros, y se cruzan si, y solo si , se cruzan , se cruzan y se cruzan . Se supone que, de un paso de tiempo al siguiente, si y se cruzan, entonces es muy probable que en el siguiente paso de tiempo todavía se crucen. Del mismo modo, si no se cruzaron en el paso de tiempo anterior, es muy probable que sigan sin hacerlo.
Así que reducimos el problema al de rastrear, de fotograma a fotograma, qué intervalos se cruzan. 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, cada intervalo puede cruzar todos los demás intervalos de la lista. Entonces, para cada lista, tendremos una matriz de ceros y unos: es 1 si los intervalos se cruzan y 0 si no se cruzan.
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 en realidad 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 número 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 se analiza a continuación, y lo mejor que se puede hacer es un algoritmo de poda de n cuerpos.
Si se puede colocar un límite superior a 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 hayamos seleccionado un par de cuerpos físicos para una mayor investigación, debemos comprobar más cuidadosamente si hay colisiones. 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. Ahora tenemos dos conjuntos de triángulos y (para simplificar, supondremos que cada conjunto tiene el mismo número de triángulos).
Lo obvio es comparar todos los triángulos con todos los triángulos en busca de colisiones, pero esto implica comparaciones, lo cual es muy ineficiente. Si es posible, es deseable utilizar un algoritmo de poda para reducir el número de pares de triángulos que debemos verificar.
La familia de algoritmos más utilizada se conoce como 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 necesitamos verificar si hay colisiones entre y , los volúmenes delimitadores jerárquicos se utilizan para reducir el número de pares de triángulos bajo consideración. Para simplificar, daremos un ejemplo utilizando esferas delimitadoras, aunque se ha observado que las esferas no son deseables en muchos casos. [ cita necesaria ]
Si es un conjunto de triángulos, podemos precalcular una esfera delimitadora . Hay muchas formas de elegir , sólo asumimos que es una esfera que contiene completamente y que sea lo más pequeña posible.
De antemano, podemos calcular y . Claramente, si estas dos esferas no se cruzan (y eso es muy fácil de probar), 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 (de antemano) 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 cruzan, entonces no tiene sentido comparar ningún triángulo con ningún 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 precalcular la esfera delimitadora .
Cuando llega el momento de probar la colisión de un par de objetos, su árbol de esferas delimitadoras se puede utilizar para eliminar muchos pares de triángulos.
Muchas variantes de los algoritmos se obtienen eligiendo algo distinto de una esfera . Si uno elige cuadros delimitadores alineados con ejes , obtiene AABBTrees. Los árboles de caja delimitadora orientados se denominan OBBTrees. Algunos árboles son más fáciles de actualizar si el objeto subyacente cambia. Algunos árboles pueden acomodar primitivas de orden superior, como splines, en lugar de simples triángulos.
Una vez que terminamos de podar, nos quedan varios pares candidatos para verificar la detección exacta de colisiones.
Una observación básica es que para dos objetos convexos cualesquiera que sean 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 implicaron métodos de " plano de separación ". Dos triángulos colisionan esencialmente sólo cuando no pueden estar separados 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 es un plano de separación. Si alguno de esos planos es un plano de separación, entonces los triángulos se consideran disjuntos. Por otro lado, si ninguno de estos planos son planos de separación, entonces se considera que los triángulos se cruzan. Hay veinte aviones de este tipo.
Si los triángulos son coplanares, esta prueba no es del todo exitosa. Se pueden agregar algunos planos adicionales, por ejemplo, planos que sean normales a los bordes de los triángulos, para solucionar el problema por completo. En otros casos, los objetos que se encuentran en una cara plana necesariamente también deben encontrarse en un ángulo en otro lugar, por lo que la detección general de colisiones podrá encontrar la colisión.
Desde entonces se han desarrollado mejores métodos. Se encuentran disponibles algoritmos muy rápidos para encontrar los puntos más cercanos en la superficie de dos objetos poliédricos convexos. Los primeros trabajos de Ming C. Lin [3] utilizaron una variación del algoritmo simplex de la 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 usan con puntos de partida de la verificació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 implicados son fijos, como es típico en los videojuegos, se pueden utilizar métodos a priori que utilizan el cálculo previo 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.
Cuando se trata de la detección exacta de colisiones por pares, esto depende en gran medida de la trayectoria, y casi hay que 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 momento, se puede comprobar la intersección de los dos triángulos utilizando los veinte planos mencionados anteriormente. Sin embargo, podemos hacerlo mejor, ya que todos estos veinte aviones pueden ser rastreados en el tiempo. Si el avión pasa por puntos, entonces hay veinte aviones 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. Observamos aquí que si se supone que las trayectorias de los vértices son polinomios lineales, entonces las sesenta funciones finales son en realidad polinomios cúbicos y, en este caso excepcional, es posible localizar el tiempo exacto de colisión utilizando la fórmula para las raíces de el cúbico. 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. [ cita necesaria ]
Los algoritmos alternativos se agrupan bajo el paraguas de partición espacial , que incluye octrees , partición de espacio binario (o árboles BSP) y otros enfoques similares. Si se divide el espacio en varias 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 los juegos. Estos algoritmos son generalmente más antiguos que los algoritmos descritos anteriormente.
Los cuadros delimitadores (o volúmenes delimitadores ) suelen ser un rectángulo 2D o un cuboide 3D , pero son posibles otras formas. Un cuadro delimitador en un videojuego a veces se denomina Hitbox. Se han probado el diamante delimitador, el paralelogramo delimitador mínimo, el casco convexo, el círculo delimitador o la bola delimitadora y la elipse delimitadora, pero los cuadros delimitadores siguen siendo los más populares debido a su simplicidad. [4] Los cuadros delimitadores se utilizan normalmente en la etapa inicial (poda) de la detección de colisiones, de modo que solo es necesario comparar en detalle los objetos con cuadros delimitadores superpuestos.
Un objeto de malla triangular se usa comúnmente en el modelado corporal 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 triangular es una ubicación del centro de masa tal que se equilibraría sobre la punta de un lápiz. La simulación sólo necesita agregar una dimensión centroide a los parámetros físicos. Dados los puntos centroides 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. Entonces, si sus vértices tienen coordenadas cartesianas , entonces el centroide es .
Aquí está la función para una distancia de segmento de línea entre dos puntos 3D.
Aquí, la longitud/distancia del segmento es un tamaño de segmento de 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. Se puede dimensionar una esfera centrada en el centroide 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 este límite 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 usar en juegos. [ cita necesaria ]
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 juegos bidimensionales, en algunos casos, el hardware pudo detectar e informar de manera eficiente píxeles superpuestos entre sprites en la pantalla. [5] En otros casos, simplemente colocar la pantalla en mosaico y vincular cada objeto en los mosaicos que se superpone proporciona suficiente poda, y para 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 corporal y durante mucho tiempo utilizaron una o varias esferas por objeto 3D real para comprobaciones por pares. Las comprobaciones exactas son muy raras, excepto en juegos que intentan simular fielmente la realidad. Aun así, no en todos los casos se utilizan necesariamente controles exactos.
Como los juegos no necesitan imitar la física real, la estabilidad no es un gran problema. 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 queda incrustado en una pared, es posible que simplemente lo devuelvan a su última ubicación buena conocida. Algunos juegos calcularán la distancia que el personaje puede moverse antes de incrustarse en una pared y solo le permitirán moverse hasta esa distancia.
En muchos casos de videojuegos, aproximar los personajes en un punto es suficiente para detectar colisiones con el entorno. En este caso, los árboles de partición del espacio binario proporcionan un algoritmo viable, eficiente y sencillo para comprobar si un punto está incrustado en el paisaje o no. Esta estructura de datos también se puede utilizar para manejar con elegancia la situación de "posición de descanso" 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 forma 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 automóvil lo salte por completo, y esto es muy indeseable. En otros casos, la "reparación" que requieren los algoritmos a posteriori no se implementa correctamente, lo que resulta en errores que pueden atrapar a los personajes en las paredes o permitirles atravesarlas y caer en un vacío sin fin donde puede haber o no un fondo mortal. pozo , a veces denominado "infierno negro", "infierno azul" o "infierno verde", según el color predominante. Estas son las características de un sistema de simulación física y detección de colisiones fallido. Big Rigs: Over the Road Racing es un ejemplo infame de un juego con un sistema de detección de colisiones defectuoso o posiblemente faltante.
Un hitbox es una forma invisible comúnmente utilizada en videojuegos para la detección de colisiones en tiempo real; es un tipo de cuadro delimitador. A menudo es un rectángulo (en juegos 2D) o un cuboide (en 3D) que está unido y sigue un punto en un objeto visible (como un modelo o un objeto). Las formas circulares o esferoidales también son comunes, aunque todavía se las llama más a menudo "cajas". Es común que los objetos animados tengan hitboxes adjuntos a cada parte móvil para garantizar la precisión durante el movimiento. [6] [ ¿ fuente poco confiable? ]
Los hitboxes se utilizan para detectar colisiones "unidireccionales", como un personaje golpeado por un puñetazo o una bala. No son adecuados para la detección de 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 siempre cambiantes de un hitbox; Este tipo de colisiones generalmente se manejan con cuadros delimitadores alineados con ejes mucho más simples . Los jugadores pueden usar el término "hitbox" para referirse a este tipo de interacciones independientemente.
Hurtbox es un término relacionado que se utiliza para diferenciar "objeto que causa daño" de "objeto que recibe daño" . Por ejemplo, un ataque solo puede aterrizar si el hitbox alrededor del golpe de un atacante se conecta con uno de los hurtboxes del oponente en su cuerpo, mientras que los hitboxes opuestos chocan pueden resultar en 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 sólo usan "hitbox" para ambos lados.
![{\displaystyle I_ {1} \ veces I_ {2} \ veces I_ {3} = [a_ {1},b_ {1}] \ veces [a_ {2},b_ {2}] \ veces [a_ {3} }, b_ {3}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/450c59ef778cb75d1ea83e0aed119f8d988cab8c)
{{cite book}}: CS1 maint: multiple names: authors list (link) CS1 maint: numeric names: authors list (link)Además, puede utilizar el hardware del sistema para detectar colisiones entre objetos y hacer que su programa reaccione ante dichas colisiones.