Pequeñas colisiones de objetos de alta velocidad: evitar la tunelización

14

EDITAR / ACTUALIZAR: Mi pregunta más importante en este momento es si la ecuación "t = ..." del paso 3 es una buena idea o hay una mejor manera de hacerlo. La mayoría de los otros problemas se han abordado parcial o totalmente, pero ningún comentario o respuesta realmente ha tocado este tema. De nuevo, probablemente se requiere una solución analítica, las velocidades y distancias son demasiado grandes y los objetos son demasiado pequeños, para cualquier solución iterativa / recursiva (algunos se sugieren a continuación en los comentarios) en los que puedo pensar (aunque si hay una solución iterativa / recursiva especial que manejará bien este tipo de situaciones, entonces definitivamente estoy abierto a ella). ¡Muchas gracias por su ayuda hasta ahora, todos ustedes son increíbles y realmente aprecio sus pensamientos y ayuda!

Estoy tratando de detectar colisiones entre objetos pequeños de alta velocidad. Esta es una situación en la que los túneles pueden ocurrir muy fácilmente, incluso a velocidades relativamente bajas.

La proyección de rayos no funcionará, ya que esto detecta una colisión entre dos objetos de alta velocidad, no entre un objeto y una pared estacionaria. (¿A menos que esté malinterpretando la proyección de rayos?) El rendimiento es MUCHO una consideración; si es posible, quiero evitar un gran impacto en el rendimiento. Ya tengo un quadtree funcional y muy efectivo ( http://en.wikipedia.org/wiki/Quadtree ) implementado, por lo que lo modificaré y usaré como se describe a continuación.

Editar: reducir el intervalo de tiempo no funcionará. Las velocidades son demasiado altas para esta solución, lo que significa que los resultados de rendimiento serían demasiado grandes, mientras que aún se pierde la gran mayoría de las colisiones de túneles . (Por ejemplo, podría tener un objeto con un tamaño de aproximadamente 1 unidad yendo a una velocidad medida en millones de unidades por intervalo de tiempo ...)

SOLUCIÓN PROPUESTA:

Paso 1:

Cree un cuadro alrededor del movimiento de cada objeto, luego alimente esos cuadros al quadtree para generar una lista inicial de posibles colisiones. Vea la siguiente imagen (esta imagen muestra un objeto circular que se mueve de una posición a otra, y el movimiento que genera un rectángulo, que se alimentará al quadtree):Rectángulo generado por movimiento

Paso 2: (¿podría saltear este paso?)

Revise la lista de posibles colisiones generadas por el quadtree. Vea si los rectángulos se cruzan en cada posible colisión. Si es así, continúe con el paso 3.

EDITAR: A continuación, Sean Middleditch sugirió usar volúmenes barridos / la intersección de las cápsulas (si los objetos son círculos). Eso deja tres opciones: 1) omitir el paso 2 por completo. 2) Haz el paso 2 a mi manera. 3) Hazlo a la manera de Sean. El camino de Sean será más costoso desde el punto de vista computacional que mi idea de caja, sin embargo, eliminará más falsos positivos que el mío, evitando que lleguen al paso final.

¿Alguien puede hablar por experiencia de cuál de estas 3 opciones es la mejor? (Tengo la intención de utilizar este motor de física para algunas cosas diferentes, por lo que estoy buscando la solución "generalmente mejor" que funcione más rápido en la más amplia variedad de situaciones, no solo un caso de prueba específico en el que pueda medir fácilmente qué solución es el más rápido)

Paso 3:

Use la ecuación t = a continuación, si el discriminante (es decir, la parte debajo de la raíz cuadrada) es negativo o 0, sin colisión, si es positivo, use el valor t como el momento de la colisión (después de lo cual es fácil ajustar las posiciones en consecuencia. ..si ambos objetos continúan existiendo después de la colisión). Ecuación:

t = (-1/2 sqrt ((2 a w-2 a x + 2 b y-2 b z-2 c w + 2 c x-2 d y + 2 dz) ^ 2-4 (w ^ 2- 2 w x + x ^ 2 + y ^ 2-2 y z + z ^ 2) (a ^ 2-2 a c + b ^ 2-2 b d + c ^ 2 + d ^ 2-r ^ 2-2 r ss ^ 2)) - a w + a xb y + b z + c wc x + d yd z) / (w ^ 2-2 w x + x ^ 2 + y ^ 2-2 y z + z ^ 2 ) .

Donde (1 y 2 se usan para denotar los objetos 1 y 2):

t es un valor de tiempo negativo entre 0 y -1, donde 0 es el cuadro actual y -1 es el cuadro anterior;

a = x posición 1;

b = y posición 1;

c = x posición 2;

d = y posición 2;

w = x velocidad 1;

