Encontrar el punto de contacto con SAT

El teorema del eje de separación (SAT) simplifica la determinación del vector de traducción mínimo, es decir, el vector más corto que puede separar dos objetos en colisión. Sin embargo, lo que necesito es el vector que separa los objetos a lo largo del vector que mueve el objeto penetrante (es decir, el punto de contacto).

Dibujé un dibujo para ayudar a aclarar. Hay una caja que se mueve desde la posición anterior a la posterior. En su posición posterior, se cruza con el polígono gris. SAT puede devolver fácilmente el MTV, que es el vector rojo. Estoy buscando calcular el vector azul.

Mi solución actual realiza una búsqueda binaria entre las posiciones antes y después hasta que la longitud del vector azul se conoce hasta cierto umbral. Funciona pero es un cálculo muy costoso ya que la colisión entre formas necesita ser recalculada en cada ciclo.

¿Existe una forma más simple y / o más eficiente de encontrar el vector del punto de contacto?

De lo que está hablando es bastante difícil si lo estructura como mover primero un objeto, luego probar la colisión y luego retroceder hasta que esté fuera del objeto. Probablemente sea mejor pensar en esto como una prueba de intersección dinámica : un objeto en movimiento contra un objeto estacionario.

Afortunadamente, las pruebas de eje de separación pueden ayudarte aquí. Aquí hay una descripción del algoritmo, cortesía de Ron Levine :

El algoritmo es así. Trabaja con el vector de velocidad relativa de los dos cuerpos convexos. Proyectar cada uno de los dos cuerpos y el vector de velocidad relativa en un eje de separación particular en t ₀ da dos intervalos 1-D y una velocidad 1-D, de modo que es fácil saber si los dos intervalos se cruzan, y si no, si Se están separando o se están moviendo juntos. Si están separados y se están separando en cualquiera de los ejes de separación (o, de hecho, en cualquier eje), entonces sabrá que no hay una colisión futura. Si en cualquier eje de separación los dos intervalos proyectados se cruzan en t₀ o están separados y se mueven juntos, entonces es fácil calcular (mediante dos simples expresiones lineales 1D) el tiempo futuro más temprano en el que los dos intervalos se intersectarán primero y (suponiendo un movimiento rectilíneo continuo) el último tiempo futuro en el que los dos los intervalos se cruzarán por última vez y comenzarán a separarse. (Si se cruzan en t ₀, entonces el tiempo de intersección futuro más temprano es t ₀). Haga esto para a lo sumo todos los ejes de separación. Si el máximo en todos los ejes del tiempo de intersección futuro más temprano es menor que el mínimo en todos los ejes del tiempo de intersección futuro más reciente, entonces ese tiempo de intersección futuro más temprano es el tiempo exacto de la primera colisión de los dos poliedros 3D, de lo contrario No hay colisión en el futuro.

En otras palabras, recorre todos los ejes que normalmente haría en una prueba de eje de separación estática. En lugar de salir temprano si no encuentra superposición, continúe y verifique la velocidad proyectada del objeto en movimiento. Si se está alejando del objeto estático, entonces saldrás temprano. De lo contrario, puede resolver el tiempo de contacto más temprano y más reciente con bastante facilidad (es un intervalo 1D moviéndose hacia otro intervalo 1D). Si hace eso para todos los ejes y mantiene el máximo del primer tiempo de intersección y el mínimo del último tiempo de intersección, entonces sabrá si su objeto en movimiento golpeará el objeto estático, así como cuándo. Para que pueda avanzar su objeto en movimiento exactamente hasta el punto en el que golpeará el objeto estático.

Aquí hay un pseudocódigo aproximado y completamente no verificado para el algoritmo:

t_min := +∞
t_max := -∞
foreach axis in potential_separating_axes
    a_min := +∞
    a_max := -∞
    foreach vertex in a.vertices
        a_min = min(a_min, vertex · axis)
        a_max = max(a_max, vertex · axis)
    b_min := +∞
    b_max := -∞
    foreach vertex in b.vertices
        b_min = min(b_min, vertex · axis)
        b_max = max(b_max, vertex · axis)
    v := b.velocity · axis
    if v > 0 then
        if a_max < b_min then
            return no_intersection
        else if (a_min < b_min < a_max) or (b_min < a_min < b_max) then
            t_min = min(t_min, (a_max - b_min) / v)
            t_max = max(t_max, 0)
        else
            t_min = min(t_min, (a_max - b_min) / v)
            t_max = max(t_max, (a_min - b_max) / v)
    else if v < 0 then
        // repeat the above case with a and b swapped
    else if v = 0 then
        if a_min < b_max and b_min < a_max then
            t_min = min(t_min, 0)
            t_max = max(t_max, 0)
        else
            return no_intersection
if t_max < t_min then
    // advance b by b.velocity * t_max
    return intersection
else
    return no_intersection

Aquí hay un artículo de Gamasutra que habla sobre esto implementado para algunas pruebas primitivas diferentes. Tenga en cuenta que, al igual que SAT, esto requiere objetos convexos.

