1. 项目概述从“耳切法”到Cocos引擎的图形渲染如果你在Cocos Creator 3.x项目中处理过复杂的2D多边形碰撞体或者尝试过将不规则图形渲染到网格上那么你很可能已经间接用到了一个名为earcut.ts的算法模块尽管你可能从未直接调用过它。这个隐藏在引擎深处的工具是解决“多边形三角剖分”这一经典计算几何问题的关键。简单来说它的任务是把一个任意形状的、可能带孔洞的平面多边形分解成一系列互不重叠的三角形。这个看似基础的操作却是现代图形渲染、物理模拟、地理信息系统GIS乃至游戏开发的基石——因为GPU只认识三角形。earcut.ts实现的核心算法就是标题中提到的“耳切法”Ear Cutting。这个名字非常形象想象一个多边形找到一个凸出的“耳朵”由连续三个顶点构成且中间顶点是凸点形成的三角形完全位于多边形内部然后“咔嚓”一刀把这个“耳朵”三角形切下来。重复这个过程直到整个多边形被完全三角化。Cocos3引擎选择将此算法集成到源码中正是看中了它在处理复杂UI图形、精灵遮罩、2D物理形状生成等场景下的高效与稳定。今天我们就深入Cocos3的源码拆解earcut.ts的实现不仅弄懂它“怎么用”更要搞明白它“为什么这么设计”以及在实际项目中我们可能遇到的“坑”和优化技巧。2. 核心需求与算法选型为什么是耳切法在深入代码之前我们必须先理解Cocos引擎为何需要这样一个三角剖分算法以及在众多算法中为何独独青睐耳切法。2.1 图形渲染的底层需求一切皆为三角形无论是WebGL、OpenGL还是Vulkan现代图形API渲染复杂形状的基础单元都是三角形。一个矩形可以用两个三角形表示一个圆形可以用许多个细小的三角形拼接扇形化来近似。但对于一个任意的、用户自定义的多边形比如一个星形、一个文字轮廓、一个不规则的地图区块引擎必须能自动将其转换为三角形网格Mesh才能交给GPU渲染。这就是earcut.ts存在的根本原因。在Cocos中cc.MeshRenderer、cc.Graphics组件在绘制非矩形填充图形时底层都可能调用到三角剖分算法。2.2 算法选型权衡耳切法 vs. 其他常见的多边形三角剖分算法还有“单调多边形剖分”、“Delaunay三角剖分”等。Cocos选择耳切法主要基于以下几点工程考量概念简单实现相对直观耳切法的核心逻辑易于理解和调试这对于需要长期维护的引擎代码至关重要。其时间复杂度为O(n²)在顶点数不多通常UI图形顶点数在几十到几百个的场景下完全可接受。对输入多边形要求宽松一个健壮的耳切法实现如Cocos采用的可以处理带孔洞的多边形、自相交多边形虽然结果可能未定义以及顶点顺序为顺时针或逆时针的多边形。这种鲁棒性非常适合处理来自美术资源或用户输入的、质量参差不齐的图形数据。结果确定性对于相同的输入顶点序列耳切法通常会产生相同的三角剖分结果除非有退化情况如共线点。这在需要结果可重现的场景下很重要比如服务器和客户端需要同步渲染逻辑时。内存开销可控算法主要操作的是顶点索引链表不需要构建复杂的空间数据结构如Delaunay三角化需要的三角网内存占用相对较小。当然耳切法也有其局限性。最坏情况下的O(n²)复杂度意味着对于顶点数上千的极端复杂多边形性能会下降。此外它生成的三角形网格在“质量”如避免出现过于狭长的三角形上可能不如Delaunay三角化。但对于Cocos引擎主要的应用场景——游戏UI、2D精灵、轻量级地图——耳切法在简单性、鲁棒性和性能之间取得了最佳平衡。注意Cocos3中的earcut.ts并非一个全新的发明它很大程度上借鉴并优化了Mapbox团队开源的earcutJavaScript库该库被广泛用于GeoJSON数据渲染。Cocos团队对其进行了TypeScript化、模块化和性能微调以更好地融入引擎的模块体系。3. 源码深度解析earcut.ts的实现拆解让我们打开Cocos3引擎的源码通常位于cocos/core/geometry/earcut.ts逐层剖析其实现。为了便于理解我会将关键代码逻辑转化为伪代码和示意图并解释每一步的意图。3.1 数据结构设计双链环与节点对象算法的核心是操作一个顶点索引的环形双向链表。每个“节点”不仅存储顶点索引还维护指向前驱和后继节点的指针以及一些计算好的几何属性。// 简化后的节点结构示意 class Node { i: number; // 顶点在原始数组中的索引 x: number; // 顶点X坐标缓存避免重复查找数组 y: number; // 顶点Y坐标 prev: Node | null; next: Node | null; // 以下属性会在算法过程中计算和缓存 isConvex?: boolean; // 是否为凸点 isEar?: boolean; // 是否构成“耳朵” }为什么用环形双向链表而不是简单的数组因为“切耳朵”是一个频繁的删除操作。当识别出一个耳朵三角形并切除后需要将中间顶点从多边形中移除。在双向链表中移除一个节点只需修改其前驱和后继的指针是O(1)操作。如果使用数组每次移除都需要移动大量元素效率极低。初始化时算法会将输入的顶点数组以及可选的孔洞起始索引数组转换成这样一个链表环。对于带孔洞的多边形算法会先通过“桥接”的方式在内外环之间添加一对重合的“桥”顶点将带孔多边形转化为一个“退化”的单环多边形然后再进行三角剖分。这个桥接逻辑是算法能处理孔洞的关键。3.2 核心流程耳切算法的三步循环算法的主体是一个循环直到链表中的节点数小于等于3即只剩下一个三角形。每次循环包含三个关键步骤步骤一计算每个节点的几何属性凸点/凹点判断遍历链表对于每个由三个连续节点(prev, node, next)构成的角计算其“转向”。利用向量叉积cross product(node.x - prev.x) * (next.y - node.y) - (node.y - prev.y) * (next.x - node.x)如果结果大于0假设Y轴向下顺时针为正向则node是凸点否则是凹点。同时如果这个角的角度非常小接近0或180度该节点可能被视为“共线点”并在预处理中被移除以提高数值稳定性。步骤二识别“耳朵”对于一个凸点node需要判断三角形(prev, node, next)是否是多边形的一个“耳朵”。条件是该三角形内部不包含任何其他多边形的顶点。 这是一个几何点是否在三角形内的问题。朴素的实现需要遍历所有其他顶点进行判断复杂度为O(n)。earcut.ts对此进行了优化首先只检查那些位于该三角形外接矩形边界框内的顶点快速排除大量明显不在内部的点。对于边界框内的点再进行精确的“点是否在三角形内”测试通常使用重心坐标法或同侧法。更进一步的优化是利用多边形是简单的这一特性只检查与当前凸点node相邻的局部顶点。但为了鲁棒性处理可能自相交的输入Cocos的实现可能仍采用相对保守的检查。如果一个凸点通过了“耳朵”测试则标记node.isEar true。步骤三切除耳朵并输出三角形遍历链表找到第一个被标记为耳朵的节点ear。将三角形(ear.prev.i, ear.i, ear.next.i)的三个顶点索引输出到结果数组中。然后将ear节点从链表中移除ear.prev.next ear.next; ear.next.prev ear.prev;。移除后相邻节点ear.prev和ear.next的几何属性凸/凹、是否为耳朵可能发生了变化因此需要重新计算这两个节点的属性。3.3 关键优化与边界处理Z-order填充规则与顶点顺序WebGL等图形API默认使用“奇偶规则”或“非零环绕规则”来判断填充。earcut.ts通过确保输出的三角形顶点顺序通常是逆时针一致来保证填充的正确性。它会在算法开始时检测输入环的缠绕方向顺时针或逆时针并在必要时进行反转确保内部逻辑统一处理逆时针方向的外环和顺时针方向的内环孔洞。数值精度处理浮点数计算存在精度误差。算法中比较点是否共线、面积是否为零时会使用一个极小的epsilon值如1e-9作为容差避免因精度问题导致错误判断。退化情况处理对于共线的顶点三个点在同一直线上算法会在预处理阶段将其移除因为这样的点不构成有效的三角形角。对于自相交的多边形算法可能无法生成有效的三角化或者生成的结果是未定义的但通常不会崩溃。4. 在Cocos引擎中的实际应用与调用链路了解了算法核心我们看看它在Cocos3中是如何被调用的。你很少会直接调用earcut函数但它却是许多高级功能的基石。4.1 Graphics组件的填充绘制当你使用cc.Graphics组件绘制一个circle、rect或polygon并调用fill()时底层流程如下Graphics将你定义的路径Path转换为一系列顶点。对于非矩形的闭合路径它会调用cc.utils.earcut这是对内部earcut.ts模块的封装进行三角剖分。将得到的三角形索引和顶点数据上传到GPU的顶点缓冲区Vertex Buffer。使用指定的填充颜色或材质进行绘制。4.2 物理引擎的碰撞体生成在Cocos Creator编辑器中当你为一个精灵节点添加PolygonCollider2D组件并点击“编辑”按钮时编辑器可能会使用耳切法或类似的算法将精灵的纹理轮廓通过像素检测得到自动生成一组凸多边形或三角形作为碰撞体的形状。虽然物理引擎如Box2D内部有自己更严格的凸分解算法如Bayazit算法但初始的轮廓三角化可能仍会用到earcut。4.3 MeshRenderer与自定义网格如果你通过程序生成一个2D自定义网格cc.Mesh并希望用MeshRenderer渲染那么将轮廓顶点转换为三角形索引数组这一步earcut函数就是你的得力工具。一个简单的调用示例import { earcut } from ‘cc’; // 假设有一个多边形轮廓顶点按顺序给出格式为 [x0,y0, x1,y1, x2,y2, ...] const polygonVertices [0,0, 100,0, 100,100, 0,100]; // 一个矩形 // 矩形有两个三角形剖分结果应为 [0,1,2, 0,2,3] const triangles earcut(polygonVertices); // 如果多边形有孔洞则需要传入第二个参数孔洞起始索引数组 const outerRing [0,0, 200,0, 200,200, 0,200]; const holeRing [50,50, 150,50, 150,150, 50,150]; const verticesWithHole outerRing.concat(holeRing); const holeIndices [outerRing.length / 2]; // 孔洞起始于第4个顶点之后一个顶点包含x,y两个数字 const trianglesWithHole earcut(verticesWithHole, holeIndices);earcut函数返回一个索引数组indices每三个数字一组指向vertices数组中的顶点构成一个三角形。5. 实战避坑与性能优化指南理论很美好但实际使用中可能会遇到各种问题。以下是我在项目中使用或调试earcut相关功能时总结的经验。5.1 常见问题与排查渲染出现空洞或错乱原因最可能的原因是顶点顺序错误。确保外环顶点是逆时针顺序而孔洞内环是顺时针顺序。这是大多数图形API的约定。排查手动计算一两个三角形的面积使用叉积如果面积为负说明顺序反了。可以在调用earcut前先对顶点数组进行方向检测和纠正。原因顶点数据中存在重复的连续顶点(x1,y1)和(x2,y2)坐标完全相同。这会导致算法创建退化的、面积为0的三角形。排查在生成顶点数组时增加一步去重处理。复杂多边形剖分性能慢原因耳切法最坏复杂度是O(n²)当多边形顶点数很多例如超过1000且形状复杂时每一步寻找“耳朵”都需要大量的点-in-三角形测试。优化简化多边形在三角剖分前使用道格拉斯-普克算法Ramer–Douglas–Peucker或其他多边形简化算法在允许的误差范围内减少顶点数量。对于显示尺寸较小的图形简化后视觉差异不大但性能提升显著。空间划分对于极度复杂的多边形可以考虑使用空间网格Spatial Grid或四叉树来加速“点是否在三角形内”的测试。但这需要修改earcut.ts源码侵入性较强。缓存结果如果同一个多边形需要被多次剖分例如一个静态的UI背景图形应将剖分得到的三角形索引缓存起来避免每帧重复计算。生成狭长三角形Silver Triangle现象剖分出的三角形中有的又细又长像一根针。这种三角形在光栅化时效率低在物理模拟中也可能导致数值不稳定。原因耳切法是一种“贪婪算法”它只关心当前能切下的耳朵不关心整体三角形网格的质量。当多边形有非常尖锐的角或相邻顶点距离差异很大时就容易产生这种三角形。缓解对于质量要求高的场景如高精度物理模拟或3D模型的平面投影耳切法可能不是最佳选择。可以考虑在剖分后对网格进行“对角线翻转”等后处理优化或者直接使用旨在生成高质量三角形的算法如约束Delaunay三角剖分CDT。Cocos内置的earcut可能无法满足这种极端需求。5.2 高级技巧与扩展思路处理带多个孔洞的多边形earcut函数的第二个参数holes是一个数组每个元素是孔洞环在顶点数组中的起始索引。例如holes: [10, 20]表示第一个孔洞从第10个顶点开始第二个从第20个顶点开始。确保每个孔洞环自身是闭合的首尾顶点相连的逻辑由算法处理。与SDF有符号距离场结合对于需要动态变形或平滑边缘的图形三角剖分可能不够用。一种高级做法是先用earcut生成一个基础网格然后在着色器Shader中使用SDF技术来定义最终的形状和边缘。这样既能利用GPU的并行能力实现平滑效果又避免了在CPU端进行极其复杂的轮廓-网格实时转换。自定义顶点属性插值earcut只处理顶点的位置坐标x, y。如果你的顶点还有颜色、UV纹理坐标等其他属性你需要确保在剖分时这些属性随着顶点一起被正确的三角形索引引用。通常你需要维护一个包含所有顶点信息的结构体数组earcut返回的索引可以直接用于索引这个结构体数组。6. 源码调试与自定义修改有时你可能需要深入earcut.ts内部进行调试甚至为了特殊需求修改它。调试在Cocos Creator中你可以在earcut.ts文件的关键位置如链表循环、耳朵判断处添加console.log或使用调试器设置断点。准备一个简单的、有问题的小多边形顶点数据作为输入单步跟踪算法的执行过程观察链表的变化和三角形的输出顺序这是理解算法和定位问题最快的方式。修改如果你想尝试优化比如集成空间划分建议先将earcut.ts文件复制到你的项目assets目录下的某个脚本文件夹中然后修改这个副本并创建一个新的模块导出供你的项目使用。不要直接修改引擎源码否则引擎升级时你的修改会被覆盖。这种“打补丁”的方式给了你最大的灵活性。例如创建一个my-earcut.ts// 基于引擎源码修改后的自定义版本 export function myEarcut(data: number[], holeIndices?: number[], dim 2): number[] { // ... 你的自定义实现 ... }最后理解earcut.ts不仅仅是掌握一个算法更是窥见了Cocos引擎将复杂几何问题抽象、封装并为上层应用提供简洁接口的设计哲学。当你下次在Cocos中绘制一个不规则图形时你会知道在流畅显示的背后是这样一个精巧的“耳切”算法在默默工作。