Mejor algoritmo para detección de colisiones eficiente entre objetos

Question

Estoy confundido. Bueno, no confundido, tanto como no querer hacer 6 programas de prueba para ver qué algoritmo es el mejor. Así que pensé en pedirle a mis amigos expertos aquí en SO que me dieran el beneficio de su experiencia.

El escenario es una escena en 3D con un área potencialmente bastante grande en comparación con los tamaños de los objetos que contiene. Hay potencialmente miles de objetos en la escena. Los objetos varían en tamaño desde décimas de una unidad hasta alrededor de 10 unidades, pero no más grandes (o más pequeñas). Los objetos tienden a estar agrupados, pero esos clústeres pueden aparecer potencialmente en cualquier parte de la escena. Todos los objetos son dinámicos y móviles. Los clústeres tienden a moverse juntos, pero cuando lo hacen, sus velocidades pueden no ser las mismas todo el tiempo. También hay geometría estática a considerar. Aunque hay un gran número de objetos dinámicos, también hay algunos objetos estáticos en la escena (los objetos estáticos tienden a ser uno o dos órdenes de magnitud más grandes que los objetos dinámicos).

Ahora, lo que quiero es una estructura de datos espaciales para realizar eficientemente detección de colisión para todos los elementos en la escena. Sería fantástico si el algoritmo también admitiera la consulta de visibilidad para la canalización de renderizado. En aras de la simplicidad, suponga que la detección de colisión aquí es de fase amplia (es decir, que todos los objetos dinámicos son simplemente esferas perfectas).

Por lo tanto, en mi investigación que puedo utilizar uno de:

(1) octárbol (2) Loose octárbol (3) lineal octárbol (+ suelto) (4) KD árbol (5) BSP Árbol (6) Hashing

Hasta ahora (6) es el único que he probado. En realidad es totalmente excelente en términos de velocidad (8192 elementos de colisión registrados en menos de 1 ms en mi sistema) si los objetos en la escena están en promedio distribuidos de manera uniforme. No es un algoritmo tan bueno si todos los objetos se combinan en un área más pequeña, lo que supongo que es posible.

¿Alguien tiene alguna idea de cuál usar, o cualquier truco que pueda emplear para acelerar? Estoy pensando que pase lo que pase, puedo usar un árbol BSP separado para la geometría estática. Supongo que las "esferas" dinámicas son las que más me preocupan aquí. Nota: no CUDA, esto es solo CPU: p.

Gracias

EDIT: Ok, gracias a Floris, he encontrado más información acerca de la AABB árboles. Hay una vieja discusión sobre GameDev aquí: http://www.gamedev.net/topic/308665-aabb-tree---wheres-the-poly-o_o/. Parece un buen compromiso.

Final EDIT: Decidió no reinventar la rueda. Es posible que la biblioteca de física de bala haga todo esto por mí (tiene un árbol AABB, probablemente también muy bien optimizado).

Answer 1

Gran pregunta.

Es, básicamente, tiene un complejo equilibrio entre:

1. velocidad de una fase de detección de colisiones completa
2. sobrecarga de la actualización/mantenimiento de la estructura de datos como objetos se mueven alrededor

La mala La noticia es que no hay una respuesta "perfecta" debido a esto: dependerá genuinamente de muchos factores diferentes, únicos en su situación. Los BSP, por ejemplo, son increíblemente rápidos para 1. cuando están precalculados con mucha geometría planar estática, lo que explica por qué eran tan frecuentes en los primeros juegos de FPS.

Mi suposición personal es que un árbol flojo AABB (caja de delimitación alineada del eje) con un número razonable de objetos (5-10?) En cada caja de límite de nivel inferior probablemente funcione mejor en su caso. Razones:

• Tiene un espacio bastante grande/escaso con grupos de objetos. Los árboles AABB tienden a ser buenos para esto, ya que puedes cortar muchos niveles que de otra manera necesitarías.
• Estás asumiendo esferas perfectas. Las pruebas de colisión esfera a esfera son muy baratas, por lo que puede permitirse realizar entre 10 y 45 pruebas por cada nodo de nivel inferior. Básicamente N^2 está bien para valores pequeños de N :-)
• La alineación de ejes hace que la actualización del árbol sea mucho más simple y las pruebas de intersección sean mucho más baratas que la mayoría de las alternativas. Dado que está asumiendo objetos más o menos esféricos, no creo que gane mucho de cuadros orientados (que solo le dan una ventaja si tiene muchas formas largas/delgadas en ángulos divertidos).
• Al permitir que los cuadros delimitadores sean sueltos y contengan una cantidad razonable de objetos, se reduce la posibilidad de que el movimiento de cualquier objeto individual lo saque de los límites de AABB. A menos que esto suceda, no necesita actualizar el árbol. Esto te ahorrará mucho tiempo de actualización de árboles. Cuando ocurra, extienda el límite con un poco de margen para que no tenga que volver a extender inmediatamente el siguiente cuadro. ¡Recuerde que la mayoría del movimiento tiende a continuar en la misma dirección durante unos pocos cuadros!

Disculpe la respuesta un tanto floja, pero espero que esto le brinde algunas ideas útiles/cosas que considerar.

Answer 2

Muchos motores de física usan un AABBTree (Árbol de caja delimitadora alineado con el eje), que subdivide un objeto en piezas cada vez más pequeñas. Puede obtener una detección de colisión muy buena utilizando este algoritmo. Este árbol se parece un poco a un octárbol.

Un OOBBTree (Caja de referencia orientada) sería su mejor parte contraria.