1. Yön testi — tek bir çapraz çarpım; DOOM’un duvar testi, Mario 64’ün zemin testi
2. Kesişim — iki doğru parçası; “nerede?” için t; DOOM’un mermisi nasıl isabet eder
3. Nokta çokgenin içinde mi? — ışın atma kuralı ve köşe tuzağı; Paradox’un renkli haritası
4. Alan ve dönüş yönü — ayakkabı bağı formülü; arka yüz ayıklama
5. Dışbükey zarf — sırala + yığın (monoton zincir); çarpışma şekillerinin kaynağı
6. Her adımda — elle izleme → canlı demo → kod (JavaScript / Python / C#) → oyunlardaki karşılığı

A, B, C’den iki vektör kur: u = B − A ve v = C − A. Bunların çapraz çarpımı:

$$u \times v = u_x v_y - u_y v_x$$

$$= (B_x - A_x)(C_y - A_y) - (B_y - A_y)(C_x - A_x)$$

• Bu sayının büyüklüğü: u ve v’nin gerdiği paralelkenarın alanı (= ABC üçgeninin alanının 2 katı).
• Bu sayının işareti: v’ye ulaşmak için u’yu hangi yöne çevirmeniz gerektiği. Yani C’nin hangi tarafta olduğu.
• Sıfır: alan yok → üç nokta aynı doğru üzerinde.
• İki çarpma, beş çıkarma. Bölme yok, karekök yok, trigonometri yok. Koordinatlar tam sayıysa sonuç hatasız.

A = (1, 1), B = (5, 3). Yani u = B − A = (4, 2). (Matematik koordinatı: y yukarı.)

Son iki satır: C’yi doğru boyunca kaydırmak sonucu değiştirmiyor. Doğruya paralel kaydırmak da (ör. (3, 5) → (5, 6)) değiştirmez: 4·5 − 2·4 = 12. Çünkü üçgenin tabanı ve yüksekliği aynı kalır.

• DOOM’un haritası duvar çizgilerinden oluşur. Motor sürekli sorar: “şu nokta bu çizginin önünde mi, arkasında mı?”
• left ve right bizim formülün iki çarpımı; right < left karşılaştırması, farkın işaretine bakmakla aynı şey: çapraz çarpımın işareti.
• Bu fonksiyon her şeyin altında: canavar duvara çarptı mı, oyuncu bir kapı çizgisini geçti mi, mermi hangi yüzden girdi…
• 1993’te kayan noktalı işlem yavaştı; DOOM bütün sayıları sabit noktalı tam sayı (fixed_t) tutar. Yan etkisi: sonuçlar her bilgisayarda birebir aynı (bu sayede oyun kayıtları, “demo”lar, yıllar sonra da aynı oynar).

• Bir nokta üçgenin içindeyse, üç kenarın hepsinin aynı tarafındadır. Üç yön testi; biri bile ters işaretliyse dışarıda.
• Super Mario 64: dünya, zemin / duvar / tavan üçgenlerinden oluşur. Her kare “Mario’nun ayağının altında hangi zemin üçgeni var?” diye sorulur.
• İkinci sekmeye bakın: oyunun kodu (yukarıdan bakışta, x ve z ile) üç kez aynı çapraz çarpımı hesaplıyor; biri negatifse continue ile sıradaki üçgene geçiyor.
• Navmesh’te “ajan hangi üçgende?” sorusu da budur (Y9).

• Koordinatlar ondalıklıysa çapraz çarpım tam 0 yerine 0.0000001 ya da −0.0000001 çıkabilir. Aynı üç nokta, farklı sırayla verilince farklı cevap.
• Belirtiler: karakter iki duvarın birleştiği köşeden “sızar”; mermi iki üçgenin tam arasından geçer; navmesh’te ajan bir kenarın üstünde titrer.
• Çare 1 · tam sayı: ızgara oyunları, DOOM’un sabit noktası. Sonuç hatasız (ama Mario 64’teki gibi yuvarlama boşlukları doğabilir).
• Çare 2 · eşik payı: abs(çapraz) < ε ise “doğrusal” say. ε, koordinatların büyüklüğüne göre seçilir.
• Çare 3 · tutarlılık: ortak bir kenarı her yerde aynı uç sırasıyla sına; iki komşu üçgen aynı kenar için aynı cevabı versin.

• AB doğrusu düzlemi ikiye böler. CD parçası AB’yi kesiyorsa C ve D farklı taraflarda olmak zorunda.
• Ama bu yetmez: C ve D farklı taraflarda olup kesişim AB parçasının ötesinde kalabilir.
• O yüzden simetrik koşul da gerekir: A ve B, CD doğrusunun farklı taraflarında.
• İki koşul birlikte ↔ parçalar kesişir. Toplam dört yön testi:

$$d_1 = \text{cross}(A,B,C) \qquad d_2 = \text{cross}(A,B,D)$$

$$d_3 = \text{cross}(C,D,A) \qquad d_4 = \text{cross}(C,D,B)$$

Kesişir ⇔ d₁ ve d₂ zıt işaretli ve d₃ ve d₄ zıt işaretli. Kodda: d1 * d2 < 0 && d3 * d4 < 0.

• Bir yön testi tam 0 çıkarsa o uç, öbür parçanın doğrusu üzerindedir. Ama parçanın içinde mi, uzantısında mı?
• Bunu onSegment cevaplar: noktanın x’i ve y’si parçanın iki ucunun arasında mı? (Parçanın sınırlayıcı kutusu.)
• T biçimi: C tam AB’nin üstünde → d₁ = 0, kutunun içinde → dokunuyorlar.
• Uç uca: B ile C aynı nokta → dokunuyorlar.
• Aynı doğru, üst üste: dört test de 0; uçlardan biri öbürünün kutusundaysa örtüşüyorlar.
• Aynı doğru, ayrık: dört test de 0 ama hiçbir uç öbürünün kutusunda değil → kesişmiyorlar.

Parçayı bir yolculuk olarak yazın: P(t) = A + t·r, r = B − A. t = 0’da A’dasınız, t = 1’de B’de, t = 0,5’te tam ortada.

Duvar da aynı şekilde: Q(u) = C + u·s, s = D − C.

Kesişimde P(t) = Q(u). İki tarafı s ile çapraz çarparsak (s × s = 0 olduğu için u yok olur):

$$t = \frac{(C - A) \times s}{r \times s} \qquad u = \frac{(C - A) \times r}{r \times s}$$

• r × s = 0 → paralel (payda sıfır).
• 0 ≤ t ≤ 1 ve 0 ≤ u ≤ 1 → kesişim iki parçanın da içinde.
• Kesişim noktası: A + t·r.

• DOOM’da tabanca, pompalı ve makineli “mermi” göndermez: tetik çekilince namludan menzil boyunca tek bir doğru parçası çizilir (hitscan).
• P_InterceptVector = bizim t formülümüz: payda iki yönün çapraz çarpımı, sonuç frac.
• Yol üzerindeki bütün duvar çizgileri ve canavarlar (her canavar, kutusunun köşegeni olan bir çizgiyle temsil edilir) için frac hesaplanıp bir listeye konur.
• P_TraverseIntercepts listeden her seferinde en küçük frac’lıyı seçer: en yakın engel önce. Engel mermiyi durdurursa (func yanlış döndürür) arkadakilere hiç bakılmaz.
• Aynı kod “kapıyı kullan” tuşu, canavarların görüş kontrolü ve patlamaların duvar arkasına geçmemesi için de çalışır.

• Mermiyi her karede bir nokta olarak düşünürseniz: bu karede duvarın önünde, sonraki karede arkasında. Hiçbir karede duvarın içinde değil → çarpışma yok!
• Hızlı mermi + ince duvar + düşük kare hızı = tünelleme. Oyun tarihinin en eski hatalarından.
• Çare tam olarak bu bölümdeki fonksiyon: merminin bu karedeki yolunu (önceki konum → yeni konum) duvarla kesiştirmek.
• Motorlardaki adı: “sürekli çarpışma tespiti” (Unity: Collision Detection → Continuous). G3’te karakterler için de göreceğiz.

1. Noktadan herhangi bir yöne (biz sağa) sonsuz bir ışın gönder.
2. Çokgenin kenarlarını kaç kez kesiyor, say.
3. Tek sayı → içeride. Çift (ya da 0) → dışarıda.

Bir kenar ışını ne zaman keser? İki koşul:

• (1) Noktanın y’si, kenarın iki ucunun y’leri arasında. (Yoksa ışın kenarın altından ya da üstünden geçer.)
• (2) Kenarın o yükseklikteki x’i, noktanın sağında. (Işın sağa gidiyor; soldaki kesişim sayılmaz.)

Kenar A–B’nin p_y yüksekliğindeki x’i (benzer üçgenler):

$$x = A_x + (p_y - A_y)\,\frac{B_x - A_x}{B_y - A_y}$$

İçbükey, girintili, yüzlerce köşeli şekillerde de çalışır. Yatay kenarlar (A_y = B_y) 1. koşulu hiç sağlamaz: sıfıra bölme olmaz.

Çokgen (üstünde V biçiminde bir çentik var): (1,1) → (6,1) → (6,5) → (3,3) → (1,5)

(4, 4) şeklin sınırlayıcı kutusunun içinde ama çentiğin boşluğunda: kutu testi burada yanılırdı.

• Paradox’un büyük strateji oyunlarında (Europa Universalis IV, Hearts of Iron IV) harita binlerce eyalete bölünür; her birinin sınırı yüzlerce köşeli. Fare hangi eyaletin üstünde?
• Oyun bunu ışın atmayla yapmaz. Oyun dosyalarında provinces.bmp adlı bir resim vardır: her eyalet kendine özgü tek bir renkle boyanmıştır.
• Yanındaki definition.csv dosyası rengi eyalete bağlar: “R 128, G 34, B 64 → 1 numaralı eyalet, Stockholm”.
• Tıkladığınız noktanın resimdeki pikseli okunur, rengi tabloda aranır: eyalet bulundu. Maliyet sabit; sınırın karmaşıklığından bağımsız.
• Mod yapanlar haritayı bir resim programında boyayarak düzenler; iki eyaleti yanlışlıkla aynı renge boyamak klasik bir mod hatasıdır.

Köşeleri sırayla dolaş, her kenar için bir çapraz çarpım topla:

$$\text{Alan} = \tfrac{1}{2}\,\Big|\sum_i (x_i\,y_{i+1} - x_{i+1}\,y_i)\Big|$$

Elle: dikdörtgen (0,0) → (4,0) → (4,3) → (0,3)

Köşeleri ters sırada verirseniz toplam −24 çıkar: işaret = dönüş yönü. İçbükey çokgende de doğru. Neden çalışır: her terim, orijin ile o kenarın oluşturduğu üçgenin (işaretli) alanının 2 katıdır; dışarıda kalan parçalar ters işaretle gelip birbirini götürür.

Gamedev Maths: point in triangle
Sebastian Lague · 3 dk 53 sn · YouTube’da aç

Bu bölümdeki “içinde mi?” sorusunun en sık görülen hâli: üç çapraz çarpımın işaretiyle nokta-üçgen testi, Sebastian Lague’ın temiz çizimleriyle. Kısa; derste izlenebilir.

• Tahtaya çiviler çakın, etrafına bir lastik bant geçirin ve bırakın. Bandın değdiği çiviler: dışbükey zarfın köşeleri.
• Tanım: bütün noktaları içine alan en küçük dışbükey çokgen.

1. Noktaları x’e göre sırala (eşitlikte y’ye göre).
2. 1. tur (soldan sağa): bir yığın tut. Her yeni nokta için: yığının son iki noktası ve yeni nokta yanlış yöne dönüyorsa (yön testi ≤ 0) sonuncuyu at; dönüş doğru olana kadar tekrarla. Sonra yeni noktayı ekle.
3. 2. tur (sağdan sola): aynısı; zarfın öbür yarısı çıkar.
4. İki zinciri birleştir (uç noktalar iki zincirde de var; birer kez yaz).

Sıralı noktalar: P1(0,0) P2(1,3) P3(2,1) P4(3,4) P5(4,0) P6(5,2) P7(6,1) · (y yukarı; “doğru dönüş” = çapraz > 0)

1. turun sonucu (alt zincir): P1 → P5 → P7.

• Bir 3B modeli fizik motoruna “dışbükey” diye verdiğinizde motor köşe noktalarının dışbükey zarfını hesaplar ve çarpışmada onu kullanır.
• Unity: MeshCollider.convex = true. Zarf en çok 255 üçgen olabilir; model daha ayrıntılıysa motor sadeleştirir. Hareket eden (Rigidbody’li) nesnelerde dışbükey olmayan ağ çarpıştırıcıya izin verilmez.
• PhysX (Unity ve Unreal’ın 3B fiziği) zarfı Quickhull ile “pişirir”: bu bölümdeki problemin 3B hâli.
• İçbükey nesne (sandalye, kemer, halka)? Tek zarf boşlukları doldurur: sandalyenin bacaklarının arasından top geçemez. Çözüm: modeli birkaç dışbükey parçaya ayırmak. Unreal’ın “Auto Convex Collision” aracı ve yaygın V-HACD kütüphanesi bunu otomatik yapar.

Bu 20 satır + sunum boyunca yazdığımız dört fonksiyon: cross, inside, polygonArea, convexHull.