Objek memiliki posisi dan vektor kecepatan. Biasanya hanya posisi yang digunakan untuk memeriksa apakah dua objek bertabrakan, ini bermasalah untuk objek yang bergerak sangat cepat karena dapat terjadi bahwa objek bergerak sangat cepat sehingga berada di depan objek pertama dalam pemeriksaan tabrakan pertama, dan di belakangnya di pemeriksaan tabrakan kedua.

Sekarang ada juga pemeriksaan tabrakan berbasis garis, di mana Anda hanya memeriksa apakah vektor pergerakan setiap objek bersinggungan dengan kotak pembatas dari objek lainnya. Ini bisa dilihat sebagai perluasan suatu titik. Ini hanya berfungsi meskipun jika objek yang bergerak cepat benar-benar kecil.

Jadi ide saya adalah, alih-alih memperluas titik, mengapa tidak memperluas persegi panjang? Ini menghasilkan Hexagon.

Sekarang, sejauh ini bagus. Tetapi bagaimana saya benar-benar memeriksa apakah dua segi enam dari jenis ini berpotongan? Perhatikan bahwa ini adalah Hexagon yang sangat spesifik.

Pertanyaan Bonus : Apakah mungkin untuk menghitung di mana tepatnya (atau lebih tepatnya setelah berapa lama) tabrakan terjadi? Ini bisa sangat berguna untuk mendeteksi apa yang sebenarnya terjadi, seperti di mana dan dengan berapa banyak daya dan untuk mensimulasikan bagaimana mereka bergerak di waktu antara tabrakan dan akhir bingkai.

Solusinya sebenarnya lebih sederhana dari yang diharapkan. Caranya adalah dengan menggunakan pengurangan Minkowski sebelum teknik segi enam Anda.

Berikut adalah persegi panjang Anda A dan B, dengan kecepatan vAdan vB. Perhatikan bahwa vAdan vBsebenarnya bukan kecepatan, itu adalah jarak yang ditempuh selama satu frame.

Sekarang ganti persegi panjang B dengan titik P, dan persegi panjang A dengan persegi panjang C = A + (- B), yang memiliki dimensi jumlah dimensi A dan B. Properti penambahan Minkowski menyatakan bahwa tabrakan antara titik dan terjadi persegi panjang baru jika dan hanya jika tabrakan antara dua persegi panjang asli terjadi:

Tetapi jika persegi panjang C bergerak di sepanjang vektor vA, dan titik P bergerak di sepanjang vektor vB, perubahan sederhana dari kerangka referensi memberitahu kita itu sama seperti jika persegi panjang C masih, dan titik P bergerak di sepanjang vektor vB-vA:

Anda kemudian dapat menggunakan rumus persimpangan kotak-segmen sederhana untuk mengetahui di mana tabrakan terjadi dalam bingkai referensi baru.

Langkah terakhir adalah kembali ke bingkai referensi yang tepat. Bagilah jarak yang ditempuh titik tersebut sampai persimpangan yang dilingkari oleh panjang vektor vB-vAdan Anda akan mendapatkan nilai ssedemikian rupa 0 < s < 1. Tabrakan terjadi pada waktu di s * Tmana Tdurasi frame Anda.

Komentar oleh madshogo :
Satu keuntungan BESAR dari teknik ini daripada yang ada dalam jawaban Tuan Beast adalah bahwa jika tidak ada rotasi, maka "pengurangan Minkowski" A + (- B) dapat dihitung satu kali untuk semua langkah waktu berikutnya !

Jadi satu-satunya algoritma yang membutuhkan waktu dalam semua ini (jumlah Minkowski, kompleksitas O (mn) di mana m adalah jumlah simpul dalam A dan n jumlah simpul dalam B ) dapat digunakan hanya sekali, secara efektif membuat deteksi tabrakan menjadi konstan- masalah waktu!

Kemudian, Anda dapat membuang jumlah begitu Anda tahu pasti bahwa A dan B berada di bagian berbeda dari adegan Anda (dari quadtree Anda?) Dan tidak akan bertabrakan lagi.

Sebaliknya, metode Mr Beast membutuhkan cukup banyak perhitungan pada setiap langkah waktu.

Juga, untuk persegi panjang yang disejajarkan dengan sumbu, A + (- B) dapat dihitung jauh lebih sederhana daripada dengan benar-benar menghitung semua jumlah, titik demi titik. Cukup rentangkan A dengan menambahkan ketinggian B ke tinggi dan lebar B ke lebarnya (satu setengah di setiap sisi).

