Masalah Deteksi Tabrakan Circle-Line

Saat ini saya sedang mengembangkan klon breakout dan saya telah memukul hambatan dalam mendapatkan deteksi tabrakan antara bola (lingkaran) dan batu bata (cembung poligon) yang bekerja dengan benar. Saya menggunakan tes deteksi tabrakan Circle-Line di mana setiap baris mewakili dan tepi pada bata cembung poligon.

Untuk sebagian besar waktu, tes Circle-Line bekerja dengan baik dan titik-titik tabrakan diselesaikan dengan benar.

Deteksi tabrakan bekerja dengan benar.

Namun, kadang-kadang kode deteksi tabrakan saya mengembalikan false karena diskriminan negatif ketika bola benar-benar memotong bata.

Deteksi tabrakan gagal.

Saya menyadari inefisiensi dengan metode ini dan saya menggunakan kotak kotak yang sejajar untuk mengurangi jumlah batu bata yang diuji. Perhatian utama saya adalah jika ada bug matematika dalam kode saya di bawah ini.

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

Segmen yang berjalan dari A ke B dapat dihitung sebagai

P (t) = A + D · t dengan D adalah B - A dan t beroperasi dari 0 hingga 1

Sekarang lingkaran dipusatkan pada titik asal (pindahkan A dan B jika perlu untuk menempatkan titik pusat pada titik asal) dan memiliki jari-jari r .

Anda memiliki persimpangan jika untuk beberapa t Anda mendapatkan bahwa P memiliki panjang r yang sama atau, ekuivalen, bahwa panjang P kuadrat sama dengan r²

Panjang kuadrat vektor diperoleh dengan melakukan produk titik vektor sendiri (ini sangat benar bahwa jika seseorang menemukan operasi yang cocok untuk produk dot ia dapat mendefinisikan konsep panjang dan baru yang konsisten)

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

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

Kami ingin mencari yang mana kami mendapatkan P · P = r² sehingga kami akhirnya bertanya pada diri sendiri kapan

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

atau kapan

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

ini adalah persamaan Quadratic yang sangat terkenal

at² + bt + c = 0

dengan

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

Kita harus memeriksa apakah determinan b² - 4ac adalah positif dan jadi kami menemukan 2 nilai t yang memberi kita titik persimpangan P (t).

t harus antara 0 dan 1 jika tidak kami menemukan solusi yang terletak pada garis yang melewati A dan B tetapi sebelum A atau setelah B

[EDIT]

Karena pertanyaan lain mungkin dapat membantu jawaban ini, saya memutuskan untuk mencoba menyederhanakan alasan dalam pengeditan ini menggunakan beberapa gambar. Ini adalah kondisi awal. Sekarang fokus pada segmen A_B

D adalah vektor yang memindahkan A ke B jadi jika t adalah antara 0 dan 1, D · t adalah "fraksi yang tepat" dari D sehingga titik A + D · t terletak di segmen A_B : titik-titik coklat muncul ketika t adalah antara 0 dan 1 dan yang hijau tua adalah ketika t> 1.

Sekarang kita dapat menyederhanakan hal-hal jika kita memindahkan pusat lingkaran ke Asal. Ini dapat selalu dilakukan karena hanya perubahan sistem koordinat yang menjaga geometri, sudut, persimpangan, ukuran, dll.

Sekarang kita memiliki cara sederhana untuk menghitung panjang P ketika t bervariasi dan mengatakan untuk apa P melintasi batas-batas lingkaran.

Seperti yang Anda lihat P ' panjangnya lebih besar dari r sedangkan P " kurang dari r. Karena baik vektor panjang dan r adalah bilangan positif, hubungan urutan menjadi lebih besar atau kurang dari yang dipertahankan adalah kita menghitung hubungan antara panjang kuadrat dan jari-jari kuadrat. P * 1 dan P * 2 adalah titik yang membuat | P | ² sama dengan r²

Seperti yang disebutkan di bagian pra-edit, kita tiba untuk mendapatkan persamaan kuadrat di mana t adalah variabel kita. Seperti diketahui nilai-nilai solusi dari t rentang dari kasus ketika t adalah beberapa bilangan kompleks - yang berarti tidak ada persimpangan; kasus ketika t adalah dua solusi yang sama - itu berarti bahwa ada satu persimpangan; kasus ketika ada dua solusi yang berbeda- itu berarti bahwa ada dua persimpangan.

The diskriminan digunakan untuk membedakan kondisi sebelumnya dan uji validitas dilakukan pada t untuk melihat apakah itu persimpangan valid tetapi di luar segmen kami - yaitu t solusi harus nyata dan antara 0 dan 1 untuk dianggap sebagai persimpangan yang tepat yang jatuh di segmen A_B