Localizando o ponto de contato com o SAT

O Teorema do Eixo Separador (SAT) facilita a determinação do Vetor Mínimo de Conversão, ou seja, o vetor mais curto que pode separar dois objetos em colisão. No entanto, o que eu preciso é do vetor que separa os objetos ao longo do vetor que o objeto penetrante está se movendo (ou seja, o ponto de contato).

Tirei uma foto para ajudar a esclarecer. Há uma caixa, movendo-se da posição anterior para a posição posterior. Na posição posterior, cruza o polígono cinza. O SAT pode retornar facilmente a MTV, que é o vetor vermelho. Eu estou olhando para calcular o vetor azul.

Minha solução atual realiza uma pesquisa binária entre as posições antes e depois até que o comprimento do vetor azul seja conhecido até um certo limite. Funciona, mas é um cálculo muito caro, pois a colisão entre as formas precisa ser recalculada a cada loop.

Existe uma maneira mais simples e / ou mais eficiente de encontrar o vetor do ponto de contato?

O que você está falando é bastante difícil se você o estruturar como primeiro movendo um objeto, testando a colisão e recuando até sair do objeto. Provavelmente é melhor pensar nisso como um teste de interseção dinâmico : um objeto em movimento contra um objeto estacionário.

Felizmente, a separação de testes de eixos pode ajudá-lo aqui! Aqui está uma descrição do algoritmo, cortesia de Ron Levine :

O algoritmo é assim. Você trabalha com o vetor de velocidade relativa dos dois corpos convexos. Projetar cada um dos dois corpos e o vetor de velocidade relativa em um eixo de separação específico em t ₀ fornece dois intervalos 1-D e uma velocidade 1-D, de modo que é fácil saber se os dois intervalos se cruzam e, se não, se eles estão se afastando ou se movendo juntos. Se eles estiverem separados e se afastarem em qualquer um dos eixos de separação (ou, de fato, em qualquer eixo), você saberá que não há colisão futura. Se em qualquer eixo de separação os dois intervalos projetados se cruzam em t₀ ou são separados e estão se movendo juntos, é fácil calcular (por duas expressões lineares 1D simples) o tempo futuro mais próximo no qual os dois intervalos se cruzam primeiro e (assumindo o movimento retilíneo contínuo) o tempo futuro mais recente no qual os dois os intervalos durarão um cruzamento e começarão a se afastar. (Se eles estiverem se cruzando em t ₀, o tempo de interseção futuro mais cedo é t ₀). Faça isso para no máximo todos os eixos de separação. Se o máximo de todos os eixos do tempo de interseção futuro mais antigo for menor que o mínimo de todos os eixos do último tempo de interseção futuro, esse tempo máximo de interseção futura será o tempo exato da primeira colisão dos dois poliedros 3D; caso contrário, haverá não há colisão no futuro.

Em outras palavras, você percorre todos os eixos que normalmente faria em um teste estático de separação de eixos. Em vez de sair mais cedo, se você não encontrar sobreposição, continue e verifique a velocidade projetada do objeto em movimento. Se ele está se movendo para longe do objeto estático, então você cedo-out. Caso contrário, você poderá resolver o primeiro e o mais recente horário de contato com bastante facilidade (é um intervalo 1D se movendo em direção a outro intervalo 1D). Se você fizer isso para todos os eixos e manter o máximo do tempo de interseção mais antigo e o mínimo do tempo de interseção mais recente, saberá se o seu objeto em movimento atingirá o objeto estático e também quando. Assim, você pode avançar seu objeto em movimento exatamente até o ponto em que atingirá o objeto estático.

Aqui estão alguns pseudocódigos aproximados e não verificados para o 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

Aqui está um artigo do Gamasutra falando sobre isso implementado para alguns testes primitivos diferentes. Observe que, assim como o SAT, isso requer objetos convexos.

