Etkileşimli 2B Çarpışma Tespiti

Ekrandaki iki şeklin ya ortak bir noktası vardır ya da yoktur. Oyunlar, fizik simülasyonları, çizim programları ve her arayüzde bir tıklamanın hangi öğeye denk geldiğini bulan kod, bu soruyu her karede defalarca sorar. Çoğu zaman da yalnızca evet ya da hayır yetmez: Şekiller birbirinin içine ne kadar girmiş, çıkış hangi yönde?

Bu yazıda dört şekil çiftini ele alıyorum: kenarları eksenlere paralel iki kutu, iki daire, bir daireyle bir kutu ve ayırıcı eksen teoremiyle iki dışbükey çokgen, yani hiçbir yerinde içe doğru girinti olmayan iki çokgen. Bunlar için kullanılan klasik testlerin nereden geldiğini adım adım gösteriyorum. Her bölümde kurcalayabileceğiniz bir çizim var. Şekilleri sürükleyin ya da Tab tuşuyla birini seçip ok tuşlarıyla taşıyın. Çizimlerin altındaki sayıları, metinde anlatılan kodun kendisi hesaplıyor.

Ekran koordinatlarını kullanıyorum: $x$ sağa doğru, $y$ ise SVG’de ve HTML canvas’ta olduğu gibi aşağıya doğru artar. Uzunlukları çizimin kendi birimiyle ölçüyorum ve bu birimi px diye yazıyorum.

Bir çarpışma testi ne söyler?

Her şekli sınırıyla, yani dış çizgisiyle birlikte düşüneceğiz; matematikte buna kapalı küme denir. Böylece yalnızca sınırları buluşan iki şekil de kesişmiş sayılır; bu duruma temas diyeceğiz. Temas da bir çarpışmadır. Yerde duran bir nesne için fizik motorunun istediği de tam budur. Aşağıdaki her testin yanıtı üç durumdan biridir: Şekiller ya ayrıdır ya temas eder ya da örtüşür. Test bunun yanında şunları da bildirir:

• derinlik $d$: şekillerin birbirinin içine ne kadar girdiği;
• normal $\mathbf{n}$: $A$ şeklinden $B$ şekline doğru bakan birim vektör, yani uzunluğu 1 olan bir yön;
• en kısa öteleme vektörü $\mathbf{t} = d\,\mathbf{n}$ (İngilizce adının kısaltmasıyla MTV): iki şeklin yalnızca temas eder hâle gelmesi için $B$’nin kaydırılması gereken en kısa yol;
• örtüşmenin olduğu yerde bir temas noktası; şekiller ayrıysa aralarındaki uzaklık ve iki şeklin birbirine en yakın noktaları.

Daha kesin söyleyelim. $B$’nin her noktasını $\mathbf{t}$ kadar kaydırınca elde edilen şekle $B + \mathbf{t} = \lbrace \mathbf{b} + \mathbf{t} : \mathbf{b} \in B \rbrace$ diyelim. MTV, $A$ ile $B + \mathbf{t}$ şekillerinin iç kısımlarında hiç ortak nokta bırakmayan en kısa $\mathbf{t}$ vektörüdür. $A$’yı $-\mathbf{t}$ kadar kaydırmak da aynı işi görür. Fizik motorları bir adımda çoğu zaman iki cismi de yolun bir kısmı kadar kaydırır.

İki kutu: AABB ile AABB

Eksenlere hizalı sınırlayıcı kutu, kenarları eksenlere paralel olan bir dikdörtgendir; İngilizce adının kısaltmasıyla buna AABB denir. Matematik diliyle bu kutu $[x_0, x_1] \times [y_0, y_1]$ kümesidir, yani $x$ koordinatı $x_0$ ile $x_1$ arasında, $y$ koordinatı $y_0$ ile $y_1$ arasında olan bütün noktalar. Test etmesi en kolay şekil budur. Son bölümde göreceğimiz gibi, ilk eleme de her yerde bu kutuyla yapılır.

Önce aralıklar

Bir doğru üzerinde iki kapalı aralık alalım: $[a_0, a_1]$ ve $[b_0, b_1]$. Bu iki aralığın ortak noktası yoksa biri tamamen ötekinin solunda kalır, yani $a_1 < b_0$ ya da $b_1 < a_0$ olur. Tersi de doğru. Demek ki iki aralık şu koşul sağlanıyorsa kesişir, sağlanmıyorsa kesişmez:

