НЕ ЗНАЮ,
говорю от фонаря, но мне кажется, что оригами-алгоритм вещь перспективная не только с точки зрения развития численных методов в геометрии, но например для такой практической области, как 3D печать.
Кролик.
В 1999 году студент Университета Ватерлоо Эрик Демейн воплотил мечту любителей оригами - алгоритм, рассчитывающий, как сложить лист бумаги, чтобы получить любую трёхмерную фигуру. Но на практике он был в общем-то бесполезен: алгоритму требовался очень длинный лист, получившиеся структуры состояли из кучи сгибов и были непрочными. Теперь Демейн, ныне профессор Массачусетского технологического института (MTI), научил своё детище выдавать реалистичные конструкции с минимальным количеством швов.
«В 1999 мы доказали, что из бумаги можно сложить любой многогранник, но придуманный нами способ был крайне неэффективным, - объясняет Демейн. - Он работает, когда лист бумаги сверхдлинный и узкий. Но если вы начнёте с квадратного куска бумаги, старый алгоритм в конце концов сложит его в узкую полоску, истратив почти весь материал. Новый алгоритм обещает быть гораздо более эффективным. Это совершенно новая стратегия создания многогранников».
3D-снежинка или гиперэдрон.
Тот факт, что алгоритм сможет складывать фигуры с минимальным количеством швов, означает, что он сохранит «границы» листа. Представьте, что у вас есть круглый кусок бумаги, и вы хотите сложить из него стаканчик. Вы можете оставить небольшой кружок в центре плоским, а стороны загнуть гармошкой. В этом случае края стакана - это внешняя граница круга. Но ранняя версия алгоритма так не работала: стакан состоял бы из много раз свёрнутой тонкой полоски бумаги, и, вероятно, не мог бы удерживать воду.
«Новый алгоритм должен предлагать более практичные способы складывания листа, - рассказывает Демейн. - Мы не знаем, как оценить это математически, за исключением того, что на практике он, похоже, работает гораздо лучше. Однако одно математическое свойство всё-таки позволяет ясно различать два метода: в результате работы нового алгоритма граница листа бумаги совпадает с границей поверхности, которую вы пытаетесь получить. Мы называем это «водонепроницаемостью».
У замкнутых поверхностей - например, у сферы - границ нет, поэтому при создании их оригами-версий, в тех местах, где границы листа встречаются, образуются швы. Алгоритм позволяет выбирать, где расположить эти швы. «Вы не можете получить полностью водонепроницаемую замкнутую поверхность, потому что где-то должны быть границы, но вы можете выбирать, куда их поместить».
Сложить нужную фигуру так, чтобы не оставалось лишнего материала - очень сложно: иногда для этого нужны десятки и сотни сгибов. Чтобы рассчитать, где должны располагаться эти сгибы, Демейн и его коллега Томохиро Тати (яп. 舘 知宏, англ. Tomohiro Tachi) использовали несколько методов, но главным стало построение диаграммы Вороного. Описать эту концепцию можно таким образом: представьте травянистую равнину, на которой одновременно зажгли несколько костров, причём огни распространяются по всем направлениям с одинаковой скоростью. Диаграмма Вороного описывает расположение костров и границы, где встречаются соседние огни. Эти границы и определяют места сгиба при работе нового алгоритма.
«Это очень впечатляюще, - говорит бывший инженер, а ныне оригамист Роберт Ланг (Robert Lang). Он назвал работу Демейна и Тати завершением двадцатилетнего квеста. «За это время мы видели, как разные учёные демонстрируют кусочки этого паззла: алгоритм, который складывает любую фигуру, но делает это не очень эффективно; алгоритм, который эффективно складывает определённые семейства древоподобных фигур, но не поверхности; алгоритм, складывающий деревья и поверхности, но не все фигуры. Новый алгоритм покрывает все эти возможности!» Ланг также добавил, что его легко реализовать на практике. Уже известно, что алгоритм станет основой для следующей версии Origamizer - эта программа авторства Тати рассчитывает расположение сгибов для фигурок оригами. Вот в этом ролике Тати показывает её в действии :
(По материалам MIT)
Кролик.
В 1999 году студент Университета Ватерлоо Эрик Демейн воплотил мечту любителей оригами - алгоритм, рассчитывающий, как сложить лист бумаги, чтобы получить любую трёхмерную фигуру. Но на практике он был в общем-то бесполезен: алгоритму требовался очень длинный лист, получившиеся структуры состояли из кучи сгибов и были непрочными. Теперь Демейн, ныне профессор Массачусетского технологического института (MTI), научил своё детище выдавать реалистичные конструкции с минимальным количеством швов.
«В 1999 мы доказали, что из бумаги можно сложить любой многогранник, но придуманный нами способ был крайне неэффективным, - объясняет Демейн. - Он работает, когда лист бумаги сверхдлинный и узкий. Но если вы начнёте с квадратного куска бумаги, старый алгоритм в конце концов сложит его в узкую полоску, истратив почти весь материал. Новый алгоритм обещает быть гораздо более эффективным. Это совершенно новая стратегия создания многогранников».
3D-снежинка или гиперэдрон.
Тот факт, что алгоритм сможет складывать фигуры с минимальным количеством швов, означает, что он сохранит «границы» листа. Представьте, что у вас есть круглый кусок бумаги, и вы хотите сложить из него стаканчик. Вы можете оставить небольшой кружок в центре плоским, а стороны загнуть гармошкой. В этом случае края стакана - это внешняя граница круга. Но ранняя версия алгоритма так не работала: стакан состоял бы из много раз свёрнутой тонкой полоски бумаги, и, вероятно, не мог бы удерживать воду.
«Новый алгоритм должен предлагать более практичные способы складывания листа, - рассказывает Демейн. - Мы не знаем, как оценить это математически, за исключением того, что на практике он, похоже, работает гораздо лучше. Однако одно математическое свойство всё-таки позволяет ясно различать два метода: в результате работы нового алгоритма граница листа бумаги совпадает с границей поверхности, которую вы пытаетесь получить. Мы называем это «водонепроницаемостью».
У замкнутых поверхностей - например, у сферы - границ нет, поэтому при создании их оригами-версий, в тех местах, где границы листа встречаются, образуются швы. Алгоритм позволяет выбирать, где расположить эти швы. «Вы не можете получить полностью водонепроницаемую замкнутую поверхность, потому что где-то должны быть границы, но вы можете выбирать, куда их поместить».
Click to viewСложить нужную фигуру так, чтобы не оставалось лишнего материала - очень сложно: иногда для этого нужны десятки и сотни сгибов. Чтобы рассчитать, где должны располагаться эти сгибы, Демейн и его коллега Томохиро Тати (яп. 舘 知宏, англ. Tomohiro Tachi) использовали несколько методов, но главным стало построение диаграммы Вороного. Описать эту концепцию можно таким образом: представьте травянистую равнину, на которой одновременно зажгли несколько костров, причём огни распространяются по всем направлениям с одинаковой скоростью. Диаграмма Вороного описывает расположение костров и границы, где встречаются соседние огни. Эти границы и определяют места сгиба при работе нового алгоритма.
«Это очень впечатляюще, - говорит бывший инженер, а ныне оригамист Роберт Ланг (Robert Lang). Он назвал работу Демейна и Тати завершением двадцатилетнего квеста. «За это время мы видели, как разные учёные демонстрируют кусочки этого паззла: алгоритм, который складывает любую фигуру, но делает это не очень эффективно; алгоритм, который эффективно складывает определённые семейства древоподобных фигур, но не поверхности; алгоритм, складывающий деревья и поверхности, но не все фигуры. Новый алгоритм покрывает все эти возможности!» Ланг также добавил, что его легко реализовать на практике. Уже известно, что алгоритм станет основой для следующей версии Origamizer - эта программа авторства Тати рассчитывает расположение сгибов для фигурок оригами. Вот в этом ролике Тати показывает её в действии :
(По материалам MIT)