Ball to Ball Collision - Detection and Handling

Dengan bantuan komunitas Stack Overflow, saya telah menulis simulator fisika yang cukup mendasar namun menyenangkan.

Anda klik dan seret mouse untuk meluncurkan bola. Ini akan memantul dan akhirnya berhenti di "lantai".

Fitur besar berikutnya yang ingin saya tambahkan adalah bola ke bola tabrakan. Gerakan bola dipecah menjadi vektor kecepatan kapak dan y. Saya memiliki gravitasi (pengurangan kecil dari vektor y setiap langkah), saya memiliki gesekan (pengurangan kecil dari kedua vektor setiap tabrakan dengan dinding). Bola-bola itu dengan jujur ​​bergerak dengan cara yang realistis dan mengejutkan.

Saya kira pertanyaan saya memiliki dua bagian:

1. Apa metode terbaik untuk mendeteksi tabrakan bola ke bola?
   Apakah saya hanya memiliki loop O (n ^ 2) yang berulang pada setiap bola dan memeriksa setiap bola lainnya untuk melihat apakah radiusnya tumpang tindih?
2. Persamaan apa yang saya gunakan untuk menangani bola ke bola tabrakan? Fisika 101
   Bagaimana pengaruhnya terhadap dua bola kecepatan vektor x / y? Apa arah yang dihasilkan kedua bola itu? Bagaimana saya menerapkan ini pada setiap bola?

Menangani deteksi tabrakan "dinding" dan perubahan vektor yang dihasilkan mudah tetapi saya melihat lebih banyak komplikasi dengan tabrakan bola-bola. Dengan dinding saya hanya harus mengambil negatif dari vektor x atau y yang sesuai dan pergi ke arah yang benar. Dengan bola saya tidak berpikir seperti itu.

Beberapa klarifikasi cepat: untuk kesederhanaan saya baik-baik saja dengan tabrakan elastis sempurna untuk saat ini, juga semua bola saya memiliki massa yang sama sekarang, tetapi saya mungkin mengubahnya di masa depan.

Sunting: Sumber yang saya temukan bermanfaat

Fisika Bola 2d dengan vektor: Tabrakan 2-Dimensi Tanpa Trigonometri.pdf
Contoh deteksi tabrakan 2d Bola: Menambahkan Deteksi Tabrakan

Keberhasilan!

Saya memiliki deteksi dan respons tabrakan bola bekerja dengan baik!

Kode yang relevan:

Deteksi Tabrakan:

for (int i = 0; i < ballCount; i++)  
{  
    for (int j = i + 1; j < ballCount; j++)  
    {  
        if (balls[i].colliding(balls[j]))  
        {
            balls[i].resolveCollision(balls[j]);
        }
    }
}

Ini akan memeriksa tabrakan antara setiap bola tetapi melewatkan pemeriksaan berlebih (jika Anda harus memeriksa apakah bola 1 bertabrakan dengan bola 2 maka Anda tidak perlu memeriksa apakah bola 2 bertabrakan dengan bola 1. Selain itu, ia melompat memeriksa tabrakan dengan dirinya sendiri. ).

Kemudian, di kelas bola saya, saya memiliki metode colliding () dan resolCollision () saya:

public boolean colliding(Ball ball)
{
    float xd = position.getX() - ball.position.getX();
    float yd = position.getY() - ball.position.getY();

    float sumRadius = getRadius() + ball.getRadius();
    float sqrRadius = sumRadius * sumRadius;

    float distSqr = (xd * xd) + (yd * yd);

    if (distSqr <= sqrRadius)
    {
        return true;
    }

    return false;
}

