Problem bei der Erkennung von Kreislinienkollisionen

11

Ich entwickle gerade einen Breakout-Klon und habe eine Straßensperre getroffen, um die Kollisionserkennung zwischen einer Kugel (Kreis) und einem Stein (konvexes Polygon) zu erhalten, die korrekt funktioniert. Ich verwende einen Kreis-Linien-Kollisionserkennungstest, bei dem jede Linie den konvexen Polygonstein darstellt und kantet.

Die meiste Zeit funktioniert der Circle-Line-Test ordnungsgemäß und die Kollisionspunkte werden korrekt aufgelöst.

Kollisionserkennung funktioniert korrekt.

Gelegentlich gibt mein Kollisionserkennungscode jedoch aufgrund einer negativen Diskriminante falsch zurück, wenn der Ball tatsächlich den Stein schneidet.

Kollisionserkennung fehlgeschlagen.

Ich bin mir der Ineffizienz dieser Methode bewusst und verwende achsenausgerichtete Begrenzungsrahmen, um die Anzahl der getesteten Steine ​​zu verringern. Mein Hauptanliegen ist, ob mein Code unten mathematische Fehler enthält.

/* 
 * from and to are points at the start and end of the convex polygons edge.
 * This function is called for every edge in the convex polygon until a
 * collision is detected. 
 */

bool circleLineCollision(Vec2f from, Vec2f to)
{
    Vec2f lFrom, lTo, lLine;
    Vec2f line, normal;
    Vec2f intersectPt1, intersectPt2;
    float a, b, c, disc, sqrt_disc, u, v, nn, vn;
    bool one = false, two = false;

    // set line vectors
    lFrom = from - ball.circle.centre;      // localised
    lTo = to - ball.circle.centre;          // localised
    lLine = lFrom - lTo;                    // localised
    line = from - to;

    // calculate a, b & c values
    a = lLine.dot(lLine);
    b = 2 * (lLine.dot(lFrom));
    c = (lFrom.dot(lFrom)) - (ball.circle.radius * ball.circle.radius);

    // discriminant
    disc = (b * b) - (4 * a * c);

    if (disc < 0.0f)
    {
        // no intersections
        return false;
    }
    else if (disc == 0.0f)
    {
        // one intersection
        u = -b / (2 * a);

        intersectPt1 = from + (lLine.scale(u));
        one = pointOnLine(intersectPt1, from, to);

        if (!one)
            return false;
        return true;
    }
    else
    {
        // two intersections
        sqrt_disc = sqrt(disc);
        u = (-b + sqrt_disc) / (2 * a);
        v = (-b - sqrt_disc) / (2 * a);
        intersectPt1 = from + (lLine.scale(u));
        intersectPt2 = from + (lLine.scale(v));

        one = pointOnLine(intersectPt1, from, to);
        two = pointOnLine(intersectPt2, from, to);

        if (!one && !two)
            return false;
        return true;
    }
}

bool pointOnLine(Vec2f p, Vec2f from, Vec2f to)
{
    if (p.x >= min(from.x, to.x) && p.x <= max(from.x, to.x) && 
        p.y >= min(from.y, to.y) && p.y <= max(from.y, to.y))
        return true;
    return false;
}
Jazzdawg
quelle
Ich kann keinen Unterschied zwischen Linie und Linie
feststellen
Der pointOnLine-Test kann vereinfacht und durchgeführt werden, bevor der tatsächliche Punkt berechnet wird.
FxIII
Wie wird sqrt_disc berechnet?
FxIII
Entschuldigung FxIII Ich muss ein wenig verwirrt gewesen sein, als ich meine Vektoren lokalisierte. Ich wusste nicht, dass die Vektoren gleich sein würden, wenn sie voneinander subtrahiert würden. Ich habe meinen Code ein wenig aufgeräumt, bevor ich gepostet habe, und ich habe vergessen, ihn sqrt_disc = sqrt(disc);wieder einzutragen . Vielen Dank für Ihre Antwort unten, die mir sehr geholfen hat.
Jazzdawg

Antworten:

20

Das von A nach B verlaufende Segment kann wie folgt berechnet werden

P (t) = A + D · T , wobei D ist , B - A und T läuft von 0 bis 1

Jetzt ist der Kreis auf dem Ursprung zentriert ( ggf. A und B verschieben , um den Mittelpunkt in den Ursprung zu setzen) und hat den Radius r .

Sie haben einen Schnittpunkt, wenn Sie für einige t erhalten, dass das P die gleiche Länge von r hat oder äquivalent, dass die Länge von P im Quadrat r² entspricht

Das Quadrat der Länge eines Vektors wird erhalten, indem das Punktprodukt eines Vektors selbst erstellt wird (dies ist so wahr, dass man, wenn man eine geeignete Operation für das Punktprodukt findet, ein neues und konsistentes Konzept der Länge definieren kann).

