Detección de colisiones: Comprensión de las intersecciones visuales en visión por computadora

Por Fouad Sabry

Qué es la detección de colisiones

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.

Cómo se beneficiará

(I) Información y validaciones sobre lo siguiente temas:

Capítulo 1: Detección de colisiones

Capítulo 2: Trazado de rayos (gráficos)

Capítulo 3: Partición del espacio binario

Capítulo 4: Centroide

Capítulo 5: Ramificación y límite

Capítulo 6: Punto de fuga

Capítulo 7: Quadtree

Capítulo 8: Delimitación volumen

Capítulo 9: Detección de ciclos

Capítulo 10: Disposición de líneas

(II) Respondiendo a las principales preguntas del público sobre detección de colisiones.

(III) Ejemplos del mundo real para el uso de la detección de colisiones en muchos campos.

Para quién es este libro

Profesionales, estudiantes de pregrado y posgrado , entusiastas, aficionados y aquellos que quieran ir más allá del conocimiento o la información básica para cualquier tipo de detección de colisiones.

 

 

• Idioma: Español
• Editorial: Mil Millones De Conocimientos [Spanish]
• Fecha de lanzamiento: 4 may 2024

Vista previa del libro

Capítulo 1: Detección de colisiones

El desafío informático de detectar la intersección de dos o más objetos se conoce como detección de colisiones. La detección de colisiones es un problema clásico en geometría computacional y tiene aplicaciones en una variedad de dominios informáticos, sobre todo gráficos por computadora, juegos de computadora, simulaciones por computadora, robótica y física computacional. Las técnicas de detección de colisiones 2D y 3D se pueden distinguir por sus respectivas dimensiones de objeto.

La simulación física implica la realización de pruebas como jugar al billar. Bajo el paraguas del movimiento del cuerpo rígido y las colisiones elásticas, la mecánica de las bolas de billar que rebotan se entiende bien. Una primera descripción de la circunstancia incluiría una descripción física detallada de la mesa de billar y las bolas, así como las ubicaciones iniciales de cada bola. Dada la fuerza impartida a la bola blanca (a menudo la consecuencia de que un jugador golpee la bola con su taco), deseamos utilizar un programa de computadora para determinar las trayectorias, el movimiento preciso y las posiciones de descanso final de todas las bolas. Una simulación de este juego requeriría múltiples módulos, uno de los cuales se encargaría de calcular las colisiones exactas entre las bolas de billar. Una pequeña inexactitud en cualquier cálculo dará lugar a cambios drásticos en la posición final de las bolas de billar, como se demuestra en este ejemplo.

Los criterios para los videojuegos son comparables, con cambios significativos. La simulación por ordenador debe imitar la física del mundo real con la mayor precisión posible, mientras que los juegos de ordenador deben simular la física del mundo real de una manera aceptable, en tiempo real y con suficiente resistencia. Siempre que la simulación resultante sea satisfactoria para los jugadores del juego, se permiten compromisos.

Los diferentes simuladores físicos responden de manera diferente a las colisiones. Algunos usan la suavidad del material para calcular una fuerza que resolverá la colisión en pasos de tiempo posteriores, como lo haría en la realidad. Debido a la dureza de algunos materiales, esto requiere una gran potencia de procesamiento. Algunos simuladores estiman el tiempo de colisión utilizando interpolación lineal, revierten la simulación y luego calculan la colisión utilizando enfoques más abstractos basados en principios de conservación.

Algunos iteran la interpolación lineal (enfoque de Newton) para calcular el tiempo de colisión con una precisión significativamente mayor que el resto de la simulación. Utilizando la coherencia temporal, la detección de colisiones permite pasos de tiempo cada vez más precisos sin aumentar significativamente la demanda de CPU, como en el control del tráfico aéreo.

Pueden producirse estados especiales de deslizamiento y reposo después de una colisión inelástica, y Open Dynamics Engine emplea restricciones para modelarlos. Las restricciones evitan la inercia y, en consecuencia, la inestabilidad. La implementación del descanso a través de un gráfico de escena evita la deriva.

En otras palabras, los simuladores físicos suelen detectar colisiones a posteriori (después de que ocurra la colisión) o a priori (antes de que ocurra la colisión) (antes de que ocurra la colisión). Además de la distinción entre a posteriori y a priori, prácticamente todos los algoritmos recientes de detección de colisiones están organizados jerárquicamente. Normalmente, se utilizan discreto y continuo en lugar de a posteriori y a priori.

En el caso a posteriori, la simulación física avanza un poco, y luego se determina si algún objeto se superpone o no o se considera visiblemente que se cruza. En cada paso de la simulación, las posiciones y trayectorias de todos los cuerpos que se cruzan se fijan para tener en cuenta la colisión. Este método se conoce como a posteriori, ya que generalmente pierde el momento exacto del impacto y solo lo detecta después del hecho.

En los enfoques a priori, existe un algoritmo de detección de colisiones que puede predecir las trayectorias de los cuerpos físicos con gran precisión. Los instantes de colisión se calculan con precisión, y los cuerpos físicos nunca chocan realmente. Esto se denomina a priori porque el método de detección de colisiones calcula los instantes de colisión antes de actualizar la configuración de los cuerpos físicos.

