2D AABB vs AABB Sweep: Como calcular o acerto normal?

8

Eu implementei um lançamento de varredura 2D AABBvsAABB no meu jogo, no entanto, estou tendo dificuldade em calcular o acerto normal do elenco de varredura.

AABB vs AABB Sweep: Como calcular o acerto normal?

Eu tenho a direção de varredura, as posições AAB B e xy min-maxs, primeiro e último tempos de batida para trabalhar, mas não a (s) aresta (s) em colisão ou a direção normal. Simplesmente não consigo conceber uma solução eficiente para esse problema específico. Alguma ideia? :)

*editar

É isso que eu tenho até agora - apenas uma implementação geral da varredura AABB de Gomez e Christer Ericson . Não há acerto normal, portanto, embora o cálculo normal seja um mistério para mim, não consigo produzir nenhuma resposta de colisão para o meu controlador de personagem.

bool SweepVelAABBvsAABB(AABB a, AABB b, Vector2 v, out Vector2 outVel, out Vector2 norm )
    {
        outVel = v; //Initialise out velocity
        norm = Vector2.zero;

        if( AABBvsAABB(a,b) ) return true; //return early if a,b overlap

        v = -v;
        float hitTime = 0.0f;
        float outTime = 1.0f;

        if(v.x < 0.0f) //sweep is going right
        {
            if(b.max.x < a.min.x) return false;
            if(a.max.x < b.min.x) hitTime = Mathf.Max( (a.max.x - b.min.x) / v.x, hitTime );
            if(b.max.x > a.min.x) outTime = Mathf.Min( (a.min.x - b.max.x) / v.x, outTime );
        }
        else if(v.x > 0.0f) //sweep is going left
        {
            if(b.min.x > a.max.x) return false;
            if(b.max.x < a.min.x) hitTime = Mathf.Max( (a.min.x - b.max.x) / v.x, hitTime );
            if(a.max.x > b.min.x) outTime = Mathf.Min( (a.max.x - b.min.x) / v.x, outTime );
        }

        if(hitTime > outTime) return false;

        //=================================

        if(v.y < 0.0f) //sweep is going up
        {
            if(b.max.y < a.min.y) return false;
            if(a.max.y < b.min.y) hitTime = Mathf.Max( (a.max.y - b.min.y) / v.y, hitTime );
            if(b.max.y > a.min.y) outTime = Mathf.Min( (a.min.y - b.max.y) / v.y, outTime );
        }
        else if(v.y > 0.0f) //sweep is going down
        {
            if(b.min.y > a.max.y) return false;
            if(b.max.y < a.min.y) hitTime = Mathf.Max( (a.min.y - b.max.y) / v.y, hitTime );
            if(a.max.y > b.min.y) outTime = Mathf.Min( (a.max.y - b.min.y) / v.y, outTime );
        }

        if(hitTime > outTime) return false;

        outVel = -v * hitTime;

        return true;
    }
Larolaro
fonte
11
Seus objetos são caixas? Eles deveriam ser capazes de girar?
Aaaaaaaaaaaa

Respostas:

6

Eu consegui encontrar uma solução simples e eficiente observando os eixos de separação.

AABBvsAABB Sweep - Cálculo normal de ocorrência

