Menemukan titik kontak dengan SAT

Teorema Pemisah Sumbu (SAT) memudahkan untuk menentukan Vektor Terjemahan Minimum, yaitu vektor terpendek yang dapat memisahkan dua objek bertabrakan. Namun, yang saya butuhkan adalah vektor yang memisahkan objek di sepanjang vektor yang bergerak menembus objek (yaitu titik kontak).

Saya membuat gambar untuk membantu memperjelas. Ada satu kotak, bergerak dari posisi sebelumnya ke posisi berikutnya. Dalam posisi setelahnya, memotong poligon abu-abu. SAT dapat dengan mudah mengembalikan MTV, yang merupakan vektor merah. Saya mencari untuk menghitung vektor biru.

Solusi saya saat ini melakukan pencarian biner antara posisi sebelum dan sesudah sampai panjang vektor biru diketahui sampai batas tertentu. Ini bekerja tetapi ini merupakan perhitungan yang sangat mahal karena tabrakan antara bentuk harus dihitung ulang setiap loop.

Apakah ada cara yang lebih sederhana dan / atau lebih efisien untuk menemukan vektor titik kontak?

Apa yang Anda bicarakan cukup sulit jika Anda menyusunnya sebagai pertama memindahkan objek, kemudian menguji tabrakan, lalu mundur sampai Anda keluar dari objek. Mungkin lebih baik untuk menganggap ini sebagai tes persimpangan dinamis : objek bergerak melawan objek stasioner.

Untungnya, memisahkan pengujian poros dapat membantu Anda di sini! Berikut deskripsi algoritma, milik Ron Levine :

Algoritma berjalan seperti ini. Anda bekerja dengan vektor kecepatan relatif dari dua benda cembung. Memproyeksikan masing-masing dari dua benda dan vektor kecepatan relatif ke sumbu pemisah tertentu pada t ₀ memberikan dua interval 1-D dan kecepatan 1-D, sehingga mudah untuk mengetahui apakah dua interval berpotongan, dan jika tidak, apakah mereka bergerak terpisah atau bergerak bersama. Jika mereka dipisahkan dan bergerak terpisah pada sumbu pemisah mana pun (atau, pada kenyataannya, pada sumbu apa pun), maka Anda tahu bahwa tidak ada tabrakan di masa depan. Jika pada sumbu pisah mana pun, kedua interval yang diproyeksikan berpotongan pada t₀ atau dipisahkan dan bergerak bersama, maka mudah untuk menghitung (dengan dua ekspresi linier 1D sederhana) waktu paling awal di mana dua interval pertama akan berpotongan dan (dengan asumsi melanjutkan gerak bujursangkar) waktu masa depan terbaru di mana keduanya interval akan berlangsung berpotongan dan mulai bergerak terpisah. (Jika mereka berpotongan di t ₀ maka waktu persimpangan paling awal di masa depan adalah t ₀). Lakukan ini paling banyak untuk semua sumbu pemisah. Jika maksimum semua sumbu dari waktu persimpangan masa depan yang paling dini adalah kurang dari minimum atas semua sumbu waktu persimpangan terbaru di masa depan maka waktu persimpangan maksimum di masa mendatang adalah waktu yang tepat dari tabrakan pertama dari dua polyhedra 3D, jika tidak ada tidak ada tabrakan di masa depan.

Dengan kata lain, Anda mengulangi semua sumbu yang biasanya Anda lakukan dalam tes sumbu pemisah statis. Alih-alih keluar-awal jika Anda tidak menemukan tumpang tindih, Anda terus berjalan dan memeriksa kecepatan yang diproyeksikan dari objek bergerak. Jika itu menjauh dari objek statis, maka Anda lebih awal. Jika tidak, Anda dapat memecahkan untuk waktu kontak paling awal dan terbaru cukup mudah (itu satu interval 1D bergerak menuju interval 1D lainnya). Jika Anda melakukan itu untuk semua sumbu dan menjaga maksimum waktu persimpangan paling awal dan minimum waktu persimpangan terbaru, maka Anda tahu apakah objek bergerak Anda akan mengenai objek statis, serta kapan. Jadi, Anda dapat memajukan objek bergerak hingga titik yang akan mengenai objek statis.

Berikut ini beberapa pseudocode kasar dan sepenuhnya tidak diverifikasi untuk algoritme:

t_min := +∞
t_max := -∞
foreach axis in potential_separating_axes
    a_min := +∞
    a_max := -∞
    foreach vertex in a.vertices
        a_min = min(a_min, vertex · axis)
        a_max = max(a_max, vertex · axis)
    b_min := +∞
    b_max := -∞
    foreach vertex in b.vertices
        b_min = min(b_min, vertex · axis)
        b_max = max(b_max, vertex · axis)
    v := b.velocity · axis
    if v > 0 then
        if a_max < b_min then
            return no_intersection
        else if (a_min < b_min < a_max) or (b_min < a_min < b_max) then
            t_min = min(t_min, (a_max - b_min) / v)
            t_max = max(t_max, 0)
        else
            t_min = min(t_min, (a_max - b_min) / v)
            t_max = max(t_max, (a_min - b_max) / v)
    else if v < 0 then
        // repeat the above case with a and b swapped
    else if v = 0 then
        if a_min < b_max and b_min < a_max then
            t_min = min(t_min, 0)
            t_max = max(t_max, 0)
        else
            return no_intersection
if t_max < t_min then
    // advance b by b.velocity * t_max
    return intersection
else
    return no_intersection

Berikut ini adalah artikel Gamasutra yang membicarakan penerapan ini untuk beberapa tes primitif yang berbeda. Perhatikan bahwa seperti halnya SAT, ini membutuhkan objek cembung.

