6.3 空间结构与算法复杂度

6.3 空间结构与算法复杂度

本节摘要：暴力宽相平方级，网格平均接近线性，最坏仍会在一格里平方。BVH 查询对数，但更新有代价。SPH 邻居同网格。选型看尺寸分布和动态程度，用候选对数和计时验收，不要只背大 O。重建 vs 增量：数据乱到一定程度，重建更可预测。

本节目标

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

1. 写出暴力、网格、SAP、BVH 的平均与最坏复杂度
2. 解释均匀网格在尺寸两极化时为何退化
3. 决定静态网格用烘焙 BVH、动态用网格或每帧重建
4. 用“候选数/物体数”当健康指标

一、大 O 要带最坏场景

暴力 AABB：次数 n(n-1)/2，每次 O(1)，总 O(n²)。n=100 还能活，n=2000 只宽相就过预算。

均匀网格：插入 O(n * cellsPerBody)。查询同格配对，平均 O(n * k)，k 为格内平均物体数。所有物体挤一格，k=n，退回平方。这就是爆炸、传送到原点、网格边长过大时的现场。

SAP：排序 O(n log n) 或几乎有序插入 O(n + 逆序)。扫描 O(n + 重叠对数)。重叠对数仍可能平方（全重叠）。SAP 不怕尺寸差异，怕完全重叠和排序被打乱。

BVH 查询 O(log n) 期望，退化树变线性。构建 O(n log n)。每帧动 n 个叶子，增量更新摊销可能比重建差，因为树质量下降后查询变慢。很多引擎动态物体每帧从头建 BVH，静态另树。

SPH 邻居：必须网格或树，暴力 SPH 比暴力刚体更早死，因为还要算核函数。

二、重建往往更老实

增量 BVH：物体小动转叶子，树慢慢歪。歪了就要旋转或重建。实现复杂，bug 表现为偶发漏检。每帧对动态集重建：时间可预测，树质量高。动态物体几百个，重建通常赢。静态关卡烘焙一次。两棵树：动态 vs 动态，动态 vs 静态。

💡 关键直觉：复杂度是发票，常数和可预测性是税。实时更恨偶发 20 毫秒尖峰，而不是平均 1 毫秒变成 1.2。

扫描修剪在爆炸时排序逆序暴增，那一帧尖峰。网格在爆炸时局部 k 增大，尖峰更局部。选你更能接受的尖峰形态。子弹穿透靠扫掠盒，与结构类型无关，哪种宽相都要做扫掠体积。

三、指标与何时停止优化

健康指标：

• 候选对数 / 动态体数：个位数到几十正常，上百检查格或掩码
• 窄相命中率：候选里真正生成接触的比例，过低说明宽相太肥
• 醒岛数
• 宽相/窄相/求解时间饼图

过早优化层次网格，场景却是 40 个尺寸相近的箱子，纯浪费。用场景分类决定结构，用指标验证。换关卡重新测， boos 关卡的格边长不是沙漠关卡的。

⚠️ 常见坑：用屏幕空间格子做宽相。摄像机一转，物理配对全变，确定性与逻辑都错。空间结构必须在世界系。

内存：网格桶、BVH 节点预分配。扩容打日志。物理中途分配是尖峰来源，6.1 已说，空间结构是重灾区。

CCD 物体集合单独用线性表都无所谓，因为数量少。不要给 CCD 再做一套复杂树，除非分析器要求。

毕业实验：n 从 50 增到 2000，画宽相耗时曲线。暴力应抛物线，网格应接近直线直到挤格。这张图是 6.3 的交付物，比背诵 O(n log n) 有用。

多层细节：远景用更大代理碰撞体，减少动态体数。这是复杂度的根号——减少 n。游戏里最强优化常常是“这堆碎片 2 秒后删掉并换成静态残骸网格”。算法优化前先问能否少模拟。

与渲染剔除不同：看不见的箱子仍可能被看见的箱子撞到，不能因摄像机剔除而睡眠。睡眠只看速度，不看镜头。不要把视锥体当宽相。

实践问答

为什么要两张曲线：均匀和带密集堆？

均匀显示平均线性，密集堆显示最坏上翘。只看均匀会低估爆炸关卡。两张一起才完整。

视锥剔除能不能当宽相？

不能。看不见的箱子仍可能被看见的撞到。睡眠看速度，不看镜头。摄像机不是物理空间结构。

动态 BVH 增量为什么不是默认？

树会歪，查询变慢，漏检 bug 难查。几百动态体每帧重建往往更老实。静态才 SAH 烘焙。

减 n 有哪些产品手段？

冻碎片成静态合并、远距代理盒、到期删除。问设计这些石头是否必须每帧活着。算法优化前先问。

候选比多少算病？

个位数到几十常见。上百检查格边长和掩码。突然翻十倍查 NaN 原点或掩码失效。进 7.1 看板。

CCD 要不要单独一棵树？

通常不要。CCD 物体少，线性表够。分析器要求再加。过早上树是复杂度迷信。

参数扫描笔记：空间结构

扫描 1：只画均匀曲线

低估密集堆最坏。两张图。

扫描 2：动态用静态 SAH 每帧重建

构建过贵。动态中点切，静态烘焙。

扫描 3：CCD 再做一套树

物体少线性表够。

扫描 4：远景仍全精度动态碎石

减 n 先于更好的树。

扫描 5：桶扩容在 step 中途

尖峰。预分配。

扫描 6：候选比突然翻十倍

掩码或原点。看板要有。

扫描 7：开放世界用单层均匀格

尺寸两极崩溃。层次网格或 BVH。

扫描 8：SAP 当 3D 开放世界默认

爆炸排序尖峰。2D 小幅运动更爱 SAP。

