1. 项目概述

在游戏开发、机器人仿真或者任何需要模拟物理世界的场景里，碰撞检测都是最核心、最基础，也最让人头疼的环节之一。想象一下，你精心设计了一个角色，结果它穿墙而过；或者两个物体明明没有接触，却莫名其妙地粘在了一起。这些“灵异事件”的根源，往往就出在碰撞检测上。今天，我们就来深入聊聊C++物理引擎中，从最基础的AABB到被誉为“黑魔法”的GJK，这六种碰撞检测算法的前世今生、实现细节以及那些只有踩过坑才知道的“潜规则”。

这篇文章不是一篇简单的API说明书，而是一个从业者视角的深度剖析。我会结合自己十多年在游戏和仿真引擎开发中的经验，从“为什么需要这么多算法”开始，逐一拆解AABB、OBB、Sphere、Sweep and Prune、SAT（分离轴定理）以及GJK算法的原理、C++实现、性能考量以及它们各自最适合的应用场景。无论你是正在学习游戏物理的在校学生，还是工作中需要优化现有碰撞系统的工程师，相信都能从中找到实用的“干货”和避坑指南。

2. 碰撞检测算法的核心思路与选型逻辑

2.1 为什么没有“一招鲜”的算法？

很多初学者会问，既然GJK这么强大，为什么物理引擎不只用它？答案很简单：性能和复杂度。碰撞检测是一个典型的“分而治之”问题，我们需要一个多层次的检测管道（Pipeline）。

一个高效的物理引擎通常采用“两阶段”或“三阶段”检测策略：

1. 粗检测阶段：快速剔除大量明显不可能发生碰撞的物体对。这个阶段要求算法极其简单、快速，允许一定的误报（即报告了碰撞但实际上没发生），但绝不能漏报。AABB和Sweep and Prune是这个阶段的明星。
2. 精检测阶段：对粗检测筛选出的潜在碰撞对，进行精确的几何相交测试。这个阶段要求算法精确、稳定。对于简单几何体（如球体、AABB、OBB），我们有高效的专用算法；对于复杂的凸体，GJK和SAT就登场了。

这种分层结构，就像机场安检：先看登机牌（粗检测），把明显不对的人排除，再对需要进一步检查的旅客进行细致的行李扫描和人身检查（精检测）。如果对每个人都直接进行最精细的全身扫描，机场早就瘫痪了。

2.2 算法选型矩阵：什么时候用什么？

在动手写代码之前，先根据你的物体形状和性能需求，参考下面的选型矩阵，可以少走很多弯路。

实操心得：在实际项目中，我几乎从未见过只用一种算法的引擎。最常见的组合是：对所有动态物体用AABB做粗检测，对筛选后的物体对，根据其形状类型（如球vs球，球vs盒，盒vs盒，凸体vs凸体）分发到不同的精检测算法。对于复杂的凸体碰撞，GJK是工业标准。

3. 核心算法解析与C++实现要点

3.1 基础包围体：AABB与Sphere

AABB（轴对齐包围盒）的实现核心是存储一个物体在世界坐标系下，沿X、Y、Z轴的最小和最大坐标值。检测两个AABB是否相交，只需要检查它们在每个轴上是否有重叠。