Bir kutu, $x$ üzerindeki bir aralıkla $y$ üzerindeki bir aralığın çarpımıdır. İki çarpımın kesişimi de kesişimlerin çarpımına eşittir:

Çarpanlardan biri boşsa bu küme de boştur. Yani iki kutu, $x$ eksenine düşen gölgeleri örtüşüyorsa ve $y$ eksenine düşen gölgeleri de örtüşüyorsa çarpışır; biri bile ayrıysa çarpışmaz. Bunun için dört karşılaştırma yeter, toplama çıkarma bile gerekmez.

Ne kadar derin, çıkış hangi yönde?

Kutuları $x$ yönünde ayırmanın iki yolu var. $B$ sağa kayabilir: Sol kenarı $A$’nın sağ kenarına gelince durur, yani $a_{x1} - b_{x0}$ kadar yol alır. Ya da sola kayabilir: Sağ kenarı $A$’nın sol kenarına gelince durur, yani $b_{x1} - a_{x0}$ kadar yol alır. Bu iki yoldan kısa olanı, o eksendeki örtüşmedir:

$o_x$ pozitifse gölgeler örtüşüyordur, sıfırsa birbirine değiyordur. Negatifse aralarında $-o_x$ genişliğinde bir boşluk vardır. Kutular $\min(o_x, o_y) \ge 0$ ise, yani iki değerin küçüğü bile negatif değilse çarpışır. Derinlik $d = \min(o_x, o_y)$ olur ve MTV, bu en küçük değeri veren eksen boyunca uzanır. Kutular ayrıysa aralarındaki uzaklık iki boşluktan şöyle hesaplanır:

const overlapX = Math.min(a.max.x - b.min.x, b.max.x - a.min.x);
const overlapY = Math.min(a.max.y - b.min.y, b.max.y - a.min.y);
const hit = overlapX >= 0 && overlapY >= 0;
const depth = hit ? Math.min(overlapX, overlapY) : 0;

Bir noktaya dikkat: $o_x$, gölgelerin ortak kısmının uzunluğu değil, gereken itmenin uzunluğudur. Kutulardan biri ötekinin içindeyse bu iki sayı farklı çıkar. Örneğin $[3, 5]$ gölgesi $[0, 10]$ aralığının içindeyse ikisinin ortak kısmı yalnızca 2 birimdir. Ama küçük gölgenin dışarı çıkması için 7 birim sağa ya da 5 birim sola gitmesi gerekir. Aşağıda küçük kutuyu büyüğün içine sürükleyin ve derinliğin, taralı örtüşme bölgesinin yüksekliğini nasıl geçtiğini izleyin.

Çarpışıyor — derinlik 25 px

x ekseninde örtüşme

25 px

y ekseninde örtüşme

95 px

MTV

(25, 0)

Temas noktası

(338, 223)

Sıfırla

Bir şekli sürükleyin ya da Tab tuşuyla seçip ok tuşlarıyla 5 px taşıyın (Shift basılıyken 25 px).

İki daire

Burada “daire” derken yalnızca çevre çizgisini değil, içiyle birlikte bütün diski kastediyorum: Merkezi $\mathbf{c}$, yarıçapı $r$ olan bir daire, $\mathbf{c}$ noktasına uzaklığı en fazla $r$ olan bütün noktalardan oluşur. İki disk şu koşul sağlanıyorsa kesişir, sağlanmıyorsa kesişmez:

Yani merkezler arasındaki uzaklık, yarıçapların toplamını geçmemeli. ($\lVert \cdot \rVert$ işareti bir vektörün uzunluğunu gösterir.)

Diskler kesişiyorsa bu koşul sağlanır. Bu, üçgen eşitsizliğinden gelir: Bir üçgende bir kenar, öbür iki kenarın toplamından uzun olamaz. İki diskte birden bulunan bir $\mathbf{p}$ noktası alırsak $\lVert \mathbf{c}_B - \mathbf{c}_A \rVert \le \lVert \mathbf{c}_B - \mathbf{p} \rVert + \lVert \mathbf{p} - \mathbf{c}_A \rVert \le r_B + r_A$ olur. Tersine, koşul sağlanıyorsa diskler kesişir. Bunu görmek için $\mathbf{c}_A$ noktasından $\mathbf{c}_B$ noktasına doğru yürüyün: $\mathbf{c}_A$ noktasına uzaklığı $\min(r_A, \lVert \mathbf{c}_B - \mathbf{c}_A \rVert)$ olan nokta iki diskin de içindedir. Kodda karekök almaya gerek yok, kareleri karşılaştırmak yeter: $\delta = \mathbf{c}_B - \mathbf{c}_A$ dersek test $\delta \cdot \delta \le (r_A + r_B)^2$ olur. ($\delta \cdot \delta$, $\delta$ vektörünün uzunluğunun karesidir.)

