Bagaimana cara melakukan deteksi tabrakan dalam ruang 3D?

8

Saya harus menulis, apa yang bisa disimpulkan, game 3D lengkap dari awal semester ini. Sampai sekarang saya hanya memprogram game 2D di waktu senggang saya, transisi sepertinya tidak sulit, permainannya sederhana. Satu-satunya masalah yang saya miliki adalah deteksi tabrakan. Satu-satunya hal yang dapat saya temukan adalah AABB, bola-bola pembatas atau rekomendasi dari berbagai mesin fisika. Saya harus memprogram kapal selam yang akan bergerak bebas di dalam sistem gua, AFAIK Saya tidak bisa menggunakan perpustakaan fisika, jadi tidak ada yang di atas menyelesaikan masalah saya.

Sampai sekarang saya menggunakan SAT untuk mendeteksi tabrakan saya. Apakah ada yang mirip, algoritma yang hebat, tetapi dibuat untuk tabrakan 3D? Saya tidak berbicara tentang octrees, atau optimasi lainnya, saya sedang berbicara tentang deteksi tabrakan langsung satu set poligon 3D dengan set poligon 3D lainnya. Saya berpikir tentang menggunakan SAT dua kali, memproyeksikan mesh dari atas dan samping, tetapi kemudian tampaknya sangat sulit untuk bahkan membagi ruang 3D menjadi bentuk cembung. Juga sepertinya penghitungan yang terlalu banyak bahkan dengan octrees.

Bagaimana cara profesional melakukannya? Bisakah seseorang menjelaskan.

dreta
sumber
1
Tidaklah sulit untuk membagi ruang 3D menjadi geometri cembung. Misalnya menggunakan BSP-Tree (partisi ruang biner).
Maik Semder

Jawaban:

5

GJK bekerja pada bentuk cembung, saya mungkin juga menggunakan SAT. Saya telah menemukan informasi yang saya inginkan. Berikut ini beberapa contohnya:

Singkatnya, saya akan melakukan pemeriksaan tabrakan bola atau elipsoid terhadap beberapa segitiga yang membentuk mesh tabrakan. Sepertinya itu yang dilakukan dan itu adalah informasi yang saya minta, kecuali ada yang bisa memberi tahu saya berbeda.

dreta
sumber
1

Hei saya menulis tentang GJK dalam 3D di sini. SAT lebih lambat daripada GJK http://in2gpu.com/2014/05/18/gjk-algorithm-3d/

Sergiu Craitoiu
sumber
Jawaban hanya tautan cenderung agak buruk, karena mereka menjadi tidak valid segera setelah dipindah dan mereka tidak mencari dengan baik. Pertimbangkan memperluas jawaban ini untuk memasukkan beberapa informasi tentang perincian solusi yang Anda coba presentasikan.
oh, ok saya pikir tidak apa
Sergiu Craitoiu
0

Nah, jika itu bukan sesuatu yang sangat sangat menuntut dan canggih, Anda bisa mulai dengan menerapkan algoritma pendeteksian tabrakan Gilbert . Itu dapat dibuat menjadi cukup cepat dan itu akan cepat, asalkan geometri tabrakan Anda tidak begitu detail (dan tidak perlu!). Begitulah cara bahkan beberapa simulator melakukan trik .. apa pun yang lebih rumit akan, mungkin, perlu lebih banyak usaha dipertimbangkan.

teko teh
sumber