2D rijit cisim çarpışması nasıl çözülür

 (sassnow.ski)
3 puan yazan GN⁺ 2024-05-25 | 1 yorum | WhatsApp'ta paylaş
  • 2D oyun fiziğinde rijit cisim çarpışma çözümü, zaten temas eden veya üst üste binen cisimlerin bir sonraki karede birbirlerinin içinden geçmemesi için hız değişimlerini hesaplama problemidir
  • Oyun döngüsü her karede hız ve Δt ile konumu güncellediğinden, yeni konumda geometri çakışırsa ek bir işlem olmadığında cisimler birbirinin içinden geçer
  • Çarpışma yalnızca temas edip etmemek değil, temas eden cisimlerin mevcut hızlarıyla hâlâ birbirlerine doğru hareket edip etmediklerini de birlikte değerlendirmeyi gerektirir
  • Bir yüzeyden uzaklaşılıp uzaklaşılmadığı, normal ile hızın skaler çarpımının işaretine bakılarak anlaşılabilir; pozitifse aynı yönlü bir bileşen, negatifse zıt yönlü bir bileşen vardır
  • İki cisim söz konusu olduğunda tek tek hızlardan çok göreli hız ve çarpışma normali önemlidir; temas durumunda göreli normal hız negatifse bu bir çarpışma olarak görülebilir

Rijit cisim fiziği ve çarpışma çözümünün kapsamı

  • Konu rijit cisim fiziği (rigid body physics) olup, kuvvet alsa da şekil değiştirmeyen cisimleri ele alır
    • Gerçekte tüm cisimler moleküler düzeyde şekil değiştirdiği için tam anlamıyla rijit cisim diye bir şey yoktur
    • Çoğu fizik simülasyonunda bu tür ayrıntılı deformasyonları hesaplamak çok zordur ya da maliyetlidir
    • Bir cisim yeterince gerçekçi görünüyorsa, onu rijitmiş gibi sadeleştirmek pratik bir yaklaşımdır
  • Oyun motorlarında çarpışma işleme genelde iki aşamaya ayrılır
    • Çarpışma algılama (collision detection): sahnede hangi cisimlerin çarpışma hâlinde olduğunu belirler
    • Çarpışma çözümü (collision resolution): çarpışan cisimlerin hareket yönü, hızı, malzemesi vb. bilgilerine dayanarak sonraki durumu belirler
  • Buradaki odak, geometrik kesişimi bulma aşaması değil, çarpışma sonrası hareketi belirleyen çarpışma çözümüdür

Oyun döngüsünde çarpışmanın oluşma biçimi

  • Çoğu oyun, büyük bir döngü içinde sahnedeki cisimlerin konumunu tekrar tekrar yeniden hesaplar
  • Her yinelemede cismin konumu mevcut hızına (velocity) göre güncellenir
    • Hız, hem büyüklüğü hem yönü olan bir vektörel niceliktir
    • Okun uzunluğu sürati, okun gösterdiği yön ise hareket yönünü ifade eder
  • Belirli bir Δt zaman aralığındaki konum değişimi yer değiştirme (displacement) ile ifade edilir
    • Yer değiştirme de büyüklüğü ve yönü olan bir vektörel niceliktir
    • Oyun döngüsü saniyede 60 kez çalışıyorsa Δt, 1/60 saniyedir
  • Yeni konum, mevcut hızdan hesaplanan yer değiştirmenin eski konuma eklenmesiyle elde edilir
  • İki cismin yeni konumu geometrilerinin üst üste gelmesine yol açarsa, ek bir işlem olmadığında cisimler birbirini delip geçer

Çarpışma çözümünün bulmaya çalıştığı değer

  • Çarpışma çözümünün amacı, simülasyon ilerlerken cisimlerin artık birbirinin içinden geçmemesi için her cismin hız değişimini belirlemektir
  • Çarpışma öncesi ve sonrası hızlar şu gösterimle ifade edilir
    • v_a,i, v_b,i: a, b cisimlerinin çarpışma öncesi hızları
    • v_a,f, v_b,f: a, b cisimlerinin çarpışma sonrası hızları
    • Δv_a, Δv_b: çarpışma nedeniyle her cisimde oluşan hız değişimi
  • Sonuçta çarpışma çözümü, Δv_a ve Δv_b değerlerini bulma problemidir
  • Gerçekçi görünen çarpışmalar üretmek için seçilen hız değişiminin ilgili fizik yasalarını sağlaması gerekir

