Ayrıntı Düzeyi (Level of Detail) – Bilgisayar Kavramları

Yazan : Selda Berker

Giriş

Level of detail ( LOD – ayrıntı düzeyi ), CPU ve GPU’nun güçlü olmadığı durumlarda kullanılan popüler bir konudur. Bu fikir high-level bir görüntüye benzeyen, fakat CPU ve GPU tarafında işleme için daha az veri gerektiren bir nesnenin, daha kaba seviyede geometrik sunumunu yapabilmek için kullanılmaktadır. Bazı durumlarda GPU, büyük veri miktarlarının üstesinden gelmek için ayrıntı düzeyini azaltmaktadır. Bununla birlikte, nesnelerin uzaklıkları daima önemli bir kavram olacaktır. 10,000 üçgenden oluşan bir karakter düşünelim, bu karakter gözleyiciye yakınlaştırıldığı zaman gerçekten iyi görünür. Şüphesiz karakterin ışıklandırılması ve dokusunun katılması gibi ayrıntılarla ona değer kazandıracaksınız. Nesnede bulunan çok sayıdaki pikselin, üçgenler sayesinde renklendirilmesi de, karakterin albenisini vurgulayacaktır. Karakter uzaklaştırıldığı zaman ise ayrıntıları tanımlamak zorlaşacaktır. 10,000 üçgen yüzeyde artık çok daha az piksel ile ifade edilecektir. Örneğin, bu karakter 100 piksel ile ifade edilirken uzaklaştırıldığında 10 piksel ile görüntülenebilecektir yani karakter yakındayken bir piksel 10 üçgen ile oluşturulurken karakter uzaklaştırıldığında bir piksel 100 üçgen ile oluşturulacaktır. Ve de her bir pikselin ortalama 100 üçgen tarafından çizildiği 100 piksel durumuna getirilse dahi büyültülmüş piksellerin çoğu zarar görecektir. Bu da sayısal kaynakların çoğunun boşa harcanması demektir. Level of detail, gözleyici nesneyi yakınlaştırdığı zaman, üçgenlerin çoğunu sağlamak için tasarlanmıştır. Aynı şekilde nesne gözleyiciden uzaklaşırken de sadece birkaç üçgen sağlanacaktır. Yani ayrıntı düzeyi sayesinde tersi bir durum sağlanarak sayısal kaynakların boşa harcanmasının önüne geçilmeye çalışılmaktadır. Bu değişim ile üçgenlerin sayısı mümkün olduğu kadar korunmaktadır.

Level of detail – ayrıntı düzeyinin, bilgisayar grafiklerinde kullanılan birkaç kategorisi vardır. “Sprites” ya da “billboard”lar nesnelerin karmaşıklığını azaltmak için kullanılırlar ve 3D yani üç boyutlu nesneleri 2D şeklinde sunarlar. Örneğin, ağaçlar tipik olarak karışık bir doku ile bir X konfigürasyonunda kesişen dikdörtgen çifti olarak çizilirler.

Diğer bir örnek ise, bir otomobil yarışındaki tribündür. Seyirciler genellikle kamera ile karşı karşıya gelecek şekilde dikdörtgen billboard sütunları olarak çizilirler. Fakat bu da dikey axisisin dönmesini engellemektedir.

“Discrete LOD”, aynı nesnenin çoklu sunumunu yaratmak için kullanılan bir kavramdır. Her ardışık sunum, bir öncekinden daha az detaylandırılır, fakat sunumların sayısı, az bir sayıdır. “Switch node” – anahtar düğüm, sunulan çizimleri ayırmak için kullanılır. Ayırma, bir göz noktasından bir LOD merkezi arasındaki mesafeye dayandırılarak yapılabilir.Üçgen hesapları ile birbirini takip eden ardışık modeller arasındaki en tipik fark ise daha geniş olmalarıdır. Ayrıca çizimciler her bir modeli ayrı ayrı üretmektedir, bu da bu işlem sürecinin daha fazla zaman alması demektir. Yani Discrete LOD, daha fazla yer ve daha fazla zaman gerektirir.

“Continuous LOD” , bir nesnenin farklı – yeniden sunumlarının üretimini otomatikleştiren bir uğraştır. Triangle mesh’ler – üçgen ağları için, nesnenin şekli korunmaya çalışılırken bir zamanda üretim, birkaç üçgeni yok etme anlamına gelir. Bu işlem, “triangle mesh decimation” – “üçgen ağ kıyımı” olarak da bilinir. Continuous level of detail içerik olarak discrete LOD ile aynıdır, fakat Discrete LOD’ta modeller kullanılırken, CLOD’ta üçgenler kullanılmaktadır ve üçgen hesabı modellere göre çok daha ufaktır. Sunumlar genelde prosedürlere kapalı olarak üretilirler. Üretim, iyi bir koordinat yapısı gerektirir, dolayısıyla da bazı durumlarda kullanımı zor olabilir.

