¿La detección de colisión es siempre O (n ^ 2)?

14

¿El motor de física puede disminuir esa complejidad, por ejemplo, al agrupar objetos que están cerca unos de otros y verificar las colisiones dentro de este grupo en lugar de hacerlo contra todos los objetos? (por ejemplo, los objetos lejanos se pueden eliminar de un grupo al observar su velocidad y distancia de otros objetos).

Si no, ¿hace que la colisión sea trivial para las esferas (en 3d) o el disco (en 2d)? ¿Debo hacer un doble bucle o crear una matriz de pares en su lugar?

EDITAR: Para motores de física como bullet y box2d, ¿la detección de colisión sigue siendo O (N ^ 2)?

jokoon
fuente
12
Dos palabras: Particionamiento espacial
MichaelHouse
1
Usted apuesta. Creo que ambos tienen implementaciones de SAP ( Sweep and Prune ) (entre otros) que es un algoritmo O (n log (n)). Busque "Detección de colisión de fase amplia" para obtener más información.
MichaelHouse
2
@ Byte56 Sweep and Prune tiene complejidad O (n log (n)) solo si necesita ordenar cada vez que realiza la prueba. Desea mantener una lista ordenada de objetos y cada vez que agregue uno, simplemente ordénelo en el lugar correcto O (log (n)), por lo tanto obtendrá O (log (n) + n) = O (n). ¡Sin embargo, se vuelve muy complicado cuando los objetos comienzan a moverse!
MartinTeeVarga
1
@ sm4, si los movimientos son limitados, entonces algunas pasadas de clasificación de burbujas pueden encargarse de eso (solo marque los objetos movidos y muévalos hacia adelante o hacia atrás en la matriz hasta que estén ordenados. Solo tenga cuidado con otros objetos en movimiento
monstruo de trinquete

Respuestas:

14

La división espacial es siempre O (N ^ 2) en el peor de los casos y de eso se trata la complejidad en informática.

Sin embargo, existen algoritmos que funcionan en tiempo lineal O (N) . Todos ellos están basados ​​en algún tipo de línea de barrido.

Básicamente, debes tener tus objetos ordenados por una coordenada. Digamos X. Si realiza el ordenamiento cada vez antes de la detección de colisión, la complejidad será O (N * logN). El truco consiste en ordenar solo cuando agrega objetos a la escena y luego cuando algo en la escena cambia. Ordenar después del movimiento no es trivial. Consulte el documento vinculado a continuación para ver un algoritmo que se pone en movimiento y aún funciona en tiempo lineal.

Luego barres de izquierda a derecha. Cada vez que su línea de barrido cruza el comienzo de un objeto, lo coloca dentro de una lista temporal. Cada vez que su línea de barrido sale del objeto, la saca de la lista. Considera las colisiones solo dentro de esta lista temporal.

La ingenua línea de barrido es O (N ^ 2) en el peor de los casos también (usted hace que todos los objetos abarquen todo el mapa de izquierda a derecha), pero puede hacerlo O (N) haciéndolo más inteligente (vea el enlace a continuación). Un algoritmo realmente bueno será bastante complejo.

Este es un diagrama simple de cómo funciona la línea de barrido:

Algoritmo de línea de barrido

La línea barre de izquierda a derecha. Los objetos se ordenan por coordenada X.

  • Caso uno: se verifican los dos primeros objetos. Nada más importa.
  • Caso dos: el primer objeto se verificó y desapareció de la lista. Dos y tres están marcados.
  • Caso tres: incluso si ese objeto choca, no lo verificamos.
  • Caso cuatro: ¡Porque verificamos en este caso!

Algoritmos como este tienen complejidad O (C * N) = O (N).

Fuente: Dos años de cursos de geometría computacional.

En la detección de colisiones, esto generalmente se denomina barrido y poda , pero la familia de algoritmos de la línea de barrido es útil en muchos otros campos.

Más lecturas recomendadas que creo que están fuera del alcance de esta pregunta, pero sin embargo son interesantes: Métodos eficientes de barrido y poda a gran escala con inserción y eliminación de AABB : este documento presenta un algoritmo mejorado de barrido y poda que utiliza cuadros delimitadores alineados con ejes (AABB ) con una ordenación que tiene en cuenta el movimiento. Algorigmo presentado en los trabajos en papel en tiempo lineal.


Ahora tenga en cuenta que este es el mejor algoritmo en teoría . No significa que se use. En la práctica, el algoritmo O (N ^ 2) con división espacial tendrá un mejor rendimiento en cuanto a velocidad en el caso típico (cercano a O (N)) y algunos requisitos adicionales de memoria. Esto se debe a que la constante C en O (C * N) puede ser muy alta. Como generalmente tenemos suficiente memoria y los casos típicos tienen objetos distribuidos uniformemente en el espacio, dicho algoritmo funcionará MEJOR. Pero O (N) es la respuesta a la pregunta original.

MartinTeeVarga
fuente
¿box2d / bullet usa esto?
jokoon
3
"Barrer y podar" es lo que normalmente se llama física. Lo bueno es que puede mantener la clasificación actualizada a medida que avanza la simulación. Además, la línea de barrido en su gráfico está un poco desviada en términos de implementación (aunque es bueno para la teoría): simplemente iteraría sobre el inicio / final de la caja, por lo que solo verificaría las posibles colisiones reales. Visto este método usado para generar árboles de partición espacial más capaces en lugar de usarse directamente también.
Sean Middleditch
3
Como técnicamente en realidad puede haber colisiones por pares O (N ^ 2), no es del todo cierto decir que barrer y podar siempre es O (N). Por el contrario, la complejidad central del algoritmo es O (N + c), donde c es el número de colisiones encontradas por el algoritmo: es sensible a la salida , al igual que muchos algoritmos de casco convexo. (Referencia: en.wikipedia.org/wiki/Output-sensitive_algorithm )
Steven Stadnicki
1
Debe respaldar sus afirmaciones con algunas publicaciones o al menos nombres de algoritmos.
sam hocevar
1
@SamHocevar He agregado un enlace a un algoritmo de barrido y poda realmente avanzado que funciona en tiempo lineal con un desglose detallado de las constantes. El hecho de que los algoritmos se denominen "Barrer y podar" era nuevo para mí, ya que nunca trabajé con él. He usado estos algoritmos en la selección de mapas (que es una especie de colisión de 1 punto con otros objetos), por lo que acabo de aplicar el conocimiento.
MartinTeeVarga
8

No. La detección de colisión no siempre es O (N ^ 2).

Por ejemplo, supongamos que tenemos un espacio de 100x100 con objetos con un tamaño de 10x10. Podríamos dividir este espacio en celdas de 10x10 con una cuadrícula.

Cada objeto puede estar en hasta 4 celdas de la cuadrícula (podría caber en un bloque o estar "entre" celdas). Podríamos mantener una lista de objetos en cada celda.

Solo necesitamos verificar las colisiones en esas celdas. Si hay un número máximo de objetos por celda de cuadrícula (por ejemplo, nunca hay más de 4 objetos en el mismo bloque), la detección de colisión para cada objeto es O (1) y la detección de colisión para todos los objetos es O (N).

Esta no es la única forma de evitar la complejidad O (N ^ 2). Existen otros métodos, más adecuados para otros casos de uso, a menudo utilizando estructuras de datos basadas en árboles.

El algoritmo que describí es un tipo de partición espacial , pero hay otros algoritmos de partición espacial. Consulte Tipos de estructuras de datos de partición espacial para obtener más algoritmos que evitan la complejidad temporal O (N ^ 2).

Tanto Box2D como Bullet admiten mecanismos para reducir el número de pares marcados.

Del manual , sección 4.15:

El procesamiento de colisión en un paso de física se puede dividir en fase estrecha y fase amplia. En la fase estrecha calculamos puntos de contacto entre pares de formas. Imagina que tenemos N formas. Usando la fuerza bruta, necesitaríamos realizar la fase estrecha para N * N / 2 pares.

La clase b2BroadPhase reduce esta carga mediante el uso de un árbol dinámico para la gestión de pares. Esto reduce en gran medida el número de llamadas de fase estrecha.

Normalmente no interactúa directamente con la fase amplia. En cambio, Box2D crea y gestiona una fase amplia internamente. Además, b2BroadPhase está diseñado teniendo en cuenta el bucle de simulación de Box2D, por lo que probablemente no sea adecuado para otros casos de uso.

Del Wiki Bullet :

Existen varios tipos de algoritmos de fase amplia que mejoran el algoritmo ingenuo O (n ^ 2) que solo devuelve la lista completa de pares. Estas fases optimizadas a veces introducen incluso más pares no colisionantes, pero esto se compensa con su tiempo de ejecución generalmente mejorado. Tienen características de rendimiento diferentes y ninguna supera a las demás en todas las situaciones.

Árbol AABB dinámico

Esto es implementado por btDbvtBroadphase en Bullet.

Como su nombre indica, este es un árbol dinámico AABB . Una característica útil de esta broadphase es que la estructura se adapta dinámicamente a las dimensiones del mundo y sus contenidos. Está muy bien optimizado y es una muy buena fase general de uso general. Maneja mundos dinámicos donde muchos objetos están en movimiento, y la adición y eliminación de objetos es más rápida que SAP.

Barrer y podar (SAP)

En Bullet, este es el rango de clases AxisSweep. Esta también es una buena fase general de propósito general, con la limitación de que requiere un tamaño mundial fijo, conocido de antemano. Esta fase ancha tiene el mejor rendimiento para mundos dinámicos típicos, donde la mayoría de los objetos tienen poco o ningún movimiento. Tanto btAxisSweep3 como bt32AxisSweep3 cuantifican los puntos de inicio y finalización para cada eje como enteros en lugar de números de coma flotante, para mejorar el rendimiento.

El siguiente enlace es una introducción general a broadphase y también una descripción del algoritmo Sweep and Prune (aunque lo llama "Ordenar y barrer"):

http://www.ziggyware.com/readarticle.php?article_id=128

Además, eche un vistazo a la página de Wikipedia:

http://en.wikipedia.org/wiki/Sweep_and_prune

luiscubal
fuente
Algunos enlaces a preguntas similares y recursos externos harían de esta una gran respuesta.
MichaelHouse
3
Esto está mal. Aún obtienes O (N ^ 2). Será mucho más rápido, algo así como N ^ 2/100, pero aún así N ^ 2. Como prueba, solo considera que todos los objetos están en una celda.
MartinTeeVarga
44
@ sm4 Este es el peor de los casos O (N ^ 2), que es lo que sucede si todos los objetos están en una celda. Sin embargo, en un motor de física, los objetos generalmente no estarán en una celda. En mi ejemplo, ningún objeto puede compartir la misma celda con más de 3 objetos. Esto sería lo que sucede en un motor de física para objetos "normales" (y por "normal" quiero decir "no solo un sensor").
luiscubal
Creo que su algoritmo requeriría verificar las 8 celdas, no solo las 4 celdas.
jokoon
66
La complejidad de @luiscubal es siempre el "peor de los casos". En teoría, está buscando una complejidad "garantizada". Es lo mismo con quicksort, que es O (N ^ 2) y mergesort, que es O (N * logN). Quicksort funciona mejor en datos reales y tiene un menor requerimiento espacial. Pero mergesort ha garantizado una mejor complejidad. Si necesita probar algo, use mergesort. Si necesita ordenar algo, use quicksort.
MartinTeeVarga
2

O (N ^ 2) se refiere al hecho de que si tiene N objetos, averiguar qué está colisionando con lo que es, en el peor de los casos , los cálculos de colisión de N ^ 2. Digamos que tienes 3 objetos. Para encontrar "quién está golpeando a quién", debe encontrar:

o1 hitting o2?  o1 hitting o3?
o2 hitting o1?  o2 hitting o3?
o3 hitting o1?  o3 hitting o2?

Eso es 6 verificaciones de colisiones, o verificaciones N * (N-1). En el análisis asintótico, expandiríamos el polinomio y lo aproximaríamos como O (N ^ 2). Si tuviera 100 objetos, entonces sería 100 * 99, que es lo suficientemente cercano a 100 * 100.

Entonces, si divide el espacio usando un octree, por ejemplo, se reduce el número promedio de comparaciones entre cuerpos. Si es posible que todos los objetos se junten en un área muy pequeña (por ejemplo, si está haciendo algún tipo de simulación de flujo de partículas, donde las partículas pueden reunirse en la misma área), entonces el O (N ^ 2) aún puede ocurrir en puntos en la simulación (en qué puntos verá desaceleración).

Entonces, todo el punto de O (N ^ 2) se debe a la naturaleza de cada cuerpo que controla a todos los demás cuerpos en la escena. Esa es solo la naturaleza del cálculo. Sin embargo, muchas cosas pueden ayudar a hacer esto más barato. Incluso un gráfico de escena (digamos que la detección entre objetos en la misma habitación solamente) reducirá el número de cálculos de colisión que se realizarán significativamente, pero seguirá siendo O (M ^ 2) (donde M es el número de objetos en la habitación para ser colisión detectada contra). Los volúmenes de delimitación esféricos hacen que la verificación inicial sea muy rápida ( if( distance( myCenter, hisCenter ) > (myRadius+hisRadius) ) then MISS), por lo que incluso si la detección de colisión es O (N ^ 2), es probable que los cálculos de la esfera de delimitación ocurran muy rápido.

bobobobo
fuente
No es necesario tomar como referencia la comprobación de la fuerza bruta: independientemente de los algoritmos inteligentes, N objetos pueden colisionar con todos los demás objetos, lo que genera colisiones de O (N ^ 2) que requieren el procesamiento de O (N ^ 2). Los buenos algoritmos solo pueden mejorar cuando hay menos colisiones.
Lorenzo Gatti