Unity计算几何库实战：从Delaunay三角剖分到Voronoi图应用

1. 项目概述：为什么Unity开发者需要一个计算几何库？

如果你在Unity里做过稍微复杂一点的游戏逻辑，比如生成随机地形、处理复杂的碰撞检测、或者实现一个策略游戏的寻路系统，你大概率已经和计算几何打过交道了。你可能自己写过一些向量运算，用Physics.Raycast或者Collider.ClosestPoint来处理碰撞，但一旦需求变得复杂——比如需要把一个不规则多边形切割成多个凸多边形，或者动态生成一片由Voronoi图划分的领土——你就会发现Unity内置的API开始力不从心，写出来的代码既臃肿又低效。

这就是Computational-geometry这个库的价值所在。它不是一个简单的工具集，而是一个系统性的、工业级的计算几何算法库，专门为Unity环境优化和封装。它把那些在学术论文和算法竞赛里才能看到的经典几何算法，比如Delaunay三角剖分、Voronoi图生成、多边形布尔运算（并集、交集、差集）、曲线拟合等，变成了Unity开发者可以直接调用的、高性能的C#组件。想象一下，你不再需要从零开始实现一个健壮的耳切法来三角化一个带洞的多边形，也不用担心自己写的线段相交检测在边界条件下崩溃。这个库帮你封装了这些复杂性，让你能专注于游戏玩法和创意本身。

我最初接触它是因为一个城市建造类项目，需要动态划分地块。手动摆放既费时又不自然，而用Computational-geometry的Voronoi图生成功能，我只需要输入一些随机点，就能立刻得到一片看起来非常有机的、由多边形划分的地块网格，并且每个地块的顶点、边信息都是结构化的，可以直接用于道路生成、区域染色或资源分配。从那以后，这个库就成了我工具箱里的常客，无论是处理2D精灵的复杂碰撞形状，还是为3D地形生成网格的辅助结构，它都能派上用场。

2. 核心功能模块深度解析

Computational-geometry库的功能相当丰富，我们可以将其核心模块分为几个大类，理解每一类能解决什么问题，是高效使用它的关键。

2.1 基础几何结构与运算

任何复杂的几何算法都建立在坚实的基础之上。这个库提供了一套完整且高效的基础结构。

• 点、向量、线段、多边形：这些不是简单的Vector2或Vector3数组。库中定义的Polygon类会严格处理顶点顺序（通常是逆时针）、确保不自交，并且内置了面积计算、重心计算、点包含性测试（射线法或环绕数法）等方法。Segment（线段）类则封装了精确的相交检测、点到线段的最近点计算。
• 几何谓词与鲁棒性：这是库的精华之一。直接使用浮点数进行几何比较（比如判断点是否在线段上）会因为浮点误差而导致错误。库内部使用了自适应精度的几何谓词，或者精心设计的容差比较，确保了算法在绝大多数情况下的鲁棒性。这意味着你的布尔运算不会因为一个微小的数值误差而产生破碎的多边形。
• 凸包算法：给定一堆散点，快速找到那个最小的凸多边形将其全部包裹起来。库通常实现了经典的Graham扫描法或Andrew单调链算法。这在需要简化碰撞体、计算包围区域时非常有用。

2.2 多边形布尔运算（裁剪）

这是使用频率最高的功能之一。它允许你对两个或多个多边形进行像集合一样的操作。

• 并集 (Union)：合并两个多边形，重叠部分只保留一份轮廓。常用于合并相邻区域。
• 交集 (Intersection)：只保留两个多边形重叠的部分。可以用来实现“视野裁剪”——将角色的视野范围多边形与障碍物多边形求交，得到实际可见区域。
• 差集 (Difference)：从一个多边形中“挖去”与另一个多边形重叠的部分。典型应用是：一个房间多边形（地板）减去多个家具占用的多边形，得到可以行走的区域。
• 异或 (XOR)：保留两个多边形不重叠的部分。相对少用，但在一些特效或特殊关卡设计中可能用到。

注意：布尔运算对输入多边形的质量要求较高。虽然库有容错处理，但确保你的多边形是简单的（不自交）、顶点顺序一致，会得到最好和最稳定的结果。对于带洞的多边形，需要按照库约定的格式（例如，外轮廓逆时针，内洞顺时针）来定义。

