Video Oyunu Fiziği Eğitimi - Bölüm II: Katı Nesneler için Çarpışma Algılama

Bu, video oyunu fiziği üzerine üç bölümlük serimizin II. Bölümüdür. Bu serinin geri kalanı için bkz.

Bölüm I: Sert Cisim Dinamiğine Giriş
Bölüm III: Kısıtlanmış Sert Cisim Simülasyonu

Bu serinin I. Kısmında katı cisimleri ve hareketlerini araştırdık. Ancak bu tartışmada nesneler birbirleriyle etkileşime girmedi. Bazı ek çalışma olmadan, simüle edilmiş katı cisimler birbirlerinin içinden geçebilir veya çoğu durumda istenmeyen bir şekilde "iç içe geçebilir".

Katı nesnelerin davranışını daha gerçekçi bir şekilde simüle etmek için, her hareket ettiklerinde birbirleriyle çarpışıp çarpışmadıklarını kontrol etmeliyiz ve eğer çarparlarsa, hızlarını değiştiren kuvvetler uygulamak gibi bu konuda bir şeyler yapmalıyız. ters yönde hareket edeceklerini söyledi. Oyun geliştiricileri için çarpışma fiziğini anlamanın özellikle önemli olduğu yer burasıdır.

Kısım II'de, 2B veya 3B bir dünyaya dağılmış muhtemelen çok sayıda cisim arasında çarpışan cisim çiftlerini bulmaktan oluşan çarpışma algılama adımını ele alacağız. Sonraki ve son bölümde, iç içe geçmeleri ortadan kaldırmak için bu çarpışmaları “çözmek” hakkında daha fazla konuşacağız.

Bu makalede atıfta bulunulan lineer cebir kavramlarının bir incelemesi için Bölüm I'deki lineer cebir hızlandırılmış kursuna başvurabilirsiniz.

Video Oyunlarında Çarpışma Fiziği

Katı cisim simülasyonları bağlamında, iki katı cismin şekilleri kesiştiğinde veya bu şekiller arasındaki mesafe küçük bir toleransın altına düştüğünde bir çarpışma meydana gelir.

Simülasyonumuzda n bedenimiz varsa, ikili testlerle çarpışmaları saptamanın hesaplama karmaşıklığı O ( n 2 ) olur, bu sayı bilgisayar bilimcilerini sindiren bir sayıdır. İkili testlerin sayısı, cisim sayısıyla birlikte ikinci dereceden artar ve keyfi konumlarda ve yönlerde iki şeklin çarpışıp çarpışmadığını belirlemek zaten ucuz değildir. Çarpışma algılama sürecini optimize etmek için, genellikle iki aşamaya böleriz: geniş faz ve dar faz .

Geniş faz, potansiyel olarak çarpışan katı cisim çiftlerini bulmaktan ve kesinlikle çarpışmayan çiftleri simülasyondaki tüm cisimler kümesinden hariç tutmaktan sorumludur. Bu adım, O ( n 2 ) zaman karmaşıklığının altında kaldığımızdan emin olmak için katı cisimlerin sayısıyla gerçekten iyi ölçeklenebilmelidir. Bunu başarmak için, bu aşama genellikle, çarpışma için bir üst sınır oluşturan sınırlayıcı hacimlerle birleştirilmiş alan bölümlemeyi kullanır.

Dar faz, çarpışan geniş faz tarafından bulunan katı cisim çiftleri üzerinde çalışır. Çarpışmaların gerçekten olup olmadığını belirlediğimiz ve bulunan her çarpışma için daha sonra çarpışmaları çözmek için kullanılacak temas noktalarını hesapladığımız bir iyileştirme adımıdır.

Sonraki bölümlerde geniş evrede ve dar evrede kullanılabilecek bazı algoritmalardan bahsedeceğiz.

Geniş Aşama

Video oyunları için çarpışma fiziğinin geniş aşamasında, hangi katı cisim çiftlerinin çarpışabileceğini belirlememiz gerekiyor. Bu cisimler çokgenler ve çokyüzlüler gibi karmaşık şekillere sahip olabilir ve bunu hızlandırmak için yapabileceğimiz şey, nesneyi kuşatmak için daha basit bir şekil kullanmaktır. Bu sınırlayıcı hacimler kesişmiyorsa, gerçek şekiller de kesişmez. Eğer kesişirlerse, gerçek şekiller kesişebilir.

Bazı popüler sınırlayıcı hacim türleri, yönlendirilmiş sınırlayıcı kutular (OBB), 2B'de daireler ve 3B'de kürelerdir. En basit sınırlayıcı hacimlerden birine bakalım: eksen hizalı sınırlayıcı kutular (AABB) .

