De Flatland-analogie
Edwin Abbott's Flatland (1884): bewoners van een tweedimensionaal vlak. Zij nemen lengte en breedte waar. Diepte: de derde dimensie boven hen, onzichtbaar. Zij kunnen deze niet waarnemen, niet gebruiken, er niet mee bouwen. De geometrie van hun wereld bevat een dimensie die ze structureel weggooien.
MOAD-0007 werkt op dezelfde manier. Objecten in 3D-ruimte dragen positie, rotatie en begrenzingsvolume: een rijke geometrische structuur. Een lineaire scan behandelt ze als een platte lijst. De ruimtelijke structuur: aanwezig, ongebruikt, weggegooid. Elke intersectietest scant de volledige lijst, alsof de objecten geen geometrie en geen positie hadden.
Het Three.js-voorbeeld
Three.js Raycaster.intersectObjects(): gegeven een straal (een positie & richting in 3D-ruimte), vind alle objecten die de straal snijdt. De implementatie: itereer door alle N scène-objecten, test elk object tegen de straal. O(N) per aanroep.
Een hover-eventhandler roept intersectObjects() één keer per frame aan bij 60 frames per seconde. Met N=100 objecten: 6.000 intersectietests per seconde. Met N=10.000 objecten: 600.000 tests per seconde. De kosten: evenredig met N, niet met het aantal objecten dat de straal daadwerkelijk snijdt.
Bij N=100: onzichtbaar. Het framebudget (16,7 ms bij 60 fps) absorbeert de kosten zonder protest.
Bij N=10.000: dominant. 600.000 intersectietests per seconde verzadigen de main thread. De framerate daalt. De scène die werkte bij N=100 stort stilletjes in zodra N de drempel overschrijdt.
De structuur die de lineaire scan weggooit
Objecten nemen posities in in de ruimte. Een object op positie (1000, 0, 0) kan niet snijden met een straal die in de richting (-1, 0, 0) wijst vanaf positie (0, 0, 0): het object ligt in de tegenovergestelde richting. Een lineaire scan controleert het toch.
Objecten hebben begrenzingsvolumes: een bol of doos die het hele object omsluit. Een straal die een begrenzingsvolume van een object niet snijdt, kan het object zelf niet snijden. Een lineaire scan voert de volledige intersectietest toch uit.
De geometrie codeert welke objecten overgeslagen kunnen worden. De lineaire scan negeert de geometrie. Dit is het weggooien.
Wat 'Structuur weggooien' betekent
De Flatland-analogie: de bewoners van Abbott konden geen diepte waarnemen. Een Flatland Defect gooit geometrische structuur weg die wel in de data aanwezig is, maar nooit in het algoritme terechtkomt.
Waarom een hashset MOAD-0007 niet kan oplossen
MOAD-0001 fix: vervang een sequentiële lidmaatschapstest door een hash-set. list.contains(x): O(N). set.has(x): O(1). De lidmaatschapsvraag: 'zit x in deze collectie?' Er is geen ruimtelijke geometrie betrokken.
MOAD-0007 fix: vervang een lineaire ruimtelijke scan door een ruimtelijke index (BVH, octree, k-d tree, R-tree). De ruimtelijke vraag: 'welke objecten in deze collectie snijden deze ray/sphere/frustum?' Ruimtelijke nabijheid vereist.
Een hash-set beantwoordt lidmaatschap: 'is dit exacte object aanwezig?' O(1). Het kan geen nabijheidsvraag beantwoorden: 'welke objecten liggen dicht bij deze ray?' Een hash-set heeft geen notie van afstand of ruimtelijke omvang. Hashing verwijdert geometrie net zo grondig als een lineaire scan.
Een BVH beantwoordt nabijheid: 'welke objecten vallen binnen deze ruimtelijke query?' O(log N + k). Het organiseert objecten op positie, zodat nabijheidsqueries geometrisch verre objecten overslaan.
| Vraag | Correcte structuur | Verkeerde structuur |
|---|---|---|
| Is object X in deze set? | HashSet (O(1)) | Lineaire lijst (O(N)) |
| Welke objecten snijden deze ray? | BVH/octree/k-d tree (O(log N)) | Lineaire scan OF HashSet (O(N) of O(N)) |
MOAD-0001 & MOAD-0007: beide O(N)-bewerkingen vervangen door iets snellere. Verschillende structuren nodig omdat de vragen verschillen.
Wanneer bouwen, wanneer overslaan
Een BVH bouwen kost O(N log N). Opvragen kost O(log N + k). Break-even: wanneer het aantal queries het aantal builds voldoende overtreft zodat de besparing op queries de bouwkosten overstijgt.
Bij N=100: lineaire scan duurt microseconden. BVH-bouw voegt overhead toe. Sla de BVH over.
Bij N=10.000 op 60 Hz: lineaire scan domineert het frame-budget. BVH-queries kosten 1/1.000ste van de lineaire scan. Bouw de BVH één keer; vraag 60 keer per seconde. Break-even bereikt vóór het eerste frame.
De regel: bouw wanneer N * Q > N log N, waarbij Q = queries per herbouwcyclus. Voor interactieve 3D-scènes: Q = 60 per seconde, N-drempel = een paar honderd objecten.
Diagnoseer & Repareer een 3D-scène
Een 3D-visualisatieapplicatie rendert 5.000 geometrische objecten. Een hover-handler vuurt 60 keer per seconde. Bij elke hover-gebeurtenis roept de handler scene.intersectObjects(ray, objects) aan, die alle 5.000 objecten doorloopt en elk object test tegen de ray. De framerate daalde van 60 fps naar 8 fps.
Een teamlid stelt voor: 'Zet alle objecten in een Set voor O(1)-opzoeken.'