Yalnızca temas, çarpışmayı göstermez

  • İki cismin birbirine değiyor olması her zaman çarpışma hâlinde oldukları anlamına gelmez
  • Çarpışma, mevcut hızlarla hareket etmeye devam edilirse cisimlerin birbirlerinin içinden geçeceği durumdur
  • Aynı temas sahnesi, iki cismin hız yönlerine bağlı olarak çarpışma da olabilir, çarpışma olmayabilir de
  • Bu nedenle çarpışma koşulu iki şeyi birlikte gerektirir
    • Cisimlerin geometrileri temas ediyor ya da çakışıyor olmalıdır
    • Cisimler hâlâ çarpışma yönünde hareket ediyor olmalıdır

Yüzey normali ve uzaklaşma yönü

  • Bir cismin bir yüzeyden uzaklaşıp uzaklaşmadığı, o yüzeye ait normal yön ile belirlenebilir
  • Normal yön, yüzeye diktir ve yüzeyden doğrudan uzaklaşan yönü gösterir
    • Düz bir yüzeyde tüm noktalardaki normal yön aynıdır
    • Eğri bir yüzeyde normal yön noktadan noktaya değişir
    • Bir çemberin çevresinde, merkezden ilgili çevre noktasına giden yön normal yöndür
  • Normal yön, uzunluğu 1 olan normalize edilmiş vektör ile ifade edilir
    • Uzunluğu 1 olan vektöre birim vektör (unit vector) da denir
    • Vektörün normalize edildiğini göstermek için değişkenin üzerine ^ işareti konabilir
  • Bir noktadaki normal yön, o noktada yüzeyin teğetine (tangent) diktir

Yön bileşenini skaler çarpımla belirlemek

  • Bir vektörün başka bir vektörle ne kadar aynı yöne baktığını hesaplamak için skaler çarpım (dot product) kullanılabilir
  • 2 boyutlu vektörlerde skaler çarpım, karşılık gelen bileşenlerin çarpımlarının toplamıdır ve sonuç bir vektör değil, skalerdir
  • Geometrik olarak skaler çarpım, bir vektörün diğer vektör yönüne izdüşümünün skaler uzunluğunun, izdüşüm alınan vektörün uzunluğu ile çarpılması olarak görülebilir
  • Skaler çarpımın işareti, iki vektör arasındaki yön ilişkisini gösterir
    • İki vektör arasındaki açı 90°'den küçükse skaler çarpım pozitif olur ve genel olarak aynı yönü gösterir
    • Açı 90°'den büyükse skaler çarpım negatif olur ve genel olarak zıt yönü gösterir
    • Açı tam olarak 90° ise skaler çarpım 0 olur
  • Bir cismin hız vektörü ile yüzey normalinin skaler çarpımı pozitifse, cisim o yüzeyden uzaklaşıyordur

İki cisim çarpışmasına uygulamak

  • İki kutu gibi iki cisim olduğunda, her cisim için bir hız vektörü vardır
  • Bu durumda tek tek hızlar yerine iki cismin göreli hızı (relative velocity) kullanılır
    • Göreli hız, iki cismin hızları arasındaki farktır
    • Geometrik olarak v_b'nin ucundan v_a'nın ucuna giden vektördür
    • Örneğin iki aracın ayrı ayrı 50 km/s hızla kafa kafaya çarpışması, diğer koşullar aynıysa bir aracın duran başka bir araca 100 km/s ile çarpmasına denktir
  • Yüzeye karşılık gelen yön, çarpışma normali (collision normal) ile ifade edilir
    • Çarpışma normalinin hesaplanma yöntemi, çarpışan cisimlerin şekline veya geometrisine göre değişir
    • Buradaki örnek, bir cismin bir noktasının veya köşesinin diğer cismin kenarıyla çarpıştığı bir vertex-edge collision durumudur
    • vertex-edge collision durumunda çarpışma normali ilgili kenara diktir
  • Geleneksel olarak cisimler a, b diye gösterildiğinde çarpışma normali a cismine yönelir
    • Hangi cisme a ya da b denildiği önemli değildir; yeter ki tüm hesap boyunca tutarlı olunsun