“Infinite LOD”a, bir ağdaki üçgenlerin rastgele seçilmiş bir numarasını üretebilmek için başvurulur yani düzgün bir şekil yaratmaktadır. Nesnenin sunulan bir yüzeyi verilir ve çalışma zamanında bir alt bölüm metoduna başvurularak yüzey döşenir. Oyun konsolları üstündeki güçlü işlemciler, yüzey sunumunda iyi bir alternatiftirler, fakat yüzey yaratma modelleri hala CAD/CAM krallığında gözüküyor ve oyun geliştirilemiyor.

Çalışmamızda, level of detail – ayrıntı düzeyini daha kapsamlı anlatabilmek için bu konuları ayrı ayrı diğer bölümlerde ele alacağız.

Billboards

“BillboardNode” sınıfı billboardları destekler. Ara yüzü şöyledir:

Billboardlar sadece model alanındaki vektörlerin dönüşünü kısıtlar. Yönlendirme bir kamerayla alakalı olarak yapılır. Böylece siz, ya kamera kurucusu olursunuz ya da AlignTo komutuna bağlı olarak onun dediklerini uygulamak zorunda kalırsınız. Billboard hizalama “UpdateGS” esnasında olur. “BillboardNode” sınıfı, UpdateGS versiyonu olan “Spatial” olarak adlandırılan, “UpdateWorldData” sanal fonksiyonunu geçersiz kılar. Uygulaması şöyledir:

Burada Spatial::UpdateWorldData, onun ailesinin evrensel dönüşümlerine ve lokal dönüşümlerine dayanan billboardların evrensel dönüşümlerini hesaplar. Şunu fark etmeliyiz ki, fonksiyonun dalları update edilmeden, değiştirilmeden önce fonksiyon Node::UpdateWorldData olarak adlandırılamaz. BillboardNode’un dalları, billboard kamera ile hizalanana kadar update edilemezler.

Göz noktası (eye point), billboardun model alanına tersi, devriği şeklinde dönüştürülür. Billboard düşüncesini uygulamak için, lokal rotation billboardu doğru bir şekilde yönlendirmeyi uygulamak zorundadır. Billboardu hizalamak için, billboardun model alanının xz-doğrusu üzerindeki kameranın izdüşümü, billboard modelinin y ekseni etrafındaki dönüş açısını inceler. Projected kamera model axsisleri üzerindeyse yani x=0 ve y=0 ise,Atan2, NaN’dan ziyade sıfır döndürür. Böylece bozulma durumlarına ve onun ayrı ayrı üstünden gelmeye çalışmasını engellemeye gerek yoktur. Yönlendirme (orientation) matrisi, döndürme matrisine başvurmadan önce ilk başvurulması gereken matristir. Bu basit doğrudur, çünkü daima world dönüşümlerinden önce, bir düğümdeki lokal dönüşümlere başvurulmalıdır.

y-axisisi etrafında yönlendirme yapıldıktan sonra, geometrik değişim, billboard düğümünün dallarına dağıtılabilir.

Parçacıkların Görüntülenmesi

Bir parçacık yani particle, bir boyut ve alandaki bir lokasyon ile değerlendirilir. “Size – boyut” niteliği, parçacığı oluşturan noktalardan çıkarılmaktadır. Parçacıkların toplamı bir parçacık sistemine aittir parçacıkların bir seti kapsayan parçacık sınıfı, “Particle system” olarak adlandırılır. Parçacık sistemi, fiziksel simülasyonlar kadar görsel görüntüleme için de oldukça yararlıdır. Veri yönetimi ile alakalı olan parçacıklar için sınıf ara yüzünün bir parçası şu şekildedir:

İlk gözlem şudur ki Class – sınıf “TriMesh”ten türetilmiştir. Parçacıklar daima yüzleri gözleyiciye dönük, billboard kareleri şeklinde çizilirler. Her bir kare iki üçgen ile oluşturulur ve bütün üçgenler triangle mesh sınıfında depolanır. Billboardların üçgenlerden oluşturulmuş karelerle nasıl yapılandırıldığının şekli aşağıdaki şekilde gösterilmektedir. Bununla birlikte, parçacıkların sayısı çoğaldığı zaman, özellikle zamanda etkisiz olunur.

Kamera sağda, üstedir ve yönlendirme vektörleri göreceli olarak R, U ve D‘dir. Parçacıkları döndürme matrisi R ile gösterilmiştir. Parçacıkların model alanı kameraya yerleştirildiği zaman, ölçeklendirme ve yer değiştirme dönüşümleri kullanılmazlar. Parçacık model alanındaki kamera vektörleri: R’ = R^T*R, U’ = R^T*U ve D’ = R^T*D. C noktası, karenin merkezi olan parçacık lokasyonudur. Parçacığın boyutu “∂”dır ve boyut ayarı da “α”dır. Vertexler şekilde gösterilmektedir:

Şekil1: Tek bir parça için billboard karesi

