1. Введение

Straight Skeleton 2D является очень красивым алгоритмом в компьютерной графике. На основе простых составляющих можно создавать разнообразные геометрические формы и придавать им фантастический вид в дизайне, архитектуре, ювелирном деле, компьютерных играх и др. Например:

Обработка текстовых символов (стилизация сделана кривой Гильберта)

2. Что такое Straight Skeleton?

Одно из определений Прямолинейного Скелета — это метод представления многоугольника его топологическим скелетом. Определение 2 (рус), Определение 3(eng). Этот алгоритм можно изобразить в виде графа для замкнутых контуров на примере следующих фигур (набор линий внутри контура каждой фигуры и есть Straight Skeleton):

Как выглядит алгоритм Straight Skeleton 2D для каждой отдельно взятой фигуры

Благодаря этому графу можно выполнить расчёт линий отступов на определённое расстояние от всех контуров:

Пример отступа на одинаковое расстояние от всех контуров

Математический рассчёт этого графа, как и самих отступов - это очень сложная задача, но рассматривать будем не её. Граф Straight Skeleton предоставляет возможность соединять между собой контуры нескольких отступов в объёмные фигуры. Примеры таких фигур и были продемонстрированы в начале статьи. Далее рассмотрим подробнее как это происходит.

3. С чего начинается расчёт объёмных фигур?

Расчёт объёмных фигур начинается с расчёта отступов (offsets), например, для фигур с одним внешним контуром offsets выглядят так:

Также возможны ситуации, когда объекты содержат отверстия и являются вложенными:

В этом примере заметно, что результат получается не просто с учётом отступов, а учитываются самопересечения отступов, их разделение на части и объединения, которые ещё лучше заметны на анимации:

Поведение offsets при изменении положения отступов

Видно, что поведение отступов не так однозначно (отдалённо напоминает магнитные поля). Отступы начинают разделяться на части, а в некоторых случаях и исчезать. Также offsets могут выходить и за пределы объекта и там объединяться с offsets от других, смежных shapes:

Выход offsets за пределы контуров (области внутри отверстий считаются наружными)

4. Как превратить отступы в объёмные фигуры?

В самом простом случае, чтобы получить объёмные фигуры, нужно разместить отступы на разных высотах и соединить их между собой. Для этого используются "профили". Профили - это плоские фигуры (для начала рассмотрим их в плоскости XY), у которых вершины являются отступами, но сами значения отступов берутся по оси X, а размещение полученных контуров по высоте берётся из значений по оси Y. Величина Z игнорируется (но в дальнейшем вы сами можете решить, что у вас будет отвечать за offset, а что за высоту). По сути задача сводится к тому, чтобы мысленно "установить" плоский профиль (profile) перпендикулярно горизонтальной форме (shape) и двигать profile вдоль контуров исходной shape, образуя замкнутую поверхность (на рисунке отступы подняты, чтобы соответствовать высотам в profile):

Далее я буду использовать терминологию profile и shape, чтобы разделять между собой эти фигуры, потому что к ним обеим одинаково подходят понятия фигуры/контуры/профили, и это будет вводить в заблуждение. С этого момента: profile - перпендикулярная форма (не обязательно замкнутая), a shape - горизонтальная форма (обязательно замкнутая).

Пример сложного profile и сложной shape в виде буквы S, написанной "обычным" шрифтом:

Пример отношения между profile и shape

Если соединить между собой точки profile по ходу перемещения вдоль контуров shape, то таким образом и будет получен результат в виде объёмной фигуры:

Расстановка и соединение контров для простого случая.

Возможны более сложные случаи соединения отступов между собой. Например, когда по соседству находятся два контура, один из которых разделён на три части, а другой на 2 части как в примере ниже:

Контур (1) разделён на три части, контур (2) разделён на 2 части

Чтобы образовалась поверхность, нужно соединить контуры (1) и (2) используя линии "прямого скелета". Топологически "прямой селет" этого полигона можно рассматривать как рельеф, а отступы (1) и (2) как горизонтали на географической карте. Контуры (1) и (2) соединятся либо напрямую, либо используют Straight Skeleton в качестве "гребня". Этот способ и создаёт поверхность соединения:

Соединение двух отступов с помощью рёбер "прямого скелета" (Straight Skeleton)

Если соединить подряд несколько отступов (при замкнутом profile), то получится замкнутая объёмная фигура:

