Analogi Flatland [BLOCK_TYPE SECTION/STEP]
Flatland karya Edwin Abbott (1884): penghuni bidang dua dimensi. Mereka hanya mempersepsi panjang & lebar. Kedalaman: dimensi ketiga di atas mereka, tak terlihat. Mereka tidak dapat mempersepsi, tidak dapat menggunakan, dan tidak dapat membangun dengan dimensi tersebut. Geometri dunia mereka mengandung dimensi yang secara struktural mereka buang. [BLOCK_TYPE SECTION/STEP]
MOAD-0007 bekerja dengan cara yang sama. Objek di ruang 3D membawa posisi, rotasi, & volume pembatas: struktur geometri yang kaya. Pemindaian linear memperlakukannya sebagai daftar datar. Struktur spasial: ada, tidak digunakan, dibuang. Setiap pengujian interseksi memindai seluruh daftar, seolah-olah objek tidak memiliki geometri & posisi. [BLOCK_TYPE SECTION/STEP]
[BLOCK_TYPE SECTION/STEP]
Contoh Three.js
Three.js Raycaster.intersectObjects(): diberikan sebuah ray (posisi & arah dalam ruang 3D), temukan semua objek yang berpotongan dengan ray tersebut. Implementasinya: iterasi melalui semua N objek scene, uji setiap objek terhadap ray. O(N) per pemanggilan.
Sebuah event handler hover memanggil intersectObjects() sekali per frame pada 60 frame per detik. Dengan N=100 objek: 6.000 pengujian intersection per detik. Dengan N=10.000 objek: 600.000 pengujian per detik. Biayanya: proporsional terhadap N, bukan terhadap jumlah objek yang benar-benar berpotongan dengan ray.
Pada N=100: tidak terlihat. Anggaran frame (16,7 ms pada 60 fps) menyerap biaya tanpa keluhan.
Pada N=10.000: dominan. 600.000 pengujian intersection per detik memenuhi main thread. Frame rate turun. Scene yang berfungsi pada N=100 runtuh secara diam-diam saat N melewati ambang batas.
Struktur yang Dibuang oleh Pemindaian Linear
Objek menempati posisi dalam ruang. Objek di posisi (1000, 0, 0) tidak mungkin berpotongan dengan ray yang mengarah ke arah (-1, 0, 0) dari posisi (0, 0, 0): objek tersebut berada di arah yang berlawanan. Pemindaian linear tetap memeriksanya.
Objek memiliki bounding volume: sebuah bola atau kotak yang melingkupi seluruh objek. Ray yang tidak berpotongan dengan bounding volume objek tidak mungkin berpotongan dengan objek tersebut. Pemindaian linear tetap menghitung pengujian intersection penuh.
Geometri mengkodekan objek mana yang harus dilewati. Pemindaian linear mengabaikan geometri. Inilah yang dibuang.
Apa Arti 'Membuang Struktur'
Analogi Flatland: penghuni Flatland karya Abbott tidak dapat mempersepsi kedalaman. Sebuah Flatland Defect membuang struktur geometris yang ada dalam data tetapi tidak pernah masuk ke dalam algoritma.
Mengapa Hash Set Tidak Dapat Memperbaiki MOAD-0007
MOAD-0001 fix: ganti pengujian keanggotaan sekuensial dengan hash set. list.contains(x): O(N). set.has(x): O(1). Pertanyaan keanggotaan: 'apakah x ada dalam koleksi ini?' Tidak ada geometri spasial yang terlibat.
MOAD-0007 fix: ganti pemindaian spasial linear dengan indeks spasial (BVH, octree, k-d tree, R-tree). Pertanyaan spasial: 'objek mana dalam koleksi ini yang berpotongan dengan ray/sphere/frustum ini?' Diperlukan kedekatan spasial.
Hash set menjawab keanggotaan: 'apakah objek persis ini ada?' O(1). Ia tidak dapat menjawab kedekatan: 'objek mana yang dekat dengan ray ini?' Hash set tidak memiliki konsep jarak atau luas spasial. Hashing membuang geometri sama persis seperti pemindaian linear.
BVH menjawab kedekatan: 'objek mana yang berada dalam kueri spasial ini?' O(log N + k). Ia mengatur objek berdasarkan posisi, sehingga kueri kedekatan melewati objek yang secara geometris jauh.
| Pertanyaan | Struktur yang Benar | Struktur yang Salah |
|---|---|---|
| Apakah objek X ada dalam set ini? | HashSet (O(1)) | Linear list (O(N)) |
| Objek mana yang berpotongan dengan ray ini? | BVH/octree/k-d tree (O(log N)) | Linear scan ATAU HashSet (O(N) atau O(N)) |
MOAD-0001 & MOAD-0007: kedua operasi O(N) digantikan oleh sesuatu yang lebih cepat. Struktur berbeda diperlukan karena pertanyaannya berbeda.
Kapan Membangun, Kapan Melewatkan
Membangun BVH membutuhkan biaya O(N log N). Pencarian membutuhkan biaya O(log N + k). Titik impas: ketika jumlah pencarian jauh lebih banyak daripada pembangunan sehingga penghematan pencarian melebihi biaya pembangunan.
Pada N=100: pemindaian linear hanya memerlukan waktu mikrodetik. Membangun BVH menambah overhead. Lewatkan BVH.
Pada N=10.000 pada 60Hz: pemindaian linear mendominasi anggaran frame. Pencarian BVH hanya memerlukan 1/1.000 dari waktu pemindaian linear. Bangun BVH sekali; lakukan pencarian 60 kali per detik. Titik impas tercapai sebelum frame pertama.
Aturannya: bangun ketika N * Q > N log N, di mana Q = jumlah pencarian per siklus pembangunan ulang. Untuk scene 3D interaktif: Q = 60 per detik, ambang batas N = beberapa ratus objek.
Diagnosa & Perbaiki Scene 3D
Sebuah aplikasi visualisasi 3D merender 5.000 objek geometri. Handler hover berjalan 60 kali per detik. Pada setiap event hover, handler memanggil scene.intersectObjects(ray, objects) yang mengiterasi semua 5.000 objek & menguji masing-masing terhadap ray. Frame rate turun dari 60fps menjadi 8fps.
Seorang rekan tim menyarankan: 'Masukkan semua objek ke dalam Set untuk pencarian O(1).'