The Flatland Analogy
Edwin Abbott's Flatland (1884): inhabitants of a two-dimensional plane. They perceive length & width. Depth: the third dimension above them, invisible. They cannot perceive it, cannot use it, cannot build with it. The geometry of their world contains a dimension they structurally discard.
MOAD-0007 works the same way. Objects in 3D space carry position, rotation, & bounding volume: a rich geometric structure. A linear scan treats them as a flat list. The spatial structure: present, unused, discarded. Every intersection test scans the entire list, as though the objects had no geometry & no position.
The Three.js Example
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.
What 'Discarding the Structure' Means
The Flatland analogy: Abbott's inhabitants could not perceive depth. A Flatland Defect discards geometric structure that exists in the data but never enters the algorithm.
Why a Hash Set Cannot Fix MOAD-0007
MOAD-0001 fix: replace a sequential membership test with a hash set. list.contains(x): O(N). set.has(x): O(1). The membership question: 'is x in this collection?' No spatial geometry involved.
MOAD-0007 fix: replace a linear spatial scan with a spatial index (BVH, octree, k-d tree, R-tree). The spatial question: 'which objects in this collection intersect this ray/sphere/frustum?' Spatial proximity required.
A hash set answers membership: 'is this exact object present?' O(1). It cannot answer proximity: 'which objects near this ray?' A hash set has no notion of distance or spatial extent. Hashing discards geometry just as thoroughly as a linear scan.
A BVH answers proximity: 'which objects fall within this spatial query?' O(log N + k). It organizes objects by position, so proximity queries skip geometrically distant objects.
| Question | Correct Structure | Wrong Structure |
|----------|------------------|-----------------|
| Is object X in this set? | HashSet (O(1)) | Linear list (O(N)) |
| Which objects intersect this ray? | BVH/octree/k-d tree (O(log N)) | Linear scan OR HashSet (O(N) or O(N)) |
MOAD-0001 & MOAD-0007: both O(N) operations replaced by something faster. Different structures required because the questions differ.
When to Build, When to Skip
Building a BVH costs O(N log N). Querying costs O(log N + k). Break-even: when queries outnumber builds by enough that query savings exceed build cost.
At N=100: linear scan takes microseconds. BVH build adds overhead. Skip the BVH.
At N=10,000 at 60Hz: linear scan dominates frame budget. BVH queries cost 1/1,000th of the linear scan. Build the BVH once; query 60 times per second. Break-even reached before the first frame.
The rule: build when N * Q > N log N, where Q = queries per rebuild cycle. For interactive 3D scenes: Q = 60 per second, N threshold = a few hundred objects.
Diagnose & Fix a 3D Scene
A 3D visualization application renders 5,000 geometric objects. A hover handler fires 60 times per second. On every hover event, the handler calls scene.intersectObjects(ray, objects) which iterates all 5,000 objects & tests each against the ray. Frame rate dropped from 60fps to 8fps.
A teammate suggests: 'Put all objects in a Set for O(1) lookup.'