Tetapi semua ini hanya berfungsi jika A atau B tidak berputar dan jika keduanya cembung. Jika rotasi ada atau jika Anda menggunakan bentuk cekung maka Anda harus menggunakan volume / area yang tersapu.
akhir komentar

Pertama-tama, dalam kasus persegi panjang selaras sumbu, jawaban Kevin Reid adalah yang terbaik dan algoritme adalah yang tercepat.

Kedua, untuk bentuk sederhana, gunakan kecepatan relatif (seperti yang terlihat di bawah) dan teorema sumbu pemisah untuk deteksi tabrakan. Ini akan memberi tahu Anda apakah tabrakan terjadi dalam kasus gerakan linear (tidak ada rotasi). Dan jika ada rotasi, Anda perlu timestep kecil agar lebih akurat. Sekarang, untuk menjawab pertanyaan:

Bagaimana cara memberi tahu dalam kasus umum apakah dua bentuk cembung berpotongan?

Saya akan memberi Anda algoritma yang bekerja untuk semua bentuk cembung dan bukan hanya segi enam.

Misalkan X dan Y adalah dua bentuk cembung. Mereka berpotongan jika dan hanya jika mereka memiliki titik yang sama, yaitu ada titik x ∈ X dan titik y ∈ Y sedemikian rupa sehingga x = y . Jika Anda menganggap spasi sebagai ruang vektor, maka ini sama dengan mengatakan x - y = 0 . Dan sekarang kita sampai ke bisnis Minkowski ini:

The Minkowski sum dari X dan Y adalah himpunan semua x + y untuk x ∈ X dan y ∈ Y .

Contoh untuk X dan Y

X, Y dan jumlah Minkowski mereka, X + Y

Anggaplah (-Y) adalah himpunan semua -y untuk y ∈ Y , maka diberikan paragraf sebelumnya, X dan Y berpotongan jika dan hanya jika X + (-Y) berisi 0 , yaitu asal .

Komentar samping: mengapa saya menulis X + (-Y) alih-alih X - Y ? Nah, karena dalam matematika, ada operasi yang disebut perbedaan Minkowski dari A dan B yang terkadang ditulis X - Y namun tidak ada hubungannya dengan himpunan semua x - y untuk x ∈ X dan y ∈ Y (Minkowski yang asli) perbedaannya sedikit lebih kompleks).

Jadi kami ingin menghitung jumlah Minkowski dari X dan -Y dan untuk menemukan apakah itu berisi asal. Asal tidak khusus dibandingkan dengan titik lain, sehingga untuk menemukan apakah asal berada dalam domain tertentu, kami menggunakan algoritma yang dapat memberi tahu kami apakah ada titik tertentu milik domain itu.

Jumlah Minkowski dari X dan Y memiliki properti keren, yaitu bahwa jika X dan Y cembung, maka X + Y juga. Dan menemukan apakah suatu titik milik himpunan cembung jauh lebih mudah daripada jika himpunan itu tidak (dikenal sebagai) cembung.

Kita tidak mungkin menghitung semua x - y untuk x ∈ X dan y ∈ Y karena ada titik tak terhingga dari titik x dan y , jadi semoga, karena X , Y dan X + Y adalah cembung, kita bisa menggunakan titik "terluar" yang mendefinisikan bentuk X dan Y , yang merupakan simpulnya, dan kita akan mendapatkan titik terluar X + Y , dan juga beberapa lagi.

Poin tambahan ini "dikelilingi" oleh titik terluar X + Y sehingga tidak berkontribusi untuk menentukan bentuk cembung yang baru diperoleh. Kami mengatakan bahwa mereka tidak mendefinisikan " convex hull " dari himpunan poin. Jadi yang kami lakukan adalah menyingkirkannya sebagai persiapan untuk algoritme terakhir yang memberi tahu kami apakah asalnya ada dalam convex hull.

Lambung cembung X + Y. Kami telah menghapus simpul "di dalam".

Karena itu, kami mendapatkannya

Algoritma pertama, naif

boolean intersect(Shape X, Shape Y) {

  SetOfVertices minkowski = new SetOfVertices();
  for (Vertice x in X) {
    for (Vertice y in Y) {
      minkowski.addVertice(x-y);
    }
  }
  return contains(convexHull(minkowski), Vector2D(0,0));

}

