Deteksi Tabrakan OBB vs OBB

20

Katakanlah Anda memiliki dua Bounding Box Objects yang masing-masing menyimpan simpul saat ini dari kotak dalam vektor dengan semua simpul objek diputar dan diterjemahkan relatif ke sumbu yang sama.

Berikut ini adalah gambar untuk menggambarkan masalah saya:

Bagaimana saya bisa bekerja jika dua OBB tumpang tindih tautan apa pun untuk membantu menjelaskan solusi untuk masalah ini akan diterima. Tidak ada yang terlalu berbelit-belit, tolong ...

Joshua Barnett
sumber

Jawaban:

16

OBB adalah lambung cembung. Convex Hull adalah bentuk 3D yang tidak memiliki "celah" di permukaannya. Setiap "benjolan" (titik) pada cembung cembung menjulur ke luar , tidak pernah ke dalam. Jika Anda mengiris pesawat melalui cembung cembung Anda akan mendapatkan (hanya satu) cembung poligon. Jika Anda berada di dalam lambung cembung dan menembakkan laser yang mengarah keluar, Anda hanya akan menembus permukaan lambung sekali (tidak pernah dua kali).

Tes Teorema Sumbu Pemisah dapat digunakan untuk mendeteksi tumbukan convex hulls. Tes SAT sederhana. Ia bekerja dalam 2D ​​dan 3D. Meskipun gambar di bawah ini dalam bentuk 2D, mereka dapat dengan mudah diterapkan ke 3D.

Konsep

Ini adalah konsep utama yang Anda gunakan dengan SAT:

  • Dua bentuk hanya berpotongan jika mereka tumpang tindih ketika "diproyeksikan" ke setiap sumbu normal dari kedua bentuk .

"Proyeksi" bentuk ke vektor 1D terlihat seperti ini (apa yang saya sebut "penghancuran")

Bentuk dengan verts merah, dan sumbu

masukkan deskripsi gambar di sini

"Memproyeksikan bentuk ke sumbu" berarti menjatuhkan tegak lurus dari setiap titik pada bentuk hanya untuk mendarat di sumbu. Anda dapat menganggap ini sebagai "menghancurkan" titik-titik dengan tangan yang mengumpulkan semuanya dan secara tegak lurus merobohkannya ke sumbu.

masukkan deskripsi gambar di sini

Apa yang tersisa dengan Anda: Poin pada sumbu

masukkan deskripsi gambar di sini

SAT mengatakan:

Agar 2 cembung lambung berpotongan, mereka harus tumpang tindih pada setiap sumbu (di mana setiap normal pada setiap bentuk dihitung sebagai sumbu yang harus kita periksa).

Ambil 2 bentuk ini:

masukkan deskripsi gambar di sini

Anda lihat mereka tidak berpotongan, jadi mari kita coba beberapa sumbu untuk menunjukkan jika tumpang tindih tidak terjadi.

Mencoba yang paling normal dari segi lima:

masukkan deskripsi gambar di sini

Ini adalah luasannya. Mereka tumpang tindih.

masukkan deskripsi gambar di sini

Coba sisi kiri persegi panjang. Sekarang mereka tidak tumpang tindih di poros ini, karena itu TIDAK ADA INTERSEKSI.

masukkan deskripsi gambar di sini

Algoritma:

Untuk setiap wajah normal pada kedua bentuk:

  • Temukan luasan minimum dan maksimum (nilai terbesar dan terkecil) dari proyeksi semua titik sudut vertex dari kedua bentuk ke sumbu itu
  • Jika tidak tumpang tindih, tidak ada persimpangan .

Dan itu benar-benar itu. Kode untuk membuat SAT berfungsi sangat singkat dan sederhana.

Berikut adalah beberapa kode yang menunjukkan cara melakukan proyeksi sumbu SAT:

void SATtest( const Vector3f& axis, const vector<Vector3f>& ptSet, float& minAlong, float& maxAlong )
{
  minAlong=HUGE, maxAlong=-HUGE;
  for( int i = 0 ; i < ptSet.size() ; i++ )
  {
    // just dot it to get the min/max along this axis.
    float dotVal = ptSet[i].dot( axis ) ;
    if( dotVal < minAlong )  minAlong=dotVal;
    if( dotVal > maxAlong )  maxAlong=dotVal;
  }
}

Kode panggilan:

// Shape1 and Shape2 must be CONVEX HULLS
bool intersects( Shape shape1, Shape shape2 )
{
  // Get the normals for one of the shapes,
  for( int i = 0 ; i < shape1.normals.size() ; i++ )
  {
    float shape1Min, shape1Max, shape2Min, shape2Max ;
    SATtest( normals[i], shape1.corners, shape1Min, shape1Max ) ;
    SATtest( normals[i], shape2.corners, shape2Min, shape2Max ) ;
    if( !overlaps( shape1Min, shape1Max, shape2Min, shape2Max ) )
    {
      return 0 ; // NO INTERSECTION
    }

    // otherwise, go on with the next test
  }

  // TEST SHAPE2.normals as well

  // if overlap occurred in ALL AXES, then they do intersect
  return 1 ;
}