Além disso, isso é um pouco mais complicado do que um simples teste de eixo de separação. Tenha certeza absoluta de que precisa antes de tentar. Um número muito grande de jogos simplesmente empurra os objetos um do outro ao longo do vetor de conversão mínimo, porque eles simplesmente não penetram muito um no outro em um determinado quadro e é praticamente imperceptível visualmente.

Você deseja usar o recorte de polígono. Isso é melhor explicado com fotos, que eu não tenho, mas esse cara fez, então eu vou deixá-lo explicar.

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

O coletor de contato retornará um ponto em um dos objetos que é "mais responsável" pela colisão, não o ponto direto da colisão. No entanto, você realmente não precisa desse ponto de colisão direta. Você pode simplesmente separar os objetos usando a profundidade de penetração e o normal que já possui, e usar o coletor de contato para aplicar outros efeitos físicos (por exemplo, faça a caixa tombar / rolar a ladeira).

Observe que sua imagem ilustra um pequeno problema: o ponto no vetor azul que você está solicitando não será encontrado em nenhuma simulação física, porque não é exatamente onde a caixa atingirá. A caixa batia com seu canto inferior esquerdo em algum lugar mais acima da ladeira, quando apenas um pequeno pedaço do canto penetra.

A profundidade de penetração será relativamente pequena, e simplesmente empurrar a caixa para fora da encosta ao longo da penetração normal colocará a caixa perto o suficiente da posição "correta" para ser quase imperceptível na prática, especialmente se a caixa estiver quicando, tombe ou deslize depois mesmo assim.

Basta projetar o vetor MAT na direção Vector. O vetor resultante pode ser adicionado ao vetor de direção para compensar a penetração. Projete da mesma maneira, como no Eixo ao fazer o SAT. Isso define o objeto exatamente na posição em que toca o outro objeto. Adicione um pequeno epsilon para combater problemas de ponto flutuante.

Há algumas ressalvas na minha resposta, que vou sair primeiro do caminho: lida apenas com caixas delimitadoras não rotativas. Ele pressupõe que você está tentando lidar com problemas de encapsulamento , ou seja, problemas causados ​​por objetos em movimento em alta velocidade.

Depois de identificar a MTV, você conhece a borda / superfície normal na qual precisa testar. Você também conhece o vetor de velocidade linear do objeto interpenetrante.

Depois de estabelecer que, em algum momento do quadro, ocorreu uma interseção, você poderá executar operações binárias de meio passo, com base nos seguintes pontos de partida: Identifique o vértice que penetrou primeiro durante o quadro:

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

Depois de identificar o vértice, a meia etapa binária se torna muito mais barata:

//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;

Isso é razoavelmente preciso, mas fornecerá apenas um único ponto de colisão, em um único caso.

O problema é que geralmente é possível dizer com antecedência se um objeto se moverá rápido o suficiente por quadro para poder fazer um túnel como esse; portanto, o melhor conselho é identificar os vértices principais ao longo da velocidade e fazer um teste de raio ao longo do vetor de velocidade. No caso de objetos rotativos, você precisará executar algum tipo de slerp binário de meia etapa para garantir o ponto de contato correto.

Na maioria dos casos, porém, pode-se supor com segurança que a maioria dos objetos em sua cena não se move rápido o suficiente para penetrar tão longe em um único quadro; portanto, não é necessário meio passo e a detecção de colisão discreta será suficiente. Objetos de alta velocidade, como marcadores, que se movem muito rápido para ver, podem ser rastreados por raios para pontos de contato.

Curiosamente, esse método de meia etapa também pode fornecer o tempo (quase) exato em que o objeto ocorreu durante o quadro:

float collisionTime = frametimeSeconds * halfstep;

Se você estiver executando algum tipo de resolução de colisão física, poderá corrigir a posição de A:

v - (v*halfstep)

então você pode fazer sua física normalmente a partir daí. A desvantagem é que, se o objeto se mover razoavelmente rápido, você o verá se teletransportando de volta ao longo do vetor de velocidade.