Loop jelas memiliki kompleksitas O (mn) di mana m dan n adalah jumlah simpul masing-masing bentuk. The minkoswkiset berisi mn elemen paling banyak. The convexHullalgoritma memiliki kompleksitas yang tergantung pada algoritma yang digunakan , dan Anda dapat bertujuan untuk O (k log (k)) di mana k adalah ukuran dari himpunan titik-titik, sehingga dalam kasus kami, kami mendapatkan O (mn log (mn) ) . The containsalgoritma memiliki kompleksitas yang linier dengan jumlah tepi (dalam 2D) atau wajah (dalam 3D) dari lambung cembung, sehingga benar-benar tergantung pada bentuk Anda mulai, tapi tidak akan lebih besar dari O (mn) .

Saya akan membiarkan Anda google untuk containsalgoritma untuk bentuk cembung, itu cukup umum. Saya dapat meletakkannya di sini jika saya punya waktu.

Tapi kami sedang melakukan deteksi tabrakan, jadi kami bisa mengoptimalkannya banyak

Kami awalnya memiliki dua badan A dan B bergerak tanpa rotasi selama timestep dt (dari apa yang saya tahu dengan melihat gambar Anda). Mari kita sebut v _A dan v _B masing-masing kecepatan A dan B , yang konstan selama catatan waktu durasi dt . Kami mendapatkan yang berikut ini:

dan, seperti yang Anda tunjukkan dalam gambar Anda, badan-badan ini menyapu area (atau volume, dalam 3D) saat bergerak:

dan mereka berakhir sebagai A ' dan B' setelah tanda waktu.

Untuk menerapkan algoritma naif kami di sini, kami hanya perlu menghitung volume sapuan. Tapi kami tidak melakukan ini.

Dalam kerangka referensi B , B tidak bergerak (ya!). Dan A memiliki kecepatan tertentu sehubungan dengan B yang Anda dapatkan dengan menghitung v _A - v _B (Anda dapat melakukan sebaliknya, menghitung kecepatan relatif B dalam kerangka referensi A ).

Dari kiri ke kanan: kecepatan dalam kerangka referensi dasar; kecepatan relatif; menghitung kecepatan relatif.

Dengan menganggap B sebagai tidak bergerak dalam kerangka acuannya sendiri, Anda hanya perlu menghitung volume yang dilalui A saat bergerak selama dt dengan kecepatan relatifnya v _A - v _B .

Ini mengurangi jumlah simpul yang akan digunakan dalam perhitungan jumlah Minkowski (kadang-kadang sangat).

Optimalisasi lain yang mungkin adalah pada titik di mana Anda menghitung volume yang disapu oleh salah satu tubuh, katakanlah A. Anda tidak harus menerjemahkan semua simpul yang membentuk A. Hanya yang memiliki tepi (wajah dalam 3D) yang luar "wajah" normal arah penyapuan. Tentunya Anda sudah memperhatikan itu ketika Anda menghitung area sapuan untuk kotak. Anda dapat mengetahui apakah normal menuju arah sapuan menggunakan produk titiknya dengan arah sapuan, yang harus positif.

Optimalisasi terakhir, yang tidak ada hubungannya dengan pertanyaan Anda tentang persimpangan, sangat berguna dalam kasus kami. Ia menggunakan kecepatan relatif yang kami sebutkan dan yang disebut metode sumbu pemisah. Tentunya Anda sudah tahu tentang itu.

Misalkan Anda tahu jari-jari dari A dan B terhadap mereka pusat massa (yang mengatakan, jarak antara pusat massa dan titik terjauh dari itu), seperti ini:

Sebuah tabrakan dapat terjadi hanya jika ada kemungkinan bahwa lingkaran berlari dari A bertemu yang dari B . Kita lihat di sini bahwa itu tidak akan, dan cara untuk memberitahu komputer yang untuk menghitung jarak dari C _B ke saya seperti pada gambar berikut dan pastikan itu lebih besar daripada jumlah jari-jari A dan B . Jika lebih besar, tidak ada tabrakan. Jika lebih kecil, maka tabrakan.

Ini tidak bekerja dengan baik dengan bentuk yang agak panjang, tetapi dalam kasus kotak atau bentuk lain, itu adalah heuristik yang sangat baik untuk menyingkirkan tabrakan .

Teorema sumbu pemisah diterapkan ke B dan volume disapu oleh A , akan memberi tahu Anda apakah tabrakan itu terjadi. Kompleksitas dari algoritma yang terkait adalah linier dengan jumlah jumlah simpul dari setiap bentuk cembung, tetapi kurang ajaib ketika tiba saatnya untuk benar-benar menangani tabrakan.

