Quadtree para detección de colisiones 2D

Question

Estoy tratando de usar un quadtree para la detección de colisiones 2D, pero estoy un poco perplejo sobre cómo implementarlo. En primer lugar, tendría un quadtree que contiene cuatro subárboles (uno que representa cada cuadrante), así como una colección de objetos que no encajan en un solo subárbol.

Al comprobar un objeto de colisiones en el árbol, me gustaría hacer algo como esto (gracias a QuadTree for 2D collision detection):

1. Compruebe el objeto de colisiones con objetos en el nodo actual.
2. Para cualquier subárbol cuyo espacio se solape con el objeto, recurse.

permite encontrar todos colisiones dentro de un árbol árbol cuádruple:

1. Comprobar cada objeto en el nodo actual uno contra el otro objeto en el nodo actual.
2. Compruebe cada objeto en el nodo actual contra cada subárbol.

para insertar en un árbol de cuatro ramas:

1. Si el objeto encaja en múltiples sub-estructuras, luego añadirlo al nodo actual, y volver.
2. De lo contrario, recurse en el subárbol que lo contenga.

para actualizar un árbol de cuatro ramas:

1. Recurse en cada sub-árbol.
2. Si algún elemento en el nodo actual ya no cabe completamente en el árbol actual, muévalo al padre.
3. Si algún elemento en el nodo actual cabe en un subárbol, insértelo en el subárbol.

¿Esto está bien? ¿Se puede mejorar?

Answer 1

Su estructura quadtree no es óptima. Tiene razón para almacenar 4 subárboles por nodo, pero los objetos reales solo deben almacenarse dentro de las hojas, no en los nodos internos. Por lo tanto, la colección que contiene los objetos reales debe moverse a las hojas.

Vamos a echar un vistazo a la ejecución de las operaciones :

1. insertar un objeto en el árbol cuádruple:
   Comprobar si el objeto se cruza con el nodo actual. Si es así, recurse. Si alcanzó el nivel de la hoja, inserte el objeto en la colección.
2. eliminar un objeto del árbol cuádruple:
   ejecutar los mismos pasos como si insertar el objeto, pero cuando se ha alcanzado el nivel de hoja eliminarlo de la colección.
3. Prueba si un objeto se cruza con cualquier objeto en el interior del árbol cuádruple:
   ejecutar los mismos pasos como si insertar el objeto, pero cuando se ha alcanzado el control del nivel de hoja de colisión con todos los objetos de la colección.
4. Prueba de todas las colisiones entre todos los objetos dentro del quadtree:
   Para cada objeto en el quadtree ejecute la prueba de colisión de un solo objeto.
5. Actualizar el quadtree:
   Borrar todos los objetos del quadtree cuya posición ha sido modificada e insertarlos de nuevo.

Esto tiene varias ventajas:

• Por solamente el almacenamiento de objetos en las hojas es muy fácil de manejar operaciones en el árbol cuádruple (menos casos especiales)
• El árbol cuádruple puede tener hojas con diferente profundidad, lo que le permite adaptar la densidad del quadtree en función de la región espacial que cubre. Esta adaptación puede ocurrir en tiempo de ejecución, manteniendo así la relación objeto/nodo óptima.

Sólo disatvantage:

• Los objetos pueden pertenecer a varias colecciones en el interior del árbol cuádruple. Necesitará una colección lineal adicional fuera del quadtree para enumerar todos los objetos sin duplicados.

Answer 2

No estoy seguro de cómo la CPU efectiva que es todavía, pero parece estar funcionando bien en mi Core Duo en eclipse, aún se ejecuta en más de 2.400 fps lol ..

básicamente, he añadido una lista a objetos colisibles para almacenar referencias a objetos de nodo quadtree con los que he asociado el objeto (mediante la inserción en el árbol cuádruple). También agregué una lista a cada nodo quadtree, que almacena referencias a cualquier objeto considerado dentro de los límites de ese nodo. Entonces cada nodo solo tendrá una ocurrencia de cada objeto. cada nodo también almacena una referencia a su nodo padre, para la navegación a nodos cercanos si quiero verificar cualquiera de ellos después del nodo inicial para una mayor precisión de colisión.

Es muy fácil de conseguir referencias a todos los demás objetos en una celda:

list temp_checklist = object.cells[cell_index].objects 
//('objects' being some sort of array or list of object references as described above) 

esperanza de que ayude a alguien;)

Answer 3

árboles Quad no son siempre la mejor estructura de datos para la detección de colisiones. La parte superior de un quadtree puede ser potencialmente ilimitada (si no se limita la profundidad del árbol) y, en el peor de los casos, no da ninguna velocidad. En su lugar, es posible que desee considerar el uso de una grilla dispersa, que ofrece un mejor rendimiento que un quadtree solo sin la sobrecarga adicional de atravesar varios niveles de árbol.

También hay otros enfoques completamente diferentes que podrían ser incluso mejores.Por ejemplo, usted podría intentar implementar el algoritmo Zomorodian y de Edelsbrunner, como lo hice en el módulo siguiente:

• https://github.com/mikolalysenko/box-intersect

Éstos son también algunos artículos que escribí que tratan estas cuestiones con más detalle:

• http://0fps.net/2015/01/07/collision-detection-part-1/
• http://0fps.net/2015/01/18/collision-detection-part-2/
• http://0fps.net/2015/01/23/collision-detection-part-3-benchmarks/

En particular, si nos fijamos en los puntos de referencia en el apartado anterior se verá que de todas las bibliotecas encuestadas, quadtrees tendían a realizar bastante mal en comparación con otros métodos de detección de colisiones como R-árboles, rejillas o segmento árboles.