Düzlem Analojisi
Edwin Abbott’un Flatland (1884) eseri: iki boyutlu bir düzlemde yaşayan varlıklar. Onlar yalnızca uzunluk ve genişliği algılar. Derinlik: onların üzerinde bulunan, görünmez üçüncü boyut. Onu algılayamazlar, kullanamazlar ve onunla bir şey inşa edemezler. Dünyalarının geometrisi, yapısal olarak attıkları bir boyuta sahiptir.
MOAD-0007 de aynı şekilde çalışır. 3B uzaydaki nesneler konum, dönüş ve sınırlayıcı hacim taşır: zengin bir geometrik yapı. Doğrusal tarama onları düz bir liste gibi ele alır. Mekansal yapı: mevcuttur, kullanılmaz, atılır. Her kesişim testi, nesnelerin geometrisi ve konumu yokmuş gibi tüm listeyi tarar.
Three.js Örneği
Three.js Raycaster.intersectObjects(): verilen bir ışın (3B uzayda bir konum ve yön) için, ışının kesiştiği tüm nesneleri bulur. Uygulama: tüm N sahne nesnesini yineleyerek, her birini ışına karşı test eder. Her çağrı için O(N).
Bir hover olay işleyicisi, saniyede 60 kare hızında intersectObjects() çağrısını her karede bir kez yapar. N=100 nesne olduğunda: saniyede 6.000 kesişim testi. N=10.000 nesne olduğunda: saniyede 600.000 test. Maliyet: N ile orantılıdır, ışının gerçekten kesiştiği nesne sayısıyla değil.
N=100'de: görünmez. Kare bütçesi (60 fps'te 16,7 ms) maliyeti şikayet etmeden karşılar.
N=10.000'de: baskın. Saniyede 600.000 kesişim testi ana iş parçacığını doyurur. Kare hızı düşer. N=100'de çalışan sahne, N eşik değerini aştığında sessizce çöker.
Doğrusal Taramadan Atılan Yapı
Nesneler uzayda konum işgal eder. (1000, 0, 0) konumundaki bir nesne, (0, 0, 0) konumundan (-1, 0, 0) yönünde bir ışınla kesişemez: nesne zıt yönde yer alır. Doğrusal tarama yine de onu kontrol eder.
Nesnelerin sınırlayıcı hacimleri vardır: nesnenin tamamını saran bir küre veya kutu. Bir nesnenin sınırlayıcı hacmiyle kesişmeyen bir ışın, nesneyle de kesişemez. Doğrusal tarama yine de tam kesişim testini hesaplar.
Geometri hangi nesnelerin atlanacağını kodlar. Doğrusal tarama geometriyi yok sayar. Atılan şey budur.
'Yapıyı Atma' Ne Anlama Gelir
Flatland analojisi: Abbott'un sakinleri derinliği algılayamıyordu. Bir Flatland Kusuru, veride var olan ancak algoritmaya hiç girmeyen geometrik yapıyı atar.
Neden Bir Hash Kümesi MOAD-0007'yi Çözemez
MOAD-0001 düzeltmesi: sıralı üyelik testini bir hash set ile değiştirin. list.contains(x): O(N). set.has(x): O(1). Üyelik sorusu: 'x bu koleksiyonda mı?' Hiçbir uzamsal geometri söz konusu değildir.
MOAD-0007 düzeltmesi: doğrusal uzamsal taramayı bir uzamsal indeks (BVH, octree, k-d tree, R-tree) ile değiştirin. Uzamsal soru: 'bu koleksiyondaki hangi nesneler bu ışın/küre/frustum ile kesişiyor?' Uzamsal yakınlık gereklidir.
Bir hash set, üyelik sorusunu yanıtlar: 'bu tam nesne mevcut mu?' O(1). Yakınlık sorusunu yanıtlayamaz: 'bu ışına yakın hangi nesneler var?' Bir hash set'in mesafe veya uzamsal kapsam kavramı yoktur. Hashing, geometriyi doğrusal tarama kadar tamamen yok sayar.
Bir BVH, yakınlık sorusunu yanıtlar: 'bu uzamsal sorgu içinde hangi nesneler yer alıyor?' O(log N + k). Nesneleri konuma göre düzenler, böylece yakınlık sorguları geometrik olarak uzak nesneleri atlar.
| Soru | Doğru Yapı | Yanlış Yapı |
|---|---|---|
| Nesne X bu sette var mı? | HashSet (O(1)) | Doğrusal liste (O(N)) |
| Hangi nesneler bu ışın ile kesişiyor? | BVH/octree/k-d tree (O(log N)) | Doğrusal tarama VEYA HashSet (O(N) veya O(N)) |
MOAD-0001 & MOAD-0007: her ikisi de O(N) işlemleri daha hızlı bir şeyle değiştirir. Farklı yapılar gereklidir çünkü sorular farklıdır.
Ne Zaman Oluşturulmalı, Ne Zaman Atlanmalı
BVH oluşturmak O(N log N) maliyetindedir. Sorgulama maliyeti O(log N + k) olur. Eşik noktası: sorgu sayısı, oluşturma maliyetini aşacak kadar sorgu tasarrufu sağladığında.
N=100 olduğunda: doğrusal tarama mikrosaniyeler alır. BVH oluşturma ek yük getirir. BVH’yi atla.
N=10.000 ve 60 Hz’de: doğrusal tarama kare bütçesini domine eder. BVH sorguları doğrusal taramanın 1/1.000’i kadar maliyetlidir. BVH’yi bir kez oluştur; saniyede 60 kez sorgula. Eşik noktası ilk kareden önce ulaşılır.
Kural: N * Q > N log N olduğunda oluştur, burada Q = yeniden oluşturma döngüsü başına sorgu sayısıdır. Etkileşimli 3B sahneler için: Q = saniyede 60, N eşiği = birkaç yüz nesne.
3B Bir Sahneyi Teşhis Et ve Düzelt
Bir 3B görselleştirme uygulaması 5.000 geometrik nesne işler. Hover işleyici saniyede 60 kez tetiklenir. Her hover olayında işleyici scene.intersectObjects(ray, objects) çağrısını yapar; bu çağrı tüm 5.000 nesneyi yineleyerek her birini ışınla test eder. Kare hızı 60 fps’den 8 fps’e düşer.
Bir takım arkadaşı öneriyor: 'Tüm nesneleri O(1) arama için bir Set içine koy.'