碰撞检测系统

可碰撞实体

• 碰撞表示是独立的数据结构，既不同于对象的玩法表示，也不同于视觉表示（三角网格、细分曲面、粒子等）。形状应尽量简单：石头用球，车引擎盖用盒，人体用一组相连的胶囊；只有简单表示不够用时才上复杂形状（卷 II 14.3.1）。
• Havok 称之为 collidable（hkpCollidable），PhysX 称为 actor（NxActor）。两者都包含形状和变换。需要变换的三个理由：形状通常以原点为中心、按规范朝向定义，必须变换到世界；移动复杂形状时只改变换比逐个移动顶点便宜；复杂形状占内存，多个 collidable 可以共享一个形状（赛车游戏里很多车形状相同）。
• 一个游戏对象可以没有、有一个或有多个 collidable（关节机械臂的每个刚性部件一个）。

碰撞世界与物理世界

• 碰撞系统用一个单例数据结构管理全部 collidable，即碰撞世界（Havok hkpWorld，PhysX NxScene，ODE dSpace 是包含所有碰撞形状的几何体层级之根）。好处：只包含可能碰撞的对象，不用遍历无关数据；数据可以按最高效的方式组织（缓存一致性）；也是良好的封装，利于可理解性、可维护性、可测试性和复用（卷 II 14.3.2）。
• 有刚体动力学时，它通常与碰撞系统共享这个"世界"，每个刚体对应一个 collidable（反之不一定），物理系统驱动碰撞系统每个时间步至少运行一次碰撞测试，所以常称为碰撞/物理世界。Havok 中 hkpRigidBody 恰好指向一个 hkpCollidable；PhysX 的 NxActor 兼任两者（刚体物理属性另存在 NxBodyDesc）。刚体可设为固定，只作碰撞体用。多数 SDK 仍尽量把碰撞库与动力学分开，以便单独使用碰撞，甚至替换碰撞系统（GEA 说实际上没那么容易）（卷 II 14.3.2.1）。
• 原书问题（API 年代）：书中 PhysX 类名 NxActor、NxScene、NxBodyDesc 属于 PhysX 2.x。PhysX 3 起 Nx 前缀改为 Px，单一 actor 类拆成层级（PxRigidActor → PxRigidStatic / PxRigidDynamic 等），多数描述符 (descriptor) 被创建函数的参数取代，对象由 PxPhysics 创建后再 scene->addActor()（NVIDIA PhysX SDK 3.4 文档 "Migrating From PhysX SDK 2.x to 3.x"）。概念（actor 兼任碰撞体与刚体、场景即物理世界）不变。

形状的概念

• 形状是由边界围成、有明确内外的空间区域：2D 有面积，边界是曲线或多边形；3D 有体积，边界是曲面或多面体。地形、河流、薄墙更适合用曲面（有正反面、无内外）。多数 SDK 把"形状"扩展到开放曲面，并允许给曲面一个挤出厚度，减少小而快的物体穿过无限薄曲面的"子弹穿纸"问题（卷 II 14.3.3）。
• 相交严格说是两个形状共有点的集合；游戏通常只想知道是否相交，以及接触信息：分离向量（沿它移动即可脱离碰撞）、哪两个 collidable、哪些子形状甚至哪些特征接触、投影到分离法线上的速度等。Havok 用 hkContactPoint 返回（卷 II 14.3.3.1–14.3.3.2）。
• 凸性：从内部出发的射线不会穿出表面超过一次；直观判断是"用保鲜膜包起来没有气泡"。2D 中圆、矩形、三角形是凸的，吃豆人 (Pac-Man) 不是。凸形状之间的相交检测更简单、更便宜（卷 II 14.3.3.3）。

碰撞图元

（卷 II 14.3.4）几何细节见 几何图元的表示 与 包围体构建。

poly soup 有没有内部：它可能只是开放曲面，信息不足以判断该往哪个方向把穿插的物体推出去。办法是让所有三角形绕序一致，整体就有正反面；再记录是否闭合（若离线工具能判定），闭合时把正反解释为外内。开放曲面（如地形）也可以约定"正面总背离地心"，即正面就是外部，但通常需要定制碰撞引擎让它理解这一约定（卷 II 14.3.4.7）。

