¿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)?
Respuestas:
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:
La línea barre de izquierda a derecha. Los objetos se ordenan por coordenada X.
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.
fuente
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:
Del Wiki Bullet :
fuente
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:
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.fuente