physics - colisiones - detectar colision unity
Detección continua de colisiones entre dos tetraedros en movimiento. (7)
Mi pregunta es bastante simple. Tengo dos tetraedros, cada uno con una posición actual, una velocidad lineal en el espacio, una velocidad angular y un centro de masa (centro de rotación, en realidad).
Teniendo estos datos, estoy tratando de encontrar un algoritmo (rápido) que determinaría con precisión (1) si colisionarían en algún momento en el tiempo, y si es el caso, (2) después de cuánto tiempo colisionaron y (3) ) el punto de colisión.
La mayoría de las personas resolverían esto haciendo la detección de colisión triángulo-triángulo, pero esto desperdiciaría unos pocos ciclos de CPU en operaciones redundantes, como verificar el mismo borde de un tetraedro contra el mismo borde del otro tetraedro al verificar diferentes triángulos. Esto solo significa que voy a optimizar las cosas un poco. Nada de que preocuparse.
El problema es que no conozco ningún algoritmo de triángulo-triángulo CCD (detección de colisión continua) público que tenga en cuenta la rotación automática.
Por lo tanto, necesito un algoritmo en el que se ingresen los siguientes datos:
- Datos de vértice para tres triángulos.
- Posición y centro de rotación / masa.
- Velocidad lineal y velocidad angular.
Y saldría lo siguiente:
- Si hay una colisión
- Después de cuánto tiempo ocurrió la colisión
- En qué punto del espacio ocurrió la colisión.
Gracias de antemano por tu ayuda.
Aquí hay un resumen de un enfoque matemático de forma cerrada. Cada elemento de esto será fácil de expresar individualmente, y la combinación final de estos sería una expresión de forma cerrada si alguna vez pudiera escribirlo:
1) La ecuación de movimiento para cada punto del tetraedro es bastante simple en su propio sistema de coordenadas. El movimiento del centro de masa (CM) simplemente se moverá suavemente a lo largo de una línea recta y los puntos de esquina girarán alrededor de un eje a través del CM, que se supone que es el eje z aquí, por lo que la ecuación para cada punto de esquina (parametrizada por tiempo, t) es p = v t + x + r (sen (wt + s) i + cos (wt + s) j ), donde v es la velocidad vectorial del centro de masa; r es el radio de la proyección sobre el plano xy; i , j y k son los vectores de las unidades x, y y z; y x y s representan la posición de inicio y la fase de rotación en t = 0.
2) Tenga en cuenta que cada objeto tiene su propio sistema de coordenadas para representar fácilmente el movimiento, pero para compararlos deberá rotar cada uno en un sistema de coordenadas común, que también puede ser el sistema de coordenadas de la pantalla. (Tenga en cuenta que los diferentes sistemas de coordenadas están fijos en el espacio y no viajan con los tetraedros). Así que determine las matrices de rotación y aplíquelas a cada trayectoria ( es decir, los puntos y el CM de cada uno de los tetraedros).
3) Ahora tienes una ecuación para cada trayectoria dentro del mismo sistema de coordenadas y necesitas encontrar los tiempos de las intersecciones. Esto se puede encontrar comprobando si alguno de los segmentos de línea desde los puntos hasta el CM de un tetraedro se interseca con cualquiera de los triángulos de otro. Esto también tiene una expresión de forma cerrada, como se puede encontrar here .
Acodar estos pasos hará que las ecuaciones sean terriblemente feas, pero no sería difícil resolverlos computacionalmente (aunque con la rotación de los tetraedros es necesario asegurarse de no quedar atrapado en un mínimo local). Otra opción podría ser conectarlo a algo como Mathematica para que haga el arranque por ti. (No todos los problemas tienen respuestas fáciles.)
He pasado bastante tiempo preguntándome sobre problemas de geometría como este, y parece que las soluciones precisas, a pesar de sus simples afirmaciones, son demasiado complicadas para ser prácticas, incluso para casos 2D análogos.
Pero intuitivamente veo que tales soluciones existen cuando se consideran las velocidades de traslación lineal y las velocidades angulares lineales. No piense que encontrará la respuesta en la web o en ningún libro porque de lo que estamos hablando aquí son casos especiales pero complejos. Una solución iterativa es probablemente lo que quieres de todos modos: el resto del mundo está satisfecho con eso, ¿por qué no deberías estarlo?
La detección de colisión discreta de uso común comprobaría los triángulos de cada forma en busca de colisión, en puntos discretos sucesivos en el tiempo. Aunque es fácil de calcular, podría pasar por alto un objeto en movimiento rápido que golpea a otro, debido a la colisión entre puntos discretos en el tiempo probado.
La detección continua de colisiones primero calcularía los volúmenes trazados por cada triángulo durante un infinito de tiempo. Para un triángulo que se mueve a velocidad constante y sin rotación, este volumen podría parecerse a un prisma triangular. CCD luego verificaría la colisión entre los volúmenes y finalmente rastrearía si los triángulos compartían el mismo espacio y en qué momento.
Cuando se introduce la velocidad angular, el volumen trazado por cada triángulo ya no parece un prisma. Puede parecerse más a la forma de un tornillo, como una hebra de ADN, u otras formas no triviales que puede obtener al girar un triángulo alrededor de un eje arbitrario mientras lo arrastra de forma lineal. Calcular la forma de tal volumen no es una tarea fácil.
Un enfoque podría primero calcular la esfera que contiene un tetraedro completo cuando está girando en el vector de velocidad angular dado, si no se moviera linealmente. Puedes calcular un círculo de rotación para cada vértice, y derivar la esfera a partir de eso. Dada una esfera, ahora podemos aproximar el volumen del CCD extruido como un cilindro con el radio de la esfera y progresando a lo largo del vector de velocidad lineal. Encontrar colisiones de tales cilindros nos da una primera aproximación a un área para buscar colisiones.
Un segundo enfoque complementario podría intentar aproximar el volumen real trazado por cada triángulo dividiéndolo en sub-volúmenes pequeños, casi prismáticos. Tomaría las posiciones de los triángulos en dos incrementos de tiempo y agregaría las superficies generadas al trazar los vértices de los triángulos en esos momentos. Es una aproximación porque conecta una línea recta en lugar de una curva real. Para que la aproximación evite errores graves, la duración entre cada momento sucesivo debe ser lo suficientemente corta como para que el triángulo solo complete una pequeña fracción de una rotación. La duración puede derivarse de la velocidad angular.
El segundo enfoque crea muchos más polígonos! Puede usar el primer método para limitar el volumen de búsqueda y luego usar el segundo para obtener una mayor precisión.
Si está resolviendo esto para un motor de juego, podría encontrar la precisión de más que suficiente (todavía me estremecería por el costo computacional). Si, más bien, está escribiendo un programa de CAD o trabajando en su tesis, puede que le resulte menos satisfactorio. En este último caso, es posible que desee refinar el segundo enfoque, quizás por una mejor descripción geométrica del volumen ocupado por un triángulo giratorio y en movimiento, cuando se limita a un pequeño ángulo de giro.
Lo siento, no soy un experto en matemáticas y no tengo idea de cuál es la terminología correcta. Espero que mis malos términos no oculten demasiado mi significado.
Elige un paso de tiempo arbitrario.
Calcule los límites de cada forma en dos dimensiones perpendiculares al eje en el que se está moviendo durante el paso del tiempo.
Para un paso de tiempo: si el eje de esos límites para cualquiera de los dos objetos se interseca, medio paso de tiempo y comience a retroceder.
Un tipo de búsqueda binaria de precisión cada vez más fina para descubrir el punto en el que se produce una intersección finita.
Pensé sobre esto en el pasado, pero perdió interés ... La mejor manera de resolverlo sería abstraer un objeto. Cree un sistema de coordenadas donde el primer tetraedro sea el centro (cordones baricéntricos o un sistema sesgado con un punto como origen) y abstraiga la rotación haciendo que el otro tetraedro gire alrededor del centro. Esto debería darte ecuaciones paramétricas si haces el tiempo de rotación. Agregue el movimiento del centro de masa hacia el primero y su giro y tendrá un conjunto de ecuaciones para el movimiento relativo al primero (distancia). Resuelve para t donde la distancia es igual a cero.
Obviamente, con este método, cuantos más efectos agregue (como la resistencia al viento) más complicadas serán las ecuaciones, pero es probablemente la más simple (casi todas las demás técnicas de colisión utilizan este método de abstracción). El mayor problema es que si agrega cualquier efecto que tenga retroalimentación sin una solución analítica, toda la ecuación quedará sin solución.
Nota: Si sigue la ruta de un sistema sesgado, tenga cuidado con las fallas con la distancia. Debes estar en el octante correcto! Sin embargo, este método favorece los vectores y los cuaterniones, mientras que los acordes baricéntricos favorecen las matrices. Así que elige el que tu sistema use más efectivamente.
Si estuvieras tratando de colisionar con tetraedros no rotativos, sugeriría tomar la suma de Minkowski y realizar una prueba de rayos, pero eso no funcionará con la rotación.
Lo mejor que se me ocurre es realizar una colisión de esferas barridas usando sus esferas delimitadas para darle un rango de veces para verificar el uso de la bisección o lo que sea que tenga.
Su problema se puede convertir en un problema de programación lineal y resolverlo exactamente.
Primero, supongamos que (p0, p1, p2, p3) son los vértices en el tiempo t0, y (q0, q1, q2, q3) son los vértices en el tiempo t1 para el primer tetraedro, luego, en 4d espacio-tiempo, llenan siguiente volumen cerrado 4d
V = { (r,t) | (r,t) = a0 (p0,t0) + … + a3 (p3,t0) + b0 (q0,t1) + … + b3 (q3,t1) }
Aquí los parámetros a0 ... a3 y b0 ... b3 están en el intervalo [0,1] y suman 1:
a0+a1+a2+a3+b0+b1+b2+b3=1
El segundo tetraedro es similarmente un polígono convexo (agregue un ''a todo lo anterior para definir V'' el volumen 4d para ese tetraedro en movimiento.
Ahora la intersección de dos polígonos convexos es un polígono convexo. La primera vez que esto suceda podría satisfacer el siguiente problema de programación lineal:
Si (p0, p1, p2, p3) se mueve a (q0, q1, q2, q3) y (p0 '', p1'', p2 '', p3'') se mueve a (q0 '', q1'', q2 '', q3'') entonces la primera vez que la intersección ocurre en puntos / tiempos (r, t):
Minimice t0 * (a0 + a1 + a2 + a3) + t1 * (b0 + b1 + b2 + b3) sujeto a
0 <= ak <=1, 0<=bk <=1, 0 <= ak’ <=1, 0<=bk’ <=1, k=0..4
a0*(p0,t0) + … + a3*(p3,t0) + b0*(q0,t1) + … + b3*(q3,t1)
= a0’*(p0’,t0) + … + a3’*(p3’,t0) + b0’*(q0’,t1) + … + b3’*(q3’,t1)
La última es en realidad 4 ecuaciones, una para cada dimensión de (r, t). Esto es un total de 20 restricciones lineales de los 16 valores ak, bk, ak ''y bk''. Si hay una solución, entonces
(r,t)= a0*(p0,t0) + … + a3*(p3,t0) + b0*(q0,t1) + … + b3*(q3,t1)
Es un punto de primera intersección. De lo contrario no se entrecruzan.