分离轴定理(SAT)算法详解：Unity与Cocos Creator 2D凸多边形碰撞检测实战

1. 项目概述为什么是SAT算法在2D游戏开发里碰撞检测是物理交互的基石。无论是角色碰到墙壁、子弹击中敌人还是两个物体发生挤压背后都需要一套高效、准确的检测逻辑。市面上有很多方法比如简单的包围盒AABB检测或者更复杂的像素级检测。但当你需要处理任意凸多边形比如一个旋转的三角形、一个不规则的六边形之间的碰撞时很多简单方法就力不从心了。这时分离轴定理Separating Axis Theorem简称SAT就登场了。它不是什么新潮概念而是图形学和物理引擎领域一个经典且强大的数学工具。我选择用它来做这个实战项目核心原因就一个它能以统一的数学方法精确判断任意两个凸多边形是否相交并且能计算出碰撞的深度和方向。这对于实现真实的物理反馈比如推开物体、计算反弹至关重要。这个项目将带你从零开始理解SAT的原理并用两种最流行的2D游戏引擎——Unity和Cocos Creator——分别实现一套可运行的碰撞检测系统。无论你是Unity的忠实用户还是Cocos Creator的开发者都能从中获得可以直接复用到自己项目里的代码和思路。我们不止步于“检测是否碰撞”还会深入到“如何分离已碰撞的物体”这是实现一个可用物理系统的关键一步。2. SAT算法核心原理拆解要驾驭SAT你得先忘掉“形状”这个概念转而思考“投影”。SAT的核心思想非常直观如果两个凸多边形没有发生碰撞那么必定存在一条直线轴能将它们投影到这条直线上时两个投影区间是分离的没有重叠。2.1 从“分离轴”到“投影重叠”想象一下你用手电筒照向两个物体在墙上留下它们的影子。如果这两个影子在任何角度的手电筒照射下都完全分开那说明这两个物体在真实空间里也肯定是分开的。反之如果存在某个角度它们的影子重叠了那它们就很可能撞在了一起。SAT就是这个思想的数学化。对于凸多边形我们不需要检查所有无穷多个角度。一个关键定理是对于两个凸多边形只需要检查它们各自所有边的法线方向作为潜在的分离轴即可。这是因为如果存在一条分离轴它要么平行于某个多边形的某条边要么平行于两个多边形各一条边的法线之一对于多边形边法线已经足够。所以我们的算法步骤就清晰了为两个多边形A和B收集所有需要检测的轴。通常是A的所有边法线加上B的所有边法线。将两个多边形分别投影到每一条检测轴上。计算两个投影区间一个最小值一个最大值在这条轴上的重叠量。如果在任何一条轴上投影区间没有重叠重叠量 0那么可以立即断定两个多边形没有碰撞。如果在所有检测轴上投影区间都有重叠那么两个多边形发生了碰撞。并且所有重叠量中的最小值就是穿透深度对应的轴就是最小平移向量MTV的方向。注意这里只讨论凸多边形。SAT适用于凸形状因为凸形状的投影区间是连续的。凹多边形需要先分解成多个凸多边形组合来处理。2.2 关键数学概念投影、法线与区间重叠1. 边的法线计算对于一个由点P1(x1, y1)和P2(x2, y2)构成的边边的向量为E P2 - P1 (dx, dy)。在2D中一条边的法线有两个方向向内和向外。我们通常取“左手法线”或“右手法线”并统一即可。一个常用的方法是normal (-dy, dx)或(dy, -dx)。需要确保所有法线都进行归一化长度为1因为后续投影计算需要。2. 点投影到轴上给定一个轴单位向量axis (ax, ay)和一个点P (px, py)点P在轴上的投影标量值可以理解为投影点到原点的带符号距离就是点乘proj px * ax py * ay。 对于一个多边形我们遍历所有顶点计算它们在轴上的投影值找出最大值max和最小值min。这个[min, max]就是多边形在该轴上的投影区间。3. 区间重叠判断假设多边形A的投影区间为[minA, maxA]多边形B的为[minB, maxB]。 它们重叠的条件是maxA minB且maxB minA。 重叠量overlap的计算为overlap Math.min(maxA, maxB) - Math.max(minA, minB)。 如果overlap 0表示重叠。这个overlap值在后面计算穿透深度时会用到。理解了这个数学骨架我们就有了实现SAT的全部理论基础。接下来我们进入实战环节看看在具体的游戏引擎中如何组织代码。3. Unity引擎下的SAT实现详解Unity虽然以3D见长但其2D物理系统Box2D集成已经非常完善。然而理解底层实现和自定义碰撞形状的需求始终存在。我们用原生的C#和Unity的数学库来实现SAT能获得最大的灵活性和学习价值。3.1 数据结构设计与多边形表示在Unity中我们通常用Vector2数组来表示一个多边形。为了封装数据和功能创建一个SATPolygon类是个好主意。using UnityEngine; using System.Collections.Generic; public class SATPolygon { public Vector2[] Vertices { get; private set; } public Vector2[] Normals { get; private set; } // 预计算的法线 public Transform Transform { get; set; } // 关联的变换组件用于处理位置和旋转 public SATPolygon(Vector2[] localVertices, Transform trans) { Transform trans; // 将本地顶点转换为世界坐标顶点 UpdateVertices(localVertices); CalculateNormals(); } // 当物体移动或旋转后需要更新世界坐标下的顶点 public void UpdateVertices(Vector2[] localVertices) { Vertices new Vector2[localVertices.Length]; for (int i 0; i localVertices.Length; i) { Vertices[i] Transform.TransformPoint(localVertices[i]); } } // 计算每条边的单位法线 private void CalculateNormals() { Normals new Vector2[Vertices.Length]; for (int i 0; i Vertices.Length; i) { Vector2 p1 Vertices[i]; Vector2 p2 Vertices[(i 1) % Vertices.Length]; // 循环到第一个点 Vector2 edge p2 - p1; // 获取垂直于边的单位法线。这里使用 ( -edge.y, edge.x )这是一个左手法线。 Normals[i] new Vector2(-edge.y, edge.x).normalized; } } // 获取多边形在当前所有检测轴上的投影极值 public void Project(Vector2 axis, out float min, out float max) { min float.MaxValue; max float.MinValue; foreach (var vertex in Vertices) { float proj Vector2.Dot(vertex, axis); // 投影计算 if (proj min) min proj; if (proj max) max proj; } } }实操心得在CalculateNormals中统一法线方向这里用了左手法线至关重要。不一致的法线方向会导致后续重叠量计算符号错误从而无法正确找到最小分离轴。另外UpdateVertices方法需要在每帧碰撞检测前调用以确保顶点数据是当前帧的世界坐标。对于静态物体这是一个可以优化的点。3.2 核心碰撞检测与响应逻辑有了多边形类我们就可以编写核心的SAT检测函数了。这个函数返回一个包含是否碰撞、穿透深度和最小分离轴信息的结构体。public struct CollisionResult { public bool IsColliding; public float PenetrationDepth; public Vector2 MinimumTranslationVector; // MTV 分离轴 * 穿透深度 } public static class SATCollision { public static CollisionResult CheckCollision(SATPolygon polyA, SATPolygon polyB) { CollisionResult result new CollisionResult(); result.IsColliding true; result.PenetrationDepth float.MaxValue; Vector2 smallestAxis Vector2.zero; // 检查多边形A的所有边法线 if (!CheckAxes(polyA, polyB, ref result.PenetrationDepth, ref smallestAxis)) { result.IsColliding false; return result; } // 检查多边形B的所有边法线 if (!CheckAxes(polyB, polyA, ref result.PenetrationDepth, ref smallestAxis)) { result.IsColliding false; return result; } // 如果所有轴都重叠则发生碰撞 result.MinimumTranslationVector smallestAxis * result.PenetrationDepth; // 确保MTV的方向是从A指向B或反之这取决于你希望推开哪个物体。 // 一个简单的判断计算从A中心到B中心的向量如果与MTV点积为负则反转MTV。 Vector2 centerA GetCenter(polyA.Vertices); Vector2 centerB GetCenter(polyB.Vertices); Vector2 direction centerB - centerA; if (Vector2.Dot(direction, result.MinimumTranslationVector) 0) { result.MinimumTranslationVector -result.MinimumTranslationVector; } return result; } private static bool CheckAxes(SATPolygon polyToCheck, SATPolygon otherPoly, ref float minPenetration, ref Vector2 minAxis) { foreach (var axis in polyToCheck.Normals) { polyToCheck.Project(axis, out float minA, out float maxA); otherPoly.Project(axis, out float minB, out float maxB); // 计算重叠量 float overlap Mathf.Min(maxA, maxB) - Mathf.Max(minA, minB); if (overlap 0) { // 在任何一条轴上发现不重叠立即返回“未碰撞” return false; } // 记录最小的重叠量及对应的轴 if (overlap minPenetration) { minPenetration overlap; minAxis axis; } } return true; // 所有被检查的轴都重叠 } private static Vector2 GetCenter(Vector2[] vertices) { Vector2 center Vector2.zero; foreach (var v in vertices) center v; return center / vertices.Length; } }关键点解析CheckAxes函数这是算法的核心循环。它遍历一组法线来自polyToCheck在每条轴上计算两个多边形的投影并检查重叠。一旦发现overlap 0立即返回false表示找到了分离轴碰撞不成立。这是一种“快速拒绝”策略能提升性能。最小穿透深度在所有重叠的轴中我们记录最小的overlap值。这个值就是两个多边形需要被分开的最小距离即穿透深度。最小平移向量MTV最小穿透深度 * 对应的分离轴单位向量就得到了MTV。这个向量指明了将两个物体分开所需的最短方向和距离。MTV方向的修正最后一步方向修正非常重要。原始的SAT算法找到的轴和深度没有指明应该移动哪个物体。通过计算两中心点的方向向量并与MTV做点积我们可以确保MTV的方向总是将物体从“重叠”状态推向“分离”状态。通常我们固定移动其中一个物体如polyA那么MTV的方向应该使得polyA沿着这个方向移动后能远离polyB。3.3 在Unity中集成与测试创建一个MonoBehaviour脚本来使用我们的SAT系统。我们可以用LineRenderer或Gizmos来可视化多边形和碰撞结果。public class SATTest : MonoBehaviour { public SATPolygon polygonA; public SATPolygon polygonB; public Vector2[] localVertsA; // 在Inspector中编辑的本地顶点 public Vector2[] localVertsB; void Start() { // 假设这个脚本挂在两个不同的GameObject上 polygonA new SATPolygon(localVertsA, transform); // polygonB 需要在另一个物体上初始化 } void Update() { // 更新顶点如果物体移动了 polygonA.UpdateVertices(localVertsA); // polygonB.UpdateVertices(localVertsB); // 执行碰撞检测 CollisionResult result SATCollision.CheckCollision(polygonA, polygonB); if (result.IsColliding) { Debug.Log($碰撞发生穿透深度{result.PenetrationDepth}, MTV: {result.MinimumTranslationVector}); // 可视化MTV Debug.DrawRay(GetCenter(polygonA.Vertices), result.MinimumTranslationVector, Color.red); // 实际响应例如将polygonA的位置加上MTV来分离 // transform.position (Vector3)result.MinimumTranslationVector; } } void OnDrawGizmos() { if (polygonA ! null polygonA.Vertices ! null) { Gizmos.color Color.green; DrawPolygonGizmos(polygonA.Vertices); } // 绘制polygonB... } void DrawPolygonGizmos(Vector2[] verts) { for (int i 0; i verts.Length; i) { Gizmos.DrawLine(verts[i], verts[(i 1) % verts.Length]); } } }注意事项在Update中直接修改transform.position来响应碰撞可能会与Unity自身的物理系统或变换层级产生冲突。在实际项目中这通常由你自己的物理引擎模块或角色控制器来处理。这里演示的是最直接的数学响应。4. Cocos Creator引擎下的SAT实现迁移Cocos Creator使用TypeScript/JavaScript作为开发语言其数学计算主要依赖于Vec2等内置模块。实现逻辑与Unity版本完全一致只是API和语法有所不同。这恰恰体现了SAT算法作为纯数学方案的优越性——与引擎无关。4.1 TypeScript中的多边形类在Cocos Creator中我们通常将组件脚本挂载在节点上。我们创建一个SATPolygon.ts组件。import { _decorator, Component, Vec2, v2, Node } from cc; const { ccclass, property } _decorator; ccclass(SATPolygon) export class SATPolygon extends Component { // 在编辑器中设置的本地顶点坐标相对于节点中心 property([Vec2]) localVertices: Vec2[] []; // 世界坐标下的顶点缓存 private _worldVertices: Vec2[] []; // 边法线缓存 private _normals: Vec2[] []; start() { this.updateGeometry(); } update(deltaTime: number) { // 如果节点可能移动或旋转每帧更新 this.updateGeometry(); } // 更新世界坐标顶点和法线 updateGeometry() { const node this.node; this._worldVertices this.localVertices.map(v { // 将本地坐标转换为世界坐标 const worldPos v.clone(); // 应用节点的旋转和缩放 // 注意这里简化处理假设节点缩放是均匀的且无倾斜。复杂情况需要完整矩阵变换。 const angle node.angle * Math.PI / 180; const cosA Math.cos(angle); const sinA Math.sin(angle); const scale node.scale.x; // 假设均匀缩放 const x v.x * scale * cosA - v.y * scale * sinA node.position.x; const y v.x * scale * sinA v.y * scale * cosA node.position.y; return v2(x, y); }); this.calculateNormals(); } // 计算法线 private calculateNormals() { this._normals []; const count this._worldVertices.length; for (let i 0; i count; i) { const p1 this._worldVertices[i]; const p2 this._worldVertices[(i 1) % count]; const edge p2.subtract(p1); // edge p2 - p1 // 左手法线: (-edge.y, edge.x) const normal v2(-edge.y, edge.x); normal.normalize(); // 单位化 this._normals.push(normal); } } // 获取世界顶点 get worldVertices(): Vec2[] { return this._worldVertices; } // 获取法线 get normals(): Vec2[] { return this._normals; } // 投影到给定轴上返回最小和最大值 project(axis: Vec2, out: { min: number, max: number }) { let min Number.MAX_VALUE; let max -Number.MAX_VALUE; for (const vertex of this._worldVertices) { const proj vertex.dot(axis); // 点乘计算投影 if (proj min) min proj; if (proj max) max proj; } out.min min; out.max max; } // 获取多边形中心近似用于MTV方向修正 getCenter(): Vec2 { const center v2(0, 0); for (const v of this._worldVertices) { center.add(v); } center.multiplyScalar(1 / this._worldVertices.length); return center; } }踩坑提醒Cocos Creator中节点的angle属性是角度制而Math.sin/cos需要弧度制记得转换。另外Vec2的subtract、multiplyScalar等方法可能会修改原对象在计算法线时使用clone()或创建新对象来避免意外修改原始数据是个好习惯。上面的顶点变换是简化版对于非均匀缩放或倾斜需要使用节点的完整世界变换矩阵node.worldMatrix。4.2 碰撞检测管理器与响应我们再创建一个SATCollisionManager.ts组件挂载在场景中的某个管理节点上负责每帧检测指定多边形之间的碰撞。import { _decorator, Component, Vec2, v2, director, Director } from cc; import { SATPolygon } from ./SATPolygon; const { ccclass, property } _decorator; interface CollisionResult { isColliding: boolean; penetrationDepth: number; mtv: Vec2; // Minimum Translation Vector } ccclass(SATCollisionManager) export class SATCollisionManager extends Component { property([SATPolygon]) polygons: SATPolygon[] []; start() { // 可以在这里手动添加多边形引用或通过查找获取 } update(deltaTime: number) { // 简单的两两检测复杂度O(n²)多边形多时需要优化如空间划分 for (let i 0; i this.polygons.length; i) { for (let j i 1; j this.polygons.length; j) { const result this.checkCollision(this.polygons[i], this.polygons[j]); if (result.isColliding) { console.log(多边形 ${i} 与 ${j} 碰撞深度${result.penetrationDepth}); // 可视化MTV const centerA this.polygons[i].getCenter(); const endPos centerA.add(result.mtv); director.getScene()?.getComponentInChildren(/* 你的绘图组件 */); // 实际响应例如移动其中一个节点 // const nodeToMove this.polygons[i].node; // nodeToMove.setPosition(nodeToMove.position.x result.mtv.x, nodeToMove.position.y result.mtv.y); } } } } checkCollision(polyA: SATPolygon, polyB: SATPolygon): CollisionResult { const result: CollisionResult { isColliding: true, penetrationDepth: Number.MAX_VALUE, mtv: v2(0, 0) }; let smallestAxis v2(0, 0); // 检查A的法线 if (!this.checkAxes(polyA, polyB, result, smallestAxis)) { result.isColliding false; return result; } // 检查B的法线 if (!this.checkAxes(polyB, polyA, result, smallestAxis)) { result.isColliding false; return result; } // 所有轴都重叠计算最终MTV result.mtv smallestAxis.multiplyScalar(result.penetrationDepth); // 修正MTV方向使其从A指向B即移动A能离开B const centerA polyA.getCenter(); const centerB polyB.getCenter(); const direction centerB.subtract(centerA); if (direction.dot(result.mtv) 0) { result.mtv result.mtv.negate(); } return result; } private checkAxes(polyToCheck: SATPolygon, otherPoly: SATPolygon, result: CollisionResult, smallestAxis: Vec2): boolean { const projA { min: 0, max: 0 }; const projB { min: 0, max: 0 }; for (const axis of polyToCheck.normals) { polyToCheck.project(axis, projA); otherPoly.project(axis, projB); const overlap Math.min(projA.max, projB.max) - Math.max(projA.min, projB.min); if (overlap 0) { return false; // 找到分离轴 } if (overlap result.penetrationDepth) { result.penetrationDepth overlap; smallestAxis.set(axis); // 记录当前最小重叠轴 } } return true; // 所有被检查轴都重叠 } }性能与优化提示预计算与缓存SATPolygon中的_normals和_worldVertices在顶点数据不变且节点未变换时无需每帧更新。可以在updateGeometry中增加脏检查。避免GC垃圾回收在update循环中频繁创建Vec2或对象如{min, max}会引发GC影响性能。可以考虑复用对象池。上面代码中将投影结果对象projA和projB作为参数传入而不是在函数内部创建就是一种优化。空间划分当场景中有大量多边形时O(n²) 的两两检测是不可接受的。必须引入空间划分算法如四叉树、网格或BVH包围体层次只对可能发生碰撞的物体对进行SAT检测。5. 常见问题、优化与扩展方向在实际应用SAT算法时你肯定会遇到一些典型问题。这里记录了我踩过的一些坑和对应的解决方案。5.1 浮点数精度与容差处理计算机浮点数计算存在精度误差。两个理论上刚好接触的多边形其投影重叠量可能是一个极小的负数如-1e-7。如果严格按照overlap 0判断会被误判为分离。解决方案引入一个微小的容差值epsilon。float epsilon 1e-5f; // 或 0.001f根据你的世界尺度调整 if (overlap epsilon) { // 视为分离 return false; } // 记录重叠量时可以减去epsilon避免“零深度”碰撞 float effectiveOverlap overlap - epsilon; if (effectiveOverlap minPenetration) { minPenetration effectiveOverlap; minAxis axis; }5.2 穿透深度过深与“隧道效应”在高速运动的物体中比如一颗高速子弹可能在一帧内从完全分离直接运动到深度穿透甚至完全穿过另一个物体。这就是“隧道效应”。单纯的每帧静态SAT检测无法捕捉到这种情况。解决方案连续碰撞检测CCD这超出了基础SAT的范围。一种简化思路是不仅检测物体当前帧的位置还检测从上一帧到当前帧的整个运动线段或 swept shape是否与目标物体相交。这需要更复杂的数学通常使用GJK算法或对运动包围体进行SAT检测。限制速度在游戏设计上限制物体的最大速度使其每帧最大移动距离小于其自身尺寸和障碍物尺寸可以很大程度上避免隧道效应。子步采样将一帧的时间分成多个子步sub-step在每个子步内进行碰撞检测和响应。这能提高时间分辨率但会增加计算量。5.3 性能优化实战技巧粗检测先行在进行精确的SAT检测前先用廉价的包围球Sphere或轴向包围盒AABB进行快速拒绝。如果两个物体的包围体都不相交那它们的多边形肯定不相交。法线缓存与更新策略如果多边形形状不变比如一个固定的三角形障碍物其本地法线可以预先计算好无需每帧计算。世界坐标下的法线需要根据旋转进行变换但不必重新计算叉积。SAT检测本身优化提前退出我们的代码已经实现了一旦发现分离轴立即返回。轴排序启发式不按固定顺序检查轴而是根据上一帧的最小分离轴或物体的相对运动方向优先检查最可能成为分离轴的几个方向。这能提高平均检测速度。支持点缓存在投影计算时不必遍历所有顶点找最大/最小值。对于凸多边形在给定轴方向上的最大/最小投影点支持点可以通过“登山算法”或类似方法更快找到尤其是顶点数很多时。5.4 扩展到其他形状SAT算法不仅限于多边形。圆形圆形可以视为拥有无穷多条法线的“形状”。但检测圆形与多边形碰撞时只需检查1) 多边形所有边法线2) 从多边形中心指向圆心的轴。圆形与圆形碰撞更简单只需比较圆心距离与半径之和。胶囊体可以分解为两个半圆和中间一个矩形分别进行SAT检测或者用更专门的算法。复合形状Concave Shapes必须先将凹多边形三角化或分解为多个凸多边形凸分解然后分别对每个凸部分进行SAT检测。实现一个完整的2D物理引擎是庞大的工程但SAT为你提供了处理任意凸形状碰撞的坚实核心。从理解原理到在Unity和Cocos Creator中实现再到处理边界情况和性能考量这个过程本身就是一个极好的游戏开发进阶训练。当你看到自己编写的代码能让两个自定义形状的物体准确地碰撞、推开时那种成就感是使用现成物理引擎无法比拟的。