V₀ = C – α∂ ( U’ – R’ )

V₁ = C + α∂ ( U’ + R’ )

V₂ = C + α∂ ( U’ – R’ )

V₃ = C – α∂ ( U’ + R’ ).

Eğer normal vektör gerektiriyorsa, dört vertex aynı miktarda belirlenir:

N₀ = N₁ = N₂ = N₃ = -D’.

İki üçgen indeksi üçlü noktalarla,

T₀ = (0,1,2), T₁ = (0,2,3).

Parçacıkları hareket ettirmeden önce, parçacıkların yapımı içeriğin ilk parçasıdır. “GenerateParticles” çağrısı “Draw” fonksiyonunun yanında yapılmaktadır

Bir efekt nesnesi parçacık nesnesine uygulandığı zaman, yorumlama konusundaki bazı karışıkların üstesinden gelinmelidir. Parçacıkların yapımı için iki giriş vardır, birincisi parçacık lokasyonu ve ikincisi ise parçacık boyutudur. Billboardların görüntülenmesi için parçacıkların vetexlerinin sayısı dört zamanda yorumlanmalıdır. Rendering – yorumlama sistemi bütün vertexler için vertex niteliklerini oluşturmayı bekler. Böyle particle class’taki vertex nitelikleri ile parçacık nitelikleri eşleşmelidir. Bu eşleştirme işlemi, “SetEffect” fonksiyonunun üyeleri olan “GenerateColorRGBs”,”GenerateColorRGBAs” ve “GenerateUVs” fonksiyonları tarafından gerçekleştirilir:

Parçacıklara uygulanan efektler m_spkParticleEffect veri üyesinde depolanırlar. m_spkEffect üyesi, yorumlanır. Böylece bilboradların köşeleri olan bütün vertexler eşleştirilmek zorundadır. Bir kopyalama, bir “clone system boyunca”, efektlerden oluşmaktadır. Renk dizileri ve texture koordinat dizileri billboardun köşeleriyle eşleşenlerden biriyle yer değiştirilmelidir. Bu diziler üretim metotları tarafından üretilirler.

“GenerateColorRGBs” fonksiyonunun, örnek diğer fonksiyonlara uygulaması şu şekildedir:

(Bu örnekte sadece birini göstereceğiz)

Tahsis edilmiş renklerin sayısını “iVQuantity” belirtmektedir. Dört zaman dilimindeki parçacıkların sayısını ise “iLQuantity” belirtir. Parçacık rengi “akPColor”da depolanır. Her parçacık rengi, parçacık sunumunda kullanılan billboardların köşeleri olarak kullanılan vertexlerle eşleştirilen, dört mesh ren slotu içinde kopyalanır. Son ifade de ise efekt vermek için renk dizileri eklenir.

Bu olayda, siz uygulama yapar iken parçacık niteliklerini değiştirebilirsiniz, böylece sadece m_spkParticleEffect üyesi değiştirilmiş olur. Bu durumda, billboard vertextlerinin meshi için niteliklerin yenilenmesine zorlamış olursunuz.

Dıscrete Level of Detail

Discrete level of detail ( farklı ayrıntı seviyeleri), modellerin ufak bir setini oluşturmayı kasteder. Yani kullanılan üçgenlerin sayısı azaltılarak, birçok ufak kopya oluşturulur. Görüntüleme zamanında, bazı mantığa göre, setteki modellerden biri çizmek için ayrılır. Ayrım için kullanılan mekanik bir standart ise göz noktası ile model ile ilgili bir nokta arasındaki uzaklıkta bir LOD merkezi alarak bunu kullanmaktır. Ufak uzaklıklarda, modeli ayırma çözümü çok daha yüksek başarımlara ulaşabilir. Diğer taraftan, büyük uzaklık mesafelerinde model ayırma çözümünde kötü denebilecek sonuçlar elde edilir.

Bütün modellerde olduğu gibi ayırma işleminde de beklemek zorundayız. Burada seçilecek olan modelin alt düğümlerden seçilmesi daha uygundur. Fakat ekran grafiklerini tekrarlama esnasında bütün alt düğümlerle ilgilenmek de istemeyiz. Bunun için de “switch node” kullanılır. “Switch node” sayesinde bir zamanda tek bir alt düğüm – child aktif olur. SwitchNode sınıfının uygulamasının ara yüzü şu şekildedir:

Sadece veri üyesi, active child’ın indeksidir. Eğer active child indeksi, “SN_INVALID_CHILD”) içine yerleştirilirse, çocuğu, alt dalı olmayan switch node seçilir ya da çizilir. Başka bir deyişle, sadece active child seçilir ya da çizilir. Şunun farkına varmalıyız ki yukarıdaki örnekte, geometrik durum updateleri ve yorumlama durum updateleri için bir override sağlamadık. Bunun anlamı ise şudur; “UpdateGS” ve “UpdateRS” metotları, bütün çocukları sadece biri aktif olsa dahi geçersiz kılacaktır.

