从零实现C++碰撞检测系统：架构、算法与性能优化-平芜编程栈

1. 项目概述：为什么我们要亲手造轮子？

如果你正在用C++开发游戏、物理模拟器，或者任何需要处理物体交互的图形应用，那么“碰撞检测”这个词对你来说一定不陌生。市面上有成熟的物理引擎，比如Bullet、Box2D，Unity和Unreal Engine也内置了强大的碰撞系统。既然如此，我们为什么还要“从零开始”实现一个C++碰撞检测系统？这听起来像是一个费力不讨好的“造轮子”行为。

但恰恰是这个过程，能让你真正掌握那些被封装在引擎黑盒里的底层原理。当你调用Physics.Raycast或者AddForce时，你知道引擎背后是如何判断两个复杂模型是否相交的吗？你知道为了优化性能，成千上万的物体是如何被高效组织起来，避免进行O(n²)次两两检测的吗？亲手实现一遍，你得到的将不仅仅是“会用”一个API，而是深刻理解其设计哲学、性能瓶颈和优化边界。这对于解决那些引擎无法直接处理的怪异Bug、进行深度的性能调优，甚至是设计全新的交互逻辑，都是至关重要的底层能力。这篇文章，就是带你走过这段“知其然，更知其所以然”的旅程，从最基础的数学概念开始，一步步构建一个具备实用价值的碰撞检测框架。

2. 碰撞检测系统的核心架构设计

一个完整的碰撞检测系统远不止一个bool CheckCollision(A, B)函数。它需要一套清晰的架构来管理场景中所有的碰撞体（Collider），并高效地处理它们之间的交互。一个典型的自研系统可以分为以下几个核心层次。

2.1 数据层：碰撞体的抽象与表示

首先，我们需要定义什么是“可碰撞的物体”。在底层，一个碰撞体通常由两部分组成：几何形状（Shape）和变换信息（Transform）。

几何形状定义了物体的“固有形态”。我们从一个最简单的AABB（轴对齐包围盒）开始。它本质上是一个长方体，但其边与坐标轴平行，这使得它的相交检测极其高效——只需比较最大最小坐标。我们用一个结构体来表示：

