Opengl’den Directx’e geçiş dönemi

June 18th, 2009 by admin

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.


D3DXMATRIX matRotateY;
D3DXMatrixRotationY(&matRotateY, index);
d3ddev->SetTransform(D3DTS_WORLD, &(matRotateY));

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 =)

Futurama!

June 9th, 2009 by admin

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

Dünya havlu günü

May 25th, 2009 by shultays

Hepimizin kutlu olsun.

Kağıt üzerinde kod

May 12th, 2009 by shultays

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.

Tetris! MSP430F417 üzerinde

May 1st, 2009 by shultays

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.

Uykusuzluk sonucu muhabbetler

April 16th, 2009 by shultays

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ı

Odtü programlama yarışması 2009

April 16th, 2009 by shultays

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 =)

operating system design

April 12th, 2009 by shultays

Anladım ki bana göre değilmiş.

Eski Odtü algoritma yarışması sorusu

April 6th, 2009 by shultays

Geçen yıl finalde sorulan sourlardan birisi o zamandan beri aklıma bir parça takılmıştır. Bir türlü nasip olmadı oturup uğraşmak.

Odtü lü arkadaşların soru için güzel bir hikayesi vardı, şimdi aklımda değil malesef.

Soruda bir input dosyasından dikdörtgen koordinatları okuyoruz (her dikdörtgen için sol-üst ve sağ alt köşenin koordinatları veriliyor). İstenen ise bu dikdörtgenleri tek renk bir kalem ile bir kağıda çizer ve boyar isek oluşan şeklin alanı.

Dikdörtgenlerin boyutlarunda ve koordinatlarında sınır olmadığı için (integer sınırlarında farzedin) “İki boyutlu bir array açayım, dikdörtgen olan yerleri 1 yapayım” gibi bir mantık işe yaramıyor.

Aklıma gelen bir çözüm yolu (ki obvious çözüm gibi bir şey) her yeni eklenen dikdörtgeni öncekiler ile karşılaştırmak ve eğer kesişiyorsa önceki dikdörtgeni kesişmeyen iki dikdörtgene bölmek. Örnek resim:

res11

Mesela soldaki örnekte b dikdörtgeni önceden gelmiş bir dökdörtgen. a ise yeni gelen dikdörtgen. Biz bu b yi şu şekilde ikiye bölüyoruz (Yazının bu kısmında l4d oynamak için ufak bir ara verdim, herkese tavsiye ederim bu oyunu =p)

res2b dikdörtgenini c ve d olarak ikiye ayırdık. Artık kesişme sorunu yok ve alan olarakta aynı alan. Elbette farklı şekilde de bölünebilirdi.

Bu bölme işleminden sonra a yı kalan dikdörtgenlerle (eğer kaldıysa) kontrol edeceğiz. Gerekirse yine aynı şekilde onları da böleceğiz. Her çakışma sonucu ikiye bölünecek diye bir şart yok. Eğer şanslı isek eski dikdörtgen yenisini kapsar ve daha fazla kontrole gerek kalmaz. Veya mesela şu örnek için:

res3Eğer yeni gelen dikdörtgen kırmızı olan ise sadece mavi dikdörtgenin kırmızı içinde kalan kısımlarını çıkartarak (mavi dökdörtgeni bir parça sol tarafından kırparak) çakışmadan kurtulabilirdik. Eğer yeni gelen mavi olan ise ve kırmızıyı bölmeye kalkarsa üçe bölmek zorunda kalacaktık. Bunun yerine algoritmayı biraz değiştirerek yine aynı şekilde maviyi (yeni gelen dikdörgeni) kırparak dikdörtgen sayısını azaltabiliriz. Yine aynı şekilde yeni gelen dikdörtgen eskini kapsıyor ise eskisini listeden çıkartabiliriz, bu durumda hala yeni dikdörtgeni kontrol etmek zorundayız ama en azından toplam dikdörtgen sayımız azaldı.

Yani en kötü ihtimalle her karşılaştırma için bir yeni dikdörtgen oluşturuyoruz. Aklıma gelen şu anlık tek çözüm bu, ama performansı konusunda şüphelerim var. Yani mesela n dikdörgen var ise, n+1 inciyi eklerken her karşılaştırma için 1 artar ise toplamda 2n+1 dikdörtgen olacak. Tabi bu çok uç bir input ve muhtemelen tek bir input dosyası içinde sayısının fazla olması imkansız. Alan hesaplamak içinde en sonunda tek tek bütün dikdörtgenlerin alanlarını toplayacağız.

Son zamanlarda da asıl aklıma takılan böyle bir algoritmanın complexity si ne olur. Yani bir kere O(n^2) den düşük olamayacak (sonuçta her yeni geleni bir öncekilerle kontrol ediyoruz). Ama devamlı dikdörtgenler bölüneceği için n^2 den yüksek bir complexity alması lazım gibi duruyor.

Yapılabilecek başka bir iyileştirme ise dikdörtgenleri sort sağ noktasının x koordinatlarına göre sort edilmiş şekilde tutmak. Eğer yeni dikdörtgenin sol noktasının x koordinatı, eskilerin sağ x ini geçer ise artık kalan dikdörtgenleri kontrol etmeye gerek kalmayacak. Eğer sorted bir şekilde tutar isek dikdörtgenleri linked list yapısında saklamak daha mantıklı çünkü bölünen yeni dikdörtgenler (ve yeni gelen dikdörtgenler) devamlı araya girmeye kalktığında array i shift etme zorluğu yaşamayalım. Bu ayrıntıyıda algoritmaya eklersek bariz bir şekilde iyileştirme sağlayacaktır (eğer bölünme olmasaydı O(nlogn) olacaktı, ama tabi gerçek complexity yi hesaplamak çok daha fazla karıştı =D).

Bu sorunun ikinci kısmı ise çevre hesaplamak idi (sadece şeklin etrafını çevreleyen değil, içerde boşluk varsa o boşluğunda çevresi de hesaba katılacak). Çevrenin tek farkı ise şu. Önce yine aynı şekilde dikdörtgenler kesişmeyecek şekilde oluşturacağız. Sonra her dikdörtgenin çevresini bir toplam çevre değerine ekleyeceğz. Daha sonra, dikdörtgeni bir önceki dikdörtgenler ile karşılaştıracağız, eğer iki dikdörtgen teğet ise ne kadar uzunlukta teğet olduğunu bulacağız ve o değerinin iki katını toplamdan çıkaracağız.

res4 Mesela a ve b nin çevreleri A, B ise ve sarı çizginin (teğet olan kısım) uzunluğu L ise toplam çevre.

Çevre = A + B - 2*L

olacak.

Henüz daha iyi bir çözüm aklıma gelmedi, olabilir diye umuyorum. Algoritmayı koda dökmeye hep üşeniyorum. Çok fazla ağır gibi durmasada iki dikdörtgenin karşılaştırılması ve bölünmesi baya zor olacak gibi duruyor, bir çok ihtimal var sonuçta. Belki daha iyi bir tane bulunabilir bilmiyorum. Odtü finalinde çok kötü bir algoritma yazmıştım, kesişen her iki dikdörtgen için kesişen alanı çıkarıyordu. Ama mesela 3 dikdörtgen aynı noktada kesişirse o durumda patlıyordu. Belki bu algoritma biraz geliştirilerek doğru sonuç verecek bir şeye çevrilebilir belli olmaz.