Deteksi tabrakan segi enam untuk objek yang bergerak cepat?

39

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.

Gagal Tabrakan BoundingBox

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.

Hexagon Collision Win

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.

Spesifikasi Segi Enam

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.

API-Beast
sumber
untuk (garis dalam A) untuk (garis dalam B) jika (garis bertabrakan) tabrakan - kecuali yang tidak mencakup A dalam B atau B dalam kasus A. Hm =)
Jari Komppa
4
Apakah Anda berkomitmen pada kotak? Kotak yang Anda gambar dapat diwakili oleh lingkaran dengan kehilangan akurasi minimal tetapi tabrakan yang relatif mudah. Mencari deteksi tabrakan lingkaran menyapu. Jika rasio panjang / lebar Anda menjauh dari 1, ini kurang menarik.
Steve H
@SteveH Saya mencari solusi yang paling fleksibel, sehingga rasio panjang / lebar adalah masalah yang agak besar.
API-Beast
1
Anda harus menyadari bahwa hanya karena heksagon bersilangan tidak berarti terjadi tabrakan. Bahkan asalkan Anda bisa tahu tanpa kesalahan apakah mereka berpotongan, Anda masih harus melakukan pekerjaan untuk menentukan apakah ada tabrakan, dan, jelas, di mana dan kapan itu terjadi. Jadi Anda belum bisa melompat ke pertanyaan bonus Anda.
jrsala
2
Saya belum pernah mencoba ini sebelumnya tetapi tampaknya bukannya segi enam dalam ruang 2d, Anda dapat menganggap gerakan dalam 2d sebagai volume dalam ruang 3d di mana satu sumbu adalah waktu. Anda kemudian memotong dua polyhedra 3d dengan koordinat (x, y, t). Jika dua benda padat berpotongan maka Anda ingin menemukan nilai t minimum. Anda mungkin menyederhanakan sedikit dengan mengubah semua koordinat B menjadi dalam kerangka referensi A. Saya belum menerapkan ini tetapi di situlah saya mulai.
amitp

Jawaban:

34

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.

Langkah 1

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:

Langkah 2

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:

langkah 3

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

sam hocevar
sumber
4
Tampak seperti pendekatan yang agak menarik, namun, saya belum menangkapnya 100%, apa yang terjadi ketika objek sangat kecil dan bergerak di antara dua garis? i.imgur.com/hRolvAF.png
API-Beast
-1: Metode ini tidak memungkinkan Anda untuk memastikan tabrakan terjadi. Ini hanya memungkinkan Anda untuk memastikan itu tidak terjadi, dalam kasus di mana segmen dan volume yang diekstrusi tidak berpotongan. Tetapi sangat mungkin bahwa mereka berpotongan dan belum ada tabrakan. Apa yang salah adalah bagian "Sekarang Anda dapat menggunakan persimpangan segmen-sederhana untuk memutuskan di mana tabrakan terjadi".
jrsala
2
@madshogo Anda benar. Saya berasumsi bahwa catatan waktu cukup kecil dibandingkan dengan ukuran objek bahwa ini tidak akan menjadi masalah, tapi tentu saja tidak terlalu kuat dalam kasus umum. Saya akan mencari cara memperbaikinya.
sam hocevar
@ SamHocevar Jika Anda bisa merevisi jawaban yang akan bagus.
API-Beast
1
@LuisAlves ya dan tidak ... semua logika berfungsi, tetapi Anda harus mengganti vB-vAdengan di g(t)-f(t)mana fdan posisi gA dan B dari waktu ke waktu. Karena ini bukan lagi garis lurus, Anda harus menyelesaikan masalah kotak - kurva persimpangan parametrik.
sam hocevar
17

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 ).

Gerakan relatif

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;

}
jrsala
sumber
2

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.

Kevin Reid
sumber
3
Anda lupa sketsa Anda.
MichaelHouse
2
@ Byte56 Tidak, maksud saya ini adalah sketsa algoritma, bahkan pseudocode.
Kevin Reid
Oh begitu. Kesalahanku.
MichaelHouse
Ini sebenarnya metode yang paling mudah. Saya menambahkan kode yang sesuai untuk mengimplementasikannya.
Pasha
1

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);
}

ilustrasi jalur dan kondisi akhir objek

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

Eazimmerman
sumber
3
Masalah dengan ini adalah bahwa jika ukuran objek jauh berbeda, objek yang lebih kecil dapat bergerak di dalam jalur objek besar tanpa memicu tabrakan.
API-Beast
0

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.

API-Beast
sumber
1
Selamat atas penemuan solusi Anda! Tapi seperti yang saya katakan sebelumnya: hanya karena segi enam bersilangan tidak berarti akan ada tabrakan. Anda dapat menggunakan metode Anda untuk menghitung waktu tabrakan yang Anda inginkan, jika tidak ada tabrakan, itu tidak terlalu berguna. Kedua, Anda dapat menggunakan kecepatan relatif sehingga hanya perlu menghitung 1 volume sapuan, dan untuk menyederhanakan perhitungan saat menggunakan SAT. Akhirnya, saya hanya punya ide kasar tentang bagaimana trik "waktu persimpangan" Anda bekerja, karena mungkin Anda membuat indeks Anda tercampur, mengingat shapeRange1 == shapeRange2dengan kode Anda, bukan?
jrsala
@madshogo Seharusnya lebih masuk akal sekarang.
API-Beast
Saya masih tidak mengerti cara kerja normalisasi rentang, tetapi saya rasa itu karena saya perlu gambar. Saya harap ini berhasil untuk Anda.
jrsala
-2

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

akson
sumber
Tidak berfungsi jika salah satu persegi panjang benar-benar kecil dan bergerak dalam ruang antara dua garis tepi.
jrsala
@madshogo Saya baru saja menambahkan respons saya. Seharusnya menjadi solusi yang lengkap sekarang.
akson
1
"Gunakan bentuk sumbu selaras (titik-persegi & titik-tri)": Bagaimana Anda bahkan menyelaraskan segitiga atau "titik-segitiga" (apa pun artinya) dengan sumbu? "sehingga yang lebih besar sejajar": bagaimana Anda bisa tahu mana yang lebih besar dari yang lain? Apakah Anda menghitung area mereka? "Ini selesai menguraikan hex Anda menjadi tris dan rect.": Hex yang mana? Ada dua. "(atau hapus tanggapan ini jika Anda ingin saya menggambarkannya untuk Anda)": Apakah Anda serius ??
jrsala
"Bagaimana kamu bahkan menyelaraskan sebuah segitiga dengan sumbu?" A: Sejajarkan jalur objek membuat area tersapu. Pilih tepi dan gunakan trigonometri. "Bagaimana kamu bisa tahu mana yang lebih besar dari yang lain?" A: Sebagai contoh, gunakan jarak antara dua titik yang berlawanan secara diagonal dari rect (tengah hex). "hex yang mana?" A: Yang besar.
axon