struct AABB { glm::vec3 min; glm::vec3 max; }; bool intersectAABB(const AABB& a, const AABB& b) { // 只要在一个轴上分离，就不相交 if (a.max.x < b.min.x || a.min.x > b.max.x) return false; if (a.max.y < b.min.y || a.min.y > b.max.y) return false; if (a.max.z < b.min.z || a.min.z > b.max.z) return false; return true; // 所有轴都重叠，则相交 }

Sphere（包围球）的检测更简单，就是计算两球心距离并与半径和比较。

struct Sphere { glm::vec3 center; float radius; }; bool intersectSphere(const Sphere& a, const Sphere& b) { glm::vec3 d = a.center - b.center; float dist2 = glm::dot(d, d); // 距离平方 float radiusSum = a.radius + b.radius; return dist2 <= (radiusSum * radiusSum); // 比较平方避免开方 }

注意事项：对于会旋转的物体，每一帧都需要根据物体的变换矩阵重新计算其世界空间的AABB，这是一个开销点。而Sphere的优点是旋转不变，中心点跟着物体走即可，但包围性往往很差。一个常见的优化是：对复杂模型，先用Sphere做一次超快剔除，再用更紧密的AABB做第二次粗筛。

3.2 更紧密的包围：OBB

OBB（有向包围盒）可以随着物体旋转，因此比AABB更紧密。它通常用一个中心点、三个互相垂直的本地轴向量、以及在这三个轴上的半长来表示。

OBB的相交检测比AABB复杂。一种经典方法是**分离轴定理（SAT）**在OBB上的应用。你需要测试15条潜在的分离轴（两个OBB各自的3个轴，以及它们两两组合的叉积，共9个轴）。只要存在一条轴，能让两个OBB在该轴上的投影区间不重叠，它们就不相交。

struct OBB { glm::vec3 center; glm::vec3 axes[3]; // 单位向量，表示本地坐标轴方向 glm::vec3 halfExtents; // 在半长 }; bool intersectOBB(const OBB& a, const OBB& b) { // 实现完整的SAT测试，涉及15条轴的投影区间重叠判断 // 代码较长，核心是计算投影半径和投影中心距离 // ... }

踩坑记录：OBB的SAT检测实现中，最容易出错的地方是轴向量的叉积以及投影半径的计算。投影半径的计算公式是：r = |(halfExtents.x * axisX) · L| + |(halfExtents.y * axisY) · L| + |(halfExtents.z * axisZ) · L|，其中L是测试轴的单位向量。务必确保你的向量点积和绝对值计算正确。

3.3 粗检测的加速器：Sweep and Prune

当场景中有成百上千个物体时，即使AABB两两检测（O(n²)）也会成为瓶颈。Sweep and Prune (SAP)算法可以将复杂度降低到接近O(n log n)。它的核心思想是：只在一个轴（比如X轴）上对每个AABB的最小值和最大值进行排序。

1. 插入：将每个物体的aabb.min.x和aabb.max.x作为端点插入一个列表。
2. 排序：对这个端点列表按X坐标进行排序（可利用上一帧已基本有序的特性，使用插入排序优化）。
3. 扫描：从头到尾扫描排序后的列表。维护一个“活动集合”。
   • 遇到一个min端点，就将对应的物体加入活动集，并与活动集中所有其他物体标记为潜在碰撞对。
   • 遇到一个max端点，就将对应的物体从活动集中移除。
4. 结果：扫描完成后，就得到了所有在X轴上重叠的物体对。为了更精确，通常还会用这些物体对的AABB在Y轴和Z轴上做快速验证。

// 伪代码概念 struct Endpoint { int objId; float value; bool isMin; // true for min, false for max }; void sweepAndPrune(const std::vector<AABB>& aabbs, std::vector<std::pair<int, int>>& potentialPairs) { std::vector<Endpoint> endpoints; // 1. 生成端点 for (int i = 0; i < aabbs.size(); ++i) { endpoints.push_back({i, aabbs[i].min.x, true}); endpoints.push_back({i, aabbs[i].max.x, false}); } // 2. 排序 (例如使用插入排序，利用时间相干性) std::sort(endpoints.begin(), endpoints.end(), [](const Endpoint& a, const Endpoint& b) { return a.value < b.value; }); // 3. 扫描 std::unordered_set<int> activeSet; for (const auto& ep : endpoints) { if (ep.isMin) { for (int activeId : activeSet) { potentialPairs.emplace_back(activeId, ep.objId); } activeSet.insert(ep.objId); } else { activeSet.erase(ep.objId); } } }

实操心得：SAP算法对物体运动速度敏感。如果一个物体在一帧内移动距离超过了自己的大小，可能会发生“隧道效应”——即它从A物体的一端“穿过”到了另一端，而min和max端点没有发生交错，导致漏检。解决方法是使用“扩展的AABB”，即在粗检测阶段使用的AABB，比物体的实际AABB稍微大一圈（根据最大速度估算），为高速物体留出缓冲空间。

3.4 2D世界的利器：分离轴定理

SAT在2D游戏开发中应用极广，因为它不仅能判断是否碰撞，还能给出一个最短的分离向量（可用于碰撞响应，将物体推开）。其原理是：对于两个凸多边形，如果存在一条直线（轴），能将它们在直线上的投影分开，那么这两个多边形就不相交。我们需要测试的轴，就是每个多边形的每条边的法线。

// 2D SAT 示例 (判断两个凸多边形是否相交) bool intersectPolygonsSAT(const std::vector<glm::vec2>& polyA, const std::vector<glm::vec2>& polyB) { // 测试多边形A的每条边作为轴 for (int i = 0; i < polyA.size(); ++i) { glm::vec2 edge = polyA[(i+1)%polyA.size()] - polyA[i]; glm::vec2 axis = glm::vec2(-edge.y, edge.x); // 法线 axis = glm::normalize(axis); // 计算两个多边形在该轴上的投影区间 Projection projA = projectPolygon(polyA, axis); Projection projB = projectPolygon(polyB, axis); // 检查区间是否重叠 if (!overlap(projA, projB)) { return false; // 找到分离轴，不相交 } } // 同样测试多边形B的每条边作为轴 for (int i = 0; i < polyB.size(); ++i) { // ... 类似上述循环 } return true; // 在所有轴上投影都重叠，则相交 }

注意事项：SAT扩展到3D会变得非常复杂，因为需要测试的分离面（不再是轴）是每个面的法线以及每条边的叉积，计算量剧增。因此，在3D中，对于凸体碰撞，更倾向于使用接下来要讲的GJK算法。

4. 凸体碰撞的王者：GJK算法深度解析

GJK（Gilbert–Johnson–Keerthi）算法是现代物理引擎处理凸体碰撞的基石。它巧妙地将“两个凸体是否相交”的问题，转化为“原点是否在它们的闵可夫斯基差集中”的问题。

4.1 GJK的核心思想：闵可夫斯基差与单纯形

闵可夫斯基差：对于两个凸体A和B，它们的闵可夫斯基差集M = A - B = {a - b | a ∈ A, b ∈ B}。这个差集本身也是一个凸集。一个至关重要的结论是：A和B相交，当且仅当原点在M的内部。

GJK算法通过迭代构建一个位于M内部的单纯形（在2D中是三角形，3D中是四面体）来逼近原点。如果这个单纯形包含原点，则物体相交；如果无法构建包含原点的单纯形，则物体分离，并且迭代过程还能给出最近距离。

支持函数：这是GJK的引擎。对于给定方向d，支持函数返回在凸体上沿方向d最远的点。对于闵可夫斯基差集M的支持点，就是support(A, d) - support(B, -d)。

// 支持函数示例：对于一个凸多面体（顶点集） glm::vec3 support(const std::vector<glm::vec3>& vertices, const glm::vec3& direction) { float maxDot = -FLT_MAX; glm::vec3 result; for (const auto& v : vertices) { float dot = glm::dot(v, direction); if (dot > maxDot) { maxDot = dot; result = v; } } return result; } // 闵可夫斯基差集的支持函数 glm::vec3 supportMinkowski(const ConvexHull& hullA, const ConvexHull& hullB, const glm::vec3& direction) { return support(hullA.vertices, direction) - support(hullB.vertices, -direction); }

4.2 GJK算法的迭代过程（3D版本）

GJK算法维护一个最多包含4个点的单纯形（点、线段、三角形、四面体）。以下是其核心循环的简化描述：

1. 初始化：选择一个初始搜索方向d（例如，从B的中心指向A的中心）。计算第一个支持点s = support(M, d)，并将其加入单纯形。
2. 迭代循环： a. 计算新的支持点p = support(M, d)。 b. 如果p在方向d上的投影小于0（即dot(p, d) < 0），说明原点在M之外，物体分离。算法可以终止，并利用当前信息计算最近距离（需要EPA算法辅助）。 c. 将p加入单纯形。 d. 判断原点是否在当前单纯形内部。如果是，则物体相交，算法结束。 e. 如果原点不在内部，则更新单纯形：剔除掉那些对寻找原点方向没有贡献的点，保留一个更小的子单纯形（例如从四面体退化为三角形）。 f. 基于新的单纯形，计算一个新的、指向原点的搜索方向d。 g. 返回步骤a继续迭代。
3. 终止条件：通常设置一个最大迭代次数（如20-30次），或者当搜索方向d的长度接近于零时终止。

核心难点与技巧：GJK实现中最棘手的部分是更新单纯形和计算新的搜索方向。这需要处理单纯形是线段、三角形、四面体等不同情况，并利用向量叉积和点积进行原点与单纯形各面的位置关系判断。网上有很多优秀的图示教程，建议结合代码理解。**一个关键优化是使用“阻尼”或“容差”**来处理数值误差，避免因浮点数精度问题导致算法在原点附近振荡或误判。

4.3 从GJK到EPA：获取碰撞信息

GJK只能判断是否相交。如果相交，我们还需要知道穿透深度和碰撞法线，以便进行物理响应（将物体推开）。这就需要EPA（Expanding Polytope Algorithm）算法。

EPA算法的思路很直观：

1. 当GJK检测到相交时，它已经给出了一个包含原点的单纯形（一个多面体）。
2. EPA将这个单纯形扩展成一个更精细的、包裹原点的多面体（即闵可夫斯基差集M在原点附近的边界）。
3. 在这个多面体上，找到离原点最近的那个面。这个面的法线方向就是碰撞法线，原点到这个面的距离就是穿透深度。

EPA的实现同样涉及复杂的几何计算，包括寻找最近面、扩展多面体、处理退化情况等。在工业级物理引擎中，GJK和EPA通常是成对出现的。

5. 算法实现中的常见问题与排查技巧

5.1 数值稳定性：浮点数的“幽灵”

所有几何算法都受浮点数精度所困。一个经典的GJK/EPA崩溃场景是：当两个物体刚好“擦边”或深度穿透时，计算出的法线或穿透深度出现NaN或极大的值。

排查与解决：

• 容差（Epsilon）是你的朋友：在比较点积、距离时，不要用== 0或> 0，而要用abs(dot) < epsilon或dot > -epsilon。这个epsilon通常取一个很小的值，如1e-6。
• 归一化前检查长度：在glm::normalize(vector)之前，务必检查向量的长度是否大于一个极小阈值，否则会得到无效向量。
• 退化单纯形处理：在GJK迭代中，如果新的支持点与单纯形中已有的点过于接近（共线或共面），会导致单纯形退化，搜索方向计算失败。此时需要检测并特殊处理，比如随机扰动一个搜索方向重新开始。
• 使用双精度：在要求极高的仿真中，可以考虑在碰撞检测阶段使用double精度，尽管这会增加一些计算开销。

5.2 性能调优：让检测飞起来

• 空间划分与Broad Phase：对于超大规模场景，仅靠SAP可能不够。需要引入空间划分结构，如四叉树（2D）、八叉树（3D）、BVH（层次包围盒）或网格法。这些结构能将物体组织起来，快速定位可能相邻的物体，大幅减少需要送入粗检测的物体对。
• 形状特化：不要所有形状都走GJK。为球体、AABB、OBB、胶囊体等常见基本形状编写高度优化的、特化的相交检测函数。这些函数的性能远超通用的GJK。
• 缓存与热启动：对于连续帧，物体的位置和方向通常变化不大。可以缓存上一帧的GJK单纯形或SAT的分离轴作为下一帧计算的初始猜测，这能显著减少迭代次数。这就是所谓的“热启动”。
• 并行化：碰撞检测是“令人尴尬的并行”问题。每一对物体的检测都是独立的。在现代多核CPU上，可以轻松使用线程池（如Intel TBB）或任务系统来并行处理粗检测和精检测。

5.3 内存与缓存友好性

• 数据布局：将物体的位置、旋转、包围盒数据以数组结构体（SoA）的方式存储，而不是结构体数组（AoS）。这有利于SIMD指令优化和缓存预取。

