平面世界的类比
爱德华·阿伯特的《平面世界》（1884）：生活在二维平面上的居民。他们感知长度和宽度。深度：对他们而言的第三维，无法感知，无法使用，无法构建。他们世界的几何结构包含了他们结构上丢弃的维度。
MOAD-0007 的工作方式相同。3D 空间中的对象带有位置、旋转和边界体积：丰富的几何结构。线性扫描将它们视为扁平列表。空间结构：存在、未使用、被丢弃。每个交点测试都扫描了整个列表，就好像对象没有几何和位置一样。
Three.js 示例
Three.js Raycaster.intersectObjects():给定一个光线（3D 空间中的一个位置和方向），找到光线与之相交的所有对象。实现：遍历所有 N 个场景对象，并将每个对象测试为光线。O(N) 每次调用。
一个悬停事件处理程序每秒调用 intersectObjects() 60 次。具有 N=100 个对象：每秒 6,000 个交点测试。具有 N=10,000 个对象：每秒 600,000 个测试。成本与 N 成比例，而不是与光线实际相交的对象数量。
在 N=100 时：不可见。帧预算（每秒 60 帧的 16.7ms）无怨地承受了成本。
在 N=10,000 时：主导。600,000 个交点测试每秒占用主线程。帧率下降。能够在 N=100 时正常工作的场景在 N 超过阈值时静音地崩溃。
线性扫描丢弃的结构
对象在空间中占据位置。一个位置为 (1000, 0, 0) 的对象无法与从位置 (0, 0, 0) 指向方向 (-1, 0, 0) 的光线相交：该对象位于相反方向。线性扫描仍然检查它。
对象具有边界体积：一个封闭整个对象的球体或盒子。一个光线无法与对象的边界体积相交，否则光线将无法与对象相交。线性扫描仍然计算全交点测试。
几何结构编码了要跳过的对象。线性扫描忽略了几何结构。这就是丢弃。
什么是'丢弃结构'的含义
平面世界的类比：阿伯特的居民无法感知深度。平面世界缺陷丢弃了数据中的几何结构，但从未进入算法。
为什么哈希集无法修复MOAD-0007
MOAD-0001修复：将顺序成员测试替换为哈希集。list.contains(x): O(N)。set.has(x): O(1)。成员问题：'x在这个集合里吗？' 没有涉及空间几何。
MOAD-0007修复：将线性空间扫描替换为空间索引(BVH,八叉树,k-d树,R树)。空间问题：'这个集合中的对象哪些与这个射线/球体/锥体相交？' 需要空间接近。
哈希集回答成员问题：'这个确切对象是否存在？' O(1)。它不能回答接近问题：'这个射线附近的对象是什么？' 哈希集没有距离或空间范围的概念。哈希ing与线性扫描一样彻底丢弃几何。
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: both O(N) operations replaced by something faster. Different structures required because the questions differ.
何时构建，何时跳过
构建 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) 查询。'