Более сложные случаи соединения не будут рассматриваться в этой статье, чтобы не усложнять восприятие результата. Поэтому перейдём к практике.

5. Получение результата в виде полигональной сетки

Решение этой задачи в виде полигональной сетки существует. Для этого не потребуются дорогие программные пакеты. Это можно сделать на бесплатных инструментах Blender 3D и бесплатном addon, который называется Sverchok. Вам потребуется выполнить следующие действия:

Скачать и установить Blender 3D (3.6.x - 4.x): https://www.blender.org/download/
Скачать и установить Sverchok: https://github.com/nortikin/sverchok?tab=readme-ov-file#installation.
После установки Sverchok активируйте библиотеку pySVCGAL в настройках:
Перед тем как вы начнёте экспериментировать, можно почитать документацию по этому инструменту: https://nortikin.github.io/sverchok/docs/nodes/CAD/straight_skeleton_2d_offset.html

Далее будет небольшой tutorial. Желательно, чтобы у вас был опыт работы в Blender 3D. Также будет плюсом, если у вас есть опыт работы с геонодами, т.к. он поможет лучше понять принцип работы. Однако сами геоноды в этом tutorial не будут задействованы (хотя они и могут пригодиться в дальнейшем).

6. Про систему нодов

Система нодов - достаточно распространённый подход в построении алгоритмов в определённом контексте. В принципе это очень удобно, когда у вас есть набор функций, которые можно объединить без программирования, соединяя блоки между собой. Системы нодов есть в разных программах, например: Houdini, Unreal Engine, Rhinoceros 3D и др. Такой подход не лишён недостатков, но во многих случаях здорово помогает.

В Blender таких систем две - для материалов и для геометрии:

Примеры нодов для материалов и геометрии в Blender

Однако в Blender встроенная геометрическая система нодов не расширяема: вы не можете написать свой геометрический нод. К тому же имеющаяся система геометрических нодов ориентирована на художников, а не инженеров. Но в Blender есть достаточно мощное API для создания своей системы нодов, и самый продвинутый аддон, который использует это API - это Sverchok. Ещё до знакомства со Sverchok было желание сделать свою систему нодов, но, познакомившись со Sverchok, понял, что это то что нужно уже готовом виде, поэтому делать свою систему нодов отказался (поверьте на слово, что делать свою систему нодов очень сложно и долго). Система нодов в Sverchok хороша тем, что предоставляет возможность создать новый нод со своими параметрами. Обычно для визуализации в Python выбирают библиотеку типа matplotlib, а тут наоборот - если рассматривать Blender как систему визуализации, то получается, что в систему визуализации встроена возможность расширения через Python. Очень рекомендую обратить на такой подход внимание, т.к. в своё распоряжение вы получите как мощную систему визуализации (с доступом к языку шейдеров OSL при необходимости), так и мощную эко-систему на Python. По этой сумме факторов я и остановился на аддоне Sverchok.

7. Краткое описание нода Straight Skeleton 2D

Инструмент, работающий с алгоритмом Straight Skeleton 2D, является нодом с названием Straight Skeleton 2D Offset. Он выглядит следующим образом:

8. Как это работает?

Нод Straight Skeleton 2D offset работает с полигональными сетками как для shape, так и для profile. Поэтому на вход требуется передать параметры полигональной сетки shape и profile:

Для shape требуется набор vertices, edges и faces (edges не обязательно, оставлено для совместимости, не используется), а для profile нужны величины отступов (offsets), их высоты (altitudes) и последовательность индексов vertex для соединения отступов, чтобы получить объёмную фигуру (profile faces indexes).

Пример, как выглядит собранная минимальная схема в интерфейсе Blender:

Эта схема содержит только 5 нодов, если у вас уже подготовлены соответствующие mesh/полигональные сетки исходных данных.

8. Что в Blender может быть использовано как shape и profile?

8.1. Некоторые типы объектов Blender

Нод "Get objects data" может преобразовывать различные объекты Blender в полигональный mesh, который и используется как исходные данные для shape нода Straight Skeleton 2D Offset:

Получение mesh из элементов Text, Bezier curve 2d, Nurbs 2d

8.2. Импортирование внешних форматов

Blender может импортировать различные графические форматы, например, SVG в Bezier Curve 2D:

Пример с SVG будет немного позже.