Normal, iki merkezi birleştiren doğrunun yönüdür: $\mathbf{n} = \delta / \lVert \delta \rVert$. Yani $\delta$ vektörünü kendi uzunluğuna bölüp uzunluğu 1 olan bir vektör elde ediyoruz. Derinlik ise yarıçapların toplamının merkezler arasındaki uzaklığı ne kadar aştığıdır:

Bu, işe yarayan ötelemelerden herhangi biri değil, en kısası. Neden? $B$ bir $\mathbf{v}$ vektörü kadar kaydırılırsa merkezler arasında en az $r_A + r_B$ kalmalıdır. $\lVert \delta + \mathbf{v} \rVert \le \lVert \delta \rVert + \lVert \mathbf{v} \rVert$ olduğundan buradan $\lVert \mathbf{v} \rVert \ge d$ çıkar. $\mathbf{n}$ yönünde kaydırmak ise tam $d$ kadar yol ister. En derindeki iki nokta, $A$ üzerinde $\mathbf{c}_A + r_A \mathbf{n}$ ve $B$ üzerinde $\mathbf{c}_B - r_B \mathbf{n}$ noktalarıdır. Bu ikisinin tam ortası, temas noktası için doğal bir seçimdir.

Merkezleri birleştiren doğrunun hiç olmadığı bir durum var: eş merkezli daireler. O zaman hangi yönü seçsek aynıdır. Kod da sıfıra bölmek yerine birini seçer; burada bu yön $\mathbf{n} = (1, 0)$.

Çarpışıyor — derinlik 19 px

Merkezler arası uzaklık

156 px

Yarıçapların toplamı

175 px

MTV

(19, −2)

Temas noktası

(325, 193)

Sıfırla

Bir şekli sürükleyin ya da Tab tuşuyla seçip ok tuşlarıyla 5 px taşıyın (Shift basılıyken 25 px).

Bir daireyle bir kutu

Bu iki farklı şekli birlikte test etmek için tek bir fikir yeter: Kutunun, dairenin $\mathbf{c}$ merkezine en yakın $\mathbf{p}$ noktasını bulun ve bu noktanın merkeze uzaklığını yarıçapla karşılaştırın. Uzaklığın karesi birbirinden bağımsız iki parçaya ayrılır,

kutunun koyduğu şartlar da iki koordinat için ayrıdır: $p_x$ değeri $[x_0, x_1]$ aralığında, $p_y$ değeri de $[y_0, y_1]$ aralığında kalmalıdır. Bu yüzden iki parçayı ayrı ayrı en küçük yapabiliriz. Bunun için $\mathbf{c}$ merkezinin her koordinatını kendi aralığının içine çekmek, yani sınırlamak yeter. Koddaki adı clamp:

Yani bir sayı aralığın içindeyse olduğu gibi kalır, dışındaysa aralığın en yakın ucuna çekilir. Daire ile kutu, $\lVert \mathbf{c} - \mathbf{p} \rVert \le r$ ise çarpışır, değilse çarpışmaz. Derinlik $r - \lVert \mathbf{c} - \mathbf{p} \rVert$ olur; normal de $\mathbf{p}$ noktasından $\mathbf{c}$ noktasına doğru bakar.

const p = { x: clamp(c.x, box.min.x, box.max.x), y: clamp(c.y, box.min.y, box.max.y) };
const dx = c.x - p.x;
const dy = c.y - p.y;
const hit = dx * dx + dy * dy <= r * r;

Kutunun kenarlarını uzatınca düzlem dokuz bölgeye ayrılır; çizimde bu çizgiler de var. Dairenin merkezi bir kenarın dışında ama o kenarın hizasındaysa koordinatlardan yalnızca biri sınırlanır ve $\mathbf{p}$ o kenar boyunca kayar. Bir köşenin ötesindeyse iki koordinat da sınırlanır ve $\mathbf{p}$ köşenin kendisi olur. Kutunun içindeyse hiçbir koordinat sınırlanmaz ve $\mathbf{p} = \mathbf{c}$ olur.

