Analogi Flatland
Flatland karya Edwin Abbott (1884): penduduk dari bidang dua dimensi. Mereka memahami panjang & lebar. Ketinggian: dimensi ketiga di atas mereka, tidak terlihat. Mereka tidak dapat memahami, tidak dapat menggunakan, tidak dapat membangunnya. Geometri dunia mereka mengandung dimensi yang mereka abaikan struktural.
MOAD-0007 bekerja dengan cara yang sama. Objek di ruang 3D memiliki posisi, rotasi, & volume batas: struktur geometri yang kaya. Scanning linear menganggap mereka sebagai daftar datar. Struktur spasial: ada, tidak digunakan, dibuang. Setiap tes perpotongan memindai daftar seluruhnya, seperti objek tidak memiliki geometri & tidak memiliki posisi.
Contoh Three.js
Three.js Raycaster.intersectObjects(): diberikan sebuah garis (posisi & arah di ruang 3D), temukan semua objek yang garis tersebut potong. Implementasinya: iterasi melalui semua N objek scene, tes setiap satu terhadap garis. O(N) per panggilan.
Pengontrol peristiwa hover memanggil intersectObjects() sekali per frame pada 60 frame per detik. Dengan N=100 objek: 6.000 tes perpotongan per detik. Dengan N=10.000 objek: 600.000 tes per detik. Biayanya proporsional ke N, bukan ke jumlah objek yang garis sebenarnya potong.
Pada N=100: tidak terlihat. Anggaran frame (16,7ms pada 60fps) menyerap biaya tanpa keluhan.
Pada N=10.000: dominan. 600.000 tes perpotongan per detik mengisi thread utama. Kecepatan frame menurun. Scene yang berfungsi pada N=100 runtuh secara diam-diam saat N menyeberangi batas.
Struktur yang Skanning Linear Abaikan
Objek mengisi posisi di ruang. Suatu objek pada posisi (1000, 0, 0) tidak dapat memotong garis yang arahnya (-1, 0, 0) dari posisi (0, 0, 0): objek berada di arah berlawanan. Scanning linear memeriksanya secara keseluruhan.
Objek memiliki volume batas: bola atau kotak yang menutupi objek keseluruhan. Sebuah garis yang tidak memotong volume batas objek tidak dapat memotong objek. Scanning linear menghitung tes perpotongan penuh secara keseluruhan.
Geometri mengkodekan objek yang dilewati. Scanning linear mengabaikan geometri. Ini adalah pengabaian.
Apa 'Mengabaikan Struktur' Berarti
Analogi Flatland: penduduk Abbott tidak dapat mempersepsikan kedalaman. Defect Flatland membuang struktur geometri yang ada dalam data tetapi tidak pernah masuk ke dalam algoritma.
Mengapa Set Hash Tidak Bisa Memperbaiki MOAD-0007
Perbaikan MOAD-0001: ganti pengujian anggota sekvensial dengan set hash. list.contains(x): O(N). set.has(x): O(1). Pertanyaan anggota: 'apakah x ada dalam kumpulan ini?' Tidak ada geometri spasial yang terlibat.
Perbaikan MOAD-0007: ganti skanning spasial linear dengan indeks spasial (BVH, octree, k-d tree, R-tree). Pertanyaan spasial: 'objek mana di kumpulan ini bersinggungan dengan ray/sphere/frustum?' Diperlukan kedekatan spasial.
Set hash menjawab keanggotaan: 'apakah objek ini tepat ada?' O(1). Namun, ia tidak menjawab keberadaan kedekatan: 'objek mana yang dekat dengan ray?' Set hash tidak memiliki konsep jarak atau luas spasial. Hashing membuang geometri sejelasnya seperti skanning linear.
BVH menjawab keberadaan kedekatan: 'objek mana yang jatuh dalam pertanyaan spasial ini?' O(log N + k). Ia mengorganisasi objek berdasarkan posisi, sehingga pertanyaan keberadaan kedekatan melewati objek yang jauh secara geometris.
| Pertanyaan | Struktur Benar | Struktur Salah |
|----------|------------------|-----------------|
| Apakah objek X ada dalam set ini? | HashSet (O(1)) | Daftar Linear (O(N)) |
| Objek mana yang bersinggungan dengan ray ini? | BVH/octree/k-d tree (O(log N)) | Skanning Linear ATAU HashSet (O(N) atau O(N)) |
MOAD-0001 & MOAD-0007: kedua operasi O(N) digantikan oleh yang lebih cepat. Struktur yang berbeda diperlukan karena pertanyaan yang berbeda.
Kapan Membangun, Kapan Melewatkan
Membangun BVH membutuhkan O(N log N). Querying membutuhkan O(log N + k). Titik keseimbangan: saat kueri melebihi pembangunan oleh cukup banyak sehingga penghematan kueri melebihi biaya pembangunan.
Pada N=100: skanner linear membutuhkan mikrodetik. Pembangunan BVH menambah beban. Lepaskan BVH.
Pada N=10,000 pada 60Hz: skanner linear mengendalikan anggaran frame. Pertanyaan BVH menghabiskan 1/1.000 dari skanner linear. Bangun BVH sekali; kueri 60 kali per detik. Titik keseimbangan tercapai sebelum frame pertama.
Aturan: bangun saat N * Q > N log N, di mana Q = kueri per siklus rekonstruksi. Untuk scene 3D interaktif: Q = 60 per detik, ambang batas N = beberapa ratus objek.
Diagnosis & Perbaiki Scene 3D
Aplikasi visualisasi 3D mengrender 5.000 objek geometri. Pemanggil handler hover 60 kali per detik. Setiap kali event hover, handler memanggil scene.intersectObjects(ray, objects) yang mengulang semua 5.000 objek & menguji setiap objek terhadap ray. Kecepatan frame turun dari 60fps menjadi 8fps.
Seorang rekan menyarankan: 'Tempatkan semua objek dalam Set untuk pencarian O(1).'