8.3. Генераторы 2D Sverchok

Sverchok имеет встроенный набор генераторов полигональных mesh, а также различные скриптовые элементы, с помощью которых Sverchok может генерировать или обрабатывать полигональный mesh. Важно, чтобы полигональный mesh был именно 2D (в плоскости XY). Основное меню генераторов сосредоточено в меню Generator (Shift-A для вызова меню, стандартный шоткат для Blender):

Генераторы 2D могут подойти не только в качестве shape, но и в качестве profile. Также в Sverchok имеются ноды для работы с Bezier Curve, которые затем можно преобразовать в mesh и также использовать как shape или как profile.

9. Примеры

9.1. Пример 01. Использование Blender mesh

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

В качестве первого примера возьмём два квадрата. Один большой для shape, другой, поменьше, в качестве profile:

Теперь создадим схему и загрузим в неё эти два объекта (в рабочем поле Sverchok):

Загрузить shape и profile в соответствующие ноды "Get Objects Data":

Загрузка shape и profile

Если всё сделано без ошибок, то в 3D View поле Blender вы увидите результат:

Profile преобразовался в объёмный mesh

Profile "обошёл" внешний контур Shape и получился объёмный объект:

Первый результат (просмотр в режиме wireframe, shift-Z)

Если теперь перейти в режим редактирования профиля "Edit mode" и выполнить перемещение точек profile, то увидим следующие изменения:

Анимация перемещения точек profile для наглядности

Теперь проверим, как будет изменяться результат при изменении положения отдельных точек profile, и для примера добавим новую точку в profile:

Таким же образом можно менять и редактировать форму shape:

9.2. Пример 02. Обработка текста

Схема как и в примере 01. Только вместо создания shape на основе Blender mesh создайте текстовый объект:

Сделаем так, чтобы надпись была более интересной. Если вы работаете в Windows, то в Windows есть забавный шрифт "Jokerman". Сделаем profile из одного face, но уже не квадратный, а поинтереснее (но без самопересечений):

Пытаться заранее угадать результат в начале использования этого инструмента почти невыполнимая задача. Чуть подвинул геометрию и результат уже другой.

Вот так, "лёгким движением руки Habr превращается...":

Простите, как получилось, не специалист по материалам.

9.3. Пример 03. Импорт SVG

При переходе к импорту SVG картинок в Blender у вас появляется достаточно мощная возможность по стилизации разных векторных изображений. Например на сайте https://svgsilh.com/ находится большой архив SVG файлов на разные темы. Выберите для примера изображение силуэта лампочки https://svgsilh.com/image/2028330.html и сохраните его как SVG-файл:

Теперь импортируйте этот файл в Blender:

Ипортированный объект SVG преобразовался в Bezier Curve 2D

Blender при этом создаст объект типа Bezier Curve 2D. Проверьте, что после импорта включён "Fill mode": "Both". Теперь можно воспользоваться той же схемой преобразования объектов как и в примере 01, с загрузкой Bezier Curve с помощью нода "Get Objects Data":

Надеюсь, что к этому моменту уже стало понятно, как получать объёмные фигуры.

10. Отладка shape и вывод ошибок в геометрии

Некоторые файлы SVG содержат не совсем корректные данные. Например, контуры shape могут самопересекаться или ручки контролов могут быть нулевой длины. Алгоритм Straight Skeleton 2D не может нормально обрабатывать такие shape. Такие контуры надо исправлять. Для отображения ошибок в ноде Straight Skeleton 2D Offset предусмотрен нижний выходной сокет. Если алгоритм анализа входной геметрии для shape обнаружит ошибку, то выведет в этот сокет координаты точек геометрии, в которых обнаружена ошибка. Например, если объект является самопересекающимся face, то он не будет обработан алгоритмом, и в нижний сокет будут выведены координаты вершин, которые алгоритм не может обработать:

Ошибки могут восприниматься неоднозначно и требовать осмысления, но если вы будете обрабатывать фигуры с большим количеством объектов, то так будет проще отлаживать ошибки в топологии shape, например, а таком слож��ом shape трудно заметить ошибки:

Одна деталь содержит ошибку. Обведена красным

В данном случае причиной ошибки является то, что одна из ручек управления Bezier Curve является нулевой по длине. Blender может отобразить такой объект на экране, но алгоритм Straight Skeleton 2D не может корректно обработать такую ситуацию:

