在三维建模与计算机图形学中，将三维网格展开为二维平面图形是一个既具理论挑战又有实际应用价值的问题。无论是用于 UV 贴图映射还是生成可打印的纸艺模型，核心矛盾在于：三维曲面在局部可以近似平面，但整体拓扑的复杂性（如环面、把手结构）使得无重叠展开变得困难。Unfolder 项目基于 Takahashi 等人提出的「优化拓扑手术」（Optimized Topological Surgery）方法，构建了一套从网格分解到平面展开再到纸艺生成的完整流水线。本文从工程实现角度，解析其中的关键技术环节与可调参数。

问题形式化与双图表示

三维网格展开的本质是将一个可能具有任意亏格（genus）的闭合曲面，通过在特定边（edge）上切割，转化为若干个拓扑等价于圆盘的单连通面片，随后将每个面片保形映射到二维平面。理解这一过程的关键在于采用双图（dual graph）表示：原网格的面（face）对应双图中的节点，共享同一条边的两个面则在双图中形成一条连接边。在此框架下，展开过程等价于在双图中寻找一组割边（cut edges），使得移除这些边后剩余的每个连通分量都是树结构，从而对应一个可展开的面片。

这种表示方式的优势在于将几何问题转化为图论问题。基于双图的跨度树（spanning tree）计算可以快速确定初始的面片划分，而后续的拼接与合并操作也可以在图结构上高效完成。工程实现中通常采用邻接表存储双图，并使用并查集（union-find）数据结构维护面片的连通性变化。

切割缝自动选择策略

切割缝（seam）的选择直接决定了展开结果的质量。过多的切割会破坏模型完整性并增加后续拼接难度，而过少的切割则可能导致面片在展开时产生严重重叠。Unfolder 采用了多阶段策略：

第一阶段：基于跨度树的面片分解。在双图中计算最小生成树或指定根节点的宽度优先搜索树，将网格分解为若干面片。每棵子树对应一个潜在的可展开单元。此阶段的目标是最小化面片总数，同时保证单个面片的复杂度可控。工程参数上，通常控制单片面片的面数上限在 200 至 500 之间，具体取决于后续展开算法的数值稳定性。

第二阶段：遗传算法驱动的拼接优化。由于初始分解往往产生多个独立面片，需要通过「缝合」（stitching）操作将相邻面片合并。Unfolder 实现了基于遗传算法的拼接策略：将每种拼接方案编码为染色体，以展开后无重叠、切割缝总长度最小化为适应度函数。交叉操作采用单点交叉，变异操作随机添加或移除特定的拼接边。种群规模通常设为 50 至 100，迭代代数 20 至 50 代可获得满意的近似解。

第三阶段：贪心重合并。遗传算法产生一组较优的拼接方案后，使用贪心策略进一步合并剩余的面片。每次迭代选择一对相邻面片，评估合并后是否产生平面重叠；若不产生重叠则执行合并。此过程持续直到无法继续合并或达到预设的面片数量上限。

平面重叠检测算法

展开后的面片必须满足严格的非重叠约束，否则生成的纸艺模型无法正确折叠。平面重叠检测在计算几何中是一个经典问题，常用算法包括：

包围盒层次检测：首先检查两个多边形的轴对齐包围盒（AABB）是否相交；若不相交则直接判定为无重叠。这种粗测方法计算成本低，可快速过滤大部分无风险的对 - pair。

分离轴定理（Separating Axis Theorem, SAT）：对于凸多边形，SAT 提供了一个充分必要条件：如果存在一条轴使得两个多边形在该轴上的投影不重叠，则它们不相交。工程实现中通常需要测试所有可能由多边形边法向构成的分离轴，时间复杂度为 O (n + m)，其中 n、m 为两个多边形的顶点数。

三角形分解法：将复杂多边形三角化后，对每对三角形执行上述 SAT 检测。优点在于实现逻辑统一，缺点是增加了额外的预处理步骤。Unfolder 在实际实现中采用了混合策略：对边数较少的多边形直接使用 SAT，对边数较多的多边形先进行凸分解再检测。

当检测到重叠时，系统需要回溯到上一状态并尝试其他拼接方案。因此，良好的重叠检测实现应支持高效的回溯机制，通常采用递归搜索配合剪枝策略。

纸艺模型生成与粘合接口

完成平面展开后，需要生成可供打印的纸艺模型。关键额外信息包括：

粘合接口（glue tabs）设计。真实纸艺模型需要在切割缝边缘添加额外的粘合区域，常见形式包括三角形、梯形或矩形接口。接口宽度通常设为网格平均边长的 0.3 至 0.5 倍，过宽会增加材料浪费，过窄则影响粘合强度。Unfolder 实现了自动接口生成功能，根据切割缝两侧面的夹角计算接口类型与尺寸。

切割线与折叠线标注。输出格式需明确区分切割线（cut lines）与折叠线（fold lines）。切割线通常使用实线表示，折叠线使用虚线或点划线。某些实现还支持在折叠线旁边标注折叠方向（如「mountain fold」或「valley fold」）。

排样优化。多个面片在纸面上的排放直接影响材料利用率。这是一个二维矩形装箱问题的变体，常用算法包括贪心策略、遗传算法和基于层次化搜索的混合方法。排样前通常对面片按面积降序排序，优先放置较大的面片。

工程参数参考

针对不同规模的网格模型，以下参数可作为初始调试的参考基准：面片内面数上限建议 200 至 500；遗传算法种群规模 50 至 100、迭代次数 20 至 50；粘合接口宽度系数 0.3 至 0.5；排样时优先放置面积大于平均面积 1.5 倍的面片。对于高精度模型（如 Stanford Bunny 超过 1000 面），建议先将网格简化至 500 面左右进行展开，再通过细分曲面反向映射细节。

小结

Unfolder 所实现的 3D 网格展开算法展示了计算几何在工程实践中的完整链路：从双图拓扑表示到切割缝优化、从平面重叠检测到纸艺模型生成，每一环节都有明确的数学基础与可调参数。该方法的核心思想 —— 通过拓扑手术将复杂曲面分解为可展面片，再以优化方法拼接 —— 不仅适用于纸艺模型，在工业展开、数控加工模板生成等领域同样具有借鉴价值。后续可进一步探索的方向包括：引入基于学习的切割缝预测以加速遗传算法收敛，以及结合考虑材料弯曲特性的非欧几里得展开。

资料来源：GitHub riceroll/unfolding-mesh 项目（实现了基于优化拓扑手术的 3D 网格展开算法）。