Algoritme GJK: Cara Menyelesaikan Hal Sederhana dengan Aneh dan Indah

 (computerwebsite.net)
2 poin oleh GN⁺ 2024-06-13 | 1 komentar | Bagikan ke WhatsApp
  • Algoritme GJK adalah metode untuk memeriksa apakah dua bentuk saling bertumpang tindih
  • Untuk memeriksa apakah bentuk A dan bentuk B bertumpang tindih, cukup periksa apakah ada titik dari kedua bentuk yang saling tumpang tindih

Selisih Minkowski

  • Membuat himpunan baru dengan mengurangkan semua titik dari dua bentuk.
  • Jika himpunan baru ini mencakup titik asal, itu berarti kedua bentuk bertumpang tindih.
  • Ini disebut selisih Minkowski.

Ide dasar algoritme

  • Memeriksa apakah selisih Minkowski dari A dan B mencakup titik asal.
  • Jika selisih tersebut mencakup titik asal, kedua bentuk bertumpang tindih.

Langkah-langkah algoritme

  1. Inisialisasi: Tetapkan vektor arah sembarang d, lalu cari titik pertama p.
  2. Mencari titik: Hitung hasil kali titik dari d dan p; jika positif lanjutkan, jika negatif hentikan.
  3. Menambahkan titik baru: Dari p, cari titik baru ke arah titik asal.
  4. Penyederhanaan: Tambahkan titik baru berdasarkan dua titik pertama untuk melakukan simplifikasi.
  5. Memeriksa apakah mencakup titik asal: Periksa apakah bentuk yang telah disederhanakan mencakup titik asal.
  6. Ulangi: Ulangi sampai bentuk mencakup titik asal atau sampai ditemukan bukti bahwa titik asal tidak tercakup.

Opini GN⁺

  • Hal yang menarik: Algoritme GJK adalah contoh yang baik tentang bagaimana masalah kompleks dapat diselesaikan dengan transformasi matematis yang sederhana.
  • Mengapa ini membantu: Sangat berguna dalam grafika real-time seperti deteksi tabrakan.
  • Sudut pandang kritis: Implementasi algoritme bisa rumit dan membutuhkan pemahaman yang tepat.
  • Teknologi terkait: Algoritme deteksi tabrakan lainnya mencakup SAT (Separating Axis Theorem) dan sebagainya.
  • Hal yang perlu dipertimbangkan: Saat menggunakan algoritme GJK, kompleksitas bentuk dan biaya komputasi perlu dipertimbangkan.

Bacaan terkait