Algoritme baru dan lebih baik kami yang menggunakan persimpangan untuk membantu mendeteksi tabrakan, tetapi masih tidak sebagus teorema sumbu pemisah untuk benar - benar mengetahui apakah tabrakan terjadi

boolean mayCollide(Body A, Body B) {

  Vector2D relativeVelocity = A.velocity - B.velocity;
  if (radiiHeuristic(A, B, relativeVelocity)) {
    return false; // there is a separating axis between them
  }

  Volume sweptA = sweptVolume(A, relativeVelocity);
  return contains(convexHull(minkowskiMinus(sweptA, B)), Vector2D(0,0));

}

boolean radiiHeuristic(A, B, relativeVelocity)) {
  // the code here
}

Volume convexHull(SetOfVertices s) {
  // the code here
}

boolean contains(Volume v, Vector2D p) {
  // the code here
}

SetOfVertices minkowskiMinus(Body X, Body Y) {

  SetOfVertices result = new SetOfVertices();
  for (Vertice x in X) {
    for (Vertice y in Y) {
      result.addVertice(x-y);
    }
  }
  return result;

}

Saya tidak berpikir menggunakan 'segi enam' itu sangat membantu. Berikut ini sketsa cara untuk mendapatkan tumbukan yang tepat untuk persegi panjang yang disejajarkan dengan sumbu:

Dua persegi panjang yang disejajarkan dengan sumbu tumpang tindih jika dan hanya jika rentang koordinat X mereka tumpang tindih dan rentang koordinat Y mereka tumpang tindih. (Ini dapat dilihat sebagai kasus khusus dari teorema sumbu pisah.) Yaitu, jika Anda memproyeksikan persegi panjang ke sumbu X dan Y Anda telah mengurangi masalah menjadi dua persimpangan garis-garis.

Hitung interval waktu di mana dua garis pada satu sumbu berpotongan (misalnya mulai pada waktu (pemisahan saat ini benda / relatif mendekati kecepatan benda)), dan melakukan hal yang sama untuk sumbu lainnya. Jika interval waktu tersebut tumpang tindih, maka waktu paling awal dalam tumpang tindih adalah waktu tabrakan.

Saya tidak berpikir ada cara mudah untuk menghitung tumbukan poligon dengan lebih banyak sisi daripada persegi panjang. Saya akan memecahnya menjadi bentuk primitif seperti garis dan kotak:

function objectsWillCollide(object1,object2) {
    var lineA, lineB, lineC, lineD;
    //get projected paths of objects and store them in the 'line' variables

    var AC = lineCollision(lineA,lineC);
    var AD = lineCollision(lineA,lineD);
    var BC = lineCollision(lineB,lineC);
    var BD = lineCollision(lineB,lineD);
    var objectToObjectCollision = rectangleCollision(object1.getRectangle(), object2.getRectangle());

    return (AC || AD || BC || BD || objectToObjectCollision);
}

Perhatikan bagaimana saya mengabaikan keadaan awal dari setiap objek seperti yang seharusnya diperiksa selama perhitungan sebelumnya.

Teorema Sumbu Terpisah

Teorema Sumbu Terpisah mengatakan "Jika kita dapat menemukan sumbu di mana dua bentuk cembung tidak berpotongan maka dua bentuk tersebut tidak berpotongan" atau lebih praktis untuk IT:

"Dua bentuk cembung hanya berpotongan jika mereka berpotongan pada semua sumbu yang mungkin."

Untuk persegi panjang sejajar sumbu ada tepat 2 sumbu yang mungkin: x dan y. Tetapi teorema ini tidak terbatas pada persegi panjang, ia dapat diterapkan pada bentuk cembung apa saja dengan hanya menambahkan sumbu lain di mana bentuk tersebut dapat berpotongan. Untuk detail lebih lanjut tentang topik ini, lihat tutorial ini oleh pengembang N: http://www.metanetsoftware.com/technique/tutorialA.html#section1

Diimplementasikan seperti ini:

axes = [... possible axes ...];
collision = true;
for every index i of axes
{
  range1[i] = shape1.getRangeOnAxis(axes[i]);
  range2[i] = shape2.getRangeOnAxis(axes[i]);
  rangeIntersection[i] = range1[i].intersectionWith(range2[i]);
  if(rangeIntersection[i].length() <= 0)
  {
    collision = false;
    break;
  }
}

Sumbu dapat direpresentasikan sebagai vektor yang dinormalisasi.

Rentang adalah garis 1-Dimensi. Awal harus ditetapkan ke titik proyeksi terkecil, ujung ke titik proyeksi terbesar.