解析几何与相交测试

• 点-球：$s=c-p$，$|s|\le r$ 则在内。球-球：$|c_1-c_2|\le r_1+r_2$；两边平方可省去开方：$s\cdot s\le(r_1+r_2)^2$（卷 II 14.3.5.1–14.3.5.2）。
• 分离轴定理：若存在一条轴，使两个凸形状在其上的投影区间 $[c_{min},c_{max}]$ 不重叠，则它们不相交；凸形状找不到这样的轴就一定相交（凹形状不成立，这也是偏好凸形状的原因之一）。区间不相交当且仅当 $c^A_{max}<c^B_{min}$ 或 $c^B_{max}<c^A_{min}$。两球即将接触时唯一的分离轴平行于球心连线，分开越远可选的轴越多（卷 II 14.3.5.3）。更多见 相交测试基础与分离轴。
• AABB-AABB：分离轴只可能是三条坐标轴，三个轴上的区间都重叠才相交（卷 II 14.3.5.4），见 包围体重叠测试。
• GJK（Gilbert、Johnson、Keerthi）：适用于任意凸多面体。两个凸形状的闵可夫斯基差 $\{A_i-B_j\}$ 包含原点当且仅当两者相交；差本身是凸的，只需关心其凸包。算法从凸包内任一点构成的单纯形开始，每次朝原点方向找凸包上的支撑顶点加入单纯形（点→线段→三角形→四面体）；若单纯形包住原点则相交，若找不到比当前单纯形更接近原点的支撑点则不相交。GEA 推荐 Casey Muratori 的视频 "Implementing GJK"，以及原论文、Christer Ericson 与 Gino van den Bergen 的 SIGGRAPH/GDC 讲稿（卷 II 14.3.5.5）。
  • 原书问题（支撑顶点的定义）：书中把支撑顶点说成"凸包上沿当前方向最接近原点的顶点"。标准定义正相反：方向 $d$ 上的支撑点是 $s(d)=\arg\max_{x\in C} d\cdot x$，即沿 $d$ 最远的点；对闵可夫斯基差有 $s_{A-B}(d)=s_A(d)-s_B(-d)$（Ericson《Real-Time Collision Detection》9.5 节；Wikipedia "Gilbert–Johnson–Keerthi distance algorithm"、"Support function"）。GJK 正是靠"最远点都越不过原点"来判定不相交。
  • 书中解释闵可夫斯基差时一句写成"sphere A 和 sphere B 有公共点"，应为一般形状 A、B（前后文都在讲任意形状）。另外"差包含原点 ⇔ 相交"其实对任意形状都成立，凸性真正的作用是让差也是凸的、可以用单纯形逼近。

flowchart TD
  S["单纯形 = 闵可夫斯基差内任一点"] --> D["求单纯形指向原点的方向"]
  D --> V["沿该方向找差的支撑顶点"]
  V --> C{"支撑点比当前单纯形更接近原点?"}
  C -- "否" --> N["不相交"]
  C -- "是" --> A["加入单纯形，升一维"]
  A --> O{"单纯形包住原点?"}
  O -- "是" --> Y["相交"]
  O -- "否" --> D

上图按 GEA 对 GJK 的文字描述绘制；真实实现还会在每步丢弃不需要的单纯形顶点，书中未展开。

形状组合与双重分派

N 种形状需要 $O(N^2)$ 种两两测试，这是碰撞引擎复杂性的主要来源，所以引擎会限制图元种类；GJK 受欢迎也因为它用一个算法覆盖所有凸形状，只是支撑函数因形状而异。选择测试函数常用双重分派：按两个对象类型索引的二维函数表，或先按 A 的类型调一个虚函数、再在其中按 B 的类型调第二个虚函数。Havok 用碰撞代理（hkpSphereSphereAgent、hkpGskConvexConvexAgent 等）处理具体组合，由 hkpCollisionDispatcher 管理二维分派表（卷 II 14.3.5.6）。

运动物体与隧穿