Aceleyle yazılmış kodun yanıldığı yer tam da bu son durumdur. $\mathbf{p} = \mathbf{c}$ olunca $\mathbf{c} - \mathbf{p}$ vektörü sıfır olur. Onu birim vektöre çevirmeye kalkarsanız sonuç NaN, yani geçersiz bir sayı olur. Geometriye bakarsak daire bir kenardan çıkmak zorundadır ve en kısa yol en yakın kenardan geçer. $c_x - x_0$, $x_1 - c_x$, $c_y - y_0$ ve $y_1 - c_y$ uzaklıklarının en küçüğüne $m$ dersek derinlik şudur:

Normal de o kenarın dışa bakan normalidir. Daha kısa bir itme işe yaramaz: Merkezin kutudan çıkması için en az $m$ yol alması, diskin tamamını dışarı taşımak için de ardından $r$ kadar daha gitmesi gerekir.

Çarpışıyor — derinlik 25 px

En yakın nokta p

(385, 145)

B dairesinin merkezi

kutunun dışında

Uzaklık |c − p|

45 px

MTV

(23, −11)

Sıfırla

Bir şekli sürükleyin ya da Tab tuşuyla seçip ok tuşlarıyla 5 px taşıyın (Shift basılıyken 25 px).

Ayırıcı eksen teoremi

Dönen kutular ve başka çokgenler için daha genel bir fikir gerekir. Kutu testine bir daha bakın: İki kutu, $x$ ya da $y$ ekseninde gölgeleri arasında boşluk kalıyorsa ayrıdır; kalmıyorsa çarpışır. Ayırıcı eksen teoremi (İngilizce adının kısaltmasıyla SAT), doğru eksenler denendiği sürece aynı fikrin herhangi iki dışbükey şekil için de işlediğini söyler.

Teorem. İki dışbükey çokgen $A$ ile $B$ ayrıksa, yani hiç ortak noktaları yoksa, öyle bir $\mathbf{n}$ yönü vardır ki iki çokgenin bu yöndeki izdüşümleri de ayrık iki aralıktır. Tersi de doğrudur: Böyle bir yön varsa çokgenler ayrıktır. Bu yöne ayırıcı eksen denir. Bir $S$ şeklinin $\mathbf{n}$ yönündeki izdüşümü, yani o yöne düşen gölgesi şu kümedir:

Üstelik $\mathbf{n}$ her zaman $A$’nın ve $B$’nin kenar normalleri arasından seçilebilir.

Algoritma doğrudan buradan çıkar: İki çokgenin bütün kenar normallerini tek tek deneyin. Her normal için iki çokgenin de o eksendeki izdüşümünü alın ve çıkan iki aralığı karşılaştırın. Tek bir boşluk, şekillerin ayrı olduğunu kanıtlar. Hiçbir eksende boşluk yoksa şekiller kesişir.

İzdüşümler ve aday eksenler

$\mathbf{n} \cdot \mathbf{s}$ iç çarpımı, $\mathbf{s}$ noktasının doğrusal bir fonksiyonudur. Doğrusal bir fonksiyon, bir çokgenin üzerinde en küçük ve en büyük değerini köşelerde alır. Bu yüzden köşeleri $\mathbf{v}_1, \dots, \mathbf{v}_k$ olan bir çokgenin izdüşümü şöyle bulunur:

$\mathbf{v}_i$ köşesinden $\mathbf{v}_{i+1}$ köşesine giden bir kenarın yönü $\mathbf{e} = \mathbf{v}_{i+1} - \mathbf{v}_i$ olsun. Bu kenara dik bir vektör, yani bir normal olarak $(e_y, -e_x)$ alınabilir. Paralel kenarlar aynı ekseni verir; bu yüzden bir dikdörtgen iki, bir üçgen üç, düzgün bir altıgen de üç eksen getirir. Şekillerin çarpışıp çarpışmadığına karar vermek için normallerin uzunluğunun 1 olması gerekmez; ne kadar örtüştüklerini ölçmek içinse gerekir.

Kenar normalleri neden yeter?

En sade kanıt, Minkowski farkı denen kümeden geçer:

Bu küme, $A$’dan bir nokta, $B$’den bir nokta alıp birinciden ikinciyi çıkarınca elde edilebilecek bütün vektörlerden oluşur.