1 komentar

 
GN⁺ 2024-06-13
Komentar Hacker News

  • Pada 1990-an, saya hampir setahun kerepotan karena GJK
    Ini berguna untuk deteksi tumbukan 3D, dan juga bisa dipakai sebagai algoritme titik terdekat. Ide dasarnya mudah dipahami. Saat ada dua benda padat cembung, ambil masing-masing satu titik sembarang dari tiap benda, hitung jarak di antara dua titik itu, lalu coba bergerak dari titik saat ini di sepanjang tiap rusuk untuk memperbaiki jaraknya dan ulangi proses memilih titik terdekat baru
    Namun jika titik terdekat bukan lagi sebuah simpul, pendekatan ini rusak, dan di sinilah konsep simplex dibutuhkan. Kombinasi titik terdekat terbagi menjadi simpul-simpul, simpul-rusuk, simpul-bidang, rusuk-rusuk, rusuk-bidang (tidak ada solusi unik), dan bidang-bidang (tidak ada solusi unik), dan penanganan simplex pada dasarnya lebih dekat ke analisis kasus-kasus ini
    Dalam praktiknya, banyak masalah muncul. Dalam engine fisika, objek sering stabil dalam keadaan kontak bidang-bidang, dan model tumbukan satu titik dapat menimbulkan osilasi atau gerakan yang salah. Selain itu, ketika posisi berkonvergensi ke kontak bidang-bidang, GJK harus menangani selisih kecil di antara nilai-nilai besar, sehingga bisa sepenuhnya kehilangan digit signifikan floating point. Kondisi terminasi juga dapat menyebabkan loop tak berhingga
    Secara teori elegan, tetapi dalam praktiknya ini adalah masalah analisis numerik yang sulit. Meski begitu, ini mungkin pendekatan tercepat untuk masalah ini. Pada kasus umum kompleksitasnya O(log N), dan jika memakai solusi terakhir sebagai titik awal pada situasi yang paling dekat dengan posisi sebelumnya, bisa mendekati O(1)
    Mendiang Prof. Steven Cameron dari Oxford melakukan banyak pekerjaan agar GJK berjalan dengan benar, dan pada akhir 1990-an GJK digunakan dalam "Falling Bodies", sistem ragdoll 3D komersial pertama

    • Setelah menemukan kontak, hampir pasti kita harus melakukan sesuatu dengannya, dan untuk sebagian besar pemrosesan yang berguna, kita perlu mengetahui informasi penetrasi yang sebenarnya
      Mendapatkan itu lebih buruk secara numerik. Mulai dari simplex yang dibuat GJK, lalu memperluasnya ke luar, dan dalam prosesnya harus melakukan triangulasi. Mengimplementasikannya dengan performa baik benar-benar mendekati mimpi buruk
    • https://www.youtube.com/watch?v=5lHqEwk7YHs
      Saya penasaran apakah patennya sudah kedaluwarsa, dan apakah ada niat untuk merilis kodenya. Secara historis itu bermakna, dan sepertinya akan menjadi bahan menarik seperti membaca source Doom

  • Saya tidak menemukan tulisan yang menjelaskan algoritme deteksi tumbukan GJK secara intuitif, jadi saya meluangkan waktu sore untuk merangkumnya sendiri
    Kalau ada cara untuk membuatnya lebih jelas dan efisien, saya akan senang diberi tahu. Tentu saja, mohon maklumi bahwa ini tulisan seorang siswa kelas 2 SMA yang menjelaskan materi matematika

    • Tulisannya sangat jelas. Kalau terus melakukan hal seperti ini, terlihat ada bakat yang suatu hari bisa menghasilkan buku teks yang bagus
      Sudah bagus, tetapi agar lebih sempurna mungkin bisa ditambahkan beberapa hal. Penjelasan singkat tentang kompleksitas waktu pada kasus terburuk, bagian terpisah yang membahas kondisi terminasi, dan pseudocode di sela-sela penjelasan akan bagus
      Cara menjelaskan dari sudut pandang matematis seperti sekarang cocok dan layak dipertahankan. Namun setelah tiap langkah, akan lebih baik jika menambahkan pseudocode singkat yang memuat sejauh mana algoritme sudah berjalan, sambil mendefinisikan fungsi bantu seperti S(•)
      Tulisan tentang model tersembunyi OpenAI juga bagus. Waktu yang dihabiskan untuk mencari tahu apa lagi yang dibuat seseorang yang menghasilkan karya mengesankan hampir selalu berharga
    • Sebagai matematikawan, kritik terburuk yang bisa saya berikan hanyalah bahwa jika ditujukan untuk pembaca matematika, saya mungkin akan menulis beberapa ungkapan sedikit berbeda
      Judulnya seharusnya "as simply as possible". Saya tidak tahu algoritme GJK sebelumnya, tetapi kalau saat ini sedang mengajar Calculus III, saya mungkin akan mencari cara memasukkan materi ini ke kelas. Penjelasannya memang sebagus itu
    • Saya penasaran apakah algoritme ini dijamin berhenti
      Pada contoh persegi panjang bersudut membulat yang halus di akhir tulisan, saya tidak tahu apa yang mencegahnya hanya makin mendekati jawaban tanpa benar-benar mencapainya. Tentu saja, dalam komputasi nyata saya tahu tidak ada alasan untuk terus berjalan setelah batas presisi praktis
    • Tiga himpunan A, B, A-B pada gambar kedua membingungkan
      Awalnya saya mengartikannya sebagai A dan B diberi suatu transformasi sehingga menghasilkan bentuk A-B. Setelah membaca ulang beberapa kali, tampaknya A-B bukan dua himpunan di kiri, melainkan menunjukkan irisan A dan B yang lain, dan yang penting adalah irisan itu tumpang tindih dengan titik asal atau 0,0. Saya penasaran apakah itu benar

  • Presentasi video yang membahas algoritme yang sama: https://www.youtube.com/watch?v=ajv46BSqcK4

  • Tulisannya sangat jelas dan menarik
    Cara lain untuk memeriksa apakah dua himpunan cembung berpotongan adalah dengan menyelesaikan masalah optimisasi cembung yang meminimalkan norma selisih antara titik yang termasuk dalam himpunan cembung pertama dan titik yang termasuk dalam himpunan cembung kedua. Jika nilai optimalnya 0, kedua himpunan berpotongan
    Akan menarik membandingkan algoritme GJK dengan optimisasi cembung. Saya tidak tahu mana yang lebih menguntungkan

    • Pertanyaan menarik. Jika tumpang tindihnya cukup besar, metode titik interior sepertinya bisa berhenti lebih cepat. Kondisi terminasi dini yang cerdas juga tampaknya bisa ditambahkan

  • Gambar pertama menunjukkan perpotongan bentuk non-cembung, sementara fakta bahwa algoritme ini hanya bekerja pada bentuk cembung baru muncul jauh setelahnya, jadi ini bisa sedikit menyesatkan

    • Dijelaskan bahwa bentuk non-cembung ditangani dengan membaginya menjadi bentuk-bentuk cembung

  • Saya sudah cukup lama memakai fungsi Minkowski di openSCAD, dan senang akhirnya mengetahui apa sebenarnya itu

  • Karena ternyata mendapat perhatian lebih besar dari yang diperkirakan, rasanya perlu saya katakan bahwa situs pribadi itu pada dasarnya adalah kumpulan inside joke yang rumit
    Kalau ingin menghubungi saya atau ada sesuatu yang perlu dilakukan, beri tahu lewat balasan

    • Kalau tertarik membimbing proyek riset, silakan kirim email: bersub@cmu.edu
    • Situsnya bagus dan kamu tampak seperti orang yang keren. Semoga terus membuat hal-hal keren

  • Hampir 10 tahun lalu saya mengimplementasikan GJK berdasarkan penjelasan Casey yang luar biasa: https://www.youtube.com/watch?v=Qupqu1xe7Io

  • Saya pernah menulis artikel terkait geometri Minkowski: https://nickp.svbtle.com/asteroid-intersections