Apakah mesin fisika dapat mengurangi kerumitan itu, misalnya dengan mengelompokkan objek yang berdekatan dan memeriksa tabrakan di dalam grup ini dan bukan terhadap semua objek? (misalnya, objek jauh dapat dihapus dari grup dengan melihat kecepatan dan jaraknya dari objek lain).
Jika tidak, apakah itu membuat tabrakan sepele untuk bola (dalam 3d) atau disk (dalam 2d)? Haruskah saya membuat loop ganda, atau membuat array pasangan?
EDIT: Untuk mesin fisika seperti peluru dan box2d, apakah deteksi tabrakan masih O (N ^ 2)?
Jawaban:
Divisi spasial selalu O (N ^ 2) dalam kasus terburuk dan itulah kompleksitas di bidang informatika.
Namun ada algoritma yang bekerja dalam waktu linier O (N) . Semuanya didasarkan pada semacam garis sapu.
Pada dasarnya Anda harus memiliki objek Anda diurutkan berdasarkan satu koordinat. Katakanlah X. Jika Anda melakukan pengurutan setiap kali sebelum deteksi tabrakan, kompleksitasnya adalah O (N * logN). Caranya adalah dengan menyortir hanya ketika Anda menambahkan objek ke adegan dan kemudian ketika sesuatu dalam adegan berubah. Menyortir setelah gerakan tidak sepele. Lihat kertas tertaut di bawah ini untuk algoritma yang bergerak dan masih bekerja dalam waktu linier.
Kemudian Anda menyapu dari kiri ke kanan. Setiap kali garis sapuan Anda melewati awal suatu objek, Anda memasukkannya ke dalam daftar sementara. Setiap kali garis sapuan Anda keluar dari objek, Anda mengeluarkannya dari daftar. Anda menganggap tabrakan hanya di dalam daftar sementara ini.
Garis sapu naif adalah O (N ^ 2) dalam kasus terburuk juga (Anda membuat semua objek span seluruh peta dari kiri ke kanan), tetapi Anda dapat membuatnya O (N) dengan membuatnya lebih pintar (lihat tautan di bawah). Algoritma yang sangat bagus akan sangat kompleks.
Ini adalah diagram sederhana cara kerja garis sapu:
Garis menyapu dari kiri ke kanan. Objek diurutkan berdasarkan koordinat X.
Algoritma seperti ini memiliki kompleksitas O (C * N) = O (N).
Sumber: Dua tahun kursus geometri komputasi.
Dalam deteksi tabrakan ini biasanya disebut Sapu dan Prune , tetapi keluarga garis algortitme berguna dalam banyak bidang lainnya.
Bacaan lebih lanjut yang direkomendasikan yang saya yakini berada di luar cakupan pertanyaan ini, namun tetap menarik: Metode Sapu dan Pemangkasan Skala Besar yang Efisien dengan Penyisipan dan Penghapusan AABB - Makalah ini menyajikan algoritme Sapu dan Pemangkas yang ditingkatkan yang menggunakan kotak-kotak yang selaras-sumbu (AABB ) dengan penyortiran yang memperhitungkan pergerakan akun. Algoritma yang disajikan dalam makalah ini bekerja dalam waktu linier.
Sekarang perhatikan bahwa ini adalah algoritma terbaik dalam teori . Itu tidak berarti bahwa itu digunakan. Dalam praktiknya, algoritma O (N ^ 2) dengan pembagian spasial akan memiliki kecepatan kinerja yang lebih baik dalam kasus khas (dekat dengan O (N)) dan beberapa persyaratan tambahan untuk memori. Ini karena konstanta C dalam O (C * N) bisa sangat tinggi! Karena kita biasanya memiliki cukup memori dan kasus-kasus tertentu memiliki objek tersebar merata di ruang angkasa - algoritma tersebut akan melakukan LEBIH BAIK. Tapi O (N) adalah jawaban untuk pertanyaan awal.
sumber
Tidak. Deteksi tabrakan tidak selalu O (N ^ 2).
Misalnya, kita memiliki ruang 100x100 dengan objek dengan ukuran 10x10. Kita bisa membagi ruang ini dalam sel 10x10 dengan kisi.
Setiap objek dapat dalam hingga 4 sel kisi (bisa pas di blok atau berada di antara sel). Kita bisa menyimpan daftar objek di setiap sel.
Kita hanya perlu memeriksa tabrakan di sel-sel itu. Jika ada jumlah maksimum objek per sel kotak (katakanlah, tidak pernah ada lebih dari 4 objek di blok yang sama), maka deteksi tumbukan untuk setiap objek adalah O (1) dan deteksi tumbukan untuk semua objek adalah O (N).
Ini bukan satu-satunya cara untuk menghindari kompleksitas O (N ^ 2). Ada metode lain, lebih memadai untuk kasus penggunaan lainnya - sering menggunakan struktur data berbasis pohon.
Algoritma yang saya jelaskan adalah satu jenis partisi Ruang , tetapi ada algoritma ruang partisi lainnya. Lihat Jenis struktur data partisi ruang untuk beberapa algoritma yang menghindari kompleksitas temporal O (N ^ 2).
Mekanisme dukungan Box2D dan Bullet untuk mengurangi jumlah pasangan yang diperiksa.
Dari manual , bagian 4.15:
Dari the Bullet Wiki :
sumber
O (N ^ 2) merujuk pada fakta bahwa jika Anda memiliki N objek, mencari tahu apa yang bertabrakan dengan apa, kasus terburuk , perhitungan tumbukan N ^ 2. Katakanlah Anda memiliki 3 objek. Untuk menemukan "siapa yang memukul siapa", Anda harus menemukan:
Itu 6 cek untuk tabrakan, atau N * (N-1) cek. Dalam analisis asimptotik kami akan memperluas polinomial dan perkiraan sebagai O (N ^ 2). Jika Anda memiliki 100 objek, maka itu akan menjadi 100 * 99, yang cukup dekat ke 100 * 100.
Jadi, jika Anda mempartisi ruang menggunakan octree misalnya, jumlah rata - rata perbandingan antara badan berkurang. Jika mungkin bagi semua objek untuk berkumpul ke area yang sangat kecil (katakanlah jika Anda melakukan semacam simulasi aliran partikel, di mana partikel dapat berkumpul di area yang sama) maka O (N ^ 2) masih dapat terjadi pada poin dalam simulasi (pada titik mana Anda akan melihat perlambatan).
Jadi, seluruh poin O (N ^ 2) ada karena sifat dari masing-masing tubuh memeriksa setiap tubuh lain di tempat kejadian. Itu hanya sifat perhitungannya. Banyak hal yang dapat membantu menjadikan ini lebih murah. Bahkan grafik adegan (misalnya mendeteksi antara objek di ruangan yang sama saja) akan mengurangi jumlah perhitungan tabrakan yang harus dilakukan secara signifikan, tetapi itu masih akan menjadi O (M ^ 2) (di mana M adalah jumlah objek di ruangan untuk dideteksi tabrakan terhadap). Volume ikatan bundar membuat pemeriksaan awal sangat cepat (
if( distance( myCenter, hisCenter ) > (myRadius+hisRadius) ) then MISS
), jadi meskipun deteksi tumbukan adalah O (N ^ 2), perhitungan bola terikat kemungkinan terjadi sangat cepat.sumber