1. $A$ ile $B$’nin ortak bir noktası olması, $\mathbf{0} \in A \ominus B$ olmasıyla, yani sıfır vektörünün bu farkın içinde olmasıyla aynı şeydir. Çünkü ortak bir $\mathbf{a} = \mathbf{b}$ noktası $\mathbf{a} - \mathbf{b} = \mathbf{0}$ verir.
2. $A \ominus B$, $A$ ile $-B$ kümelerinin Minkowski toplamıdır. İki dışbükey çokgenin Minkowski toplamı yine dışbükey bir çokgendir. $A$’nın ve $-B$’nin kenarlarını yönlerine göre sıraya dizince bu çokgenin kenarları çıkar. Bu yüzden onun her kenar normali, $A$’nın ya da $B$’nin bir kenar normaliyle ya aynı yöndedir ya da tam ters yönde.
3. Dışbükey bir çokgen, kenarlarının belirlediği $\lbrace \mathbf{x} : \mathbf{n}_j \cdot \mathbf{x} \le h_j \rbrace$ yarı düzlemlerinin kesişimidir. (Yarı düzlem, bir doğrunun bir yanında kalan bütün noktalardır.) Burada $\mathbf{n}_j$ kenarın dışa bakan normali, $h_j$ de $\mathbf{n}_j \cdot \mathbf{x}$ ifadesinin çokgen üzerindeki en büyük değeridir. Bu yüzden $\mathbf{0}$ noktasının çokgenin dışında kalması, $h_j < 0$ olan bir kenar bulunmasıyla aynı şeydir.
4. $A \ominus B$ için bu en büyük değer şudur:

$h_j < 0$ ise $A$’nın $\mathbf{n}_j$ üzerindeki gölgesinin her noktası, $B$’nin gölgesinin her noktasından küçüktür; yani izdüşümler ayrıktır.

Hepsini birleştirelim: Çokgenler ayrıksa $A$’nın ya da $B$’nin kenar normallerinden biri onları ayırır. Öte yandan, hangi yönde olursa olsun tek bir ayırıcı eksen bulmak bile ayrık olduklarını kanıtlamaya yeter. $h_j = 0$ ise şekiller birbirine değer: $\mathbf{0}$ noktası $A \ominus B$ kümesinin tam sınırındadır.

Minkowski farkı MTV’yi de hiç ek iş gerektirmeden verir. $B$’yi $\mathbf{t}$ kadar kaydırmak, $A \ominus B$ kümesini $-\mathbf{t}$ kadar kaydırır. Bu yüzden $\mathbf{0}$ noktasını farkın dışına çıkaran en kısa ötelemenin boyu, $\mathbf{0}$ noktasının farkın sınırına olan uzaklığı kadardır. $\mathbf{0}$ noktasını içeren dışbükey bir çokgende bu uzaklık, en küçük $h_j$ değeridir. Her aday eksende yapılan hesap, kutulardaki “iki itmeden kısa olanı” hesabının aynısıdır; eksenin iki yönüne de bakılır:

Yani en az örtüşen ekseni seçmek, çoğu zaman işe yarayan bir kestirme değil: Normaller birim uzunluktaysa bu eksen derinliği tam olarak verir ve MTV onun boyunca uzanır.

/** İki dışbükey çokgenin derinliği; bir eksen onları ayırıyorsa null. */
function sat(a: Vec[], b: Vec[]): number | null {
  let depth = Infinity;
  for (const poly of [a, b]) {
    for (let i = 0; i < poly.length; i++) {
      const e = sub(poly[(i + 1) % poly.length], poly[i]);
      const n = normalize({ x: e.y, y: -e.x });
      const [minA, maxA] = project(a, n);
      const [minB, maxB] = project(b, n);
      const overlap = Math.min(maxA - minB, maxB - minA);
      if (overlap < 0) return null; // ayırıcı eksen: çarpışma yok
      depth = Math.min(depth, overlap);
    }
  }
  return depth;
}

Aşağıdaki çizim bu döngünün daha kapsamlı bir sürümünü çalıştırıyor. İlk boşlukta durmak yerine bütün eksenleri saklıyor; böylece çizimin altındaki liste hepsini gösterebiliyor. Yönü, temas noktasını ve örtüşme bölgesini de hesaplıyor.

Çarpışıyor — derinlik 39 px

Aday eksenler