Farz edelim ki bir “UpdateGS” metodu, bir ekran hiyerarşisini ve kullanılan bir switch node’u geçersiz kılıyor. Eğer switch node geçersiz kılınırsa sadece aktif olan child çağırılacaktır, sonra diğer tüm çocuklar dönüşümlere sahip olacaktır. Yeter ki, bu çocuklar pasif kalsın, bu problem değil. Şimdi faz edelim, aktif yapmak için farklı bir child seçmeye karar verdiniz. Bu durumda mutlaka mevcut geometrik konumunu bilmemiz gerekiyor. Böylece child üstünden UpdateGS metodunu çağırabiliriz. Hemen sonraki update de bir önceki aktif olan child’ı değiştirebiliriz. Bu zamanda asla yeni aktif child’ın bir update gerektirmediğini bilemeyiz. Sonra tekrar, eğer diğer işlemler switching arasında oluyorsa yine aktif child’ın bir update gerektirdiğini bilemeyiz. Burada bildiğimiz ve emin olduğumuz tek şey, değiştirme yaptığımız zaman “UpdateGS” metodunun çağrıldığıdır. Maalesef, eğer çocuklar geniş alt ağaçlar – subtrees ile karıştırılmışsa, ihtiyacın olmadığı halde çağırılan UpdateGS metotları ile birçok zaman boşa harcanmış olacaktır. Buna dikkat etmeliyiz. Bu yüzden de, override edilmemiş UpdateGS metotlarını seçmeliyiz ve önceki updateleri alarak onların ekranda gidişatını takip etmeliyiz. Eğer cüretkâr davranmak istiyorsanız, çocukların güncel olup olmadıklarını gösteren Bool değerlerinin bir dizisini sürdürmek için SwitchNode değerini değiştirebilirsiniz ve de sonra bunları kullanmak için UpdateGS metodunu override edebilirsiniz. Böylece switch üstünde yeni aktif bir child olur ve siz de sadece ihtiyacınız olduğunda güncellemeleri alabilirsiniz.

Aktif child’ın sınırlandırılması, “Picking” diğer bir yöntemdir. Bu yöntem anlam katar, çünkü aktif child muhtemelen ekran üzerinde gördüğünüz görüntüden yalnızca biridir.

Biz bu çalışmada sadece bir aktif child olduğunu, bir zamanda bir switch node’un sadece tek bir aktif child’ı desteklediğini varsayıyoruz. Fakat normalde, bu çeşitli şekillerde yapılabilir, mesela birden fazla child’ın aktif olmasına izin verilebilir. Bu durumda da MultiswitchNode gibi adlandırılacak, birden fazla child’ın aktif olacağı, yeni bir sınıf eklemek gerekmektedir.

Bazen gerekli olan oyun mantığına dayandırılan değiştirmenin bulunduğu otomatik bir “switching system” için, SwitchNode’dan bir sınıf türetilir ve otomatikleştirme eklenir. Örneğin Wild Magic, türetilmiş DlodNode sınıfına sahiptir. ( “DLOD”, discrete level of detail sözcüklerinin baş harflerinden oluşan kelimedir.)

Parametreleri, bir model merkezi ve her child için mesafelerin aralıkları olarak seçebilirsiniz. Elbette model merkezi, koordinat sistemine bağlı olarak bir parent node tarafından belirlenir. Model mesafe aralıkları, düzensiz aralıkları kastetmektedir. Fakat şayet çakışırlarsa sistem de muhtemelen çalışmayacaktır. Merkez ve uzaklık aralıkları, “DlodNode” tarafından otomatik olarak belirlenir. Çizim aşamasına geçildiğinde, merkez ile göz noktası arasındaki mesafe hesaplanır. Belirlenen mesafe aralığındaki child ise aktif yapılır. Mesafe hesaplamaları ve child seçimi, Draw fonksiyonu tarafından çağırılan”SelectLevelOfDetail” metodu ile belirlenir.

Continuous Level of Detail

En basit örnek, açık veya basit kapalı bir eğri olan, kapalı polyline’daki vertexlerin azalmasıdır. Polyline, vertexine sahiptir. Algoritma, vertexlere atanan ağırlıklara dayanarak, bir zamanda bir vertexi ortadan kaldırır. Bir vertexin ağırlığı, tayin edilmiş bir vertexteki polyline’ın değişim ölçüsüdür. vertexi için, birbirini izleyen , ve olmak üzere üç vertexe dayandırılan, ağırlığı şu şekilde bulunur:

Segment (U,V), U’dan V’ye olan line segmentini belirtir. İlk ortadan kaldırılan vertex, minimum ağırlığı olan vertextir. Şuna dikkat edilmelidir ki, minimum ağırlığı sıfır ise, segment üstündeki bir noktadır. Bu yüzden sıfır ağırlıklı bir noktayı ortadan kaldırmak, polyline azaltmak için ideal olandır.

