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):
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!
fuente
Respuestas:
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.
fuente
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 )
fuente
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:
fuente