GJK algoritması: basit bir işi tuhaf ve güzel bir şekilde çözmenin yolu

 (computerwebsite.net)
2 puan yazan GN⁺ 2024-06-13 | 1 yorum | WhatsApp'ta paylaş
  • GJK algoritması, iki şeklin üst üste binip binmediğini kontrol etmenin bir yoludur
  • Şekil A ile şekil B'nin çakışıp çakışmadığını kontrol etmek için, iki şeklin noktalarından en az birinin çakışıp çakışmadığını kontrol etmek yeterlidir

Minkowski farkı

  • İki şeklin tüm noktaları birbirinden çıkarılarak yeni bir küme oluşturulur.
  • Bu yeni küme orijini içeriyorsa, bu iki şeklin çakıştığı anlamına gelir.
  • Buna Minkowski farkı denir.

Algoritmanın temel fikri

  • A ile B'nin Minkowski farkının orijini içerip içermediği kontrol edilir.
  • Fark kümesi orijini içeriyorsa şekiller çakışır.

Algoritma adımları

  1. Başlatma: Rastgele bir yön vektörü d belirlenir ve ilk nokta p bulunur.
  2. Nokta bulma: d ile p arasındaki iç çarpım hesaplanır; sonuç pozitifse devam edilir, negatifse sonlandırılır.
  3. Yeni nokta ekleme: p'den orijin yönüne doğru yeni bir nokta bulunur.
  4. Sadeleştirme: İlk iki nokta temel alınarak yeni nokta eklenir ve sadeleştirme yapılır.
  5. Orijini içerip içermediğini kontrol etme: Sadeleştirilmiş şeklin orijini içerip içermediği kontrol edilir.
  6. Tekrarlama: Orijin içerilene kadar veya içerilmediğine dair bir kanıt bulunana kadar işlem tekrarlanır.

GN⁺ görüşü

  • İlginç nokta: GJK algoritması, karmaşık bir problemi basit bir matematiksel dönüşümle çözmenin iyi bir örneğidir.
  • Neden faydalı: Çarpışma algılama gibi gerçek zamanlı grafiklerde çok yararlı şekilde kullanılır.
  • Eleştirel bakış: Algoritmanın uygulanması karmaşık olabilir ve doğru anlaşılması gerekir.
  • İlgili teknolojiler: Diğer çarpışma algılama algoritmaları arasında SAT(Separating Axis Theorem) gibi yöntemler vardır.
  • Dikkate alınacaklar: GJK algoritması kullanılırken şekillerin karmaşıklığı ve hesaplama maliyeti göz önünde bulundurulmalıdır.

İlgili okumalar