Juga, ini sedikit lebih rumit daripada tes sumbu pemisah sederhana. Pastikan Anda benar-benar membutuhkannya sebelum mencobanya. Sejumlah besar gim hanya mendorong benda-benda dari satu sama lain di sepanjang vektor terjemahan minimum, karena mereka tidak menembus sangat jauh satu sama lain pada bingkai tertentu dan itu cukup banyak tidak terlihat secara visual.

Anda ingin menggunakan kliping poligon. Ini paling baik dijelaskan dengan gambar, yang tidak saya miliki, tetapi orang ini melakukannya, jadi saya akan membiarkan dia menjelaskannya.

http://www.codezealot.org/archives/394

Manifold kontak akan mengembalikan titik pada salah satu objek yang "paling bertanggung jawab" untuk tabrakan, bukan titik tumbukan langsung. Namun, Anda tidak benar-benar membutuhkan titik tumbukan langsung. Anda cukup mendorong objek terpisah menggunakan kedalaman penetrasi dan normal yang sudah Anda miliki, dan menggunakan manifold kontak untuk menerapkan efek fisik lainnya (misalnya, buat kotak jatuh / gulung ke bawah lereng).

Perhatikan bahwa gambar Anda mengilustrasikan masalah kecil: titik pada vektor biru yang Anda minta tidak akan ditemukan dalam simulasi fisik apa pun, karena itu sebenarnya bukan tempat kotak akan mengenai. Kotak itu akan mengenai sudut kiri bawahnya di suatu tempat lebih jauh di lereng karena hanya sedikit sudut yang menembus.

Kedalaman penetrasi akan relatif kecil, dan hanya mendorong kotak keluar dari kemiringan sepanjang penetrasi normal akan menempatkan kotak cukup dekat ke posisi "benar" sehingga hampir tidak terlihat dalam praktek, terutama jika kotak akan memantul, jatuh , atau geser sesudahnya.

Proyeksikan vektor MAT ke vektor arah. Vektor yang dihasilkan dapat ditambahkan ke Direction Vector untuk mengkompensasi penetrasi. Proyeksikan dengan cara yang sama, seperti yang Anda lakukan pada Sumbu saat melakukan SAT. Ini mengatur Objek tepat pada posisi yang menyentuh objek lain. Tambahkan epsilon kecil untuk melawan masalah floating point.

Ada beberapa peringatan untuk jawaban saya, bahwa saya akan keluar dari jalan pertama: Ini hanya berurusan dengan kotak berlari yang tidak berputar. Diasumsikan bahwa Anda mencoba menangani masalah tunneling , yaitu masalah yang disebabkan oleh objek yang bergerak dengan kecepatan tinggi.

Setelah Anda mengidentifikasi MTV, Anda tahu tepi / permukaan normal yang perlu Anda uji. Anda juga tahu vektor kecepatan linier dari objek yang saling menembus.

Setelah Anda menetapkan bahwa di beberapa titik selama bingkai, terjadi persimpangan, Anda kemudian dapat melakukan operasi setengah langkah biner, berdasarkan titik awal berikut: Identifikasi titik yang pertama kali menembus selama bingkai:

vec3 vertex;
float mindot = FLT_MAX;
for ( vert : vertices )
{
    if (dot(vert, MTV) < mindot)
    {
         mindot = dot(vert, MTV);
         vertex = vert;
    }
}

Setelah Anda memiliki simpul diidentifikasi, setengah langkah biner menjadi jauh lebih murah:

//mindistance is the where the reference edge/plane intersects it's own normal. 
//The max dot product of all vertices in B along the MTV will get you this value.
halfstep = 1.0f;
vec3 cp = vertex;
vec3 v = A.velocity*framedurationSeconds;
float errorThreshold = 0.01f; //choose meaningful value here
//alternatively, set the while condition to be while halfstep > some minimum value
while (abs(dot(cp,normal)) > errorThreshold)
{            
    halfstep*=0.5f;
    if (dot(cp,normal) < mindistance) //cp is inside the object, move backward
    {
        cp += v*(-1*halfstep);
    }
    else if ( dot(cp,normal) > mindistance) //cp is outside, move it forward
    {
        cp += v*(halfstep);
    }
}

return cp;

Ini cukup akurat, tetapi hanya akan memberikan satu titik tumbukan, dalam satu kasus.

Masalahnya adalah, biasanya mungkin untuk mengetahui terlebih dahulu apakah suatu objek akan bergerak cukup cepat per frame untuk dapat terowongan seperti ini, jadi saran terbaik adalah mengidentifikasi simpul terkemuka sepanjang kecepatan dan melakukan tes sinar sepanjang vektor kecepatan. Dalam hal objek berputar, Anda harus melakukan semacam biner halfstep slerp untuk memastikan titik kontak yang benar.

Dalam kebanyakan kasus, meskipun demikian, dapat diasumsikan dengan aman bahwa sebagian besar objek dalam adegan Anda tidak akan bergerak cukup cepat untuk menembus sejauh itu dalam satu frame tunggal, sehingga tidak diperlukan setengah langkah, dan deteksi tabrakan diskrit akan cukup. Objek berkecepatan tinggi seperti peluru, yang bergerak terlalu cepat untuk dilihat, dapat ditelusuri untuk titik kontak.

Menariknya, metode setengah-setengah ini juga dapat memberi Anda (hampir) waktu yang tepat ketika objek terjadi selama bingkai:

float collisionTime = frametimeSeconds * halfstep;

Jika Anda melakukan semacam resolusi tabrakan fisika, Anda kemudian dapat memperbaiki posisi A dengan:

v - (v*halfstep)

maka Anda dapat melakukan fisika Anda secara normal dari sana. Kelemahannya adalah jika objek bergerak cukup cepat, Anda akan melihatnya bergerak kembali bersama vektor kecepatannya.