将3d网格分解为2d网格

Question

假设您有一个三维对象，以某种常见文件格式表示为三维网格。你将如何设计一个算法来将网格分解成一个或多个2D网格 - 也就是说，可以剪切并折叠以创建原始3D对象的二维表示。

除其他事项外，算法将需要考虑：

• 多个可能的分解对于任何给定对象
• 处理网格装配到固定大小的画布（纸张）。
• 确认网络中的两个面板何时会重叠（因而无效）。
• 由于重叠或页面大小限制，如果不能将网格表示为单个网格，则会将网格划分为多个网格。
• 在适当的位置生成选项卡，用于附加相邻的面。

明显的退化情况是简单地创建一个网面，每边都有一个网点，边上有一半标签。显然这并不理想：理想的情况是一个连续的网络。复杂形状的现实可能在中间的某个地方。

我意识到寻找最佳网（最少的网/最少的网页）可能在计算上很昂贵，但寻找“足够好”的网络的一个很好的启发就足够了。

Answer 1

当我读到你的问题时，“自动papercraft算法”这个词来找我。所以我搜索了它，发现了由Massarwi等人发现的Papercraft Models using Generalized Cylinders（pdf）。

我们提出了通过基于 条形逼近的装置产生的，从 三角网格 圆形玩具动物附图 展开papercraft图案的新方法。虽然在 原则三角模型可以通过 保留尽可能多 尽可能它连接的同时 检查中 展开的平面相交的三角形，创建具有三角形数以万计的模式 简单地展开是 不现实的。我们的方法是通过一组 连续三角形条对 进行近似网格模型，而没有 内部顶点。最初，我们 将我们的网格细分成与 模型的特征相对应的部分 。我们将每个部分分为区域 区域，分组的三角形为 与 部分边界相似的拓扑距离。我们通过简化网格生成三角形 条，而 保留区域 区域的边界和附加的切割线。 图案然后简单地通过 展开一组条。 我们的方法 的区别特征是我们通过一组连续条来近似一个网格模型，而不是通过其他直纹表面，例如圆锥或圆柱体的部分 。因此，仅使用网格操作 和简单展开算法生成的近似展开图案可以是 。另外，一组条可以是仅通过弯曲纸 （没有断裂边缘）而制作的 ，并且 可以代表 原始网格模型的平滑特征。

Shatz等人也有一篇较早的相关论文Paper craft models from meshes（9MB pdf）。

本文介绍了 的算法分割的网格到显影 近似值。算法可以是用于CAD 和计算机图形学中的各种应用的 。这篇论文 侧重于纸制造，并且 表明算法 生成的近似值是可展开的，容易剪切的，并且可以将 胶合在一起。它也表明 给定的模型和 之间的误差很小。

来源：http://www.ee.technion.ac.il/~ayellet/images/sel-papers-pic-5.jpg

Answer 2

的算法eed3si9n连接会产生很好的合理papercraft从复杂的几何形状网格。如果你想展示网格完全按照它的模型，比如多面体模型，那么这里有一个相对简单的技术来展开任何网格，因为它站立起来

从你的源网格构建一个图形，其中每个面是一个顶点在图中，并且如果它们在网格中共享公共边，则连接两个顶点。其中一个图表示一个可展开的网格，当且仅当它没有循环时，即它是一棵树。

一棵好树代表了从起点到达最远的人脸所需的最少的折线，因为每个褶皱都代表将在成品模型中积累的误差。 Dijkstra的算法在这里很好，但最小生成树不起作用。每条边的权重都相等，所有的树都是最小的生成树，甚至可以将网格展开成一个大螺旋。当你把模型粘在一起时，错误就会积累起来，直到最后几张脸完全不适合。

一旦你有了这棵树，开始在原点绘制你的起始脸。然后通过计算新顶点作为两个圆的交点，并将半径与原始网格中边的长度相对应，然后漫步树并添加新面。选项卡的位置对应于原始网格中的边缘，但不在可扁平树中。

用户指定的剪切可以在树步骤之前作为边缘删除进行处理。

该技术的一些缺点是，它会愉快地创建在平坦图案重叠的部分，并且它依赖于找到一个很好的起点的脸。我试图用Floyd-Warshal找到一个最小直径的脸，但是它的O（n^3）行为会造成过长的咖啡时间。重叠的部分可以通过将树的分支标记为“不完整”来处理，跳过它，并且再次在所有不完整的面上重新运行算法。

Answer 3

我知道这不是一个答案，但它是相关的。前SGI图形家伙Paul Haeberli的Lamina程序是针对此问题的解决方案。