3.1 宽相检测：别让每对都去测

3.1 宽相检测：别让每对都去测

本节摘要：宽相用包围盒把不可能相交的物体对丢掉，把候选数量从平方级压到近似线性。均匀网格适合尺寸接近、分布均匀的动态体；扫描修剪适合沿某一轴稀疏的场景；BVH 适合静态大世界。宽相可以误报，不能漏报。漏报就是穿模，误报只是多跑几次窄相。

本节导读

阅读完本节，你应当能够：

1. 写出 AABB 重叠的六次比较，并给旋转物体算紧 AABB
2. 实现均匀网格插入与邻格查询
3. 说明扫描修剪为何对“沿轴排序几乎有序”很快
4. 用层掩码和静态/动态分表减少无意义对

一、先承认平方测完是自杀

N 个动态物体两两测试是 N(N-1)/2 次。一千个箱子就是约五十万次，即使每次只做 AABB，预算也难看；再乘窄相就没了。货仓里不会让每个托盘和其余所有托盘量一次尺寸，而是先问：你们是不是在同一巷道、同一货架段。宽相就是巷道索引。

包围盒必须包住形状。球的 AABB 是中心加减半径。OBB 盒子旋转后，世界 AABB 取八个顶点的分量最小最大，或用 |R| * halfExtents 公式：每轴半径是旋转矩阵绝对值乘局部半长。算小了会漏检，算大了只是多几个候选。永远偏向算大。高速物体还要把本步扫过的体积并进 AABB（扫掠盒），否则薄板会被穿过且宽相根本看不到重叠。

function aabbOverlap(a, b):
    return a.minX <= b.maxX and b.minX <= a.maxX
       and a.minY <= b.maxY and b.minY <= a.maxY
       and a.minZ <= b.maxZ and b.minZ <= a.maxZ
​

二维去掉 z。这是宽相的原子操作，必须无分支友好，数据从 1.3 节的 AABB 列顺序读。

不要一上来写 BVH。堆箱子演示用网格或 SAP 就够。BVH 的坑在更新：物体一动就变树，处理不好比暴力还慢。

二、均匀网格：把空间变成字典

选格边长大约等于平均物体直径的 1.5 到 2 倍。太小，一个物体占很多格，插入贵；太大，一格里东西太多，退回平方。物体覆盖的所有格都登记它的 id。查询时，只和同格及为避免重复而对的“半邻域”配对，例如只和 id 更大的物体生成对。

哈希网格不分配三维数组，用 hash(ix,iy,iz) 进桶。适合稀疏空间。注意哈希碰撞：桶内仍是链表或小数组，重叠测试还是 AABB。单元格坐标用 floor(pos / cell)，负数要向负无穷取整，向零取整会把 -0.1 和 0.1 丢进同一错误格。

for each body:
    minC = cellOf(aabb.min)
    maxC = cellOf(aabb.max)
    for ix in minC.x .. maxC.x:
        for iy ...
            insert id into bucket[ix,iy,iz]
for each bucket:
    emit unique pairs among ids
    plus pairs with neighbor buckets using an ordering rule
​

静态几何单独一张网格或一张大 BVH，动态只对静态查询，动态之间再走动态网格。关卡里一万块静态石头不该每帧重新插入动态网格。

扫描修剪（Sweep and Prune）：每个 AABB 在 x 轴上是区间，把所有端点排序，扫描时维护活动集合，集合内物体在 x 上重叠，再检查 y/z。物体小幅移动时排序几乎有序，插入排序接近线性。爆炸、传送会打乱顺序，退化为 n log n。2D 平台游戏很爱 SAP；3D 开放世界更常见网格或 BVH。

💡 关键直觉：宽相卖的是召回率 100% 的粗筛。你可以用更肥的盒子换更简单的更新，只要窄相吃得消候选数量。

层掩码：玩家、子弹、碎片、触发器。子弹不打触发器，碎片不打碎片，用 64 位掩码 maskA & layerB。这比空间索引更能砍对数。实现放在出对之后、窄相之前，便宜。

休眠体可以不插入动态宽相，但要让“醒着的邻居”仍能找到它们——否则箱子砸到睡着的堆会穿透。常见做法：睡着的仍留在网格，但睡着-睡着不对，睡着-醒着要对。岛睡眠第 6 章会和这套标记汇合。

三、 sap、网格、BVH 怎么选，以及更新策略

场景里物体尺寸差两个数量级（战舰和螺栓）时，单层均匀网格会崩溃：格太小螺栓还行战舰占半个地图，格太大螺栓全挤一格。用层次网格：每层格边长加倍，物体按自身 AABB 最长边入层，查询时向更大层探。实现比单层烦一倍，但比过早上 BVH 可控。

BVH 对静态三角形网格几乎是必选项：关卡烘焙一棵树，动态物体拿 AABB 去树里查。动态对动态若也用 BVH，可用每帧从叶子重建（如 Sweep 重建）或增量旋转叶子。重建在几千物体时往往比增量更可预测。可预测对实时很重要。

图 三种宽相适用区

宽相输出应去重。网格邻域规则写错会生成 (i,j) 和 (j,i) 两次，窄相跑两遍，求解器接到反向重复接触，堆叠会抖。用 i < j 规范化，或哈希集合。调试时统计“候选对数 / 物体数”，健康值随场景而变，但突然翻十倍说明格太大或掩码失效。

⚠️ 常见坑：物体传送后只更新位置不更新网格占用，宽相仍在旧巷道找它，新位置幽灵穿模。传送必须先从旧格摘掉再插入，并刷新扫掠盒。