AABB'ler, basit oldukları ve iyi ödünleşimler sundukları için fizik programcılarından çok sevilirler. 2 boyutlu bir AABB, C dilinde şuna benzer bir yapı ile temsil edilebilir:

 typedef struct { float x; float y; } Vector2; typedef struct { Vector2 min; Vector2 max; } AABB;

min alanı kutunun sol alt köşesinin konumunu ve max alanı sağ üst köşeyi temsil eder.

İki AABB'nin kesişip kesişmediğini test etmek için, yalnızca projeksiyonlarının tüm koordinat eksenlerinde kesişip kesişmediğini bulmamız gerekir:

 BOOL TestAABBOverlap(AABB* a, AABB* b) { float d1x = b->min.x - a->max.x; float d1y = b->min.y - a->max.y; float d2x = a->min.x - b->max.x; float d2y = a->min.y - b->max.y; if (d1x > 0.0f || d1y > 0.0f) return FALSE; if (d2x > 0.0f || d2y > 0.0f) return FALSE; return TRUE; }

Bu kod, Box2D motorundaki (sürüm 2.3.0) b2TestOverlap işlevinin aynı mantığına sahiptir. Her iki eksende de her iki AABB'nin min ve max değerleri arasındaki farkı her iki sırada hesaplar. Bu değerlerden herhangi biri sıfırdan büyükse, AABB'ler kesişmez.

Bir AABB örtüşme testi ucuz olsa da, hala istenmeyen O ( n 2 ) zaman karmaşıklığına sahip olduğumuz için olası her çift için ikili testler yapmamız pek yardımcı olmaz. AABB çakışma testlerinin sayısını en aza indirmek için, sorguları hızlandıran veritabanı dizinleriyle aynı ilkeler üzerinde çalışan bir tür alan bölümleme kullanabiliriz. (PostGIS gibi coğrafi veritabanları aslında uzamsal dizinleri için benzer veri yapıları ve algoritmalar kullanır.) Bu durumda, AABB'ler sürekli hareket edecek, bu nedenle genel olarak, simülasyonun her adımından sonra endeksleri yeniden oluşturmalıyız.

Tek tip ızgaralar, 2B'de dörtlü ağaçlar, 3B'de oktrees ve uzamsal karma gibi bunun için kullanılabilecek çok sayıda alan bölümleme algoritması ve veri yapısı vardır. İki popüler uzamsal bölümleme algoritmasına daha yakından bakalım: sıralama ve süpürme ve sınırlayıcı hacim hiyerarşileri (BVH).

Sıralama ve Süpürme Algoritması

Sıralama ve süpürme yöntemi (alternatif olarak süpürme ve budama olarak da bilinir), katı cisim simülasyonunda kullanım için fizik programcıları arasında favori seçeneklerden biridir. Örneğin Bullet Physics motoru, btAxisSweep3 sınıfında bu yöntemin bir uygulamasına sahiptir.

Bir AABB'nin tek bir koordinat eksenine izdüşümü esasen bir aralıktır [ b , e ] (yani, başlangıç ​​ve bitiş). Simülasyonumuzda, birçok katı cisme ve dolayısıyla birçok AABB'ye sahip olacağız ve bu, birçok aralık anlamına gelir. Hangi aralıkların kesiştiğini bulmak istiyoruz.

Sırala ve süpür algoritmasında tüm b ve e değerlerini tek bir listeye ekliyoruz ve skaler değerlerine göre artan şekilde sıralıyoruz. Sonra listeyi tararız veya geçeriz. Bir b değeriyle karşılaşıldığında, karşılık gelen aralığı ayrı bir etkin aralıklar listesinde saklanır ve bir e değeriyle karşılaşıldığında, karşılık gelen aralığı etkin aralıklar listesinden çıkarılır. Herhangi bir anda, tüm aktif aralıklar kesişiyor. (Ayrıntılar için David Baraff'ın Doktora Tezi, s. 52'ye bakın. Postscript dosyasını görüntülemek için bu çevrimiçi aracı kullanmanızı öneririm.) Aralıkların listesi, simülasyonun her adımında yeniden kullanılabilir, burada verimli bir şekilde yeniden sıralayabiliriz. bu liste, neredeyse sıralanmış listeleri sıralamada iyi olan eklemeli sıralamayı kullanır.

İki ve üç boyutta, sıralama ve taramayı yukarıda açıklandığı gibi tek bir koordinat ekseni üzerinde çalıştırmak, yapılması gereken doğrudan AABB kesişim testlerinin sayısını azaltacaktır, ancak getirisi bir koordinat ekseni üzerinde diğerinden daha iyi olabilir. Bu nedenle, sıralama ve tarama algoritmasının daha karmaşık varyasyonları uygulanmaktadır. Gerçek Zamanlı Çarpışma Tespiti (sayfa 336) adlı kitabında, Christer Ericson tüm AABB'leri tek bir dizide sakladığı ve her sıralama ve tarama çalışması için bir koordinat ekseninin seçildiği ve dizinin şuna göre sıralandığı verimli bir varyasyon sunar. hızlı sıralamayı kullanarak seçilen eksendeki AABB'lerin min değeri. Daha sonra dizi çaprazlanır ve AABB örtüşme testleri yapılır. Sıralama için kullanılması gereken bir sonraki ekseni belirlemek için, AABB'lerin merkezinin varyansı hesaplanır ve bir sonraki adım için daha büyük varyansa sahip eksen seçilir.

