新算法生成折叠模式以生成任何3-D折纸结构

在1999年的一篇论文中，Erik Demaine-现在是麻省理工学院电气工程和计算机科学教授，但当时在加拿大滑铁卢大学的一名18岁的博士生描述了一种算法，可以确定如何折叠一块纸张成任何可以想象的三维形状。

这是计算折纸领域的里程碑论文，但该算法没有产生非常实用的折叠模式。基本上，它需要一个很长的纸条并将其卷成所需的形状。由此产生的结构往往有很多接缝，条带自身翻倍，所以它们不是很坚固。

在7月的计算几何学术研讨会上，东京大学的Demaine和Tomohiro Tachi将宣布完成从1999年论文开始的任务：折叠折纸形状的通用算法，保证最小数量的接缝。

“在1999年，我们证明你可以折叠任何多面体，但我们展示如何做到这一点的方式是非常低效的，”Demaine说。“如果你的初始纸片超长而且很瘦，那就很有效。但是如果你要用方形纸开始，那么旧的方法基本上会将方纸折叠成薄条，几乎浪费掉所有的纸张。材料。新结果有望提高效率。考虑如何制作多面体，这是一个完全不同的策略。“

Demaine和Tachi也在努力在新版本的Origamizer中实现该算法，这是一款用于生成折纸折痕图案的免费软件，其首版Tachi于2008年发布。

保持边界

研究人员的算法设计用于生成任何多面体的折痕图案，即由许多平面构成的三维表面。例如，计算机图形软件将三维物体建模为由多个小三角形组成的多面体。“任何弯曲的形状你可以用很多小平面来近似，”Demaine解释道。

从技术上讲，保证折叠将涉及最小数量的接缝意味着它保留了原始纸张的“边界”。例如，假设您有一张圆形纸，想将其折叠成杯子。在纸张的中心留下一个较小的圆圈，你可以用褶皱的图案将两侧聚在一起; 事实上，一些水冷却杯是按照这种精确的设计制造的。

在这种情况下，杯子的边缘 - 其边缘 - 与展开的圆圈 - 其外边缘的边界相同。Demaine及其同事的早期算法所产生的折叠也是如此。在那里，杯子将由一条薄薄的纸条包裹成一个圆形和圆形的线圈 - 它可能不会保持水。

“ 新算法可以为你提供更好，更实用的折叠，”Demaine说。“我们不知道如何在数学上精确地量化，除了它似乎在实践中更好地工作。但我们确实有一个数学属性可以很好地区分这两种方法。新方法保留了原始块的边界在你试图制作的表面边界上的纸张。我们称之为水密性。“

封闭的表面 - 例如球体 - 没有边界，因此它的折纸近似将需要边界相交的接缝。但是“用户可以选择放置边界的位置，”Demaine说。“你不能让整个封闭的表面变得不透水，因为边界必须在某个地方，但你可以选择那里。”

照明火灾

该算法首先将目标多面体的小平面映射到平坦表面上。但是当折叠完成时刻面将会接触，而它们在平坦表面上可以相互远离。“你折叠掉所有额外的材料并将多面体的面部聚集在一起，”Demaine说。

折叠多余的材料可能是一个非常复杂的过程。将多个面拼合在一起的折叠可能涉及数十个甚至数百个单独的折痕。

开发一种自动计算折痕模式的方法涉及许多不同的见解，但一个中心的方法是它们可以用称为Voronoi图的东西来近似。要理解这个概念，想象一下草地平原。同时设置了许多火灾，它们都以相同的速率向所有方向扩散。以19世纪乌克兰数学家Gyorgy Voronoi命名的Voronoi图描述了火灾发生的位置和相邻火灾相遇的边界。在Demaine和Tachi的算法中，Voronoi图的边界定义了论文中的折痕。

“我们必须在我们的环境中稍微调整一下，”Demaine说。“我们还想象同时在多面体的整个多边形上点火并从那里长出来。但这个概念确实非常有用。挑战是设置点火的地方，基本上，以便Voronoi图表具有所有我们需要的属性。“

完成任务

“这是非常令人印象深刻的东西，”计算折纸的先驱之一，美国数学学会的研究员罗伯特·朗说，他在2001年放弃了成功的光学工程职业，成为一名全职的原创者。“它完成了我将其描述为20多年前开始的任务：一种从纸张上有效折叠任何指定形状的计算方法。一路上，有几个很好的示例拼图：一种折叠任何形状但不是非常有效的算法;一种有效折叠特定树状结构系列而不是表面的算法;一种折叠树木和曲面但不是每种形状的算法。这个算法涵盖了所有这些!算法令人惊讶的复杂，但这是因为它是全面的。它真正涵盖了所有可能性。它不仅仅是一个抽象的证据; 它很容易在计算上实现。“

Joseph O'Rourke，史密斯学院数学与计算机科学教授，如何折叠它的作者：联系数据，折纸和多面体，同意。他说：“之前所知道的是'作弊' - 用薄带缠绕多面体 - 或者不能保证成功。” “他们的新算法保证产生折叠，而且与作弊相反，因为多面体的每个面都被纸张的”无缝“面覆盖，并且纸的边界映射到多面体的边界。歧管 - 他们的'防水'属性。最后，实现折叠所需的额外结构“闪光”都可以隐藏在内部，因此是隐形的。“