x = x velocidad 2;

y = y velocidad 1;

z = y velocidad 2;

r = radio 1;

s = radio 2;

Derivación: (^ 2 significa al cuadrado)

Tome ecuaciones paramétricas (por ejemplo, newxpos1 = a + t w) para los movimientos de los objetos y conéctelos a la fórmula de distancia (cuadrando ambos lados): fórmula de distancia al cuadrado = (a + t w - (c + t x)) ^ 2 + (b + t y - (d + t * z)) ^ 2. Recuerde, t va a ser negativo. Para encontrar el tiempo de colisión de dos objetos circulares, establecemos el lado izquierdo igual a (r + s) ^ 2. Resolviendo t usando la ecuación cuadrática (y una gran cantidad de álgebra muy tediosa), obtenemos la ecuación "t = ..." anterior.

Mis preguntas:

1) ¿Es esta una buena manera de hacerlo? ¿Funcionará en absoluto? ¿Me voy a encontrar con algún problema imprevisto? (Sé que tendré problemas cuando choquen más de 2 objetos a la vez, pero no me importa, ya que el único caso al que realmente me opongo es cuando tienen velocidades relativas bajas (si las velocidades relativas son altas entonces la solución "tonta" que proporciona el algoritmo será "suficientemente buena", y será imposible que un humano vea el error), y si más de 2 chocan con bajas velocidades relativas en el mismo intervalo de tiempo, la mayoría de las soluciones estar lo suficientemente cerca de todos modos, ya que no planeo tener un montón de colisiones inelásticas)

2) ¿Mi rendimiento sufrirá mucho? No creo que lo haga, pero si lo hace, ¿hay una mejor manera de hacerlo?

3) ¿Debo omitir el paso 2 e ir directamente del paso 1 al 3? Obviamente, el paso 2 no es vital, pero podría ayudar al rendimiento (O podría costar más tiempo de CPU de lo que ahorra).

Todos los demás comentarios, sugerencias o críticas son bienvenidos. ¡Gracias por tu ayuda!

MindSeeker
fuente
1
Christer Ericson tiene alguna información sobre la esfera barrida / prueba de esfera en su libro naranja. Hay bastantes maneras de resolver el problema, pero imagino que lo más conveniente es reducir a la mitad el intervalo. Es bueno tratar de obtener estas cosas por su cuenta, pero realmente debería ir a ver el libro naranja y comparar para obtener una rutina de detección realmente buena y aprender más.
RandyGaul
Parece que ya tienes un plan ... pruébalo y ve cómo funciona.
Trevor Powell
Creo que la forma "habitual" es tener un pequeño intervalo máximo en su tiempo delta. Entonces, si tiene un lapso de 1000 ms, simplemente simule 10x 100ms (o 100x 10ms, o 33x 30ms, o algo similar).
cenizas999
@RandyGaul Revisé el algoritmo descrito en la página 215-218, especialmente la página 218 (vista previa de Google). Es bastante elegante, aunque todavía no he pensado en todas sus implicaciones, fortalezas y debilidades. ¿Será mucho más rápido que el mío? Si es así, ¿qué parte de mi algoritmo es lenta en comparación con la recurrencia de Ericson? ¿La ecuación en el paso 3 va a ser demasiado lenta? La recursión me hace dudar, ya que algunos objetos pueden moverse MUY rápido y, por lo tanto, podría ser necesaria una gran recursividad en algunos casos. (También, OUCH, $ 70 por ese libro ...)
MindSeeker
1
@MindSeeker No tengo tiempo para revisar su derivación, pero estoy seguro de que los algoritmos en el libro de Ericson, cualquiera de ellos, funcionarán realmente bien y probablemente serán más rápidos y más robustos que sus cosas. Puede encontrar versiones en PDF en línea de forma gratuita, si desea hacer una demostración de las otras páginas. Además, si va a hacer la detección de colisiones con frecuencia, el libro naranja es un elemento básico.
RandyGaul

Respuestas:

9

Esencialmente, ha creado una versión algo entusiasta de los volúmenes barridos .

Toma las dos posiciones del objeto. "Barrer" el objeto de principio a fin. Para una esfera, esto crearía una cápsula. Para una caja, esto crearía un hexágono (o una caja más larga es el movimiento a lo largo de un solo eje). Para polígonos convexos generales, esto crearía un polígono convexo diferente.

Ahora puede hacer pruebas de intersección (incluidas las consultas de quadtree) utilizando este volumen barrido. Puede calcular cuándo se produjo la colisión, avanzar la simulación desde el momento de inicio hasta el tiempo de colisión y repetir.

