假设您有一个 3 维对象，以某种常见文件格式表示为 3d 网格。您将如何设计一种算法来将网格分解为一个或多个 2d“网”——即可以切割和折叠以创建原始 3d 对象的二维表示。
除其他事项外，该算法需要考虑：
明显的退化情况是简单地为每个面创建一个网，在一半的边缘上带有标签。显然，这并不理想：理想情况是单个连续网络。复杂形状的现实可能在中间的某个地方。
我意识到找到最佳网络（最少的网络/最少的页面）可能在计算上很昂贵，但是找到“足够好”的网络的一个很好的启发式就足够了。
链接到的算法 eed3si9n 将从复杂的几何形状生成漂亮合理的纸模型网格。如果您想完全按照建模的方式展开网格，例如多面体模型，那么这里有一个相对简单的技术，可以按原样展开任何网格
从源网格构造一个图形，其中每个面都是图形中的一个顶点，如果两个顶点在网格中共享一条公共边，则它们是连接的。这些图之一表示一个可展开的网格当且仅当它没有环，即它是一棵树。
一棵好的树代表从起点到最远面的最少折叠线，因为每个折叠代表将在最终模型中累积的误差。Dijkstra 的算法在这里很好，但最小生成树不起作用。由于每条边的权重相同，所有树都是最小生成树，甚至是将您的网格展开成一个大螺旋的树。当您将模型粘合在一起时，错误会累积起来，直到最后几张脸完全不适合。
一旦你有了树，首先在原点绘制你的起始面。然后遍历树并通过将新顶点计算为两个圆的交点来添加新面，其半径对应于原始网格中边的长度。选项卡的位置对应于原始网格中的边，但不在可展平树中。
用户指定的切割可以在树步骤之前作为边缘删除处理。
这种技术的一些缺点是它会很高兴地在平面图案中创建重叠部分，并且它依赖于找到一个好的起始面。我尝试 Floyd-Warshal 来找到一个最小直径的脸，但它的 O(n^3) 行为会导致咖啡休息时间过长。可以通过将该树的分支标记为“不完整”、跳过它并再次在所有不完整的面上重新运行算法来处理重叠部分。
当我读到你的问题时，我想到了“自动纸工艺算法”这个词。所以我在谷歌上搜索并找到了使用Massarwi 等人的广义圆柱体 (pdf) 的 Papercraft 模型。
我们提出了一种通过带状近似从三角网格中生成圆形玩具动物形象的展开纸工艺图案的新方法。尽管原则上可以通过在展开平面中检查相交三角形的同时尽可能多地保留其连通性来展开三角模型，但创建具有数万个三角形的图案是不现实的。我们的方法是通过一组没有内部顶点的连续三角形带来近似网格模型。最初，我们将网格细分为与模型特征相对应的部分。我们将每个部分分割成带状区域，将与部分边界具有相似拓扑距离的三角形分组。我们通过简化网格来生成三角形条带，同时保留带状区域的边界和额外的切割线。然后通过展开这组条带简单地创建图案。我们方法的显着特点是我们通过一组连续的条带来近似网格模型，而不是通过其他规则表面，例如圆锥体或圆柱体的一部分。因此，可以仅使用网格操作和简单的展开算法来生成近似的展开模式。此外，只需弯曲纸张（不破坏边缘）即可制作一组条带，并且可以表示原始网格模型的平滑特征。我们方法的显着特点是我们通过一组连续的条带来近似网格模型，而不是通过其他规则表面，例如圆锥体或圆柱体的一部分。因此，可以仅使用网格操作和简单的展开算法来生成近似的展开模式。此外，只需弯曲纸张（不破坏边缘）即可制作一组条带，并且可以表示原始网格模型的平滑特征。我们方法的显着特点是我们通过一组连续的条带来近似网格模型，而不是通过其他规则表面（例如圆锥体或圆柱体的一部分）。因此，可以仅使用网格操作和简单的展开算法来生成近似的展开模式。此外，只需弯曲纸张（不破坏边缘）即可制作一组条带，并且可以表示原始网格模型的平滑特征。
还有一篇较早的相关论文，称为来自网格的纸工艺模型(9MB pdf)，由 Shatz 等人撰写。
本文介绍了一种将网格分割成可展开近似的算法。该算法可用于 CAD 和计算机图形学中的各种应用。本文重点介绍纸张制作，并演示该算法生成的近似值是可开发的、易于切割的并且可以粘合在一起。还表明给定模型与纸模型之间的误差很小。
来源：http ://www.ee.technion.ac.il/~ayellet/images/sel-papers-pic-5.jpg
我知道这不是答案，但它是相关的。前 SGI 图形专家 Paul Haeberli 的Lamina程序可以解决这个问题。
