1. 为什么需要凹多边形切割在游戏开发或者物理引擎实现中碰撞检测是个绕不开的话题。你可能已经听说过分离轴算法SAT这个算法在处理凸多边形碰撞时效率很高但有个前提条件它只能处理凸多边形。现实情况是我们遇到的图形往往都是凹多边形比如一个凹字形的物体或者更复杂的星形图案。这里有个很实际的问题如果直接把分离轴算法用在凹多边形上会得到错误的碰撞结果。我刚开始做游戏时就踩过这个坑明明两个物体看起来没有碰撞系统却判定它们撞在了一起。后来才发现原来是因为凹多边形的某些特性导致分离轴算法失效。那么解决方案就很明确了先把凹多边形切割成多个凸多边形再对每个凸多边形进行碰撞检测。听起来简单但具体怎么切这就是我们今天要重点讨论的向量法实现方案。2. 向量法基础判断凹点2.1 多边形顶点顺序约定首先我们需要约定多边形的顶点存储顺序。在Unity等大多数游戏引擎中我们采用逆时针顺序存储顶点。这个约定很重要因为后续的所有计算都依赖于这个顺序。判断一个点是不是凹点本质上就是看这个点处的内角是否大于180度。这里就要用到向量的叉乘了。我记得刚开始学这个的时候花了好几个小时才想明白叉乘的方向判断。2.2 叉乘判断凹点具体操作是这样的对于多边形中的每个顶点我们取它前一条边和后一条边做叉乘。在左手坐标系中Unity就是左手系如果叉乘结果指向屏幕外侧说明这个点的内角大于180度就是个凹点。用代码表示大概是这样Vector3 cur polygon[i]; Vector3 prev polygon[(i-1 count)%count]; Vector3 next polygon[(i1)%count]; if(Vector3.Cross(cur-prev, next-cur).z 0) { // 这是个凹点 }在实际项目中我建议把这个判断封装成一个独立函数因为后面会反复用到。第一次实现时我犯了个错误没有处理好顶点索引的循环问题导致数组越界调试了好久才发现。3. 边延长与相交测试3.1 延长凹点的起始边找到凹点后我们需要延长这个凹点的起始边。举个例子假设我们有个五边形ABCDE发现点C是凹点那么就要延长边BC。这里的关键问题是延长线会和哪条边相交我们需要遍历多边形的其他边找出与延长线相交的那条边。但要注意跳过一些特殊情况跳过当前边BC本身跳过下一条边CD因为C是凹点延长线不可能与CD相交3.2 相交测试的实现相交测试是整套算法中最容易出错的部分。我最初用的是简单的叉乘法后来发现有些边界情况处理不了。比如当延长线正好穿过某个顶点时就需要特殊处理。正确的做法是bool IsIntersect(Vector3 a1, Vector3 a2, Vector3 b1, Vector3 b2) { float cross1 Vector3.Cross(b1-a1, a2-a1).z; float cross2 Vector3.Cross(b2-a1, a2-a1).z; if(cross1 * cross2 0) return false; float cross3 Vector3.Cross(a1-b1, b2-b1).z; float cross4 Vector3.Cross(a2-b1, b2-b1).z; return cross3 * cross4 0; }这个函数可以正确处理大多数情况但要注意处理延长线穿过顶点的情况这时候需要额外判断叉乘结果是否为零。4. 求交点与多边形分割4.1 直线交点计算找到相交的边后我们需要计算延长线与这条边的交点。这里有两种常用方法直线方程法参数方程法我更喜欢用直线方程法虽然需要处理斜率不存在的特殊情况但理解起来更直观。具体实现时一定要记得处理垂直线斜率无限大的情况这是最常见的bug来源。Vector3 GetIntersection(Vector3 p1, Vector3 p2, Vector3 p3, Vector3 p4) { // 处理垂直线情况 if(Mathf.Approximately(p1.x, p2.x)) { float m (p4.y - p3.y)/(p4.x - p3.x); float b p3.y - m*p3.x; return new Vector3(p1.x, m*p1.x b); } if(Mathf.Approximately(p3.x, p4.x)) { float m (p2.y - p1.y)/(p2.x - p1.x); float b p1.y - m*p1.x; return new Vector3(p3.x, m*p3.x b); } // 一般情况 float m1 (p2.y - p1.y)/(p2.x - p1.x); float b1 p1.y - m1*p1.x; float m2 (p4.y - p3.y)/(p4.x - p3.x); float b2 p3.y - m2*p3.x; float x (b2 - b1)/(m1 - m2); float y m1*x b1; return new Vector3(x, y); }4.2 多边形分割策略求得交点后我们需要根据交点位置将原多边形分割成两个新多边形。这里有两种主要情况延长线与后续的边相交比如延长BC与DE相交延长线与前面的边相交比如延长BC与EA相交每种情况的分割方式略有不同。我建议在实现时先画几个具体的例子把顶点索引的变化规律搞清楚。第一次实现时我就在这里搞反了顶点顺序导致分割后的多边形顶点顺序错乱。5. 完整算法与优化5.1 广度优先分割流程为了完整处理凹多边形我们需要使用广度优先搜索BFS的策略初始化一个队列放入原始凹多边形从队列取出一个多边形尝试找到凹点并进行分割如果分割成功将得到的新多边形放回队列如果无法分割已经是凸多边形加入结果列表重复直到队列为空这个流程保证了我们会处理所有可能的凹多边形直到全部变成凸多边形为止。5.2 特殊情况的处理在实际项目中有几个特殊情况需要特别注意延长线正好穿过顶点这时候需要修改分割逻辑确保顶点不会被重复添加共线边当多边形有共线顶点时可能会影响凹点判断浮点数精度问题在比较叉乘结果时建议使用Mathf.Approximately而不是直接比较我在项目中就遇到过因为浮点精度导致的bug两个理论上应该相交的边因为精度问题被判定为不相交导致整个算法失效。后来通过增加一个很小的epsilon值比较解决了这个问题。6. 性能考量与实现建议6.1 算法复杂度分析这个算法的时间复杂度取决于凹多边形的复杂程度。最坏情况下一个n边形可能需要被分割成n-2个凸多边形。每次分割都需要遍历所有边进行相交测试所以整体复杂度大概是O(n³)。在实际应用中我发现对于不太复杂的凹多边形比如只有1-2个凹点性能还是可以接受的。但对于特别复杂的形状可能需要考虑其他优化方法比如预先计算凸包等。6.2 实现优化技巧经过几个项目的实践我总结出几个优化建议缓存中间结果比如已经确认是凸多边形的部分可以缓存起来尽早终止如果发现某个多边形已经是凸的就立即停止处理空间分区对于场景中有大量多边形的情况可以先做空间分区减少需要检测的多边形数量并行处理现代CPU多核心可以考虑把不同多边形的处理分配到不同线程在移动设备上实现时要特别注意内存分配问题。频繁创建新的多边形列表会导致GC压力最好使用对象池来管理内存。7. 实际应用案例7.1 在Unity中的实现在Unity中我们可以把这个算法封装成一个静态类方便各个组件调用。下面是一个简化版的调用示例public class CollisionHelper { public static ListListVector2 SplitConcavePolygon(ListVector2 concavePoly) { // 实现我们前面讨论的算法 } } // 使用示例 ListVector2 originalPoly new ListVector2{...}; var convexPolys CollisionHelper.SplitConcavePolygon(originalPoly); foreach(var poly in convexPolys) { // 对每个凸多边形进行碰撞检测 }7.2 与其他系统的集成切割后的凸多边形可以很方便地用于各种物理引擎。比如在Unity中可以用MeshCollider为每个凸多边形创建碰撞体可以用Raycast对每个凸多边形单独检测可以用于2D物理系统的碰撞检测我在一个塔防游戏中就用到了这个技术处理那些不规则的防御工事形状。刚开始尝试用多个简单碰撞体拼凑效果很差。改用这个算法后碰撞检测既准确又高效。