Las principales ventajas de los enfoques a posteriori son las siguientes. Se proporciona una lista simple de cuerpos físicos al algoritmo, y el programa produce una lista de cuerpos que se intersecan. La técnica de detección de colisiones no requiere conocimientos de fricción, colisiones elásticas o inelásticas, ni cuerpos deformables. Además, los algoritmos a posteriori son una dimensión más simples que sus homólogos a priori. La variable tiempo se omite en el problema a posteriori, lo que requiere un algoritmo a priori.

Por otro lado, los algoritmos a posteriori presentan problemas durante el paso de arreglo, donde se deben reparar las intersecciones físicamente incorrectas. Además, si el paso discreto es demasiado grande, es posible que no se reconozca la colisión, lo que provocará que un objeto atraviese otro si es lo suficientemente rápido o pequeño.

Las ventajas de los algoritmos a priori son la precisión y la consistencia mejoradas. Separar la simulación física del método de detección de colisiones es difícil (aunque no imposible). Sin embargo, en todas las circunstancias, excepto en las más simples, el problema de predecir cuándo colisionarían dos cuerpos (dados los datos iniciales) no tiene una solución de forma cerrada: normalmente se requiere un buscador de raíces numéricas.

Por ejemplo, un jarrón que descansa sobre una mesa está en contacto de reposo o colisión, pero no salta ni se interpenetra. El contacto en reposo siempre exige un tratamiento específico: si dos elementos chocan (a posteriori) o se deslizan (a priori) y su velocidad relativa es inferior a un umbral, la fricción se convierte en fricción y ambos objetos se colocan en la misma rama del gráfico de la escena.

Los métodos convencionales para detectar colisiones entre varios objetos son extremadamente lentos. Obviamente, comparar cada objeto con cualquier otro objeto funcionará, pero es un desperdicio cuando el número de objetos es significativo. La comprobación de objetos de geometría compleja entre sí de la manera convencional, comparando cada cara con todas las demás, es un proceso que requiere mucho tiempo. Por lo tanto, se han realizado estudios sustanciales para acelerar la solución del problema.

En muchas aplicaciones, la configuración de los cuerpos físicos varía poco de un paso de tiempo a otro. Muchos de los objetos pueden estar inmóviles. Los algoritmos se han creado de tal manera que los cálculos realizados en un período de tiempo anterior se pueden utilizar en el período de tiempo actual, lo que resulta en un cálculo más rápido.

En el nivel general de detección de colisiones, el objetivo es identificar pares de objetos que podrían colisionar. Estas parejas requerirán una investigación adicional. Usando cuadros delimitadores alineados con los ejes para todos los n cuerpos de la imagen, Ming C. Lin de la Universidad de California, Berkeley [1] creó un método temprano con alto rendimiento para este propósito.

Cada caja se denota por el producto de tres intervalos (es decir, 1, 2 y 3), una caja sería

I_{1}\times I_{2}\times I_{3}=[a_{1},b_{1}]\times [a_{2},b_{2}]\times [a_{3},b_{3}]

).

Barrido y poda es una técnica típica para la detección de colisiones de cuadros delimitadores.

Observe que hay dos cajas de este tipo, I_{1}\times I_{2}\times I_{3} e J_{1}\times J_{2}\times J_{3} interseque si, así como si, I_{1} se cruza J_{1} , I_{2} se interseca J_{2} e I_{3} interseca J_3 .

Se anticipa que, de un paso de tiempo al siguiente, si I_{k} y J_{k} se cruzan, entonces es muy probable que continúen superponiéndose en el paso de tiempo siguiente.

Del mismo modo, si no se cruzaron durante el paso de tiempo anterior, entonces no lo harán ahora, entonces es probable que continúen sin hacerlo.

Por lo tanto, simplificamos el problema a uno de seguimiento, de imagen a imagen, qué intervalos de intersección existen.

Tenemos tres listas de intervalos (una para cada eje) y todas las listas tienen la misma longitud (ya que cada lista tiene longitud n , la cantidad de cuadros de límite. En cada lista, cada intervalo puede intersecarse con todos los demás intervalos de la lista.

Por lo tanto, para cada lista, tendremos una n\times n matriz M=(m_{{ij}}) de ceros y unos: m_{ij} es 1 si los intervalos i y j se intersecan, 0 si las dos líneas no se cruzan.

En nuestra estimación, la matriz M asociada a una lista de intervalos permanecerá esencialmente sin cambios de un paso de tiempo al siguiente.

Para utilizar esto, en realidad, la lista de intervalos se mantiene como una lista de puntos de conexión etiquetados.

Cada elemento de la lista contiene las coordenadas del punto final de un intervalo, además de un entero distinto que identifica ese intervalo.

A continuación, la lista se ordena por coordenadas, y se actualiza la matriz M a medida que avanzamos.

Si la configuración de los cuadros delimitadores no cambia mucho de un paso de tiempo al siguiente, no es difícil pensar que este método se ejecutará con bastante rapidez.

En el caso de cuerpos deformables, como la simulación de telas, puede no ser práctico emplear una estrategia de poda por pares más especializada como se describe a continuación; Un enfoque de poda de n cuerpos es lo