1. 项目概述在游戏开发、机器人仿真或者任何需要模拟物理世界的场景里碰撞检测都是最核心、最基础也最让人头疼的环节之一。想象一下你精心设计了一个角色结果它穿墙而过或者两个物体明明没有接触却莫名其妙地粘在了一起。这些“灵异事件”的根源往往就出在碰撞检测上。今天我们就来深入聊聊C物理引擎中从最基础的AABB到被誉为“黑魔法”的GJK这六种碰撞检测算法的前世今生、实现细节以及那些只有踩过坑才知道的“潜规则”。这篇文章不是一篇简单的API说明书而是一个从业者视角的深度剖析。我会结合自己十多年在游戏和仿真引擎开发中的经验从“为什么需要这么多算法”开始逐一拆解AABB、OBB、Sphere、Sweep and Prune、SAT分离轴定理以及GJK算法的原理、C实现、性能考量以及它们各自最适合的应用场景。无论你是正在学习游戏物理的在校学生还是工作中需要优化现有碰撞系统的工程师相信都能从中找到实用的“干货”和避坑指南。2. 碰撞检测算法的核心思路与选型逻辑2.1 为什么没有“一招鲜”的算法很多初学者会问既然GJK这么强大为什么物理引擎不只用它答案很简单性能和复杂度。碰撞检测是一个典型的“分而治之”问题我们需要一个多层次的检测管道Pipeline。一个高效的物理引擎通常采用“两阶段”或“三阶段”检测策略粗检测阶段快速剔除大量明显不可能发生碰撞的物体对。这个阶段要求算法极其简单、快速允许一定的误报即报告了碰撞但实际上没发生但绝不能漏报。AABB和Sweep and Prune是这个阶段的明星。精检测阶段对粗检测筛选出的潜在碰撞对进行精确的几何相交测试。这个阶段要求算法精确、稳定。对于简单几何体如球体、AABB、OBB我们有高效的专用算法对于复杂的凸体GJK和SAT就登场了。这种分层结构就像机场安检先看登机牌粗检测把明显不对的人排除再对需要进一步检查的旅客进行细致的行李扫描和人身检查精检测。如果对每个人都直接进行最精细的全身扫描机场早就瘫痪了。2.2 算法选型矩阵什么时候用什么在动手写代码之前先根据你的物体形状和性能需求参考下面的选型矩阵可以少走很多弯路。算法名称核心思想时间复杂度 (粗略)适用形状主要阶段优点缺点AABB轴对齐包围盒O(1) 每对检测任何形状的近似粗检测计算极快实现简单包围不紧密旋转后需更新精度低Sphere包围球O(1) 每对检测任何形状的近似粗检测计算最快旋转不变包围非常不紧密尤其对于长条形物体OBB有向包围盒O(1) 每对检测凸多面体、刚体粗检测/精检测比AABB更紧密精度更高计算比AABB复杂需要存储方向Sweep and Prune排序与扫描O(n log n) 全局配合AABB使用粗检测全局能高效处理大量静态/慢速物体对高速运动物体可能产生“隧道效应”SAT (2D)分离轴定理O(nm) 每对检测凸多边形(2D)精检测原理直观能得出穿透向量仅适用于2D凸多边形3D实现复杂GJK闵可夫斯基差与单纯形迭代收敛通常很快凸体(2D/3D)精检测统一框架处理任意凸体可计算最近距离算法理解难度高实现需注意数值稳定性实操心得在实际项目中我几乎从未见过只用一种算法的引擎。最常见的组合是对所有动态物体用AABB做粗检测对筛选后的物体对根据其形状类型如球vs球球vs盒盒vs盒凸体vs凸体分发到不同的精检测算法。对于复杂的凸体碰撞GJK是工业标准。3. 核心算法解析与C实现要点3.1 基础包围体AABB与SphereAABB轴对齐包围盒的实现核心是存储一个物体在世界坐标系下沿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 更紧密的包围OBBOBB有向包围盒可以随着物体旋转因此比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的最小值和最大值进行排序。插入将每个物体的aabb.min.x和aabb.max.x作为端点插入一个列表。排序对这个端点列表按X坐标进行排序可利用上一帧已基本有序的特性使用插入排序优化。扫描从头到尾扫描排序后的列表。维护一个“活动集合”。遇到一个min端点就将对应的物体加入活动集并与活动集中所有其他物体标记为潜在碰撞对。遇到一个max端点就将对应的物体从活动集中移除。结果扫描完成后就得到了所有在X轴上重叠的物体对。为了更精确通常还会用这些物体对的AABB在Y轴和Z轴上做快速验证。// 伪代码概念 struct Endpoint { int objId; float value; bool isMin; // true for min, false for max }; void sweepAndPrune(const std::vectorAABB aabbs, std::vectorstd::pairint, int potentialPairs) { std::vectorEndpoint 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_setint 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::vectorglm::vec2 polyA, const std::vectorglm::vec2 polyB) { // 测试多边形A的每条边作为轴 for (int i 0; i polyA.size(); i) { glm::vec2 edge polyA[(i1)%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算法深度解析GJKGilbert–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::vectorglm::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个点的单纯形点、线段、三角形、四面体。以下是其核心循环的简化描述初始化选择一个初始搜索方向d例如从B的中心指向A的中心。计算第一个支持点s support(M, d)并将其加入单纯形。迭代循环 a. 计算新的支持点p support(M, d)。 b. 如果p在方向d上的投影小于0即dot(p, d) 0说明原点在M之外物体分离。算法可以终止并利用当前信息计算最近距离需要EPA算法辅助。 c. 将p加入单纯形。 d. 判断原点是否在当前单纯形内部。如果是则物体相交算法结束。 e. 如果原点不在内部则更新单纯形剔除掉那些对寻找原点方向没有贡献的点保留一个更小的子单纯形例如从四面体退化为三角形。 f. 基于新的单纯形计算一个新的、指向原点的搜索方向d。 g. 返回步骤a继续迭代。终止条件通常设置一个最大迭代次数如20-30次或者当搜索方向d的长度接近于零时终止。核心难点与技巧GJK实现中最棘手的部分是更新单纯形和计算新的搜索方向。这需要处理单纯形是线段、三角形、四面体等不同情况并利用向量叉积和点积进行原点与单纯形各面的位置关系判断。网上有很多优秀的图示教程建议结合代码理解。**一个关键优化是使用“阻尼”或“容差”**来处理数值误差避免因浮点数精度问题导致算法在原点附近振荡或误判。4.3 从GJK到EPA获取碰撞信息GJK只能判断是否相交。如果相交我们还需要知道穿透深度和碰撞法线以便进行物理响应将物体推开。这就需要EPAExpanding Polytope Algorithm算法。EPA算法的思路很直观当GJK检测到相交时它已经给出了一个包含原点的单纯形一个多面体。EPA将这个单纯形扩展成一个更精细的、包裹原点的多面体即闵可夫斯基差集M在原点附近的边界。在这个多面体上找到离原点最近的那个面。这个面的法线方向就是碰撞法线原点到这个面的距离就是穿透深度。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::vectorglm::vec3 positions; std::vectorglm::quat rotations; std::vectorAABB 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::vectorPotentialPair 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::vectorPhysicsObject* m_objects; std::vectorContactManifold 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都会让你对这些算法的理解加深一分。网上有大量优秀的开源参考如Box2D2D、Bullet3D和Dyn4jJava 2D/3D阅读它们的源码是学习的捷径。记住在物理引擎的世界里纸上得来终觉浅绝知此事要躬行。