P · P = ( A + D · t) · ( A + D · t) =

A · A + 2 A · D t + D · D

Wir wollen herausfinden, für welches t wir P · P = r² erhalten, also fragen wir uns am Ende, wann

A · A + 2 A · D t + D · D t² = r²

oder wann

D · D t² + 2 A · D t + A · A - r² = 0

Dies ist die sehr berühmte quadratische Gleichung

at² + bt + c = 0

mit

a = D · D ; b = 2 A · D und c = A · A -

Wir müssen prüfen, ob die Determinante b² - 4ac positiv ist, und so finden wir 2 Werte von t, die uns die Schnittpunkte P (t) geben.

t muss zwischen 0 und 1 liegen, sonst haben wir Lösungen gefunden, die auf der Linie durch A und B liegen, aber vor A oder nach B liegen

[BEARBEITEN]

Da andere Fragen möglicherweise Hilfe zu dieser Antwort finden, habe ich mich entschlossen, die Argumentation in dieser Bearbeitung anhand einiger Bilder zu vereinfachen. Startbedingung Dies ist die Ausgangsbedingung. Konzentrieren Sie sich nun auf das Segment A_B

Segment von A nach B.

D ist der Vektor, der A nach B bewegt. Wenn also t zwischen 0 und 1 liegt, ist D · t ein "richtiger Bruch" von D, sodass der Punkt A + D · t im A_B- Segment liegt: Die braunen Punkte kommen, wenn t ist zwischen 0 und 1 und dem dunkelgrünen liegt, wenn t> 1 ist.

Jetzt können wir die Dinge vereinfachen, wenn wir den Mittelpunkt des Kreises in den Ursprung verschieben. Dies kann immer erfolgen, da es sich lediglich um eine Änderung des Koordinatensystems handelt, bei der Geometrie, Winkel, Schnittpunkte, Maße usw. erhalten bleiben.

Kreis bewegt sich zur Mitte

Jetzt haben wir eine einfache Möglichkeit, die Länge von P zu berechnen, wenn t variiert, und zu sagen, für welche t P die Grenzen des Kreises überschreitet.

Beispiele

Wie Sie sehen , ist P ' in der Länge größer als r, während P " kleiner als r ist. Da sowohl die Vektorlänge als auch r positive Zahlen sind, berechnen wir die Beziehung zwischen den Längen, wenn das Verhältnis der Größenordnung größer oder kleiner als erhalten bleibt Quadrat und Radius im Quadrat. P * 1 und P * 2 sind der Punkt, an dem | P | ² gleich r² ist

Wie im Abschnitt vor der Bearbeitung erwähnt, erhalten wir eine quadratische Gleichung, in der t unsere Variable ist. Bekanntlich reichen die Lösungswerte von t von dem Fall, in dem t ein paar komplexe Zahlen sind - das bedeutet keine Schnittmenge; der Fall, wenn t zwei gleiche Lösungen sind - das bedeutet, dass es einen Schnittpunkt gibt; Wenn es zwei unterschiedliche Lösungen gibt, bedeutet dies, dass es zwei Schnittpunkte gibt.

Die Diskriminante wird verwendet, um die vorherige Bedingung zu unterscheiden, und es wird ein Gültigkeitstest für t durchgeführt, um festzustellen, ob es sich um eine gültige Kreuzung handelt, jedoch außerhalb unseres Segments. Das heißt, die Lösung t muss real sein und zwischen 0 und 1 liegen, um als geeignete Kreuzung im Herbst zu gelten im Segment A_B

FxIII
quelle
3
Dies ist der richtige Algorithmus. Eine wirklich gute Beschreibung der Funktionsweise finden Sie in Real Time Rendering Third Edition , Seiten 787 bis 791. Wenn Sie sie in einer Bibliothek finden, lohnt sich ein Blick darauf.
Darcy Rayner
4
Mit der 8. Gegenstimme zu dieser Antwort habe ich 2.000 Reputationspunkte erreicht. Ich schätze das Vertrauen, das Sie mir entgegengebracht haben, sehr. Dies ist sowohl eine Anerkennung meiner Bemühungen als auch ein Anreiz, weiterhin mein Bestes zu geben, um eine Antwort von höchster Qualität zu erzielen. Vielen Dank
FxIII
Moment mal, berücksichtigt dies die beiden Eckfälle korrekt? Zum Beispiel kann ein Kreis die durch die Linie außerhalb von t0 <= t <= t1 definierte Ebene kreuzen, aber etwas später die Endpunkte des Liniensegments treffen. Sie müssen den Mindestabstand zwischen den Linienendpunkten und dem Kreispfad überprüfen. Wenn dieser Abstand kleiner als der Kreisradius ist, wurde die Linie getroffen.
Darcy Rayner
@DarcyRayner meinst du den Fall, wenn beide Punkte innerhalb des Kreisbereichs liegen?
FxIII