Category Archives: Algoritma

Biraz internette bulduğum bir collision detection algoritması üzerine bahsedeceğim. Şu sitede tanıştım kendisi ile

http://spiritking.tripod.com/cdtut.htm

Algoritma hareket eden insanı bir silindir olarak düşünüyor. Mantık olarak çok güzel düşünülmüş, performansıda gayet iyi gibi duruyor. Lakin sitedeki implementation biraz kusurlu olmuş ve algoritmanın biraz eksiği var gibi.

Collision detection için gerekli olan verilerimiz, kamera koordinatı, silindirin alt ve üst sınırlarının y koordinatları ve bir de silindirimizin yarı çapı. Ayrıca polygonlarımızın koordinatları, normal leri lazım olacak.

Şu resmi bir inceleyelim. (Yukarıdaki sayfada olduğu gibi benim programımda da y ekseni yukarısı olarak tanımlanmış)

Yukarıdaki resimde 3 tane polygonumuz var. Kamerada silindir ile gösterilmiş. En sağdaki polygon silindir ile collision yapmış gibi duruyor (daha kolay anlaşılması için o üçgeni hafif eğimli bir duvar gibi düşünün bizde üzerine doğru yürümüşüz) Sahnenin z yönünde bir kesini görüyoruz. Collision detectionun ilk aşaması silindirin alt ve üst yüzeylerinden geçen 2 tane düzlem düşünün. Bütün polygonları bu iki düzlem arasında kalan kısımlarını kullanıyoruz. Mesela soldaki polygon un hem üstünden hem altından kesmişiz ve sonuçta silindirin yükseklik sınırlarında kalan bir beşgen ortaya çıkmış.  Ortadaki polygon tamamı iki düzlem arasında kalmış, o yüzden bir kesintiye uğramıyor. Sağdakininde sadece alt kısmı kesilmiş ve gene ortaya bir üçgen çıkmış.(eğer bir polygon bu iki düzlemin tamamen ters taraflarında ise tamamen göz ardı edilecekti)

Ortadaki resim sadece polygonların kesildikten sonraki halini gösteriyor. Görebileceğiniz gibi kestiğimiz kısımların collision yapabilmesi imkansızdı, sadece bu parçalar collision ihtimaline sahip.

Burada kesme işleminin nasıl olduğunu anlatayım. Verdiğim sitedeki örnekten biraz daha farklı bir yol izledim, oradaki örnek hatalı gibi geldi ve bazı durumları atlayabiliyordu.

Kesme işlemi alt ve üst sınır için iki kere yapılıyor. her abc üçgen için abc üçgeni için 3 tane doğru parçamız var, ab bc ca. Her doğru parçası için şu algoritmayı uyguluyoruz.

• Eğer her iki noktada doğru tarafta ise, ikinci noktayı al.
• Birinci nokta doğru, ikincisi yanlış tarafta ise doğru parçasının sınır ile kesiştiği yeri al.
• Birinci nokta yanlış, ikincisi doğru tarafta ise önce doğru parçasının sınır ile kesiştiği yerisonra ikinci noktayı al.
• Her iki noktada dışarda ise hiç bir nokta alma.

Bu algoritma sonucu aldığımız noktalar üçgenin plane in doğru tarafında kalan kısmı olmuş oluyor. Mesela yukarıdaki resimde soldaki üçgen için

Önce üst kısım için clip yapıyoruz. a dan b ye giderken her iki noktada doğru tarafta, sadece b alınıyor. b den c ye giderken b içerde c dışarıda bc doğru parçası ile sınırın kesiştiği yeri (bc’) alıyoruz. c den tekrar a ya giderken ilk nokta yanlış ikincisi doğru yerde olduğu için kesişim noktasını (ca’) ve sonra a yı alıyorız. sonuçta yeni oluşan şekil. b bc’ ca’ a dörtgeni oluyor. aynı işlemi bu sefer alt sınır için yapıyoruz ve sonuçta bc’ ca’ a b(bc’)’ ab’ beşgenini elde etmiş oluyoruz. Bu algoritma sonucu elimizde en iyi ihtimalle 0 nokta  (tüm noktalar dışarıda ise) en kötü ihtimallede bir beşgen oluşacak.

En alttaki resim algoritmanın güzel tarafını gösteriyor. Bütün polygonları kestikten sonra bu sefer y ekseni yönünde bakam bir kesit aldığınızı düşünün. Her şey iki boyuta iniyor ve silindirimiz bir çembere dönüşüyor. Eğer bu çember içinde kalan bir polygonumuz varsa bu onun silindir içinde kaldığını ve kamera ile çarğıştığını gösteriyor!