Sondaki ve noktaları, özel işleme tarzı gerektirir. En kolayı sondaki bu noktaları sonsuza atamaktır: = = . Böylece sondaki noktalar asla ortadan kaldırılmayacaktır. Vertex azaltma işlemi, polyline’da sadece iki vertex kalana kadar devam eder. Bununla birlikte, şayet = ise bu polyline kapalıdır. Ağırlığı sonsuza atamak‘ı daima azaltma noktası yapacaktır. Bunun yerine, ağırlık formülü, içeriği modül n seçme anlayışı ile kapalı bir polyline’da her vertexe uygulanabilir.

Vertex ağırlıkları için başka tanımlamalar da kullanılabilir. Örneğin, ‘nin daha geniş komşusu kullanılabilir. Veya her vertexe eğrinin eğimini atamak için, bir polinom eğrisi kullanılabilir. Birçok alternatif vardır, fakat vertexlerin ortadan kaldırılma sırasını incelemek için ağırlık tanımından bağımsız bir algoritma geliştirilebilir.

Bu çalışmada düşünülen algoritma, bir zaman içinde vertexleri ortadan kaldıracaktır. Azalan polyline’nın vertexleri, orijinal polyline’ın vertexlerinin bir altkümesini oluşturmaktadır. Bu kullanışlıdır, fakat gerekli değildir. Eğer , bütün vertexlerin minimum ağırlığını sağlıyorsa, {, } çiftinin {, , } üçlüsüyle yer değiştirmesi uygundur. ve , orijinal üçlüden türetilen ve muhtemelen diğer komşu vertexlerden türetilen miktarlardır.

Basit Bir Algoritma

Azaltma için en basit algoritma, kendini tekrarlayan bir algoritmadır. Verile bir polyline , hesaplanan ağırlığı olsun. Minimum ağırlık, için ağırlıkları hesaplanır. Polyline’dan kaldırılır. Böylece ilk adımda P polyline’nından n-1 vertexe sahip P’ polyline’ı elde edilir. Bu sefer algoritma P’ polyline’ı üzerinden devam ettirilir. Bu bir O() algoritmasıdır. İlk adımda n tane vertexe sahip polyline ikinci adımda n-1 vertexe sahip olur ve bu böyle devam eder. İşlenmiş vertexlerin toplam sayısı ise:

n+ (n-1)+…+3 = n(n+1)/2 – 3.
Hızlı Bir Algoritma

Hızlı bir algoritma olarak bilinir. İlk aşamada bütün n ağırlıkları hesaplanır. Polyline’dan bir vertexi kaldırıldığı zaman, sadece ve vertexleri etkilenecektir. P’ vertexleri için bütün ağırlıkların hesaplanması gereğinden fazla işlem gerektirir. Ayrıca, tek bir ağırlık çifti değiştiriliyorsa da, minimum değer için bütün birbirini izleyen ağırlıkların araştırılması gerekmez. Bir O(1) aramasını desteklemek için bir yığın veri yapısı kullanılabilir. Eğer yığın bütün bir binary ağacı olarak uygulanırsa, ağacın kökünde minimum değerler olacaktır. Minimum değerler kaldırıldığı zaman da, binary ağacının bir O(logn) update’i yığına geri çevrilmelidir. Yığının ilk yapısı, ağırlıkların çeşidini karşılaştırmayı yani O(nlogn) işlemini gerektirir.

Hızlı azaltma, klasik yığın veri yapısının bir parçası olmayan geleneksel bir işlem gerektirir. Yığın, başlangıçta O(n logn) zamanda yeniden yapılandırılır. Minimum değer ortadan kaldırılır ve binary ağacı yığını yeniden O(log n) zamanda oluşturmak için yeniden organize edilir. Vertexi ortadan kaldırmak, yığındaki iki ağırlıkta bir değişime neden olur. Bir defa bu ağırlıklar değiştirilir ve yığın sunumu için binary ağacı da çok uzun olmayacaktır. Eğer yığından iki eski ağırlığı ortadan kaldırırsak, sonra iki yeni ağırlık ekleyebiliriz. Maalesef, klasik yığın veri yapısı, lokasyondan bir elementi kaldırmayı desteklemez. Toparlayacak olursak, eğer yığındaki bir ağırlık değiştirilirse, binary ağacında eşleşen düğüm ya ağacın köküne doğru ya da ağacın yapraklarına doğru çoğaltılabilir. Bu, onun parent ya da child düğümlerinin ağırlıklarının nasıl karşılaştırıldığına bağlı olarak yapılmaktadır. Çoğaltma işlemi ağaç yapısını değiştirmeksizin yapılabilir, bu da O(logn)update işlemidir. Şayet ağırlık parent ağırlığından daha az değiştiriliyorsa, düğüm de onun parent düğümüyle değiştirilir. Böylece yığın özelliği muhafaza edilmiş olur. Şayet ağırlık child’ların ağırlığından daha fazla değiştiriliyorsa, düğüm bu seferde fazla ağırlığı olan child’ın düğümüyle değiştirilir. Böylece bu durumda da yığın özelliği muhafaza edilmiş olur.

