¿Estructuras de datos espaciales para mover objetos?

Question

Me preguntaba ¿cuál es la mejor estructura de datos para tratar con muchos objetos en movimiento (esferas, triángulos, cajas, puntos, etc.)? Intento responder dos preguntas, Vecino más cercano y Detección de colisión.

Me doy cuenta de que tradicionalmente, las estructuras de datos como R se usan para las consultas de vecinos más cercanos y Oct/Kd/BSP se usan para problemas de detección de colisiones con objetos estáticos o con muy pocos objetos en movimiento.

Solo espero que haya algo más que sea mejor.

Agradezco toda la ayuda.

Answer 1

Bounding Spheres probablemente lo ayude con muchos objetos en movimiento; calcula el radio al cuadrado del objeto y lo rastrea desde su centro. Si la distancia cuadrada entre los centros de dos objetos es menor que la suma de los radios cuadrados de los dos objetos, entonces tiene una colisión potencial. Todo hecho con distancias cuadradas; sin raíces cuadradas

Puede ordenar los vecinos más cercanos por la distancia mínima al cuadrado entre sus objetos. La detección de colisiones puede ser compleja, por supuesto, y con objetos de forma no esférica, Bounding Spheres no necesariamente obtendrá información de colisión, pero puede podar bastante el árbol de objetos que necesita para la colisión.

Necesitará, por supuesto, rastrear el CENTRO de su objeto; e idealmente, le gustaría que cada objeto sea rígido, para evitar tener que recalcular los tamaños de las esferas delimitadoras (aunque el recálculo no es particularmente difícil, particularmente si utiliza un árbol de objetos rígidos cada uno con su propia esfera delimitadora para los objetos que no son rígidos, pero se complican).

Básicamente, para responder a su pregunta sobre estructuras de datos, puede mantener todos sus objetos en una matriz maestra; Tendría un conjunto de matrices de "región" que consisten en referencias a los objetos en la matriz maestra en la que puede clasificar los objetos rápidamente en función de sus coordenadas cartesianas; las matrices de "región" deben tener una superposición definida de al menos 2 veces el radio de objeto más grande en su matriz de objetos maestra (si es factible, aparece una pregunta de escala de esfera que limita el número de objetos)

Una vez tienes eso, puedes hacer una prueba de colisión rápida comparando las distancias de todos los objetos dentro de una región entre sí, de nuevo, aquí es donde la definición de la región se vuelve importante, porque estás haciendo un intercambio significativo de número de regiones para numerar Sin embargo, es un poco más simple simplemente porque sus comparaciones de distancia se reducen a simples restas (y operaciones abs(), por supuesto).

Por supuesto, entonces usted tiene que hacer la detección de colisión real entre su no esférica objetos, y que pueden ser no t rivial, pero ha reducido el número de posibles comparaciones de manera muy dramática en ese momento.

Básicamente, es un sistema de dos niveles; la primera es la matriz de región, mediante la cual haces un tipo aproximado en tu escena. En segundo lugar, tiene su comparación de distancia intra-región; en donde vas a hacer tu detección de colisión básica y marcar colisión en los objetos que han colisionado.

Probablemente hay espacio en este tipo de algoritmo para el uso de árboles en la determinación de regiones dinámicas para igualar los tamaños de su región para asegurar que el tamaño de su región no crezca demasiado rápido en regiones "atestadas"; ese tipo de cosas, sin embargo, no es trivial, porque con objetos de diferentes tamaños, su tipo de densidad se vuelve ... complejo, por decir lo menos.

Answer 2

Un método interesante para hacer la detección de colisión es utilizar cajas delimitadoras alineadas axialmente (AABB) organizadas dentro de una estructura especial de octárboles. La ayuda de AABB se debe a que hacen los cálculos de colisiones gruesas muy rápido porque solo necesita realizar hasta 6 comparaciones.

Hay un par de trucos que puedes usar con la estructura de octárbol:

