Как построить фрактал в python
3D моделирование в Python
Допустим, вам потребовалось на языке программирования python, построить трёхмерную модель некоторого объекта, затем визуализировать его, или подготовить файл для печати на 3D принтере. Существует несколько библиотек, помогающих в решении этих задач. Поговорим о том, как строить трёхмерные модели из точек, граней и примитивов в python. Как выполнять элементарные приемы 3D моделирования: перемещение, поворот, объединение, вычитание и другие.
Примеры кода можно найти в репозитории на GitHub.
Docker для исполнения примеров Pymesh:
sudo sh get-docker.sh
Компилятор g++ для PyTorch3d:
sudo apt install g++
Клонирование репозитория и установка библиотек:
git clone https://github.com/format37/python3d.git
pip install «git+https://github.com/facebookresearch/pytorch3d.git»
sudo apt-get install openscad
Numpy-stl: Обзор библиотеки
Строение полигональной модели:
Изображение из Википедии
Если вы не знакомы с Jupyter notebook
Что такое jupyter-ноутбук и зачем он нужен
Вершины пирамиды
Несмотря на то, что пока описаны только вершины, уже можно взглянуть как будет выглядеть модель, если соединить их треугольниками:
Изоповерхность пирамиды
Выглядит так, будто грани уже существуют. Но пока у нас есть только вершины. Чтобы сформировать stl файл, опишем грани, что можно сделать вручную, или предоставить эту работу функции spatial.ConvexHull из библиотеки scipy
В результате, массив faces содержит описание граней:
Например, последняя грань содержит числа 3, 1, 0. Значит грань собрана из точек 0-го, 1-го и 3-го элементов массива vertices:
Принцип описания граней через позиции вершин
Грани пирамиды
Как видно из рисунка, одна грань пирамиды оказалась перевернута. В последующих примерах, при построении фракталов, метод ConvexHull применяться не будет, так как он располагает точки грани в произвольном порядке, что приводит к переворачиванию некоторых граней.
Для просмотра stl файлов разработано довольно много программ. Одна из них называется Blender, доступна для скачивания и не требует оплаты за использование
Снимок экрана. Blender: numpy_stl_example_02.stl
Метод spatial.ConvexHull предназначен для вычисления выпуклой оболочки и хорошо справляется с пирамидой и кубом. Но в объектах, имеющих впадины, часть точек будет потеряна и при сборке stl произойдет ошибка из-за несоответствия количества граней количеству точек.
Это хорошо видно на примере в двух измерениях: numpy_stl_example_03.ipynb
В hull.simplices содержится описание граней:
Отобразим вершины и грани на графике:
Центральные точки не связаны с гранями
Для таких случаев придется найти альтернативу ConvexHull, или описать грани вручную:
Добавлено две грани: одна для нижней точки, одна для верхней
Numpy-stl: Построение фрактала
Пришло время построить фрактал. В numpy-stl нет функции булева вычитания. Для построения фрактала Menger Sponge пойдем от обратного. В нашем распоряжении два метода:
Построение элементарного mesh куба. Назовем его voxel.
Объединение нескольких voxel в единый mesh.
Построим фрактал из кубиков, как из конструктора.
Описание логики построения фрактала
Найдем сторону вокселя на глубинах 1 и 2. Упростим задачу, свернув фрактал с 3-х до 1-мерного случая:
Если фрактал второго уровня, длина стороны куба составит 1/(3**2) или 1/9. Составим набор кубов так, чтобы своим расположением они заполнили исходный куб. Получится воксельный куб. Вычислим области отверстий. Исключим воксели, которые входят в области отверстий. В завершение, объединим оставшиеся воксели в один объект и сохраним.
Numpy-stl: Рендеринг изображения
Для рендеринга, в функцию вывода plot_mesh, будем передавать mesh, загруженный из stl файла.
PyMesh: Обзор библиотеки
К сожалению, библиотека PyMesh не установилась у меня ни через менеджер пакетов PIP (несмотря на упоминание этого способа в документации), ни через Anaconda. Есть два способа установки.
Следуя инструкции, собрать из исходников.
Используя Docker контейнер. Выберем этот вариант, как более интересный. Запуск контейнера будет инициирован с параметрами. При помощи параметров запуска смонтируем в контейнер папку скриптов. Передадим необходимые параметры в скрипт. После завершения работы скрипта, контейнер будет удален. Если Docker вы уже установили следуя инструкции в начале статьи, более ничего устанавливать не нужно.
Если Docker вам не подходит, скомпилируйте PyMesh, следуя инструкции в документации. Такой вариант тоже будет работать.
Начнем с простого куба. В папке pymesh_examples находится скрипт pymesh_example_01.py. В дальнейшем, контейнер будет брать файлы именно из этой папки.
Из корня проекта запустим контейнер:
Что тут происходит?
Запускается контейнер pymesh. При первом запуске будет загружен образ, это займёт некоторое время.
Папка pymesh_examples монтируется в контейнер
В контейнере запускается python скрипт /pymesh_examples/pymesh_example_01.py
Импортируется библиотека pymesh
функция generate_box_mesh генерирует куб на основании двух противоположных вершин в точках [0,0,0] и [1,1,1]
функция save_mesh сохраняет объект в stl файл.
После исполнения, в папке pymesh_examples появляется файл pymesh_example_01.stl
Квадратное отверстие сделаем при помощи булева вычитания. Строим параллелепипед и вычитаем его из основного куба.
Снимок экрана. Blender: pymesh_example_02.stl
Здесь boolean применяется не только для вычитания. Всего доступно 4 операции:
Difference: A∖B (два последних примера)
Symmetric difference: A XOR B (изображение не представлено)
Иллюстрация применения операции boolean на сфере и кубе
Чтобы лучше понять как перемещать и вращать объект, бывает удобно временно заменить операцию Difference на Union.
Сделаем второе отверстие, переместим и повернем его.
В этом скрипте добавлены функции перемещения и поворота. При перемещении создается новый mesh объект на основании измененных вершин и граней исходного объекта. Для поворота, сначала при помощи класса Quaternion, описывается поворот, а затем, аналогично случаю с перемещением, используется создание нового, повернутого объекта, на основании вершин и граней исходного объекта, а также описания поворота.
О кватернионах есть довольно подробная статья:
Доступно о кватернионах и их преимуществах
В результате исполнения скрипта, получается куб с двумя пересекающимися отверстиями:
Снимок экрана. Blender: pymesh_example_03.stl
Перечисленных инструментов достаточно для построения фрактала.
PyMesh: Построение фрактала
В этом скрипте добавлен входящий параметр для передачи глубины вычисления фрактала. Для каждой глубины создается параллелепипед, который затем дважды копируется, поворачивается и смещается. Получается всего 3 параллелепипеда, которые вычитаются из основного куба. По одному на каждую грань. Операция повторяется x и y раз, чтобы заполнить все строки и колонки грани. Проверка на вычитание из пустого пространства не выполняется.
На этот раз при запуске необходимо явно указать глубину фрактала:
Исполняться он будет 5-15 минут. После исполнения, в папке pymesh_examples появляется stl файл:
Снимок экрана. Blender: pymesh_example_04_3.stl Если запросить фрактал 4-го уровня
Построение займет около 4-х часов, а размер файла составит 73 мб:
Снимок экрана. Blender: pymesh_example_04_4.stl
PyMesh: Рендеринг изображения
Mesh мы уже поворачивали, на этот раз повернём камеру.
Один из кадров анимации Показать анимацию
PyTorch3d: Обзор библиотеки
Построение пирамиды. Пример: pytorch3d_example_01.py
В примере ниже, сразу на устройстве описываем вершины, копируем их с устройства на хост. На основании вершин вычисляем грани. Сохраняем объект. Файл в формате obj можно импортировать в blender:
Снимок экрана. Blender: pytorch3d_example_01.obj
Обратите внимание на команду verts.cpu().numpy()
Вершины копируются с устройства на хост. Если вы работаете с GPU, каждое копирование будет замедлять работу алгоритма. В планировании архитектуры программы, количество операций копирования между хостом и устройством, по возможности, лучше свести к минимуму. Например, изначально имея на хосте список вершин, можно вычислить грани, не прибегая к копированию вершин с устройства на хост, как это будет сделано в следующем примере.
PyTorch3d: Построение фрактала
Использование GPU даёт некоторый прирост производительности.
В этом скрипте объявляем вершины минимального для указанной глубины вокселя. По знакомому из прошлого примера алгоритму вычисляем координаты отверстий в двух измерениях. Заполняем первичный куб вокселями, которые не попадают в пределы отверстий.
Cкорость расчета увеличилась на порядок, что позволило примерно за 5 часов построить фрактал 5 уровня:
Снимок экрана. Blender Menger Sponge 5 lvl
Размер stl файла составил 1.9 ГБ. При построении фрактала 5-го уровня, программа останавливалась из-за переполнения памяти видеокарты. Пришлось сборку объекта выполнять пакетами. Создавалось по 10 слоев “двумерных” фракталов, затем они присоединялись к основному объекту, до тех пор, пока не построился полный фрактал.
PyTorch3d: Рендеринг изображения
Помимо plotly визуализаций, pytorch3d отдельно выделяет рендеринг и подход нему тут довольно основательный, с текстурами и шейдерами.
SolidPython: Обзор библиотеки
SolidPython Самая богатая методами моделирования библиотека, среди перечисленных. 3D сцена описывается на python, в формате, очень похожем на openscad, генерируется openscad код, который пишется в scad файл и далее его можно редактировать в openscad или сразу сохранить в stl.
Снимок экрана. Openscad: solidpython_example_01.scad
solidpython удобно отлаживать. С одной стороны экрана открыт scad файл, с другой jupyter notebook. При исполнении scad_render_to_file картинка в openscad автоматически обновляется.
Если нужен stl, openscad умеет рендерить файлы этого формата через команды консоли. Пример вызова из jupyter notebook:
Снимок экрана. Blender: solidpython_example_01.stl
Общий принцип такой: Любая функция возвращает объект. Если над объектом необходимо произвести некоторое действие, объект (или список объектов) передается в круглых скобках после вызова соответствующей функции.
Тут разрешение регулируется параметром slices.
Снимок экрана. Openscad: solidpython_example_02.scad
SolidPython: Построение фрактала
SolidPython: Рендеринг изображения
Сформируем серию изображений последней сцены, поворачивая камеру в каждом изображении.
Кроме того, solidpython предлагает формирование анимации средствами openscad. В документации об этом есть небольшой раздел с примером.
Напоследок рассмотрим код, использованный для построения сцены из заголовка статьи.
Сравнение библиотек
Сравнение производительности не совсем объективно, так как имеются значительные различия в алгоритмах. В Pymesh и SolidPython применялось вычитание, тогда как в Numpy-stl и Pytorch3d объединение mesh.
(Время вычисления фрактала 3-го уровня, в секунду)
3D моделирование в Python
Допустим, вам потребовалось на языке программирования python, построить трёхмерную модель некоторого объекта, затем визуализировать его, или подготовить файл для печати на 3D принтере. Существует несколько библиотек, помогающих в решении этих задач. Поговорим о том, как строить трёхмерные модели из точек, граней и примитивов в python. Как выполнять элементарные приемы 3D моделирования: перемещение, поворот, объединение, вычитание и другие.
Примеры кода можно найти в репозитории на GitHub.
Docker для исполнения примеров Pymesh:
sudo sh get-docker.sh
Компилятор g++ для PyTorch3d:
sudo apt install g++
Клонирование репозитория и установка библиотек:
git clone https://github.com/format37/python3d.git
pip install «git+https://github.com/facebookresearch/pytorch3d.git»
sudo apt-get install openscad
Numpy-stl: Обзор библиотеки
Изображение из Википедии
Если вы не знакомы с Jupyter notebook
Вершины пирамиды
Несмотря на то, что пока описаны только вершины, уже можно взглянуть как будет выглядеть модель, если соединить их треугольниками:
Изоповерхность пирамиды
Выглядит так, будто грани уже существуют. Но пока у нас есть только вершины. Чтобы сформировать stl файл, опишем грани, что можно сделать вручную, или предоставить эту работу функции spatial.ConvexHull из библиотеки scipy
В результате, массив faces содержит описание граней:
Например, последняя грань содержит числа 3, 1, 0. Значит грань собрана из точек 0-го, 1-го и 3-го элементов массива vertices:
Принцип описания граней через позиции вершин
Грани пирамиды
Как видно из рисунка, одна грань пирамиды оказалась перевернута. В последующих примерах, при построении фракталов, метод ConvexHull применяться не будет, так как он располагает точки грани в произвольном порядке, что приводит к переворачиванию некоторых граней.
Для просмотра stl файлов разработано довольно много программ. Одна из них называется Blender, доступна для скачивания и не требует оплаты за использование
Снимок экрана. Blender: numpy_stl_example_02.stl
Метод spatial.ConvexHull предназначен для вычисления выпуклой оболочки и хорошо справляется с пирамидой и кубом. Но в объектах, имеющих впадины, часть точек будет потеряна и при сборке stl произойдет ошибка из-за несоответствия количества граней количеству точек.
Это хорошо видно на примере в двух измерениях: numpy_stl_example_03.ipynb
В hull.simplices содержится описание граней:
Отобразим вершины и грани на графике:
Центральные точки не связаны с гранями
Для таких случаев придется найти альтернативу ConvexHull, или описать грани вручную:
Добавлено две грани: одна для нижней точки, одна для верхней
Numpy-stl: Построение фрактала
Пришло время построить фрактал. В numpy-stl нет функции булева вычитания. Для построения фрактала Menger Sponge пойдем от обратного. В нашем распоряжении два метода:
Построение элементарного mesh куба. Назовем его voxel.
Объединение нескольких voxel в единый mesh.
Построим фрактал из кубиков, как из конструктора.
Описание логики построения фрактала
Найдем сторону вокселя на глубинах 1 и 2. Упростим задачу, свернув фрактал с 3-х до 1-мерного случая:
Если фрактал второго уровня, длина стороны куба составит 1/(3**2) или 1/9. Составим набор кубов так, чтобы своим расположением они заполнили исходный куб. Получится воксельный куб. Вычислим области отверстий. Исключим воксели, которые входят в области отверстий. В завершение, объединим оставшиеся воксели в один объект и сохраним.
Numpy-stl: Рендеринг изображения
Для рендеринга, в функцию вывода plot_mesh, будем передавать mesh, загруженный из stl файла.
PyMesh: Обзор библиотеки
К сожалению, библиотека PyMesh не установилась у меня ни через менеджер пакетов PIP (несмотря на упоминание этого способа в документации), ни через Anaconda. Есть два способа установки.
Следуя инструкции, собрать из исходников.
Используя Docker контейнер. Выберем этот вариант, как более интересный. Запуск контейнера будет инициирован с параметрами. При помощи параметров запуска смонтируем в контейнер папку скриптов. Передадим необходимые параметры в скрипт. После завершения работы скрипта, контейнер будет удален. Если Docker вы уже установили следуя инструкции в начале статьи, более ничего устанавливать не нужно.
Если Docker вам не подходит, скомпилируйте PyMesh, следуя инструкции в документации. Такой вариант тоже будет работать.
Начнем с простого куба. В папке pymesh_examples находится скрипт pymesh_example_01.py. В дальнейшем, контейнер будет брать файлы именно из этой папки.
Из корня проекта запустим контейнер:
Что тут происходит?
Запускается контейнер pymesh. При первом запуске будет загружен образ, это займёт некоторое время.
Папка pymesh_examples монтируется в контейнер
В контейнере запускается python скрипт /pymesh_examples/pymesh_example_01.py
Импортируется библиотека pymesh
функция generate_box_mesh генерирует куб на основании двух противоположных вершин в точках [0,0,0] и [1,1,1]
функция save_mesh сохраняет объект в stl файл.
После исполнения, в папке pymesh_examples появляется файл pymesh_example_01.stl
Квадратное отверстие сделаем при помощи булева вычитания. Строим параллелепипед и вычитаем его из основного куба.
Снимок экрана. Blender: pymesh_example_02.stl
Здесь boolean применяется не только для вычитания. Всего доступно 4 операции:
Difference: A∖B (два последних примера)
Symmetric difference: A XOR B (изображение не представлено)
Иллюстрация применения операции boolean на сфере и кубе
Чтобы лучше понять как перемещать и вращать объект, бывает удобно временно заменить операцию Difference на Union.
Сделаем второе отверстие, переместим и повернем его.
В этом скрипте добавлены функции перемещения и поворота. При перемещении создается новый mesh объект на основании измененных вершин и граней исходного объекта. Для поворота, сначала при помощи класса Quaternion, описывается поворот, а затем, аналогично случаю с перемещением, используется создание нового, повернутого объекта, на основании вершин и граней исходного объекта, а также описания поворота.
О кватернионах есть довольно подробная статья:
В результате исполнения скрипта, получается куб с двумя пересекающимися отверстиями:
Снимок экрана. Blender: pymesh_example_03.stl
Перечисленных инструментов достаточно для построения фрактала.
PyMesh: Построение фрактала
В этом скрипте добавлен входящий параметр для передачи глубины вычисления фрактала. Для каждой глубины создается параллелепипед, который затем дважды копируется, поворачивается и смещается. Получается всего 3 параллелепипеда, которые вычитаются из основного куба. По одному на каждую грань. Операция повторяется x и y раз, чтобы заполнить все строки и колонки грани. Проверка на вычитание из пустого пространства не выполняется.
На этот раз при запуске необходимо явно указать глубину фрактала:
Исполняться он будет 5-15 минут. После исполнения, в папке pymesh_examples появляется stl файл:
Снимок экрана. Blender: pymesh_example_04_3.stl Если запросить фрактал 4-го уровня
Построение займет около 4-х часов, а размер файла составит 73 мб:
Снимок экрана. Blender: pymesh_example_04_4.stl
PyMesh: Рендеринг изображения
Mesh мы уже поворачивали, на этот раз повернём камеру.
Один из кадров анимации Показать анимацию
PyTorch3d: Обзор библиотеки
В примере ниже, сразу на устройстве описываем вершины, копируем их с устройства на хост. На основании вершин вычисляем грани. Сохраняем объект. Файл в формате obj можно импортировать в blender:
Снимок экрана. Blender: pytorch3d_example_01.obj
Обратите внимание на команду verts.cpu().numpy()
Вершины копируются с устройства на хост. Если вы работаете с GPU, каждое копирование будет замедлять работу алгоритма. В планировании архитектуры программы, количество операций копирования между хостом и устройством, по возможности, лучше свести к минимуму. Например, изначально имея на хосте список вершин, можно вычислить грани, не прибегая к копированию вершин с устройства на хост, как это будет сделано в следующем примере.
PyTorch3d: Построение фрактала
Использование GPU даёт некоторый прирост производительности.
В этом скрипте объявляем вершины минимального для указанной глубины вокселя. По знакомому из прошлого примера алгоритму вычисляем координаты отверстий в двух измерениях. Заполняем первичный куб вокселями, которые не попадают в пределы отверстий.
Cкорость расчета увеличилась на порядок, что позволило примерно за 5 часов построить фрактал 5 уровня:
Снимок экрана. Blender Menger Sponge 5 lvl
Размер stl файла составил 1.9 ГБ. При построении фрактала 5-го уровня, программа останавливалась из-за переполнения памяти видеокарты. Пришлось сборку объекта выполнять пакетами. Создавалось по 10 слоев “двумерных” фракталов, затем они присоединялись к основному объекту, до тех пор, пока не построился полный фрактал.
PyTorch3d: Рендеринг изображения
Помимо plotly визуализаций, pytorch3d отдельно выделяет рендеринг и подход нему тут довольно основательный, с текстурами и шейдерами.
SolidPython: Обзор библиотеки
SolidPython Самая богатая методами моделирования библиотека, среди перечисленных. 3D сцена описывается на python, в формате, очень похожем на openscad, генерируется openscad код, который пишется в scad файл и далее его можно редактировать в openscad или сразу сохранить в stl.
Снимок экрана. Openscad: solidpython_example_01.scad
solidpython удобно отлаживать. С одной стороны экрана открыт scad файл, с другой jupyter notebook. При исполнении scad_render_to_file картинка в openscad автоматически обновляется.
Если нужен stl, openscad умеет рендерить файлы этого формата через команды консоли. Пример вызова из jupyter notebook:
Снимок экрана. Blender: solidpython_example_01.stl
Общий принцип такой: Любая функция возвращает объект. Если над объектом необходимо произвести некоторое действие, объект (или список объектов) передается в круглых скобках после вызова соответствующей функции.
Тут разрешение регулируется параметром slices.
Снимок экрана. Openscad: solidpython_example_02.scad
SolidPython: Построение фрактала
SolidPython: Рендеринг изображения
Сформируем серию изображений последней сцены, поворачивая камеру в каждом изображении.
Кроме того, solidpython предлагает формирование анимации средствами openscad. В документации об этом есть небольшой раздел с примером.
Напоследок рассмотрим код, использованный для построения сцены из заголовка статьи.
Сравнение библиотек
Сравнение производительности не совсем объективно, так как имеются значительные различия в алгоритмах. В Pymesh и SolidPython применялось вычитание, тогда как в Numpy-stl и Pytorch3d объединение mesh.
(Время вычисления фрактала 3-го уровня, в секунду)