Unity游戏开发：基于二维叉乘与分离轴定理的多边形碰撞检测实战

1. 项目概述为什么多边形碰撞检测是游戏开发的“硬骨头”在游戏开发里碰撞检测是个绕不开的基础话题。从最简单的“碰到就死”到复杂的物理模拟碰撞检测的精度和效率直接决定了游戏的物理反馈是否真实、玩法是否流畅。对于矩形、圆形这类规则形状Unity内置的Collider组件已经做得相当好了开箱即用。但一旦涉及到不规则的多边形比如一个自定义形状的岛屿、一个破碎的岩石碎片或者一个复杂的角色轮廓问题就变得棘手起来。很多开发者初遇这个问题可能会想“用多个BoxCollider或者CircleCollider拼起来不就行了” 这确实是一种方案但对于复杂轮廓你需要管理大量的子碰撞体性能开销大且边缘的贴合度总是不尽如人意物理反馈也显得生硬。另一种思路是使用Unity的PolygonCollider2D它确实能完美贴合任意凸多边形但对于凹多边形它内部会自动进行三角剖分有时会产生不符合预期的碰撞区域且在动态生成或频繁变形的物体上性能消耗也不容忽视。这时我们就需要一种更底层、更可控的解决方案分离轴定理Separating Axis Theorem, SAT。而实现SAT算法的核心数学工具就是二维叉乘。这个项目就是要带你亲手用Unity和C#从零实现一套基于二维叉乘和SAT的多边形碰撞检测系统。我们不止是调用API而是要深入理解每一行代码背后的几何原理让你在面对任何奇形怪状的碰撞需求时都能心中有数手中有策。2. 核心原理拆解二维叉乘与分离轴定理的几何直觉在动手写代码之前我们必须把核心原理吃透。很多教程一上来就扔公式看得人云里雾里。我们换个方式用最直观的“投影”和“影子”来理解。2.1 二维叉乘到底“乘”出了什么在三维空间叉乘的结果是一个新的向量。但在二维空间两个向量的叉乘结果是一个标量一个数字。这个数字的几何意义极其重要它代表了由这两个向量所张成的平行四边形的有向面积。公式很简单对于二维向量a (ax, ay)和b (bx, by)它们的叉乘有时也叫外积或叉积定义为a × b ax * by - ay * bx这个值s能告诉我们什么正负号方向如果s 0表示向量b在向量a的逆时针方向如果s 0则在顺时针方向如果s 0则两向量共线。绝对值大小|s|等于以a和b为邻边的平行四边形的面积。在碰撞检测中我们最关心的是它的方向判断功能。例如判断一个点在一个多边形的哪一侧或者判断两个多边形的边是否“面对面”。2.2 分离轴定理一维空间里的“有没有空隙”SAT的原理可以概括为一句话如果能找到一条直线轴使得两个多边形在这条直线上的投影影子不重叠那么这两个多边形就一定没有碰撞。想象一下在阳光下两个物体在地上会有影子。如果它们的影子在任何一个方向上都是分开的那这两个物体在三维空间里肯定也没挨着。SAT就是把三维的“任何方向”简化到二维多边形所有边的法线方向上。为什么是边的法线因为对于凸多边形只需要检查每个边的法线方向作为投影轴就足以判断是否分离。这是SAT算法高效的关键。算法步骤的通俗解释遍历多边形A的每一条边。求出这条边的法向量垂直于边的向量。这里就会用到叉乘的一个小技巧给定边向量edge一个简单的法向量是(-edge.y, edge.x)。你可以用二维叉乘验证edge × normal的结果不为零说明它们垂直。将这条法向量单位化变成长度为1作为我们当前的“投影轴”。把多边形A和多边形B的所有顶点都“投影”到这条轴上。投影操作其实就是顶点向量与轴的单位向量进行点积得到一个标量值。找出两个多边形在这条轴上投影的最小值和最大值。这就在这条轴上得到了两个线段A的投影线段和B的投影线段。判断这两个线段是否重叠。如果不重叠那么恭喜找到了一个分离轴两个多边形肯定没碰撞算法可以立即返回false。如果对于多边形A的所有边以及多边形B的所有边是的也要检查B的边作为轴在所有轴上的投影都重叠那么两个多边形就是碰撞的。这个“投影重叠”的判断是整个算法的核心也是我们代码里要反复计算的部分。注意SAT只适用于凸多边形。对于凹多边形你需要先将其分解为多个凸多边形凸分解再分别检测。本文实现的也是凸多边形的检测。3. 实战准备Unity项目结构与核心数据结构理解了原理我们开始搭建战场。在Unity中新建一个2D项目。3.1 创建自定义多边形组件我们不直接使用PolygonCollider2D而是自己定义多边形的数据和行为这样理解更深刻。创建一个C#脚本命名为CustomPolygonCollider。这个脚本需要挂载在游戏物体上用来定义多边形的形状。using UnityEngine; using System.Collections.Generic; [RequireComponent(typeof(MeshRenderer), typeof(MeshFilter))] public class CustomPolygonCollider : MonoBehaviour { // 多边形的顶点列表本地坐标 public ListVector2 vertices new ListVector2() { new Vector2(-0.5f, -0.5f), new Vector2(0.5f, -0.5f), new Vector2(0.5f, 0.5f), new Vector2(-0.5f, 0.5f) }; // 用于可视化多边形的Mesh private Mesh mesh; void Start() { GenerateMesh(); } void OnDrawGizmosSelected() { // 在Scene视图中绘制多边形边线 if (vertices.Count 2) return; Gizmos.color Color.green; for (int i 0; i vertices.Count; i) { Vector3 current transform.TransformPoint(vertices[i]); Vector3 next transform.TransformPoint(vertices[(i 1) % vertices.Count]); Gizmos.DrawLine(current, next); } // 绘制顶点 Gizmos.color Color.red; foreach (var vertex in vertices) { Gizmos.DrawSphere(transform.TransformPoint(vertex), 0.05f); } } void GenerateMesh() { // 根据顶点生成一个Mesh方便可视化 if (vertices.Count 3) return; MeshFilter meshFilter GetComponentMeshFilter(); if (meshFilter null) return; mesh new Mesh(); Vector3[] meshVertices new Vector3[vertices.Count]; for (int i 0; i vertices.Count; i) { meshVertices[i] new Vector3(vertices[i].x, vertices[i].y, 0); } mesh.vertices meshVertices; // 三角剖分简单中心剖分仅适用于凸多边形 int[] triangles new int[(vertices.Count - 2) * 3]; for (int i 0; i vertices.Count - 2; i) { triangles[i * 3] 0; triangles[i * 3 1] i 1; triangles[i * 3 2] i 2; } mesh.triangles triangles; mesh.RecalculateNormals(); meshFilter.mesh mesh; } // 获取变换后的世界坐标顶点 public Vector2[] GetWorldVertices() { Vector2[] worldVertices new Vector2[vertices.Count]; for (int i 0; i vertices.Count; i) { worldVertices[i] transform.TransformPoint(vertices[i]); } return worldVertices; } }这个组件允许我们在Inspector面板中编辑顶点并在Scene视图中实时看到多边形的形状。GetWorldVertices方法至关重要因为碰撞检测需要在同一个坐标系世界坐标系下进行。3.2 创建碰撞检测管理器我们需要一个“裁判”来执行检测逻辑。创建一个名为CollisionManager的脚本可以挂在一个空物体上。using UnityEngine; using System.Collections.Generic; public class CollisionManager : MonoBehaviour { public ListCustomPolygonCollider colliders new ListCustomPolygonCollider(); void Update() { // 每帧进行两两碰撞检测 for (int i 0; i colliders.Count; i) { for (int j i 1; j colliders.Count; j) { bool isColliding SATCollisionDetection( colliders[i].GetWorldVertices(), colliders[j].GetWorldVertices() ); // 这里可以处理碰撞结果例如改变颜色 MeshRenderer rendererA colliders[i].GetComponentMeshRenderer(); MeshRenderer rendererB colliders[j].GetComponentMeshRenderer(); if (rendererA ! null) rendererA.material.color isColliding ? Color.red : Color.white; if (rendererB ! null) rendererB.material.color isColliding ? Color.red : Color.white; } } } // 核心SAT碰撞检测函数下一节实现 bool SATCollisionDetection(Vector2[] verticesA, Vector2[] verticesB) { // 待实现 return false; } }框架搭好了接下来就是填充最核心的SATCollisionDetection函数。4. 核心算法实现逐行解析SAT检测代码这是整个项目的灵魂所在。我们将严格按照SAT的步骤用C#实现。4.1 投影与重叠判断辅助函数在实现主函数前我们先写两个关键的辅助函数。// 计算多边形在给定轴上的投影范围最小值和最大值 void ProjectPolygon(Vector2 axis, Vector2[] vertices, out float min, out float max) { // 初始化将第一个顶点的投影值同时赋给min和max min max Vector2.Dot(axis, vertices[0]); // 遍历剩余顶点扩展投影范围 for (int i 1; i vertices.Length; i) { float projection Vector2.Dot(axis, vertices[i]); if (projection min) min projection; if (projection max) max projection; } } // 判断两个区间 [minA, maxA] 和 [minB, maxB] 是否重叠 bool IsOverlapping(float minA, float maxA, float minB, float maxB) { // 判断不重叠的情况更简单一个区间的最大值小于另一个区间的最小值 return !(maxA minB || maxB minA); }Vector2.Dot是点积运算在这里的作用就是计算顶点向量在轴向量上的投影长度。IsOverlapping函数的逻辑是碰撞检测中的常见模式记住它。4.2 实现SAT主检测函数现在我们来填充SATCollisionDetection函数。bool SATCollisionDetection(Vector2[] verticesA, Vector2[] verticesB) { // 1. 检查多边形A的每条边作为分离轴 for (int i 0; i verticesA.Length; i) { // 获取当前边向量 Vector2 currentVertex verticesA[i]; Vector2 nextVertex verticesA[(i 1) % verticesA.Length]; // 循环到第一个顶点 Vector2 edge nextVertex - currentVertex; // 计算该边的法向量单位化 // 法向量垂直于边一个简单的方法是 (-edge.y, edge.x) Vector2 axis new Vector2(-edge.y, edge.x).normalized; // .normalized 是关键确保是单位向量 // 计算两个多边形在该轴上的投影 ProjectPolygon(axis, verticesA, out float minA, out float maxA); ProjectPolygon(axis, verticesB, out float minB, out float maxB); // 判断投影是否重叠 if (!IsOverlapping(minA, maxA, minB, maxB)) { // 发现分离轴肯定没有碰撞 return false; } } // 2. 检查多边形B的每条边作为分离轴 for (int i 0; i verticesB.Length; i) { Vector2 currentVertex verticesB[i]; Vector2 nextVertex verticesB[(i 1) % verticesB.Length]; Vector2 edge nextVertex - currentVertex; Vector2 axis new Vector2(-edge.y, edge.x).normalized; ProjectPolygon(axis, verticesA, out float minA, out float maxA); ProjectPolygon(axis, verticesB, out float minB, out float maxB); if (!IsOverlapping(minA, maxA, minB, maxB)) { return false; } } // 3. 所有轴上的投影都重叠判定为碰撞 return true; }将这段代码放入CollisionManager的SATCollisionDetection函数中。现在你的碰撞检测系统就已经完成了核心逻辑4.3 代码要点与深度解析边的循环(i 1) % vertices.Length这个操作确保了最后一条边的终点是第一个顶点形成了一个闭合的多边形。法向量的计算new Vector2(-edge.y, edge.x)是获得垂直于edge的一个法向量。你也可以用(edge.y, -edge.x)这决定了法向量的“朝向”顺时针还是逆时针但在SAT中我们只关心轴的方向单位化后正反方向其实是同一条轴所以不影响结果。务必进行.normalized否则投影计算的长度单位不一致会导致错误。分离即返回一旦在任何一条轴上发现投影不重叠函数立即返回false这体现了SAT算法的高效性——它不需要检查完所有轴。必须检查两个多边形的所有边只检查A的边是不够的。想象两个细长的矩形呈十字交叉状仅用A的边作为轴可能无法找到分离轴必须也用B的边作为轴来检查。5. 功能扩展获取碰撞深度与碰撞法向量仅仅知道“是否碰撞”对于游戏来说往往不够。我们还需要知道“撞得有多深”以及“从哪个方向撞的”这样才能实现真实的物理反馈比如将物体推开。这就需要用到SAT算法的另一个优势在判定碰撞的同时可以很容易地计算出最小平移向量Minimum Translation Vector, MTV。MTV是一个向量其方向是分离轴的方向即碰撞法向量其长度是将两个物体分开所需的最小距离。5.1 修改检测函数以返回MTV我们需要重构SATCollisionDetection函数让它返回一个包含碰撞布尔值和MTV的结构体。首先定义一个结构体public struct CollisionResult { public bool isColliding; public Vector2 mtv; // Minimum Translation Vector public float penetrationDepth; }然后修改主检测函数CollisionResult SATCollisionDetectionWithMTV(Vector2[] verticesA, Vector2[] verticesB) { CollisionResult result new CollisionResult(); result.isColliding true; result.penetrationDepth float.MaxValue; // 初始化为一个很大的数 Vector2 smallestAxis Vector2.zero; // 记录最小穿透深度的轴 // 检查多边形A的边 for (int i 0; i verticesA.Length; i) { Vector2 currentVertex verticesA[i]; Vector2 nextVertex verticesA[(i 1) % verticesA.Length]; Vector2 edge nextVertex - currentVertex; Vector2 axis new Vector2(-edge.y, edge.x).normalized; ProjectPolygon(axis, verticesA, out float minA, out float maxA); ProjectPolygon(axis, verticesB, out float minB, out float maxB); if (!IsOverlapping(minA, maxA, minB, maxB)) { result.isColliding false; result.mtv Vector2.zero; result.penetrationDepth 0; return result; // 发现分离立即返回 } else { // 计算在当前轴上的穿透深度 float overlap Mathf.Min(maxA, maxB) - Mathf.Max(minA, minB); // 记录最小的穿透深度及其对应的轴 if (overlap result.penetrationDepth) { result.penetrationDepth overlap; smallestAxis axis; } } } // 检查多边形B的边 for (int i 0; i verticesB.Length; i) { Vector2 currentVertex verticesB[i]; Vector2 nextVertex verticesB[(i 1) % verticesB.Length]; Vector2 edge nextVertex - currentVertex; Vector2 axis new Vector2(-edge.y, edge.x).normalized; ProjectPolygon(axis, verticesA, out float minA, out float maxA); ProjectPolygon(axis, verticesB, out float minB, out float maxB); if (!IsOverlapping(minA, maxA, minB, maxB)) { result.isColliding false; result.mtv Vector2.zero; result.penetrationDepth 0; return result; } else { float overlap Mathf.Min(maxA, maxB) - Mathf.Max(minA, minB); if (overlap result.penetrationDepth) { result.penetrationDepth overlap; smallestAxis axis; } } } // 确定MTV的方向需要确保MTV的方向是从A指向B或者反方向通常是将物体A沿MTV方向推开。 // 一个简单的策略是计算从A中心到B中心的向量如果这个向量与smallestAxis的点积为正则MTV方向取反。 Vector2 centerA CalculateCenter(verticesA); Vector2 centerB CalculateCenter(verticesB); Vector2 centerDir centerB - centerA; if (Vector2.Dot(centerDir, smallestAxis) 0) { smallestAxis -smallestAxis; } result.mtv smallestAxis * result.penetrationDepth; return result; } // 辅助函数计算多边形顶点集的中心简单平均 Vector2 CalculateCenter(Vector2[] vertices) { Vector2 center Vector2.zero; foreach (var vertex in vertices) { center vertex; } return center / vertices.Length; }5.2 MTV的应用简单的碰撞响应有了MTV我们就可以实现一个非常基础的碰撞响应——将发生碰撞的物体推开。在CollisionManager的Update函数中修改检测和响应逻辑void Update() { for (int i 0; i colliders.Count; i) { for (int j i 1; j colliders.Count; j) { CollisionResult result SATCollisionDetectionWithMTV( colliders[i].GetWorldVertices(), colliders[j].GetWorldVertices() ); MeshRenderer rendererA colliders[i].GetComponentMeshRenderer(); MeshRenderer rendererB colliders[j].GetComponentMeshRenderer(); if (rendererA ! null) rendererA.material.color result.isColliding ? Color.red : Color.white; if (rendererB ! null) rendererB.material.color result.isColliding ? Color.red : Color.white; // 简单的碰撞响应将物体i沿MTV方向的反方向移动一半深度物体j沿正方向移动一半深度 if (result.isColliding result.mtv ! Vector2.zero) { // 注意这是一个非常简化的响应仅用于演示。真实的物理响应需要考虑质量、速度等。 colliders[i].transform.position - (Vector3)(result.mtv * 0.5f); colliders[j].transform.position (Vector3)(result.mtv * 0.5f); } } } }现在运行场景让两个多边形碰撞你会看到它们不再穿透而是被彼此推开。这就是MTV的力量。6. 性能优化与高级话题我们实现的基础SAT算法时间复杂度是O(n*m)其中n和m是两个多边形的边数。对于边数不多的物体这完全够用。但在需要检测大量物体的复杂场景中我们需要优化。6.1 使用包围盒进行快速预筛选在进行昂贵的SAT计算之前先用一个简单的形状如轴对齐包围盒AABB进行快速排斥测试。bool AABBOverlap(Vector2[] verticesA, Vector2[] verticesB) { // 计算AABB float minAX float.MaxValue, minAY float.MaxValue, maxAX float.MinValue, maxAY float.MinValue; float minBX float.MaxValue, minBY float.MaxValue, maxBX float.MinValue, maxBY float.MinValue; foreach (var v in verticesA) { if (v.x minAX) minAX v.x; if (v.x maxAX) maxAX v.x; if (v.y minAY) minAY v.y; if (v.y maxAY) maxAY v.y; } foreach (var v in verticesB) { if (v.x minBX) minBX v.x; if (v.x maxBX) maxBX v.x; if (v.y minBY) minBY v.y; if (v.y maxBY) maxBY v.y; } // 判断AABB是否重叠 return !(maxAX minBX || maxBX minAX || maxAY minBY || maxBY minAY); }在SATCollisionDetectionWithMTV函数的最开始调用这个函数如果AABB都不重叠直接返回不碰撞。6.2 分离轴缓存与增量计算对于形状不变的静态物体其边的法向量分离轴是固定的可以预先计算并缓存起来避免在每帧检测中重复计算normalized。对于旋转或变形的物体需要更新缓存。但更新缓存计算法向量并单位化的成本仍然远低于在SAT循环中为每个顶点计算点积。6.3 处理凹多边形凸分解如前所述SAT只适用于凸多边形。处理凹多边形的主流方法是凸分解。你可以使用第三方库如Clipper库或算法如耳切法将凹多边形分解为多个凸多边形的集合。然后分别对这些凸多边形进行碰撞检测只要有一个凸部分发生碰撞就认为整个凹多边形发生了碰撞。6.4 与Unity物理引擎的集成我们自制的碰撞检测系统可以独立运行用于游戏逻辑判断如触发事件、伤害判定。但如果需要复杂的物理模拟重力、摩擦力、弹力建议还是将其作为触发器与Unity的Rigidbody2D和内置碰撞器结合使用。例如你可以让CustomPolygonCollider在检测到碰撞时调用OnCollisionEnter等自定义事件通知其他脚本而实际的物理运动和阻挡则由一个简单的BoxCollider2D作为物体的粗略包围盒配合Rigidbody2D来处理。这是一种混合策略兼顾了精度和性能。7. 常见问题与调试技巧实录在实际编码和测试中你肯定会遇到各种奇怪的现象。以下是我踩过的一些坑和解决方法。7.1 问题碰撞检测时有时无不稳定可能原因1浮点数精度问题。在判断投影是否重叠 (IsOverlapping) 时对于刚好擦边的情况浮点误差可能导致误判。解决引入一个微小的容差值epsilon。bool IsOverlapping(float minA, float maxA, float minB, float maxB, float epsilon 0.001f) { return !(maxA minB - epsilon || maxB minA - epsilon); }可能原因2顶点顺序问题。CustomPolygonCollider的vertices列表必须按顺时针或逆时针顺序依次排列不能乱序。乱序的顶点会导致边向量计算错误进而法向量也错误。解决在OnDrawGizmosSelected或编辑时确保顶点顺序正确。可以写一个编辑器工具来验证或重新排序顶点。7.2 问题MTV方向错误物体被“吸”进去而不是推开可能原因MTV方向判断逻辑有误。我们之前通过中心向量点积来判断方向这个方法在大多数情况下有效但在某些极端形状下可能出错。更稳健的方法在计算穿透深度时同时记录下是哪个多边形的哪条边导致了最小穿透。然后根据这条边的方向以及两个多边形的相对位置更精确地确定MTV方向。这需要更复杂的簿记但方向更可靠。7.3 问题性能瓶颈物体多时帧率下降排查使用ProfilerUnity的Profiler是性能分析的神器。查看Update中SATCollisionDetectionWithMTV函数的耗时。检查复杂度确保使用了AABB预筛选这能过滤掉大量明显不碰撞的物体对。减少检测频率不是所有物体都需要每帧检测。对于移动缓慢或静态的物体可以降低检测频率如每2-3帧一次。空间划分当物体数量非常多时成百上千必须引入空间划分算法如四叉树、网格划分等只检测相邻区域的物体这是将O(n²)复杂度降下来的关键。7.4 调试可视化技巧在开发阶段强大的可视化能极大帮助理解。绘制分离轴和投影在SATCollisionDetectionWithMTV函数中可以添加调试代码用Debug.DrawRay绘制出当前检测的轴并用不同颜色线段绘制两个多边形在该轴上的投影范围。这能让你清晰地看到算法是如何工作的以及是在哪条轴上找到了分离或未找到。绘制MTV碰撞发生时用Debug.DrawLine绘制出MTV向量检查其方向和长度是否合理。// 示例在检测函数中绘制轴需在Scene视图查看 Debug.DrawRay(centerA, axis * 5, Color.blue, 0.1f); // 示例碰撞后绘制MTV if(result.isColliding) { Debug.DrawLine(centerA, centerA result.mtv, Color.magenta, 0.1f); }实现一个自定义的、基于二维叉乘和SAT的多边形碰撞检测系统远不止是完成一个功能。它是一次对计算机图形学基础、几何算法和性能思考的深度实践。从理解叉乘的几何意义到实现SAT的投影判断再到优化和问题排查每一步都加深了你对“碰撞”这一游戏基础概念的理解。当你再看到Unity里那些复杂的碰撞体组件时你看到的将不再是一个黑盒而是一套清晰、可掌控的逻辑。这套代码可以作为你工具箱里的一件利器用于实现那些内置碰撞体难以满足的、充满创意的碰撞需求。