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

Question

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

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 den el beneficio de su experiencia.

El escenario es una escena 3d con un área potencialmente bastante grande en comparación con los tamaños de los objetos en su interior. Hay 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ños). Los objetos tienden a agruparse, pero esos grupos pueden aparecer en cualquier lugar de la escena. Todos los objetos son dinámicos y en movimiento. Los cúmulos 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 el dinámico objeto).

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 genial si el algoritmo también soportara la consulta de visibilidad también, para la canalización de renderizado. En aras de la simplicidad, supongamos que la detección de colisiones aquí es de fase amplia (es decir, todos los objetos dinámicos son simplemente esferas perfectas).

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

(1) Octree (2) Octree flojo (3) Octree linear (+flojo) (4) KD Arbol (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 uniformemente. No es un algoritmo tan bueno si todos los objetos se juntan en un área más pequeña, lo que supongo que es posible.

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

Gracias

EDIT: Ok, gracias a Floris, he encontrado 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: Decidimos no reinventar la rueda. Es es posible que la biblioteca de física bullet haga todo esto por mí (tiene AABB tree en ella, probablemente muy bien optimizado también).

36

collision-detection dynamic structure

Author: Robinson, 2011-08-18

Source

2 answers

Muchos motores de física utilizan un AABBTree (Axis aligned Bounding Box Tree), que subdivide un objeto en piezas cada vez más pequeñas. Puede obtener una muy buena detección de colisiones usando este algo. Este árbol se parece un poco a un Octree.

Un OOBBTree (Caja Delimitadora orientada) sería la mejor parte del contador.

5

Author: Floris,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2011-08-18 14:04:22

score 14 · Accepted Answer

Gran pregunta.

Básicamente tienes una compleja compensación entre:

Velocidad de una fase completa de detección de colisiones
Sobrecarga 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 - realmente dependerá de muchos factores diferentes únicos a su situación. Por ejemplo, los BSP son increíblemente rápidos para 1. cuando están pre-calculados con una gran cantidad de planos estáticos geometría, lo que explica por qué eran tan frecuentes en los primeros juegos FPS.

Mi conjetura personal es que un árbol AABB (Caja Delimitadora Alineada con Eje) suelto con un número razonable de objetos (5-10?) en cada cuadro delimitador de nivel inferior probablemente funcionará mejor en su caso. Razones:

Tienes 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.
Usted está asumiendo esferas perfectas. Las pruebas de colisión esfera a esfera son muy baratas, por lo que puede permitirse fácilmente hacer 10-45 pruebas para 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 mucho más baratas que la mayoría de las alternativas. Dado que estás asumiendo objetos más o menos esféricos, no creo que ganarías mucho con las cajas delimitadoras orientadas (que solo te dan una ventaja si tienes muchas formas largas / delgadas en ángulos divertidos).
Al permitir que las cajas delimitadoras estén sueltas y contengan un número razonable de objetos, reduce la posibilidad de que el movimiento de cualquier objeto individual lo lleve fuera de los límites de AABB. A menos que esto suceda, no es necesario actualizar el árbol. Esto le ahorrará mucho tiempo de actualización del árbol. Cuando suceda, extienda el límite con un poco de margen para que no tenga que volver a extender de inmediato el siguiente fotograma: recuerde que la mayoría del movimiento tiende a continuar en el ¡la misma dirección para unos pocos fotogramas!

Lo siento por la respuesta ligeramente lanudo pero espero que esto le da algunas ideas útiles / cosas a considerar!