Flatland-analogin
Edwin Abbotts Flatland (1884): invånare i ett tvådimensionellt plan. De uppfattar längd och bredd. Djup: den tredje dimensionen ovanför dem, osynlig. De kan inte uppfatta den, kan inte använda den, kan inte bygga med den. Geometrin i deras värld innehåller en dimension som de strukturellt kasserar.
MOAD-0007 fungerar på samma sätt. Objekt i 3D-rymden bär position, rotation och bounding volume: en rik geometrisk struktur. En linjär sökning behandlar dem som en platt lista. Den spatiala strukturen: närvarande, oanvänd, kasserad. Varje intersection-test skannar hela listan, som om objekten saknade geometri och position.
Three.js-exemplet
Three.js Raycaster.intersectObjects(): given a ray (a position & direction in 3D space), find all objects the ray intersects. The implementation: iterate through all N scene objects, test each one against the ray. O(N) per call.
A hover event handler calls intersectObjects() once per frame at 60 frames per second. With N=100 objects: 6,000 intersection tests per second. With N=10,000 objects: 600,000 tests per second. The cost: proportional to N, not to the number of objects the ray actually intersects.
At N=100: invisible. The frame budget (16.7ms at 60fps) absorbs the cost without complaint.
At N=10,000: dominant. 600,000 intersection tests per second saturates the main thread. Frame rate drops. The scene that worked at N=100 collapses silently as N crosses the threshold.
The Structure the Linear Scan Discards
Objects occupy positions in space. An object at position (1000, 0, 0) cannot intersect a ray pointing in the direction (-1, 0, 0) from position (0, 0, 0): the object lies in the opposite direction. A linear scan checks it anyway.
Objects have bounding volumes: a sphere or box that encloses the entire object. A ray that does not intersect an object's bounding volume cannot intersect the object. A linear scan computes the full intersection test anyway.
The geometry encodes which objects to skip. The linear scan ignores the geometry. This is the discard.
Vad 'Discarding the Structure' betyder
Flatland-analogin: Abbotts invånare kunde inte uppfatta djup. En Flatland-defekt kastar bort geometrisk struktur som finns i datan men aldrig når algoritmen.
Varför en hash-mängd inte kan lösa MOAD-0007
MOAD-0001 fix: ersätt en sekventiell medlemskapskontroll med en hash-mängd. list.contains(x): O(N). set.has(x): O(1). Medlemskapsfrågan: ”finns x i denna samling?” Ingen rumslig geometri inblandad.
MOAD-0007 fix: ersätt en linjär rumslig sökning med ett spatialt index (BVH, octree, k-d tree, R-tree). Den rumsliga frågan: ”vilka objekt i denna samling korsar denna ray/sphere/frustum?” Rumslig närhet krävs.
En hash-mängd besvarar medlemskap: ”finns detta exakta objekt?” O(1). Den kan inte besvara närhet: ”vilka objekt finns nära denna ray?” En hash-mängd har ingen uppfattning om avstånd eller rumslig utsträckning. Hashning kastar bort geometri lika effektivt som en linjär sökning.
En BVH besvarar närhet: ”vilka objekt ligger inom denna rumsliga fråga?” O(log N + k). Den organiserar objekt efter position, så närhetsfrågor hoppar över geometriskt avlägsna objekt.
| Fråga | Rätt struktur | Fel struktur |
|---|---|---|
| Finns objekt X i denna mängd? | HashSet (O(1)) | Linjär lista (O(N)) |
| Vilka objekt korsar denna ray? | BVH/octree/k-d tree (O(log N)) | Linjär sökning ELLER HashSet (O(N) eller O(N)) |
MOAD-0001 & MOAD-0007: båda O(N)-operationer ersatta av något snabbare. Olika strukturer krävs eftersom frågorna skiljer sig åt.
När man ska bygga, när man ska hoppa över
Att bygga en BVH kostar O(N log N). Att söka kostar O(log N + k). Brytpunkt: när antalet sökningar överstiger antalet uppbyggnader tillräckligt för att besparingarna ska överstiga byggkostnaden.
Vid N=100: linjär sökning tar mikrosekunder. BVH-byggande lägger till overhead. Hoppa över BVH.
Vid N=10 000 vid 60 Hz: linjär sökning dominerar bildbudgeten. BVH-sökningar kostar 1/1 000 av den linjära sökningen. Bygg BVH en gång; sök 60 gånger per sekund. Brytpunkten nås före första bildrutan.
Regeln: bygg när N * Q > N log N, där Q = sökningar per uppbyggnadscykel. För interaktiva 3D-scener: Q = 60 per sekund, N-tröskel = några hundra objekt.
Diagnostisera & åtgärda en 3D-scen
En 3D-visualiseringsapplikation renderar 5 000 geometriska objekt. En hover-hanterare körs 60 gånger per sekund. Vid varje hover-händelse anropar hanteraren scene.intersectObjects(ray, objects) som itererar över alla 5 000 objekt och testar varje mot strålen. Bildfrekvensen sjönk från 60 fps till 8 fps.
En lagkamrat föreslår: 'Lägg alla objekt i en Set för O(1)-uppslagning.'