1. 带洞多边形在2D画图里到底难在哪做过Unity3D 2D画图的朋友大概率都遇到过这个场景用GUI或者GL在屏幕上画一个实心多边形简单顶点数组丢进去三角化提交绘制完事。但一旦这个多边形中间需要挖掉一块——比如做一个环形进度条、一个带镂空的UI遮罩、一张地图上标注某个区域但中间要排除湖泊——事情立刻变得棘手起来。带洞多边形Polygon with Holes的本质是一个外轮廓加上若干个内轮廓内轮廓围住的区域不属于填充范围。听起来像是“画两个多边形然后做布尔减运算”但在实际渲染管线里GPU只认三角形它不理解“洞”这个概念。你必须把带洞多边形转换成一组三角形而且这些三角形不能覆盖到洞的区域。这个问题的核心难点在于三角化。普通的凸多边形三角化用扇形展开就行简单粗暴。凹多边形稍微麻烦一点需要耳切法Ear Clipping。但带洞多边形比凹多边形还要复杂一层外环和内环之间没有直接的顶点连接关系你不能简单地把所有顶点混在一起做耳切那样会得到一堆跨越洞区域的错误三角形。我在实际项目里踩过的坑是这样的最初想偷懒把外环和内环顶点合并成一个数组直接跑耳切算法。结果画出来的图形洞的位置被填上了而且边缘出现了诡异的三角形穿插。后来才想明白耳切算法要求多边形是简单多边形没有自交、没有洞带洞多边形必须先做“桥接”处理把带洞多边形转化成一个等效的简单多边形然后再三角化。这个桥接的思路是找到内环上某个顶点和外环上某个顶点之间的一条可见连线沿着这条线把内环“缝”到外环上形成一个单一的、带一条零宽度通道的简单多边形。这条连线在几何上是一条重复边三角化之后不会产生可见的填充区域但拓扑上它把两个环合并成了一个环。听起来简单做起来有几个关键决策点桥接边怎么选选不好会导致三角化失败或者产生退化三角形。顶点顺序怎么保证外环逆时针、内环顺时针这是约定搞反了洞就变成实心了。数值精度怎么处理浮点数运算下桥接边的可见性判断容易出现误判。这些细节在后面会逐一展开。先说一下整体方案的设计思路。2. 整体方案设计与技术选型拆解2.1 为什么不用Unity自带的Mesh API直接搞定Unity的Mesh类确实可以提交任意三角形列表但它不提供带洞多边形的三角化功能。MeshTriangulator之类的第三方库有但要么依赖Unity的特定版本要么内部实现不够透明出了问题不好排查。而且这个项目是“纯C#版2D画图”意思是核心算法不依赖Unity的渲染管线只输出三角形索引和顶点坐标后续可以用GUI、GL、甚至导出到其他渲染环境。所以方案很明确自己实现一套带洞多边形的三角化流程输入是外环顶点列表和内环顶点列表输出是三角形索引数组。整个流程分三步环的方向规范化、桥接合并、耳切三角化。2.2 方向规范化外逆内顺是铁律在计算几何里多边形的方向绕序决定了它的“正面”朝向。对于带洞多边形约定俗成的规则是外环逆时针CCW内环顺时针CW。这样在计算有符号面积时外环面积为正内环面积为负总面积等于外环面积减去内环面积。如果你拿到的顶点数据方向不对需要先做一次反转。判断方向的方法很简单计算多边形的有符号面积Shoelace公式面积为正说明是逆时针为负说明是顺时针。float SignedArea(ListVector2 polygon) { float area 0f; int n polygon.Count; for (int i 0; i n; i) { Vector2 p0 polygon[i]; Vector2 p1 polygon[(i 1) % n]; area (p1.x - p0.x) * (p1.y p0.y); } return area * 0.5f; }注意这里用的是梯形法而不是叉积法两种方法等价但梯形法在数值上更稳定一些。如果算出来外环面积是负的就Reverse一下内环面积是正的也Reverse一下。这里有个容易忽略的点如果你的内环顶点是逆时针的反转之后变成顺时针但反转操作会改变顶点的起始索引。后续桥接时需要记录原始索引的映射关系否则洞的边界会对不上。2.3 桥接策略找一条“看不见”的缝桥接的核心是找到一对顶点一个在外环一个在内环使得它们之间的线段完全位于多边形内部且不与任何边相交。这条线段就是“桥”它把内环和外环连成一个整体。最朴素的找法是遍历所有外环顶点和内环顶点的组合对每一对做可见性测试。但这样复杂度是O(n*m)对于顶点数较多的多边形性能堪忧。实际项目中我通常用“最右顶点法”来快速定位候选桥接点。具体做法找到内环中X坐标最大的顶点如果有多个取Y最小的然后从这个顶点向右发射一条射线找到与外环的第一个交点所在的边该边的某个端点就是桥接目标。这个方法的几何直觉是内环最右顶点向右看第一个挡住它的外环边就是“最近的墙”从这面墙上找一个顶点连过去大概率是可见的。但“大概率”不够还需要做精确的可见性验证。验证方法是检查桥接线段是否与任何外环边或内环边相交不包括共享端点的边。如果相交就换一个候选顶点重试。bool IsBridgeValid(Vector2 innerVertex, Vector2 outerVertex, ListVector2 outer, ListVector2 inner) { // 检查与外环边的相交 for (int i 0; i outer.Count; i) { Vector2 a outer[i]; Vector2 b outer[(i 1) % outer.Count]; if (a outerVertex || b outerVertex) continue; if (SegmentsIntersect(innerVertex, outerVertex, a, b)) return false; } // 检查与内环边的相交 for (int i 0; i inner.Count; i) { Vector2 a inner[i]; Vector2 b inner[(i 1) % inner.Count]; if (a innerVertex || b innerVertex) continue; if (SegmentsIntersect(innerVertex, outerVertex, a, b)) return false; } return true; }这个验证过程是桥接算法里最耗时的部分但它是保证正确性的关键。我试过跳过验证直接连结果在某些凹形外环的情况下桥接边穿到了多边形外面三角化出来的图形完全不对。2.4 耳切三角化最后一步的经典算法桥接完成后我们得到了一个单一的简单多边形顶点数等于外环加内环再加2因为桥接边两端各重复一次。对这个简单多边形跑耳切算法即可。耳切算法的逻辑是每次找到一个“耳”——即一个凸顶点且其相邻两个顶点形成的三角形不包含其他任何顶点——把这个耳切掉记录三角形然后继续。直到剩下三个顶点最后一个三角形也记录下来。Listint EarClip(ListVector2 polygon) { Listint triangles new Listint(); Listint indices new Listint(); for (int i 0; i polygon.Count; i) indices.Add(i); int guard 0; while (indices.Count 3 guard 10000) { bool earFound false; for (int i 0; i indices.Count; i) { int prev indices[(i - 1 indices.Count) % indices.Count]; int curr indices[i]; int next indices[(i 1) % indices.Count]; if (IsEar(polygon, indices, prev, curr, next)) { triangles.Add(prev); triangles.Add(curr); triangles.Add(next); indices.RemoveAt(i); earFound true; break; } } if (!earFound) break; // 防止死循环 guard; } if (indices.Count 3) { triangles.Add(indices[0]); triangles.Add(indices[1]); triangles.Add(indices[2]); } return triangles; }IsEar的判断包含两个条件顶点是凸的叉积方向正确且三角形内部不包含任何其他顶点。第二个条件的朴素实现是遍历所有剩余顶点做点在三角形内的测试复杂度O(n)整体耳切复杂度O(n^2)。对于2D画图场景顶点数通常不会太大几十到几百这个复杂度完全可以接受。3. 核心细节解析与实操要点3.1 桥接边的顶点插入顺序桥接的时候顶点的插入顺序非常关键。假设外环顶点列表是outer内环是inner找到的桥接对是outer[i]和inner[j]。合并后的顶点列表应该是从outer[i]开始沿着外环走到outer[i]完整一圈然后跳到inner[j]沿着内环走到inner[j]完整一圈再跳回outer[i]。用代码表示就是ListVector2 merged new ListVector2(); // 外环从i开始 for (int k 0; k outer.Count; k) merged.Add(outer[(i k) % outer.Count]); // 内环从j开始 for (int k 0; k inner.Count; k) merged.Add(inner[(j k) % inner.Count]); // 回到外环起点闭合 merged.Add(outer[i]);注意最后又加了一个outer[i]这样merged列表的首尾都是outer[i]形成了一个闭合的简单多边形。这个重复顶点在耳切时会被正确处理因为耳切算法处理的是索引列表重复顶点在几何上重合但索引不同不会造成问题。这里有个细节如果内环有多个多个洞需要依次桥接。每桥接一个洞合并后的多边形就多一段“缝”。多个洞的情况下桥接顺序会影响后续桥接的可见性判断因为之前的桥接边也变成了多边形的一部分。我的做法是按洞的X坐标从右到左依次桥接这样每次桥接时右侧的洞已经合并进来了左侧的洞向右看时不会穿过已合并的区域。3.2 浮点数精度问题的处理计算几何里最让人头疼的就是浮点数精度。两个理论上相等的点在浮点运算下可能差个1e-7导致线段相交判断出现误判。我的经验是所有涉及相等判断的地方都用一个epsilon阈值。比如判断两个点是否相同不用而是用距离小于1e-5。判断叉积是否为零不用0而是用绝对值小于1e-6。const float EPS 1e-5f; bool PointsEqual(Vector2 a, Vector2 b) { return (a - b).sqrMagnitude EPS * EPS; } float Cross(Vector2 a, Vector2 b, Vector2 c) { return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x); } bool IsConvex(Vector2 prev, Vector2 curr, Vector2 next) { return Cross(prev, curr, next) EPS; }在线段相交判断里也要用epsilon来处理“端点恰好落在另一条线段上”的情况。这种情况在桥接验证时经常出现因为桥接边的端点就是多边形的顶点它必然与相邻边共享端点。如果不排除共享端点的情况所有桥接都会被判定为无效。3.3 退化三角形的过滤耳切过程中可能产生面积接近零的退化三角形这些三角形在渲染时不可见但会浪费顶点索引空间还可能引起某些渲染管线的警告。我通常会在输出最终三角形列表前做一次过滤Listint FilterDegenerate(ListVector2 vertices, Listint triangles) { Listint result new Listint(); for (int i 0; i triangles.Count; i 3) { Vector2 a vertices[triangles[i]]; Vector2 b vertices[triangles[i 1]]; Vector2 c vertices[triangles[i 2]]; float area Mathf.Abs(Cross(a, b, c)) * 0.5f; if (area EPS) { result.Add(triangles[i]); result.Add(triangles[i 1]); result.Add(triangles[i 2]); } } return result; }这个过滤在桥接边附近特别重要因为桥接边是一条重复边它两侧的三角形可能退化成一条线。3.4 与MVVM框架的集成方式这个项目是“基于Unity3D GUI的轻量级MVVM框架”的一部分所以带洞多边形的处理需要以MVVM的方式暴露给上层。我的做法是定义一个PolygonViewModel它持有外环和内环的顶点数据用ObservableCollection或者自定义的绑定列表当数据变化时触发重新三角化输出的三角形列表通过绑定更新到View层的MeshRenderer或者GUI绘制逻辑。public class PolygonViewModel : ViewModelBase { private ListVector2 _outerRing; private ListVector2 _innerRings; private Listint _triangles; public ListVector2 OuterRing { get _outerRing; set { _outerRing value; Rebuild(); OnPropertyChanged(); } } public Listint Triangles { get _triangles; private set { _triangles value; OnPropertyChanged(); } } private void Rebuild() { var processor new PolygonWithHolesProcessor(); Triangles processor.Triangulate(_outerRing, _innerRings); } }这样View层只需要绑定Triangles属性拿到三角形索引后直接提交给绘制接口。数据驱动的更新方式让整个流程很清晰改顶点数据自动重新三角化自动重绘。4. 完整实操流程与关键环节实现4.1 从零搭建带洞多边形处理器的步骤先定义数据结构和接口。我习惯把处理器设计成无状态的每次调用传入外环和内环返回三角形索引列表。这样方便单元测试也方便在MVVM里做缓存。public class PolygonWithHolesProcessor { public Listint Triangulate(ListVector2 outerRing, ListListVector2 innerRings) { // Step 1: 方向规范化 var outer EnsureCounterClockwise(outerRing); var inners innerRings.Select(EnsureClockwise).ToList(); // Step 2: 依次桥接每个内环 var merged new ListVector2(outer); foreach (var inner in inners) { merged BridgeHole(merged, inner); } // Step 3: 耳切三角化 var triangles EarClip(merged); // Step 4: 过滤退化三角形 return FilterDegenerate(merged, triangles); } }这个骨架很清晰每一步的职责单一。下面展开每一步的实现细节。4.2 方向规范化的实现与验证EnsureCounterClockwise和EnsureClockwise的实现ListVector2 EnsureCounterClockwise(ListVector2 polygon) { if (SignedArea(polygon) 0) { var reversed new ListVector2(polygon); reversed.Reverse(); return reversed; } return new ListVector2(polygon); } ListVector2 EnsureClockwise(ListVector2 polygon) { if (SignedArea(polygon) 0) { var reversed new ListVector2(polygon); reversed.Reverse(); return reversed; } return new ListVector2(polygon); }验证方法拿一个正方形外环逆时针和一个正方形内环顺时针跑一遍看输出的三角形是否只覆盖了环形区域。我通常会在Scene视图里用Gizmos画出三角形肉眼确认洞的位置没有被填充。4.3 桥接算法的完整实现桥接是整个过程里最复杂的部分。我的实现分两步先找候选桥接点再验证可见性。ListVector2 BridgeHole(ListVector2 outer, ListVector2 inner) { // 找内环最右顶点 int innerIdx 0; for (int i 1; i inner.Count; i) { if (inner[i].x inner[innerIdx].x || (Mathf.Abs(inner[i].x - inner[innerIdx].x) EPS inner[i].y inner[innerIdx].y)) { innerIdx i; } } // 找外环上可见的桥接点 int outerIdx -1; for (int i 0; i outer.Count; i) { if (IsBridgeValid(inner[innerIdx], outer[i], outer, inner)) { outerIdx i; break; } } if (outerIdx -1) { Debug.LogError(找不到有效的桥接点); return outer; } // 构建合并后的顶点列表 var merged new ListVector2(); for (int k 0; k outer.Count; k) merged.Add(outer[(outerIdx k) % outer.Count]); for (int k 0; k inner.Count; k) merged.Add(inner[(innerIdx k) % inner.Count]); merged.Add(outer[outerIdx]); return merged; }这个实现里IsBridgeValid的复杂度是O(nm)外层循环最多n次所以桥接的总复杂度是O(n*(nm))。对于几百个顶点的多边形这个开销在毫秒级完全可以接受。实测经验如果内环的最右顶点恰好与外环的某个顶点重合比如洞的边界碰到了外边界桥接会失败。这种情况需要特殊处理通常的做法是把洞的边界稍微向内缩一点或者把重合的顶点合并。我在项目里遇到过一次是因为地图数据里湖泊的边界和陆地边界共享了一个顶点后来在数据预处理阶段做了顶点去重。4.4 耳切三角化的性能优化朴素的耳切算法在每次找耳时都要遍历所有剩余顶点做点在三角形内的测试复杂度O(n^2)。对于顶点数超过500的多边形这个开销开始变得明显。我做过一个测试1000个顶点的带洞多边形朴素耳切耗时约15ms在60帧的游戏里占了一帧的四分之一有点危险。优化思路是维护一个“凸顶点候选列表”每次切掉一个耳后只更新受影响的相邻顶点。这样大部分情况下不需要遍历所有顶点。但实现复杂度会上升不少对于2D画图场景我通常先用朴素版本如果性能不达标再优化。另一个优化是空间加速用网格或者四叉树来加速“点在三角形内”的测试。但同样对于几百个顶点的场景收益不明显。我的建议是顶点数小于300用朴素耳切大于300考虑优化。实际项目中2D画图的带洞多边形很少超过200个顶点所以朴素版本够用。4.5 在Unity GUI中绘制三角形列表三角化输出的三角形索引列表最终要提交给绘制接口。如果用Unity的GL可以这样画void OnRenderObject() { material.SetPass(0); GL.Begin(GL.TRIANGLES); GL.Color(fillColor); foreach (int idx in triangles) { GL.Vertex(vertices[idx]); } GL.End(); }如果用GUI可以用GL在OnGUI里画或者用MeshRenderer加一个动态Mesh。我倾向于用GL因为不需要创建GameObject适合轻量级的2D画图需求。注意GL.Begin/End必须在OnRenderObject或OnPostRender里调用不能在Update里直接调。另外GL绘制的坐标是屏幕空间还是世界空间取决于当前的相机矩阵需要根据项目设置调整。5. 常见问题与排查技巧实录5.1 洞被填充了怎么办这是最常见的问题。现象是明明传入了内环但画出来的图形洞的位置被填上了。原因通常是内环的方向不对。如果内环是逆时针的有符号面积为正在桥接和耳切过程中会被当作外环的一部分洞就消失了。排查方法在桥接之前打印外环和内环的有符号面积确认外环为正、内环为负。如果不是检查EnsureClockwise是否被正确调用。另一个可能的原因是桥接失败merged列表实际上只包含了外环。检查BridgeHole的返回值如果outerIdx为-1说明没找到有效桥接点需要检查IsBridgeValid的逻辑。5.2 三角形穿过了洞的边界现象是洞的位置虽然没有被完全填充但有一些细长的三角形跨越了洞的区域。这通常是桥接边选择不当导致的。桥接边虽然满足“不与任何边相交”但它可能穿过了洞的内部区域。等等桥接边的一个端点在内环上另一个在外环上如果它穿过了洞的内部那它必然与内环的某条边相交因为洞的内部被内环包围。所以只要IsBridgeValid正确排除了与内环边的相交就不会出现这个问题。如果出现了检查IsBridgeValid里对内环边的遍历是否包含了所有边特别是桥接端点相邻的两条边是否被正确排除。5.3 耳切陷入死循环耳切算法在找不到耳的情况下会死循环。我加了一个guard计数器超过一定次数就跳出。但跳出意味着三角化不完整需要排查为什么找不到耳。常见原因多边形不是简单多边形有自交或者桥接后的多边形有重复顶点导致IsEar判断异常。排查方法是把merged列表的顶点画出来肉眼检查是否有自交或重合。还有一种情况是浮点数精度导致IsConvex判断错误一个实际上是凸的顶点被判定为凹。这时候需要调整EPS阈值或者改用更稳定的叉积计算方式。5.4 多个洞的桥接顺序问题多个洞的情况下桥接顺序会影响结果。我试过随机顺序桥接有时候能成功有时候失败。后来固定为按洞的最右顶点X坐标从大到小排序先桥接最右边的洞再桥接左边的。这样每次桥接时右侧的洞已经合并到外环里了左侧的洞向右看时不会穿过已合并的区域。如果洞之间有重叠这在几何上是不合法的带洞多边形桥接必然失败。需要在数据预处理阶段检测洞之间的重叠并报错。5.5 性能问题的排查思路如果三角化耗时超过预期按以下顺序排查排查项可能原因解决方法顶点数顶点过多导致O(n^2)耳切变慢简化多边形或改用优化版耳切桥接验证每次桥接都遍历所有边用空间索引加速相交测试重复三角化数据变化频繁触发重建加缓存只有顶点数据真正变化时才重建GC压力每次重建都分配新列表用对象池复用List我在项目里遇到过一次性能问题每帧都在重建三角形列表因为ViewModel的属性绑定触发了多次OnPropertyChanged。后来改成批量更新一次数据变化只触发一次重建帧率立刻恢复正常。5.6 与MVVM绑定的常见坑MVVM框架里ViewModel的属性变化会触发View更新。如果Triangles属性每次重建都赋一个新列表绑定系统会认为数据变了触发重绘。这本身没问题但如果重建频率过高比如每帧就会造成性能问题。我的做法是在ViewModel里加一个脏标记只有顶点数据真正变化时才重建。另外Triangles属性用ObservableCollection或者自定义的绑定列表避免每次赋值都触发完整的绑定刷新。还有一个坑是线程安全。如果三角化在后台线程执行而View在主线程读取Triangles需要加锁或者用线程安全的集合。我通常把三角化放在主线程因为对于2D画图场景顶点数不多耗时可以忽略。6. 一些实战中的经验补充带洞多边形的处理在2D画图里算是一个中等难度的计算几何问题。说难不难因为算法都是现成的说简单也不简单因为细节很多每个细节处理不好都会导致渲染结果不对。我个人的经验是先把方向规范化做对这是基础。然后桥接算法要写扎实可见性验证不能省。耳切算法可以用最朴素的版本性能不够再优化。最后一定要写单元测试用几个典型的带洞多边形一个洞、多个洞、凹外环、凸内环、凹内环验证输出三角形的正确性。验证方法很简单把所有三角形的面积加起来应该等于外环面积减去所有内环面积。如果不等说明三角化有问题。这个面积校验我每次改完代码都会跑一遍帮我抓到了好几次桥接边的bug。另外如果你用的是Unity的Vector2注意它的精度是float对于坐标值很大的多边形比如地图坐标浮点误差会放大。这种情况下可以考虑用double做中间计算最后再转回float。这个带洞多边形的处理器后来被我抽成了一个独立的C#库不依赖Unity可以在任何.NET环境里跑。MVVM框架那边只需要引用这个库把顶点数据传进来拿三角形列表出去。解耦之后测试和复用都方便了很多。