2D AABB vs AABB Sweep: Wie berechnet man den normalen Treffer?

8

Ich habe einen 2D-AABBvsAABB-Sweep-Cast in mein Spiel implementiert, habe jedoch Schwierigkeiten, die Treffer-Normalen des Sweep-Casts zu berechnen.

AABB vs AABB Sweep: Wie berechnet man den normalen Treffer?

Ich habe die Sweep-Richtung, sowohl die a- als auch die b-AABB-Position und die xy-Min-Max-Werte, die ersten und letzten Trefferzeiten, aber nicht die Kollisionskante (n) oder die normale Richtung. Ich kann mir einfach keine effiziente Lösung für dieses spezielle Problem vorstellen. Irgendwelche Ideen? :) :)

*bearbeiten

Dies ist, was ich bisher habe - nur eine allgemeine Implementierung des AABB-Sweeps von Gomez und Christer Ericson . Es gibt keinen normalen Treffer, daher ist mir die normale Berechnung zwar ein Rätsel, aber ich kann keine Kollisionsantwort für meinen Charakter-Controller erzeugen.

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
quelle
1
Sind Ihre Objekte Boxen? Sollen sie sich drehen können?
aaaaaaaaaaa

Antworten:

6

Ich habe es geschafft, eine einfache und effiziente Lösung zu finden, indem ich die Trennachsen beobachtet habe.

AABBvsAABB Sweep - Hit Normal Calculation

// 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
quelle
2

Diagramm mit Normalen

Beachten Sie, wie normal der Treffer des A ist sum(Normals of Vectors of Edges on B involved in collision). In geordneten Worten:

  1. Finden Sie die Kanten des Objekts, mit dem wir kollidieren .
  2. Von erhalten Sie die Eckpunkte von diesen Kanten.
  3. Summiere die Normalen dieser Eckpunkte.
  4. Verwandeln Sie den resultierenden Vektor in einen Einheitsvektor (normalisieren).

Denken Sie daran, dass eine 'Kante' tatsächlich nur ein Scheitelpunkt sein kann ( wir kollidieren mit der Ecke eines anderen Felds).

Sie werden auch feststellen, dass dies für den normalen Treffer von B gilt .

Jonathan Dickinson
quelle
Ah, ich verstehe , das wäre ein guter Weg, um die normale Richtung zu erhalten. Ein Problem dabei ist jedoch, dass ich nicht die Kante habe, die kollidiert, um die normale Richtung zu berechnen.
Larolaro
Machen Sie den aabb vs aabb Test und überprüfen Sie dann weiter, welche der Kanten kollidieren.
Gustavo Maciel
Leider ist es genau das, was mir entgeht, wie ich die Kanten überprüfe. Ich kann die fraglichen Kanten nicht überprüfen, wenn ich nicht weiß, wie ich sie bekommen kann.
Larolaro
Überprüfen Sie aabb vs aabb, wenn dies der Fall ist, und überprüfen Sie dann Vertex vs aabb. Ermitteln Sie alle Scheitelpunkte, die sich schneiden, ermitteln Sie die Kanten anhand der Scheitelpunkte und berechnen Sie die Normalen.
Gustavo Maciel
Ich kann das tun, aber zu keinem Zeitpunkt schneidet das "A" tatsächlich "B", selbst wenn es sein würde (der Sweep würde ungültig werden, wenn er sich innerhalb des Objekts befindet, gegen das Sie fegen). Ich würde eine beliebige Anzahl von Eckpunkten / Kanten erhalten irrelevant für die tatsächliche Kollisionskante. Würde es Ihnen etwas ausmachen, eine Antwort zu veröffentlichen, um Ihre Theorie zu erklären?
Larolaro
0

Wenn ich das richtig verstehe, findet Ihr Algorithmus bisher die Position entlang der Bewegung von A, an der sich A und B gerade berühren.

Führen Sie mit dieser Position einen eindimensionalen Schnittpunkttest zwischen A und B auf allen drei Achsen durch. Eine (oder mehrere in Eckfällen) dieser Achsen haben keine Überlappung; Die Treffernormale sollte parallel zu dieser Achse und in Richtung von B nach A sein.

Wenn mehr als eine Achse keine Überlappung aufweist, haben Sie eine Kante oder Ecke perfekt getroffen. Sie können entweder willkürlich eine Option auswählen oder die Ergebnisse für eine "abgerundete" Ecke summieren.

Kevin Reid
quelle
Das Überprüfen von Überlappungen mit "B" und der Trefferzeit "A" würde zu inkonsistenten Ergebnissen führen, da die Kanten ziemlich gleich sind (die Berechnung verschiebt die Kanten unendlich bündig), selbst wenn ein zusätzliches Epsilon für die Trefferzeit vorliegt, wäre der Schnittpunkt immer über zwei Achsen überlappend.
Larolaro
Ja, es sollte sich über zwei Achsen überlappen. Es ist die Achse, die sich nicht oder kaum überlappt, die parallel zur Normalen verläuft. Wenn Sie über numerische Fehler besorgt sind, wählen Sie die Achse aus, die sich am wenigsten überlappt (oder nicht überlappt).
Kevin Reid