Göreli normal hız ile çarpışmayı tanımlamak

  • Göreli hız v_ab ile çarpışma normali n^ arasındaki skaler çarpım hesaplanırsa, iki cismin çarpışma yönünde hareket edip etmediği anlaşılabilir
  • Bu değere göreli normal hız (relative normal velocity) denir
    • Göreli hızın çarpışma normali yönündeki bileşenidir
    • Burada işaret önemlidir, ancak daha sonra çarpışma sırasında etki eden kuvvetleri hesaplarken de önemli rol oynar
  • Göreli normal hızın işareti çarpışma durumunu ayırır
    • Değer pozitifse iki cisim zaten birbirinden uzaklaşıyordur
    • Değer negatifse iki cisim hâlâ birbirine doğru geliyordur
  • Sonuç olarak, bir cismin bir noktası diğer cisme temas ediyor ve göreli normal hız negatifse çarpışma meydana gelir

İlgili okumalar

1 yorum

 
GN⁺ 2024-05-25
Hacker News yorumları
  • Merhaba, yazının yazarıyım! Biraz arka plan eklemek gerekirse, bu yazı yazmayı planladığım katı cisim fiziği blog serisinin yalnızca ilk bölümü
    Bu yazı, benim gibi oyun geliştiricisi olmayan ve matematik geçmişi de güçlü olmayan kişileri hedefliyordu. Bu yüzden bu alanda deneyimli olanlara neredeyse apaçık görünecek kavramları da epey uzun anlattım. Sorularınız olursa memnuniyetle yanıtlarım
    • Geri bildirim olarak, girişteki “Mario’nun Goomba’nın üzerinden sekmesi...” örneği biraz yanlış anlaşılmaya açık görünüyor. NES ve SNES dönemindeki klasik Super Mario tarzı oyunların çoğu bu hesaplamaların büyük kısmına ihtiyaç duymuyordu ve bunları kullanmıyordu
      Oyun geliştirmeye yeni başlayanlar, çarpışma işlemleri için katı cisim çarpışma hesaplamalarına ya da Box2D gibi bir 2D fizik motoruna ihtiyaç olduğunu sıkça yanlış anlıyor. Bilardo oyunu ya da Angry Birds gibi kutuların yıkıldığı bir oyun yapmak istiyorsanız evet, ama 2D platform oyunu için eksene hizalı dikdörtgenleri karşılaştırarak çarpışmayı algılamak ve çakışmayı geri almak için karakterin X/Y koordinatlarını değiştirmek ya da zıplama/iniş sonrası Y hızını ayarlamak yeterlidir. Böylece karakter kontrol hissini daha ince ayarlamak da kolaylaşır; atalet de olur ama genellikle fiziksel olarak gerçekçi bir atalet değildir. Yeni başlayanlar gerçekçi fizik kullanmaya çalıştığında hareketlerin havada süzülüyormuş gibi ve tatmin edici olmayan bir hâle gelmesi kolaydır
      Bu basit, fizik motorsuz yaklaşımla başlayabileceğiniz bir eğitim örneği: https://www.love2d.org/wiki/Tutorial:Baseline_2D_Platformer
    • Çok iyiydi. “A word about math” bölümü gerçekten önemli. Ben de matematikte pek iyi sayılmam, ama eskiden matematik kavramlarını aşırı basitleştirerek çok temel bir fizik simülasyonu yapmıştım
      Nokta, çizgi gibi bileşenleri tekrar tekrar üst üste kurdum; küçük adımlar ve çok sayıda görsel hata ayıklama çizgisi ekleyince sonuç çok gıcırtılı ve yavaştı ama yine de bir ölçüde çalıştı
    • Yazı harika ve okuması keyifliydi. Ben de güçlü bir matematik geçmişi olmayan biri olarak bu “apaçık” kavramları açıkladığınız için teşekkür ederim :)
      İleride XPBD’yi (Extended Position Based Dynamics - http://mmacklin.com/xpbd.pdf) de okuyup açıklamayı planlıyor musunuz? Bu kavram giderek daha fazla ilgi görüyor gibi ve ben Bevy’de https://github.com/Jondolf/bevy_xpbd üzerinden oldukça başarılı şekilde kullandım. Genel yaklaşımdan daha kararlı görünüyor
    • Yazıyı gerçekten keyifle okudum :) Okulda benzer konularda zorlanmış biri olarak bile anlaşılması kolaydı
      Takip etmeye devam edebilmem için bir RSS akışı eklerseniz gerçekten harika olur
    • Açıklama gerçekten çok iyi!
      Merakımdan soruyorum, o sayfayı yapmak için hangi araçları kullandınız?
  • Vay! İyi araştırılmış, derinlemesine açıklanmış ve etkileşimli bir yazı
    Dürüst olmak gerekirse başta alan adına bakıp üst seviye alan adının “.ski” olduğunu görünce, bunun Mechanical Watch [1] ve başka harika yazılar yazan kişinin sitesi olduğunu sandım. Meğer tamamen başka biriymiş ama kalite benzer. Bu “.ski” üst seviye alan adında nasıl bir sihirli formül var acaba :)
    1. https://news.ycombinator.com/item?id=31261533
    • Nedeni çok basit. “ski”, Polonya soyadlarındaki en yaygın sonektir; en ünlü örnek de Kowalski’dir. Polonyalı ya da Polonya kökenli epey insan var
      Burada sevdiğimiz https://ciechanow.ski sitesinin yazarı da Apple’da çalışan Polonyalı bir programcıdır
  • Şu sıralar oğlumla birlikte yan proje olarak bir 2D uzay nişancı oyunu yapıyoruz. Üstten görünüşlü; her oyuncunun bir tür gemiyi kontrol edip uzay enkazıyla dolu kapalı bir alanda uçarak rakibine ateş ettiği bir fikir
    Oyunun önemli unsurlarından biri, uzay enkazını arena içinde hareket ettirebilmek ve bunu rakibi sıkıştırmak ya da hedefe ulaşmasını engellemek gibi yaratıcı şekillerde kullanmak. Projenin bir parçası olarak oyun motorunu tamamen atlamak istedik. Oğluma uygulama yapısını biraz daha öğretmek istiyordum ve ileride hazır bir oyun motoru kullansa bile en azından bir kez her şeyi baştan uygulama sürecinden geçmesini istedim. Çarpışma algılama ve çözümlemeye yaklaşana kadar her şey yolundaydı. Ondan sonra işler hızla kötüleşti. Teorik matematik geçmişim olmasına rağmen muazzam miktarda sınır durum karşısında kısa sürede bunaldım ve sonunda vazgeçip Box2D kullanmaya karar verdik. Profesyonel oyun geliştiricisi değilim ama 20 yılı aşkın yazılım geliştirme deneyimim ve matematik geçmişim var; buna rağmen bu problemi hafife alma hatasına düştüm. Sözle anlatınca kolay görünse de ayrıntılara indikçe karmaşıklığı geometrik olarak artan bir problem gibi
    • O oyun için gerçekçi fizik çarpışmaları gerçekten gerekli miydi? Değilse gereksiz karmaşıklık olabilir. 2000 öncesi 2D nişancı oyunlarının neredeyse tamamı, sonraki oyunların da yalnızca çok küçük bir kısmı bu yöntemi kullanır
      Çok basit dikdörtgen karşılaştırmalarıyla nişancı oyunu yapmanın yaygın bir yolu burada: https://kidscancode.org/blog/2016/08/pygame_shmup_part_3/
      Ancak uzay enkazı nesnelerinin gerçekçi biçimde çarpışıp kümelenmesi ve oyuncu gemisinin ağır cisim yığınlarını itmesini zorlaştırmak istiyorsanız fizik kütüphanesi kullanmak mantıklı
    • Verlet entegrasyonuna [1] baktınız mı? Birçok kullanım için oldukça ikna edici ve pratik, ayrıca gerçekten epey basit. Bu harika eğitimi [2] izleyip birkaç saat içinde temel bir fizik sistemi yapabildiğime kendim de şaşırmıştım
      [1]https://m.youtube.com/watch?v=lS_qeBy3aQI&pp=ygUSVmVybGV0IGl...