// Sweep a in the direction of v against b, returns true & info if there was a hit
// ===================================================================
bool SweepBoxBox( AABB a, AABB b, Vector2 v, out Vector2 outVel, out Vector2 hitNormal )
{
    //Initialise out info
    outVel = v;
    hitNormal = Vector2.zero;

    // Return early if a & b are already overlapping
    if( AABBvsAABB(a, b) ) return false;

    // Treat b as stationary, so invert v to get relative velocity
    v = -v;

    float hitTime = 0.0f;
    float outTime = 1.0f;
    Vector2 overlapTime = Vector2.zero;

    // X axis overlap
    if( v.x < 0 )
    {
        if( b.max.x < a.min.x ) return false;
        if( b.max.x > a.min.x ) outTime = Mathf.Min( (a.min.x - b.max.x) / v.x, outTime );

        if( a.max.x < b.min.x )
        {
            overlapTime.x = (a.max.x - b.min.x) / v.x;
            hitTime = Mathf.Max(overlapTime.x, hitTime);
        }
    }
    else if( v.x > 0 )
    {
        if( b.min.x > a.max.x ) return false;
        if( a.max.x > b.min.x ) outTime = Mathf.Min( (a.max.x - b.min.x) / v.x, outTime );

        if( b.max.x < a.min.x )
        {
            overlapTime.x = (a.min.x - b.max.x) / v.x;
            hitTime = Mathf.Max(overlapTime.x, hitTime);
        }
    }

    if( hitTime > outTime ) return false;

    //=================================

    // Y axis overlap
    if( v.y < 0 )
    {
        if( b.max.y < a.min.y ) return false;
        if( b.max.y > a.min.y ) outTime = Mathf.Min( (a.min.y - b.max.y) / v.y, outTime );

        if( a.max.y < b.min.y )
        {
            overlapTime.y = (a.max.y - b.min.y) / v.y;
            hitTime = Mathf.Max(overlapTime.y, hitTime);
        }           
    }
    else if( v.y > 0 )
    {
        if( b.min.y > a.max.y ) return false;
        if( a.max.y > b.min.y ) outTime = Mathf.Min( (a.max.y - b.min.y) / v.y, outTime );

        if( b.max.y < a.min.y )
        {
            overlapTime.y = (a.min.y - b.max.y) / v.y;
            hitTime = Mathf.Max(overlapTime.y, hitTime);
        }
    }

    if( hitTime > outTime ) return false;

    // Scale resulting velocity by normalized hit time
    outVel = -v * hitTime;

    // Hit normal is along axis with the highest overlap time
    if( overlapTime.x > overlapTime.y )
    {
        hitNormal = new Vector2(Mathf.Sign(v.x), 0);
    }
    else
    {
        hitNormal = new Vector2(0, Mathf.Sign(v.y));
    }

    return true;
}
Larolaro
fonte
2

Diagrama com normais

Observe como o acerto normal do A é sum(Normals of Vectors of Edges on B involved in collision). Em ordem de palavras:

  1. Encontre as arestas envolvidas no objeto com o qual estamos colidindo .
  2. De obter os vértices dessas arestas.
  3. Soma as normais desses vértices.
  4. Transforme o vetor resultante em um vetor unitário (normalize).

Lembre-se de que uma "aresta" pode ser apenas um vértice ( estamos colidindo com o canto em outra caixa).

Você também notará que isso se aplica ao acerto normal de B.

Jonathan Dickinson
fonte
Ah, entendo, seria uma boa maneira de obter a direção normal, no entanto, um problema disso é que não tenho a borda colidida para calcular a direção normal.
Larolaro
faça o teste aabb vs aabb e verifique novamente quais bordas estão colidindo.
Gustavo Maciel
Infelizmente, como verificar as arestas é o que me escapa, não posso verificar as arestas em questão se não souber como obtê-las.
Larolaro
verifique aabb vs aabb se true, então verifique vértice vs aabb, obtenha todos os vértices que se cruzam, obtenha as arestas pelos vértices, calcule o normal.
Gustavo Maciel
Eu posso fazer isso, mas em nenhum momento o "A" realmente cruza o "B", mesmo que fosse (a varredura se tornaria inválida por estar dentro do objeto contra o qual você está varrendo) Eu obteria qualquer número de vértices / arestas irrelevante para a aresta de colisão real. Você se importaria de postar uma resposta para explicar sua teoria?
Larolaro
0

Se bem entendi, seu algoritmo até agora encontra a posição ao longo do movimento de A na qual A e B estão apenas tocando.

Com essa posição, execute um teste de interseção unidimensional entre A e B nos três eixos. Um (ou mais em casos de canto) desses eixos não terá sobreposição; o acerto normal deve ser paralelo a esse eixo e na direção de B a A.

Se mais de um eixo não tiver sobreposição, você acertará uma aresta ou um canto perfeitamente; você pode escolher arbitrariamente uma opção ou somar os resultados para um canto "arredondado".

Kevin Reid
fonte
A verificação de sobreposições com "B" e o tempo de acerto "A" daria resultados inconsistentes porque as arestas são praticamente iguais entre si (o cálculo desliza as arestas infinitamente niveladas) mesmo com um épsilon adicional no tempo de acerto, a interseção seria sempre sobrepondo-se a dois eixos.
Larolaro
Sim, deve estar sobreposto em dois eixos. É o eixo que não se sobrepõe ou quase se sobrepõe, que é paralelo ao normal. Se você estiver preocupado com erros numéricos, escolha o eixo que menos se sobrepõe (ou não se sobrepõe).
Kevin Reid