Menerapkannya ke Rectangle "sweeped"

Segi enam dalam pertanyaan dihasilkan dengan "menyapu" AABB objek. Menyapu menambahkan tepat satu sumbu tabrakan yang mungkin untuk bentuk apa pun: vektor gerakan.

shape1 = sweep(originalShape1, movementVectorOfShape1);
shape2 = sweep(originalShape2, movementVectorOfShape2);

axes[0] = vector2f(1.0, 0.0); // X-Axis
axes[1] = vector2f(0.0, 1.0); // Y-Axis
axes[2] = movementVectorOfShape1.normalized();
axes[3] = movementVectorOfShape2.normalized();

Sejauh ini baik-baik saja, sekarang kita sudah dapat memeriksa apakah dua segi enam berpotongan. Tapi itu menjadi lebih baik.

Solusi ini akan berfungsi untuk segala bentuk cembung (misalnya segitiga) dan segala bentuk cembung yang disapu (misalnya octagons yang di-sweep). Namun, semakin kompleks bentuknya, semakin tidak efektif.

Bonus: Di mana keajaiban terjadi.

Seperti yang saya katakan, satu-satunya kapak tambahan adalah vektor pergerakan. Pergerakan waktu dikalikan dengan kecepatan, jadi dalam arti mereka bukan hanya sumbu ruang, mereka adalah sumbu ruang-waktu.

Ini berarti kita dapat memperoleh waktu di mana tabrakan bisa terjadi dari dua sumbu ini. Untuk ini kita perlu menemukan persimpangan antara dua persimpangan pada sumbu gerakan. Sebelum kita dapat melakukan ini, kita perlu menormalkan kedua rentang, sehingga kita dapat benar-benar membandingkannya.

shapeRange1 = originalShape1.getRangeOnAxis(axes[2]);
shapeRange2 = originalShape2.getRangeOnAxis(axes[3]);
// Project them on a scale from 0-1 so we can compare the time ranges
timeFrame1 = (rangeIntersection[2] - shapeRange1.center())/movementVectorOfShape1.project(axes[2]);
timeFrame2 = (rangeIntersection[3] - shapeRange2.center())/movementVectorOfShape2.project(axes[3]);
timeIntersection = timeFrame1.intersectionWith(timeFrame2);

Ketika saya mengajukan pertanyaan ini, saya agak sudah menerima kompromi bahwa akan ada beberapa kesalahan positif yang jarang terjadi dengan metode ini. Tapi saya salah, dengan memeriksa persimpangan waktu ini kita dapat menguji apakah tabrakan "benar-benar" terjadi dan kita dapat mengurutkannya dengan positif:

if(collision)
{
  [... timeIntersection = see above ...]
  if(timeIntersection.length() <= 0)
    collision = false;
  else
    collisionTime = timeIntersection.start; // 0: Start of the frame, 1: End of the frame
}

Jika Anda melihat ada kesalahan dalam contoh kode beri tahu saya, saya belum menerapkannya dan dengan demikian tidak dapat mengujinya.

Selama area sapuan keduanya tertutup (tidak ada celah di batas yang dibentuk oleh garis-tepi), berikut ini akan bekerja (cukup kurangi uji tabrakan Anda menjadi garis-garis dan titik-rect / point-tri):

1. Apakah ujung-ujungnya menyentuh? (tabrakan garis-garis) Periksa apakah ada garis tepi area yang disapu memotong dengan garis tepi dari area sapuan lainnya. Setiap area sapuan memiliki 6 sisi.

2. Apakah yang kecil di dalam yang besar? (Gunakan sumbu yang disejajarkan (point-rect & point-tri)) Ubah orientasi (rotate) area yang disapu sehingga yang lebih besar sejajar sumbu dan uji apakah yang lebih kecil adalah internal (dengan menguji apakah ada titik sudut ( harus semua atau tidak ada) berada di dalam area sapuan sumbu-sejajar). Hal ini dilakukan dengan menguraikan hex Anda menjadi tris dan rect.

Tes mana yang Anda lakukan pertama tergantung pada kemungkinan masing-masing (lakukan yang paling umum terjadi terlebih dahulu).

Anda mungkin menemukan lebih mudah untuk menggunakan lingkaran sapuan sapuan (kapsul daripada hex) karena lebih mudah untuk membaginya menjadi dua setengah lingkaran dan kotak ketika itu disejajarkan dengan sumbu. ..Aku akan membiarkanmu menggambar solusinya