[2]https://m.youtube.com/watch?v=3HjO_RGIjCU&pp=ygUSdmVybGV0IGl...

  • Yine de oğlunuz için iyi bir ders olacak gibi. Bir projenin her parçasını tamamen kendi ellerinizle yapma hayalinin peşinden gitmek her zaman buna değmeyebiliyor.
  • Şimdi olmasa bile ileride faydalı bir başvuru kaynağı olacaktır. http://www.jeffreythompson.org/collision-detection/table_of_... nokta, daire, dikdörtgen, çizgi, çokgen ve üçgenler arasındaki çarpışma algılamayı ele alıyor.
  • N oyununun açıklamasını her zaman sevmişimdir: https://www.metanetsoftware.com/technique/tutorialA.html
    Flash’ın her yerde olduğu zamanlardı.
  • Bu konuda zıplayan ve çarpışan toplar içeren bir TypeScript demosu hazırlarken çok eğlendim. Çok şey öğrendim.
    Kod: https://github.com/vandrieu/canvas-bouncing-ball
    Çarpışma mantığı src/collision.ts içinde.
    Sonuç/demo: https://vandrieu.github.io/canvas-bouncing-ball/
    • Gerçekten güzel bir demo, elinize sağlık! Uygunsa bunu küçük bir çok oyunculu oyuna dönüştürmeyi denemek isterim.
      Mümkünse bir lisans ekleyebilir misiniz?
  • Katı cisim dinamiği ve kısıtlamalar konusunda daha derine inmek isterseniz, bu blog yazısı serisi çok faydalı olmuştu: https://www.toptal.com/game/video-game-physics-part-i-an-int...
  • Çarpışma, cisimler arasındaki ikili kesişmeme kısıtının ihlalidir. Çarpışma kuvvetleri, bu kısıtın Lagrange çarpanlarıdır. Çarpışma normali, bir cismin konfigürasyonuna göre kısıt fonksiyonunun normalize edilmiş kısmi türevidir.
    • Fiziği 1 kHz’in üzerinde hesaplayıp enerji korunumu ilkesine saygı gösteren, sayısal olarak kararlı bir integrasyon algoritması kullandığınızda bu yaklaşım iyi uyacak gibi.
      Ama oyunlarda fizik güncellemeleri bazen 30 Hz’e kadar düşen, keyfi bir Euler-Cromer yöntemiyle yapıldığı için oldukça farklı bir yaklaşım gerekiyor.
    • İlginç! Bu bakış açısını daha ayrıntılı açıklayan kaynaklar var mı?
  • Gerçekten harika! Anlatımı, etkileşimi ve özellikle yazının samimi tonunu sevdim. Sonraki yazıları da merakla bekliyorum.
  • 2D katı cisim fizik motoru yapmak gerçekten eğlenceli bir proje. Ben lineer cebir öğrenmeden önce JavaScript ile bir tane yapmıştım ve çalıştırabilmek için matematiğin içine epey daldım.
    Aylarımı verdim ama yaygın bilinen temellerin biraz ötesine geçen noktada ancak yüzeyi kazımış oldum. Cisimlerin birbirinin içine gömülmediği ya da titremediği kararlı bir motor yapmak dipsiz bir tavşan deliği; bulabildiğim matematik ağırlıklı yazıların çoğu da bunu pek ele almıyordu. Matematiği Christ Hecker’ın eski yazı serisiyle kavradım.
    http://www.chrishecker.com/Rigid_Body_Dynamics
    • Kesinlikle! “Part 3: Collision Response” aslında bu yazıların referans aldığı içerik.
  • JavaScript öğrenmek için canvas ile başladım ve oyun geliştirme deneyimim olmadan birkaç şirin küçük tarayıcı oyunu yaptım. Bunlardan biri bir Galaga klonu; genel olarak iyi çalışıyor.
    Zor kısım mermi çarpışmaları. Merminin mevcut konumunu ve bir sonraki zaman adımındaki konumunu alıp, düşmanın hitbox’ına da aynı şekilde bakarak kesişip kesişmediklerini kontrol etmem gerekiyordu; ben ise yalnızca mevcut zaman adımını kontrol ettim. Bu yüzden mermiler sihirli bir şekilde düşmanların yanından geçip gidebiliyor! Aptalca bir şey. Belki bir gün geri dönüp düzeltirim.