  // 更优的SoA布局 (便于SIMD) struct PhysicsData { std::vector<glm::vec3> positions; std::vector<glm::quat> rotations; std::vector<AABB> aabbs; // ... };

• 避免动态内存分配：在核心的碰撞检测循环中，避免使用new/delete或std::vector的push_back（可能导致扩容）。预先分配好足够大小的固定数组或内存池。

5.4 调试与可视化

“我的碰撞检测为什么错了？” 这是最常遇到的问题。没有可视化，调试几何算法如同盲人摸象。

• 绘制包围盒：在调试模式下，用不同颜色绘制每个物体的AABB、OBB或Sphere。一眼就能看出粗检测阶段是否正确。
• 绘制GJK单纯形：在GJK迭代的每一步，将当前单纯形（点、线、面）绘制出来。你可以清晰地看到算法是如何一步步逼近原点的。
• 绘制碰撞法线与接触点：当检测到碰撞后，在接触点画一条沿着碰撞法线的短线。这能直观验证碰撞信息的正确性。
• 单步执行与状态输出：在关键算法（如GJK循环）中设置断点，并打印出每一步的搜索方向、支持点、单纯形顶点等信息。

6. 从理论到实践：构建一个简易的碰撞检测管道

理论说了这么多，我们如何把它们串起来？下面是一个高度简化的、单线程的碰撞检测管道伪代码框架，它体现了分层的思想：

class SimpleCollisionPipeline { public: void update(float dt) { // 1. 更新所有物体的变换和世界空间包围体 for (auto& obj : m_objects) { obj.updateTransform(dt); obj.updateWorldAABB(); // 更新AABB // 对于需要OBB的物体，也更新OBB } // 2. 粗检测阶段 (Broad Phase) std::vector<PotentialPair> broadPhasePairs; // 方法A: 直接两两AABB检测 (适用于物体少的情况) // bruteForceAABBCheck(m_objects, broadPhasePairs); // 方法B: Sweep and Prune (更高效) sweepAndPrune(m_objects, broadPhasePairs); // 3. 精检测阶段 (Narrow Phase) m_contacts.clear(); for (const auto& pair : broadPhasePairs) { CollisionShape* shapeA = pair.objA->getShape(); CollisionShape* shapeB = pair.objB->getShape(); // 根据形状类型分发到不同的精检测函数 ContactManifold contact; if (shapeA->type == SPHERE && shapeB->type == SPHERE) { if (intersectSphereSphere(..., contact)) { m_contacts.push_back(contact); } } else if (shapeA->type == BOX && shapeB->type == SPHERE) { if (intersectBoxSphere(..., contact)) { m_contacts.push_back(contact); } } else if (shapeA->type == CONVEX_HULL && shapeB->type == CONVEX_HULL) { // 使用GJK/EPA if (intersectGJKEPA(..., contact)) { m_contacts.push_back(contact); } } // ... 其他形状组合 } // 4. 碰撞响应 (物理求解器处理，此处略) // resolveContacts(m_contacts, dt); } private: std::vector<PhysicsObject*> m_objects; std::vector<ContactManifold> m_contacts; };

这个框架虽然简单，但涵盖了从更新、粗检测、精检测到结果收集的全流程。在实际项目中，你需要在此基础上添加空间划分、并行计算、缓存、休眠管理等高级特性。

7. 总结与进阶方向

从简单的AABB到复杂的GJK，我们看到了碰撞检测算法如何通过分层和特化，在精度和性能之间取得精妙的平衡。没有一种算法是万能的，但它们的组合让实时物理仿真成为可能。

如果你已经理解了这些基础算法，并想进一步深入，以下是一些值得探索的进阶方向：

• 连续碰撞检测：解决高速物体的“隧道效应”。不仅检测物体当前帧是否相交，还检测在上一帧到当前帧的移动过程中是否发生了碰撞。这通常涉及扫掠体（Swept Volume）的构造和更复杂的数学。
• 碰撞过滤与图层：不是所有物体都需要相互碰撞。通过设置碰撞图层（Layer）和掩码（Mask），可以高效地过滤掉不必要的检测（比如子弹不和粒子特效碰撞）。
• 软体与粒子碰撞：这涉及到完全不同的领域，如基于SDF（有向距离场）的碰撞检测，或基于位置动力学的约束求解。
• GPU加速碰撞检测：将整个碰撞检测管线（特别是粗检测和GJK）移植到GPU上计算，利用其强大的并行能力处理成千上万的物体。这正是像NVIDIA PhysX 5.0等现代物理引擎正在做的事情。

最后，也是最重要的一点：动手实现一遍。你可以从2D的AABB和SAT开始，再到2D的GJK，最后挑战3D的GJK/EPA。过程中遇到的每一个bug，都会让你对这些算法的理解加深一分。网上有大量优秀的开源参考，如Box2D（2D）、Bullet（3D）和Dyn4j（Java 2D/3D），阅读它们的源码是学习的捷径。记住，在物理引擎的世界里，纸上得来终觉浅，绝知此事要躬行。