Peki 2 boyutlu düzlemde bir çember ve doğru parçasının (artık şekilleri doğru parçası array i olarka düşünelim =) ) kesiştiğini nasıl anlayacağız? Bunun için biraz vektör bilgisine ihtiyaç var. Sitede verilen örnek programın bu kısmı düzgün çalışıyor, açıklamasına şuradan bakabilirsiniz.

http://local.wasp.uwa.edu.au/~pbourke/geometry/pointline/

Burada farklı olan tek şey eğer doğru üzerindeki nokta doğru parçası dışında ise biz o noktaya yakın olan sınırı alıyoruz.

Eğer çemberimiz şekil ile kesişiyorsa kişiyi hareket ettirmek durumunda kalıyoruz. Burada iki ihtimal var. Ya üçgenimizin üzerine tırmanırız (eğer eğim uygun ise) veya silindiri üçgen ile kesişmiycek şekilde uzaklaştırırız.

İkinci durum daha kolay olayı, iki boyutta düşünürek halledebiliyoruz. Eğer aradaki uzaklık a ise, çemberi r – a kadar hareket ettiriyoruz ve sorun çözülüyor.

Birinci durumda (verdiğim sitede yeterli anlatılmamış, eksik kalmış gibime geldi) ise işler biraz daha karışık. Eğer üçgenin eğimi uygun ise üçgenin üzerine tırmanmamız gerekiyor.  Öncelikle çemberin kesişen nokta yönündeki uç noktayı (a boktası) buluyoruz. Amaç bu a noktasını yeterince yukarı kaldırmak böylece collision u engellemek. Bunun içinde üçgen üzerinde olan a’ noktasını bulmak lazım. Bunu bulmak içinde şu formülü kullandım.

http://gpwiki.org/index.php/MathGem:Height_of_a_Point_in_a_Triangle

Bu linkte procedure kısmındaki formül ile a’ noktasını buluyoruz. Bu nokta üçgen üzerinde ve a ile aynı x-z koordinatlarına sahip (formülde z ve y harflerini değiştirin, bizim aradığımız y). a’ noktasını bulduktan sonraa ile arasındaki yükseklik farkını buluyoruz ve silindirimizi o uzunlukta yukarı kaldırıyoruz.

Bütün sorunları bu şekilde çözemiyoruz malesef. Bir diğer problem ise tamamen yatay düzlemlerde oluşuyor. Mesela yüksek bir noktadan düştüğümüzü düşünün. Altımızda ise büyük bir üçgen var, bu üçgen bizim silindirimizin sınırlarına girdiğinde üstten görünüş şu oluyor.

Burada dikkat ederseniz hiç bir doğru parçası çember ile kesişmiyor, ama yine de bir collision var. Bu durumu anlayabilmek için bir test daha gerekiyor. Bu testte çemberin merkezinin üçgen içinde mi değil mi onu arıyoruz. Bunun için abc üçgeni ve n noktasında her doğru parçası için merkez aynı tarafta mı kontrol ediyoruz. mesela ab doğru parçası için önce an vektörünü buluyoruz ve bunun dot product ını hesaplıyoruz, aynı işlemi bc ve ca için de yapıyoruz. Eğer bütün dot product lar pozitif ise nokta çemberin içinde demek oluyor. Bu durumda yine aynı şekilde silindiri bir parça yukarı kaldırarak sorunu çözüyoruz. (şurada ayrıntı açıklama var http://www.blackpawn.com/texts/pointinpoly/default.html)

Ama maalesef bu da yeterli olmuyor =) Bir diğer (ve oldukça büyük bir sorun) ise eğer çok hızlı hareket ediyorsak ne olacağı. Bu durumu henüz programa eklemedim ama şu şekilde çözülebilir. Önceki koordinatımızdan yeni koordinata bir doğru parçası çizdiğimizde eğer bu doğru parçası polygon ile kesişiyorsa collision oluyor demektir. Ama bu tam yeterli bir çözüm değil o yüzden henüz eklemek istemedim. Aklıma daha iyi bir çözüm geldiğinde onu eklemeye çalışacağım.

Programın son hali

Kaynak dosyaları

(ek: f tuşunu basılı tutarak uçabiliyorsunuz =D)