新算法生成折疊模式以生成任何3-D折紙結(jié)構(gòu)

在1999年的一篇論文中，Erik Demaine-現(xiàn)在是麻省理工學(xué)院電氣工程和計(jì)算機(jī)科學(xué)教授，但當(dāng)時(shí)在加拿大滑鐵盧大學(xué)的一名18歲的博士生描述了一種算法，可以確定如何折疊一塊紙張成任何可以想象的三維形狀。

這是計(jì)算折紙領(lǐng)域的里程碑論文，但該算法沒(méi)有產(chǎn)生非常實(shí)用的折疊模式?；旧希枰粋€(gè)很長(zhǎng)的紙條并將其卷成所需的形狀。由此產(chǎn)生的結(jié)構(gòu)往往有很多接縫，條帶自身翻倍，所以它們不是很堅(jiān)固。

在7月的計(jì)算幾何學(xué)術(shù)研討會(huì)上，東京大學(xué)的Demaine和Tomohiro Tachi將宣布完成從1999年論文開始的任務(wù)：折疊折紙形狀的通用算法，保證最小數(shù)量的接縫。

“在1999年，我們證明你可以折疊任何多面體，但我們展示如何做到這一點(diǎn)的方式是非常低效的，”Demaine說(shuō)。“如果你的初始紙片超長(zhǎng)而且很瘦，那就很有效。但是如果你要用方形紙開始，那么舊的方法基本上會(huì)將方紙折疊成薄條，幾乎浪費(fèi)掉所有的紙張。材料。新結(jié)果有望提高效率?？紤]如何制作多面體，這是一個(gè)完全不同的策略。“

Demaine和Tachi也在努力在新版本的Origamizer中實(shí)現(xiàn)該算法，這是一款用于生成折紙折痕圖案的免費(fèi)軟件，其首版Tachi于2008年發(fā)布。

保持邊界

研究人員的算法設(shè)計(jì)用于生成任何多面體的折痕圖案，即由許多平面構(gòu)成的三維表面。例如，計(jì)算機(jī)圖形軟件將三維物體建模為由多個(gè)小三角形組成的多面體。“任何彎曲的形狀你可以用很多小平面來(lái)近似，”Demaine解釋道。

從技術(shù)上講，保證折疊將涉及最小數(shù)量的接縫意味著它保留了原始紙張的“邊界”。例如，假設(shè)您有一張圓形紙，想將其折疊成杯子。在紙張的中心留下一個(gè)較小的圓圈，你可以用褶皺的圖案將兩側(cè)聚在一起; 事實(shí)上，一些水冷卻杯是按照這種精確的設(shè)計(jì)制造的。

在這種情況下，杯子的邊緣 - 其邊緣 - 與展開的圓圈 - 其外邊緣的邊界相同。Demaine及其同事的早期算法所產(chǎn)生的折疊也是如此。在那里，杯子將由一條薄薄的紙條包裹成一個(gè)圓形和圓形的線圈 - 它可能不會(huì)保持水。

“ 新算法可以為你提供更好，更實(shí)用的折疊，”Demaine說(shuō)。“我們不知道如何在數(shù)學(xué)上精確地量化，除了它似乎在實(shí)踐中更好地工作。但我們確實(shí)有一個(gè)數(shù)學(xué)屬性可以很好地區(qū)分這兩種方法。新方法保留了原始?jí)K的邊界在你試圖制作的表面邊界上的紙張。我們稱之為水密性。“

封閉的表面 - 例如球體 - 沒(méi)有邊界，因此它的折紙近似將需要邊界相交的接縫。但是“用戶可以選擇放置邊界的位置，”Demaine說(shuō)。“你不能讓整個(gè)封閉的表面變得不透水，因?yàn)檫吔绫仨氃谀硞€(gè)地方，但你可以選擇那里。”

照明火災(zāi)

該算法首先將目標(biāo)多面體的小平面映射到平坦表面上。但是當(dāng)折疊完成時(shí)刻面將會(huì)接觸，而它們?cè)谄教贡砻嫔峡梢韵嗷ミh(yuǎn)離。“你折疊掉所有額外的材料并將多面體的面部聚集在一起，”Demaine說(shuō)。

折疊多余的材料可能是一個(gè)非常復(fù)雜的過(guò)程。將多個(gè)面拼合在一起的折疊可能涉及數(shù)十個(gè)甚至數(shù)百個(gè)單獨(dú)的折痕。

開發(fā)一種自動(dòng)計(jì)算折痕模式的方法涉及許多不同的見(jiàn)解，但一個(gè)中心的方法是它們可以用稱為Voronoi圖的東西來(lái)近似。要理解這個(gè)概念，想象一下草地平原。同時(shí)設(shè)置了許多火災(zāi)，它們都以相同的速率向所有方向擴(kuò)散。以19世紀(jì)烏克蘭數(shù)學(xué)家Gyorgy Voronoi命名的Voronoi圖描述了火災(zāi)發(fā)生的位置和相鄰火災(zāi)相遇的邊界。在Demaine和Tachi的算法中，Voronoi圖的邊界定義了論文中的折痕。

“我們必須在我們的環(huán)境中稍微調(diào)整一下，”Demaine說(shuō)。“我們還想象同時(shí)在多面體的整個(gè)多邊形上點(diǎn)火并從那里長(zhǎng)出來(lái)。但這個(gè)概念確實(shí)非常有用。挑戰(zhàn)是設(shè)置點(diǎn)火的地方，基本上，以便Voronoi圖表具有所有我們需要的屬性。“

完成任務(wù)

“這是非常令人印象深刻的東西，”計(jì)算折紙的先驅(qū)之一，美國(guó)數(shù)學(xué)學(xué)會(huì)的研究員羅伯特·朗說(shuō)，他在2001年放棄了成功的光學(xué)工程職業(yè)，成為一名全職的原創(chuàng)者。“它完成了我將其描述為20多年前開始的任務(wù)：一種從紙張上有效折疊任何指定形狀的計(jì)算方法。一路上，有幾個(gè)很好的示例拼圖：一種折疊任何形狀但不是非常有效的算法;一種有效折疊特定樹狀結(jié)構(gòu)系列而不是表面的算法;一種折疊樹木和曲面但不是每種形狀的算法。這個(gè)算法涵蓋了所有這些!算法令人驚訝的復(fù)雜，但這是因?yàn)樗侨娴?。它真正涵蓋了所有可能性。它不僅僅是一個(gè)抽象的證據(jù); 它很容易在計(jì)算上實(shí)現(xiàn)。“

Joseph O'Rourke，史密斯學(xué)院數(shù)學(xué)與計(jì)算機(jī)科學(xué)教授，如何折疊它的作者：聯(lián)系數(shù)據(jù)，折紙和多面體，同意。他說(shuō)：“之前所知道的是'作弊' - 用薄帶纏繞多面體 - 或者不能保證成功。” “他們的新算法保證產(chǎn)生折疊，而且與作弊相反，因?yàn)槎嗝骟w的每個(gè)面都被紙張的”無(wú)縫“面覆蓋，并且紙的邊界映射到多面體的邊界。歧管 - 他們的'防水'屬性。最后，實(shí)現(xiàn)折疊所需的額外結(jié)構(gòu)“閃光”都可以隱藏在內(nèi)部，因此是隱形的。“