扫描 9：重建 vs 增量不测可预测性

平均 1.2 毫秒但偶发 20 毫秒更恨。

扫描 10：把视锥当宽相优化

逻辑错。看不见仍能被撞。

工程备忘录

备忘 1

和美术、策划交接「03-空间结构与复杂度」参数时，用测试盒而不是形容词。说清楚二十厘米台阶能上、八十厘米不能，比说手感更跟手有用。测试盒还能在引擎升级后当合同跑一遍。 本条对应「03-空间结构与复杂度」第 1 号备忘，和相邻条目不要合并成一句空话，分开验收。

备忘 2

「03-空间结构与复杂度」若跨模块耦合，先单向再双向。布料先撞静地，流体先撞静箱，关节先吊静锚。双向一步到位时，你分不清是 A 推 B 写错还是 B 还力写错。控制变量不是学术，是省生命。 本条对应「03-空间结构与复杂度」第 2 号备忘，和相邻条目不要合并成一句空话，分开验收。

备忘 3

睡眠和唤醒属于「03-空间结构与复杂度」正确性，不只是性能。该醒不醒会穿模，不该醒全醒会卡顿。爆炸查询、关节边、运动学平台都是唤醒图的边。漏一条边，现场像鬼。 本条对应「03-空间结构与复杂度」第 3 号备忘，和相邻条目不要合并成一句空话，分开验收。

备忘 4

「03-空间结构与复杂度」的默认值要进协议版本。改默认迭代次数、默认 dt、默认皮肤半径，旧回放会分叉。版本头拒绝错版本，比静默错乱重放更负责任。 本条对应「03-空间结构与复杂度」第 4 号备忘，和相邻条目不要合并成一句空话，分开验收。

备忘 5

先写 2D 再写 3D 适用于「03-空间结构与复杂度」里所有几何麻烦事。二维金字塔、二维绳、二维铰链能看见点的增减。三维裁剪 bug 极难看，会让你怀疑人生。二维过了再加一根轴。 本条对应「03-空间结构与复杂度」第 5 号备忘，和相邻条目不要合并成一句空话，分开验收。

备忘 6

「03-空间结构与复杂度」不要在热路径调用脚本。求解器迭代十次回调十次，缓存和确定性一起死。标记事件，步末再发。这是布局问题也是架构问题。 本条对应「03-空间结构与复杂度」第 6 号备忘，和相邻条目不要合并成一句空话，分开验收。

备忘 7

对账数字比观感先行。静止支撑冲量是否接近质量乘重力乘 dt，自由落体一秒是否接近四点九米，两球对心是否交换速度。「03-空间结构与复杂度」相关实现先过对账，再谈好看。 本条对应「03-空间结构与复杂度」第 7 号备忘，和相邻条目不要合并成一句空话，分开验收。

备忘 8

「03-空间结构与复杂度」出抖动时按清单：时间步是否固定、流形点是否闪、法向是否跳、恢复系数是否在静止时仍生效、bias 是否过大、迭代是否其实在清零热启动。不要先把摩擦系数调到十。 本条对应「03-空间结构与复杂度」第 8 号备忘，和相邻条目不要合并成一句空话，分开验收。

备忘 9

空间结构必须在世界系。把「03-空间结构与复杂度」绑到摄像机或屏幕格子，逻辑和确定性都会在转视角时崩。渲染剔除不能代替宽相，看不见的物体仍能被撞到。 本条对应「03-空间结构与复杂度」第 9 号备忘，和相邻条目不要合并成一句空话，分开验收。

备忘 10

「03-空间结构与复杂度」的预分配策略：按关卡上限留容量，超出打日志并降级，不要在 step 中途默默扩容。扩容是卡顿尖峰，也是回放时分配顺序不同导致的潜在分叉源。 本条对应「03-空间结构与复杂度」第 10 号备忘，和相邻条目不要合并成一句空话，分开验收。

备忘 11

把「03-空间结构与复杂度」相关的失败做成最小复现：关掉渲染特效、关掉音频、只留固定 dt 的 step 和一份输入日志。能在十秒内重放出来的 bug 才叫被抓住。不能重放就先补录制，再谈修。很多人在这一步省时间，后面用几天陪着偶发抖动。 本条对应「03-空间结构与复杂度」第 11 号备忘，和相邻条目不要合并成一句空话，分开验收。

备忘 12

在「03-空间结构与复杂度」路径上加计数器要进 step 末尾快照，不要在热循环里格式化字符串。计数器本身若分配内存，你会优化一个被测量污染的世界。发布版可用宏剥掉绘制，但计数器的定义要保留，方便线上开一个极轻的统计开关。 本条对应「03-空间结构与复杂度」第 12 号备忘，和相邻条目不要合并成一句空话，分开验收。

备忘 13

「03-空间结构与复杂度」一旦和随机数沾边，随机必须绑在 tick 上。墙钟、哈希表遍历、线程完成顺序都是隐藏输入。隐藏输入会让哈希校验在某一帧突然红，而你却以为是公式写错。先排除隐藏输入，再怀疑有效质量。 本条对应「03-空间结构与复杂度」第 13 号备忘，和相邻条目不要合并成一句空话，分开验收。

要点速记

• 网格平均线性、挤格平方；SAP 怕全重叠；BVH 质量靠构建。
• 静态烘焙、动态可每帧重建，增量不是默认更优。
• 用候选比和计时曲线验收，不要只谈大 O。
• 世界系结构，绝不用屏幕格。
• 预分配防尖峰；CCD 集合通常很小。
• 减少 n 是最强优化：代理、合并残骸、删碎片。
• 视锥剔除不能当物理宽相。

下一章把看不见的东西画出来，并让同样输入得到同样轨迹，最后谈何时自研、何时用现成引擎。