Problem z wykrywaniem kolizji koło-linia

Obecnie opracowuję klon umożliwiający wybicie i trafiłem na przeszkodę w wykrywaniu kolizji między kulą (kołem) a cegłą (wypukłym wielokątem) działającą poprawnie. Używam testu wykrywania kolizji Koło-Linia, w którym każda linia reprezentuje i krawędź wypukłej cegły wielokąta.

Przez większość czasu test Koła-Linii działa poprawnie, a punkty kolizji są poprawnie rozwiązywane.

Wykrywanie kolizji działa poprawnie.

Czasami jednak mój kod wykrywający kolizję zwraca wartość false z powodu negatywnego dyskryminatora, gdy piłka faktycznie przecina cegłę.

Błąd wykrywania kolizji.

Zdaję sobie sprawę z nieskuteczności tej metody i używam wyrównanych do osi obwiedni, aby zmniejszyć liczbę testowanych cegieł. Moim głównym zmartwieniem jest to, czy w moim kodzie znajdują się jakieś błędy matematyczne.

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

Segment biegnący od A do B można obliczyć jako

P (t) = + D -t gdzie D jest B - A , a t wynosi od 0 do 1

Teraz okrąg jest wyśrodkowany na początku (przesuń A i B, jeśli to konieczne, aby umieścić środek na początku) i ma promień r .

Masz przecięcie, jeśli dla niektórych t uzyskasz, że P ma tę samą długość r lub, równoważnie, że długość P do kwadratu jest równa r²

Długość kwadratu wektora jest uzyskiwana przez wykonanie iloczynu kropkowego wektora (jest to tak prawdziwe, że jeśli znajdzie się odpowiednią operację dla iloczynu kropkowego, można zdefiniować nową i spójną koncepcję długości)

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

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

Chcemy znaleźć, dla którego t otrzymujemy P · P = r², więc ostatecznie zadajemy sobie pytanie, kiedy

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

albo kiedy

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

to jest bardzo znane równanie kwadratowe

at² + bt + c = 0

z

a = D · D ; b = 2 A · D ic c = A · A -r²

Musimy sprawdzić, czy wyznacznik b² - 4ac jest dodatni, dlatego też znajdujemy 2 wartości t, które dają nam punkty przecięcia P (t).

t musi wynosić od 0 do 1, w przeciwnym razie znaleźliśmy rozwiązania, które leżą na linii przechodzącej przez A i B, ale które są przed A lub po B

[EDYTOWAĆ]

Ponieważ inne pytania mogą znaleźć pomoc w tej odpowiedzi, postanowiłem spróbować uprościć rozumowanie w tej edycji za pomocą niektórych zdjęć. To jest warunek początkowy. Teraz skup się na segmencie A_B

D jest wektorem, który przenosi A do B, więc jeśli t jest między 0 a 1, D · t jest „właściwą ułamkiem” D, więc punkt A + D • t leży w segmencie A_B : brązowe punkty pojawiają się, gdy t jest między 0 a 1, a ciemnozielony występuje, gdy t> 1.

Teraz możemy uprościć sprawy, jeśli przeniesiemy środek okręgu do Początku. Można to zawsze zrobić, ponieważ jest to po prostu zmiana układu współrzędnych, który zachowuje geometrię, kąty, przecięcie, pomiary itp.

Teraz mamy prosty sposób obliczyć długość P, gdy t się zmienia, i powiedzieć, dla którego t P przekracza granice okręgu.

Jak widać, P ' ma długość większą niż r, podczas gdy P " jest mniejsze niż r. Ponieważ zarówno długość wektora r, jak i r są liczbami dodatnimi, relacja kolejności bycia większa lub mniejsza niż zachowana to obliczamy relację między długościami do kwadratu, a do kwadratu promień. P * 1 i P * 2 to punkt, który sprawia, że | P | ² jest równe r²

Jak wspomniano w sekcji wstępnej edycji, dochodzimy do równania kwadratowego, w którym t jest naszą zmienną. Jak wiadomo, wartości rozwiązania t mieszczą się w przypadku, gdy t jest kilkoma liczbami zespolonymi - oznacza to brak przecięcia; przypadek, gdy t są dwoma równymi rozwiązaniami - oznacza to, że istnieje jedno skrzyżowanie; przypadek, gdy istnieją dwa różne rozwiązania - oznacza to, że istnieją dwa skrzyżowania.

Dyskryminacyjna jest używany do rozróżnienia poprzedniego stanu i test ważności odbywa się na T, aby sprawdzić, czy jest poprawny skrzyżowanie, ale poza naszym segmencie - czyli rozwiązanie t musi być realne i między 0 a 1 należy uznać za prawidłowe skrzyżowanie że upadek w segmencie A_B