5

Ayırıcı eksen

yok

MTV

(37, −10)

Temas noktası

(340, 208)

Her eksendeki izdüşümler

Çizimde: A2 (otomatik)

Çizimde görmek istediğiniz ekseni seçin; otomatik seçime dönmek için aynı ekseni yeniden seçin.

• Eksen A1örtüşme 126 px
• Eksen A2örtüşme 39 px
• Eksen B1örtüşme 100 px
• Eksen B2örtüşme 57 px
• Eksen B3örtüşme 48 px

A şeklinin gölgesiB şeklinin gölgesi

B şekli

ÜçgenDikdörtgenBeşgen

Döndür

AB

Sıfırla

Bir şekli sürükleyin ya da Tab tuşuyla seçip ok tuşlarıyla 5 px taşıyın (Shift basılıyken 25 px). Q ve E tuşları seçili şekli 15° döndürür.

Denemeye değer birkaç şey var. B’yi, A’nın bir köşesine neredeyse değecek kadar yaklaştırın ama değdirmeyin: Çoğu zaman boşluğu yalnızca B’nin eksenlerinden biri bulur; A’nın kendi eksenlerinde gölgeler hâlâ örtüşür. B için dikdörtgeni seçin ve kenarları A’nınkilerle aynı hizaya gelene kadar döndürün: Eksenleri A’nınkilere paralel olur ve liste bunların yeni bir şey katmadığını gösterir. Beşgeni seçince yedi aday eksen olur ve derinlik her zaman bunlar arasındaki en küçük örtüşmedir.

Döndürülmüş dikdörtgenler ve üçgenler

Merkezi $\mathbf{c}$, yarı genişliği $w$, yarı yüksekliği $h$ ve açısı $\theta$ olan döndürülmüş bir dikdörtgenin köşeleri şunlardır:

Dikdörtgenin iki ekseni $R(\theta)$ matrisinin sütunlarıdır: $\mathbf{u} = (\cos\theta, \sin\theta)$ ve $\mathbf{v} = (-\sin\theta, \cos\theta)$. Yani bu eksenleri kenarlardan hesaplamaya hiç gerek yok. Dikdörtgenin birim uzunluktaki bir $\mathbf{n}$ eksenine izdüşümü, merkezi $\mathbf{n} \cdot \mathbf{c}$, yarı uzunluğu $w \lvert \mathbf{n} \cdot \mathbf{u} \rvert + h \lvert \mathbf{n} \cdot \mathbf{v} \rvert$ olan bir aralıktır. Böylece dört köşenin izdüşümünü tek tek almaya gerek kalmaz. İki döndürülmüş dikdörtgen için dört eksen gerekir. Eksenlere hizalı kutu, $\theta = 0$ olan özel durumdur; o zaman dört eksen, bildiğimiz iki eksene iner.

Bir $\mathbf{a}\mathbf{b}\mathbf{c}$ üçgeni üç eksen getirir. $(\mathbf{b} - \mathbf{a}) \times (\mathbf{c} - \mathbf{a})$ vektörel çarpımının işareti, üçgenin köşelerinin saat yönünde mi tersine mi sıralandığını söyler. $(e_y, -e_x)$ normalinin üçgenin dışına mı içine mi baktığını da bu sıra belirler. SAT testinin kendisi için bunun önemi yok, çünkü ekseni ters çevirince iki aralık da aynadaki gibi ters döner ve örtüşüp örtüşmedikleri değişmez. Ama dışa bakan normallerle MTV’nin yönünü düşünmek daha kolaydır. Aynı vektörel çarpım, bir $\mathbf{p}$ noktasının üçgenin içinde olup olmadığını da söyler. Bunun için çarpımı $\mathbf{p}\mathbf{b}\mathbf{c}$, $\mathbf{a}\mathbf{p}\mathbf{c}$ ve $\mathbf{a}\mathbf{b}\mathbf{p}$ alt üçgenlerine uygularız: Üç işaretten hiçbiri bütün üçgeninkinin tersi değilse nokta içeridedir.

Dışbükeylik neden önemli?