连续运动：AABB 取本步起点终点的并。更严的 CCD 在窄相做时间 of impact。宽相若不用扫掠盒，CCD 根本没有候选，等于没做。先把扫掠盒做对，再考虑 TOI。

测试集建议：两个缓慢靠近的球必须出对；两个远距球不能出对；一个高速球穿过薄 AABB 墙，有扫掠盒时必须出对。第三项很多人漏写，上线后子弹穿墙。

层掩码与材质是两件事。掩码决定测不测；材质决定摩擦恢复。不要用“摩擦=0”冒充“不碰撞”，传感器/触发器应走独立标志：生成接触但不进求解器，只进事件队列。否则零摩擦触发器仍会挡住物体。

宽相可以每两帧跑一次吗？动态激烈时不行。静态为主的场景可以对静态对动态的查询结果做脏标记。过早的“隔帧宽相”会漏高速物体。先保证正确，再在分析器证明宽相占 40% 以上时才做脏更新。

把弹跳球世界扩成 200 个球，先暴力 AABB 再换网格，对比候选对数和耗时。这是宽相这一节的毕业条件。数字比感觉可靠。格边长扫一遍参数，画出“候选数 vs 格边长”的 U 形曲线，谷底就是你的场景甜点。把这张曲线留下来，换场景时再扫一次，不要把某一关的格边长写死成引擎常量。

哈希桶容量也要盯。某个桶长度突然到几百，通常是所有物体挤在原点——常见于未初始化位置或 NaN。宽相是 NaN 检测器：AABB 出现 inf 时直接断言，比让求解器吃到 NaN 接触更早暴露。

四、层掩码设计与统计面板

层不要按“敌人、玩家、子弹”无限加。按“谁和谁需要物理响应”分组：静态地形、动态可推、角色控制器、传感器、碎片。碎片之间常常关掉，能省大量对。子弹只对地形和角色。掩码表做成数据，策划可改，不要写死在宽相核心。

统计面板每帧打印：插入格子数、平均桶长、最大桶长、候选对数、被掩码杀掉的对数。最大桶长突然上千，检查原点 NaN 或格边长。被掩码杀掉的比例很高说明层设计有效；低到几乎为零说明所有层都在互撞，掩码没干活。

动态物体传送必须提供 teleportBody 接口，内部摘格、写位置、清扫掠、插值取消。脚本直接改位置列是漏洞。宽相是空间的真理来源，位置更新必须走它的门。

与静态 BVH 的配合：动态网格只含动态，每对动态先网格，再拿动态 AABB 去静态 BVH 查。两套结构，两套候选，合并去重。不要把静态每帧插入动态网格“图省事”，那是用内存和插入时间换自己的懒。

实践问答

格边长甜点怎么找？

扫边长，画候选数曲线，取谷底。换关卡再扫。不要当引擎常量写死。平均物体直径的 1.5 到 2 倍是起点不是终点。

负数坐标为什么向负无穷取整？

向零取整会把 -0.1 和 0.1 丢进错误的同一格或跳格。格子必须覆盖空间剖分，floor 才对。写单元测试覆盖负象限。

SAP 爆炸尖峰怎么缓解？

爆炸时排序逆序多。可以爆炸期间改用网格，或接受那一帧尖峰并钳制 maxSteps。不要在 SAP 里为爆炸写一堆特例，除非分析器说这是主因。

触发器为什么不能靠零摩擦？

零摩擦仍进求解器，仍能挡住。传感器走独立标志，生成事件不生成求解接触。两套列表，别省。

参数扫描笔记：宽相参数

扫描 1：格边长等于平均直径

物体占多格，插入贵。1.5 到 2 倍作起点再扫谷底。

扫描 2：所有物体挤原点

最大桶长上千。宽相当 NaN 检测器。

扫描 3：传送只改位置不摘格

幽灵穿模。必须 teleport 接口。

扫描 4：睡着-睡着仍出对

浪费。睡着-醒着必须出对否则砸穿。

扫描 5：层掩码全开

掩码没干活。看被杀掉的比例。

扫描 6：屏幕空间格子

摄像机一转配对全变。必须世界系。

扫描 7：CCD 集合也上复杂树

物体少，线性表够。

扫描 8：候选不去重

反向重复接触，堆叠抖。i 小于 j 规范化。

扫描 9：静态每帧插入动态网格

用插入时间换懒。分开。

工程备忘录

备忘 1

调「01-宽相检测别穷举」时一次只改一个量，写下场景名、旧值、新值、醒岛数或能量变化。没有笔记的调参会在一周后变成传说。传说不能回归，不能交给同事，也不能在换库时当合同。 本条对应「01-宽相检测别穷举」第 1 号备忘，和相邻条目不要合并成一句空话，分开验收。

备忘 2

「01-宽相检测别穷举」的单元测试尽量不依赖图形窗口。能在无头模式跑的断言，才会每次提交都跑。只靠进游戏看一看，等于没有测试。把金字塔睡眠、速度交换、自由落体距离这类金标准写成断言。 本条对应「01-宽相检测别穷举」第 2 号备忘，和相邻条目不要合并成一句空话，分开验收。

一节小结

• 宽相可误报不可漏报；包围盒含旋转与扫掠体积。
• N 很小用暴力，动态相近尺寸用网格，2D 小幅运动用 SAP，静态大世界用 BVH。
• 负数格坐标必须向负无穷取整；成对输出要去重。
• 静态分表、层掩码、休眠规则比更炫的树更能砍成本。
• 传送要摘格再入格；触发器用标志，不用零摩擦冒充。
• 用候选对数和三则单元测试卡住实现。
• 格边长用曲线扫，不要拍脑袋当全局常量。

下一节对候选对做窄相：从布尔变成法向、深度和接触点。