L'analogia di Flatland
Flatland (1884) di Edwin Abbott: abitanti di un piano bidimensionale. Percepiscono lunghezza e larghezza. Profondità: la terza dimensione sopra di loro, invisibile. Non possono percepirla, non possono usarla, non possono costruirci sopra. La geometria del loro mondo contiene una dimensione che strutturalmente scartano.
MOAD-0007 funziona allo stesso modo. Gli oggetti nello spazio 3D portano posizione, rotazione e volume di delimitazione: una ricca struttura geometrica. Una scansione lineare li tratta come una lista piatta. La struttura spaziale: presente, inutilizzata, scartata. Ogni test di intersezione scansiona l'intera lista, come se gli oggetti non avessero geometria né posizione.
L'esempio Three.js
Three.js Raycaster.intersectObjects(): dato un raggio (una posizione e una direzione nello spazio 3D), trova tutti gli oggetti che il raggio interseca. L'implementazione: itera su tutti gli N oggetti della scena, testando ciascuno contro il raggio. O(N) per chiamata.
Un gestore di eventi hover chiama intersectObjects() una volta per frame a 60 frame al secondo. Con N=100 oggetti: 6.000 test di intersezione al secondo. Con N=10.000 oggetti: 600.000 test al secondo. Il costo: proporzionale a N, non al numero di oggetti che il raggio interseca effettivamente.
A N=100: invisibile. Il budget per frame (16,7 ms a 60 fps) assorbe il costo senza problemi.
A N=10.000: dominante. 600.000 test di intersezione al secondo saturano il thread principale. Il frame rate cala. La scena che funzionava a N=100 collassa silenziosamente quando N supera la soglia.
La struttura che la scansione lineare scarta
Gli oggetti occupano posizioni nello spazio. Un oggetto in posizione (1000, 0, 0) non può intersecare un raggio che punta nella direzione (-1, 0, 0) dalla posizione (0, 0, 0): l'oggetto si trova nella direzione opposta. Una scansione lineare lo controlla comunque.
Gli oggetti hanno volumi di contenimento: una sfera o un box che racchiude l'intero oggetto. Un raggio che non interseca il volume di contenimento di un oggetto non può intersecare l'oggetto stesso. Una scansione lineare esegue comunque il test completo di intersezione.
La geometria codifica quali oggetti saltare. La scansione lineare ignora la geometria. Questo è lo scarto.
Cosa significa 'Scartare la Struttura'
L'analogia di Flatland: gli abitanti di Abbott non potevano percepire la profondità. Un Difetto Flatland scarta la struttura geometrica che esiste nei dati ma non entra mai nell'algoritmo.
Perché un Set Hash non può risolvere MOAD-0007
MOAD-0001 fix: sostituisci un test di appartenenza sequenziale con un hash set. list.contains(x): O(N). set.has(x): O(1). La domanda di appartenenza: 'x è presente in questa collezione?' Nessuna geometria spaziale coinvolta.
MOAD-0007 fix: sostituisci una scansione spaziale lineare con un indice spaziale (BVH, octree, k-d tree, R-tree). La domanda spaziale: 'quali oggetti in questa collezione intersecano questo raggio/sfera/frustum?' Richiesta di prossimità spaziale.
Un hash set risponde all'appartenenza: 'questo oggetto esatto è presente?' O(1). Non può rispondere alla prossimità: 'quali oggetti sono vicini a questo raggio?' Un hash set non ha nozione di distanza o estensione spaziale. L'hashing scarta la geometria esattamente come una scansione lineare.
Un BVH risponde alla prossimità: 'quali oggetti rientrano in questa query spaziale?' O(log N + k). Organizza gli oggetti per posizione, quindi le query di prossimità saltano gli oggetti geometricamente distanti.
| Domanda | Struttura Corretta | Struttura Errata |
|---|---|---|
| L'oggetto X è in questo set? | HashSet (O(1)) | Lista lineare (O(N)) |
| Quali oggetti intersecano questo raggio? | BVH/octree/k-d tree (O(log N)) | Scansione lineare O HashSet (O(N) o O(N)) |
MOAD-0001 & MOAD-0007: entrambe operazioni O(N) sostituite da qualcosa di più veloce. Strutture diverse richieste perché le domande sono diverse.
Quando costruire, quando saltare
Costruire un BVH costa O(N log N). Le query costano O(log N + k). Punto di pareggio: quando il numero di query supera il numero di build abbastanza da far sì che il risparmio sulle query superi il costo di costruzione.
Con N=100: la scansione lineare impiega microsecondi. La costruzione del BVH aggiunge overhead. Salta il BVH.
Con N=10.000 a 60Hz: la scansione lineare domina il budget del frame. Le query BVH costano 1/1.000 della scansione lineare. Costruisci il BVH una volta; esegui query 60 volte al secondo. Il punto di pareggio è raggiunto prima del primo frame.
La regola: costruisci quando N * Q > N log N, dove Q = query per ciclo di rebuild. Per scene 3D interattive: Q = 60 al secondo, soglia N = poche centinaia di oggetti.
Diagnostica e correggi una scena 3D
Un'applicazione di visualizzazione 3D renderizza 5.000 oggetti geometrici. Un gestore hover si attiva 60 volte al secondo. Ad ogni evento hover, il gestore chiama scene.intersectObjects(ray, objects) che itera su tutti i 5.000 oggetti e testa ciascuno contro il ray. Il frame rate è sceso da 60fps a 8fps.
Un compagno di squadra suggerisce: 'Metti tutti gli oggetti in un Set per una ricerca O(1).'