平面国类比
埃德温·艾博特 1884 年的《平面国》：生活在二维平面上的居民。他们只能感知长度与宽度。深度——位于他们上方的第三维度——是不可见的。他们无法感知、无法使用、也无法用它来构建。他们的世界几何包含一个被结构上丢弃的维度。
MOAD-0007 的工作方式与此相同。三维空间中的对象携带位置、旋转和包围体：一个丰富的几何结构。线性扫描将它们视为一个扁平列表。空间结构：存在、未使用、被丢弃。每次相交测试都扫描整个列表，仿佛这些对象没有几何也没有位置。
Three.js 示例
Three.js Raycaster.intersectObjects()：给定一条射线（三维空间中的位置与方向），找出该射线与所有相交的对象。其实现方式为：遍历场景中的全部 N 个对象，逐一测试每条射线。每次调用复杂度为 O(N)。
悬停事件处理器每帧调用一次 intersectObjects()，帧率为 60 fps。当 N=100 时，每秒执行 6,000 次相交测试；当 N=10,000 时，每秒执行 600,000 次相交测试。其成本与 N 成正比，而非与射线实际相交的对象数量成正比。
当 N=100 时：几乎不可见。帧预算（60 fps 下为 16.7 ms）可轻松吸收该开销。
当 N=10,000 时：开销占主导。600,000 次相交测试每秒会占满主线程，导致帧率下降。原本在 N=100 时运行流畅的场景，会在 N 越过阈值后悄然崩溃。
线性扫描所丢弃的结构
对象在空间中占据位置。位于 (1000, 0, 0) 的对象不可能与从 (0, 0, 0) 沿 (-1, 0, 0) 方向发出的射线相交：该对象处于相反方向。线性扫描仍会对其进行检查。
对象具有包围体：一个包围整个对象的球体或盒子。若射线未与对象的包围体相交，则不可能与该对象相交。线性扫描仍会执行完整的相交测试。
几何结构编码了哪些对象可以跳过。线性扫描忽略了这一几何信息。这就是所丢弃的部分。
“丢弃结构”是什么意思
Flatland 比喻：Abbott 的居民无法感知深度。Flatland 缺陷会丢弃数据中实际存在、但算法从未使用的几何结构。
为什么哈希集合无法解决 MOAD-0007
MOAD-0001 修复：将顺序成员测试替换为哈希集合。list.contains(x)：O(N)。set.has(x)：O(1)。成员问题：“x 是否存在于此集合中？”不涉及空间几何。
MOAD-0007 修复：将线性空间扫描替换为空间索引（BVH、八叉树、k-d 树、R 树）。空间问题：“此集合中哪些对象与该射线/球体/视锥相交？”需要空间邻近性。
哈希集合回答成员问题：“此精确对象是否存在？”O(1)。它无法回答邻近问题：“哪些对象靠近该射线？”哈希集合没有距离或空间范围的概念。哈希处理会像线性扫描一样彻底丢弃几何信息。
BVH 回答邻近问题：“哪些对象落在此空间查询范围内？”O(log N + k)。它按位置组织对象，因此邻近查询会跳过几何上较远的对象。
| 问题 | 正确结构 | 错误结构 |
|---|---|---|
| 对象 X 是否在此集合中？ | HashSet (O(1)) | 线性列表 (O(N)) |
| 哪些对象与此射线相交？ | BVH/八叉树/k-d 树 (O(log N)) | 线性扫描或 HashSet (O(N) 或 O(N)) |
MOAD-0001 & MOAD-0007：两者均为 O(N) 操作，现已被更快的方法取代。需要不同的数据结构，因为查询需求不同。
何时构建，何时跳过
构建 BVH 的成本为 O(N log N)。查询成本为 O(log N + k)。平衡点：当查询次数足够多，使得查询节省的成本超过构建成本时。
当 N=100 时：线性扫描只需几微秒。BVH 构建会增加额外开销。跳过 BVH。
当 N=10,000 且帧率为 60Hz 时：线性扫描会占用大部分帧预算。BVH 查询成本仅为线性扫描的 1/1000。构建一次 BVH，每秒查询 60 次。平衡点在第一帧之前即可达到。
规则：当 N * Q > N log N 时构建，其中 Q = 每次重建周期内的查询次数。对于交互式 3D 场景：Q = 每秒 60 次，N 阈值约为几百个对象。
诊断并修复 3D 场景
一个 3D 可视化应用渲染 5,000 个几何对象。悬停处理器每秒触发 60 次。每次悬停事件时，处理器调用 scene.intersectObjects(ray, objects)，该调用会遍历全部 5,000 个对象并逐一与射线进行测试。帧率从 60fps 降至 8fps。
一位队友建议：“将所有对象放入 Set 以实现 O(1) 查找。”