Octree soruları

[The_Cuisinart]

Selamlar.

İnceden space partionining işine giriyorum ve görünen o ki terrain için octree kullanacağım.Yalnız octree ile ilgili aklıma takılan ve adam gibi cevap bulamadığım bazı sorular var:

1-Şimdi söz konusu bayağı büyük bir terrain var diyelim,içinde 100000 üçgen olan.Bu büyük terraini bir root küp(node) içine koyuyoruz,sonra mesela bunu en son nodelerin içinde 50 üçgenden az oluncaya kadar bölüyoruz.Şimdi diyelim n kere bu recursive bölme işlemi gerçekleşti.
Herşey iyi güzel de,bunun bir de her frame başında frustum cullingi var,"rootun çocuklarını cull et,eğer bir çocuk node frustumu sadece kesiyorsa bunun çocuklarını cull et,ondan sonra onların çocuklarını ... vb." bu oldukça uzun zaman alan bir işlem gibi gözüküyor ilk bakışta.Oluşan node sistemini frustum cullingden geçirmenin daha kolay bir yolu yok mudur?(Mesela haritayı bir kaç parçaya bölsek ve sadece kameranın o framede içinde bulunduğu node'u ve onun çocuklarını teste soksak gibi birşey düşündüm ben en başta)

2-Bir de şöyle bir durum kesinlikle olacaktır:Bir üçgenin bir vertexinin bir nodeda,diğer ikisinin hemen yanındaki komşu nodeda olması,üçgenin iki hatta daha çok node içinde olması.Bu duruma karşı ne yapılabilir?Ben üçgeni içinde bulunduğu tüm nodelara dahil etmeyi düşünüyorum ama bu durumdaki tüm üçgenleri birden fazla çizdirmek israf olur.Bir kere çizilen üçgene bir daha çizilmesin diye bir flag koymak buna bir alternatif olabilir diye düşünüyorum,ama bu durumdaki bir sürü üçgenin,poligonun her frame flag'ıyla uğraşmak pek de pratik gibi durmuyor.

Aslında bu octree mevzusunu gametutorials.com'da çok güzel bir şekilde anlatıyorlardı,ama site paralı oldu,zamanında indirdiğim örnekler de harddiskin karanlıklarında yok olup gitti çoktan.İşin teorik yönü kolay ama implementasyona gelince kazın ayağı biraz farklı oluyor(perdeli).Öte yandan da bir buçuk senelik ÖSS arası çok şey alıp götürmüş benden;eski kodlarımı saatlerce boş bakışlarla süzüp anlamaya çalışıyorum,yazar burada ne demek istemiş hesabı.Bir de bir sürü pixel shader dı,vertex shader dı coşmuş ortalık...

Neyse, önerilerinizi bekliyorum,herkese iyi çalışmalar.

[Black_Knight]

Hmmm.
Kendi deneyimlerimden cvp veriyim.
Octree diil quadtree kullaniyorum ama pek farketmez.
Benim arazi 256x256 idi bir zamanlar yani 256 x256x2 ucgen 131k tane ediyor.
Sonra bunu boluyordum iste 3 kez falan.End nodelar 2000 tane ucgen kaliyodu.4 kez bolunce 500 tane kaliyor.Duruma gore degistirilebilir.
Cullingde ise performans sorunu yasamadim.Cizerken her nodeun bounding box u var ben bounding sphere de eklemistim oyle test ediyorum.
Eger cok bolersen yani her nodeda 50 ucgen birakirsa belki yavaslar ama bence 50 ucgen cok az bir node icin.
2. soru icin ben ucgen ler nodelar icindemi diye kontrol etmedim arazi heightmap oldugu icin x,z yonlerinde hep ayni araliktalar zaten.vertexler nodelar icindemi diye kontrole ettim.sadece kenarlardaki vertexler 2 nodeda birden oluyor.Ama dedigim gibi cok bolmedigim icin memory sorunu olmadi.

[The_Cuisinart]

Şimdi quadtreede bildiğim kadarıyla tüm arazi x-z ekseni üzerinde bölünüyor öyle değil mi? Yani büyük bir kübü git gide daha ufak parçalara ayırarak böyle bir sürü ince uzun dikdörtgen prizmaları elde ediliyor ve bunlar teste sokuluyor.(En azından benim quadtreeler ile ilgili okuduğum tutorialler buna benzer birşeyler diyorlardı.)

[3ddreams]

http://rapidshare.de/files/3445901/Octree2_OGL.zip.html

[The_Cuisinart]

3ddreams, gerçekten çok teşekkür ederim,çok makbule geçti doğrusu

[MD-C]

Frustum, sırasında eğer büyük hacimli bir OccTree parçası yakarlarsan... child'ları da test et... Yani iyi bir hiyararşi yap! Bir hücre parçası içinde çok az sayıda poligon görünüyorsa ve görünmeyenleri elemek istiyorsan eğer... Görüş alanına giren Hucreyi saptadıktan sonra... istersen bir alt hücreye geçercis yani polginonun bulunduğu Sub Boinding BOX'ı bul ve o hücre içindeki tüm poligonlerı test et... böylece büyük bir hücre içinde sadece görünen 3-4 poligon için tüm hücreyi çizmene gerek kalmaz!

[Black_Knight]

Evet en tepeden yani root node dan basliyorum.sonra yavas yavas iniyosn iste asagi gorunen end nodelari ciziyosun.Eger parent lardan biri gozukmuyorsa zaten alttakilere bakmiyosun bile.
Son biside ben quadtree yaparken olusan diktorgen prizmalarani uzun uzun birakmadim hepsini x,y,z yonlerinde tam olarak ucgenleri kapsicak sekilde ayarladim.Boylece bosuna fazladan cizim olmuyor.

[leblebi]

Unreal 2 ve 2.5 un yaptigi sekilde de yapabilirsiniz cunku frustum culling yalniz basina cok kazandiramayabilir...

Yani, map editor'de heightmapin yani sira occluder objeleri koyun(mesela tepelerin icine vs.), quadtree nodelarini once frustum ile sonra occluderlar ile cull edin. Eger frustum cull codeu varsa bunun ustune occluder cull eklemek kolay olacaktir zaten. (Occluder ile de bir "culling frustum" olusturucaksin obje culling frustumun icindeyse cizmiyceksin. Yani ayni fonksiyonun zit return degeri)

Unreal terrainler icin uniform partitioning kullaniyo ama quadtree daha efficient olabilir tabii ki. Tahmin ediyorum ki elemanlar denemislerdir ve fazla bi kazanc olmadigini gormuslerdir.

[lucifer]

Hahaha, iste hastasi oldugum konu, octtree'ler

buyuk bi haritada octtree yapinca node'larin bounding boxlari ucgenlerin ortasindan mutlaka geciyo. Ucgeni daha once cizdim mi diye bir flag tutmak olmuyo, cunku o zaman her ucgeni cizmeden once bi 'if' yapmak gerekicek. Ben octtree'leri rendering icin degil collision hesaplamak icin kullanmistim (render icin de kullandim ama performans artisi yerine azalmasi oldu). Neyse, collision hesaplarken de render ederken de ayni ucgeni iki kere cizmek/collide etmek problem olusturacak. Ben bounding box'larin ucgenleri kestigi yerlerde ucgenleri bounding box'a gore clip etmistim. Bu durumda ortasindan bounding plane gecen bir ucgen, uc parcaya bolunuyor (niye uc.. cunku ucgeni ikiye bolersen ortaya iki degil uc ucgen cikiyo). ucgenlerden biri bir node'in icinde diger ikisi diger node'in icinde kaliyor, boylece level'i load edip octtree'yi olustururken level'daki ucgen sayisini bi %20 falan arttirmis oluyorsun, ama tum ucgenlerin sadece ve sadece 1 node'in icinde kaliyor.

Bu collision hesaplanacak ucgen sayisini dusurmek icin yaptigim octree'de mukemmel calisti... FPS birseydi iste, kapali ortamda shooter. ama render ederken soyle bir problemin oluyor o zaman, node'larin icindeki triangle'ler karman corman oluyor.. onu da triangle'leri loading sirasinda shader'e gore falan yeniden sort ederek duzeltebilirsin herhalde. Ama su var, elinde render edilecek 40 tane node olsun. levelda da toplamda 20 tane shader olsun. Her node'a ortalama 10 tane shader dussun.. (bunlar hayli mantikli sayilar)... Sonucta sen 40 node'u cizmek icin 400 kere shader switch yapacaksin, bu da performansini cok kotu etkileyecek. karmakarisik vertex buffer'larin olacak...etc. Ben ondan dolayi biraz daha degisik birsey dusunmustum... modelling sirasinda tum room'lari el ile mantikli sayida ucgenleri olan obcelere boluyorum (maya). sonra bu obcelerin bounding box'larini frustum cull'a sokuyorum... boylece shader switch sayisi cok daha azalmis oluyor.


Tabii bunlar 4 yil oncesinde yaptigim seyler, simdiki kartlarda ve grafik detayinda daha optimal cozumler olabilir.

Bir ara ugrasip inglizce yazmistim, surada var : http://www.geocities.com/lucesferre/octtree.htm

Suradan da installer halinde luces'i download edebilirsiniz (reklam yapayim biraz): http://www.geocities.com/lucesferre/luces/luces_information.htm. Galiba F4'e (yada F3'e, isyerindeyim deneyemiyorum) basinca octree bounding box'larini cizdiriyo (cizmezse diger exe'yi dene), diger f3/f4 ile de ucgenleri, bir kere basinca normal modellenen halleri ile, bir kere daha basinca da bounding box'a gore bolunmus halleri ile ekrana basiyor.

Her eve bir maya kampanyasina destek : www.her.eve.bir.maya.com.tr

[The_Cuisinart]

Cevap için sağol lucifer;
Şimdi ben terrain için triangle strip kullanıyorum,yani terraine ait vertex array içerisinde,vertexlerin indexleri benim için çok önemli,zira onları ayrı bir arrayda tutup glDrawElements'e veriyorum.Senin bahsettiğin üçgen clip etme metodunu biliyorum(evet üç tane üçgen olacak ),clip etme yöntemine açıkçası pek sıcak bakmıyorum.Şimdi hem dediğin gibi,arazi biraz büyükse üçgen yükünü aşırı bir şekilde arttıyor,bir de bahsettiğin karmanlık çormanlık durumu var tabii ki.Bir üçgenden üç yeni üçgen türüyor ve bunları vertex arraya ekleyip mantıklı indexlerde olmalarını sağlamak gerekli.Bu bir süre sonra içinden çıkılmaz hale gelebiliyor.Ayrıca texture koordinatları falan birbirine giriyor.Tabii bir de yarın öbür gün bir LOD algoritması eklemeyi düşünsem,o zaman da yeni sorunlar çıkartabilir diye düşünüyorum.Niye triangle strip diye soracak olursan hız derim,normal GL_TRIANGLES metodu ile 51x51 vertexlik,100x100 birimlik arazi 90 fps ile çiziliyır,GL_TRIANGLE_STRIP ile 200-300 fps arasında değişiyor.

Benim arazi vertexlerinin x ve z koordinatları arasında sabit mesafeler var(mesela 2.0 birim),ancak y koordinatları için noise function kullanıyorum.Octree için bölme yaptığım zaman eğer x veya z eksenlerinde bir üçgeni ortadan bölme durumu olursa,nodeları sabit bir miktarda genişletip veya küçültüp,x ve z eksenlerinde bu üçgen bölme sorununu aşıyorum.Çünkü vertexler arasındaki mesafeler sabit...
Ama y ekseni için bu mümkün değil,vertexlerin y koordinatları zaten rastgele olsun diye noise ile hesaplanıyor,bu yüzden bir node'u y ekseninde tüm üçgenleri kapsasın diye küçültünce/genişletince bir anda yeni yeni bölünmeler meydana geliyor.

Aslında gametutorials.com forumlarında bu konu ile ilgili bir soru sordum,eloğlu "Baba sen flag,klip için kasma bırak üçgenler duplicate çizilsin,daha hızlı olur" türünden şeyler dediler.Tabii deneyip görmek lazım,farklı durumları bir karşılaştırmak gerekir.

Ee,bu arada cahilliğimi mazur gör,