C++实现分离轴定理：2D凸多边形碰撞检测的核心原理与工程实践

1. 项目概述从“撞上”到“检测”游戏与仿真中的刚体物理基石在开发2D游戏、物理仿真或是任何涉及图形交互的应用时一个无法绕开的核心问题就是屏幕上这两个图形对象到底碰没碰到一起对于简单的矩形或圆形我们或许可以用边界框或距离公式快速判断。但当你需要处理任意形状的飞船、不规则的地形瓦片或是复杂的机械零件时问题就变得棘手了。这时分离轴定理Separating Axis Theorem, SAT便闪亮登场它被誉为2D凸多边形碰撞检测的“瑞士军刀”高效、精确且原理优雅。我最初接触SAT是在为一个2D平台游戏编写物理引擎时。面对各种多边形组成的角色和障碍物简单的AABB轴向包围盒碰撞已经不够用了角色在斜坡上会“卡住”复杂的形状穿透更是家常便饭。在尝试并对比了多种算法后SAT以其清晰的几何解释和稳定的性能成为了我的首选。它不依赖于特定的形状库只要你提供的是凸多边形的顶点列表它就能工作。无论是用C编写高性能游戏引擎还是在JavaScript中实现一个交互式演示其核心思想都是相通的。简单来说SAT的核心思想非常直观如果两个凸多边形没有发生碰撞那么至少存在一条直线分离轴能够将这两个多边形完全分隔在直线的两侧。反之如果找不到任何一条这样的分离轴那么这两个多边形必然相交。我们的任务就是去系统地检查所有可能的候选分离轴。对于凸多边形这些候选轴就是每个多边形的每条边的法线方向。这个项目就是要用C从零开始实现这一算法构建一个可靠、高效的2D碰撞检测工具函数。2. 核心原理拆解为什么是边的法线在深入代码之前我们必须吃透SAT背后的几何原理。为什么检查多边形的边就足够了为什么是边的法线而不是别的方向理解这个“为什么”是写出正确代码和后续调试的关键。想象一下两个凸多边形A和B。如果它们没有碰撞就像两个在桌子上互不接触的积木你总能找到一条缝隙插进一把刀片将两者分开。这把“刀片”的方向就是分离轴。现在考虑两个多边形所有可能的相对位置最有可能成为那把“刀片”的恰恰是它们彼此最接近的那些边。更严谨的数学原理是凸多边形可以看作是其所有边的半空间的交集。两个凸集的交集为空当且仅当存在一个超平面在2D中就是一条直线将它们分离。而支撑超平面的法线方向就来自于两个凸集各自某个面的法线。投影将高维问题降维SAT的精妙之处在于引入了“投影”。在一条轴一个方向向量上我们将一个多边形所有顶点投影到这条轴上得到一个线段区间。例如多边形在X轴上的投影就是其所有顶点X坐标的最小值到最大值。碰撞检测这个2D空间的问题被转化为了在一条条1D数轴上的区间重叠判断。如果在所有候选轴上两个多边形的投影区间都重叠那么它们在2D空间中就一定相交。只要存在一条轴其上的投影区间不重叠那么它们就一定分离。候选轴的选择对于两个凸多边形我们需要检查的候选轴集合是多边形A每条边的法线 多边形B每条边的法线。边的法线是一个垂直于该边的单位向量它指向多边形的“外侧”这依赖于顶点是顺时针还是逆时针存储需要统一。理论上两个多边形最多有(边数A 边数B)条候选轴需要检查。但在实际优化中因为一条边和它的法线是成对出现的我们通常直接使用边的方向向量旋转90度得到的向量作为轴无需单位化在计算投影时统一处理这可以节省一次开方运算。注意这里有一个非常重要的细节我们使用的是“边的法线”而不是“顶点连线”的方向。很多初学者会误以为需要检查所有顶点到顶点的连线这是不必要的也是SAT效率高的原因之一。对于凸多边形检查所有边的法线足矣。3. 数据结构设计与数学工具准备在动手实现碰撞检测函数前我们需要搭建好基础设施。清晰的数据结构和基础的数学工具函数能让核心逻辑变得干净利落。3.1 定义核心数据结构我们首先定义二维向量Vec2这是所有2D几何运算的基石。// Vec2.hpp #ifndef VEC2_HPP #define VEC2_HPP #include cmath struct Vec2 { float x, y; Vec2() : x(0.0f), y(0.0f) {} Vec2(float x_, float y_) : x(x_), y(y_) {} // 向量加法、减法、数乘等基本运算 Vec2 operator(const Vec2 other) const { return Vec2(x other.x, y other.y); } Vec2 operator-(const Vec2 other) const { return Vec2(x - other.x, y - other.y); } Vec2 operator*(float scalar) const { return Vec2(x * scalar, y * scalar); } // 点积内积用于投影计算 float dot(const Vec2 other) const { return x * other.x y * other.y; } // 获取向量的垂直向量法线默认返回逆时针旋转90度的向量 Vec2 perpendicular() const { return Vec2(-y, x); } // 计算向量长度平方避免开方用于比较 float lengthSquared() const { return x*x y*y; } // 单位化向量 void normalize() { float len std::sqrt(lengthSquared()); if (len 1e-7) { // 避免除零 x / len; y / len; } } }; #endif // VEC2_HPP接下来定义多边形Polygon。我们假设多边形是凸的顶点按顺序存储顺时针或逆时针但必须统一。// Polygon.hpp #ifndef POLYGON_HPP #define POLYGON_HPP #include vector #include Vec2.hpp class Polygon { public: std::vectorVec2 vertices; // 顶点列表按顺序存储 Polygon() default; Polygon(const std::vectorVec2 verts) : vertices(verts) {} // 获取第i条边从顶点i指向顶点i1 Vec2 getEdge(size_t i) const { size_t next (i 1) % vertices.size(); // 循环到第一个顶点 return vertices[next] - vertices[i]; } // 获取第i条边的法线未单位化即垂直向量 Vec2 getEdgeNormal(size_t i) const { return getEdge(i).perpendicular(); // 使用我们定义的perpendicular方法 } // 计算多边形在给定轴上的投影区间 [min, max] void projectOntoAxis(const Vec2 axis, float minProj, float maxProj) const { if (vertices.empty()) { minProj maxProj 0.0f; return; } // 初始化将第一个顶点的投影作为初始值 minProj maxProj axis.dot(vertices[0]); // 遍历所有顶点找到投影的最小值和最大值 for (size_t i 1; i vertices.size(); i) { float proj axis.dot(vertices[i]); if (proj minProj) minProj proj; if (proj maxProj) maxProj proj; } } }; #endif // POLYGON_HPP3.2 投影与区间重叠判断这是SAT算法的核心辅助函数。给定两个区间[minA, maxA]和[minB, maxB]判断它们是否重叠并计算重叠深度用于后续可能的碰撞响应。// SATUtils.hpp #ifndef SATUTILS_HPP #define SATUTILS_HPP #include algorithm // for std::max, std::min namespace SAT { /** * 判断两个1D投影区间是否重叠并计算重叠深度。 * param minA 多边形A投影最小值 * param maxA 多边形A投影最大值 * param minB 多边形B投影最小值 * param maxB 多边形B投影最大值 * param overlap 输出参数存储计算出的重叠深度如果重叠 * return true 如果区间重叠否则 false */ bool intervalsOverlap(float minA, float maxA, float minB, float maxB, float overlap) { // 检查分离情况A整体在B左边或A整体在B右边 if (maxA minB || maxB minA) { return false; // 不重叠存在分离轴 } // 计算重叠的两种情形取最小的重叠量作为“穿透深度” // 情形1: A部分在B左边重叠部分为 maxA - minB // 情形2: A部分在B右边重叠部分为 maxB - minA overlap std::min(maxA, maxB) - std::max(minA, minB); // 这里可以处理“刚好接触”的情况。通常如果overlap 0我们可以认为没有碰撞分离。 // 但在某些物理引擎中刚好接触也需要响应。这里我们定义 overlap 0 为不重叠。 // 为了数值稳定性我们使用一个很小的容差。 const float epsilon 1e-5f; if (overlap epsilon) { return false; } return true; } } #endif // SATUTILS_HPP实操心得容差Epsilon的重要性在浮点数计算中由于精度问题两个理论上刚好接触的多边形其投影区间的maxA和minB可能并不完全相等而是有极其微小的差异如1e-7。如果不设置容差算法可能会错误地报告碰撞或非碰撞导致物体“抖动”或“粘滞”。这个epsilon的值需要根据你的世界坐标尺度来调整。如果你的游戏单位是米1e-5通常足够如果单位是像素可能需要0.1或0.5。这是一个需要根据实际情况微调的参数。4. SAT碰撞检测算法完整实现有了上面的准备我们现在可以实现核心的checkSATCollision函数。这个函数不仅返回是否碰撞还可以返回碰撞法线和穿透深度这些信息对于后续的碰撞响应如将物体推开至关重要。// SATCollision.hpp #ifndef SATCOLLISION_HPP #define SATCOLLISION_HPP #include Polygon.hpp #include SATUtils.hpp #include limits // for std::numeric_limits namespace SAT { struct CollisionResult { bool isColliding false; Vec2 normal; // 碰撞法线单位向量指向从A到B的分离方向或最小穿透方向 float depth 0.0f; // 穿透深度 }; /** * 使用分离轴定理检测两个凸多边形是否碰撞。 * param polyA 多边形A * param polyB 多边形B * return CollisionResult 包含碰撞状态、法线和深度 */ CollisionResult checkSATCollision(const Polygon polyA, const Polygon polyB) { CollisionResult result; result.depth std::numeric_limitsfloat::max(); // 初始化为最大值 Vec2 smallestAxis; // 记录最小穿透深度的轴 // 用于临时存储投影区间 float minA, maxA, minB, maxB; // 1. 检查多边形A的所有边法线 for (size_t i 0; i polyA.vertices.size(); i) { // 获取当前边的法线候选轴 // 注意这里我们使用边的垂直向量它不一定单位化。 Vec2 axis polyA.getEdgeNormal(i); // 将两个多边形投影到该轴上 polyA.projectOntoAxis(axis, minA, maxA); polyB.projectOntoAxis(axis, minB, maxB); float overlap; if (!intervalsOverlap(minA, maxA, minB, maxB, overlap)) { // 发现分离轴绝对没有碰撞 result.isColliding false; return result; } // 如果重叠记录最小的重叠深度及对应的轴 // 穿透深度是投影重叠的长度但我们需要考虑轴的“长度”对投影值的影响。 // 因为 axis 可能不是单位向量直接计算的 overlap 是投影标量差不是空间距离。 // 我们需要将 overlap 除以轴的长度得到真实的空间穿透距离。 // 更高效的做法在投影前将轴单位化或者在此处进行校正。 // 我们选择在投影函数内部不单位化轴以节省计算在此处校正。 float axisLength std::sqrt(axis.dot(axis)); // 计算轴的长度 if (axisLength 1e-7) { overlap / axisLength; // 得到真实的空间穿透深度 } if (overlap result.depth) { result.depth overlap; smallestAxis axis; // 暂时存储当前轴方向可能还需要调整 } } // 2. 检查多边形B的所有边法线 for (size_t i 0; i polyB.vertices.size(); i) { Vec2 axis polyB.getEdgeNormal(i); polyA.projectOntoAxis(axis, minA, maxA); polyB.projectOntoAxis(axis, minB, maxB); float overlap; if (!intervalsOverlap(minA, maxA, minB, maxB, overlap)) { result.isColliding false; return result; } float axisLength std::sqrt(axis.dot(axis)); if (axisLength 1e-7) { overlap / axisLength; } if (overlap result.depth) { result.depth overlap; smallestAxis axis; } } // 3. 如果所有轴都重叠则发生碰撞 result.isColliding true; // 4. 确定碰撞法线的方向。 // smallestAxis 目前只是最小分离轴的方向向量未单位化。 // 我们需要确保法线指向从A到B的分离方向即将A沿此方向平移可以最快地分离。 // 一个常用的方法是计算从A中心到B中心的向量然后检查其与法线的点积。 // 如果点积为正说明中心向量与法线方向大致相同法线方向正确从A指向B。 // 如果点积为负则需要反转法线方向。 Vec2 centerA(0,0), centerB(0,0); // 简单计算多边形的中心质心对于凸多边形可以用顶点平均值近似 for (const auto v : polyA.vertices) centerA centerA v; for (const auto v : polyB.vertices) centerB centerB v; centerA centerA * (1.0f / polyA.vertices.size()); centerB centerB * (1.0f / polyB.vertices.size()); Vec2 centerToCenter centerB - centerA; // 从A中心指向B中心的向量 // 单位化 smallestAxis 作为最终的法线 smallestAxis.normalize(); // 如果中心向量与法线方向相反则反转法线 if (centerToCenter.dot(smallestAxis) 0) { smallestAxis smallestAxis * (-1.0f); } result.normal smallestAxis; // 注意此时的 depth 已经是沿法线方向的最小穿透距离。 return result; } } #endif // SATCOLLISION_HPP5. 算法优化与边界情况处理基础的SAT实现已经完成但在实际应用中我们还需要考虑性能优化和处理一些棘手的边界情况。5.1 性能优化技巧提前剔除Broad PhaseSAT是一种“精细检测”Narrow Phase。在场景中有成百上千个物体时对每对物体都进行SAT检测是不可接受的。必须先使用空间划分如四叉树、网格或粗略包围体如AABB、包围圆进行快速筛选只对可能碰撞的物体对进行SAT检测。缓存法线如果一个多边形的形状不变比如静态地形可以预先计算并存储其所有边的单位法线避免在每次检测时重复计算perpendicular()和normalize()。投影计算优化projectOntoAxis函数中的点积循环是热点。确保编译器能进行向量化优化。对于顶点数固定的简单形状如矩形、三角形可以手动展开循环。使用平方长度进行比较在寻找最小穿透深度时我们比较的是overlap已经是距离。但有时在早期分离判断中我们可以先比较未除以轴长度的overlap平方因为开方运算较慢。不过在现代CPU上一次检测中的几次开方开销通常可以接受代码清晰更重要。尽早跳出一旦发现任何一条分离轴函数立即返回false。这是SAT算法高效的关键之一。5.2 处理特殊与边界情况退化多边形确保多边形至少有三个顶点且顶点不共线。在构造函数或顶点设置函数中可以添加验证。顶点顺序算法假设顶点是连续且按顺序顺时针或逆时针排列的。如果顶点顺序是乱的getEdgeNormal计算的法线方向将不一致导致检测失败。可以在Polygon类中添加一个ensureWindingOrder方法来纠正顶点顺序。“刚好接触”的处理如前所述使用epsilon容差。对于某些游戏逻辑如平台边缘判定你可能希望overlap 0时返回“碰撞”以便触发事件。这时可以调整intervalsOverlap函数的逻辑将overlap epsilon改为overlap -epsilon才判定为分离。含旋转和多边形的检测我们的Polygon类存储的是局部坐标或世界坐标。如果物体有旋转、缩放和平移你需要在检测前将物体的模型变换旋转、缩放应用到顶点上生成一个世界空间的多边形副本或者更高效地在投影时结合变换矩阵进行计算。通常的做法是维护一个物体的变换矩阵在检测时动态计算其世界空间顶点。// 示例在物体类中获取世界空间多边形 class GameObject { Polygon localPolygon; // 局部坐标下的形状 Vec2 position; float rotation; // 弧度 float scale; public: Polygon getWorldPolygon() const { std::vectorVec2 worldVerts; worldVerts.reserve(localPolygon.vertices.size()); float cosR std::cos(rotation); float sinR std::sin(rotation); for (const auto v : localPolygon.vertices) { // 应用缩放、旋转、平移 Vec2 transformed; transformed.x (v.x * cosR - v.y * sinR) * scale position.x; transformed.y (v.x * sinR v.y * cosR) * scale position.y; worldVerts.push_back(transformed); } return Polygon(worldVerts); } };6. 完整测试用例与调试可视化理论再完美也需要实践检验。编写全面的测试用例和简单的可视化调试工具是确保算法正确性的不二法门。6.1 编写单元测试使用简单的测试框架如Catch2或直接写main函数测试。// test_sat.cpp #include iostream #include SATCollision.hpp void testBasicCollision() { // 测试1两个分离的三角形 Polygon triA({Vec2(0,0), Vec2(2,0), Vec2(1,2)}); Polygon triB({Vec2(5,0), Vec2(7,0), Vec2(6,2)}); auto result SAT::checkSATCollision(triA, triB); std::cout Test 1 - Separated triangles: (result.isColliding ? FAIL : PASS) std::endl; // 测试2相交的矩形和三角形 Polygon rect({Vec2(0,0), Vec2(3,0), Vec2(3,2), Vec2(0,2)}); Polygon triC({Vec2(2,1), Vec2(4,1), Vec2(3,3)}); result SAT::checkSATCollision(rect, triC); std::cout Test 2 - Intersecting rect and tri: (result.isColliding ? PASS : FAIL) std::endl; if (result.isColliding) { std::cout Collision Normal: ( result.normal.x , result.normal.y ) std::endl; std::cout Penetration Depth: result.depth std::endl; } // 测试3刚好接触在容差内 Polygon rectA({Vec2(0,0), Vec2(2,0), Vec2(2,2), Vec2(0,2)}); Polygon rectB({Vec2(2,0), Vec2(4,0), Vec2(4,2), Vec2(2,2)}); // 右边刚好接触 result SAT::checkSATCollision(rectA, rectB); // 根据我们的epsilon设置应该判定为不碰撞 std::cout Test 3 - Touching rectangles: (!result.isColliding ? PASS : FAIL) std::endl; } int main() { testBasicCollision(); return 0; }6.2 简单可视化调试基于控制台或简单图形库对于复杂的碰撞情况肉眼难以判断。可以借助简单的图形库如SFML、SDL2甚至OpenCV将多边形和分离轴画出来。调试绘制思路绘制两个多边形。在检测过程中将每条候选轴也绘制出来从某个中心点延伸。用不同颜色标记投影区间是否重叠。最终用醒目的颜色标出“最小穿透深度轴”即碰撞法线。这个过程能极大地帮助你理解算法每一步在做什么以及为什么某些情况下会判断错误。例如你可能会发现因为顶点顺序错误导致所有法线都指向多边形内部从而永远检测不到分离轴。7. 常见问题排查与性能调优实录在实际项目中集成SAT时你几乎一定会遇到下面这些问题。这里记录了我的排查日记和解决方案。问题1物体高速移动时发生“隧道效应”Tunneling现象一个快速移动的子弹从两个障碍物的缝隙中穿过没有触发碰撞。原因离散的帧检测。在上一帧子弹在障碍物前下一帧子弹已经穿到了障碍物后。两帧之间的位置都没有发生碰撞。解决方案连续碰撞检测CCD不是检测两个静态形状而是检测从上一帧到当前帧的“运动扫掠体”Swept Volume是否与目标相交。实现更复杂。增加检测频率提高物理更新的帧率如从60Hz到240Hz。使用更宽的“厚”形状对于高速物体使用比其视觉模型稍大的碰撞体进行检测。子步采样Sub-stepping在渲染帧内进行多次物理检测。例如物体从A移动到B在中间插入多个检测点。问题2碰撞法线方向不稳定导致物体响应时抖动现象两个盒子堆叠时上面的盒子会轻微地左右抖动。原因当两个多边形的多条边几乎平行时计算出的几条分离轴投影重叠深度可能非常接近。由于浮点数精度误差最小深度的轴可能在两帧之间来回切换导致法线方向突变。解决方案法线平滑不要直接使用当前帧的法线而是与上一帧的法线进行加权平均如normal 0.7 * oldNormal 0.3 * newNormal然后单位化。增加容差在比较重叠深度时增加一个小的容差范围。如果两条轴的重叠深度差小于容差则优先选择与上一帧法线更接近的那条轴。使用“最稳定”的轴有时选择与两物体中心连线方向最接近的法线作为碰撞法线反而更稳定。问题3对于非常细长的多边形检测结果不可靠现象一个很细的针状多边形与另一个多边形相交但SAT可能检测不到。原因细长多边形在垂直于其长边的方向上投影区间非常短。如果穿透主要发生在长边方向而算法检查的是边的法线即短边方向微小的浮点误差可能导致投影区间被误判为分离。解决方案增加顶点在长边上中间插入更多顶点但这会增加计算量。使用GJK算法对于极端形状Gilbert–Johnson–Keerthi (GJK) 算法可能更健壮它不依赖于投影所有边而是通过迭代寻找单纯形。结合AABB快速剔除先用AABB快速判断如果AABB不相交则直接返回不碰撞。这可以避免大部分无意义的SAT检测。问题4性能瓶颈分析当游戏实体数量n很大时即使有粗略阶段精细检测的对数m也可能很大。使用性能分析工具如Visual Studio Profiler、Very Sleepy定位热点。发现projectOntoAxis中的点积循环和sqrt开方运算是主要开销。优化SIMD指令集使用SSE或AVX指令集并行计算多个顶点的点积。这对于顶点数固定的形状如使用8个顶点的八边形效果显著。近似计算在寻找最小穿透深度时可以不进行开方而是比较overlapSquared / axisLengthSquared。因为除法和开方开销大但比较本身不需要精确值只需要找出最小值对应的轴。找到轴后再计算一次精确的深度和单位法线。减少候选轴对于某些特定形状对如矩形对矩形只有4条独立的轴需要检查两个矩形的各两条主轴而不是8条。可以写特化的检测函数。下表总结了常见问题与解决思路问题现象可能原因排查方向与解决方案该碰撞没报顶点顺序错误检查多边形顶点是否为顺时针/逆时针连续排列可视化法线方向。不该碰撞报了容差设置不当调整epsilon值检查投影计算中是否有浮点溢出。高速物体穿透离散检测局限性引入连续检测、增加检测频率或使用扫掠体。碰撞响应抖动法线方向不稳定对碰撞法线进行帧间平滑处理或增加深度比较容差。性能随物体数增长慢算法复杂度高确保使用了空间划分四叉树/网格进行粗略剔除。性能热点在SAT内部投影计算频繁缓存静态形状的法线对动态形状使用SIMD优化点积计算。实现一个健壮的SAT碰撞检测器就像打磨一把好刀。核心算法checkSATCollision是刀身必须坚固锋利。而数据结构、数学工具、测试用例和这些优化技巧则是刀柄、刀鞘和磨刀石它们共同决定了这把刀在实际战斗中的可靠性与手感。从理解原理到写出代码再到处理各种边界情况和性能优化每一步都需要耐心和实践。当你看到自己编写的物理引擎里各种形状的物体流畅、稳定地碰撞和反弹时那种成就感是对所有调试时间最好的回报。