Dinamik Sınırlama Hacmi Ağaçları

Bir başka kullanışlı uzaysal bölümleme yöntemi, Dbvt olarak da bilinen dinamik sınırlayıcı hacim ağacıdır . Bu, bir tür sınırlayıcı hacim hiyerarşisidir .

Dbvt, her düğümün alt öğelerinin tüm AABB'lerini sınırlayan bir AABB'ye sahip olduğu ikili bir ağaçtır. Sert gövdelerin AABB'leri yaprak düğümlerinde bulunur. Tipik olarak, bir Dbvt, kavşakları tespit etmek istediğimiz AABB'yi vererek "sorgulanır". Bu işlem verimlidir, çünkü sorgulanan AABB ile kesişmeyen düğümlerin alt öğelerinin çakışma açısından test edilmesine gerek yoktur. Bu nedenle, bir AABB çakışma sorgusu kökten başlar ve yalnızca sorgulanan AABB ile kesişen AABB düğümleri için ağaç boyunca özyinelemeli olarak devam eder. Ağaç, bir AVL ağacında olduğu gibi, ağaç dönüşleriyle dengelenebilir.

Box2D, b2DynamicTree sınıfında gelişmiş bir Dbvt uygulamasına sahiptir. b2BroadPhase sınıfı, geniş aşamayı gerçekleştirmekten sorumludur ve AABB sorgularını gerçekleştirmek için bir b2DynamicTree örneğini kullanır.

Dar Faz

Video oyunu çarpışma fiziğinin geniş aşamasından sonra, potansiyel olarak çarpışan bir dizi katı cisim var. Bu nedenle, her iki cismin şekli, konumu ve yönelimi verilen her bir çift için, bunların gerçekten çarpışıp çarpışmadığını bulmamız gerekir; kesişiyorsa veya mesafeleri küçük bir tolerans değerinin altına düşüyorsa. Ayrıca, çarpışmaları daha sonra çözmek için gerekli olduğundan, çarpışan cisimler arasında hangi temas noktalarının olduğunu da bilmemiz gerekir.

Dışbükey ve İçbükey Şekiller

Bir video oyunu fiziği genel kuralı olarak, iki rastgele şeklin kesişip kesişmediğini belirlemek veya aralarındaki mesafeyi hesaplamak önemsiz değildir. Bununla birlikte, ne kadar sert olduğunu belirlemede kritik öneme sahip bir özellik, şeklin dışbükeyliğidir . Şekiller hem dışbükey hem de içbükey olabilir ve içbükey şekillerle çalışmak daha zordur, bu nedenle bunlarla başa çıkmak için bazı stratejilere ihtiyacımız var.

Dışbükey bir şekilde, şekil içindeki herhangi iki nokta arasındaki bir doğru parçası her zaman tamamen şeklin içine düşer. Ancak içbükey (veya "dışbükey olmayan") bir şekil için, şekildeki noktaları birleştiren tüm olası doğru parçaları için aynı şey geçerli değildir. Şeklin dışında kalan en az bir doğru parçası bulabilirseniz, şekil içbükeydir.

Hesaplamalı olarak, bir simülasyonda tüm şekillerin dışbükey olması arzu edilir, çünkü dışbükey şekillerle çalışan çok sayıda güçlü mesafe ve kesişim testi algoritmamız vardır. Yine de tüm nesneler dışbükey olmayacaktır ve genellikle bunların etrafında iki şekilde çalışırız: dışbükey gövde ve dışbükey ayrıştırma.

Bir şeklin dışbükey gövdesi , onu tamamen içeren en küçük dışbükey şekildir. İki boyutlu bir içbükey çokgen için, her bir köşeye bir çivi çakmak ve tüm çivilerin etrafına lastik bir bant sarmak gibi olacaktır. Bir çokgen veya çokyüzlü için veya daha genel olarak bir dizi nokta için dışbükey gövdeyi hesaplamak için, kullanılacak iyi bir algoritma, ortalama zaman karmaşıklığı O ( n log n ) olan hızlı gövde algoritmasıdır.