bool overlaps( float min1, float max1, float min2, float max2 )
{
  return isBetweenOrdered( min2, min1, max1 ) || isBetweenOrdered( min1, min2, max2 ) ;
}

inline bool isBetweenOrdered( float val, float lowerBound, float upperBound ) {
  return lowerBound <= val && val <= upperBound ;
}
bobobobo
sumber
Hullinator mengimplementasikan tes SAT untuk convex hulls
bobobobo
penjelasan yang luar biasa! Terima kasih. Saya pikir Anda mungkin memiliki kesalahan ketik pada baris: "sehingga memungkinkan mencoba beberapa sumbu ke acara yang tumpang tindih tidak terjadi.", Karena Anda melanjutkan untuk memberikan contoh di mana mereka melakukan tumpang tindih. Terima kasih lagi!
Tidakkah Anda perlu melakukan tes juga untuk semua produk silang dari normals? Artikel ini geometrictools.com/Documentation/DynamicCollisionDetection.pdf mengatakan demikian.
iNFINITEi
Perlu disebutkan bahwa metode khusus SAT ini hanya berfungsi dalam 2D. Dalam 3D, Anda perlu mendapatkan lebih dari sekadar norma setiap wajah. Namun, setelah Anda memiliki normals yang tepat, sisa proses (proyek, bandingkan) persis sama.
Dana Gugatan Monica
Benar-benar sulit untuk mengetahui dari gambar 2D Anda arah panah mana yang akan bergerak.
WDUK
7

Anda pasti harus mencari Teorema Pemisah Sumbu . Ini untuk benda cembung. Ada aturan: "Jika dua objek cembung tidak berpotongan, maka ada bidang di mana proyeksi kedua objek ini tidak akan berpotongan".

Anda dapat menemukan beberapa contoh di wiki . Tapi ini sedikit lebih rumit daripada untuk kasus Anda.

Sesuatu yang lebih cocok untuk masalah Anda dapat ditemukan di sini (dua mobil bertabrakan).

zacharmarz
sumber
1

Lebih banyak artikel SAT .

Artikel terakhir di situs ini dilengkapi dengan kode lengkap, saya pikir itu dalam FLASH, saya tidak tahu, tapi saya punya 0 masalah mengkonversikannya menjadi C ++ ketika saya harus menggunakan SAT untuk pertama kalinya, seharusnya tidak sulit untuk lakukan hal yang sama untuk bahasa lain. Satu-satunya hal yang harus Anda tambahkan adalah menyimpan vektor perpindahan pada setiap perhitungan (jika itu terkecil, tentu saja, Anda akan memahami ini ketika Anda belajar tentang SAT), kode dalam tutorial ini tidak melakukannya, jadi Anda berakhir dengan vektor terhitung terakhir.

http://rocketmandevelopment.com/tag/separation-axis-theorem/

Bagus, tutorial N-Game lama. Teori SAT terbaik di web.

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

dreta
sumber
Sangat menjengkelkan sehingga tidak ada yang memposting sumber yang berfungsi penuh dengan semua kelas yang diperlukan. Saya porting kodenya ke dalam demo saya sendiri tetapi tidak berhasil. :( Ini adalah proyek saya sejauh ini jika ada yang bisa membantu saya men-debug-nya, itu akan bagus. Tautan
Joshua Barnett
apa maksudmu itu tidak berhasil? perhatikan bagaimana Anda menyimpan simpul Anda, pada gambar yang Anda miliki dalam sistem koordinat kartesius, dalam tutorial ia menyimpan simpul sebagai vektor relatif terhadap centroid (yang harus Anda lakukan adalah mengurangi centroid dari simpul Anda sendiri atau hapus garis-garis di mana ia memodifikasi simpulnya sendiri), fungsi-fungsi seperti titik produk yang dapat Anda buat sendiri, Anda tidak perlu panduan untuk itu, sisanya harus lurus ke depan, itu bukan bahan salin, pelajari SAT sebelum mencoba menerapkannya
dreta
Beginilah cara saya mengimplementasikannya: SAT.as , Shape2D.as , Apa yang Anda maksud dengan centroid? Bagian tengah poligon seperti (x, y)?
Joshua Barnett
Saat ini saya memiliki fungsi getOBB () yang mengembalikan simpul seperti yang dijelaskan dalam gambar asli saya. Ini dihitung dari Vector <b2Vec2> yang berisi simpul-simpul bentuk, variabel sudut, dan variabel posisi.
Joshua Barnett
ya, pusat, cara orang ini membuat poligonnya adalah dengan memberikan offset dari pusat, idk AS3, tetapi dari apa yang saya lihat Anda memproyeksikan simpul Anda sebagaimana adanya, ketika menghitung produk titik mencoba untuk mengurangi centroid dari simpul (vektor subraksi) ), di samping ini Anda tidak memeriksa vektor pemisahan mana yang masih terkecil, Anda hanya menyimpan yang terakhir dihitung
dreta