Şimdi, burada da başka bir karışıklık ile karşı karşıyayız. Eğer dâhili bir yığın düğümündeki bir ağırlık değiştirilirse, O(log n) update’ini uygulayabilmek için düğümün yerini bilmemiz gerekmektedir. Değiştirilen düğümü bulmak için de binary ağacını araştırırız. Bu, O(n) işlemi olan lineer bir araştırmadır. Minimum yığının tek özelliği, iki child düğümün toplam ağırlığının bu düğümün ağırlığına eşit veya daha fazla olmasıdır. Bu bilgi, bir araştırma sorgusu için, karar verebilmek için yeterli değildir. Bu problemi çözmek içinde polyline’daki her vertex için bir veri yapısı yaratılır. Farz edelim ki komşu bir dizi içinde yığının binary ağacı depolanmaktadır. Vertex veri yapısı da yığın düğümlerine içerik olarak depolanmak zorundadır. İçerik, bir yığın elementinin parent ya da child’ı çoğaltıldığı zaman değiştirilir.
Bir Örnek – Gösterim

16 kenarlı bir poligonu örnek olarak verelim. 0 <= k <16 için vertexleri olsun. Genişlikleri ise şu şekilde rastgele üretilmiştir: A0 = 75.0626, A1 = 103.1793, A2 = 84.6652, A3 = 115.4370, A4 = 104.2505, A5 = 98.9937, A6 = 92.5146, A7 = 119.7981, A8 = 116.1420, A9 = 112.3302, A10 = 83.7054, A11 = 117.9472, A12 = 110.5251, A13 = 100.6768, A14 = 90.1997, ve A15 = 75.7492. aşağıdaki şekilde numaralandırılmış vertexler ile poligon gösterilmektedir.

Minimum yığın, 16 kaydın olduğu bir dizi olarak depolanır.

Vertex içeriği ve çift bağlı liste yapısı, kendi polyline’ınını belirtir. Vertexler olduğu gibi kaldırılır, liste ise yansıma için update edilir. Ağırlık, yığının sıraladığı nümerik bir değerdir. Daha evvel de bahsedilen yığın indeksi, kimin ağırlığının değiştirildiğinin yığın kayıtlarının, bir O(1)araması için izin verir.
Yığının Başlangıcı

Yığın kayıtları orijinal vertexlerden veri ile başlatılır. Vertex içeriği ve yığın içeriği de başlangıçta aynıdır. Şekil3’te gösterilen yığın dizisi başlangıç değerlerini içermektedir. Burada yığın göstergeleri, vertex göstergeleri ve ağırlıklar gösterilmektedir. Sol taraftaki komşusu ve sağ taraftaki komşusu olan vertexinin ağırlığı, 5. kısımda da belirtilen eşitlik kullanılarak hesaplanır.

Min bir yığın olması için, binary ağaçtakiolan her bir düğüm, child düğümleri olan ve düğümlerinin ağırlıklarının toplamından ya daha küçük olmalılar ya da toplama eşit olmalıdırlar. Ağacın bu işlemi yapmak için tarama işlemi ise ağacın aşağısından başlatılabilir. Aşağıdan başlayarak ağacın köküne doğru yukarılara çıkılır. Bu örnekte ilk parent işlemi ‘dir. Bunun tek bir child’ı vardır, o da ‘dir. ‘in değeri daha küçük olduğu için de ve değiştirilmek zorundadır. Değişimden sonraki yığının durumu ise Şekil4’te gösterilmiştir.

Şekil3: Yığın dizisindeki ilk değerler

Şekil4: Şekil3’teki ve düğümlerinin değişimden sonraki yığın dizisi

Diğer parent işlemi ‘dır. ‘nın ağırlığı onun iki çocuğunun ağırlığının toplamından daha küçüktür, bu yüzden değiştirilmesi gerekmez. Aynı olay ve düğümleri içinde geçerlidir. düğümünün ağırlığı ise her iki çocuğunun ağırlığının toplamından daha büyüktür. Değiş tokuş ise en küçük ağırlığa sahip child arasında olacaktır yani ve düğümleri değiştirilecektir. Şekil4’te değiştirildikten sonra yığın dizisinin durumu gösterilmiştir.

Şekil4: Şekil3’teki ve düğümlerinin değişiminden sonraki yığın dizisi

Değiştirilmeden önce child’daki alt ağacın minimum yığın olduğu garanti altına alınır. Değişimden sonraki en kötü durum ise alt ağaçtaki lineer yolu sağlayabilmek için ağırlığa ihtiyacımız olmasıdır. Daha ileriki değişimler de daima minimum child ağırlığı ile olacaktır. Örneğin değişimi bittikten sonra ve düğümleri arasında değişim olacaktır. Bu da şekil5’da gösterilmiştir.

