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

Question

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

除此之外,该算法还需要考虑:

• 对任何给定对象进行多次可能的分解
• 处理将网格装配到固定尺寸的画布(纸张).
• 识别网中的两个面板何时重叠(因此无效).
• 由于重叠或页面大小限制,如果网格无法表示为单个网格,则将网格分成多个网络.
• 在适当的位置生成制表符,用于附加相邻的面.

明显的退化情况就是每面创建一个网,边缘有一半.这显然不是理想的:理想的情况是单个连续网.复杂形状的现实很可能在中间.

我意识到找到最佳网络(最少网络/最少页面)可能计算成本很高,但是找到"足够好"的网络的良好启发式就足够了.

Answer 1

当我读到你的问题时,"自动纸制算法"这个词出现了.所以我用Google搜索并发现了Massarwi等人使用广义圆柱(pdf)的Papercraft模型.

我们提出了一种新方法,通过基于条带的近似,从三角网格中生成圆形玩具动物人物的展开纸制图案.虽然原则上三角形模型可以简单地通过在检查展开平面中的交叉三角形时尽可能多地保持其连接性来展开,但是创建具有数万个三角形的图案是不现实的.我们的方法是通过一组没有内部顶点的连续三角形条来近似网格模型.最初,我们将网格细分为与模型特征相对应的部分.我们将每个部分分成区域区域,将与区域边界相似的拓扑距离的三角形分组.我们通过简化网格生成三角形条带,同时保留区域区域和其他切割线的边界.然后简单地通过展开条带组来创建图案.我们的方法的显着特征是我们通过一组连续条带来近似网格模型,而不是通过其他规则表面(例如锥体或圆柱体的部分)来近似网格模型.因此,可以仅使用网格操作和简单的展开算法来生成近似展开的图案.此外,可以通过弯曲纸张(不破坏边缘)来制作一组条带,并且可以表示原始网格模型的平滑特征.

还有一篇早期的相关论文,称为Shatz等人的网格纸工艺模型(9MB pdf).

本文介绍了一种将网格划分为可展开近似的算法.该算法可用于CAD和计算机图形学中的各种应用.本文重点介绍纸张制作,并证明该算法可生成可开发,易于切割且可粘合在一起的近似值.还表明给定模型和纸模型之间的误差很小.

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

Answer 2

链接到的eed3si9n算法将从复杂的几何体中生成合理的合理的纸制网格.如果您想完全按照建模的方式展开网格,例如对于多面体模型,那么这是一种相对简单的技术,用于展开任何网格

从源网格构造图形,其中每个面都是图形中的顶点,如果它们在网格中共享公共边,则连接两个顶点.这些图中的一个表示不可展开的网格,当且仅当它没有循环时,即它是树.

好的树表示从起点到达最远面的最少折叠线,因为每个折叠代表将在完成的模型中累积的误差.Dijkstra的算法在这里很好,但最小生成树不起作用.每条边均衡加权,所有树都是最小的生成树,甚至可以将网格展开成一个大螺旋.当你将模型粘在一起时,错误会累积,直到最后几个面完全不适合.

拥有树后,首先在原点绘制起始面.然后通过计算新顶点作为两个圆的交点,并使用与原始网格中边的长度相对应的半径来遍历树并添加新面.选项卡的位置对应于原始网格中的边,但不在可展平树中.

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

这种技术的一些缺点是它会在平面图案中愉快地创建重叠部分,并且它取决于找到一个好的起始面.我试过Floyd-Warshal找到一个最小直径的脸开始,但它的O(n ^ 3)行为造成了过长的咖啡休息时间.可以通过将树的分支标记为"不完整",跳过它并再次在所有不完整的面上重新运行算法来处理重叠的部分.