После исправления (немного подвинуть контрол, чтобы он стал не нулевой длины) расчёт выполнится корректно:

11. Параметр Cache

Самым сложным и затратным по времени в работе этого инструмента является расчёт самого Straight Skeleton. Чем сложнее геометрия, тем дольше и ощутимее затраты по времени (особенно при анимации). Если полигональная форма контура для shape будет состоять из нескольких сотен или тысяч точек, то время расчёта может достигать нескольких минут и больше. Однако, если вы не предполагаете менять геометрию shape в дальнейшем, то нет необходимости выполнять повторный расчёт Straight Skeleton при неизменной геометрии. В этом случае имеет смысл воспользоваться настройкой Cache:

Тогда нод только проверяет, что геометрия shape не поменялась, поэтому расчёт Straight Skeleton повторно выполняться не будет, а будет взят из внутреннего кэш. Это существенно сократит общее время расчёта. Останется только рассчитать offset-ы.

Примечание: параметр cache рассчитывает контрольную сумму геометрии входного объекта на основе координат, поэтому запоминает несколько предыдущих геометрий, а не только последнюю. Если вы предполагаете преобразовывать геометрию несколько раз, то эта настройка будет помнить предыдущие расчёты Straight Skeleton по этим геометриям.

12. Loop Selection

Одной из отличительных особенностей работы этого инструмента является приведение объекта к циклической топологии, т.е. все горизонтальные контуры зациклены без разрывов и Loop Selection охватывает полный контур без разрывов:

Пример Loop посложнее, где один внешний контур охватывает все буквы, а меньшие контуры могут части:

Это позволяет существенно упростить запекание, например, UV-map:

13. Немного технических деталей

Данный инструмент является кроссплатформенным, собран для Windows, Linux и MacOS, т.е. на тех платформах, где работает Blender 3.6.x и выше, но проверена работа только под Windows и Linux. Если у вас есть возможность запутить этот инструмент под MacOS, то буду очень признателен, если сообщите результаты, удалось ли запустить этот нод под MacOS (возможность собрать была, а проверить - нет).

14. Заключение

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

Если будут возникать какие-то проблемы (инструмент новый, сложный), то можете оставить issue: https://github.com/nortikin/sverchok/issues.

15. Файл для экспериментов

Некоторые примеры из этой статьи вы можете попробовать, скачав файл примеров в формате ==> .blend <==. Требуется установленный Blender 3.6.x и выше с установленным addon Sverchok.

16. Ещё примеры

Немного ювелирного урбанизма:

Анимация вращения кривой Гильберта по контуру объекта. Выполнено средствами Sverchok и Blender.

Пример использования индексов профиля в парном режиме

17. Материалы и документация

https://www.raybevel.com/ и https://www.tylermw.com/posts/rayverse/raybevel-introduction.html - Отличные картинки, которыми я вдохновлялся на начальном этапе.

https://en.wikipedia.org/wiki/Straight_skeleton - Описание алгоритма Straight Skeleton.

https://stackoverflow.com/questions/60132143/how-to-compute-the-mitered-offset-of-a-polygon-using-its-straight-skeleton - Отличная анимированная картинка. Тоже использовал для вдохновения.

https://doc.cgal.org/latest/Straight_skeleton_2/index.html - Документация по расчёту Straight Skeleton 2D из библиотеки CGAL.

Sverchok addon: github repository.

Sverchok documentation.

18. Благодарности

Илье Портнову, Никите Городецкому, Михаилу Белобородому. Отдельно благодарен Йохану за идею.

P.S.

Мне не удалось найти примеры подобного использования алгоритма Straight Skeleton 2D в других графических пакетах, даже платных, хотя расчёт самого Straight Skeleton 2D имеется, например, в RhinoCerros 3D. Основным источником примеров служил сайт https://www.tylermw.com/posts/rayverse/raybevel-introduction.html, но их решение носит явно ограниченный характер и точно не предназначено для художников и дизайнеров. Поиск аналогичного применения алгоритма Straight Skeleton 2D в Google Images также не находит ничего подобного. Примеров с отступами и крышами много.

Если у кого-то есть похожие примеры, можете ли показать? Хотелось бы увидеть и сравнить.

Straight Skeleton 2D — один из красивейших алгоритмов. Создание и визуализация