Şekil5: Şekil4’teki ve düğümlerinin değişiminden sonraki yığın dizisi

Diğer parent işlemi H₂’dir. H₂’deki ağırlık, minimum child ağırlığı olan ‘dan daha fazladır. Bu yüzden bu iki düğüm mutlaka değiştirilmelidir. Bu değişimden sonraki yığın durumu ise şekil6’de gösterilmiştir.

Şekil6: Şekil5’teki H₂ ve ‘daki düğümlerinin değişiminden sonraki yığın dizisi

Diğer bir değişim ise şimdi ile minimum ağırlığa sahip child düğümü arasında gerçekleştirilmektedir. Değişimden sonraki yığın durumu da şekil7’de gösterilmektedir.

Şekil7: Şekil6’daki ve düğümlerinin değişiminden sonraki yığın dizisi

Diğer parent işlemi H₁’dir. H₁’deki ağırlık, minimum child ağırlığı olan ‘ten daha fazladır. Bu yüzden bu iki düğüm de mutlaka değiştirilmelidir. Bu değişimden sonraki yığın durum da şekil8’da gösterilmektedir.

Diğer bir değişim ile minimum ağırlıklı child arasında olmaktadır. Bu durumda şekil9’da gösterilmektedir.

Şekil8: Şekil7’deki H₁ ve düğümlerinin değişiminden sonraki yığın dizisi

Şekil9: Şekil8’deki ve düğümlerinin değişiminden sonraki yığın dizisi

Son parent işlemi H₀’dır. H₀’daki ağırlık, minimum ağırlık olan H₁ childından daha fazladır. Böylece bu düğümler arası mutlaka değişim yapılmalıdır. Değişimden sonraki yığın durumu da şekil10’de gösterilmiştir.

Şekil10: Şekil9’daki H₀ ve H₁ düğümlerinin değişiminden sonraki yığın durumu

Şekil11: şekil10’daki H₁ ve H₄ düğümlerinin değişiminden sonraki yığın durumu

Gerçekleşmek zorunda olan diğer değişim H₁ ile minimum ağırlıklı H₄ childı arasındadır. Fakat diğer hiçbir değişimde bu alt ağaç gerekli değildi. Şekil11’de değişimden sonraki yığının durumu gösterilmektedir. . Artık yığın dizisi minimum bir yığın dizisiyle sunulmalıdır, çünkü her bir düğümdeki çocukların ağırlıkları, parent ağırlıklarına eşit ya da daha küçüktür.
Yok etme ve Güncelleme işlemleri

Minimum ağırlıklı vertex, polyline’dan ilk kaldırılan vertextir. Yığının kökü bu vertex ile eşleştirilir. Böylece kök, yığından kaldırılmış olur. Vertex kaldırıldı. Bütün bir binary ağacını korumak için yığın dizisindeki son nesne, yığının köküyle yer değiştirilir.

Dizi minimumum yığın özelliğini karşılamaz, çünkü kökün ağırlığı, minimum child ağırlığından daha fazladır. Kök düğümü H₀, H₁ ile değiştirilmek zorundadır. Çünkü H₁ minimum ağırlığı child idir. Değiştirme işlemi, minimum ağırlıklı child ağırlığı altındaki düğüm ağırlığından daha küçük kalıncaya kadar devam ettirilir. Bu örnekte H₁ ve H₄ değiştirilir, sonra H₄ ve değiştirilir.

Bu işlem, yığından minimum ağırlıklı elementi kaldırmak için kullanılan tipik bir işlemdir. Bunun birlikte, polyline uygulamasında, daha çok çalışma yapılmaktadır. ve ‘daki vertexlerin ağırlıkları, ‘e bağlıdır. ‘ün sağındaki komşu idi, fakat şimdi ise ‘dır. ‘ın solundaki komşu, idi, şimdi ise ‘tür. Komşular değiştiğinden dolayı da ve ‘ün ağırlıkları yeniden hesaplanmalıdır. ‘ün eski ağırlığı, 187.79 iken yeni ağırlığı 164.52 olur. ‘ın eski ağırlığı, 52.65 iken yeni ağırlığı 52.77 olur. Değişimlerin hiçbiri, değersiz bir yığına yol açmaz. Bu yüzden yığın dizisinin update edilmemesi gerekir. Şekil13’te, Şekil2’deki poligon gösterilmektedir. Yanında da ağırlığının kaldırılmış hali gösterilir.

Şekil12: ve vertexlerindeki ağrılıklar değiştirildikten sonraki yığın. Yeni ağırlıklar gri ile gösterilmektedir.

Şekil13: (a) Şekil2’deki poligon (b) vertexinin kaldırıldığı poligon