public void resolveCollision(Ball ball)
{
    // get the mtd
    Vector2d delta = (position.subtract(ball.position));
    float d = delta.getLength();
    // minimum translation distance to push balls apart after intersecting
    Vector2d mtd = delta.multiply(((getRadius() + ball.getRadius())-d)/d); 


    // resolve intersection --
    // inverse mass quantities
    float im1 = 1 / getMass(); 
    float im2 = 1 / ball.getMass();

    // push-pull them apart based off their mass
    position = position.add(mtd.multiply(im1 / (im1 + im2)));
    ball.position = ball.position.subtract(mtd.multiply(im2 / (im1 + im2)));

    // impact speed
    Vector2d v = (this.velocity.subtract(ball.velocity));
    float vn = v.dot(mtd.normalize());

    // sphere intersecting but moving away from each other already
    if (vn > 0.0f) return;

    // collision impulse
    float i = (-(1.0f + Constants.restitution) * vn) / (im1 + im2);
    Vector2d impulse = mtd.normalize().multiply(i);

    // change in momentum
    this.velocity = this.velocity.add(impulse.multiply(im1));
    ball.velocity = ball.velocity.subtract(impulse.multiply(im2));

}

Kode Sumber: Sumber lengkap untuk collider bola ke bola.

Jika ada yang punya saran untuk meningkatkan simulator fisika dasar ini, beri tahu saya! Satu hal yang belum saya tambahkan adalah momentum sudut sehingga bola akan bergulir lebih realistis. Ada saran lain? Tinggalkan komentar!

Untuk mendeteksi apakah dua bola bertabrakan, cukup periksa apakah jarak antara pusatnya kurang dari dua kali radius. Untuk melakukan tumbukan elastis sempurna di antara bola, Anda hanya perlu khawatir tentang komponen kecepatan yang ada di arah tumbukan. Komponen lainnya (bersinggungan dengan tabrakan) akan tetap sama untuk kedua bola. Anda bisa mendapatkan komponen tumbukan dengan membuat vektor satuan yang menunjuk ke arah dari satu bola ke bola lainnya, kemudian mengambil produk titik dengan vektor kecepatan bola. Anda kemudian dapat memasukkan komponen-komponen ini ke dalam persamaan tumbukan elastis sempurna 1D.

Wikipedia memiliki ringkasan yang cukup bagus dari keseluruhan proses . Untuk bola massa apa pun, kecepatan baru dapat dihitung menggunakan persamaan (di mana v1 dan v2 adalah kecepatan setelah tumbukan, dan u1, u2 berasal dari sebelumnya):

Jika bola memiliki massa yang sama, maka kecepatannya akan berubah. Berikut beberapa kode yang saya tulis yang melakukan hal serupa:

void Simulation::collide(Storage::Iterator a, Storage::Iterator b)
{
    // Check whether there actually was a collision
    if (a == b)
        return;

    Vector collision = a.position() - b.position();
    double distance = collision.length();
    if (distance == 0.0) {              // hack to avoid div by zero
        collision = Vector(1.0, 0.0);
        distance = 1.0;
    }
    if (distance > 1.0)
        return;

    // Get the components of the velocity vectors which are parallel to the collision.
    // The perpendicular component remains the same for both fish
    collision = collision / distance;
    double aci = a.velocity().dot(collision);
    double bci = b.velocity().dot(collision);

    // Solve for the new velocities using the 1-dimensional elastic collision equations.
    // Turns out it's really simple when the masses are the same.
    double acf = bci;
    double bcf = aci;

    // Replace the collision velocity components with the new ones
    a.velocity() += (acf - aci) * collision;
    b.velocity() += (bcf - bci) * collision;
}

Adapun efisiensi, Ryan Fox benar, Anda harus mempertimbangkan membagi wilayah menjadi beberapa bagian, kemudian melakukan deteksi tabrakan dalam setiap bagian. Ingatlah bahwa bola dapat bertabrakan dengan bola lain pada batas-batas bagian, jadi ini dapat membuat kode Anda jauh lebih rumit. Efisiensi mungkin tidak akan menjadi masalah sampai Anda memiliki beberapa ratus bola. Untuk poin bonus, Anda dapat menjalankan setiap bagian pada inti yang berbeda, atau membagi proses tumbukan di dalam setiap bagian.

Nah, bertahun-tahun lalu saya membuat program seperti yang Anda sajikan di sini.
Ada satu masalah tersembunyi (atau banyak, tergantung pada sudut pandang):

• Jika kecepatan bola terlalu tinggi, Anda bisa melewatkan tabrakan.

