Unity 2D 碰撞分离实战：手动实现 GJK+EPA 算法解决穿透问题

1. 项目概述为什么我们需要自己动手处理碰撞分离在Unity里做2D游戏物理引擎是个好东西Rigidbody2D和Collider2D一挂碰撞检测和响应基本就交给引擎了省心。但不知道你有没有遇到过这种情况两个物体高速运动或者因为复杂的物理模拟它们“卡”在了一起或者穿透得很深引擎自带的物理解算有时候会显得力不从心物体可能会抖动、弹飞或者干脆就粘住了。尤其是在一些对碰撞精度和响应有特殊要求的场景比如高精度模拟的物理谜题、需要自定义碰撞反馈的动作游戏或者你正在开发自己的简易物理引擎时Unity内置的“黑盒”处理就可能不够用了。这时候我们就需要深入到碰撞检测与响应的“最后一公里”——精确计算穿透向量Penetration Vector并据此将物体准确地分离开。GJKGilbert–Johnson–Keerthi算法和EPAExpanding Polytope Algorithm算法就是解决这个问题的黄金搭档。GJK负责快速判断两个凸形状是否相交而EPA则在它们相交后精确计算出最小的穿透深度和方向。网上关于GJK/EPA原理的文章不少但大多停留在数学推导和伪代码真正能直接抄作业、在Unity里跑起来的完整C#实现尤其是针对2D的并不多见。所以这个项目的目的很明确不依赖Unity的物理引擎纯手动实现一套基于GJKEPA算法的2D凸多边形碰撞检测与分离系统并提供可直接集成到项目中的完整C#源码。这不仅能让你彻底理解碰撞响应的核心更能让你在遇到棘手物理问题时手里多一把锋利的“手术刀”。2. 核心算法原理快速扫盲在动手写代码之前我们得先搞清楚GJK和EPA到底在干什么。不用担心我会尽量用最直白的方式解释。2.1 GJK算法用“单纯形”快速问“是否碰撞”你可以把GJK想象成一个非常聪明的“盲人摸象”过程。它的目标不是知道大象具体长什么样而是快速回答“我的面前有没有一头大象两个形状是否相交”。它的核心是一个叫Minkowski差的数学概念。对于两个形状A和B它们的Minkowski差定义为 A - B {a - b | a ∈ A, b ∈ B}。这个差集有一个神奇的性质如果A和B相交那么Minkowski差集必然包含原点0,0。反之如果它们不相交原点就在Minkowski差集之外。GJK算法的工作就是它不需要计算出整个庞大的Minkowski差集而是通过一种叫“支撑函数Support Function”的迭代采样在Minkowski差集中构建一个越来越逼近原点的单纯形Simplex——在2D里单纯形就是点、线段或者三角形。支撑函数这是算法的基石。给定一个方向向量d形状A的支撑点是在这个方向上投影最远的点。对于Minkowski差 A-B支撑点 s(d) support_A(d) - support_B(-d)。简单说就是分别在两个形状上找“最朝d方向”和“最朝-d方向”的点然后相减。迭代构建单纯形算法从一个随机方向开始用支撑函数得到一个Minkowski差集上的点。然后它朝着原点的方向不断寻找新的支撑点并用这些点构建单纯形点-线段-三角形。每次迭代它都检查当前单纯形是否包含原点。终止条件如果在某次迭代中新找到的支撑点在与原点相反方向上的投影距离不再增加即无法更靠近原点说明原点不在Minkowski差集中两个形状不相交。如果构建出的单纯形三角形包含了原点则说明它们相交。GJK的高明之处在于它的速度它通常只需要几次迭代就能得出结论复杂度与顶点数无关只与迭代次数有关。2.2 EPA算法相交之后问“穿多深往哪推”当GJK告诉我们“撞上了”之后EPA就该上场了。EPA要解决的问题是既然撞了那它们重叠了多少我应该把其中一个物体往哪个方向、移动多少距离才能让它们刚好分开EPA在GJK停止的地方开始工作。GJK最后得到的那个包含了原点的单纯形一个三角形就是EPA的起点。EPA会把这个三角形看作是一个**凸包Polytope**的初始状态这个凸包位于Minkowski差集的边界上并且包裹着原点。寻找最近边在当前的凸包一开始是三角形上找到离原点最近的那条边。沿法线方向扩张沿着这条最近边的法线方向指向凸包外部调用支撑函数得到Minkowski差集边界上的一个新点。重构凸包将这个新点插入到凸包中重构一个更大的、仍然包裹着原点的凸包。迭代收敛重复步骤1-3。每次迭代凸包都会更贴合Minkowski差集真正的边界。最近边到原点的距离会逐渐收敛。终止与输出当新加入的支撑点到最近边的距离变化小于一个非常小的阈值比如0.0001时我们认为已经足够精确了。此时那个“最近边”的法线方向就是穿透方向Penetration Normal而原点到该边的距离就是穿透深度Penetration Depth。这个穿透方向和深度正是我们将两个相交物体分离开所需的关键信息。将物体A沿此方向移动深度距离或者将物体B反向移动它们就能恰好分开。注意GJK/EPA只适用于**凸Convex**形状。对于凹形状你需要先将其分解为多个凸形状的组合凸分解Convex Decomposition。Unity的PolygonCollider2D如果勾选了“Used by Composite”其内部就是这样处理的。3. 实战C#核心代码实现与解析理论说再多不如一行代码。下面我们分模块拆解实现。我会先给出关键代码片段然后解释其作用和注意事项。3.1 数据结构定义支撑点与单纯形首先我们需要定义一些基础数据结构。// 描述Minkowski差集上的一个支撑点 public struct SupportPoint { public Vector2 Point; // Minkowski差点 (a - b) public Vector2 PointA; // 来自形状A的顶点 public Vector2 PointB; // 来自形状B的顶点 public SupportPoint(Vector2 point, Vector2 pointA, Vector2 pointB) { Point point; PointA pointA; PointB pointB; } } // 描述一个2D单纯形顶点数3 public class Simplex { private ListSupportPoint _points new ListSupportPoint(); public int Count _points.Count; public void Insert(SupportPoint point, int index) { _points.Insert(index, point); } public SupportPoint this[int index] _points[index]; public void RemoveAt(int index) { _points.RemoveAt(index); } }为什么需要记录PointA和PointB这是关键EPA算法最后输出的穿透向量需要作用回原始物体。我们只知道Minkowski差点Point是不够的必须知道这个点是由哪两个原始顶点PointA和PointB相减得来的这样才能在分离物体时知道力应该作用在哪个局部坐标上或者用于计算碰撞点。3.2 支撑函数的实现支撑函数是算法的性能关键。对于不同的形状实现方式不同。这里以最常见的凸多边形为例。public static SupportPoint GetSupportPoint(ListVector2 verticesA, ListVector2 verticesB, Vector2 direction) { // 在形状A上找方向d上最远的点 Vector2 pointA GetFarthestPointInDirection(verticesA, direction); // 在形状B上找反方向-d上最远的点因为Minkowski差是A-B Vector2 pointB GetFarthestPointInDirection(verticesB, -direction); // 计算Minkowski差点 Vector2 minkowskiPoint pointA - pointB; return new SupportPoint(minkowskiPoint, pointA, pointB); } private static Vector2 GetFarthestPointInDirection(ListVector2 vertices, Vector2 direction) { float maxDot float.NegativeInfinity; Vector2 farthestVertex vertices[0]; foreach (var vertex in vertices) { // 点积可以反映顶点在给定方向上的投影长度 float dot Vector2.Dot(vertex, direction); if (dot maxDot) { maxDot dot; farthestVertex vertex; } } return farthestVertex; }实操心得这里的顶点列表vertices应该是物体在世界空间下的坐标。如果你的碰撞体数据是局部坐标需要在调用前用物体的变换矩阵位置、旋转、缩放将其转换到世界空间。这是一个常见的错误来源——在局部坐标下计算支撑点会导致整个算法失效。3.3 GJK算法核心迭代这是GJK的判断循环我把它写成了一个返回布尔值的函数。public static bool GJKCollisionCheck(ListVector2 verticesA, ListVector2 verticesB, out Simplex simplex) { simplex new Simplex(); // 1. 选择初始方向可以取A中心指向B中心的方向 Vector2 direction (GetCenter(verticesB) - GetCenter(verticesA)).normalized; if (direction Vector2.zero) direction Vector2.right; // 防零向量 // 2. 获取第一个支撑点 SupportPoint sp GetSupportPoint(verticesA, verticesB, direction); simplex.Insert(sp, 0); // 下一次搜索方向指向原点 direction -sp.Point; // 3. 开始迭代最多迭代次数防止死循环 int maxIterations 20; for (int i 0; i maxIterations; i) { // 获取新支撑点 sp GetSupportPoint(verticesA, verticesB, direction); // 如果新点在与方向相反的方向上没有推进点积0则原点不在Minkowski差集中 if (Vector2.Dot(sp.Point, direction) 0) { return false; // 不相交 } simplex.Insert(sp, 0); // 插入到单纯形中 // 根据单纯形顶点数处理并更新搜索方向 if (HandleSimplex(ref simplex, ref direction)) { // HandleSimplex返回true说明单纯形包含了原点 return true; // 相交 } // 否则direction已被更新为指向原点的方向继续循环 } // 达到最大迭代次数保守起见返回不相交或者可以根据情况抛出异常 return false; }关键在HandleSimplex函数里它根据单纯形是线段还是三角形使用向量叉乘等几何运算来判断原点位置并更新搜索方向。这部分代码几何性较强核心是判断原点相对于线段的位置在线段左侧、右侧还是之间以及是否在三角形内部。private static bool HandleSimplex(ref Simplex simplex, ref Vector2 direction) { if (simplex.Count 2) { // 单纯形是一条线段 AB // 使用向量运算判断原点相对于线段AB的位置并更新direction使其指向原点 // 如果原点在线段AB的“之间”则说明单纯形线段已经包含原点在2D中不可能线段是1维的 // 但实际上我们需要检查原点是否在线段AB的“前面”。这里逻辑是判断原点是否在AB的垂直区域。 // 具体实现涉及向量AO, AB, 以及叉乘perp(AB)等。 return UpdateDirectionForLine(simplex, ref direction); } else if (simplex.Count 3) { // 单纯形是一个三角形 ABC // 检查原点是否在三角形内部。如果是返回true碰撞发生。 // 否则移除离原点最远的那个点将单纯形退化为一条边并更新direction指向原点。 return UpdateDirectionForTriangle(simplex, ref direction); } // simplex.Count 1 的情况在循环中处理就是继续找点 return false; }3.4 EPA算法从相交到分离向量当GJK返回true并给出一个包含原点的初始单纯形后EPA开始工作。public static bool EPAPenetration(Simplex simplex, ListVector2 verticesA, ListVector2 verticesB, out Vector2 penetrationNormal, out float penetrationDepth) { penetrationNormal Vector2.zero; penetrationDepth 0f; // 将GJK得到的单纯形作为EPA的初始凸包多边形 ListEdge polytope new ListEdge(); // 将单纯形的边添加到凸包中注意顺序保证凸包是逆时针的 // 假设simplex有3个点A,B,C // 添加边 AB, BC, CA // ... float tolerance 0.0001f; int maxIterations 30; Edge closestEdge default; SupportPoint newSupportPoint; for (int i 0; i maxIterations; i) { // 1. 找到凸包中离原点最近的边 FindClosestEdge(polytope, out closestEdge, out float distance); // 2. 沿着该边的外法线方向获取新的支撑点 Vector2 supportDirection closestEdge.Normal; // 外法线方向 newSupportPoint GetSupportPoint(verticesA, verticesB, supportDirection); // 3. 计算新支撑点到这条边的距离在法线方向上的投影 float supportDistance Vector2.Dot(newSupportPoint.Point, supportDirection); // 4. 判断是否收敛如果新点带来的距离增量非常小则认为找到最小穿透 if (Mathf.Abs(supportDistance - distance) tolerance) { penetrationNormal closestEdge.Normal; penetrationDepth supportDistance tolerance; // 加一点容差确保分离 return true; } // 5. 未收敛将新点插入凸包重构凸包 // 插入逻辑找到新点应该插入的两条边之间移除旧的边添加两条新边 InsertPointInPolytope(ref polytope, newSupportPoint, closestEdge.Index); } // 迭代次数用尽返回最后一次找到的近似结果 penetrationNormal closestEdge.Normal; penetrationDepth Vector2.Dot(newSupportPoint.Point, closestEdge.Normal); return false; // 或者 true但精度可能不够 }FindClosestEdge函数需要遍历凸包的所有边计算原点到每条边的有符号距离通过边法线与原点向量点乘并记录距离最小的边及其外法线方向。InsertPointInPolytope函数是EPA的另一个关键它需要维护凸包的有序性逆时针。插入新点后要确保凸包仍然是凸的并且所有边都指向外侧。注意事项EPA的迭代次数和容差tolerance需要根据你的游戏尺度来调整。如果你的游戏单位是米那么tolerance0.00010.1毫米通常足够。迭代次数maxIterations防止无限循环30-50次对于2D凸多边形通常绰绰有余。过高的精度要求会导致不必要的性能开销。4. 集成到Unity碰撞分离的完整流程有了穿透法线和深度我们就能分离物体了。但这里有一个非常重要的选择分离哪个物体通常有几种策略分离质量小的物体符合物理直觉轻的物体被推开。分离运动中的物体比如只分离动态物体静态物体不动。按比例分离根据物体的质量或自定义权重按比例分配穿透深度。下面是一个简单的分离函数示例假设我们选择分离物体Apublic static void SeparateBodies(Transform transformA, Transform transformB, Vector2 penetrationNormal, float penetrationDepth, ListVector2 localVerticesA, ListVector2 localVerticesB) { // 分离策略将物体A沿穿透法线方向移动 Vector2 separationVector penetrationNormal * penetrationDepth; transformA.position new Vector3(separationVector.x, separationVector.y, 0); // 可选更高级的处理计算碰撞点并应用冲量 // 1. 使用EPA最后得到的最近边上的信息或者用支撑点近似找到世界空间下的碰撞点。 // 2. 根据碰撞点、法线、物体速度和质量计算冲量Impulse。 // 3. 更新物体的速度如果是Rigidbody2D可以修改其velocity。 }一个完整的每帧碰撞处理流程可以这样组织void FixedUpdate() { // 假设我们有两个碰撞体数据 MyCollider colliderA ...; MyCollider colliderB ...; // 1. 获取世界坐标下的顶点 ListVector2 worldVertsA colliderA.GetWorldVertices(); ListVector2 worldVertsB colliderB.GetWorldVertices(); Simplex simplex; // 2. GJK检测 if (GJKCollisionCheck(worldVertsA, worldVertsB, out simplex)) { Vector2 normal; float depth; // 3. EPA计算穿透信息 if (EPAPenetration(simplex, worldVertsA, worldVertsB, out normal, out depth)) { // 4. 根据策略分离物体 SeparateBodies(colliderA.transform, colliderB.transform, normal, depth, colliderA.localVertices, colliderB.localVertices); // 5. 可选触发碰撞事件传递法线、深度、碰撞点等信息 OnCollisionDetected(colliderA, colliderB, normal, depth); } } }5. 性能优化与常见陷阱自己实现物理算法性能是绕不开的话题。GJK/EPA本身是高效的但不当的实现会成为瓶颈。5.1 性能优化点缓存支撑点计算对于固定形状在给定方向上的最远点通常是那几个“极端点”。可以考虑为每个形状预计算一个凸包并缓存各个方向上的候选顶点但实现复杂度较高。对于顶点数不多的多边形直接线性搜索通常可以接受。提前剔除Broad Phase这是最重要的优化不要对所有物体两两进行GJK检测。先用AABB轴对齐包围盒或包围圆进行粗略的快速剔除只有AABB相交的物体对才进入GJK/EPA窄相位检测。Unity的物理引擎内部就是这样做的。限制迭代次数如代码所示为GJK和EPA设置合理的最大迭代次数。使用值类型SupportPoint、Vector2使用struct值类型减少堆分配。避免频繁的List分配Simplex和EPA的polytope列表可以在类级别缓存每帧复用而不是每次检测都new一个新的。5.2 常见问题与排查物体抖动或穿透原因分离后下一帧由于速度等原因又立刻碰撞EPA计算出的分离向量可能略有不同导致位置来回变化。解决引入“位置纠正Positional Correction”或“滑移Slop”。不要完全按照理论穿透深度分离而是分离(depth - slop)留出一个微小的允许穿透量如0.01个单位。这能增加稳定性。许多物理引擎都有这个参数。EPA不收敛或结果异常原因a顶点数据不是凸多边形。必须确保输入给GJK/EPA的顶点列表构成一个凸多边形且顶点顺序是逆时针的。你可以用Vector2.Cross遍历所有边检查叉积是否始终同号都大于0或都小于0。原因b浮点数精度问题。在判断点是否在边上、距离是否接近零时使用一个小的容差值Mathf.Epsilon。原因c支撑函数返回的点不在形状的边界上。检查你的顶点变换局部到世界是否正确以及GetFarthestPointInDirection函数逻辑。GJK循环无法终止原因方向向量计算错误导致搜索陷入循环。仔细检查HandleSimplex中更新方向的几何逻辑确保方向向量始终指向原点。调试在迭代中打印direction和simplex的点可视化观察算法的搜索路径。分离后物体旋转异常注意本项目提供的分离只处理了平移Translation。如果你同时需要处理旋转引起的碰撞比如一个长杆旋转着插进另一个物体则需要更复杂的“连续碰撞检测CCD”和考虑转动惯量的冲量计算。本方案适用于大多数平移为主的碰撞响应。6. 扩展与应用场景掌握了基础的GJKEPA分离你可以在此基础上构建更丰富的物理交互碰撞响应冲量计算分离解决了穿透但物体应该有反弹。结合碰撞法线、相对速度、恢复系数弹性和摩擦系数可以计算碰撞冲量并应用到物体的线速度和角速度上模拟真实的碰撞反弹。这需要你管理物体的质量、转动惯量和速度状态。射线投射Ray CastGJK算法可以很容易地改造成射线与凸形状的相交检测原理类似将射线看作一个长度无限的“薄”形状。最近点计算当GJK判断为不相交时其最终得到的单纯形通常是线段可以用于计算两个凸形状之间的最近点和最近距离这在AI寻路、障碍规避时很有用。自定义碰撞体你可以为任何凸形状实现支撑函数比如椭圆、胶囊体可以用线段和圆的Minkowski和来构造。这样就能让自定义的奇怪形状也接入你的碰撞系统。实现自己的GJK/EPA碰撞分离就像给游戏开发技能树点了一个高级专精。它让你从物理引擎的使用者变成了理解其内在逻辑的掌控者。当再次遇到诡异的碰撞bug时你不再只能盲目调整物理材质参数而是可以深入到算法层面去分析和解决。提供的完整源码是一个坚实的起点建议你亲手敲一遍并在简单的几何体上调试、可视化每一步这比读十篇文章理解得更深刻。