struct AABB { glm::vec3 min; // 最小顶点坐标 (x_min, y_min, z_min) glm::vec3 max; // 最大顶点坐标 (x_max, y_max, z_max) // 根据一个点集（比如模型的顶点）计算AABB void Fit(const std::vector<glm::vec3>& points) { min = max = points[0]; for (const auto& point : points) { min = glm::min(min, point); max = glm::max(max, point); } } // 判断两个AABB是否相交 bool Intersects(const AABB& other) const { return (max.x > other.min.x && min.x < other.max.x) && (max.y > other.min.y && min.y < other.max.y) && (max.z > other.min.z && min.z < other.max.z); } };

注意：glm::vec3来自GLM数学库，它是一个在图形学中广泛使用的头文件库。如果你不想引入外部依赖，也可以自己实现一个简单的三维向量类，包含x, y, z和基本的加减、比较操作。

然而，AABB是轴对齐的，一旦物体旋转，它的AABB就会变得非常“臃肿”，包含大量空白区域，导致检测精度下降。这时，我们就需要引入OBB（有向包围盒）。OBB也是一个长方体，但它的方向是任意的，需要用一个变换矩阵（包含旋转、缩放）来定义。它的相交检测涉及分离轴定理（SAT），比AABB复杂得多，但精度更高。

更复杂的形状还有球体（Sphere）、胶囊体（Capsule）、凸包（Convex Hull）甚至三角形网格（Triangle Mesh）。一个健壮的系统需要设计一个基类CollisionShape，然后派生出各种具体形状。这里就涉及到一个关键设计选择：是用继承还是用组件（如std::variant）？

继承方案：设计一个Shape基类，包含虚函数如GetType()、GetAABB(const Transform&)、TestIntersection(const Shape&, ...)。优点是扩展性强，符合传统OOP思想。缺点是虚函数调用有开销，且需要处理复杂的双分派（Double Dispatch）问题来判断两个未知具体类型的形状是否相交。
组件/标签方案：使用std::variant<AABB, Sphere, OBB, ...>来存储形状。通过std::visit来访问具体类型。优点是内存布局紧凑，能利用现代C++的编译期多态，性能可能更好。缺点是类型列表需要预先确定，扩展稍显繁琐。

对于学习目的，我建议从继承开始，因为它概念更清晰。我们可以这样设计：

enum class ShapeType { AABB, Sphere, OBB /*, ...*/ }; class CollisionShape { public: virtual ~CollisionShape() = default; virtual ShapeType GetType() const = 0; // 获取该形状在当前变换下的AABB（用于空间划分的粗略检测） virtual AABB GetAABB(const Transform& transform) const = 0; }; class SphereShape : public CollisionShape { public: float radius; // ... 实现虚函数 }; class BoxShape : public CollisionShape { // 可以是AABB或OBB public: glm::vec3 halfExtents; // 从中心到各面的距离 // 对于OBB，还需要一个旋转矩阵 // ... 实现虚函数 };

2.2 逻辑层：碰撞对生成与粗检测（Broad Phase）

当场景中有N个物体时，进行两两精细检测（Narrow Phase）的复杂度是O(N²)，这在N很大时（比如超过1000）是完全不可接受的。粗检测（Broad Phase）的目标就是快速剔除那些明显不可能相交的物体对，将需要精细检测的候选对数量减少到O(N)或O(N log N)级别。

最经典的粗检测算法是基于空间划分（Spatial Partitioning）。我们这里重点实现一个简单高效的动态AABB树（Dynamic Bounding Volume Hierarchy, Dynamic BVH）。它的思想是：为每个碰撞体计算一个包围盒（通常是AABB，因为它计算快），然后将这些包围盒组织成一棵二叉树。树的每个节点都存储一个能包围其所有子节点AABB的更大的AABB。

当需要检测碰撞时，我们从根节点开始递归：

如果当前节点是叶子节点（存储了一个碰撞体），则将其加入待检测列表。
如果当前节点是内部节点，则检查查询的AABB是否与该节点的AABB相交。
- 不相交：该节点下的所有物体都不可能相交，整棵子树被剔除。
- 相交：递归检查它的两个子节点。

这样，我们只需要检查与查询AABB相交的那些叶子节点。对于两两检测，我们可以通过遍历树来生成所有可能相交的叶子节点对。

动态BVH的难点在于更新。物体移动后，其AABB发生变化，需要更新它在树中的位置。一个简单策略是：先删除该叶子节点，然后用新的AABB重新插入。为了保持树的平衡（避免退化成链表），在插入和删除时需要一些旋转或重构策略。

实操心得：在项目初期，不必追求完美的动态BVH。可以先实现一个简单的基于网格（Grid）的划分：将世界空间划分为均匀的单元格，每个物体根据其AABB所在的单元格注册进去。检测时，只检查与物体所在单元格相邻的单元格内的物体。这种方法实现简单，对于物体均匀分布的场景效果不错，是快速验证想法的好工具。

2.3 逻辑层：精细检测（Narrow Phase）与碰撞信息

粗检测给我们提供了一个“可能碰撞”的物体对列表。接下来，精细检测（Narrow Phase）就要对这些候选对进行精确的几何相交测试，并计算出详细的碰撞信息。

碰撞信息（ContactManifold）通常包括：

碰撞点（Contact Point）：一个或多个物体表面的接触点。
碰撞法线（Contact Normal）：垂直于接触面的方向，通常从物体A指向物体B，用于计算反弹。
穿透深度（Penetration Depth）：物体相互嵌入的深度，用于将物体推开（解决穿透）。

不同的形状组合需要不同的检测算法：

球体 vs 球体：最简单。计算圆心距离，与半径和比较。碰撞点位于圆心连线上，法线即连线方向。
AABB vs AABB：如前所述，比较坐标即可。但计算碰撞信息（特别是多个接触点）稍复杂，通常简化为找到最小穿透深度的面。
OBB vs OBB或凸包 vs 凸包：使用分离轴定理（SAT）。核心思想是：如果能找到一条轴，使得两个物体在该轴上的投影不重叠，则它们不相交；如果所有候选轴上的投影都重叠，则它们相交。对于OBB，候选轴就是两个盒子各自的三个面法向量，以及它们边向量的叉积（共15条轴）。这是碰撞检测中的核心算法，务必理解透彻。
球体 vs AABB/OBB：计算球心到盒子的最近点，然后判断该点与球心的距离。
胶囊体 vs 三角形网格：更复杂，通常用于角色控制器。需要用到射线与三角形的相交检测（Möller–Trumbore算法），以及点到线段、点到三角形的距离计算。

实现时，我们可以使用一个双分派（Double Dispatch）模式。定义一个CollisionDetector类，里面包含一系列静态函数，如DetectSphereSphere,DetectSphereBox,DetectBoxBox等。然后通过形状类型的组合来调用相应的函数。

struct ContactPoint { glm::vec3 point; glm::vec3 normal; float depth; }; using ContactManifold = std::vector<ContactPoint>; class CollisionDetector { public: static bool Detect(const SphereShape& a, const Transform& ta, const SphereShape& b, const Transform& tb, ContactManifold& outManifold); static bool Detect(const SphereShape& a, const Transform& ta, const BoxShape& b, const Transform& tb, ContactManifold& outManifold); static bool Detect(const BoxShape& a, const Transform& ta, const BoxShape& b, const Transform& tb, ContactManifold& outManifold); // ... 更多组合 };

3. 核心算法深度剖析与实现细节

理解了架构，我们来深入几个最核心算法的实现细节，这是整个系统的灵魂所在。

3.1 分离轴定理（SAT）在OBB碰撞中的实战

SAT是处理凸体相交检测的利器。对于两个OBB的检测，步骤如下：

准备数据：每个OBB由中心c、三个互相垂直的单位方向向量u[0],u[1],u[2]（即旋转矩阵的基向量），以及在这三个方向上的半长e[0],e[1],e[2]定义。
计算候选分离轴：总共15条轴。
- A的3个面法线（Au0, Au1, Au2）。
- B的3个面法线（Bu0, Bu1, Bu2）。
- A的每个边方向与B的每个边方向的叉积（3x3=9条），即Au_i x Bu_j。注意叉积可能得到零向量，需要忽略。
对每条轴L进行投影测试：
- 计算两个OBB中心在该轴上的投影距离：d = | (cB - cA) · L |。
- 计算两个OBB在该轴上的“投影半径”：
  - 对于OBB A:rA = eA0*|Au0·L| + eA1*|Au1·L| + eA2*|Au2·L|
  - 对于OBB B:rB = eB0*|Bu0·L| + eB1*|Bu1·L| + eB2*|Bu2·L|
- 如果d > rA + rB，则在此轴上投影不重叠，找到了分离轴，立即返回“不相交”。
如果所有15条轴都未能分离，则两个OBB相交。

实现时，最大的性能优化点是提前退出。一旦找到一条分离轴，检测立即结束。此外，计算投影半径时，点积的绝对值运算|Au_i·L|可以预先计算好一个3x3的旋转矩阵R，其中R[i][j] = Au_i · Bu_j，这样在计算叉积轴上的投影时会方便一些。

注意事项：SAT只能告诉你是否相交。要获取碰撞信息（法线、深度），需要额外计算。通常，我们选择穿透深度最小的那条轴作为碰撞法线方向。这条轴就是使(rA + rB - d)值最大的那条轴（且d不为0）。深度就是该值。碰撞点的计算则更为复杂，通常涉及寻找两个多面体的接触特征（面-面、边-边、点-面等），可以使用GJK（Gilbert–Johnson–Keerthi）算法或EPA（Expanding Polytope Algorithm）来求取。对于刚入门，可以先只实现相交检测，碰撞信息用近似值（如中心连线方向）。

3.2 动态AABB树的实现与优化

实现一个可用的动态BVH，我们需要定义树节点：

struct BVHNode { AABB aabb; // 该节点包围的AABB BVHNode* left = nullptr; BVHNode* right = nullptr; BVHNode* parent = nullptr; Collider* collider = nullptr; // 如果是叶子节点，指向对应的碰撞体 int height = 0; // 节点高度，用于平衡 bool IsLeaf() const { return collider != nullptr; } };

核心操作包括：

插入（Insert）：递归地将新节点的AABB与当前节点比较，选择能使合并后AABB面积增量最小的子节点方向向下，直到找到叶子节点，将其替换为一个新的内部节点，该内部节点有两个子节点：原来的叶子节点和新插入的节点。然后需要向上更新父节点的AABB和高度。
删除（Remove）：将目标叶子节点从其父节点中移除。如果父节点（现在只有一个子节点）的父节点存在，用这个子节点替代父节点。然后向上更新AABB和高度。
更新（Update）：如果物体的AABB移动后仍然被当前节点的AABB所包含，则可以不用调整树结构，只需更新叶子节点的AABB并向上更新父节点AABB。如果移动后超出了当前节点的AABB，则执行一次Remove后接Insert。
查询（Query）：如前所述，递归地进行AABB相交测试。

平衡优化：不平衡的树会严重降低查询效率。在插入或删除后，我们可以像AVL树或红黑树那样进行旋转操作，但基于AABB的旋转平衡条件不同。一个更简单实用的启发式方法是：定期（比如每帧或每N次更新后）对整棵树进行完全重构。我们可以将所有叶子节点收集起来，然后使用一种高效的方法（如表面面积启发式SAH）重新构建一棵平衡的树。虽然单次开销大，但分摊到多帧后，往往能获得更好的整体性能。

3.3 碰撞响应与穿透解决浅析

检测到碰撞后，系统通常需要给出响应。这属于“物理引擎”的范畴，但我们的碰撞检测系统需要为其提供准确的数据。最基本的响应是解决穿透（Penetration Resolution），也叫“推离”。

假设我们得到了碰撞法线n和穿透深度d。最简单的解决方法是直接沿着法线方向将两个物体分开：

// 假设物体A是动态的，物体B是静态的 transformA.position += n * d;

但这会产生抖动，特别是当多个碰撞同时发生时。更稳定的方法是使用迭代求解或脉冲/约束求解器。例如，可以存储一个“位置修正”向量，在一帧内对所有碰撞进行多次迭代修正，逐步消除穿透。

更复杂的响应包括计算碰撞冲量（Impulse），改变物体的速度（线性速度和角速度），模拟摩擦和弹性。这需要物体的质量、惯性张量等物理属性。虽然超出了纯碰撞检测的范围，但一个设计良好的碰撞检测系统应该能方便地与物理层对接，输出足够的信息（碰撞点、法线、相对速度等）供物理层计算。

4. 系统集成与性能优化实战

有了核心组件，我们需要将它们集成到一个可用的CollisionWorld或PhysicsScene中。

4.1 主循环与对象管理

class CollisionWorld { public: void AddCollider(Collider* collider); void RemoveCollider(Collider* collider); void Update(float deltaTime); // 更新所有动态碰撞体的变换，并更新BVH // 执行一帧的碰撞检测，返回所有碰撞对及其信息 std::vector<CollisionPair> DetectCollisions(); private: std::vector<Collider*> m_Colliders; BVHTree m_BVHTree; // 或 Grid 等空间划分结构 // ... 其他状态 }; void CollisionWorld::Update(float deltaTime) { for (auto& collider : m_DynamicColliders) { collider->UpdateTransform(deltaTime); // 例如，根据速度更新位置 m_BVHTree.Update(collider->GetNode()); // 更新BVH中该碰撞体的节点 } // 可选：定期重构BVH以保持平衡 if (m_FrameCount++ % 60 == 0) { // 每60帧重构一次 m_BVHTree.Rebuild(); } } std::vector<CollisionPair> CollisionWorld::DetectCollisions() { std::vector<CollisionPair> results; // 1. Broad Phase: 使用BVH生成候选对 auto candidatePairs = m_BVHTree.GeneratePairs(); // 2. Narrow Phase: 对每个候选对进行精细检测 for (auto& pair : candidatePairs) { ContactManifold manifold; if (CollisionDetector::Detect( *pair.first->shape, pair.first->GetTransform(), *pair.second->shape, pair.second->GetTransform(), manifold)) { if (!manifold.empty()) { results.push_back({pair.first, pair.second, std::move(manifold)}); } } } return results; }

4.2 性能剖析与关键优化点

实现基本功能后，必须进行性能剖析（Profiling）。在Debug模式下，你的系统可能很慢，这很正常。在Release模式下进行测试，并关注以下几点：

内存布局与缓存友好：Collider对象应尽量紧凑，避免过多指针跳转。将频繁访问的数据（如位置、AABB）连续存储（例如用std::vector<ColliderData>），可以提高CPU缓存命中率。
避免动态内存分配：在DetectCollisions这样的每帧调用函数中，避免使用new或std::vector::push_back导致频繁分配。使用对象池（Object Pool）或预分配内存的容器（如std::vector::reserve）。
简化精细检测：不是所有碰撞对都需要计算完整的ContactManifold。在游戏逻辑中，有时只需要知道“是否碰撞”。可以提供一个快速的TestIntersection函数，它可能在找到一条分离轴后就提前返回，省去计算碰撞点的开销。
分层检测（Layer Masking）：为碰撞体设置层级（Layer）和遮罩（Mask）。只有层级与遮罩匹配的物体才会进行检测。这可以大量减少不必要的检测对。例如，子弹不需要检测其他子弹，背景装饰物不需要相互检测。
时间相干性（Temporal Coherence）：利用上一帧的检测结果。如果两个物体上一帧没有碰撞，且它们在本帧移动不大，那么它们在本帧碰撞的可能性也很低。可以在BVH更新或粗检测阶段利用这个信息进行优化。
并行化：碰撞检测是“令人尴尬的并行”问题。候选对之间的检测是相互独立的。可以使用多线程（如C++11的std::async或std::thread）或SIMD指令来加速精细检测。例如，使用SSE/AVX指令集同时进行多个标量点积运算。

4.3 调试与可视化

一个看不见的碰撞系统是难以调试的。必须实现可视化工具：

绘制包围盒：在Debug渲染中，用线框绘制每个碰撞体的AABB或OBB。用不同颜色表示静态/动态，或者是否处于碰撞状态。
绘制碰撞法线：在碰撞点处绘制一条短线，方向为碰撞法线，长度与穿透深度相关。
打印统计信息：在屏幕上显示每帧处理的碰撞体总数、生成的候选对数量、实际发生的碰撞数量、检测耗时（毫秒）等。这是性能调优的黄金指标。
单步调试与选择：能够暂停游戏，选择特定的碰撞体，高亮显示它，并打印其详细信息（位置、大小、当前碰撞列表等）。

5. 常见陷阱、问题排查与进阶思考

即使按照指南实现，你也一定会遇到各种奇怪的问题。这里记录一些我踩过的坑和解决方案。

5.1 浮点数精度误差与容差处理

这是碰撞检测中最隐蔽的Bug来源。两个理论上刚好接触的物体，由于浮点数计算误差，可能被判定为“轻微穿透”或“微小分离”。

症状：物体在应该停下的地方轻微抖动或缓慢穿透。
解决：引入一个小的容差值（Epsilon），比如1e-6。在比较距离、深度时，使用if (distance < radiusSum + EPSILON)而不是if (distance < radiusSum)。在SAT算法中，当投影距离d非常接近投影半径和rA+rB时，可以认为它们刚好接触。
注意：容差值不能太大，否则会错误地将明显分离的物体判定为碰撞。通常需要根据你的世界尺度来调整。

5.2 高速物体穿透（Tunneling）

当物体移动速度非常快时（比如子弹），它可能在一帧内从A点移动到B点，完全穿过了另一个薄物体，导致两帧的AABB都没有发生相交，从而检测不到碰撞。

症状：高速运动的物体（子弹、炮弹）穿过了墙壁或敌人。
解决：
1. 连续碰撞检测（CCD）：不检测物体在离散时间点的状态，而是检测它们在一段时间内的运动轨迹是否相交。对于AABB，可以计算其在本帧的“扫掠体”（从上一帧AABB到本帧AABB的凸包），然后与目标进行检测。计算量较大。
2. 子步长（Sub-stepping）：将物理更新的时间步长（deltaTime）分成多个更小的子步长。在每个子步长内，物体的位移变小，穿透就不容易发生。这是最常用且相对简单的方法。
3. 扩大包围盒：根据物体的最大速度，适当扩大其包围盒（比如在速度方向上加一个“厚度”），但这会增加误报。

5.3 复杂形状与凸分解

我们的系统目前只处理了基本凸形状（球、盒、胶囊）。对于复杂的凹网格（比如一个茶杯），直接进行SAT或GJK检测是不行的，因为算法只适用于凸体。

解决：将凹网格分解为多个凸体（Convex Decomposition）。有很多算法和工具可以做这件事（如V-HACD库）。然后，一个复杂的碰撞体就由多个凸子碰撞体组成。检测时，分别检测这些子碰撞体与目标的碰撞。只要有一个子碰撞体发生碰撞，就认为整个物体发生了碰撞。
代价：碰撞体数量增加，性能下降。需要权衡精度和性能。