Dan juga, hampir dalam 100% kasus kecepatan baru Anda akan salah. Yah, bukan kecepatan , tapi posisi . Anda harus menghitung kecepatan baru tepat di tempat yang benar. Kalau tidak, Anda hanya menggeser bola pada sejumlah "kesalahan" kecil, yang tersedia dari langkah diskrit sebelumnya.

Solusinya jelas: Anda harus membagi timestep sehingga, yang pertama kali Anda bergeser ke tempat yang benar, kemudian bertabrakan, kemudian bergeser selama sisa waktu yang Anda miliki.

Anda harus menggunakan partisi ruang untuk menyelesaikan masalah ini.

Bacalah Binary Space Partitioning dan Quadtrees

Sebagai klarifikasi atas saran oleh Ryan Fox untuk membagi layar menjadi wilayah, dan hanya memeriksa tabrakan di dalam wilayah ...

misalnya, membagi area permainan menjadi kotak kotak (yang akan secara sewenang-wenang mengatakan adalah 1 unit panjang per sisi), dan memeriksa tabrakan dalam setiap kotak kotak.

Itu benar-benar solusi yang tepat. Satu-satunya masalah dengan itu (seperti yang ditunjukkan poster lain) adalah bahwa tabrakan lintas batas adalah masalah.

Solusi untuk ini adalah overlay grid kedua pada 0,5 unit vertikal dan horizontal offset ke yang pertama.

Kemudian, setiap tabrakan yang akan melintasi batas di kotak pertama (dan karenanya tidak terdeteksi) akan berada di dalam kotak kotak di kotak kedua. Selama Anda melacak tabrakan yang sudah Anda tangani (karena kemungkinan ada beberapa tumpang tindih), Anda tidak perlu khawatir tentang penanganan kasus tepi. Semua tabrakan akan berada dalam kotak persegi di salah satu kotak.

Cara yang baik untuk mengurangi jumlah pemeriksaan tabrakan adalah dengan membagi layar menjadi beberapa bagian. Anda kemudian hanya membandingkan setiap bola dengan bola di bagian yang sama.

Satu hal yang saya lihat di sini untuk mengoptimalkan.

Sementara saya setuju bahwa bola memukul ketika jarak adalah jumlah jari-jari mereka, seharusnya tidak pernah benar-benar menghitung jarak ini! Alih-alih, hitunglah kuadratnya dan bekerjalah seperti itu. Tidak ada alasan untuk operasi root kuadrat yang mahal itu.

Juga, setelah Anda menemukan tabrakan Anda harus terus mengevaluasi tabrakan sampai tidak ada lagi yang tersisa. Masalahnya adalah bahwa yang pertama mungkin menyebabkan orang lain yang harus diselesaikan sebelum Anda mendapatkan gambar yang akurat. Pertimbangkan apa yang terjadi jika bola mengenai bola di tepi? Bola kedua menyentuh tepi dan segera rebound ke bola pertama. Jika Anda menabrak tumpukan bola di sudut Anda bisa memiliki beberapa tabrakan yang harus diselesaikan sebelum Anda dapat mengulangi siklus berikutnya.

Sedangkan untuk O (n ^ 2), yang dapat Anda lakukan adalah meminimalkan biaya penolakan yang terlewatkan:

1) Bola yang tidak bergerak tidak bisa mengenai apa pun. Jika ada cukup banyak bola yang tergeletak di lantai, ini bisa menghemat banyak tes. (Perhatikan bahwa Anda masih harus memeriksa apakah sesuatu mengenai bola stasioner.)

2) Sesuatu yang mungkin layak dilakukan: Membagi layar menjadi beberapa zona tetapi garis-garisnya harus tidak jelas - bola-bola di tepi zona terdaftar sebagai berada di semua zona yang relevan (bisa 4). Saya akan menggunakan kotak 4x4, menyimpan zona sebagai bit. Jika DAN dari zona dua bola mengembalikan nol, akhir pengujian.

3) Seperti yang saya sebutkan, jangan lakukan root kuadrat.

Saya menemukan halaman yang sangat bagus dengan informasi tentang deteksi tabrakan dan respons dalam 2D.

http://www.metanetsoftware.com/technique.html

Mereka mencoba menjelaskan bagaimana hal itu dilakukan dari sudut pandang akademik. Mereka mulai dengan deteksi tabrakan objek-ke-objek sederhana, dan beralih ke respon tabrakan dan bagaimana meningkatkannya.