Kanıtta dışbükeyliği iki yerde kullandık. 2. adımda $A \ominus B$ kümesinin dışbükey bir çokgen çıkmasına, 3. adımda da dışbükey bir çokgenin dışındaki her noktanın kenar yarı düzlemlerinden birinin dışında kalmasına dayandık. İçbükey, yani bir yerinde içe doğru girinti olan şekillerde bu sonuç geçerli değildir. Aşağıdaki çizimde küçük bir kare, U biçimli bir şeklin oyuğunda, ona değmeden duruyor. Her aday eksende gölgeler örtüşüyor, bu yüzden SAT çarpışma bildiriyor. Sorun şu: Şekiller birbirine değmese de aralarından düz bir çizgi geçirilemez, çünkü aradaki boşluk oyuğun içinde kalıyor.

SAT: çarpışıyor — yanlış, şekiller arasında 25 px boşluk var

SAT (U’nun tamamı)

çarpışıyor

Dışbükey parçalar

çarpışma yok

Uzaklık

25 px

Ayırıcı eksen

yok

Sıfırla

Bir şekli sürükleyin ya da Tab tuşuyla seçip ok tuşlarıyla 5 px taşıyın (Shift basılıyken 25 px).

Bu sorunun olağan çözümü, içbükey çokgeni $P_1, \dots, P_k$ gibi dışbükey parçalara bölmek ve her parçayı ayrı ayrı test etmektir. Örneğin çokgeni kulak kesme (ear clipping) yöntemiyle üçgenlere ya da bir dışbükey ayrıştırmayla daha az sayıda parçaya bölebilirsiniz. Parçalardan biri çarpışıyorsa şekiller çarpışır; hiçbiri çarpışmıyorsa çarpışmaz. Derinlik ise daha fazla dikkat ister. Parçaların derinliklerinin en büyüğü, bütün şeklin derinliği için yalnızca bir alt sınırdır; yani gerçek derinlik bundan az olamaz ama daha fazla olabilir. Çünkü $B$’yi bir parçanın dışına iten hareket, onu doğrudan başka bir parçanın içine sokabilir. Kesin MTV için parçaları birlikte düşünmek gerekir: MTV yine $\mathbf{0}$ noktasından sınıra giden en kısa yoldur, ama bu kez sınır, $P_i \ominus B$ Minkowski farklarının birleşiminin sınırıdır.

Hesap ne kadar sürer?

İlk üç test sabit zamanda çalışır, yani her seferinde aynı, az sayıda işlem yapar: iki kutu için dört karşılaştırma; iki daire için uzaklığın karesiyle yarıçaplar toplamının karesi arasında tek bir karşılaştırma; bir daireyle bir kutu için iki sınırlama ve bir uzaklık karesi.

Köşe sayıları $n$ ve $m$ olan iki çokgende SAT, en fazla $n + m$ eksenin her biri için $n + m$ köşenin izdüşümünü alır. Bu, $O\bigl((n + m)^2\bigr)$ iş demektir, yani iş köşe sayısının karesiyle büyür. İlk boşluk bulununca da döngüden hemen çıkılır. Sıradan bir oyundaki küçük çokgenler için bu hızlıdır. Çok köşeli şekillerde ya da 3B’de ise GJK (Gilbert–Johnson–Keerthi) gibi yinelemeli algoritmalar daha iyi ölçeklenir. GJK, Minkowski farkıyla destek noktaları üzerinden çalışır; derinliği bulmak için yanına EPA (expanding polytope algorithm) eklenir.

Asıl maliyet ise çiftlerin sayısından gelir. $N$ şekilli bir sahnede $N(N - 1)/2$ çift vardır: bin şekil için her karede 499.500 çift.

Uygulamada

Önce kaba eleme, sonra kesin test

Gerçek sistemler işi ikiye böler. Önce kaba eleme aşaması (İngilizce kaynaklarda broad phase) çiftlerin çoğunu ucuz bir yoldan ayıklar. Bunu temkinli yapar, yani çarpışabilecek hiçbir çifti atmaz. Bunun için her şekli eksenlere hizalı bir kutuya sarar: döndürülmüş bir dikdörtgeni dört köşesini içine alan kutuya, bir daireyi kenarı $2r$ olan kareye. Sonra örtüşen kutuları uzamsal bir veri yapısıyla bulur. Bu iş için eşit hücreli bir ızgara, kutuları tek eksen boyunca sıralayıp tarayan bir yöntem (sort and sweep) ya da bir sınırlayıcı hacim hiyerarşisi (BVH) kullanılabilir. Yalnızca bu elemeyi geçen adaylar yukarıdaki kesin testlere ulaşır; bu ikinci aşamaya kesin test aşaması (narrow phase) denir. Böylece en basit test olan kutu testi iki ayrı yerde iş görür.

