1. 项目概述从“能用”到“可靠”的鸿沟“多边形碰撞检测”这七个字对于任何一个涉足游戏开发、物理仿真或者图形学领域的C开发者来说都绝不陌生。随便搜一下网上能找到成百上千篇教程从基础的分离轴定理SAT讲起附带几段代码示例似乎半小时就能搞定。然而当你真正把那段“教科书式”的代码塞进自己的项目处理起千奇百怪的多边形——可能是从建模软件导出的复杂网格可能是玩家实时编辑的地形甚至可能是物理破碎后产生的碎片——你会发现程序开始出现各种灵异现象物体明明没碰上却报告碰撞了明明嵌在一起了却检测为分离在某些刁钻的角度下性能骤降更别提那些因为浮点数精度问题导致的、时有时无的诡异抖动。这就是理论与实战的差距。标题里提到的“99%新手忽略的关键细节”指的不是算法原理本身而是将原理转化为健壮、高效、稳定的工业级代码过程中那些教科书不会写、博客很少提但却足以让你调试到崩溃的“魔鬼细节”。这些细节处理不好你的碰撞检测就永远停留在“玩具”阶段无法承受真实项目的考验。今天我们就来彻底拆解这些难点我会结合自己趟过的坑把那些关键的实现细节、优化策略和调试心得掰开揉碎了讲清楚。无论你是正在实现自己的第一个物理引擎还是试图优化项目中现有的碰撞系统这篇文章都能给你提供直达问题核心的实用指南。2. 核心思路与算法选型为什么是SAT多边形碰撞检测算法众多如分离轴定理SAT、吉尔伯特-约翰逊-凯尔蒂距离算法GJK、Minkowski差等。对于凸多边形SAT因其概念直观、实现相对简单且能提供碰撞深度和方向等额外信息成为最广泛采用的方法。它的核心思想非常优雅如果两个凸多边形没有发生碰撞那么必然存在一条直线分离轴能够将两者完全分隔开并且两个多边形在该直线上的投影区间不会重叠。2.1 SAT算法基础复盘与“想当然”的陷阱几乎所有教程都会告诉你SAT的步骤获取两个多边形所有边的法向量作为潜在的分离轴。将两个多边形分别投影到每一条轴上。检查投影区间是否重叠。如果所有轴上的投影都重叠则碰撞发生只要找到一条轴投影不重叠则分离。新手按照这个描述很快就能写出第一版代码。但这里第一个“想当然”的陷阱就出现了边的法向量怎么算很多人的第一反应是对于一条从点A(x1, y1)到点B(x2, y2)的边其方向向量是(B-A)那么法向量不就是(-dy, dx)或(dy, -dx)吗这没错但紧接着的问题是你需要的是单位法向量吗投影计算时使用边向量直接做法线和使用归一化后的单位法向量在判断区间重叠的“深度”时会有差异。SAT不仅可以判断是否碰撞还能求出最小穿透向量MTV用于在物理响应中将物体推开。而计算MTV需要的是在分离轴上的穿透深度这个深度值与轴的模长有关。因此一个常见的优化是在寻找分离轴时我们只关心“是否存在”可以使用未归一化的边向量作为轴但当检测到碰撞并需要计算MTV时则必须使用该轴的单位向量来计算精确的穿透深度。很多初版实现混淆了这两个阶段导致算出的推开方向不正确或力度有误。// 一个常见的、需要小心的法向量计算片段 struct Vec2 { float x, y; }; Vec2 GetEdgeNormal(const Vec2 a, const Vec2 b) { Vec2 edge {b.x - a.x, b.y - a.y}; // 法向量垂直于edge。选择(-edge.y, edge.x)还是(edge.y, -edge.x) // 这决定了法向量的“朝向”。为了保证法向量指向多边形的“外侧” // 需要与多边形顶点的缠绕顺序顺时针CW或逆时针CCW一致。 Vec2 normal {-edge.y, edge.x}; // 假设顶点是逆时针顺序这就是外法线 // 重要此时normal可能不是单位向量 return normal; }2.2 缠绕顺序与法线朝向一切的基础上段代码注释里提到了“缠绕顺序”。这是第二个关键细节也是后续很多问题的根源。多边形的顶点存储顺序顺时针或逆时针决定了其“正面”和“背面”。SAT算法要求我们使用外法线即指向多边形外部的法向量作为分离轴。如果法线方向算反了成了内法线投影区间会错乱导致碰撞检测完全失效。如何保证得到外法线这依赖于一个约定你的所有凸多边形顶点必须采用统一的缠绕顺序通常约定为逆时针CCW。这样对于每条边(v[i], v[i1])通过计算(v[i1] - v[i])并旋转90度(-dy, dx)得到的向量就是大致向外的法线。为了精确可以在初始化多边形时先检测其顶点顺序如果不是约定顺序则进行反转。这是一个预处理步骤但至关重要。// 检测并确保多边形顶点为逆时针顺序 void EnsureCCW(std::vectorVec2 vertices) { float area 0.0f; for (size_t i 0; i vertices.size(); i) { const Vec2 v1 vertices[i]; const Vec2 v2 vertices[(i 1) % vertices.size()]; area (v2.x - v1.x) * (v2.y v1.y); // 鞋带公式的一部分 } if (area 0.0f) { // 面积为正表示顺时针取决于坐标系Y轴向上时 std::reverse(vertices.begin(), vertices.end()); } }注意这里“面积”正负与坐标系Y轴向上还是向下有关。上面的代码假设Y轴向上屏幕坐标系常见。在OpenGL等Y轴向下的坐标系中判断条件可能相反。务必与你使用的坐标系匹配。3. 核心难点拆解与实战实现理解了基础我们进入深水区。下面这些难点才是区分“Demo代码”和“生产代码”的关键。3.1 浮点数精度幽灵碰撞与抖动之源浮点数计算是碰撞检测中最大的“玄学”问题。两个理论上应该刚好接触的多边形因为浮点误差其投影区间可能计算出一个极小的重叠如1e-7或极小的间隙如-1e-7。这会导致幽灵碰撞肉眼看着没碰上却检测为碰撞。抖动两个静止堆叠的物体在碰撞/分离状态间高频振荡。解决方案不是追求“零误差”而是引入一个容差Tolerance。核心思想是当两个投影区间的间隙小于某个极小正值时我们认为它们“已经接触”当重叠深度小于某个极小正值时我们认为它们“刚刚接触”可以忽略或做特殊处理。const float EPSILON 1e-6f; // 根据项目尺度调整1e-6对于米制单位是个不错的起点 bool CheckOverlapOnAxis(const Vec2 axis, const Polygon polyA, const Polygon polyB, float overlapDepth) { Projection projA ProjectPolygonOnAxis(axis, polyA); Projection projB ProjectPolygonOnAxis(axis, polyB); // 检查是否分离加入容差 if (projA.max projB.min - EPSILON || projB.max projA.min - EPSILON) { return false; // 找到分离轴 } // 计算重叠深度 overlapDepth std::min(projA.max, projB.max) - std::max(projA.min, projB.min); // 如果重叠深度极小可以视为“刚好接触”MTV可能不稳定可特殊处理 return true; }在计算最小穿透向量MTV时也应对穿透深度进行“净化”如果深度绝对值小于EPSILON可以将其置为0或者直接忽略这条轴作为MTV候选因为数值不稳定。3.2 最小穿透向量计算不只是深度SAT的优势在于能给出MTV即推开物体所需的最小向量。但计算MTV有几个坑轴的方向性分离轴法向量有正反两个方向。投影区间[min, max]的重叠深度是一个标量但我们需要一个向量。这个向量的方向应该是从A指向B还是反过来这取决于你如何定义“推开”。通常我们计算的是将A从B身上推开的最小向量。这意味着当计算重叠深度时我们需要知道是A的max超过了B的min还是B的max超过了A的min以此决定MTV的方向是沿着轴的方向还是反方向。多轴比较我们会在多条轴上得到重叠。MTV是其中重叠深度最小的那条轴所对应的向量深度 * 单位法向量。这里“最小”指的是绝对值最小。必须遍历所有轴找到这个最小值。零重叠或负深度由于容差的存在可能计算出极小的正深度、零深度或负深度视为分离。在比较和选择MTV时必须正确处理这些边界情况。bool SATCollision(const Polygon polyA, const Polygon polyB, Vec2 mtv) { float minOverlap std::numeric_limitsfloat::max(); Vec2 smallestAxis; // 检查A的边 for (size_t i 0; i polyA.vertices.size(); i) { Vec2 edge polyA.vertices[(i1)%polyA.vertices.size()] - polyA.vertices[i]; Vec2 axis {-edge.y, edge.x}; // 外法线 // 为了MTV计算这里最好归一化使穿透深度物理意义明确 axis Normalize(axis); float overlap; if (!CheckOverlapOnAxis(axis, polyA, polyB, overlap)) { return false; // 分离 } if (overlap minOverlap) { minOverlap overlap; smallestAxis axis; // 需要判断方向确保mtv的方向是将A从B身上推开 // 可以通过比较两个投影的中心点来确定 float centerA (ProjectionA.min ProjectionA.max) * 0.5f; float centerB (ProjectionB.min ProjectionB.max) * 0.5f; if (centerA centerB) { smallestAxis axis; // 方向从A指向B } else { smallestAxis -axis; // 方向从B指向A即A需要被推向-axis方向 } } } // 检查B的边类似代码略 // ... if (minOverlap ! std::numeric_limitsfloat::max()) { mtv smallestAxis * minOverlap; return true; } return false; // 理论上不会走到这里 }3.3 顶点投影与区间计算效率与精度平衡投影计算ProjectPolygonOnAxis是SAT中最耗时的部分因为需要对每个顶点进行点积运算。对于一个有n个顶点的多边形每次投影是O(n)操作。两个多边形检查m条边m nA nB总复杂度是O(nA * nB)。对于复杂多边形这是性能瓶颈。优化点1预先计算并缓存法向量。多边形的边法向量在物体旋转时才改变。如果物体是刚体且旋转不频繁可以缓存这些法向量避免每帧重复计算。优化点2使用SoA数组结构或SIMD指令。将顶点的x和y坐标分别存储在连续数组中可以利用SIMD指令同时计算多个顶点的点积大幅提升投影计算速度。这是工业级物理引擎的常见优化。优化点3及早退出Early Out。在遍历所有轴之前如果发现某条轴上的投影间隙大于某个值可以立即返回“分离”无需检查剩余轴。但注意计算MTV时需要遍历所有轴找到最小重叠所以“检测是否碰撞”和“计算MTV”可以是两个不同优化路径的函数。精度方面点积运算本身是浮点密集操作。确保你的顶点坐标尺度合理避免过大或过小的数值并考虑使用双精度浮点数double进行关键的投影和重叠计算尽管这会牺牲一些性能但能显著提升稳定性尤其是在大型世界坐标中。3.4 复杂多边形与凹多边形处理SAT只适用于凸多边形。如果你的模型是凹多边形直接应用SAT会得到错误结果。处理凹多边形有两种主流方法分解将凹多边形分解为多个凸多边形的集合凸分解。然后对这些凸部分分别进行SAT检测。这是最通用的方法但分解算法本身如耳切法比较复杂且分解结果会影响性能。GJK算法吉尔伯特-约翰逊-凯尔蒂算法是另一种检测凸形状碰撞的方法它通过迭代计算Minkowski差来工作天生支持凸形状并且可以通过EPA算法得到穿透深度。对于凹多边形仍然需要先进行凸分解但GJK在处理某些类型的凸形状时可能比SAT更高效。在项目中一个务实的选择是规定所有碰撞体必须是凸的。在美术资源和关卡设计阶段就做好约束。如果必须使用凹形状则在导入时或运行时预先进行凸分解并将分解后的凸部分作为一组碰撞体来处理。4. 性能优化与工程化实践当你的基础碰撞检测工作后下一步就是让它能在游戏里跑得快、跑得稳。4.1 空间划分与粗检测逐对检测所有多边形是O(N²)的不可行。必须引入空间划分结构进行粗检测Broad Phase快速筛选出可能发生碰撞的对象对再交给SAT进行精检测Narrow Phase。网格划分将世界划分为均匀网格每个物体根据其AABB轴对齐包围盒注册到覆盖的网格中。只检测同一网格或相邻网格内的物体对。实现简单适合物体分布均匀的场景。四叉树/八叉树递归地将空间划分为四个/八个子区域动态地将物体放入相应节点。适合物体分布不均匀的场景查询效率高。BVH层次包围盒树为每个物体构建一个层次结构的包围盒如AABB树。从根节点开始如果两个包围盒不相交则其下的所有子物体都不需要检测。特别适合检测单个复杂物体如由许多三角形组成的网格的自碰撞或与环境的大量检测。粗检测阶段通常使用AABB轴对齐包围盒因为AABB的重叠检测极其快速只需比较最大最小值。你需要为每个动态物体每帧更新其AABB这通常比直接更新多边形顶点要廉价。4.2 缓存与增量计算对于移动或旋转的物体其世界空间下的顶点和法向量每帧都需要更新。完全重新计算是昂贵的。缓存变换后的顶点在物体变换位置、旋转、缩放更新后计算一次世界坐标下的顶点并缓存直到下次变换发生。SAT检测都使用缓存后的顶点。增量更新法向量如果只有平移法向量不变。如果发生旋转可以对本地空间的法向量应用同样的旋转矩阵而不是重新从边计算。缩放如果是均匀的不影响法线方向但可能需要重新归一化非均匀缩放会改变形状需要谨慎处理可能需重新计算。4.3 模块化与接口设计一个好的碰撞检测模块应该职责清晰、接口简洁。形状基类定义Shape基类提供虚函数如GetType(),GetAABB(),Support()用于GJK等。凸多边形类继承自Shape内部存储本地顶点、世界缓存顶点、法向量缓存等。提供UpdateTransform()和CheckCollision()方法。碰撞检测管理器管理所有碰撞体执行粗检测和精检测调度。提供注册/注销接口以及查询碰撞结果的接口。碰撞结果结构体不仅返回是否碰撞还应包含MTV、碰撞点或近似碰撞点、碰撞法线、以及涉及的两个物体引用等信息供物理响应模块使用。struct CollisionResult { bool isColliding; Vec2 mtv; // 最小穿透向量 Vec2 normal; // 碰撞法线单位向量通常指向物体A外部 float depth; // 穿透深度 Vec2 contactPoint; // 近似接触点计算这个点本身又是一个话题 Collider* colliderA; Collider* colliderB; };5. 调试与可视化让碰撞“看得见”碰撞检测的Bug往往难以捉摸因为没有视觉反馈。实现调试可视化是必不可少的开发环节。绘制多边形轮廓在调试模式下用线条绘制出每个碰撞体的精确形状世界坐标下的顶点连线。绘制AABB用不同颜色的线框绘制每个物体的AABB用于验证粗检测。高亮碰撞对当检测到碰撞时用醒目的颜色如红色填充或勾勒发生碰撞的两个多边形。绘制分离轴/MTV在发生碰撞的位置绘制出计算得到的MTV向量一条从碰撞点出发的箭头这能直观地检查MTV方向是否正确。绘制投影区间在选定的分离轴上绘制出两个多边形在该轴上的投影区间可以画成两条平行的线段用不同颜色表示两个物体直观展示重叠或分离的状态。这些可视化工具能帮你快速定位是算法逻辑错误、数据问题顶点顺序、变换错误还是精度问题。6. 常见问题与排查清单即使按照指南实现你仍可能遇到奇怪的问题。下面是一个快速排查清单问题现象可能原因排查步骤物体明显分离却报告碰撞1. 顶点缠绕顺序不一致导致法线方向错误。2. 浮点容差EPSILON设置过大。3. AABB粗检测失效导致不该检测的对进入了精检测。1. 可视化多边形和法线检查法线是否指向外侧。2. 减小EPSILON或使用双精度计算关键比较。3. 检查AABB更新逻辑确保其紧密包围多边形。物体明显碰撞却未检测到1. 分离轴漏算例如只算了一个多边形的边。2. 顶点坐标或变换矩阵有误世界坐标错误。3. 投影区间计算错误min/max搞反。1. 确认检查了两个多边形所有边的法向量。2. 可视化世界坐标下的多边形顶点确认其位置正确。3. 单步调试打印一条已知碰撞轴上的投影区间值。MTV方向错误物体被“吸进去”1. MTV方向判断逻辑错误中心点比较有误。2. 法向量未归一化导致深度计算和方向结合后出错。1. 可视化MTV箭头观察其方向。检查计算MTV方向时的符号逻辑。2. 确保用于计算MTV深度的轴是单位向量。性能随物体增多急剧下降1. 未使用空间划分Broad Phase是O(N²)检测。2. 每帧都在重新计算顶点和法向量未缓存。3. 投影计算未做任何优化如SIMD。1. 实现网格或四叉树进行粗检测。2. 仅在变换改变时更新缓存。3. 对热点函数投影计算进行性能分析。物体堆叠时剧烈抖动1. 浮点精度问题导致碰撞状态在帧间频繁切换。2. 物理响应处理不当与碰撞检测形成正反馈。3. MTV深度过小数值不稳定。1. 增加合理的碰撞容差并引入“睡眠”机制对低速/静止物体停止检测。2. 在物理积分中引入位置纠正但避免过度纠正。3. 对小于阈值的穿透深度忽略或施加一个很小的固定纠正力。旋转后碰撞形状不对1. 顶点变换矩阵应用错误顺序、左乘右乘。2. 法向量更新未考虑旋转直接用了本地法线。3. 缩放为非均匀导致形状不再是凸的或法线错误。1. 确认变换矩阵通常为 Scale * Rotation * Translation。2. 对法向量应用旋转矩阵如果是单位向量只需3x3旋转部分。3. 考虑禁止非均匀缩放或在碰撞检测中使用未缩放的形状。最后分享一个我个人的深刻体会不要试图在碰撞检测中追求数学上的完美。物理引擎的本质是“看起来正确”的近似模拟。花费大量精力去处理那些极端刁钻的、几乎不会在正常游戏中出现的碰撞情况比如两个高速旋转的细长多边形以极小的角度相切其性价比往往很低。你的目标是建立一个在99.9%的游戏场景下稳定、高效、可预测的系统。对于剩下的0.1%有时一个巧妙的约束、一个特殊 case 的处理甚至是一个合理的“作弊”比如在特定条件下强制认为不碰撞比一个理论上完美但复杂脆弱的通用方案要可靠得多。理解原理然后为了性能和鲁棒性做出务实的妥协和优化这才是工程实践的真谛。 多边形碰撞检测实战：从SAT原理到工业级C++实现的关键细节
1. 项目概述从“能用”到“可靠”的鸿沟“多边形碰撞检测”这七个字对于任何一个涉足游戏开发、物理仿真或者图形学领域的C开发者来说都绝不陌生。随便搜一下网上能找到成百上千篇教程从基础的分离轴定理SAT讲起附带几段代码示例似乎半小时就能搞定。然而当你真正把那段“教科书式”的代码塞进自己的项目处理起千奇百怪的多边形——可能是从建模软件导出的复杂网格可能是玩家实时编辑的地形甚至可能是物理破碎后产生的碎片——你会发现程序开始出现各种灵异现象物体明明没碰上却报告碰撞了明明嵌在一起了却检测为分离在某些刁钻的角度下性能骤降更别提那些因为浮点数精度问题导致的、时有时无的诡异抖动。这就是理论与实战的差距。标题里提到的“99%新手忽略的关键细节”指的不是算法原理本身而是将原理转化为健壮、高效、稳定的工业级代码过程中那些教科书不会写、博客很少提但却足以让你调试到崩溃的“魔鬼细节”。这些细节处理不好你的碰撞检测就永远停留在“玩具”阶段无法承受真实项目的考验。今天我们就来彻底拆解这些难点我会结合自己趟过的坑把那些关键的实现细节、优化策略和调试心得掰开揉碎了讲清楚。无论你是正在实现自己的第一个物理引擎还是试图优化项目中现有的碰撞系统这篇文章都能给你提供直达问题核心的实用指南。2. 核心思路与算法选型为什么是SAT多边形碰撞检测算法众多如分离轴定理SAT、吉尔伯特-约翰逊-凯尔蒂距离算法GJK、Minkowski差等。对于凸多边形SAT因其概念直观、实现相对简单且能提供碰撞深度和方向等额外信息成为最广泛采用的方法。它的核心思想非常优雅如果两个凸多边形没有发生碰撞那么必然存在一条直线分离轴能够将两者完全分隔开并且两个多边形在该直线上的投影区间不会重叠。2.1 SAT算法基础复盘与“想当然”的陷阱几乎所有教程都会告诉你SAT的步骤获取两个多边形所有边的法向量作为潜在的分离轴。将两个多边形分别投影到每一条轴上。检查投影区间是否重叠。如果所有轴上的投影都重叠则碰撞发生只要找到一条轴投影不重叠则分离。新手按照这个描述很快就能写出第一版代码。但这里第一个“想当然”的陷阱就出现了边的法向量怎么算很多人的第一反应是对于一条从点A(x1, y1)到点B(x2, y2)的边其方向向量是(B-A)那么法向量不就是(-dy, dx)或(dy, -dx)吗这没错但紧接着的问题是你需要的是单位法向量吗投影计算时使用边向量直接做法线和使用归一化后的单位法向量在判断区间重叠的“深度”时会有差异。SAT不仅可以判断是否碰撞还能求出最小穿透向量MTV用于在物理响应中将物体推开。而计算MTV需要的是在分离轴上的穿透深度这个深度值与轴的模长有关。因此一个常见的优化是在寻找分离轴时我们只关心“是否存在”可以使用未归一化的边向量作为轴但当检测到碰撞并需要计算MTV时则必须使用该轴的单位向量来计算精确的穿透深度。很多初版实现混淆了这两个阶段导致算出的推开方向不正确或力度有误。// 一个常见的、需要小心的法向量计算片段 struct Vec2 { float x, y; }; Vec2 GetEdgeNormal(const Vec2 a, const Vec2 b) { Vec2 edge {b.x - a.x, b.y - a.y}; // 法向量垂直于edge。选择(-edge.y, edge.x)还是(edge.y, -edge.x) // 这决定了法向量的“朝向”。为了保证法向量指向多边形的“外侧” // 需要与多边形顶点的缠绕顺序顺时针CW或逆时针CCW一致。 Vec2 normal {-edge.y, edge.x}; // 假设顶点是逆时针顺序这就是外法线 // 重要此时normal可能不是单位向量 return normal; }2.2 缠绕顺序与法线朝向一切的基础上段代码注释里提到了“缠绕顺序”。这是第二个关键细节也是后续很多问题的根源。多边形的顶点存储顺序顺时针或逆时针决定了其“正面”和“背面”。SAT算法要求我们使用外法线即指向多边形外部的法向量作为分离轴。如果法线方向算反了成了内法线投影区间会错乱导致碰撞检测完全失效。如何保证得到外法线这依赖于一个约定你的所有凸多边形顶点必须采用统一的缠绕顺序通常约定为逆时针CCW。这样对于每条边(v[i], v[i1])通过计算(v[i1] - v[i])并旋转90度(-dy, dx)得到的向量就是大致向外的法线。为了精确可以在初始化多边形时先检测其顶点顺序如果不是约定顺序则进行反转。这是一个预处理步骤但至关重要。// 检测并确保多边形顶点为逆时针顺序 void EnsureCCW(std::vectorVec2 vertices) { float area 0.0f; for (size_t i 0; i vertices.size(); i) { const Vec2 v1 vertices[i]; const Vec2 v2 vertices[(i 1) % vertices.size()]; area (v2.x - v1.x) * (v2.y v1.y); // 鞋带公式的一部分 } if (area 0.0f) { // 面积为正表示顺时针取决于坐标系Y轴向上时 std::reverse(vertices.begin(), vertices.end()); } }注意这里“面积”正负与坐标系Y轴向上还是向下有关。上面的代码假设Y轴向上屏幕坐标系常见。在OpenGL等Y轴向下的坐标系中判断条件可能相反。务必与你使用的坐标系匹配。3. 核心难点拆解与实战实现理解了基础我们进入深水区。下面这些难点才是区分“Demo代码”和“生产代码”的关键。3.1 浮点数精度幽灵碰撞与抖动之源浮点数计算是碰撞检测中最大的“玄学”问题。两个理论上应该刚好接触的多边形因为浮点误差其投影区间可能计算出一个极小的重叠如1e-7或极小的间隙如-1e-7。这会导致幽灵碰撞肉眼看着没碰上却检测为碰撞。抖动两个静止堆叠的物体在碰撞/分离状态间高频振荡。解决方案不是追求“零误差”而是引入一个容差Tolerance。核心思想是当两个投影区间的间隙小于某个极小正值时我们认为它们“已经接触”当重叠深度小于某个极小正值时我们认为它们“刚刚接触”可以忽略或做特殊处理。const float EPSILON 1e-6f; // 根据项目尺度调整1e-6对于米制单位是个不错的起点 bool CheckOverlapOnAxis(const Vec2 axis, const Polygon polyA, const Polygon polyB, float overlapDepth) { Projection projA ProjectPolygonOnAxis(axis, polyA); Projection projB ProjectPolygonOnAxis(axis, polyB); // 检查是否分离加入容差 if (projA.max projB.min - EPSILON || projB.max projA.min - EPSILON) { return false; // 找到分离轴 } // 计算重叠深度 overlapDepth std::min(projA.max, projB.max) - std::max(projA.min, projB.min); // 如果重叠深度极小可以视为“刚好接触”MTV可能不稳定可特殊处理 return true; }在计算最小穿透向量MTV时也应对穿透深度进行“净化”如果深度绝对值小于EPSILON可以将其置为0或者直接忽略这条轴作为MTV候选因为数值不稳定。3.2 最小穿透向量计算不只是深度SAT的优势在于能给出MTV即推开物体所需的最小向量。但计算MTV有几个坑轴的方向性分离轴法向量有正反两个方向。投影区间[min, max]的重叠深度是一个标量但我们需要一个向量。这个向量的方向应该是从A指向B还是反过来这取决于你如何定义“推开”。通常我们计算的是将A从B身上推开的最小向量。这意味着当计算重叠深度时我们需要知道是A的max超过了B的min还是B的max超过了A的min以此决定MTV的方向是沿着轴的方向还是反方向。多轴比较我们会在多条轴上得到重叠。MTV是其中重叠深度最小的那条轴所对应的向量深度 * 单位法向量。这里“最小”指的是绝对值最小。必须遍历所有轴找到这个最小值。零重叠或负深度由于容差的存在可能计算出极小的正深度、零深度或负深度视为分离。在比较和选择MTV时必须正确处理这些边界情况。bool SATCollision(const Polygon polyA, const Polygon polyB, Vec2 mtv) { float minOverlap std::numeric_limitsfloat::max(); Vec2 smallestAxis; // 检查A的边 for (size_t i 0; i polyA.vertices.size(); i) { Vec2 edge polyA.vertices[(i1)%polyA.vertices.size()] - polyA.vertices[i]; Vec2 axis {-edge.y, edge.x}; // 外法线 // 为了MTV计算这里最好归一化使穿透深度物理意义明确 axis Normalize(axis); float overlap; if (!CheckOverlapOnAxis(axis, polyA, polyB, overlap)) { return false; // 分离 } if (overlap minOverlap) { minOverlap overlap; smallestAxis axis; // 需要判断方向确保mtv的方向是将A从B身上推开 // 可以通过比较两个投影的中心点来确定 float centerA (ProjectionA.min ProjectionA.max) * 0.5f; float centerB (ProjectionB.min ProjectionB.max) * 0.5f; if (centerA centerB) { smallestAxis axis; // 方向从A指向B } else { smallestAxis -axis; // 方向从B指向A即A需要被推向-axis方向 } } } // 检查B的边类似代码略 // ... if (minOverlap ! std::numeric_limitsfloat::max()) { mtv smallestAxis * minOverlap; return true; } return false; // 理论上不会走到这里 }3.3 顶点投影与区间计算效率与精度平衡投影计算ProjectPolygonOnAxis是SAT中最耗时的部分因为需要对每个顶点进行点积运算。对于一个有n个顶点的多边形每次投影是O(n)操作。两个多边形检查m条边m nA nB总复杂度是O(nA * nB)。对于复杂多边形这是性能瓶颈。优化点1预先计算并缓存法向量。多边形的边法向量在物体旋转时才改变。如果物体是刚体且旋转不频繁可以缓存这些法向量避免每帧重复计算。优化点2使用SoA数组结构或SIMD指令。将顶点的x和y坐标分别存储在连续数组中可以利用SIMD指令同时计算多个顶点的点积大幅提升投影计算速度。这是工业级物理引擎的常见优化。优化点3及早退出Early Out。在遍历所有轴之前如果发现某条轴上的投影间隙大于某个值可以立即返回“分离”无需检查剩余轴。但注意计算MTV时需要遍历所有轴找到最小重叠所以“检测是否碰撞”和“计算MTV”可以是两个不同优化路径的函数。精度方面点积运算本身是浮点密集操作。确保你的顶点坐标尺度合理避免过大或过小的数值并考虑使用双精度浮点数double进行关键的投影和重叠计算尽管这会牺牲一些性能但能显著提升稳定性尤其是在大型世界坐标中。3.4 复杂多边形与凹多边形处理SAT只适用于凸多边形。如果你的模型是凹多边形直接应用SAT会得到错误结果。处理凹多边形有两种主流方法分解将凹多边形分解为多个凸多边形的集合凸分解。然后对这些凸部分分别进行SAT检测。这是最通用的方法但分解算法本身如耳切法比较复杂且分解结果会影响性能。GJK算法吉尔伯特-约翰逊-凯尔蒂算法是另一种检测凸形状碰撞的方法它通过迭代计算Minkowski差来工作天生支持凸形状并且可以通过EPA算法得到穿透深度。对于凹多边形仍然需要先进行凸分解但GJK在处理某些类型的凸形状时可能比SAT更高效。在项目中一个务实的选择是规定所有碰撞体必须是凸的。在美术资源和关卡设计阶段就做好约束。如果必须使用凹形状则在导入时或运行时预先进行凸分解并将分解后的凸部分作为一组碰撞体来处理。4. 性能优化与工程化实践当你的基础碰撞检测工作后下一步就是让它能在游戏里跑得快、跑得稳。4.1 空间划分与粗检测逐对检测所有多边形是O(N²)的不可行。必须引入空间划分结构进行粗检测Broad Phase快速筛选出可能发生碰撞的对象对再交给SAT进行精检测Narrow Phase。网格划分将世界划分为均匀网格每个物体根据其AABB轴对齐包围盒注册到覆盖的网格中。只检测同一网格或相邻网格内的物体对。实现简单适合物体分布均匀的场景。四叉树/八叉树递归地将空间划分为四个/八个子区域动态地将物体放入相应节点。适合物体分布不均匀的场景查询效率高。BVH层次包围盒树为每个物体构建一个层次结构的包围盒如AABB树。从根节点开始如果两个包围盒不相交则其下的所有子物体都不需要检测。特别适合检测单个复杂物体如由许多三角形组成的网格的自碰撞或与环境的大量检测。粗检测阶段通常使用AABB轴对齐包围盒因为AABB的重叠检测极其快速只需比较最大最小值。你需要为每个动态物体每帧更新其AABB这通常比直接更新多边形顶点要廉价。4.2 缓存与增量计算对于移动或旋转的物体其世界空间下的顶点和法向量每帧都需要更新。完全重新计算是昂贵的。缓存变换后的顶点在物体变换位置、旋转、缩放更新后计算一次世界坐标下的顶点并缓存直到下次变换发生。SAT检测都使用缓存后的顶点。增量更新法向量如果只有平移法向量不变。如果发生旋转可以对本地空间的法向量应用同样的旋转矩阵而不是重新从边计算。缩放如果是均匀的不影响法线方向但可能需要重新归一化非均匀缩放会改变形状需要谨慎处理可能需重新计算。4.3 模块化与接口设计一个好的碰撞检测模块应该职责清晰、接口简洁。形状基类定义Shape基类提供虚函数如GetType(),GetAABB(),Support()用于GJK等。凸多边形类继承自Shape内部存储本地顶点、世界缓存顶点、法向量缓存等。提供UpdateTransform()和CheckCollision()方法。碰撞检测管理器管理所有碰撞体执行粗检测和精检测调度。提供注册/注销接口以及查询碰撞结果的接口。碰撞结果结构体不仅返回是否碰撞还应包含MTV、碰撞点或近似碰撞点、碰撞法线、以及涉及的两个物体引用等信息供物理响应模块使用。struct CollisionResult { bool isColliding; Vec2 mtv; // 最小穿透向量 Vec2 normal; // 碰撞法线单位向量通常指向物体A外部 float depth; // 穿透深度 Vec2 contactPoint; // 近似接触点计算这个点本身又是一个话题 Collider* colliderA; Collider* colliderB; };5. 调试与可视化让碰撞“看得见”碰撞检测的Bug往往难以捉摸因为没有视觉反馈。实现调试可视化是必不可少的开发环节。绘制多边形轮廓在调试模式下用线条绘制出每个碰撞体的精确形状世界坐标下的顶点连线。绘制AABB用不同颜色的线框绘制每个物体的AABB用于验证粗检测。高亮碰撞对当检测到碰撞时用醒目的颜色如红色填充或勾勒发生碰撞的两个多边形。绘制分离轴/MTV在发生碰撞的位置绘制出计算得到的MTV向量一条从碰撞点出发的箭头这能直观地检查MTV方向是否正确。绘制投影区间在选定的分离轴上绘制出两个多边形在该轴上的投影区间可以画成两条平行的线段用不同颜色表示两个物体直观展示重叠或分离的状态。这些可视化工具能帮你快速定位是算法逻辑错误、数据问题顶点顺序、变换错误还是精度问题。6. 常见问题与排查清单即使按照指南实现你仍可能遇到奇怪的问题。下面是一个快速排查清单问题现象可能原因排查步骤物体明显分离却报告碰撞1. 顶点缠绕顺序不一致导致法线方向错误。2. 浮点容差EPSILON设置过大。3. AABB粗检测失效导致不该检测的对进入了精检测。1. 可视化多边形和法线检查法线是否指向外侧。2. 减小EPSILON或使用双精度计算关键比较。3. 检查AABB更新逻辑确保其紧密包围多边形。物体明显碰撞却未检测到1. 分离轴漏算例如只算了一个多边形的边。2. 顶点坐标或变换矩阵有误世界坐标错误。3. 投影区间计算错误min/max搞反。1. 确认检查了两个多边形所有边的法向量。2. 可视化世界坐标下的多边形顶点确认其位置正确。3. 单步调试打印一条已知碰撞轴上的投影区间值。MTV方向错误物体被“吸进去”1. MTV方向判断逻辑错误中心点比较有误。2. 法向量未归一化导致深度计算和方向结合后出错。1. 可视化MTV箭头观察其方向。检查计算MTV方向时的符号逻辑。2. 确保用于计算MTV深度的轴是单位向量。性能随物体增多急剧下降1. 未使用空间划分Broad Phase是O(N²)检测。2. 每帧都在重新计算顶点和法向量未缓存。3. 投影计算未做任何优化如SIMD。1. 实现网格或四叉树进行粗检测。2. 仅在变换改变时更新缓存。3. 对热点函数投影计算进行性能分析。物体堆叠时剧烈抖动1. 浮点精度问题导致碰撞状态在帧间频繁切换。2. 物理响应处理不当与碰撞检测形成正反馈。3. MTV深度过小数值不稳定。1. 增加合理的碰撞容差并引入“睡眠”机制对低速/静止物体停止检测。2. 在物理积分中引入位置纠正但避免过度纠正。3. 对小于阈值的穿透深度忽略或施加一个很小的固定纠正力。旋转后碰撞形状不对1. 顶点变换矩阵应用错误顺序、左乘右乘。2. 法向量更新未考虑旋转直接用了本地法线。3. 缩放为非均匀导致形状不再是凸的或法线错误。1. 确认变换矩阵通常为 Scale * Rotation * Translation。2. 对法向量应用旋转矩阵如果是单位向量只需3x3旋转部分。3. 考虑禁止非均匀缩放或在碰撞检测中使用未缩放的形状。最后分享一个我个人的深刻体会不要试图在碰撞检测中追求数学上的完美。物理引擎的本质是“看起来正确”的近似模拟。花费大量精力去处理那些极端刁钻的、几乎不会在正常游戏中出现的碰撞情况比如两个高速旋转的细长多边形以极小的角度相切其性价比往往很低。你的目标是建立一个在99.9%的游戏场景下稳定、高效、可预测的系统。对于剩下的0.1%有时一个巧妙的约束、一个特殊 case 的处理甚至是一个合理的“作弊”比如在特定条件下强制认为不碰撞比一个理论上完美但复杂脆弱的通用方案要可靠得多。理解原理然后为了性能和鲁棒性做出务实的妥协和优化这才是工程实践的真谛。