dynamic - El mejor algoritmo para la detección eficiente de colisiones entre objetos

structure collision-detection

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 en su interior. 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 de manera eficiente la detección de colisiones para todos los elementos de 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 esferas perfectas).

Entonces, en mi investigación puedo usar uno de:

(1) Octree (2) Octree suelto (3) Octree lineal (+ suelto) (4) Árbol KD (5) Árbol BSP (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 las cosas? 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

EDITAR: Ok, gracias a Floris, encontré más información sobre AABB Trees. 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.

Edición final: 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

Básicamente tiene una compleja compensación entre:

1. Velocidad de una fase completa de detección de colisión
2. Gastos generales de actualización / mantenimiento de la estructura de datos a medida que los objetos se mueven

La mala noticia es que no hay una respuesta "perfecta" debido a esto; dependerá genuinamente de muchos factores diferentes únicos a 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 (Axis Bounding Bounding Box) con un número razonable de objetos (5-10?) En cada cuadro de límite de nivel inferior probablemente funcione mejor en su caso. Razones:

• Usted tiene un espacio bastante grande / disperso 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 del eje hace que la actualización del árbol sea mucho más simple y las pruebas de intersección sean mucho más económicas 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!

Perdón por la respuesta ligeramente floja, pero espero que esto te brinde algunas ideas / cosas útiles para 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 Límite Orientada) sería su mejor contraparte.