2.3 三角剖分与网格化

将复杂多边形分解为三角形，这是渲染和物理模拟的基石。

• 耳切法 (Ear Clipping)：适用于简单多边形（无洞）的三角剖分。算法思想是不断地“剪掉”多边形的一个“耳朵”（由连续三个顶点组成的凸角）。库的实现会高效地判断“耳朵”并处理顶点链表。
• 带洞多边形的三角剖分：这是难点。库可能需要你将外轮廓和内洞的顶点连接成一个“伪简单多边形”，然后再应用耳切法或其他算法（如单调多边形剖分）。Computational-geometry通常会提供一个统一的接口，你只需要传入外轮廓和洞的列表即可。
• Delaunay三角剖分：给定一组平面点集，生成一个三角网格，并满足Delaunay准则（任意三角形的外接圆内不包含其他点）。这种剖分能最大化最小角，避免出现“瘦长”的三角形，在数值计算中更稳定。它是生成Voronoi图的基础。

2.4 Voronoi图与Delaunay三角剖分

这两者是紧密相关的对偶图。Delaunay三角剖分连接了点，而Voronoi图划分了区域。

• 从Delaunay到Voronoi：库生成Delaunay三角剖分后，可以很容易地推导出Voronoi图。每个Voronoi单元格（区域）对应一个原始点，区域内的任意位置到该点的距离都比到其他点更近。
• 应用场景：
  • 程序化生成：生成自然的地块、细胞、裂纹纹理。用随机点生成Voronoi图，每个单元格可以赋予不同的生物群系、资源或领土归属。
  • 地图分区：将游戏地图划分为多个区域，用于AI寻路（先在区域间寻路，再在区域内寻路）、动态加载或事件管理。
  • 破碎效果：虽然物理破碎更复杂，但Voronoi图可以作为生成破碎裂纹形状的优秀起点。

2.5 曲线与路径

处理贝塞尔曲线、样条曲线等，用于平滑运动轨迹、武器弹道或UI动画。

• 贝塞尔曲线求值与分割：库提供了标准的三次贝塞尔曲线函数，可以获取曲线上任意比例的点位置和切线方向。更重要的是，它可能包含曲线扁平化算法，即将曲线分割成一系列足够短的线段，以便于渲染或碰撞检测。
• 路径偏移与轮廓生成：给定一条中心线（路径），生成其平行线（等距线）。这可以用来从一条路径生成道路的左右边界，或者为线条生成描边。这里涉及到大量几何计算，如线段平移、圆弧拐角处理等，自己实现非常繁琐。

3. 在Unity项目中的实战集成与应用

知道有什么工具是一回事，知道怎么用是另一回事。下面我们看看如何把这个库真正集成到Unity项目中，并解决实际问题。

3.1 库的获取与项目设置

通常，Computational-geometry会以.unitypackage或通过Unity的Package Manager (UPM) 以Git URL的形式提供。

1. 导入：将包导入项目后，你会在Assets目录下看到相关的脚本、示例场景和可能预制体。第一件事是浏览示例场景，这是最快的学习途径。
2. 命名空间：库的所有核心类通常都在一个特定的命名空间下，比如ComputationalGeometry或CG。在你的脚本开头需要添加using指令。
3. 版本兼容性：关注库的更新日志，确保其与你使用的Unity版本兼容。一些底层数学库的更新（如Mathematics包）可能会影响兼容性。

3.2 典型应用案例分步实现

让我们通过两个具体案例，来走一遍完整的实现流程。

案例一：动态生成随机地图并划分领土

假设我们在做一个RTS或4X策略游戏，需要随机生成一张地图并用自然边界划分给不同玩家或势力。

1. 生成随机点：在游戏地图的矩形边界内，用泊松圆盘采样算法生成一组随机点。这能保证点与点之间有一个最小距离，避免生成过于细碎的Voronoi单元格。你可以先使用库中的基础随机点生成，或者用其他算法生成更均匀的点集。

   // 伪代码思路 List<Vector2> points = PoissonDiskSampling.GeneratePoints(mapWidth, mapHeight, minDistance);

2. 执行Delaunay三角剖分：将点集输入库的Delaunay剖分函数。

   using ComputationalGeometry; DelaunayTriangulation triangulation = DelaunayTriangulator.Triangulate(points);

