1. 项目概述为什么凹多边形三角剖分是三维场景的基石在Unity3D里折腾过三维场景建模的朋友估计都遇到过这么个头疼事儿从外部建模软件比如Blender、3ds Max或者SolidWorks辛辛苦苦建好一个复杂的模型导出FBX或OBJ文件满怀期待地拖进Unity结果发现模型显示异常或者物理碰撞体Mesh Collider根本不起作用控制台还飘着一堆关于“非凸面体”的警告。这背后十有八九就是凹多边形Concave Polygon在作祟。简单来说凹多边形就是那些“内凹”进去的多边形像一个缺了一角的星星或者一个字母“L”的形状。而现代实时渲染的GPU其底层硬件和图形API如OpenGL、DirectX几乎只认一种基本图元三角形。所有复杂的模型最终都必须被分解即“三角剖分”成一个个三角形才能被绘制。对于凸多边形这个分解很简单随便选个顶点连起来就行。但对于凹多边形如果随便连接顶点生成的三角形可能会跑到多边形外部或者相互重叠导致渲染错乱、光照计算错误更致命的是物理引擎无法为其生成正确的碰撞体。所以“凹多边形三角网剖分”这个听起来很学术的词实际上是我们每个Unity开发者构建高质量、高性能三维场景时无法绕开的一个底层技术环节。它直接决定了模型渲染的正确性错误的三角剖分会导致模型表面撕裂、闪烁或出现空洞。物理模拟的准确性Unity的Mesh Collider要求网格是“水密”的Watertight且通常建议是凸的。对于复杂的凹形碰撞体要么用多个凸碰撞体Convex Hull组合近似要么就必须依赖一个正确的三角剖分算法来生成凹的Mesh Collider否则角色会穿墙、物体掉落异常。后续处理的可行性诸如动态破碎、网格编辑、导航网格NavMesh生成等高级功能都依赖于一个拓扑结构清晰、无错误的三角形网格。网上能找到的很多“三角剖分”代码示例往往只处理简单的凸多边形或特定情况。今天我就结合自己踩过的坑分享一个在Unity中实现耳切法Ear Clipping来处理简单凹多边形的完整代码示例并深入探讨其原理、局限以及在实际项目如处理导入的SolidWorks模型中的应用策略。目标是让你不仅拿到能跑的代码更能理解背后的“为什么”从而在遇到更复杂网格问题时能有思路去排查和解决。2. 核心算法解析耳切法Ear Clipping是如何工作的面对一个凹多边形我们如何系统地将它切成一个个三角形呢耳切法是一种直观且经典的算法。它的核心思想可以类比为“剪耳朵”在一个多边形中找到一个“耳朵”即一个顶点它与相邻两个顶点构成的三角形完全位于多边形内部且不包含任何其他顶点然后把这个“耳朵”三角形剪下来。重复这个过程直到多边形被剪成一个三角形为止。2.1 算法原理与关键概念让我们先定义几个关键术语这有助于理解代码逻辑顶点列表Vertices List按顺时针或逆时针顺序存储的多边形顶点序列。保持一致的环绕顺序Winding Order至关重要通常Unity和大多数图形系统使用逆时针Counter-Clockwise顺序表示正面。耳朵Ear对于顶点V[i]考虑其前驱V[i-1]和后继V[i1]。如果三角形(V[i-1], V[i], V[i1])满足以下两个条件则V[i]是一个“耳朵”顶点该三角形是凸角Convex Corner。即顶点V[i]处的内角小于180度。可以通过计算叉积Cross Product来判断。该三角形的内部不包含多边形中的任何其他顶点。凸顶点与凹顶点Convex and Concave Vertex通过计算相邻边的叉积可以判断一个顶点是凸的还是凹的。这对于快速筛选潜在的“耳朵”候选点至关重要。算法的步骤可以拆解如下初始化将多边形所有顶点按顺序存入一个列表。顶点分类遍历所有顶点根据叉积结果将其标记为“凸顶点”或“凹顶点”。寻找耳朵遍历所有“凸顶点”对于每个凸顶点V[i]检查三角形(V[i-1], V[i], V[i1])内部是否包含任何其他顶点。如果不包含则V[i]是一个“耳朵”。剪切耳朵一旦找到一个耳朵就将这个三角形(V[i-1], V[i], V[i1])输出到最终的三角形列表即三角网中。然后将顶点V[i]从当前多边形顶点列表中移除相当于剪掉了这个耳朵。更新与迭代移除顶点后它相邻顶点的属性凸/凹可能发生了变化。需要重新计算V[i-1]和V[i1]现在是相邻的了的凸凹性。然后回到步骤3在新的、顶点数减一的多边形中继续寻找耳朵。终止当顶点列表中只剩下3个顶点时将最后这个三角形输出算法结束。注意耳切法要求多边形是“简单多边形”Simple Polygon即边不自交。从规范建模软件导出的模型通常满足这一点但从某些来源获取的网格数据可能需要先进行清洗。2.2 算法优缺点与适用场景耳切法不是万能的理解其边界才能正确使用。优点概念简单易于实现逻辑清晰适合学习理解三角剖分的基本原理。适用于简单凹多边形对于大多数游戏中的非极端复杂模型如建筑部件、地形碎片的凹多边形面片它工作良好。输出质量尚可虽然不能保证产生绝对最优如所有三角形最接近等边的剖分但结果通常可以接受。缺点与局限性能问题最耗时的部分是“点是否在三角形内”的测试。朴素实现需要O(n)次测试来检查一个候选耳朵整个算法复杂度接近O(n³)对于顶点数很多1000的单个多边形面片效率较低。可以通过空间划分如网格或四叉树来优化。对“退化”情况敏感如果多边形存在共线点或极小的锐角算法可能失败或产生极细长的三角形Sliver Triangles这种三角形在光照和物理模拟中可能引发问题。不适用于带洞多边形标准的耳切法无法直接处理中间有洞的多边形。需要先将多边形和洞的边界连接成一个复杂边界才能处理。适用场景在Unity开发中耳切法非常适合用于运行时动态生成简单网格例如根据玩家划线生成一个封闭区域的网格。处理导入模型中的特定复杂面片当发现某个模型的部分面片因为凹多边形导致问题时可以针对性地用此算法重新剖分该面片。学习与原型开发作为理解网格处理的基础。对于SolidWorks等CAD软件导入的复杂机械模型它们通常包含大量精确的曲线和曲面在转换为多边形网格时可能生成非常复杂包含洞或嵌套结构的凹多边形。此时耳切法可能力不从心更需要依赖建模软件本身导出高质量三角化网格或者在Unity中使用更强大的网格处理库如Clipper库的三角化功能或Unity Mesh API配合System.Numerics进行计算。3. Unity中的代码实现与详解下面我将提供一个在Unity C#中实现的耳切法核心代码。这个实现侧重于清晰易懂并包含了关键的优化和健壮性检查。3.1 数据结构与数学工具准备首先我们需要一些基础工具。Unity的Vector3虽然好用但为了进行精确的2D几何计算三角剖分通常针对一个多边形面片可以在其局部平面进行我们最好将3D点投影到2D平面或者直接使用Vector2。using System.Collections.Generic; using UnityEngine; public class EarClippingTriangulator { // 定义一个简单的2D顶点结构包含位置和索引 private struct Vertex2D { public Vector2 position; public int originalIndex; // 保留原始顶点索引用于映射回3D顶点 public Vertex2D(Vector2 pos, int idx) { position pos; originalIndex idx; } } // 核心数学工具方法 // 计算叉积 (对于2D向量叉积结果是一个标量代表z轴分量) private static float Cross(Vector2 a, Vector2 b) { return a.x * b.y - a.y * b.x; } // 判断点p是否在三角形(a,b,c)内使用重心坐标法更稳定 private static bool IsPointInTriangle(Vector2 p, Vector2 a, Vector2 b, Vector2 c) { // 计算向量 Vector2 v0 c - a; Vector2 v1 b - a; Vector2 v2 p - a; // 计算点积和叉积 float dot00 Vector2.Dot(v0, v0); float dot01 Vector2.Dot(v0, v1); float dot02 Vector2.Dot(v0, v2); float dot11 Vector2.Dot(v1, v1); float dot12 Vector2.Dot(v1, v2); // 计算重心坐标 float invDenom 1 / (dot00 * dot11 - dot01 * dot01); float u (dot11 * dot02 - dot01 * dot12) * invDenom; float v (dot00 * dot12 - dot01 * dot02) * invDenom; // 检查点是否在三角形内包含边 return (u 0) (v 0) (u v 1); } // 判断顶点是否为凸顶点假设顶点按逆时针顺序排列 // 对于逆时针多边形如果连续三点的叉积 0则中间点为凸顶点 private static bool IsConvexVertex(Vector2 prev, Vector2 curr, Vector2 next) { return Cross(curr - prev, next - curr) 0; } }3.2 核心剖分算法实现接下来是耳切法的主体逻辑。我们假设输入的顶点已经是按逆时针顺序排列的并且没有重复点。public static Listint Triangulate(ListVector3 vertices3D) { // 1. 将3D顶点投影到2D平面这里简单选择XZ平面适用于大多数水平面片 // 对于任意朝向的面片需要先计算其法向并投影到对应平面这里为简化使用XZ平面 ListVertex2D vertices2D new ListVertex2D(); for (int i 0; i vertices3D.Count; i) { vertices2D.Add(new Vertex2D(new Vector2(vertices3D[i].x, vertices3D[i].z), i)); } // 存储最终三角形索引指向原始vertices3D列表 Listint triangles new Listint(); // 2. 初始化顶点索引列表动态的会随着“剪耳朵”而减少 Listint indexList new Listint(); for (int i 0; i vertices2D.Count; i) { indexList.Add(i); } // 3. 主循环当多边形顶点数大于3时继续 while (indexList.Count 3) { bool earFound false; // 遍历当前多边形的所有顶点 for (int i 0; i indexList.Count; i) { int prevIdx GetPreviousIndex(i, indexList.Count); int currIdx i; int nextIdx GetNextIndex(i, indexList.Count); Vertex2D prev vertices2D[indexList[prevIdx]]; Vertex2D curr vertices2D[indexList[currIdx]]; Vertex2D next vertices2D[indexList[nextIdx]]; // 步骤A: 检查当前顶点是否为凸顶点 if (!IsConvexVertex(prev.position, curr.position, next.position)) { continue; // 是凹顶点不可能是耳朵 } // 步骤B: 检查三角形(prev, curr, next)内部是否包含任何其他顶点 bool isEar true; Vector2 a prev.position; Vector2 b curr.position; Vector2 c next.position; for (int j 0; j indexList.Count; j) { // 跳过三角形的三个顶点本身 if (j prevIdx || j currIdx || j nextIdx) continue; Vector2 testPoint vertices2D[indexList[j]].position; if (IsPointInTriangle(testPoint, a, b, c)) { isEar false; break; } } // 步骤C: 如果是耳朵则剪切它 if (isEar) { // 输出三角形索引映射回原始顶点 triangles.Add(prev.originalIndex); triangles.Add(curr.originalIndex); triangles.Add(next.originalIndex); // 从当前多边形中移除“耳朵”顶点curr indexList.RemoveAt(currIdx); earFound true; break; // 找到一只耳朵并处理后跳出循环重新开始寻找因为顶点列表已变 } } // 安全保护防止无限循环理论上不会但针对退化多边形 if (!earFound) { Debug.LogError(三角剖分失败无法找到有效的耳朵。多边形可能自交或数据有误。); // 应急方案使用一个简单的退化三角化如扇形分割或返回空列表 // 这里直接跳出循环返回已生成的部分三角形可能不完整 break; } } // 4. 最后剩下三个顶点构成最后一个三角形 if (indexList.Count 3) { triangles.Add(vertices2D[indexList[0]].originalIndex); triangles.Add(vertices2D[indexList[1]].originalIndex); triangles.Add(vertices2D[indexList[2]].originalIndex); } return triangles; } // 辅助函数获取循环链表中的前一个和后一个索引 private static int GetPreviousIndex(int currentIndex, int count) { return (currentIndex - 1 count) % count; } private static int GetNextIndex(int currentIndex, int count) { return (currentIndex 1) % count; }3.3 在Unity Mesh中的使用示例现在我们如何将这个三角剖分算法应用到实际的Unity Mesh上呢通常我们需要对Mesh的每个子网格SubMesh的每个多边形面片进行处理。但注意现代3D模型导出的Mesh其mesh.triangles数组已经是一个完全三角化的列表。我们使用这个算法的场景更多是“重新生成”或“动态创建”。下面是一个示例假设我们有一个由轮廓点定义的凹多边形要动态生成一个Mesh。[RequireComponent(typeof(MeshFilter), typeof(MeshRenderer))] public class DynamicConcaveMesh : MonoBehaviour { public ListVector3 contourPoints; // 在Inspector中设置或在代码中生成按顺序排列 void Start() { GenerateMesh(); } void GenerateMesh() { // 1. 使用耳切法计算三角形索引 Listint triangleIndices EarClippingTriangulator.Triangulate(contourPoints); // 2. 检查结果有效性 if (triangleIndices null || triangleIndices.Count 3) { Debug.LogError(三角剖分失败无法生成网格。); return; } // 3. 创建Unity Mesh Mesh mesh new Mesh(); mesh.name Dynamic Concave Mesh; // 设置顶点 mesh.vertices contourPoints.ToArray(); // 设置三角形注意Unity是顺时针正面 // 我们的算法假设输入是逆时针输出三角形顶点顺序也是逆时针。 // Unity中正面是顺时针所以如果模型显示反面可能需要反转三角形顺序。 // 这里先按原样设置如果发现面片是反的再反转。 mesh.triangles triangleIndices.ToArray(); // 4. 自动计算法线和UV简单处理 // 对于复杂情况需要根据业务计算UV法线可以自动重算 mesh.RecalculateNormals(); mesh.RecalculateBounds(); // 简单平面投影UV Vector2[] uvs new Vector2[contourPoints.Count]; Bounds bounds mesh.bounds; for (int i 0; i contourPoints.Count; i) { // 将顶点坐标归一化到0-1范围基于XZ平面投影 uvs[i] new Vector2( (contourPoints[i].x - bounds.min.x) / bounds.size.x, (contourPoints[i].z - bounds.min.z) / bounds.size.z ); } mesh.uv uvs; // 5. 赋值给MeshFilter GetComponentMeshFilter().mesh mesh; } // 在Scene视图中绘制轮廓点方便调试 private void OnDrawGizmosSelected() { if (contourPoints null) return; Gizmos.color Color.green; for (int i 0; i contourPoints.Count; i) { Gizmos.DrawSphere(transform.TransformPoint(contourPoints[i]), 0.1f); if (i contourPoints.Count - 1) { Gizmos.DrawLine(transform.TransformPoint(contourPoints[i]), transform.TransformPoint(contourPoints[i 1])); } } // 闭合多边形 if (contourPoints.Count 1) { Gizmos.DrawLine(transform.TransformPoint(contourPoints[contourPoints.Count - 1]), transform.TransformPoint(contourPoints[0])); } } }实操心得在实际项目中contourPoints的顺序至关重要。务必确保它们是按逆时针顺序排列的并且形成一个不自交的简单多边形。你可以通过一个可视化工具如上面的Gizmos来确认点的顺序。如果生成的Mesh是透明的或者看起来是“内部”朝外很可能是因为顶点顺序是顺时针的。这时你可以在调用Triangulate之前先判断并反转contourPoints列表的顺序。4. 性能优化与高级话题上面的基础实现对于顶点数较少50的多边形是可行的。但在实际项目中尤其是处理复杂模型或需要实时动态剖分时性能可能成为瓶颈。此外我们还需要处理一些更复杂的情况。4.1 算法优化策略预计算并缓存凸凹性在主循环外先计算所有顶点的凸凹性并存入一个数组。当剪掉一个耳朵后只需要更新被影响的相邻两个顶点的凸凹性而不是重新计算全部。优化“点是否在三角形内”的测试这是性能热点。可以引入空间加速结构。边界盒Bounding Box快速剔除在测试一个点是否在三角形内之前先判断该点是否在三角形的轴对齐边界盒AABB内。这可以快速排除大量明显不在内部的点。空间网格Spatial Grid将整个多边形所在的2D区域划分成均匀的网格。将每个顶点放入对应的网格单元格中。当测试三角形内部时只需检查与三角形AABB相交的那些网格单元格中的顶点而不是全部顶点。使用更高效的剖分算法对于要求极高的场景可以考虑实现或集成更高效的算法如单调多边形剖分Monotone Polygon Triangulation或Delaunay三角剖分。Unity的NavMesh生成和一些第三方网格处理库就使用了这些更高级的算法。4.2 处理带洞多边形与三维网格耳切法本身不直接支持洞。处理带洞多边形的标准流程是连接外轮廓和内洞从外轮廓的某一点到内洞的某一点添加一条“桥接”边实际上添加两段重合但方向相反的边从而将带洞多边形转化为一个顶点数更多、边可能自交但通过桥接处理了的简单多边形。这一步需要小心处理确保连接后多边形的环绕顺序依然正确外轮廓逆时针内洞顺时针。应用耳切法对转化后的简单多边形进行三角剖分。移除退化三角形桥接边会产生一些面积为零的退化三角形需要在剖分后过滤掉。对于三维网格的凹多边形面片问题更加复杂。一个三维模型上的“凹多边形”可能并不位于同一个平面上即非共面多边形。标准的2D三角剖分算法无法直接处理。这时需要平面投影计算该多边形面片所有顶点的平均法线然后将所有顶点投影到垂直于该法线的平面上在2D空间进行剖分。这是最常用的方法但投影可能引入扭曲。使用三维三角剖分库寻找能处理三维点集的三角剖分库但这类算法更为复杂。4.3 与SolidWorks模型导入的结合实践当我们将SolidWorks等CAD模型导入Unity时通常会在导出设置中选择较高的曲面细分精度以确保模型已经过良好的三角化。但有时为了优化面数我们可能选择较低的精度这时模型中就可能残留一些未三角化的N边形N4面片其中包含凹多边形。排查与解决流程定位问题网格在Unity中选中模型在Inspector中查看Mesh的详细信息。使用Window - Analysis - Model或第三方工具如Mesh Debug来检查网格中是否存在非三角形面片即索引数不是3的倍数。分离问题面片如果发现某个子网格SubMesh有问题可能需要编写一个编辑器脚本读取mesh.vertices和mesh.triangles分析三角形列表找出那些共享顶点但未形成正确三角形序列的区域。应用剖分算法对于找出的凹多边形顶点环使用我们实现的耳切法或更强大的库重新计算三角形索引。重建Mesh用新的三角形索引列表替换原有的mesh.triangles并重新计算法线、切线等。踩坑记录我曾经遇到一个从SolidWorks导入的复杂装配体其中一个薄壁零件在Unity中物理碰撞完全失效。用Mesh Collider勾选“Convex”没问题但性能差不勾选则碰撞体根本不生成。最后用Wireframe模式查看发现该零件的一个面是由一个复杂的凹多边形带有多个内凹结构构成的。Unity内置的网格处理在生成非凸Mesh Collider时可能对这类复杂凹多边形支持不佳。解决方案是在SolidWorks中对该面进行“分割线”操作手动将其划分为多个凸四边形或三角形再重新导出。这比在Unity中运行时处理要可靠得多。5. 常见问题、调试技巧与替代方案即使有了代码在实际集成中还是会遇到各种问题。这里记录一些典型问题和解决方法。5.1 常见问题排查表问题现象可能原因排查与解决方法生成的Mesh完全不显示或显示为碎片1. 三角形索引顺序错误正面朝内。2. 顶点顺序不是简单的、不自交的多边形。3. 算法陷入无限循环未输出完整三角形。1. 检查mesh.triangles顺序尝试反转所有三角形的顶点顺序如[0,1,2]改为[0,2,1]。2. 使用Gizmos绘制顶点和边确认多边形轮廓是否自交或顺序混乱。3. 在Triangulate函数中添加循环计数器超过顶点数*10次循环则强制退出并报错。Mesh有破洞或缺失部分1. “点是否在三角形内”的判断函数有精度误差错误地将边界点判为内部点导致耳朵识别失败。2. 多边形存在共线点或极小的锐角导致算法无法找到有效的“耳朵”。1. 在IsPointInTriangle中使用带容差epsilon的比较例如(u -epsilon) (v -epsilon) (u v 1epsilon)。2. 在剖分前对顶点进行预处理移除距离过近的重复点合并近似共线的点。性能极差顶点稍多就卡顿朴素的O(n³)算法复杂度导致。实现上文提到的优化策略特别是边界盒快速剔除和空间网格加速性能会有数量级提升。对于静态模型务必在编辑时或加载时预处理而非运行时每帧计算。应用于3D模型后部分三角面扭曲或拉伸将3D顶点投影到2D平面时选择了不合适的投影平面导致几何关系失真。计算多边形面片的平均法线将顶点投影到垂直于该法线的平面上。对于接近垂直的面片可以选择投影到XY或YZ平面或者使用平面拟合算法找到最佳投影平面。5.2 调试与可视化技巧逐帧可视化在Triangulate函数中在关键步骤如找到一个耳朵、剪切一个三角形后使用Debug.DrawLine在Scene视图中实时绘制出当前已生成的三角形和剩余的多边形轮廓。这能帮你直观理解算法的执行过程。输出日志在循环中打印顶点的凸凹性、候选耳朵的测试结果等信息有助于定位逻辑错误。单元测试准备几个已知结果的测试用例如一个正方形、一个五角星、一个带凹角的L形。用你的算法计算并与预期的手动三角剖分结果对比。5.3 现成的替代方案与库如果你的项目对三角剖分的健壮性和性能要求极高或者需要处理带洞、非平面多边形等复杂情况强烈建议考虑使用成熟的库而不是重复造轮子。Unity Mesh API (Mesh.SetTriangles)对于已经三角化的网格Unity管理得很好。问题在于“生成”三角化数据。你可以结合System.Numerics命名空间下的Vector3等进行计算但核心算法仍需自己实现或引入库。第三方C#几何库Clipper2一个功能极其强大的多边形裁剪和偏移库也包含三角剖分功能通过PolyTree结构可以获取三角化的结果。它非常稳定工业级品质是处理复杂多边形包括带洞的绝佳选择。Triangle.NET一个纯C#实现的Delaunay三角剖分库能生成高质量的三角形网格支持约束性Delaunay三角剖分即保持边界非常适合地形生成、导航网格计算等。LibTessDotNet一个C#移植的著名曲面细分库功能强大能处理非常复杂的多边形情况。集成建议对于学习和小型动态生成需求自己实现耳切法非常有价值。但对于处理SolidWorks等导入的复杂工程模型更好的工作流是在DCC数字内容创建工具链中解决网格质量问题。确保在Blender、3ds Max或SolidWorks自身的导出设置中启用“三角化所有面”Triangulate All Faces选项并设置合理的细分精度。这将一劳永逸地获得干净、标准的三角网格避免在Unity中引入额外的运行时开销和潜在错误。Unity的真正优势在于交互和渲染复杂的几何处理应尽量前置。
1. 项目概述为什么凹多边形三角剖分是三维场景的基石在Unity3D里折腾过三维场景建模的朋友估计都遇到过这么个头疼事儿从外部建模软件比如Blender、3ds Max或者SolidWorks辛辛苦苦建好一个复杂的模型导出FBX或OBJ文件满怀期待地拖进Unity结果发现模型显示异常或者物理碰撞体Mesh Collider根本不起作用控制台还飘着一堆关于“非凸面体”的警告。这背后十有八九就是凹多边形Concave Polygon在作祟。简单来说凹多边形就是那些“内凹”进去的多边形像一个缺了一角的星星或者一个字母“L”的形状。而现代实时渲染的GPU其底层硬件和图形API如OpenGL、DirectX几乎只认一种基本图元三角形。所有复杂的模型最终都必须被分解即“三角剖分”成一个个三角形才能被绘制。对于凸多边形这个分解很简单随便选个顶点连起来就行。但对于凹多边形如果随便连接顶点生成的三角形可能会跑到多边形外部或者相互重叠导致渲染错乱、光照计算错误更致命的是物理引擎无法为其生成正确的碰撞体。所以“凹多边形三角网剖分”这个听起来很学术的词实际上是我们每个Unity开发者构建高质量、高性能三维场景时无法绕开的一个底层技术环节。它直接决定了模型渲染的正确性错误的三角剖分会导致模型表面撕裂、闪烁或出现空洞。物理模拟的准确性Unity的Mesh Collider要求网格是“水密”的Watertight且通常建议是凸的。对于复杂的凹形碰撞体要么用多个凸碰撞体Convex Hull组合近似要么就必须依赖一个正确的三角剖分算法来生成凹的Mesh Collider否则角色会穿墙、物体掉落异常。后续处理的可行性诸如动态破碎、网格编辑、导航网格NavMesh生成等高级功能都依赖于一个拓扑结构清晰、无错误的三角形网格。网上能找到的很多“三角剖分”代码示例往往只处理简单的凸多边形或特定情况。今天我就结合自己踩过的坑分享一个在Unity中实现耳切法Ear Clipping来处理简单凹多边形的完整代码示例并深入探讨其原理、局限以及在实际项目如处理导入的SolidWorks模型中的应用策略。目标是让你不仅拿到能跑的代码更能理解背后的“为什么”从而在遇到更复杂网格问题时能有思路去排查和解决。2. 核心算法解析耳切法Ear Clipping是如何工作的面对一个凹多边形我们如何系统地将它切成一个个三角形呢耳切法是一种直观且经典的算法。它的核心思想可以类比为“剪耳朵”在一个多边形中找到一个“耳朵”即一个顶点它与相邻两个顶点构成的三角形完全位于多边形内部且不包含任何其他顶点然后把这个“耳朵”三角形剪下来。重复这个过程直到多边形被剪成一个三角形为止。2.1 算法原理与关键概念让我们先定义几个关键术语这有助于理解代码逻辑顶点列表Vertices List按顺时针或逆时针顺序存储的多边形顶点序列。保持一致的环绕顺序Winding Order至关重要通常Unity和大多数图形系统使用逆时针Counter-Clockwise顺序表示正面。耳朵Ear对于顶点V[i]考虑其前驱V[i-1]和后继V[i1]。如果三角形(V[i-1], V[i], V[i1])满足以下两个条件则V[i]是一个“耳朵”顶点该三角形是凸角Convex Corner。即顶点V[i]处的内角小于180度。可以通过计算叉积Cross Product来判断。该三角形的内部不包含多边形中的任何其他顶点。凸顶点与凹顶点Convex and Concave Vertex通过计算相邻边的叉积可以判断一个顶点是凸的还是凹的。这对于快速筛选潜在的“耳朵”候选点至关重要。算法的步骤可以拆解如下初始化将多边形所有顶点按顺序存入一个列表。顶点分类遍历所有顶点根据叉积结果将其标记为“凸顶点”或“凹顶点”。寻找耳朵遍历所有“凸顶点”对于每个凸顶点V[i]检查三角形(V[i-1], V[i], V[i1])内部是否包含任何其他顶点。如果不包含则V[i]是一个“耳朵”。剪切耳朵一旦找到一个耳朵就将这个三角形(V[i-1], V[i], V[i1])输出到最终的三角形列表即三角网中。然后将顶点V[i]从当前多边形顶点列表中移除相当于剪掉了这个耳朵。更新与迭代移除顶点后它相邻顶点的属性凸/凹可能发生了变化。需要重新计算V[i-1]和V[i1]现在是相邻的了的凸凹性。然后回到步骤3在新的、顶点数减一的多边形中继续寻找耳朵。终止当顶点列表中只剩下3个顶点时将最后这个三角形输出算法结束。注意耳切法要求多边形是“简单多边形”Simple Polygon即边不自交。从规范建模软件导出的模型通常满足这一点但从某些来源获取的网格数据可能需要先进行清洗。2.2 算法优缺点与适用场景耳切法不是万能的理解其边界才能正确使用。优点概念简单易于实现逻辑清晰适合学习理解三角剖分的基本原理。适用于简单凹多边形对于大多数游戏中的非极端复杂模型如建筑部件、地形碎片的凹多边形面片它工作良好。输出质量尚可虽然不能保证产生绝对最优如所有三角形最接近等边的剖分但结果通常可以接受。缺点与局限性能问题最耗时的部分是“点是否在三角形内”的测试。朴素实现需要O(n)次测试来检查一个候选耳朵整个算法复杂度接近O(n³)对于顶点数很多1000的单个多边形面片效率较低。可以通过空间划分如网格或四叉树来优化。对“退化”情况敏感如果多边形存在共线点或极小的锐角算法可能失败或产生极细长的三角形Sliver Triangles这种三角形在光照和物理模拟中可能引发问题。不适用于带洞多边形标准的耳切法无法直接处理中间有洞的多边形。需要先将多边形和洞的边界连接成一个复杂边界才能处理。适用场景在Unity开发中耳切法非常适合用于运行时动态生成简单网格例如根据玩家划线生成一个封闭区域的网格。处理导入模型中的特定复杂面片当发现某个模型的部分面片因为凹多边形导致问题时可以针对性地用此算法重新剖分该面片。学习与原型开发作为理解网格处理的基础。对于SolidWorks等CAD软件导入的复杂机械模型它们通常包含大量精确的曲线和曲面在转换为多边形网格时可能生成非常复杂包含洞或嵌套结构的凹多边形。此时耳切法可能力不从心更需要依赖建模软件本身导出高质量三角化网格或者在Unity中使用更强大的网格处理库如Clipper库的三角化功能或Unity Mesh API配合System.Numerics进行计算。3. Unity中的代码实现与详解下面我将提供一个在Unity C#中实现的耳切法核心代码。这个实现侧重于清晰易懂并包含了关键的优化和健壮性检查。3.1 数据结构与数学工具准备首先我们需要一些基础工具。Unity的Vector3虽然好用但为了进行精确的2D几何计算三角剖分通常针对一个多边形面片可以在其局部平面进行我们最好将3D点投影到2D平面或者直接使用Vector2。using System.Collections.Generic; using UnityEngine; public class EarClippingTriangulator { // 定义一个简单的2D顶点结构包含位置和索引 private struct Vertex2D { public Vector2 position; public int originalIndex; // 保留原始顶点索引用于映射回3D顶点 public Vertex2D(Vector2 pos, int idx) { position pos; originalIndex idx; } } // 核心数学工具方法 // 计算叉积 (对于2D向量叉积结果是一个标量代表z轴分量) private static float Cross(Vector2 a, Vector2 b) { return a.x * b.y - a.y * b.x; } // 判断点p是否在三角形(a,b,c)内使用重心坐标法更稳定 private static bool IsPointInTriangle(Vector2 p, Vector2 a, Vector2 b, Vector2 c) { // 计算向量 Vector2 v0 c - a; Vector2 v1 b - a; Vector2 v2 p - a; // 计算点积和叉积 float dot00 Vector2.Dot(v0, v0); float dot01 Vector2.Dot(v0, v1); float dot02 Vector2.Dot(v0, v2); float dot11 Vector2.Dot(v1, v1); float dot12 Vector2.Dot(v1, v2); // 计算重心坐标 float invDenom 1 / (dot00 * dot11 - dot01 * dot01); float u (dot11 * dot02 - dot01 * dot12) * invDenom; float v (dot00 * dot12 - dot01 * dot02) * invDenom; // 检查点是否在三角形内包含边 return (u 0) (v 0) (u v 1); } // 判断顶点是否为凸顶点假设顶点按逆时针顺序排列 // 对于逆时针多边形如果连续三点的叉积 0则中间点为凸顶点 private static bool IsConvexVertex(Vector2 prev, Vector2 curr, Vector2 next) { return Cross(curr - prev, next - curr) 0; } }3.2 核心剖分算法实现接下来是耳切法的主体逻辑。我们假设输入的顶点已经是按逆时针顺序排列的并且没有重复点。public static Listint Triangulate(ListVector3 vertices3D) { // 1. 将3D顶点投影到2D平面这里简单选择XZ平面适用于大多数水平面片 // 对于任意朝向的面片需要先计算其法向并投影到对应平面这里为简化使用XZ平面 ListVertex2D vertices2D new ListVertex2D(); for (int i 0; i vertices3D.Count; i) { vertices2D.Add(new Vertex2D(new Vector2(vertices3D[i].x, vertices3D[i].z), i)); } // 存储最终三角形索引指向原始vertices3D列表 Listint triangles new Listint(); // 2. 初始化顶点索引列表动态的会随着“剪耳朵”而减少 Listint indexList new Listint(); for (int i 0; i vertices2D.Count; i) { indexList.Add(i); } // 3. 主循环当多边形顶点数大于3时继续 while (indexList.Count 3) { bool earFound false; // 遍历当前多边形的所有顶点 for (int i 0; i indexList.Count; i) { int prevIdx GetPreviousIndex(i, indexList.Count); int currIdx i; int nextIdx GetNextIndex(i, indexList.Count); Vertex2D prev vertices2D[indexList[prevIdx]]; Vertex2D curr vertices2D[indexList[currIdx]]; Vertex2D next vertices2D[indexList[nextIdx]]; // 步骤A: 检查当前顶点是否为凸顶点 if (!IsConvexVertex(prev.position, curr.position, next.position)) { continue; // 是凹顶点不可能是耳朵 } // 步骤B: 检查三角形(prev, curr, next)内部是否包含任何其他顶点 bool isEar true; Vector2 a prev.position; Vector2 b curr.position; Vector2 c next.position; for (int j 0; j indexList.Count; j) { // 跳过三角形的三个顶点本身 if (j prevIdx || j currIdx || j nextIdx) continue; Vector2 testPoint vertices2D[indexList[j]].position; if (IsPointInTriangle(testPoint, a, b, c)) { isEar false; break; } } // 步骤C: 如果是耳朵则剪切它 if (isEar) { // 输出三角形索引映射回原始顶点 triangles.Add(prev.originalIndex); triangles.Add(curr.originalIndex); triangles.Add(next.originalIndex); // 从当前多边形中移除“耳朵”顶点curr indexList.RemoveAt(currIdx); earFound true; break; // 找到一只耳朵并处理后跳出循环重新开始寻找因为顶点列表已变 } } // 安全保护防止无限循环理论上不会但针对退化多边形 if (!earFound) { Debug.LogError(三角剖分失败无法找到有效的耳朵。多边形可能自交或数据有误。); // 应急方案使用一个简单的退化三角化如扇形分割或返回空列表 // 这里直接跳出循环返回已生成的部分三角形可能不完整 break; } } // 4. 最后剩下三个顶点构成最后一个三角形 if (indexList.Count 3) { triangles.Add(vertices2D[indexList[0]].originalIndex); triangles.Add(vertices2D[indexList[1]].originalIndex); triangles.Add(vertices2D[indexList[2]].originalIndex); } return triangles; } // 辅助函数获取循环链表中的前一个和后一个索引 private static int GetPreviousIndex(int currentIndex, int count) { return (currentIndex - 1 count) % count; } private static int GetNextIndex(int currentIndex, int count) { return (currentIndex 1) % count; }3.3 在Unity Mesh中的使用示例现在我们如何将这个三角剖分算法应用到实际的Unity Mesh上呢通常我们需要对Mesh的每个子网格SubMesh的每个多边形面片进行处理。但注意现代3D模型导出的Mesh其mesh.triangles数组已经是一个完全三角化的列表。我们使用这个算法的场景更多是“重新生成”或“动态创建”。下面是一个示例假设我们有一个由轮廓点定义的凹多边形要动态生成一个Mesh。[RequireComponent(typeof(MeshFilter), typeof(MeshRenderer))] public class DynamicConcaveMesh : MonoBehaviour { public ListVector3 contourPoints; // 在Inspector中设置或在代码中生成按顺序排列 void Start() { GenerateMesh(); } void GenerateMesh() { // 1. 使用耳切法计算三角形索引 Listint triangleIndices EarClippingTriangulator.Triangulate(contourPoints); // 2. 检查结果有效性 if (triangleIndices null || triangleIndices.Count 3) { Debug.LogError(三角剖分失败无法生成网格。); return; } // 3. 创建Unity Mesh Mesh mesh new Mesh(); mesh.name Dynamic Concave Mesh; // 设置顶点 mesh.vertices contourPoints.ToArray(); // 设置三角形注意Unity是顺时针正面 // 我们的算法假设输入是逆时针输出三角形顶点顺序也是逆时针。 // Unity中正面是顺时针所以如果模型显示反面可能需要反转三角形顺序。 // 这里先按原样设置如果发现面片是反的再反转。 mesh.triangles triangleIndices.ToArray(); // 4. 自动计算法线和UV简单处理 // 对于复杂情况需要根据业务计算UV法线可以自动重算 mesh.RecalculateNormals(); mesh.RecalculateBounds(); // 简单平面投影UV Vector2[] uvs new Vector2[contourPoints.Count]; Bounds bounds mesh.bounds; for (int i 0; i contourPoints.Count; i) { // 将顶点坐标归一化到0-1范围基于XZ平面投影 uvs[i] new Vector2( (contourPoints[i].x - bounds.min.x) / bounds.size.x, (contourPoints[i].z - bounds.min.z) / bounds.size.z ); } mesh.uv uvs; // 5. 赋值给MeshFilter GetComponentMeshFilter().mesh mesh; } // 在Scene视图中绘制轮廓点方便调试 private void OnDrawGizmosSelected() { if (contourPoints null) return; Gizmos.color Color.green; for (int i 0; i contourPoints.Count; i) { Gizmos.DrawSphere(transform.TransformPoint(contourPoints[i]), 0.1f); if (i contourPoints.Count - 1) { Gizmos.DrawLine(transform.TransformPoint(contourPoints[i]), transform.TransformPoint(contourPoints[i 1])); } } // 闭合多边形 if (contourPoints.Count 1) { Gizmos.DrawLine(transform.TransformPoint(contourPoints[contourPoints.Count - 1]), transform.TransformPoint(contourPoints[0])); } } }实操心得在实际项目中contourPoints的顺序至关重要。务必确保它们是按逆时针顺序排列的并且形成一个不自交的简单多边形。你可以通过一个可视化工具如上面的Gizmos来确认点的顺序。如果生成的Mesh是透明的或者看起来是“内部”朝外很可能是因为顶点顺序是顺时针的。这时你可以在调用Triangulate之前先判断并反转contourPoints列表的顺序。4. 性能优化与高级话题上面的基础实现对于顶点数较少50的多边形是可行的。但在实际项目中尤其是处理复杂模型或需要实时动态剖分时性能可能成为瓶颈。此外我们还需要处理一些更复杂的情况。4.1 算法优化策略预计算并缓存凸凹性在主循环外先计算所有顶点的凸凹性并存入一个数组。当剪掉一个耳朵后只需要更新被影响的相邻两个顶点的凸凹性而不是重新计算全部。优化“点是否在三角形内”的测试这是性能热点。可以引入空间加速结构。边界盒Bounding Box快速剔除在测试一个点是否在三角形内之前先判断该点是否在三角形的轴对齐边界盒AABB内。这可以快速排除大量明显不在内部的点。空间网格Spatial Grid将整个多边形所在的2D区域划分成均匀的网格。将每个顶点放入对应的网格单元格中。当测试三角形内部时只需检查与三角形AABB相交的那些网格单元格中的顶点而不是全部顶点。使用更高效的剖分算法对于要求极高的场景可以考虑实现或集成更高效的算法如单调多边形剖分Monotone Polygon Triangulation或Delaunay三角剖分。Unity的NavMesh生成和一些第三方网格处理库就使用了这些更高级的算法。4.2 处理带洞多边形与三维网格耳切法本身不直接支持洞。处理带洞多边形的标准流程是连接外轮廓和内洞从外轮廓的某一点到内洞的某一点添加一条“桥接”边实际上添加两段重合但方向相反的边从而将带洞多边形转化为一个顶点数更多、边可能自交但通过桥接处理了的简单多边形。这一步需要小心处理确保连接后多边形的环绕顺序依然正确外轮廓逆时针内洞顺时针。应用耳切法对转化后的简单多边形进行三角剖分。移除退化三角形桥接边会产生一些面积为零的退化三角形需要在剖分后过滤掉。对于三维网格的凹多边形面片问题更加复杂。一个三维模型上的“凹多边形”可能并不位于同一个平面上即非共面多边形。标准的2D三角剖分算法无法直接处理。这时需要平面投影计算该多边形面片所有顶点的平均法线然后将所有顶点投影到垂直于该法线的平面上在2D空间进行剖分。这是最常用的方法但投影可能引入扭曲。使用三维三角剖分库寻找能处理三维点集的三角剖分库但这类算法更为复杂。4.3 与SolidWorks模型导入的结合实践当我们将SolidWorks等CAD模型导入Unity时通常会在导出设置中选择较高的曲面细分精度以确保模型已经过良好的三角化。但有时为了优化面数我们可能选择较低的精度这时模型中就可能残留一些未三角化的N边形N4面片其中包含凹多边形。排查与解决流程定位问题网格在Unity中选中模型在Inspector中查看Mesh的详细信息。使用Window - Analysis - Model或第三方工具如Mesh Debug来检查网格中是否存在非三角形面片即索引数不是3的倍数。分离问题面片如果发现某个子网格SubMesh有问题可能需要编写一个编辑器脚本读取mesh.vertices和mesh.triangles分析三角形列表找出那些共享顶点但未形成正确三角形序列的区域。应用剖分算法对于找出的凹多边形顶点环使用我们实现的耳切法或更强大的库重新计算三角形索引。重建Mesh用新的三角形索引列表替换原有的mesh.triangles并重新计算法线、切线等。踩坑记录我曾经遇到一个从SolidWorks导入的复杂装配体其中一个薄壁零件在Unity中物理碰撞完全失效。用Mesh Collider勾选“Convex”没问题但性能差不勾选则碰撞体根本不生成。最后用Wireframe模式查看发现该零件的一个面是由一个复杂的凹多边形带有多个内凹结构构成的。Unity内置的网格处理在生成非凸Mesh Collider时可能对这类复杂凹多边形支持不佳。解决方案是在SolidWorks中对该面进行“分割线”操作手动将其划分为多个凸四边形或三角形再重新导出。这比在Unity中运行时处理要可靠得多。5. 常见问题、调试技巧与替代方案即使有了代码在实际集成中还是会遇到各种问题。这里记录一些典型问题和解决方法。5.1 常见问题排查表问题现象可能原因排查与解决方法生成的Mesh完全不显示或显示为碎片1. 三角形索引顺序错误正面朝内。2. 顶点顺序不是简单的、不自交的多边形。3. 算法陷入无限循环未输出完整三角形。1. 检查mesh.triangles顺序尝试反转所有三角形的顶点顺序如[0,1,2]改为[0,2,1]。2. 使用Gizmos绘制顶点和边确认多边形轮廓是否自交或顺序混乱。3. 在Triangulate函数中添加循环计数器超过顶点数*10次循环则强制退出并报错。Mesh有破洞或缺失部分1. “点是否在三角形内”的判断函数有精度误差错误地将边界点判为内部点导致耳朵识别失败。2. 多边形存在共线点或极小的锐角导致算法无法找到有效的“耳朵”。1. 在IsPointInTriangle中使用带容差epsilon的比较例如(u -epsilon) (v -epsilon) (u v 1epsilon)。2. 在剖分前对顶点进行预处理移除距离过近的重复点合并近似共线的点。性能极差顶点稍多就卡顿朴素的O(n³)算法复杂度导致。实现上文提到的优化策略特别是边界盒快速剔除和空间网格加速性能会有数量级提升。对于静态模型务必在编辑时或加载时预处理而非运行时每帧计算。应用于3D模型后部分三角面扭曲或拉伸将3D顶点投影到2D平面时选择了不合适的投影平面导致几何关系失真。计算多边形面片的平均法线将顶点投影到垂直于该法线的平面上。对于接近垂直的面片可以选择投影到XY或YZ平面或者使用平面拟合算法找到最佳投影平面。5.2 调试与可视化技巧逐帧可视化在Triangulate函数中在关键步骤如找到一个耳朵、剪切一个三角形后使用Debug.DrawLine在Scene视图中实时绘制出当前已生成的三角形和剩余的多边形轮廓。这能帮你直观理解算法的执行过程。输出日志在循环中打印顶点的凸凹性、候选耳朵的测试结果等信息有助于定位逻辑错误。单元测试准备几个已知结果的测试用例如一个正方形、一个五角星、一个带凹角的L形。用你的算法计算并与预期的手动三角剖分结果对比。5.3 现成的替代方案与库如果你的项目对三角剖分的健壮性和性能要求极高或者需要处理带洞、非平面多边形等复杂情况强烈建议考虑使用成熟的库而不是重复造轮子。Unity Mesh API (Mesh.SetTriangles)对于已经三角化的网格Unity管理得很好。问题在于“生成”三角化数据。你可以结合System.Numerics命名空间下的Vector3等进行计算但核心算法仍需自己实现或引入库。第三方C#几何库Clipper2一个功能极其强大的多边形裁剪和偏移库也包含三角剖分功能通过PolyTree结构可以获取三角化的结果。它非常稳定工业级品质是处理复杂多边形包括带洞的绝佳选择。Triangle.NET一个纯C#实现的Delaunay三角剖分库能生成高质量的三角形网格支持约束性Delaunay三角剖分即保持边界非常适合地形生成、导航网格计算等。LibTessDotNet一个C#移植的著名曲面细分库功能强大能处理非常复杂的多边形情况。集成建议对于学习和小型动态生成需求自己实现耳切法非常有价值。但对于处理SolidWorks等导入的复杂工程模型更好的工作流是在DCC数字内容创建工具链中解决网格质量问题。确保在Blender、3ds Max或SolidWorks自身的导出设置中启用“三角化所有面”Triangulate All Faces选项并设置合理的细分精度。这将一劳永逸地获得干净、标准的三角网格避免在Unity中引入额外的运行时开销和潜在错误。Unity的真正优势在于交互和渲染复杂的几何处理应尽量前置。
![[C++]内存管理：串顺序存储的内存回收](http://pic.xiahunao.cn/yaotu/[C++]内存管理：串顺序存储的内存回收)
