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
"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.
Apa yang tersisa dengan Anda: Poin pada sumbu
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:
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:
Ini adalah luasannya. Mereka tumpang tindih.
Coba sisi kiri persegi panjang. Sekarang mereka tidak tumpang tindih di poros ini, karena itu TIDAK ADA INTERSEKSI.
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 ;
}
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).
sumber
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
sumber