Edit: Tautan yang diperbarui

Anda memiliki dua cara mudah untuk melakukan ini. Jay telah meliput cara akurat mengecek dari pusat bola.

Cara yang lebih mudah adalah dengan menggunakan kotak pembatas persegi panjang, atur ukuran kotak Anda menjadi 80% dari ukuran bola, dan Anda akan mensimulasikan tabrakan dengan cukup baik.

Tambahkan metode ke kelas bola Anda:

public Rectangle getBoundingRect()
{
   int ballHeight = (int)Ball.Height * 0.80f;
   int ballWidth = (int)Ball.Width * 0.80f;
   int x = Ball.X - ballWidth / 2;
   int y = Ball.Y - ballHeight / 2;

   return new Rectangle(x,y,ballHeight,ballWidth);
}

Kemudian, di loop Anda:

// Checks every ball against every other ball. 
// For best results, split it into quadrants like Ryan suggested. 
// I didn't do that for simplicity here.
for (int i = 0; i < balls.count; i++)
{
    Rectangle r1 = balls[i].getBoundingRect();

    for (int k = 0; k < balls.count; k++)
    {

        if (balls[i] != balls[k])
        {
            Rectangle r2 = balls[k].getBoundingRect();

            if (r1.Intersects(r2))
            {
                 // balls[i] collided with balls[k]
            }
        }
    }
}

Saya melihatnya mengisyaratkan di sana-sini, tetapi Anda juga bisa melakukan perhitungan lebih cepat terlebih dahulu, seperti, membandingkan kotak terikat untuk tumpang tindih, dan KEMUDIAN melakukan tumpang tindih berbasis radius jika tes pertama berlalu.

Matematika penambahan / perbedaan jauh lebih cepat untuk kotak pembatas daripada semua pemicu untuk jari-jari, dan seringkali, uji kotak pembatas akan mengabaikan kemungkinan tabrakan. Tetapi jika Anda kemudian menguji ulang dengan trigonometri, Anda mendapatkan hasil yang akurat yang Anda cari.

Ya, ini dua tes, tetapi secara keseluruhan akan lebih cepat.

Ini KineticModeladalah implementasi dari pendekatan yang dikutip di Jawa.

Saya menerapkan kode ini dalam JavaScript menggunakan elemen HTML Canvas, dan menghasilkan simulasi yang luar biasa pada 60 frame per detik. Saya memulai simulasi dengan koleksi selusin bola pada posisi dan kecepatan acak. Saya menemukan bahwa pada kecepatan yang lebih tinggi, tabrakan sekilas antara bola kecil dan bola yang jauh lebih besar menyebabkan bola kecil tersebut muncul untuk TETAP. ke tepi bola yang lebih besar, dan bergerak ke sekitar 90 derajat di sekitar bola yang lebih besar sebelum memisahkan. (Aku ingin tahu apakah ada orang lain yang mengamati perilaku ini.)

Beberapa logging perhitungan menunjukkan bahwa Jarak Terjemahan Minimum dalam kasus ini tidak cukup besar untuk mencegah bola yang sama bertabrakan di langkah waktu berikutnya. Saya melakukan beberapa percobaan dan menemukan bahwa saya dapat memecahkan masalah ini dengan meningkatkan MTD berdasarkan kecepatan relatif:

dot_velocity = ball_1.velocity.dot(ball_2.velocity);
mtd_factor = 1. + 0.5 * Math.abs(dot_velocity * Math.sin(collision_angle));
mtd.multplyScalar(mtd_factor);

Saya memverifikasi bahwa sebelum dan setelah perbaikan ini, energi kinetik total dilestarikan untuk setiap tabrakan. Nilai 0,5 di mtd_factor adalah kira-kira nilai minumum yang ditemukan selalu menyebabkan bola terpisah setelah tabrakan.

Meskipun perbaikan ini memperkenalkan sejumlah kecil kesalahan dalam fisika yang tepat dari sistem, tradeoffnya adalah sekarang bola yang sangat cepat dapat disimulasikan di browser tanpa mengurangi ukuran langkah waktu.