Además, esto es bastante más complicado que una simple prueba de eje de separación. Asegúrese absolutamente de que lo necesita antes de probarlo. Una gran cantidad de juegos simplemente empujan los objetos entre sí a lo largo del vector de traducción mínimo, porque simplemente no penetran mucho entre sí en un cuadro determinado y es prácticamente imperceptible visualmente.

Desea usar el recorte de polígonos. Esto se explica mejor con imágenes, que no tengo, pero este tipo sí, así que le dejaré que lo explique.

http://www.codezealot.org/archives/394

El colector de contacto devolverá un punto en uno de los objetos que es "más responsable" de la colisión, no el punto directo de la colisión. Sin embargo, realmente no necesita ese punto de colisión directa. Simplemente puede separar los objetos usando la profundidad de penetración y la normal que ya tiene, y usar el colector de contacto para aplicar otros efectos físicos (por ejemplo, haga que la caja caiga / ruede por la pendiente).

Tenga en cuenta que su imagen ilustra un pequeño problema: el punto en el vector azul que está solicitando no se encontrará en ninguna simulación física, porque eso no es realmente donde golpearía la caja. La caja golpearía con su esquina inferior izquierda en algún lugar más arriba de la pendiente, ya que solo una pequeña parte de la esquina penetra.

La profundidad de penetración será relativamente pequeña, y simplemente empujando la caja fuera de la pendiente a lo largo de la penetración normal colocará la caja lo suficientemente cerca de la posición "correcta" para que sea casi imperceptible en la práctica, especialmente si la caja va a rebotar, caerse , o deslice después de todos modos.

Simplemente proyecte el vector MAT en la dirección del vector. El vector resultante se puede agregar al vector de dirección para compensar la penetración. Proyecte de la misma manera, como lo hace en el Eje cuando hace el SAT. Esto establece el objeto exactamente en la posición en que toca el otro objeto. Agregue un pequeño épsilon para combatir problemas de coma flotante.

Hay un par de advertencias en mi respuesta, que primero me saldré del camino: solo trata con cajas de límite no giratorias. Asume que está tratando de lidiar con problemas de túnel , es decir, problemas causados ​​por objetos que se mueven a alta velocidad.

Una vez que haya identificado la MTV, sabrá el borde / superficie normal con la que debe probar. También conoce el vector de velocidad lineal del objeto interpenetrante.

Una vez que haya establecido que en algún momento durante el cuadro, se produjo una intersección, puede realizar operaciones binarias de medio paso, en base a los siguientes puntos de partida: Identifique el vértice que penetró primero durante el cuadro:

vec3 vertex;
float mindot = FLT_MAX;
for ( vert : vertices )
{
    if (dot(vert, MTV) < mindot)
    {
         mindot = dot(vert, MTV);
         vertex = vert;
    }
}

Una vez que haya identificado el vértice, el medio paso binario se vuelve mucho menos costoso:

//mindistance is the where the reference edge/plane intersects it's own normal. 
//The max dot product of all vertices in B along the MTV will get you this value.
halfstep = 1.0f;
vec3 cp = vertex;
vec3 v = A.velocity*framedurationSeconds;
float errorThreshold = 0.01f; //choose meaningful value here
//alternatively, set the while condition to be while halfstep > some minimum value
while (abs(dot(cp,normal)) > errorThreshold)
{            
    halfstep*=0.5f;
    if (dot(cp,normal) < mindistance) //cp is inside the object, move backward
    {
        cp += v*(-1*halfstep);
    }
    else if ( dot(cp,normal) > mindistance) //cp is outside, move it forward
    {
        cp += v*(halfstep);
    }
}

return cp;

Esto es razonablemente preciso, pero solo proporcionará un único punto de colisión, en un solo caso.

La cuestión es que, por lo general, es posible saber de antemano si un objeto se moverá lo suficientemente rápido por cuadro como para poder hacer un túnel como este, por lo que el mejor consejo es identificar los vértices principales a lo largo de la velocidad y hacer una prueba de rayos a lo largo del vector de velocidad. En el caso de objetos rotativos, tendrá que hacer algún tipo de slerp binario de medio paso para ensamblar el punto de contacto correcto.

Sin embargo, en la mayoría de los casos, se puede suponer con seguridad que la mayoría de los objetos en su escena no se moverán lo suficientemente rápido como para penetrar tan lejos en un solo cuadro, por lo que no es necesario medio paso, y la detección discreta de colisión será suficiente. Los objetos de alta velocidad como las balas, que se mueven demasiado rápido para ver, se pueden rastrear por puntos de contacto.

Curiosamente, este método de medio paso también puede darle el tiempo (casi) exacto en que ocurrió el objeto durante el marco:

float collisionTime = frametimeSeconds * halfstep;

Si está haciendo algún tipo de resolución de colisión física, puede corregir la posición de A:

v - (v*halfstep)

entonces puedes hacer tu física normalmente desde allí. La desventaja es que si el objeto se mueve razonablemente rápido, lo verá teletransportarse a lo largo de su vector de velocidad.