• 最简单的做法是把每个时间步的世界当作静止快照做静态测试。只要物体相对自身尺寸不太快就很好用，Havok 默认如此（卷 II 14.3.5.7）。
• 小而快的物体一步移动距离大于自身尺寸时，前后两个快照之间有空隙，中间的物体会被完全漏掉，即"子弹穿纸"或隧穿 (tunneling)。
• 扫掠形状：形状从上一快照移到当前快照扫出的新形状（扫掠球 = 胶囊，扫掠三角形 = 三棱柱），相当于对运动线性插值。沿曲线扫掠的凸形状不再凸；旋转中的凸形状即使沿线段扫掠也不一定凸，用两快照极端特征线性外推可以得到凸形状，但未必反映真实运动。
• 连续碰撞检测 (CCD)：求一个时间区间内两物体最早的冲击时间 (TOI)。保存每个 collidable 上一步与当前步的位置和朝向，分别线性插值得到中间时刻的近似变换，再沿路径搜索最早 TOI。常见方法：Brian Mirtich 的保守前进法、对闵可夫斯基和做射线投射、取各特征对的最小 TOI；Erwin Coumans 提出了保守前进的变体。

性能优化

• 碰撞检测吃 CPU 的两个原因：单次相交计算不简单；物体多时测试对数急剧增长，暴力两两测试是 $O(n^2)$。实际会用空间哈希、空间细分或层次包围体（卷 II 14.3.6）。
• 时间相干性（帧间相干性）：速度合理时位置朝向帧间变化不大，可以跨时间步缓存结果。Havok 的碰撞代理通常跨帧持久，只要运动没让之前的计算失效就复用（卷 II 14.3.6.1）。
• 空间划分：八叉树、BSP 树、kd 树、球树等层次结构；沿一个分支向下时，该分支中的对象不可能与兄弟分支中的对象碰撞（卷 II 14.3.6.2）。见 空间数据结构 与 空间分区。
• 宽相、中相、窄相（Havok 的三级筛选）：宽相用粗略 AABB 找可能相交的 collidable；中相测复合形状的粗包围体（复合形状可以嵌套，一般是一棵包围体层次）；窄相测具体图元（卷 II 14.3.6.3）。
• 扫描剪除 (sweep and prune)：GEA 说 Havok、ODE、PhysX 等主要引擎的宽相都用它。原书问题（以偏概全）：SAP 很常见，但并非唯一或默认：ODE 提供 dSimpleSpace、dQuadTreeSpace、dHashSpace、dSAPSpace 四种宽相空间（ODE Wiki "How Collision Detection Works"）；Bullet 同时提供 btDbvtBroadphase（动态 AABB 树，插入删除比 SAP 快，适合大量运动物体）和 btAxisSweep3（SAP）（Bullet 2.83 User Manual；btDbvtBroadphase.h 注释）；PhysX 4 起有多种宽相并加入 automatic multi-broad phase（NVIDIA "PhysX SDK 4.0 Available Now"）。把各 AABB 在三条主轴上的最小、最大值排序，遍历有序列表找重叠。借助帧间相干性，$O(n\log n)$ 的排序可降到期望 $O(n)$；物体旋转时更新 AABB 也能受益。

碰撞过滤

• 例：多数物体应能穿过水面（再用浮力模拟让它浮起或沉底）。按游戏规则接受或拒绝接触称为碰撞过滤（卷 II 14.3.8）。
• 层与掩码：Havok 中每个 collidable 属于且只属于一个碰撞层，默认过滤器 hkpGroupFilter 为每层维护一个 32 位掩码，每一位表示能否与另一层碰撞。
• 回调：碰撞库检测到碰撞时调用回调决定接受或拒绝。Havok 在接触点首次加入时调用 contactPointAdded()，确认有效后（可能因找到更早的 TOI 接触而无效）调用 contactPointConfirmed()，应用都可以在其中拒绝。
• 碰撞材质：类似渲染材质，给每个碰撞表面关联一组属性：撞击声音与粒子、恢复系数和摩擦系数、过滤信息等。简单图元整体一个材质；poly soup 可以逐三角形指定，所以绑定要紧凑，常用 8/16/32 位整数索引全局材质数组，或一个指针。

与 UE5 的对照