空间索引 — Wu Chenfeng

所有对象两两比较会快速增长，空间索引先排除不可能相交区域。Grid、树与BVH保存不同分布，构建、更新和查询要一起比较。场景图表达语义父子，不能替代空间索引。

空间候选筛选

粗筛与精确查询

$N$ 个对象两两碰撞是 $O(N^2)$ 。空间结构先做粗筛，把候选减少后再做精确碰撞检测。

结构选择取决于静态/动态、密度、对象大小、查询类型和维度。

均匀网格与空间哈希

把空间分为固定格子，对象按包围体插入覆盖的格子。范围查询只访问相交格子。

边长h为正的格子用 floor(position/h) 求整数坐标。位置-0.1、h=1应进入-1格；向零截断会误放到0格。包围盒覆盖区间先约定闭区间或半开区间，遍历候选格后再做精确相交，结果按稳定对象ID去重。

对象移动时保存它上一次占用的格子集合，与新集合求差。只从旧集合删除离开的格子、向新集合加入进入的格子，保持的格子无需重写。删除对象也使用旧成员表清理，避免只有位置变了、旧桶仍残留ID。

以一维投影推演二维插桶：格长1米，对象A的闭区间包围范围为[-0.2,1.2]，覆盖格号-1、0、1；对象B覆盖[0.8,1.4]，进入0、1。查询[0.9,1.0]时访问0、1，两个桶都会返回A、B，因此先按ID去重，再对原包围体做精确判断。二维分别计算X、Y格号范围，再枚举笛卡尔积。闭区间上端恰好在整数边界时保守纳入两侧只会增加候选；漏掉一侧则可能漏检边界接触。

A平移2米后范围变为[1.8,3.2]，新成员为1、2、3。删除旧桶-1、0，保留1，加入2、3，才能让旧位置查询不再看到A。这里保存旧成员表的原因已经具体化：只知道新位置，无法准确删除过去占用的桶。

优点：实现简单、并行友好、动态更新直接。问题：

格子太小，大对象跨很多格子；
格子太大，每格候选过多；
密度极不均匀时浪费；
同一对象出现在多个格子，需要查询去重。

无限/稀疏世界可用格子 Coordinate 哈希，不分配空 Grid。哈希键要稳定处理负坐标和整数溢出。

四叉树与八叉树

四叉树每节点分四块，用于二维/地形；八叉树分八块，用于三维。

它们适合空间密度自适应、LOD 和区域查询。但边界对象如何放置很关键：复制到所有子节点、保留父节点，或使用松散树。

松散八叉树扩大子节点包围体，减少对象跨节点，但会增加重叠和查询候选。

树过深会产生大量小节点和指针。可用线性四叉树/八叉树、Morton编码和连续数组提高局部性。

BVH

BVH 按对象包围体分组，而不是固定切空间。它适合射线、碰撞、剔除和不均匀几何。

静态 BVH 可用 SAH 构建高质量层级；动态对象可重拟合或局部/整体重建。包围体重叠越多，遍历越容易访问两边分支。

树索引的剪枝依赖包围体确实包含所有后代。更新叶节点后要沿祖先扩大或重算包围体，否则查询会在父节点提前排除真实命中。平衡树高度约为对数，只说明到达一个叶子的深度；一次范围或射线查询可能遍历大量节点，最坏仍是线性。

在这个模块里，选择重点是：

构建与更新频率；
查询类型和数量；
节点布局与缓存；
动态变形导致的质量退化；
是否需要 GPU 并行遍历。

求交细节见光线求交与BVH。

KD-Tree与空间分割

KD-Tree按轴向平面分割点或空间，适合静态最近邻、范围查询和部分光线追踪。高维时剪枝效果下降，动态更新也不如 Grid 简单。

点KD-Tree与空间 KD-Tree的数据归属不同。使用库前先确认节点保存点集合还是 Primitive 空间切分。

语义层级与空间索引

场景图表达父级变换和语义层级。把同一层级直接用于可见性查询会出问题：一个空分组下面可能有横跨整张地图的对象。

运行时通常另建空间索引。变换层级变化时更新对象包围体，再把它同步到 BVH/Grid/八叉树。

复杂度与数据局部性

指针式BVH的访问成本取决于剪枝与节点布局；高度平衡也不能保证查询只访问对数个节点。候选很小时，连续数组扫描可能更快，需用同一查询集比较。

优化步骤：

用真实规模和查询记录基线；
检查算法增长；
检查分配、缓存、Branch 和数据布局；
批量查询并行化；
再考虑更复杂结构。

结构越复杂，构建/更新和调试成本也越高。编辑器中每秒一次的 1000 项扫描不需要商业级 BVH。

候选查询

模型伪代码把粗筛与精确判断分开，同一对象跨多个格子时去重。

text

candidates = index.Query(bounds)
for id in Deduplicate(candidates):
    if ExactPredicate(object[id]): output.add(id)

验证方法

随机与聚团场景比较全量扫描结果，测试负坐标、跨格大对象、更新与删除。记录构建、更新、候选数和内存，BVH精确射线求交见光线求交与BVH。

实现与证据

网格更新与BVH祖先包含关系为机制说明，未运行空间索引实现。验证入口按全量扫描作独立正确性参照，不能仅检查返回数量。

参考资料

PBRT4 Bounding Volume Hierarchies：包围体包含、构建与遍历。