1 yorum

 
GN⁺ 2024-06-13
Hacker News yorumları

  • 1990'larda GJK yüzünden neredeyse bir yıl uğraştım
    3D çarpışma algılamada kullanışlıdır ve en yakın nokta algoritması olarak da kullanılabilir. Temel fikri anlaması kolaydır. İki dışbükey cisim olduğunda, her cisimden rastgele birer nokta seçip iki nokta arasındaki mesafeyi bulursunuz; sonra mevcut noktadan her kenar boyunca hareket ederek mesafeyi iyileştirmeyi dener ve yeni en yakın noktayı seçersiniz, bunu tekrar edersiniz
    Ancak en yakın nokta artık bir köşe noktası değilse bu yöntem bozulur; işte burada simpleks (simplex) kavramı gerekir. En yakın nokta kombinasyonları köşe-köşe, köşe-kenar, köşe-yüzey, kenar-kenar, kenar-yüzey (tekil çözüm yok), yüzey-yüzey (tekil çözüm yok) olarak ayrılır; simpleks işleme de fiilen bu durumları analiz etmeye yakındır
    Pratikte çok sorun çıkar. Fizik motorlarında nesneler çoğu zaman yüzey-yüzey temas durumunda kararlı hâle gelir ve tek noktalı çarpışma modeli titreşim ya da hatalı hareket üretebilir. Ayrıca konum yüzey-yüzey temasa yakınsadığında GJK büyük değerler arasındaki küçük farklarla uğraşır ve kayan nokta anlamlı basamaklarını tamamen kaybedebilir. Sonlandırma koşulları da sonsuz döngüye yol açabilir
    Teoride zarif, ama pratikte zor bir sayısal analiz problemidir. Yine de muhtemelen bu probleme yönelik en hızlı yaklaşım olabilir. Genel durumda O(log N), önceki konuma en yakın durumda son çözümü başlangıç noktası olarak kullanırsanız O(1)'e yakındır
    Oxford'dan merhum Prof. Steven Cameron, GJK'nin düzgün çalışması için çok emek verdi ve 1990'ların sonunda ilk ticari 3D ragdoll sistemi olan "Falling Bodies"de GJK kullanıldı

    • Teması bulduktan sonra neredeyse mutlaka onunla bir şey yapmanız gerekir ve çoğu yararlı işlem için gerçek örtüşme bilgisini bilmeniz gerekir
      Bunu elde etmek sayısal açıdan daha da kötüdür. GJK'nin oluşturduğu simpleksten başlayıp dışa doğru genişletirsiniz ve bu süreçte üçgenlere ayırma yapmanız gerekir. Performanslı bir uygulama yapmak tam bir kâbusa yakındır
    • https://www.youtube.com/watch?v=5lHqEwk7YHs
      Patent artık süresi doldu mu, kodu yayımlamayı düşünüyorlar mı merak ediyorum. Tarihsel olarak anlamlı olurdu ve Doom kaynak kodunu okumak gibi ilginç bir materyal olacağını düşünüyorum

  • GJK çarpışma algılama algoritmasını sezgisel biçimde açıklayan bir yazı bulamadığım için öğleden sonramı ayırıp kendim derledim
    Daha anlaşılır ve verimli hâle getirmenin bir yolu varsa söylerseniz sevinirim. Tabii bunun matematikle ilgili konuları anlatan bir lise ikinci sınıf öğrencisinin yazısı olduğunu da uygun ölçüde hesaba katmanızı isterim

    • Yazı çok anlaşılır. Böyle çalışmalara devam edersen bir gün harika bir ders kitabı yazabilecek kadar yetenekli görünüyorsun
      Zaten iyi, ama daha eksiksiz kılmak için birkaç şey eklenebilir. En kötü durum zaman karmaşıklığı hakkında kısa bir açıklama, sonlandırma koşullarını ele alan ayrı bir bölüm ve anlatımın aralarına serpiştirilmiş sözde kod iyi olurdu
      Şu anki gibi matematiksel bakış açısıyla açıklama biçimi uygun ve korunmaya değer. Ancak her adımdan sonra S(•) gibi yardımcı fonksiyonları tanımlayıp algoritmanın nereye kadar ilerlediğini içeren kısa bir sözde kod eklersen daha da iyi olabilir
      OpenAI'ın gizli modeliyle ilgili yazın da iyiydi. Etkileyici işler çıkaran birinin başka neler yaptığına bakmak için harcanan zaman neredeyse her zaman karşılığını veriyor
    • Bir matematikçi olarak söyleyecek olursam, matematik okurlarına yönelik yazılmış olsaydı bazı ifadeleri çok az farklı kurardım; en sert eleştirim bu olurdu
      Başlık "as simply as possible" olmalı. GJK algoritmasını bilmiyordum ama şu anda Calculus III dersi veriyor olsaydım bunu derse katmanın bir yolunu arardım. Açıklama o kadar iyi
    • Bu algoritmanın sonlanmasının garanti olup olmadığını merak ediyorum
      Yazının sonundaki yumuşak köşeli dikdörtgen örneğinde, cevaba giderek yaklaşmaktan öteye geçmeyip fiilen ulaşamamasını neyin engellediğini bilmiyorum. Elbette gerçek hesaplamada pratik hassasiyet sınırından sonra devam etmenin anlamı olmadığını biliyorum
    • İkinci görseldeki üç küme A, B, A-B kafa karıştırıcı
      Başta A ve B'ye bir dönüşüm uygulanıp A-B şeklinin elde edildiği anlamına geldiğini sandım. Birkaç kez tekrar okuyunca A-B'nin soldaki iki küme değil, başka bir A ile B'nin kesişimini temsil ettiği ve önemli olanın bu kesişimin orijinle ya da 0,0 ile örtüşmesi olduğu anlaşılıyor. Doğru mu merak ediyorum

  • Aynı algoritmayı ele alan video sunumu: https://www.youtube.com/watch?v=ajv46BSqcK4

  • Yazı çok anlaşılır ve ilginç
    İki dışbükey kümenin kesişip kesişmediğini kontrol etmenin başka bir yolu da, birinci dışbükey kümeye ait bir nokta ile ikinci dışbükey kümeye ait bir noktanın farkının normunu minimize eden bir dışbükey optimizasyon problemi çözmektir. Optimum değer 0 ise iki küme kesişir
    GJK algoritmasıyla dışbükey optimizasyonu karşılaştırmak ilginç olurdu. Hangisinin daha avantajlı olduğundan pek emin değilim

    • İlginç bir soru. Örtüşme yeterince büyükse iç nokta yöntemi hızlı sonlanabilir gibi görünüyor. Akıllı erken sonlandırma koşulları da eklenebilir sanırım

  • İlk görsel dışbükey olmayan şekillerin kesişimini gösteriyor, ancak algoritmanın yalnızca dışbükey şekillerde çalıştığı gerçeği çok daha sonra belirtiliyor; bu biraz yanlış anlaşılmaya yol açabilir

    • Dışbükey olmayan şekillerin dışbükey şekillere bölünerek işlendiği açıklanmış

  • openSCAD'de Minkowski fonksiyonunu bir süredir kullanıyordum; onun gerçekte ne olduğunu öğrenmek güzel oldu

  • Beklediğimden çok daha fazla ilgi gördüğüne göre, kişisel web sitemin aslında incelikli iç şakalar derlemesi olduğunu söylemem gerekir sanırım
    İletişime geçmek isterseniz ya da bir işiniz olursa yanıt olarak yazabilirsiniz

    • Araştırma projesi mentörlüğüyle ilgileniyorsan e-posta gönderebilirsin: bersub@cmu.edu
    • Site güzel ve havalı birine benziyorsun. Harika şeyler yapmaya devam etmeni dilerim

  • Neredeyse 10 yıl önce Casey'nin mükemmel açıklamasına dayanarak GJK'yi uygulamıştım: https://www.youtube.com/watch?v=Qupqu1xe7Io

  • Minkowski geometrisi ile ilgili bir yazı yazmıştım: https://nickp.svbtle.com/asteroid-intersections