Açıkçası, içbükey bir nesneyi temsil etmek için dışbükey bir gövde kullanırsak, içbükey özelliklerini kaybedecektir. Nesne yine de içbükey bir grafik temsile sahip olacağından, "hayalet" çarpışmalar gibi istenmeyen davranışlar belirgin hale gelebilir. Örneğin, bir araba genellikle içbükey bir şekle sahiptir ve onu fiziksel olarak temsil etmek için dışbükey bir gövde kullanır ve üzerine bir kutu koyarsak, kutu yukarıdaki boşlukta yüzer gibi görünebilir.

Genel olarak, dışbükey gövdeler genellikle içbükey nesneleri temsil etmek için yeterince iyidir, çünkü ya gerçekçi olmayan çarpışmalar çok belirgin değildir ya da içbükey özellikleri simüle edilen her şey için gerekli değildir. Ancak bazı durumlarda, içbükey nesnenin fiziksel olarak içbükey bir şekil gibi davranmasını isteyebiliriz. Örneğin, bir kaseyi fiziksel olarak temsil etmek için dışbükey bir gövde kullanırsak, içine hiçbir şey koyamayız. Nesneler sadece üzerinde yüzer. Bu durumda, içbükey şeklin dışbükey ayrışmasını kullanabiliriz.

Dışbükey ayrıştırma algoritmaları, içbükey bir şekil alır ve birleşimi orijinal içbükey şekille aynı olan bir dışbükey şekiller kümesi döndürür. Bazı içbükey şekiller yalnızca çok sayıda dışbükey şekil ile temsil edilebilir ve bunların hesaplanması ve kullanılması aşırı derecede maliyetli olabilir. Bununla birlikte, bir yaklaşıklık genellikle yeterince iyidir ve bu nedenle, V-HACD gibi algoritmalar, bir içbükey çokyüzlüden küçük bir dışbükey çokyüzlüler seti üretir.

Bununla birlikte, birçok çarpışma fiziği vakasında, dışbükey ayrıştırma bir sanatçı tarafından elle yapılabilir. Bu, ayrıştırma algoritmaları ile performansı vergilendirme ihtiyacını ortadan kaldırır. Performans, gerçek zamanlı simülasyonların en önemli yönlerinden biri olduğundan, genellikle karmaşık grafik nesneler için çok basit fiziksel temsiller oluşturmak iyi bir fikirdir. Aşağıdaki görüntü, dokuz dışbükey şekil kullanan bir 2D arabanın olası bir dışbükey ayrıştırmasını göstermektedir.

Kavşak Testi - Ayıran Eksen Teoremi

Ayırma ekseni teoremi (SAT), iki dışbükey şeklin, ancak ve ancak bu eksen üzerindeki şekillerin dik izdüşümlerinin kesişmediği en az bir eksen varsa kesişmediğini belirtir.

2B'de bir çizgi veya 3B'de iki şekli ayıran bir düzlem bulmak genellikle görsel olarak daha sezgiseldir, ancak bu aslında aynı prensiptir. 2B'de çizgiye dik bir vektör veya 3B'de düzlemin normal vektörü, “ayırma ekseni” olarak kullanılabilir.

