Evin yeni üyesi, o kadar tatlı bir şey ki
Uyurken filme çektim. Uyandırmak istedim ama bir türlü uyanmadı sonrada kıyamadım. Esnemesini yakalayabilsem keşke =)
http://www.youtube.com/watch?v=Hnf8Jfbir6Q
Bu da daha haraketli olduğu bir film.
http://www.youtube.com/watch?v=O6FG7DIwhGQ
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.
(ek: f tuşunu basılı tutarak uçabiliyorsunuz =D)
Yavaş yavaş directx ile örnekleri incelemeye ve kendi çalışmalarımı yapmaya başladım.
Directx kullanırken aslında opengl i yanlış kullandığımı farkettim. Misal opengl de bir şekil çizerken
glVertex3f(…);
glVertex3f(…);
glVertex3f(…);
gibi 3 tane koordinat veriyordum. Bu fonksiyonlarda bu koordinatları ekran kartına yolluyor ve çizim işlemlerine başlıyordu. Her frame için tekrar tekrar yolladığımız için çok fazla yük biniyormuş.
Directx öğrenirken ise bu koordinatları (vertex leri diyeyim artık) bir vertex buffer ına bir kere yazıyoruz ve daha sonra bu buffer ı ekran kartı hafızasına kopyaladığımızı gördüm. Daha sonra istediğimiz zaman directx e “koordinatları bu bufferdan al artık” diyerek ekstra bir işlemci-ekran kartı arasında veri akışı olmadan çizimlerimizi yapabiliyorduk.
Yanlış hatırlamıyorsam opengl de de vardı böyle bir işlem (illa vardır yani =) ). Lakin bu özelliği kullanmayınca çok daha küçük polygon sayıları ile uğraşıyordum. Directx de ne kadar fazla polygon kullanabildiğimi görünce ufak bir şok yaşadım.
Bir örnek ile göstereyim. Aşağıda ki örnekte 512*512*2 yani yaklaşık 525 bin tane polygon var. Ve gayet akıcı bir şekilde çalışıyor.
Binary dosyalar
Kaynak Dosyalar
Shader değiştirmek için 1-9 tuşlarını kullanabilirsiniz.
Sol üst resim haritanın normal renkleri. Sağ üst resim ise siyah beyaz. Siyah beyaz olması için pixel shader kullandım. Kabaca pixel shader her pixel ekrana çizilirken ekran kartı üzerinde çalışan o pixelin rengini veren program(cık). Mesela ilk resim için pixel shader o an kullandığımız texture üzerinde gerçek rengi döndürürken, siyah beyaz yapabilmek için (r + g + b)/3 rengini döndürüyoruz. Pixel shader HLSL ile yazılıyor, ve .fx dosyaları içinde bulabilirsiniz.
Sol alt resim gene farklı bir pixel shader ürünü. O anki görüntünün emboss effect li halini veriyor. Son resim için durum biraz daha farklı. O post processing ile yapıldı (aslında hepsi post processing ile yapılı benim örneğimde ama son resim için post processing zorunlu =)). Postprocessing sahnenin ekrana değilde bir buffer a çizilmesi ve daha sonra bu buffer ekrana çizilirken pixel shader ile oynamalar yapılması işlemi. Burada da resmin x koordinatının sinüs üne göre y koordinatını hafif kaydırıyoruz ve böyle dalgalı bir görüntü elde etmiş oluyoruz.
Ayrıca dikkat ederseniz t3.x diye hayvani boyutta bir dosya var. Bu arazinin model dosyası. 3d max ile oluşturdum. İşleri baya basitleştiriyor, .x dosyasını yükledikten sonra tek bir fonksiyon çağırarak kendisini çizebiliyoruz. Lakin çizmek dışında pek bir işlemimiz yok tabi. Mesela collision detection yapabilmek için .x dosyasını yüklüyorum, daha sonra bunu tekrar normal ram e kopyalıyorum anca o zaman kullanabiliyorum =)
Bu ara pek haşır neşir olduğum siteler
http://www.directxtutorial.com/ başlangıç için harika bir kaynak
http://www.applicachia.com/ çok güzel örnekler var. Benim örnekte aslında buradakilerden bir tanesinin üzerinden gidiyor =D
ve google tabiki =)
Daha yazılacak çok şey var ama aklıma gelenler bunlar. Geliştirdikçe daha ayrıntı olarak anlatacağım umarım
Gerçekten sancılı bir dönemmiş. Henüz directx e yeni başladım ve opengl den ne kadar çok farklı olduğu görülebiliyor.
En başta glut tarzı bir çok işi basitleştiren bir arayüzün (bir adı vardı ama unuttum şimdi) yokluğu hissettiriyor. Bir pencere açabilmek ve bunu opengl e bağlamak glut ile hazır fonksiyonlar ile yapılırken directx de her şeyi biz yapıyoruz. Tabi bu çok daha fazla esneklik sağlıyor ve daha iyi öğrenmemize yarıyor ama en basit uygulamalar için bile fazladan ~200 satır kod anlamına geliyor. Çoğunlukla copy paste olsa da okunabilirliği feci oranda düşürüyor. Aslında bir ara bunları basitleştirecek bir kütüphane yazmak geliyor içimden ama ondan önce öğrenecek çok şey var.
Bir diğer sıkıntı da opengl de tek bir fonksiyonla yaptığımız şeylerin directx de çok uzun sürmesi. Mesela glRotatef yerine şöyle bir şey diyoruz.
[code language='c++'] D3DXMATRIX matRotateY; D3DXMatrixRotationY(&matRotateY, index); d3ddev->SetTransform(D3DTS_WORLD, &(matRotateY)); [/code]
Bizleri düşünen birisi bunun için hazır bir kütüphane yazmış, çok hoş duruyor ama henüz kullanma fırsatım olmadı.
http://www.adamdawes.com/programming/windows/directx_matrixtransforms.html
Bir diğer zorluk da bana sanki directx için daha az kaynak var gibi geliyor. opengl de herhangibir konuda bir yığın örnek bulunabilirken directx’de bu durum daha sıkıntılı gibi.
Directx te şu an en çok ilgilendiğim konu shader lar. Basitçe tanımlamak gerekirse shader dediğimiz GPU üzerinde çalışabilecek programcının yazdığı uygulamalar. 3 çeşidi var: vertex shader, pixel shader ve geometry shader.
c++ dan farklı bir dil HLSL: ile yazılıyor. Açılımı High Level Shading Language ama gözüme o kadar da ‘high’ gelmedi. Ama bir diğer seçenek olarak assembly ile de yazılabiliyor ki buna göre tabi çok daha yüksek seviye kalıyor tabi =)
Şurada shader lar için basit bir kaç örnek var (ayrıca oyunu da oynayın muhteşem yapmış adam)
http://www.facewound.com/tutorials/shader1/
Öğrendikçe daha ayrıntılı bilgiler vermeye çalışacağım, kendime iyice kavramak için bir yaz süre vardım, fazla bir sayılır ama yazın sıcağında pek heves kalmıyor =)
Herkesin izlemesi gereken bir yapım. Nedense yayından kaldırılmış idi, yakında tekrar dönüyormuş.
http://www.tvsquad.com/2009/06/08/benders-back-baby-new-futurama-episodes-are-in-our-future/
Umarım simpsons lar kadar uzun bir ömrü olur
Hepimizin kutlu olsun.
Evrimsel algoritmalar dersine giren hocamızın bir isteği olmuştu, ilk duyduğumda baya garipsemiştim. Proje kodunun yazılı çıktısını istemişti. Yani o zaman ne kadar saçma bir şey diye düşündüm ama şimdi aslında bir parça mantıklı geliyor.
Yani mesela ben oturup bir program yazarken (daha doğrusu yazmadan önce) uzun süre problem üzerinde düşünmeyi severim. Bu düşünme sürecinden sonrada bir kerede (eğer büyük bir şey değilse) yazmaya çalışırım. Zaten olabilecek hataları kafamdan bulabildiğim için yazma süreci nispeten hatasız olur (yani algoritma olarak hatasız, yoksa hala bol bol yazım hatası yaparım =D). Eğer bir problemle karşılaşırsam düşünme evresine geri dönerim.
Yani böyle bir durum için ideal olabilir, eğer bir başkasının kodunu inceleyeceksem (hele buda proje gibi büyük bir şey ise) çıktı almak iyi bir fikir olabilir. Mesela operating system design projesinde az zaman harcamadım ekran başında o kernel kodlarını çözmek için.
Şimdi projeyi çıktı alınabilir uygun bir formata sokmaya çabalıyordum oradan aklıma geldi =)
Evrimsel algoritmalar projeside bir parça yalan oldu gibi. Şu an nispeten çok daha kısa sürelerde (1 saat ^^) 25 milyona kadar iniyor fitness değerlerim ama ondan sonra çok yavaşlıyor. 1-2 gün beklerse heral 20 milyonu bulacak ama bir noktadan sonra dahada ineceğini sanmıyorum. Yani sonuçta az sayıda ki üçgenlerle ne kadar elde edilebilir bir resim bilemiyorum.
Bir çözüm yolu resmi parça parça oluşturmak olabilir. Önce tüm resim için algoritma çalışır ve bir anahat görüntüsü elde edilir. Sonra daha ufak parçaları oluşturmaya çalışırız, bu anahat resmi de arkada kalır. Bu parçalar gittike küçültülür ve sonunda düzgün bir resim elde edilir. Ama üçgen sayısı kaça çıkar bilemiyorum. Tahminimce 1024 üçgen yeterli olacaktır, buda 72 kb anlamına geliyor. Orjinal 512×512 resim 768kb ki arada ciddi fark.
Microcontrollers & Microprocessors dönem projesi. Aslında proje olarak sadece led lerden ekran yapmak ve bir kaç basit uygulama düşünmüştüm ama sonradan tetris fikri aklıma geldi.
4 adet 5×7 led matrix kullanıyor (LMD20057BSR). Mikro işlemci olarak msp430f417 var. Bilgisayar bağlantısı sadece güç için kullanılıyor, yoksa vcc ve gnd bağlanınca kendi başınada çalışacaktır.
Asıl istediğiğim LCD bir ekranı bu işlemci üzerinden çalıştırabilmekti ama malesef hiç o tip bir şey bulamadım. 3 renkli led matrixler bile satılmıyordu.
httpv://www.youtube.com/watch?v=yJeE6TDqXxw
http://www.cclub.metu.edu.tr/yarisma/2009/
sonuclar Finalistler açıklanmış, bu sene de odtü ye gidiyoruz bakalım ^^ Geçen senenin aksine iyi bir grup kurduk bakalım umutluyuz ama oraya gidince durumlar nasıl olacak.
Doğrusu öneleme sorularını biraz özensiz bulmuştum. Geçen sene ki neredeyse bütün sorular bir cinlik gerektiriyordu, bu sene ise 6 sorudan 3 ü çok basit bir biçimde çözülebiliyor. 1 tanesi ise verilen kısıtlamalarla çözülebilir gibime gelmedi. Diğer iki sorudan birisi baya meşhur bir problem, google da arama yapılınca çözüm yardım alınabilecek bir şeydi. Doğrusu tek bir soru benim hoşuma gitti =)
isa:
genetik algoritmalarda iş yok ya.
Bir Garip Büyücü:
ya iyiler aslında da
benim problem uygun değil o kadar
veya uygun ama genetik algoritma da ancak bu kadar çözüyor
isa:
ay lav ai
Bir Garip Büyücü:
ay lav brut fors
isa:
ayı