Otra opción, algo más simple, es hacer lo que @ ashes999 dijo y simplemente usar un intervalo de tiempo más pequeño o velocidades más pequeñas. Hay una velocidad máxima ideal derivada del intervalo en el que ningún objeto puede moverse más lejos que su lado más estrecho en una sola interacción física. Para objetos particularmente pequeños o particularmente rápidos, es posible que no pueda encontrar un intervalo razonablemente pequeño que funcione bien.

Consulte Detección de colisiones en tiempo real para obtener uno de los mejores libros introductorios / intermediarios sobre el tema de la detección de colisiones.

Sean Middleditch
fuente
¡Gracias por la increíble aportación! Desglosando su respuesta para poder hacer preguntas al respecto: "" Barrer "el objeto desde el principio hasta el final". Hasta ahora estoy rastreando; Definitivamente una mejora sobre mi método de caja. Alimentaré estas formas por quadtree y luego buscaré colisiones más exactas. "Puedes calcular cuándo ocurrió la colisión". Jaja más fácil decirlo que hacerlo :) ¿Recomiendas que me quede con mi ecuación del paso 3 para el paso? ¿O hay un mejor camino? Esta es la parte realmente crítica.
MindSeeker
[continúa] "Otra opción ..." Pensé en esa opción, pero desafortunadamente las velocidades son demasiado altas. Vea la respuesta de mi comentario a @ ashes999 y edite más arriba para obtener más información. ¡Muchas gracias por su ayuda!
MindSeeker
La única forma de saber sobre el rendimiento es probarlo, medirlo y ver. He visto algún código "obviamente" ineficiente que supera ampliamente a las versiones eficientes antes, generalmente por razones bastante no intuitivas. No preguntes qué es lo más rápido; prueba y descúbrelo.
Sean Middleditch
Muy bien, seguiré adelante y probaré mi método, modificado como usted sugirió. Sin embargo, mi pregunta en el comentario sigue en pie: "Puedes calcular cuándo ocurrió la colisión". ¿Recomienda que me quede con mi ecuación del paso 3 para ese paso? ¿O hay un mejor camino? Esta es la parte más difícil del problema, creo. Los volúmenes barridos, si los entiendo correctamente, pueden decirme que las rutas de los objetos se cruzan, pero no pueden decirme si / cuando los objetos chocan.
MindSeeker
1
La geometría de @MindSeeker Swept está emitiendo rayos, excepto que está proyectando la forma en lugar de un rayo. Por lo tanto, el método debería ser similar al uso de la proyección de rayos con "rayos" para todos los objetos que se mueven rápidamente en lugar de un solo rayo versus un objeto estacionario. Después de determinar las posibles colisiones de los "rayos", debe resolver el tiempo en ambos "rayos" para asegurarse de que estaban en el mismo lugar al mismo tiempo.
stonemetal
2

El algoritmo propuesto en la pregunta funciona muy bien: es rápido y es completamente preciso , incluso cuando los objetos van a velocidades extremas. Tengo un quadtree implementado, así que después de alimentar los cuadros del paso 1 al quadtree, descubrí que el paso 2 era innecesario: mi programa se estaba ejecutando casi tan rápido como antes.

He estado usando este algoritmo durante un par de meses, y parece ser perfectamente preciso para determinar t, el momento de la colisión. Dado que parece que no hay nada en la web que sea mejor, recomiendo usar este. (Algunas de las respuestas en las otras respuestas y comentarios anteriores son geniales, pero no satisfacen las necesidades tal como se indica en la pregunta o el autor fue muy ambiguo sobre algo y nunca volvió a responder cuando se le preguntó sobre la ambigüedad )

MindSeeker
fuente
1

Todavía no tengo suficiente reputación para comentar, pero me gustaría agregar que usando lo que Sean Middleditch mencionó anteriormente hace posible calcular su "t". Al menos si entendí su respuesta y preguntas correctamente.

Aquí hay un enlace a una respuesta increíble de sam hocevar que proporciona la mejor explicación que he encontrado (¡también dibujó, hurra!)

/gamedev//a/55991/112940

Si eso es más rápido que su propio método, no puedo decirlo, pero seguro que le da todo lo que necesita para implementarlo y compararlo con el suyo.

Solo para evitar dejar una "respuesta de solo enlace", proporcionaré un resumen rápido de su idea:

  1. calcular la diferencia de Minkowski entre los dos cuadros delimitadores
  2. usando la velocidad relativa entre ellos, proyecte un segmento de rayo / línea desde el origen hasta el cuadro creado por la Diferencia de Minkowski para obtener el punto de intersección
  3. Si el rayo golpea, divida la distancia recorrida por su rayo por la longitud del vector que representa la velocidad relativa y obtendrá su "t"
  4. haga clic en el enlace que proporcioné arriba y vea una hermosa explicación de todo esto, con muchas fotos. Es asombroso.
user1593842
fuente