Oyun fiziği motorları, daireler (3B'de küreler), kenarlar (tek bir çizgi parçası) ve dışbükey çokgenler (3B'de çokyüzlüler) gibi bir dizi farklı şekil sınıfına sahiptir. Her bir şekil türü çifti için belirli bir çarpışma algılama algoritması vardır. Bunların en basiti muhtemelen daire-daire algoritmasıdır:

 typedef struct { float centerX; float centerY; float radius; } Circle; bool CollideCircles(Circle *cA, Circle *cB) { float x = cA->centerX - cB->centerX; float y = cA->centerY - cB->centerY; float centerDistanceSq = x * x + y * y; // squared distance float radius = cA->radius + cB->radius; float radiusSq = radius * radius; return centerDistanceSq <= radiusSq; }

SAT çemberler için geçerli olsa da, merkezleri arasındaki mesafenin yarıçaplarının toplamından daha küçük olup olmadığını kontrol etmek çok daha kolaydır. Bu nedenle, SAT, dışbükey çokgene karşı dışbükey çokgen (veya 3B'de çokyüzlüler) gibi belirli şekil sınıfı çiftleri için çarpışma algılama algoritmasında kullanılır.

Herhangi bir şekil çifti için, ayrılma için test edebileceğimiz sonsuz sayıda eksen vardır. Bu nedenle, verimli bir SAT uygulaması için önce hangi eksenin test edileceğini belirlemek çok önemlidir. Neyse ki, bir çift dışbükey çokgenin çarpışıp çarpışmadığını test ederken, potansiyel ayırma eksenleri olarak kenar normallerini kullanabiliriz. Bir kenarın normal vektörü n , kenar vektörüne diktir ve çokgenin dışını gösterir. Her çokgenin her kenarı için, diğer çokgenin tüm köşelerinin kenarın önünde olup olmadığını bulmamız yeterlidir.

Herhangi bir test geçerse - yani herhangi bir kenar için diğer çokgenin tüm köşeleri onun önündeyse - o zaman çokgenler kesişmez. Lineer cebir bu test için kolay bir formül sağlar: a ve b köşeleri olan ilk şekil üzerinde bir kenar ve diğer şekil üzerinde bir v tepe noktası verildiğinde, eğer ( v - a ) · n sıfırdan büyükse, o zaman tepe noktası öndedir. kenardan.

Çokyüzlüler için, yüz normallerini ve ayrıca her şekildeki tüm kenar kombinasyonlarının çapraz çarpımını kullanabiliriz. Bu, test edilecek pek çok şey gibi görünüyor; ancak, işleri hızlandırmak için, kullandığımız son ayırma eksenini önbelleğe alabilir ve simülasyonun sonraki adımlarında tekrar kullanmayı deneyebiliriz. Önbelleğe alınan ayırma ekseni artık şekilleri ayırmıyorsa, önceki yüze veya kenara bitişik olan yüzlerden veya kenarlardan başlayarak yeni bir eksen arayabiliriz. Bu işe yarar çünkü bedenler genellikle adımlar arasında çok fazla hareket etmez veya dönmez.

Box2D, b2CollidePolygon.cpp içindeki çokgen-çokgen çarpışma algılama algoritmasında iki dışbükey çokgenin kesişip kesişmediğini test etmek için SAT kullanır.

Hesaplama Mesafesi - Gilbert-Johnson-Keerthi Algoritması

Birçok çarpışma fiziği vakasında, nesnelerin yalnızca gerçekten kesişiyorlarsa değil, aynı zamanda aralarındaki mesafeyi bilmemizi gerektiren birbirlerine çok yakınlarsa çarpıştığını düşünmek istiyoruz. Gilbert-Johnson-Keerthi (GJK) algoritması, iki dışbükey şekil arasındaki mesafeyi ve ayrıca en yakın noktaları hesaplar. Aşağıda açıklandığı gibi destek işlevleri, Minkowski toplamları ve tek eksenler aracılığıyla dışbükey şekillerin örtük bir temsiliyle çalışan zarif bir algoritmadır.

Destek fonksiyonları

Bir destek işlevi s A ( d ) , d vektörü üzerinde en yüksek izdüşümüne sahip olan A şeklinin sınırındaki bir noktayı döndürür. Matematiksel olarak, d ile en yüksek nokta çarpımına sahiptir. Buna destek noktası denir ve bu işlem destek eşleme olarak da bilinir. Geometrik olarak bu nokta şeklin d yönündeki en uzak noktasıdır.

Bir çokgen üzerinde bir destek noktası bulmak nispeten kolaydır. d vektörü için bir destek noktası için, köşeleri arasında dolaşmanız ve d ile en yüksek nokta çarpımına sahip olanı bulmanız yeterlidir, şöyle:

 Vector2 GetSupport(Vector2 *vertices, int count, Vector2 d) { float highest = -FLT_MAX; Vector2 support = (Vector2){0, 0}; for (int i = 0; i < count; ++i) { Vector2 v = vertices[i]; float dot = vx * dx + vy * dy; if (dot > highest) { highest = dot; support = v; } } return support; }

Bununla birlikte, bir destek fonksiyonunun gerçek gücü, diğerlerinin yanı sıra koniler, silindirler ve elipsler gibi şekillerle çalışmayı kolaylaştırmasıdır. Bu tür şekiller arasındaki mesafeyi doğrudan hesaplamak oldukça zordur ve GJK gibi bir algoritma olmadan, işleri daha basit hale getirmek için genellikle bunları bir çokgen veya çokyüzlü olarak ayırmanız gerekir. Bununla birlikte, bir polihedronun yüzeyi, çokyüzlü çok detaylı olmadıkça, örneğin bir kürenin yüzeyi kadar pürüzsüz olmadığı için, bu başka sorunlara yol açabilir, bu da çarpışma tespiti sırasında düşük performansa yol açabilir. Diğer istenmeyen yan etkiler de ortaya çıkabilir; örneğin, "çokyüzlü" bir küre düzgün bir şekilde yuvarlanmayabilir.

Orijini merkez alan bir küre için bir destek noktası elde etmek için, d' yi normalize etmemiz yeterlidir (yani, d / || d || , hala aynı yönü gösteren 1 uzunluğu (birim uzunluk) olan bir vektördür) d ) ve sonra onu küre yarıçapı ile çarpıyoruz.

Diğer şekillerin yanı sıra silindirler ve koniler için daha fazla destek işlevi örneği bulmak için Gino van den Bergen'in makalesine bakın.

Nesnelerimiz, elbette, simülasyon uzayında başlangıç ​​noktasından itibaren yer değiştirecek ve döndürülecek, bu nedenle dönüştürülmüş bir şekil için destek noktalarını hesaplayabilmemiz gerekiyor. Nesnelerimizin yerini değiştirmek ve döndürmek için T ( x ) = R x + c afin dönüşümünü kullanırız, burada c yer değiştirme vektörüdür ve R döndürme matrisidir . Bu dönüşüm önce nesneyi orijin etrafında döndürür ve sonra onu çevirir. Dönüştürülmüş bir A şekli için destek işlevi:

Minkowski Toplamları

İki A ve B şeklinin Minkowski toplamı şu şekilde tanımlanır:

Bu, A ve B'de bulunan tüm noktaların toplamını hesapladığımız anlamına gelir. Sonuç, A ile B'yi şişirmek gibidir.

Benzer şekilde, Minkowski farkını şu şekilde tanımlarız:

A'nın -B ile Minkowski toplamı olarak da yazabiliriz:

Dışbükey A ve B için, A⊕B de dışbükeydir.

Minkowski farkının kullanışlı bir özelliği, bir önceki resimde görülebileceği gibi, uzayın orijinini içeriyorsa, şekillerin kesişmesidir. Nedenmiş? Çünkü iki şekil kesişirse, uzayda aynı yerde bulunan en az bir ortak noktaları vardır ve aralarındaki fark, aslında orijin olan sıfır vektörüdür.

Minkowski farkının bir başka güzel özelliği de orijini içermiyorsa orijin ile Minkowski farkı arasındaki minimum uzaklığın şekiller arasındaki uzaklık olmasıdır.

İki şekil arasındaki mesafe şu şekilde tanımlanır:

Başka bir deyişle, A ile B arasındaki mesafe, A'dan B'ye giden en kısa vektörün uzunluğudur. Bu vektör A⊖B'de bulunur ve en küçük uzunluğa sahip olandır, dolayısıyla orijine en yakın olanıdır.

İki şeklin Minkowski toplamını açıkça oluşturmak genellikle basit değildir. Neyse ki, destek eşlemesini burada da kullanabiliriz, çünkü:

Simpleksler

GJK algoritması, Minkowski farkı üzerindeki orijine en yakın noktayı yinelemeli olarak arar. Bunu, her yinelemede orijine daha yakın olan bir dizi simpleks oluşturarak yapar. Bir simpleks - veya daha spesifik olarak, bir k tamsayısı için bir k -simpleks - k boyutlu bir uzayda k + 1 afin bağımsız noktaların dışbükey gövdesidir. Yani, iki nokta için çakışmamaları, üç nokta için ayrıca aynı doğru üzerinde bulunmamaları ve dört noktamız varsa aynı düzlemde bulunmamaları gerekir. Dolayısıyla, 0-simpleks bir nokta, 1-simpleks bir doğru parçası, 2-simpleks bir üçgen ve 3-simpleks bir dörtyüzlüdür. Bir simpleksten bir nokta çıkarırsak, boyutluluğunu bir azaltırız ve bir simplekse bir nokta eklersek, boyutluluğunu bir arttırırız.

GJK İş Başında

GJK'nın nasıl çalıştığını görmek için hepsini bir araya getirelim. İki A ve B şekli arasındaki mesafeyi belirlemek için, onların Minkowski farklarını A⊖B alarak başlıyoruz. Ortaya çıkan şekil üzerinde orijine en yakın noktayı arıyoruz, çünkü bu noktaya olan mesafe orijinal iki şekil arasındaki mesafedir. A⊖B'de bir v noktası seçiyoruz, bu bizim uzaklık yaklaşımımız olacak. Ayrıca, mevcut test simpleksindeki noktaları içerecek olan W boş bir nokta seti tanımlıyoruz.

Ardından bir döngüye giriyoruz. A⊖B üzerindeki v üzerine izdüşümü orijine en yakın olan nokta olan w = s A⊖B (- v ) destek noktasını alarak başlıyoruz.

Eğer || w || || 'den çok farklı değil v || ve aralarındaki açı fazla değişmedi (önceden tanımlanmış bazı toleranslara göre), bu, algoritmanın yakınsadığı ve || v || mesafe olarak.

Aksi takdirde, w'yi W'ye ekleriz. W'nin dışbükey gövdesi (yani, tek yönlü) orijini içeriyorsa, şekiller kesişir ve bu da işimizin bittiği anlamına gelir. Aksi takdirde, simplekste orijine en yakın noktayı buluruz ve sonra v'yi bu yeni en yakın yaklaşıklık olacak şekilde sıfırlarız. Son olarak, W'de en yakın nokta hesaplamasına katkıda bulunmayan noktaları kaldırıyoruz. (Örneğin bir üçgenimiz varsa ve orijine en yakın nokta kenarlarından birindeyse, bu kenarın köşesi olmayan noktayı W'den kaldırabiliriz.) yakınsar.

Sonraki görüntü, GJK algoritmasının dört yinelemesinin bir örneğini göstermektedir. Mavi nesne Minkowski farkı A⊖B'yi temsil eder ve yeşil vektör v'dir . Burada v'nin orijine en yakın noktada nasıl ilerlediğini görebilirsiniz.

GJK algoritmasının ayrıntılı ve derinlemesine bir açıklaması için, Gino van den Bergen'in Dışbükey Nesnelerin Çarpışma Tespiti için Hızlı ve Sağlam GJK Uygulaması makalesine bakın. dyn4j fizik motoru blogunda ayrıca GJK hakkında harika bir gönderi var.

Box2D, b2Distance işlevinde b2Distance.cpp içinde GJK algoritmasının bir uygulamasına sahiptir. Sürekli çarpışma algılama algoritmasında yalnızca etki hesaplaması sırasında GJK'yi kullanır (aşağıda tartışacağımız bir konu).

Chimpunk fizik motoru, tüm çarpışma algılaması için GJK'yi kullanır ve uygulaması cpCollision.c'de, GJK işlevindedir. GJK algoritması kesişimi bildirirse, yine de penetrasyon derinliği ile birlikte temas noktalarının ne olduğunu bilmesi gerekir. Bunu yapmak için, daha sonra inceleyeceğimiz Genişleyen Politop Algoritmasını kullanır.

Penetrasyon Derinliğini Belirleme - Genişleyen Politop Algoritması

Yukarıda belirtildiği gibi, eğer A ve B şekilleri kesişiyorsa, GJK, Minkowski farkı A⊖B içinde orijini içeren bir simpleks W üretecektir. Bu aşamada, yalnızca şekillerin kesiştiğini biliyoruz, ancak birçok çarpışma algılama sisteminin tasarımında, ne kadar kesişimimiz olduğunu ve temas noktaları olarak hangi noktaları kullanabileceğimizi hesaplayabilmek arzu edilir, böylece çarpışmayı gerçekçi bir şekilde ele alıyoruz. Genişleyen Politop Algoritması (EPA), GJK'nin bıraktığı yerden başlayarak bu bilgiyi elde etmemizi sağlar: orijini içeren bir tek yönlü ile.

Penetrasyon derinliği , kesişen bir şekli diğer şekilden ayırmak için çevirebileceğimiz en küçük vektör olan minimum öteleme vektörünün (MTV) uzunluğudur.

İki şekil kesiştiğinde, onların Minkowski farkı orijini içerir ve Minkowski farkının sınırında orijine en yakın olan nokta MTV'dir. EPA algoritması, GJK'nın bize verdiği tek yönlülüğü bir çokgene genişleterek bu noktayı bulur; kenarlarını art arda yeni köşelere bölerek.

İlk olarak, orijine en yakın olan simpleksin kenarını buluyoruz ve Minkowski farkındaki destek noktasını kenara dik (yani ona dik ve çokgenin dışını gösteren) bir yönde hesaplıyoruz. Daha sonra bu destek noktasını ona ekleyerek bu kenarı böldük. Vektörün uzunluğu ve yönü fazla değişmeyene kadar bu adımları tekrarlıyoruz. Algoritma yakınsadığında, MTV'ye ve penetrasyon derinliğine sahibiz.

GJK'yı EPA ile birlikte kullanarak, nesneler zaten kesişiyorsa veya çarpışma olarak değerlendirilecek kadar yakınsa çarpışmanın ayrıntılı bir tanımını alıyoruz.

EPA algoritması, yine Gino van den Bergen tarafından yazılmış olan 3D Oyun Nesneleri Üzerindeki Yakınlık Sorguları ve Penetrasyon Derinliği Hesaplaması adlı kağıtta açıklanmıştır. dyn4j blogunda ayrıca EPA hakkında bir gönderi var.

Sürekli Çarpışma Algılama

Şimdiye kadar sunulan video oyunu fizik teknikleri, simülasyonun statik bir anlık görüntüsü için çarpışma tespiti gerçekleştirir. Buna ayrık çarpışma algılama denir ve önceki ve mevcut adımlar arasında ne olduğunu yok sayar. Bu nedenle, özellikle hızlı hareket eden nesneler için bazı çarpışmalar algılanamayabilir. Bu sorun tünelleme olarak bilinir.

Sürekli çarpışma algılama teknikleri, simülasyonun önceki ve mevcut adımı arasında iki cismin ne zaman çarpıştığını bulmaya çalışır. Çarpışma zamanını hesaplarlar, böylece zamanda geriye gidebilir ve çarpışmayı o noktada işleyebiliriz.

Çarpma zamanı (veya temas zamanı) t c , iki cisim arasındaki mesafenin sıfır olduğu zaman anıdır. Zaman içinde iki cisim arasındaki uzaklık için bir fonksiyon yazabilirsek, bulmak istediğimiz bu fonksiyonun en küçük kökünü bulmaktır. Bu nedenle, etki hesaplama zamanı bir kök bulma problemidir .

Darbe hesaplama zamanı için, vücudun durumunu (konum ve oryantasyonu) önceki adımda t i -1 zamanında ve mevcut adımda t i zamanını dikkate alıyoruz. İşleri kolaylaştırmak için adımlar arasında doğrusal hareket olduğunu varsayıyoruz.

Şekillerin daire olduğunu varsayarak sorunu basitleştirelim. Yarıçapları r 1 ve r 2 olan, kütle merkezleri x 1 ve x 2'nin ağırlık merkezleriyle çakıştığı (yani, kütle merkezleri etrafında doğal olarak döndükleri) iki C1 ve C2 çemberi için uzaklık fonksiyonunu yazabiliriz. olarak:

Adımlar arasındaki lineer hareketi göz önünde bulundurarak, C 1'in t i -1'den t i'ye kadar olan konumu için aşağıdaki fonksiyonu yazabiliriz.

x 1 ( t ben -1 ) ile x 1 ( t ben ) arasında doğrusal bir enterpolasyondur . Aynısı x 2 için de yapılabilir. Bu aralık için başka bir uzaklık fonksiyonu yazabiliriz:

Bu ifadeyi sıfıra eşitleyin ve t üzerinde ikinci dereceden bir denklem elde edin. Kökler doğrudan ikinci dereceden formül kullanılarak bulunabilir. Daireler kesişmezse, ikinci dereceden formülün bir çözümü olmayacaktır. Eğer yaparlarsa, bir veya iki kökle sonuçlanabilir. Yalnızca bir kökü varsa, o değer etki zamanıdır. İki kökü varsa, en küçüğü çarpma zamanı, diğeri ise dairelerin ayrıldığı zamandır. Buradaki çarpma zamanının 0'dan 1'e kadar bir sayı olduğuna dikkat edin. Saniye cinsinden bir zaman değildir; bu sadece cesetlerin durumunu çarpışmanın gerçekleştiği kesin konuma enterpolasyon yapmak için kullanabileceğimiz bir sayıdır.

Daire Olmayanlar İçin Sürekli Çarpışma Algılama

Diğer şekil türleri için bir mesafe fonksiyonu yazmak zordur, çünkü öncelikle mesafeleri oryantasyonlarına bağlıdır. Bu nedenle, genellikle nesneleri çarpışma olarak kabul edilecek kadar yakın olana kadar her yinelemede birbirine yaklaştıran yinelemeli algoritmalar kullanırız.

Muhafazakar ilerleme algoritması, gövdeleri yinelemeli olarak ileriye doğru hareket ettirir (ve döndürür). Her yinelemede yer değiştirme için bir üst sınır hesaplar. Orijinal algoritma, Brian Mirtich'in cisimlerin balistik hareketini ele alan Doktora Tezinde (bölüm 2.3.2) sunulmuştur. Erwin Coumans'ın (Bullet Physics Engine'in yazarı) bu makalesi, sabit doğrusal ve açısal hızları kullanan daha basit bir versiyon sunar.

Algoritma, A ve B şekilleri arasındaki en yakın noktaları hesaplar, bir noktadan diğerine bir vektör çizer ve hareket için bir üst sınır hesaplamak için hızı bu vektöre yansıtır. Vücuttaki hiçbir noktanın bu projeksiyonun ötesine geçmemesini garanti eder. Daha sonra gövdeleri bu miktar kadar ilerletir ve mesafe küçük bir tolerans değerinin altına düşene kadar tekrar eder.

Bazı durumlarda, örneğin cisimlerden birinin açısal hızı çok yüksek olduğunda, yakınsamak çok fazla yineleme gerektirebilir.

Çarpışmaları Çözme

Bir çarpışma algılandıktan sonra, çarpışan nesnelerin hareketlerini gerçekçi bir şekilde değiştirmek, örneğin birbirlerinden sektirmelerine neden olmak gerekir. Bu teorilerin sonraki ve son bölümünde, video oyunlarındaki çarpışmaları çözmek için bazı popüler yöntemleri tartışacağız.

Referanslar

Çarpışma algılama algoritmaları ve teknikleri gibi çarpışma fiziği hakkında daha derin bir anlayış elde etmekle ilgileniyorsanız, Christer Ericson tarafından yazılan Gerçek Zamanlı Çarpışma Algılama kitabı mutlaka edinmelisiniz.

Çarpışma tespiti büyük ölçüde geometriye dayandığından, Toptal'ın Python'da Hesaplamalı Geometri: Teoriden Uygulamaya başlıklı makalesi konuya mükemmel bir giriş niteliğindedir.