В 1999 году Эрик Демейн (Erik Demaine), тогда еще 18-летний аспирант Университета Уотерлу в Канаде описал алгоритм, который мог бы определить, как свернуть лист бумаги в любую мыслимую трехмерную форму. Это была значимая веха в области вычислительных оригами, но алгоритм не мог создать схемы для складывания, которые можно было бы действительно применить на практике.

По существу, алгоритм брал за основу очень длинную полоску бумаги и сворачивал ее в желаемую форму. Полученные структуры, как правило, имели много линий швов, где слои бумажной ленты накладывались друг на друга, образуя складки, из-за чего получаемые конструкции были не очень прочными.

В 1999 году Демейн доказал, что можно сложить любой полиэдр, но способ, которым этого можно достичь, оказался не самым эффективным. Предложенный метод работает, если исходный лист бумаги длинный и узкий. Но если нужно работать, например, с квадратным листом, то алгоритм все равно будет сначала складывать бумагу до тонкой полосы, растрачивая весь материал почем зря.

Теперь профессор электротехники и информатики Массачусетского технологического института Эрик Демейн и его коллега Томохиро Тачи из Токийского университета готовы объявить о завершении квеста, который начался с работы 1999 года: в июле 2017 года на симпозиуме по вычислительной геометрии они представят алгоритм для создания оригами, который гарантирует минимально возможное количество швов. Демейн и Тачи также работают над внедрением алгоритма в новой версии Origamizer — бесплатного ПО для генерации рисунков с оригами. Первая версия была выпущена Тачи в 2008 году.

Алгоритм исследователей разрабатывает шаблоны сгибов для создания любого многогранника, то есть трехмерной поверхности, состоящей из многих плоскостей. Программное обеспечение для создания компьютерной графики моделирует трехмерные объекты как многогранники, состоящие из множества крошечных треугольников.



Строго говоря, гарантия того, что складывание листа будет включать минимальное количество швов означает, что он сохраняет «границы» оригинального листа бумаги. Предположим, у вас есть круглый лист бумаги и вы хотите сложить из него чашку. Оставив меньший круг в центре этого листа, вы можете соединить стороны.

В этом случае граница чашки — ее обод — такая же, как граница развернутой окружности — ее внешний край. То же самое делал предыдущий алгоритм Демейна: чаша, которую он предлагал, складывалась из тонкой полоски бумаги, завернутой в катушку, и, вероятно, не смогла бы удерживать воду.

Математическое свойство, различающее оба метода, ученые называют «водонепроницаемостью». Так новый алгоритм сохраняет границу оригинального листа бумаги на границе поверхности, которую пользователь пытается сделать. Закрытая поверхность, такая как сфера, не имеет границы, поэтому оригами потребует шва, где встретятся эти границы. Мы не можем получить полностью замкнутую поверхность, но можем выбрать, где поставить границу.


Складывание поверхности по предыдущему алгоритму Демейна (слева) и «водонепроницаемому» (справа). Граница листа обозначена толстой линией.

На первом этапе алгоритм проецирует грани нужной фигуры на плоскую поверхность. Но в то время, когда грани будут соприкасаться, когда сворачивание завершено, они могут быть довольно далеко друг от друга на плоской поверхности. Пользователь складывает все дополнительные материалы и объединяет грани фигуры. Складывание дополнительного материала может быть очень сложным процессом. Сгибы, объединяющие несколько сторон, могут включать в себя десятки или даже сотни отдельных сгибов.


Схема Orgamizer для складывания кролика

Разработка метода автоматического расчета инструкций оригами включала в себя несколько разных идей, но центральной стала та, которую можно было бы назвать приблизительно соответствующей диаграмме Вороного. Чтобы понять эту концепцию, авторы предлагают представить себе равнину, покрытую травой, На ней одновременно включается ряд огней, и все они распространяются во всех направлениях с одинаковой скоростью.

Диаграмма Вороного, названная в честь российского ученого XIX века Геория Вороного, описывается как место, где установлены огни, так и границы, с которыми встречаются прилегающие огни. В алгоритме Демейна и Тачи границы диаграммы Вороного определяют места сгиба бумаги.

Работа ученых получила весьма благосклонные отзывы от других экспертов в этой области. Роберт Ланг (Robert Lang), один из пионеров вычислительных оригами и член Американского математического общества, который в 2001 году отказался от успешной карьеры в области оптической техники чтобы стать полноправным оригамистом, отметил, что это очень впечатляющий материал.

Ланг считает, что ученым удалось удачно завершить долгий путь по созданию вычислительного метода для эффективного сгибания листа бумаги любой заданной формы, который начался 20 лет назад. По пути некоторым исследователям удавалось продемонстрировать несколько вариантов решения проблемы, которые нельзя было назвать универсальными. Были разработаны алгоритмы складывания бумаги любой формы, которые оказались не очень эффективными, а также алгоритм складывания древовидных форм, но не поверхностей. По его мнению, алгоритм Демейна и Точи довольно сложен, но это связано в большей степени с тем, что он является и всеобъемлющим.

doi: 10.4230/LIPIcs.SoCG.2017.34