3. 生成Voronoi图：从Delaunay三角剖分结果中构建Voronoi图。库通常会返回一个VoronoiDiagram对象，其中包含所有Voronoi站点（原始点）和对应的多边形单元格。

   VoronoiDiagram voronoiDiagram = new VoronoiDiagram(triangulation); foreach (VoronoiCell cell in voronoiDiagram.Cells) { Polygon cellPolygon = cell.GetPolygon(); // 获取该单元格的多边形表示 // cellPolygon 可能是一个凸多边形，也可能是一个凹多边形（如果靠近边界） }

4. 裁剪到地图边界：生成的Voronoi单元格是无限延伸的，我们需要用地图的矩形边界多边形去裁剪每一个单元格多边形，这里就用到了多边形布尔运算（求交）。

   Polygon mapBoundsPolygon = CreateRectPolygon(mapWidth, mapHeight); foreach (VoronoiCell cell in voronoiDiagram.Cells) { Polygon clippedPolygon = PolygonClipper.Intersect(cell.GetPolygon(), mapBoundsPolygon); // 现在 clippedPolygon 就是在地图范围内的领土多边形 }

5. 可视化与数据关联：你可以为每个裁剪后的多边形生成一个Mesh用于渲染，或者添加一个PolygonCollider2D用于物理交互。同时，将这个多边形对象与你游戏中的“领土”、“省份”等数据对象关联起来。

案例二：实现一个复杂的2D角色视野系统（带障碍物遮挡）

许多潜行或RTS游戏需要计算角色的视野范围，并且视野会被墙壁等障碍物阻挡。

1. 定义视野范围：通常是一个以角色为圆心、一定半径为半径的扇形或圆形。我们可以用一个高精度的多边形（例如，用很多边近似一个圆）来表示这个“理想视野区域”。

   Polygon idealFOV = Polygon.CreateCircle(characterPosition, viewRadius, 60); // 用60条边近似圆

2. 获取障碍物信息：收集视野范围内所有障碍物的碰撞体（如BoxCollider2D, PolygonCollider2D），并将它们的形状转换为库能识别的Polygon对象。注意处理障碍物的世界坐标变换。
3. 视野裁剪：将“理想视野区域”多边形与所有障碍物多边形的并集进行差集运算。但直接与所有障碍物依次做差集会非常慢且可能出错。更优的策略是：
   • 先将所有障碍物多边形合并成一个大的“阻挡区域”多边形（使用多次并集运算）。
   • 然后用“理想视野区域”减去这个“阻挡区域”。

   Polygon combinedObstacles = obstaclePolygons[0]; for (int i = 1; i < obstaclePolygons.Count; i++) { combinedObstacles = PolygonClipper.Union(combinedObstacles, obstaclePolygons[i]); } Polygon actualFOV = PolygonClipper.Difference(idealFOV, combinedObstacles);

4. 处理结果与优化：运算结果actualFOV可能是一个复杂多边形（可能带洞，也可能被分割成多个独立部分）。你需要遍历它的所有轮廓进行渲染。对于动态更新的视野，需要考虑性能优化，比如使用空间划分（四叉树）来快速获取潜在障碍物，并对视野多边形进行低精度简化（道格拉斯-普克算法）后再渲染。

3.3 性能考量与优化技巧

计算几何算法可能是CPU密集型的，尤其是在对象很多或多边形很复杂时。

• 缓存结果：如果某些几何形状是静态的（如关卡中的墙壁），预先将其转换为Polygon对象并缓存起来，避免每帧都从Collider转换。
• 简化输入：在进行复杂运算（如布尔运算）前，用多边形简化算法减少顶点数量。Computational-geometry库可能内置了简化功能，或者你可以先自己用道格拉斯-普克算法处理。
• 空间划分：对于需要处理大量几何体的场景（如数百个障碍物），使用四叉树（2D）或BVH树来快速剔除无关对象，只对视野或兴趣范围内的物体进行计算。
• 分帧处理：如果视野更新不需要每帧都完全精确，可以考虑分几帧来完成计算，或者使用上一帧的结果作为近似。
• 关注算法复杂度：了解你所调用函数的算法复杂度。例如，简单的凸包算法是O(n log n)，而多边形布尔运算可能更复杂。避免在Update中处理顶点数上千的多边形。

4. 常见问题、调试技巧与进阶使用

即使有了强大的库，在实际开发中还是会遇到各种问题。这里记录一些我踩过的坑和解决方法。

4.1 常见错误与异常处理

4.2 可视化调试：让几何问题无所遁形

计算几何的问题光看日志很难定位，必须“看到”数据。

1. 自定义Debug绘制：在OnDrawGizmos或OnDrawGizmosSelected中，使用Gizmos.DrawLine,Gizmos.DrawSphere,Handles.DrawPolyLine等函数，将你的点、线段、多边形轮廓实时绘制在Scene视图中。

   void OnDrawGizmosSelected() { if (myPolygon != null && myPolygon.Vertices.Count > 1) { Gizmos.color = Color.green; for (int i = 0; i < myPolygon.Vertices.Count; i++) { Vector3 start = myPolygon.Vertices[i]; Vector3 end = myPolygon.Vertices[(i + 1) % myPolygon.Vertices.Count]; Gizmos.DrawLine(start, end); } // 绘制顶点 Gizmos.color = Color.red; foreach (var vertex in myPolygon.Vertices) { Gizmos.DrawSphere(vertex, 0.1f); } } }

2. 分步绘制：对于复杂的多步运算，将每一步的中间结果用不同颜色绘制出来。例如，绘制原始多边形为蓝色，绘制障碍物为红色，绘制布尔运算后的结果为绿色。这样哪一步出了问题一目了然。
3. 使用TextMeshPro显示数据：在Game视图里，将关键信息（如顶点数、面积、算法耗时）实时显示在UI上，方便在运行时监控。

4.3 与Unity其他系统的协同

Computational-geometry库生成的几何数据最终需要融入到Unity的生态中。

• Mesh生成：将Polygon转换为Mesh用于渲染。你需要处理顶点、三角形索引和UV。对于带洞的多边形，三角剖分是这一步的前提。Unity的Mesh类有SetVertices,SetTriangles,SetUVs等方法。
• Collider生成：
  • 2D：PolygonCollider2D可以通过SetPath来设置轮廓。注意顶点数限制和凸多边形限制（如果是凹多边形，需要先分解为凸多边形）。
  • 3D：情况更复杂。通常需要先三角剖分生成Mesh，然后使用MeshCollider。对于复杂静态物体，考虑在编辑器下预生成。
• NavMesh：如果你想用计算几何划分的区域来影响AI寻路，可能需要将生成的多边形边界转换为NavMesh的障碍物（NavMeshObstacle）或者手动烘焙多个NavMesh区域。Unity的NavMesh系统有对应的API可以操作。
• Tilemap与2D工具：如果你在使用Unity的Tilemap系统，计算几何生成的多边形区域可以用来定义可建筑区域、不可通行区域等，通过脚本将数据同步到Tilemap的规则瓦片或染色上。

4.4 从使用到贡献：理解源码与扩展

当你对这个库依赖越来越深，可能会遇到一些特殊需求库本身不支持，或者发现了一些小bug。这时，理解其源码结构就很有必要了。

1. 阅读关键算法：不要试图一开始就读懂所有代码。找到你最常用的功能模块（比如PolygonClipper.cs），从它的公开接口入手，逐步深入。关注它的核心算法是引用了哪篇论文，或者实现了哪种经典算法（如Greiner-Hormann算法用于多边形裁剪）。
2. 编写扩展方法：C#的扩展方法非常适合为库的现有类添加便捷功能。例如，你可以为Polygon类添加一个ToMesh()的扩展方法，封装从多边形到Unity Mesh的转换逻辑，方便在各个项目中复用。

   public static class PolygonExtensions { public static Mesh ToMesh(this Polygon polygon) { // 三角剖分，创建Mesh... return mesh; } }

3. 报告问题与贡献：如果你确认发现了bug，并且有能力修复，可以考虑向开源仓库提交Pull Request。在提交前，确保你理解了代码风格，并添加了相应的测试用例。

5. 性能优化深度实践与内存管理

在游戏运行时，尤其是移动平台或VR/AR应用中，计算几何操作的性能瓶颈可能非常明显。除了之前提到的通用技巧，这里还有一些更深层次的优化策略。

5.1 算法层面的选择性使用

不是所有问题都需要动用最通用的算法。根据输入数据的特性，选择更高效的特定算法。

• 凸多边形 vs 凹多边形：对于凸多边形，许多操作（如点包含检测、与其他凸多边形的相交测试）有O(log n)或O(n)的专用算法，远比处理凹多边形的通用算法快。在数据设计阶段，尽量使用凸多边形。如果必须是凹多边形，考虑用凸分解算法将其预先分解为多个凸多边形的集合。Computational-geometry库可能本身就包含凸分解算法（如Hertel-Mehlhorn算法）。
• 近似计算换取速度：在某些对精度要求不高的场景，如视野的粗略估计、远距离LOD（细节层次）判断，可以使用更简单的几何近似。例如，用多边形的最小包围圆或轴对齐包围盒（AABB）来进行快速但保守的碰撞检测，只有在这个粗略检测通过后，才进行精确的多边形相交测试。
• 空间哈希与网格化：对于大量小型、动态的几何体（如数百个飞行的子弹），可以将空间划分为均匀网格。每个几何体根据其位置注册到对应的网格单元格中。当需要检测某个区域时，只需查询该区域覆盖的少数几个单元格内的对象，极大地减少了需要两两检测的对象对数。

5.2 内存与GC（垃圾回收）优化实战

在Unity中，C#的垃圾回收（GC）是导致帧率卡顿的常见元凶。计算几何算法容易产生大量的临时Vector2、List<T>等托管对象。

1. 结构体（Struct）的使用：确保库中的基础类型（如Point、Segment）是struct而非class。struct是值类型，分配在栈上，方法退出时自动回收，不会增加GC压力。检查你使用的库，如果关键类型是class，考虑向作者反馈或寻找替代。
2. 对象池系统化：不要只池化Polygon对象。为算法中频繁使用的List<Vector2>、List<int>（用于存储索引）、HashSet<Edge>等集合类型也建立对象池。

   // 一个简单的List<Vector2>对象池示例 public static class Vector2ListPool { private static readonly Stack<List<Vector2>> pool = new Stack<List<Vector2>>(); public static List<Vector2> Get() { return pool.Count > 0 ? pool.Pop() : new List<Vector2>(64); // 预设容量 } public static void Release(List<Vector2> list) { list.Clear(); // 清空内容，而非销毁对象 pool.Push(list); } } // 使用 List<Vector2> tempVertices = Vector2ListPool.Get(); // ... 执行算法，填充tempVertices ... Vector2ListPool.Release(tempVertices); // 用完归还

3. 重用输出容器：许多库的函数签名是Polygon SomeOperation(Polygon a, Polygon b)，这意味着每次调用都会返回一个新的Polygon对象。如果可能，寻找或封装一个具有void SomeOperation(Polygon a, Polygon b, ref Polygon result)签名的版本，允许你传入一个预先分配好的Polygon对象来存储结果，避免分配新对象。
4. Array代替List：在性能极度敏感且大小固定的循环中，使用数组Vector2[]代替List<Vector2>。数组的访问速度略快，且没有List的边界检查开销（在非开发版本中）。但牺牲了灵活性。

5.3 多线程与Job System的探索

Unity的C# Job System和Burst编译器可以将计算密集型任务转移到多核CPU上并行执行，极大提升性能。但将现有的计算几何代码移植到Job中需要小心。

• 数据准备：Job不能访问托管对象（如List<T>）。你需要将几何数据（顶点数组）转换为原生的NativeArray<T>。这本身会带来一次内存分配和复制开销，因此只对数据稳定且计算量大的操作有意义。
• 算法并行化：并非所有几何算法都容易并行化。像Delaunay三角剖分中的某些增量算法，其步骤间存在数据依赖，难以并行。但像对大量独立多边形进行相同的布尔运算（如每个角色计算自己的视野），或者对一个大点集进行空间哈希网格的分配，这些任务则是“令人尴尬的并行”，非常适合Job System。
• Burst编译：为你的Job结构体添加[BurstCompile]特性，可以让Burst编译器将其编译为高度优化的本地代码，获得数倍甚至数十倍的性能提升。确保你的Job代码只使用Burst支持的数据类型和数学函数（如Unity.Mathematics中的float2,math命名空间下的函数）。

一个简单的想法是：将需要处理的一批多边形数据准备好NativeArray，然后调度一个并行执行的Job，每个Job处理一个多边形对的布尔运算，最后在主线程收集结果。这需要对库的源码有较深的理解和修改能力。

6. 与其他Unity生态工具的整合方案

一个强大的库不会孤立存在。将Computational-geometry与Unity的其他流行工具和资源结合，能发挥出1+1>2的效果。

6.1 与Shader Graph和VFX Graph的联动

计算几何的结果可以驱动视觉效果。

• 数据传递到Shader：将生成的多边形顶点数据或Voronoi图的站点坐标，通过MaterialPropertyBlock或自定义的Shader变量传递到材质球。在Shader中，可以利用这些数据实现基于距离的区域染色、蜂窝状特效、动态溶解边缘等。
  • 例如：将Voronoi单元格的站点位置和ID传入Shader，在片段着色器中计算当前像素到各个站点的距离，实现泰森多边形风格的着色。
• 控制粒子系统：使用计算几何生成的路径（如平滑的贝塞尔曲线）作为ParticleSystem的轨迹。或者，用Voronoi单元格来控制粒子发射器的密度和范围，实现非均匀的粒子分布效果。

6.2 与Timeline和动画系统的结合

让几何变化动起来。

• 动画顶点：通过对多边形顶点进行关键帧动画或程序化变换（如噪声位移、正弦波），可以创建动态变化的形状，再结合上面的Mesh生成，就能实现流动的液体边界、呼吸感的护盾等效果。Computational-geometry库负责提供初始形状和关键的布尔运算，动画系统负责顶点的逐帧插值。
• Timeline控制：你可以创建自定义的Playable Asset，在Timeline轨道上控制几何参数的变化。例如，在过场动画中，用一个Timeline轨道控制视野多边形的半径和角度，实现镜头视野的平滑缩放和旋转。

6.3 在URP/HDRP渲染管线中的实践

现代可编程渲染管线（URP/HDRP）提供了更多控制渲染细节的可能性。

• 自定义渲染器特性：你可以编写一个ScriptableRendererFeature，在渲染流程的特定阶段（如渲染不透明物体之后）注入你的绘制逻辑。在这里，你可以使用CommandBuffer来绘制由计算几何生成的、用于后期处理效果的几何图形（如自定义的遮罩形状）。
• 体积光与遮罩：文章开头热词中提到了“unity urp shader 体积光”。你可以用计算几何生成一个表示光线照射范围的体积形状（一个锥体与场景几何体求交后的复杂多面体），然后将这个形状的深度或模板信息写入缓冲区，在自定义的体积光Shader中读取，实现被几何体精确遮挡的体积光效果。这比简单的屏幕空间方法要精确得多。

6.4 面向数据技术栈的适配

随着Unity DOTS（面向数据的技术栈）的逐渐成熟，高性能计算的需求日益增长。

• ECS与几何数据：在ECS架构中，几何数据（顶点、边）可以作为IComponentData存储在Entity上。你可以编写一个ISystem，使用Burst编译的Job来并行处理成千上万个实体的几何运算。例如，在一个大规模策略游戏中，同时计算所有单位的视野区域。
• 与Unity.Mathematics的协作：Computational-geometry库的内部实现如果尚未使用Unity.Mathematics中的float2、float3和math函数，你可以考虑在其外围封装一层适配器，将Vector2/3转换为float2/3后再调用核心算法，以便更好地与Burst和Jobs集成。长远来看，一个原生基于Unity.Mathematics的计算几何库会是性能最优的选择。

我个人在几个大型项目中深度使用这个库的经验是，它的价值不仅仅在于提供了现成的算法，更在于它建立了一种“几何思维”。当你遇到一个游戏逻辑问题时，你会开始思考：“这个问题能不能用一个多边形来表示？能不能通过几何运算来解决？” 这种思维转变，往往能带来更优雅、更高效的解决方案。最后一个小建议是，建立一个你自己的“几何工具集”脚本，把项目中验证过的、常用的操作（如快速创建矩形/圆形多边形、常用的裁剪流程、到Mesh/Collider的转换）封装成静态函数，这能极大提升你未来的开发效率。