Разложение 3d-сетки на 2d-сетку

Когда я прочитал ваш вопрос, мне пришли в голову слова «алгоритм автоматического создания бумаги». Поэтому я погуглил и нашел Модели из бумаги с использованием обобщенных цилиндров (pdf) Massarwi et al.

Мы предлагаем новый метод изготовления развернутых бумажных макетов округлых фигурок игрушечных животных из треугольных сеток с помощью аппроксимации на основе полос. Хотя в принципе триангулированную модель можно развернуть, просто сохранив как можно больше ее связности при проверке на наличие пересекающихся треугольников в развернутой плоскости, создать шаблон с десятками тысяч треугольников нереально. Наш подход заключается в аппроксимации сетчатой ​​модели набором непрерывных треугольных полос без внутренних вершин. Изначально мы разбиваем нашу сетку на части, соответствующие особенностям модели. Мы сегментируем каждую часть на зональные области, группируя треугольники, которые находятся на близких топологических расстояниях от границы части. Мы генерируем треугольные полосы, упрощая сетку с сохранением границ зональных областей и дополнительных линий разреза. Затем создается узор, просто разворачивая набор полосок. Отличительной чертой нашего метода является то, что мы аппроксимируем сетчатую модель набором непрерывных полос, а не другими линейчатыми поверхностями, такими как части конусов или цилиндров. Таким образом, аппроксимированный развернутый шаблон может быть сгенерирован с использованием только операций с сеткой и простого алгоритма развертывания. Кроме того, набор полосок можно создать, просто согнув бумагу (без разрыва краев), и они могут представлять гладкие элементы исходных моделей сетки.

Существует также более ранняя связанная статья под названием Модели бумажных поделок из сетки (9MB pdf) Shatz et al.

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

Источник: http://www.ee.technion.ac.il/~ayellet/images/sel-papers-pic-5.jpg

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

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

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

Когда у вас есть дерево, начните с рисования начального лица в начале координат. Затем пройдитесь по дереву и добавьте новые грани, вычислив новую вершину как пересечение двух окружностей с радиусами, соответствующими длинам ребер в исходной сетке. Расположение вкладок соответствует ребрам, которые были в исходной сетке, но не в сглаживаемом дереве.

Пользовательские разрезы могут обрабатываться как удаление ребер перед шагом дерева.

Некоторыми недостатками этой техники является то, что она будет успешно создавать перекрывающиеся части в развертке, и это зависит от нахождения хорошей начальной грани. Я попробовал Floyd-Warshal, чтобы найти грань минимального диаметра для начала, но его поведение O (n ^ 3) приводило к чрезмерно длинным перерывам на кофе. С перекрывающимися частями можно было бы справиться, пометив эту ветвь дерева как «незавершенную», пропустив ее и повторно запустив алгоритм на всех неполных гранях.

Я знаю, что это не ответ, но это связано. Программа Lamina бывшего специалиста по графике SGI Пола Хеберли (Paul Haeberli) является решением этой проблемы.