Düzlem AnalOGji
Edwin Abbott'un Flatland (1884): iki boyutlu bir düzlemin sakinleri. Uzunluk ve genişlik algılarlar. Derinlik: üzerlerinde bulunan üçüncü boyut, görünmez. Onlar bunu algılayamaz, kullanamaz, inşa edemezler. Dünya geometri, onların yapısal olarak atladığı bir boyut içerir.
MOAD-0007 aynı şekilde çalışır. 3D uzaydaki nesneler, pozisyon, döndürme ve sınırlı hacim taşıyor: zengin bir geometrik yapı. Bir lineer tarama, onları düz bir liste olarak ele alır. Uzaysal yapı: mevcut, kullanılmamış, atılmış. Her bir kesişim testi, nesnelerin herhangi bir geometrik ve konumları olmadığını varsayarak, nesnelerin tamamen listelenmesini taramaya devam eder.
Üç.js Örneği
Three.js Raycaster.intersectObjects(): verilen bir ışın (3D uzayda bir pozisyon ve yön), ışınla kesişen nesneleri bulur. İmplementation: tüm N nesneyi dolaşarak, her birini ışınla karşılaştırır. O(N) her çağrıda.
Bir dalgıç olay işleyicisi, 60 kareyi bir saniyede bir intersectObjects() çağırır. N=100 nesne ile: saniye başına 6.000 kesişim testi. N=10.000 nesne ile: saniye başına 600.000 test. Maliyet: N'ye orantılı, değil kesişen ışınların gerçek sayısı.
N=100'te: görünmez. Frame bütçesi (60 fps'de 16.7ms) maliyeti emer.
N=10.000'de: baskın. Ana dizi üzerinde 600.000 kesişim testi saniye başına, frame hızı düşer. N=100'de çalışmış olan sahne sessizce N eşiğinde geçtikçe çöker.
Lineer Tarama tarafından Atılan Yapı
Nesneler uzaysal pozisyonlarda yer alırlar. Bir nesne (1000, 0, 0) konumunda, (0, 0, 0) konumundan (-1, 0, 0) yönünde bir ışınla kesişemeyecek: nesne karşıt yönde yer almalıdır. Lineer tarama bunu yine de kontrol eder.
Nesneler sınırlı hacimler taşıyor: nesneyi tamamen kaplayan bir küp veya küre. Bir ışın, nesnenin sınırlı hacmine kesişmezse, nesneyi kesişemeyecek. Lineer tarama tam kesişim testini yine de hesaplar.
Geometri, hangi nesnelerin atlanması gerektiğini gösterir. Lineer tarama geometriyi görmezden gelir. Bu, atma işlemidir.
Yapının 'Atılması' Nesi Anlama
Düzlem analoji: Abbott'un sakinleri derinliği algılayamıyordu. Bir Flatland Defect, veride mevcut olan ancak algoritmada hiç girmeyen geometrik yapıyı atlar.
Neden Hash Set MOAD-0007'u Çözemez?
MOAD-0001 fix: bir 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 koleksiyon içinde mi?' Uzaysal geometri içermez.
MOAD-0007 fix: bir lineer uzaysal taramayı bir uzay dizini (BVH, oktree, k-d tree, R-tree) ile değiştirin. Uzaysal soru: 'Bu koleksiyon içindeki nesneler bu ray/sphere/frustum ile çakışıyor mu?' Uzaysal yakınlık gereklidir.
Bir hash set, tam nesnenin mevcut olup olmadığını sorma yanıtı verir: 'O?' O(1). Yakınlık sorusuna yanıt veremez: 'Bu ray etrafındaki nesneler?' Bir hash set, mesafe veya uzaysal boyut kavramına sahip değildir. Hashleme, düz tarama kadar geometriyi atlar.
Bir BVH, bu uzaysel sorgu içinde hangi nesnelerin düşüğünü sorma yanıtı verir: 'O(log N + k)'. Nesneleri konumlarına göre organize eder, böylece yakınlık soruları geometrik olarak uzak nesneleri atlar.
| Soru | Doğru Yapı | Yanlış Yapı |
|----------|------------------|-----------------|
| X nesnesi bu kümede mi? | HashSet (O(1)) | Lineer liste (O(N)) |
| Bu rayle çakışan nesneler | BVH/octree/k-d tree (O(log N)) | Lineer tarama veya HashSet (O(N) veya O(N)) |
MOAD-0001 & MOAD-0007: hem O(N) operasyonları daha hızlı bir şeylerle değiştirdik. Söylediğimiz sorulara göre farklı yapılar gerekti.
İnşaa Zamanı, Atlama Zamanı
BVH inşa etmek O(N log N) maliyetlidir. Sorgulama O(log N + k) maliyetlidir. Karşılaştırma: sorguların inşa maliyetinden daha fazla tasarruf sağladığında inşa etmeyi geçmeye değer.
N=100'de: lineer tarama mikrosaniyeler alır. BVH inşa etmek ek yük oluşturur. BVH oluşturmayın.
N=10,000 ve 60Hz'de: lineer tarama kareyi belirler. BVH sorguları lineer taramadan 1/1,000'ü kadar maliyetlidir. BVH bir kez oluşturun ve saniye başına 60 kez sorgulayın. İlk kareye kadar karşılaştırma sınırına ulaşılmıştır.
Kural: N * Q > N log N, burada Q = yenileme döngüsündeki sorgular. Interaktif 3D sahnelere yönelik: saniye başına 60 sorgu, nesne sayısı eşiği birkaç yüz nesnedir.
3D Sahne Tanım ve Tamir Et
Bir 3D görselleştirme uygulaması 5.000 geometrik nesneyi render ediyor. Bir hover işleyicisi saniye başına 60 kez çalışıyor. Her hover olayında, işleyici scene.intersectObjects(ray, objects) metodunu çağırıyor, bu da her birini raye karşı test etmek için tüm 5.000 nesneyi iter ediyor. Frame hızı 60 fps'ten 8 fps'ye düştü.
Bir arkadaşı öneride bulunarak 'Tüm nesneleri bir Set içine yerleştirin, O(1) arama için' dedi.