Uzamsal optimizasyon: böl ve yönet

BVH, objeleri geometrik yakınlıklarına göre bir «aile ağacı» yapısına sokar: üst düğümler geniş kablamalarla bir küme geometriyi özetler; derine indikçe kutular ve içerik daha seçkin hale gelir. Bu hiyerarşi, düzgün ızgaraya zorlamadan geometriyi kümelere ayırır — bu yüzden düzensiz dağılmış objelerde sık tercih edilir.

Nasıl çalışır?

En dışta tüm sahneyi kapsayan geniş bir kutu (kök) bulunur. Bu düğüm alt düğümlere bölünür — tipik BVH düzeninde çoğu zaman ikili bölme ile — ve alt kutular kendi içinde yine bölünerek devam eder. En sonda yaprak düğümlerde tekil objeler (veya küçük geometri grupları) yer alır; bölme ekseni ve durdurma kuralı uygulamaya göre değişir.

Işın testi: Işın önce kök kabla bakar. Çarpmıyorsa alt dallara hiç girmeden elenir. Çarpıyorsa yalnızca o dalın altındaki kutulara inilir — kökten kesilen geniş geometri paketleri tek seferde düşer; gereksiz yüzey ve üçgen testleri azalır.

Öne çıkan özelliği: Objeler taşınsa bile ağaç yapısı yeniden düzenlenebilir: yeniden inşa (rebuild), kabla güncelleme (refit) veya ikisinin karışımı gibi stratejilerle yaş tutulur; maliyet sahneye ve hareket miktarına bağlıdır. Animasyonlu karakterler gibi dinamik nesnelerin olduğu sahneler için bu esneklik yüzünden sıklıkla tercih edilir.

Octree, uzayın kendisini matematiksel olarak sekiz eşit küpe (octant) bölen bir yapıdır. BVH’nin geometriyi kümelere göre sarmalamasının aksine burada önce hacim bölünür; objeler uygun hücrelere yerleştirilir. Bu yüzden dünya düzeni düzgün kübik bölgelere benziyorsa yol bulmak kolaydır.

Nasıl çalışır?

Kübik bir alan düşünün: bu küpü X, Y ve Z eksenlerinden tam ortadan kesince sekiz küçük küp elde edilir. Bir küpün içinde hâlâ çok fazla obje veya detay varsa, o küp de kendi içinde yeniden sekize bölünür (özyinelemeli). Ne zaman duracağı uygulamaya göre değişir: örneğin hücre başına obje sayısı eşiği, maksimum derinlik veya benzer bir kural ile yaprak düğümler oluşturulur.

Pratikte «tam küpe sığmayan» büyük objeler üst düğümlerde tutulabilir veya birden fazla hücreye kayıtlı olabilir — hangi politikanın seçildiği projeye bağlıdır.

Işın testi: Işın yolu hangi node ve alt hücrelerden geçiyorsa yalnızca o bölgelerdeki listelerle dar test yapılır; boş veya seyrek bölgeler üçgen döngüsüne girmez. Bu «boşluğu önce ele» davranışı, özellikle geniş ama seyrek dünyalarda hissedilir.

Öne çıkan özelliği: Statik dünyalar — mimari, şehir blokları, arazi ve voxel tarzı veriler — için çok hızlıdır: uzay önceden belirlenmiş düzenli bir ızgara yapısında olduğu için ışının hangi hücre zincirinden geçeceği genelde iyi tahmin edilir ve önbelleğe dost erişim düzenleri kurulabilir. Yoğun dinamik taşıma gerekiyorsa güncelleme maliyeti öne çıkar; bu yüzden karşılaştırma için bir sonraki bölümde BVH ile yan yana düşünmek yerinde olur.

İkisi de «ayıklayıcı geniş faz» sunar; fakat bölme mantığı ve güçlü oldukları senaryolar farklıdır.

Uzamsal optimizasyonun gücü matematikten gelir. Basit bir doğrusal taramada N objeyi tek tek ele almak tipik olarak O(N) ile — yani doğrusal — ölçeklenir. İyi kurulmuş bir BVH veya octree ile ağaç üzerindeki gezinme çoğu durumda O(log N) mertebesinde düşünülür: her adımda aday kümesi belirgin biçimde küçülür. Bu asimptotik üstün davranış gerçek süreyi tek başına yazmaz — dallanma derecesi, örtüşme, kötü durum senaryosu, önbellek ve dar fazın maliyeti yine sahneye bağlıdır — ama büyük N’lerde kazanım sıklıkla «bir iki sıra büyüklük» hissine kadar yükselir.

• Optimizasyon yok: Örneğin 1.000.000 obje için kötü durumda yaklaşık 1.000.000 aday kontrolü düşünülebilir (her şeyi dümdüz denemek).
• Yapı ile: Aynı ölçekte log₂ düşüncesine yakın olarak yaklaşık 20 mertebesi sık dile getirilir — çünkü 2²⁰ ≈ 1.000.000; bu, «ağaçta birkaç kat derinlikte dalıp çoğu geometriyi paket olarak elemek» fikrinin basit bir rakamsal karşılığıdır. Gerçek iş sayısı düğüm başına testler, ışın başına tekrarlar ve dar faz kalitesiyle çarpılır.

Bu ölçek farkı, uygulamanın saniyede tek kare ile akıcı etkileşim arasındaki mesafeyi — özellikle yoğun seçim ve çarpışma döngülerinde — belirleyebilir; amaçlanan FPS rakamını garanti etmez, «iş yükünün N ile kabaca birlikte şişmemesi» şansını yükseltir.

Aynı küp sahnesinde yapı yok / BVH / octree / hybrid arasında geçiş yapın; sahne düzeni (clustered, grid, sparse, zorlu) ve isteğe bağlı yoğun sahne ile birlikte düşünün. Amaç yalnızca FPS değil — ziyaret edilen düğüm/hücre, dar testteki obje ve üçgen sayısı ile gezinmenin kendisini göstermektir.

Yeşil kutu zinciri aktif gezinme yolunu (zamanla açılır), kırmızı kabuklar erken elenen dallar / hücreler, soluk dış çerçeve tüm sahne kabını gösterir. Yapı yok modunda her mesh kabı altın ile «tam tarama» vurgulanır. Öğretim modeli: ikili bölme BVH ve merkeze göre sekizli octree; üretimdeki SAH / gevşek octree / refit burada yoktur — fakat «ilgisiz olanı tek hamlede ele» fikrini somutlaştırır.