data structures - Estructuras de datos espaciales para mover objetos?

data-structures geometry (5)

Bounding Spheres probablemente te ayudaría 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 cuadrada 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ás, por supuesto, rastrear el CENTRO de tu 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 2x el radio de objeto más grande en su matriz de objetos maestra (si eso es factible, una pregunta de escala de esfera que limita el objeto vs. cantidad de objetos obviamente aparece).

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

Por supuesto, entonces tienes que hacer una detección de colisión real entre tus objetos no esféricos, y eso puede ser no trivial, pero has reducido el número de comparaciones potenciales de manera muy dramática en ese punto.

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 haya espacio en este tipo de algoritmo para el uso de árboles en la determinación de regiones dinámicas para igualar el tamaño 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.

Me preguntaba cuál es la mejor estructura de datos para manejar 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 árboles R se utilizan 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.

Yo aprecio toda la ayuda.

Un método interesante para realizar la detección de colisiones 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 debes usar con la estructura de octree:

1) El área de delimitación que ocupa un nodo debe ser el doble de grande que lo sería para un octree normal (donde el octree divide el 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, puedes cambiarlo para usar una estructura de octree dispersa, solo guardando 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 quizás quieras 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 adecuados para su uso con AABB.

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

(Ha pasado un tiempo desde que hice este tipo de codificación de desarrollo de juegos espaciales).

barrer y podar fase amplia + fase estrecha de gjk

RDC puede ser útil, especialmente si sus objetos son escasos (no muchas intersecciones).

Puede dividir la escena en un octárbol y utilizar coherencia de escena. 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, lo difícil es que cuando su objeto esté cerca del borde de su partición, debería asegurarse de actualizar en qué nodo se encuentra el objeto.
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.
Simplifique siempre la forma que esté probando con algo parecido a un cuadro delimitador alineado por el eje. Una prueba de colisión inicial
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.
Hay muchas otras optimizaciones dependiendo de la forma del objeto. Los círculos o cuadrados o formas más complejas tienen optimizaciones específicas que puedes hacer mientras te mueves.
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.
Sé de más, pero no puedo pensar en nada fuera de mi cabeza. No he hecho esto por un tiempo.

Ahora, por supuesto, esto depende de cómo esté haciendo 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 mediante la extrusión de la forma y la determinación de los puntos de colisión inicial? 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.