Kayan nokta hatalarına pay bırakmak

Kâğıt üzerinde tam olarak birbirine değen şekiller, hesap kayan noktalı sayılarla yapılınca nadiren tam olarak değer. IEEE çift duyarlıklı sayılarda (double) 0.1 + 0.2 işlemi 0.30000000000000004 verir; 0.1 sayısını on kez toplamak da 0.9999999999999999 eder. Bir dikdörtgeni $\pi/2$ kadar, yani 90 derece döndürürken $0$ yerine $\cos(\pi/2) \approx 6{,}1 \times 10^{-17}$ değeri kullanılır. Bu yüzden $x = 2$ doğrusuna oturması gereken bir köşe 1.9999999999999998 konumuna düşer ve birbirine değmesi gereken iki dikdörtgen yaklaşık $2 \times 10^{-16}$ kadar örtüşür. Buradan birkaç pratik kural çıkıyor:

• Temas durumunu bir toleransla tanımlayın: $\pm\varepsilon$ içinde kalan, yani sıfıra çok yakın bir örtüşme temas sayılsın. Bu yazıdaki çizimler $\varepsilon = 0{,}5$ px kullanıyor; bu, gözün ancak ayırt edebildiği kadar bir fark. Genel kullanım içinse çizimlerin arkasındaki kod, varsayılan $10^{-9}$ değerini koordinatların büyüklüğüne göre ölçekliyor, çünkü yuvarlama hataları sayılar büyüdükçe artar.
• Yalnızca evet ya da hayır yanıtı gerekiyorsa uzunlukların karelerini karşılaştırın. Vektörleri ancak bir derinlik ya da yön gerektiğinde birim vektöre çevirin.
• Sıfır olabilecek bir uzunluğa yapılan her bölmeyi önceden kontrol edin: eş merkezli daireler, kutunun içine düşen bir merkez, uzunluğu sıfır olan kenarlar, bir doğru parçasına ya da tek bir noktaya dönüşen çokgenler.

Çarpışan şekilleri ayırmak

En basit çözüm MTV’dir: Şekillerden birini bu vektör kadar kaydırın ya da kaydırmayı iki şekil arasında kütleleriyle orantılı olarak paylaştırın. Bir fizik motoru normale de ihtiyaç duyar; hızın öteki cisme doğru olan bileşenini onunla sıfırlar. Bir tuzak daha var: Hızlı ve küçük bir nesne, iki kare arasında ince bir nesnenin içinden geçip gidebilir ve hiçbir karede onunla örtüşmüş görünmez. Buna tünelleme denir. Sürekli çarpışma tespiti bunu önler: Şeklin hareket ederken taradığı alanı test eder ya da çarpışmanın tam anını hesaplar. Zaman adımlarını küçültmek de işe yarar.

Özet

Çift	Ne zaman çarpışır?	Derinlik	Maliyet
Kutu ve kutu	gölgeler hem $x$ hem $y$ ekseninde örtüşüyorsa	$\min(o_x, o_y)$	$O(1)$
Daire ve daire	$\lVert \mathbf{c}_B - \mathbf{c}_A \rVert \le r_A + r_B$ ise	$r_A + r_B - \lVert \mathbf{c}_B - \mathbf{c}_A \rVert$	$O(1)$
Daire ve kutu	$\lVert \mathbf{c} - \mathbf{p} \rVert \le r$ ise ($\mathbf{p}$: sınırlanmış nokta)	$r - \lVert \mathbf{c} - \mathbf{p} \rVert$; merkez içerideyse $r + m$	$O(1)$
Dışbükey çokgenler	hiçbir kenar normali gölgeleri ayırmıyorsa	kenar normallerindeki en küçük örtüşme	$O\bigl((n + m)^2\bigr)$

Her test, aynı fikrin daha özel ya da daha genel bir hâli: Şekillerin gölgesini, soruyu tek boyuta indiren bir eksene düşürün ve bir boşluk arayın. Çizimlerin arkasındaki kod, burada konuştuğumuz uç durumların testleriyle birlikte sitenin deposunda, src/lib/geometry klasöründe duruyor. Bu uç durumlar şunlar: birbirine değen şekiller, iç içe şekiller, bir çizgiye ya da noktaya dönüşen çokgenler ve $\pi/2$ kadar döndürme.