Birbirine bitişik vertexlerin ağırlıkları, update edilmek zorundadır. Bu durumda ve ağırlıkları update edilir. ‘ün eski ağırlığı 1435.54 iken, yeni ağırlığı 1492.74 olur. Bu, düğümündeki yığını geçersiz kılmaz. için eski ağırlık 120.11, yeni ağırlık 157.11 olur. Bu değişim ise düğümündeki yığını geçersiz kılar. ve ‘deki düğümler, yığını onarmak için değiştirilmelidirler.Şekil17’de bu iki ağırlık değiştirildikten sonraki yığın durumu gösterilmektedir. Şekil 16’de Şekil13(b)’deki poligon gösterilmektedir.(‘ün kaldırıldığı poligon)

Daha sonra kaldırılacak olan vertex ise vertexidir. Son yığın düğümü olan ‘ün içeriği, köke harekete ettirilir, sonuçta da geçersiz bir yığın elde edilir. ve arasında iki değişim olmak zorundadır. Şekil17’da bu değişimlerden sonraki yığının durumu gösterilmektedir.

Şekil14: ve düğümleri hareket ettirildikten sonra ve ile ve ile değiştirildikten sonraki yığın

Şekil15: ve vertexlerinin ağırlıkları ve ve düğümleri değiştirildikten sonraki yığın. Yeni ağırlıklar gri ile gösterilmektedir.

Bitişik olan ve vertexlerinin ağırlıkları update edilmek zorundadır. Soldaki komşu, uygulamada ilk işlenen olur. için, eski ağrılık 164.52 iken yeni ağırlık 65.80 olur. Yığın geçersizdir, çünkü parent düğümü ‘in ağırlığı, ağırlığından daha fazladır. Bu yüzden ile arasında ve ile düğümleri arasında iki ayrı değişim olmalıdır. için, eski ağırlık, 2258.57 iken yeni ağırlık 791.10 olur. Fakat yığın şimdi geçerlidir. Şekil15’de ağrılıkların değişiminden sonraki yığının durumu gösterilmektedir. Şekil16’da, Şekil13(b)’deki poligon gösterilmektedir.

Şekil16: (a)Şekil13’teki poligon (b)V4 ‘ü kaldırılmış poligon

Şekil17: ve hareket ettirildikten ve ile ve ile arasındaki değişimlerden sonraki yığının durumu

——————————————————————————————————————

Şekil18: ‘teki ağırlık değişildikten ve ile v ve ile arasında değiş tokuş yapıldıktan sonraki yığının durumu

Kalan vertexler içinde benzer işlemler yapılır ve sırasıyla , , , , , , , ve vertexleri kaldırılır. Vertex , ve kalır. Şekil20’de azalan poligonlar karşılaştırılmaktadır. Soldan sağa, yukarıdan aşağıya yıkım gerçekleştirilmektedir.

Şekil19: (a) Şekil16’daki poligon (b) vertexi kaldırıldıktan sonraki poligon

Şekil20: Soldan sağa, yukarıdan aşağıya olan, kalan vertex yıkımları
1. INFINITE LEVEL OF DETAIL
İnfinite level of detail (sonsuz ayrıntı düzeyi)’i elde etmenin en klasik yolu, bir yüzeyin fonksiyonel tanımı ile başlamaktır:

P(u,v) = (x(u,v), y(u,v), z(u,v))

(u,v) parametreleri, hem bir dikdörtgen alanın hem de bir üçgen alanın parametreleridir. Dikdörtgen için parametreler genellikle, 0<=u<=1 ve 0<=v<=1 aralıklarındayken, üçgen için u>=0, v>=0 ve u+v<=1’dir. Parametreler alanı üçgen şeklinde alt parçalara bölerler ve 3D triangle mesh’ler üstünde vertexler eşleştirlirler. Şekil21’de de gösterildiği gibi örneğin bir dikdörtgen birkaç adımda alt parçalara bölünebilir. Aynı şey üçgen içinde geçerlidir. Bu ise Şekil22’de gösterilmektedir.

Giriş parametreleriyle birleştirilmiş gerçek vertex lokasyonlarını kontrol etmek için kullanılan yüzey fonksiyonları için kullanabileceğimiz birçok alternatif vardır.

Şekil21: üçgenlerin içinde bir dikdörtgen alanının birkaç alt bölümü

Şekil22: üçgenlerin içinde bir üçgen alanının birkaç alt bölümü

KAYNAKLAR

Kitaplar

David h. Eberly. 3D Game Engine Architecture, Engineering Real-Time Applications with Wild Magic. San Francisco, CA: Morgan Kaufmann Publishers, 2005.

Websites

http://www.cs.nps.navy.mil/people/faculty/capps/4473/projects/LOD/LODlong.html

http://www.cc.gatech.edu/gvu/people/peter.lindstrom/papers/siggraph96/siggraph96.pdf

http://isg.cs.tcd.ie/cosulliv/Pubs/CGforumCrowds.pdf

http://www.gametools.org/archives/publications/UJI_DGCI2006.pdf