1) El área de delimitación, que un nodo ocupa debe ser dos veces tan grande como lo sería para un octree normal (donde las particiones octárbol la espacio sin superposición). Como cada nodo debe superponer la mitad del área de sus nodos adyacentes. Como la AABB puede pertenecer a un solo nodo, este tamaño y superposición adicionales le permite permanecer en el nodo durante un período de tiempo más largo.

2) También en cada nodo, y probablemente en cada nivel de la jerarquía, mantiene enlaces a los vecinos del nodo. Esto implicará una gran cantidad de código adicional, pero le permitirá mover elementos entre los nodos cerca de la hora O (1) en lugar de O (2logn).

Si el octárbol está ocupando demasiada memoria, podría cambiarlo para usar una estructura de octree dispersa, solo manteniendo el árbol para las partes del mundo del juego que en realidad contenían entidades. Sin embargo, esto significaría que tendrías que realizar más cálculos para cada cuadro cuando las entidades se muevan por el mundo.

Algunas otras ideas que puede querer probar en lugar de un octree es usar un árbol kd (creo que ese es el nombre correcto), o usar AABB para construir la estructura de abajo hacia arriba.

Los árboles KD (de memoria) dividen el espacio utilizando planos alineados axialmente, por lo que son aptos para su uso con AABB.

La otra idea es en lugar de forzar la generación de octree de arriba hacia abajo (comenzando con una caja que rodea el mundo entero), la construye desde las entidades base y construye AABB más grandes que crecen hasta que la más grande abarca todo mundo. Aunque no estoy seguro de cómo funcionaría con muchas entidades de movimiento rápido.

(Ha pasado un tiempo desde que he hecho este tipo de codificación espacial de desarrollo del juego.)

Answer 3

1. que puede particionar la escena en un octree y utilizar escena coherencia. El objeto en movimiento que está probando va a estar en un nodo específico del árbol para una cantidad específica de cuadros dependiendo de su velocidad. Esto significa que puede suponer que estará en el nodo y, por lo tanto, cortar rápidamente una gran cantidad de objetos que no están en el nodo. Por supuesto, el truco es cuando su objeto está cerca del borde de su partición, debería asegurarse de actualizar en qué nodo está el objeto.

2. Un objeto en movimiento tiene una dirección y una velocidad. Puede dividir fácilmente la escena en dos secciones utilizando una división perpendicular de la dirección de movimiento de los objetos. Cualquier objeto en el lado equivocado de esta división no necesita ser verificado. Por supuesto, compensa la velocidad del otro objeto. Entonces, si el otro objeto es razonablemente lento, puede cortarlo fácilmente de las comprobaciones adicionales.

3. Simplifique siempre cualquier forma que esté probando con algo parecido a un cuadro delimitador alineado por el eje. Una prueba de colisión inicial

4. Puede tomar la distancia entre su objeto y otro objeto en movimiento más las velocidades. Si el otro objeto en movimiento se mueve en la misma dirección general a una velocidad más rápida, puede eliminarlo de su cheque.

5. Existen muchas otras optimizaciones según la forma del objeto. Los círculos o cuadrados o formas más complejas tienen optimizaciones específicas que puedes hacer mientras te mueves.

6. Suponiendo que algunos objetos se detienen o pueden detenerse, puede hacer un seguimiento de los objetos que se detienen. estos objetos pueden ser tratados como objetos estáticos y, por lo tanto, los controles son más rápidos y puede aplicarles todas las técnicas de optimización estáticas.

7. Sé de más, pero no puedo pensar en ninguna de la parte superior de la cabeza. No he hecho esto por un tiempo.

Ahora, por supuesto, esto depende de cómo se realiza la detección de colisión. ¿Estás actualizando incrementalmente la posición del objeto en función de la velocidad y la comprobación como si fuera estático? ¿O está compensando la velocidad al extruir la forma y calcular los puntos de colisión iniciales? El primero necesita un pequeño paso para el objeto en movimiento rápido. Este último es más complicado y costoso, pero da mejores resultados. Además, si va a tener objetos giratorios, las cosas se vuelven un poco más complicadas.

Answer 4

barrido y podar fase amplio + gjk fase estrecho

Answer 5

RDC pueden ser de utilidad, especialmente si los objetos son escasos (no muchas intersecciones).