Привет, Хабр!

Меня всё также зовут Андрей Гринблат, и в первой части я начал рассказывать о такой технологии, как ray marching, и о нормированных пространствах. В этой части начнём с построения простых геометрических фракталов — губки Менгера и тетраэдра Серпинского, затем построим IFS-фракталы, рассмотрим технику орбитальных ловушек, и в завершение построим фрактал «Ящик Мандельброта», или Мандельбокс.

Губка Менгера

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

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

SDF операции вычитания объектов было описано ранее, а сам «крест» есть объединение трёх «вытянутых» кубов. Полученное ��наивное» SDF не является точным, но для наших целей более чем удовлетворительно.

SDF креста получаем так: вытягиваем по осям, причём вытянуть нужно более чем в три раза, поэтому знаменатель сделаем равным, например, 4:

Получим SDF в первой итерации:

Отрисуем первую итерацию

Видим, что внутри губки не учитываются тени и дополнительное рассеивание света: выглядит так, будто освещенность внутри губки, такая же, как и снаружи. Добавим простую ложную окклюзию, это сделает изображение более реалистичным. Для этого умножим вектор цвета фрагмента (RGB-ую часть в данном случае) на что-нибудь, например, такое:

, где — параметр окклюзии, а — количество шагов по лучу.

Следующий и остальные шаги в построении губки — это уменьшение «креста» и удаление его из уменьшенных кубов, то есть масштабирование и повторение домена. Будем как бы слоями удалять «кресты»: на первом шаге — слой из 1 «креста», на втором — из 20, уменьшенных втрое, на третьем — из 400, уменьшенных ещё втрое, и так далее Для этого сделаем, например, такой цикл:

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

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

Простейшие преобразования и операции с фракталом

Описанные ниже преобразования и операции можно применять не только к губке Менгера, но и ко многим другим фракталам. Это позволяет увеличить вариативность получаемых форм. Существует и множество других интересных преобразований: искажения, добавление шума в форму — всё ограничено лишь вашей фантазией!

Но для начала сделаем немного более привлекательным окружающее губку пространство: на плоскости сделаем паркет и добавим текстуру на небесную сферу.

Сделаем срез губки.

Посмотрим на губку в различным пространствах.

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

С переносами всё очевидно: просто прибавляем вектор переноса. А вот повороты реализуем через умножение кватернионов, которое нам также понадобится для построения трёхмерной проекций, четырёхмерных фракталов Жулиа и Мандельброта. Кроме того, группа кватернионов SU(2), являющаяся двулистным накрытием группы вращений в трёхмерном пространстве SO(3), более удобна в использовании. По сравнению с матрицами из SO(3) кватернионы обеспечивают более точные и стабильные вращения, не накапливая численных ошибок и всегда выполняя поворот по кратчайшему пути.

Такие преобразования с точками приводят к изменениям формы фрактала. Примеры: один, два.

Рассмотрим построение других фракталов. Начнём с тетраэдра Серпинского.

Тетраэдр Серпинского

Нулевая итерация тетраэдра Серпинского — это обычный тетраэдр. Давайте найдём его SDF.

Расстояние от точки до тетраэдра — это минимальное из расстояний от точки до его граней. Если точка находится внутри тетраэдра, то минимальное из расстояний до граней окажется равным минимальному из расстояний до плоскостей, содержащих эти грани. Находим его и берём со знаком «-», так как область внутренняя. Если же точка находится снаружи, то придётся находить ра��стояние именно до граней.

Выясним расположение нашей точки и самого тетраэдра относительно его граней, посмотрим, по одну или по разные стороны они лежат. Для этого вычислим пять определителей размером 4×4.

— вершины тетраэдра;

— текущая точка;

• если , то точка и тетраэдр находятся по разные стороны от -й грани;

• если , то точка и тетраэдр находятся по одну сторону от -й грани.

Если все , то текущая точка расположена внутри тетраэдра

Если ровно одно , то в качестве нижней грани расстояния можно взять расстояние от P до плоскости, определяемой вершинами с номерами:

Если ровно два значения отрицательны, , , то в качестве нижней грани расстояния можно взять расстояние от до прямой, определяемой вершинами с номерами:

Наконец, если только одно , то в качестве расстояния можно взять расстояние от до -ой вершины тетраэдра.

Эти вычисления можно оптимизировать. Например, заменив вычисления определителей на соответствующие вычисления векторных и скалярных произведений, которые также используются в дальнейшем.

Такая функция не является точным SDF, но она квази-SDF тетраэдра и позволяет построить его изображение. Чтобы довести функцию до точного SDF, необходимо ещё рассмотреть проекцию текущей точки на плоскость соответствующих грани и/или ребра.

Нарисуем правильный тетраэдр с вершинам:

Рассмотрим следующую — первую — итерацию тетраэдра Серпинского, она представляет собой тетраэдр, из которого вынули октаэдр. Октаэдр построим как сферу в пространстве с манхэттенской нормой.

Получим изображение:

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

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

Для примера рассмотрим ещё фрактал — «многоэтажные дома Дзюбы».

Многоэтажные дома Дзюбы

Для его построения берут куб, из которого удаляют «сферы» (в различных вариантах нормы пространства).

Получим изображения:

Перейдём к построению октаэдра Серпинского.

Октаэдр Серпинского

Рассмотрим другие, возможно, более естественные методы построения трёхмерных фракталов.

Октаэдр Серпинского представляет собой притягивающее множество (аттрактор) системы итерируемых функций (IFS). Эта система, в данном случае, состоит из сжимающих гомотетий с центрами в вершинах октаэдра и коэффициентом сжатия, равным 0,5.

Будем искать расстояние от точки до аттрактора последовательными приближениями. Октаэдр Серпинского состоит из шести, уменьшенных в два раза, его копий. Выберем из них ближайшую к нашей точке. Для этого найдём расстояния до вершин исходного октаэдра и возьмём ту копию, которой принадлежит вершина с наименьшим расстоянием до неё. Задача свелась к нахождению расстояния от точки до этой копии октаэдра. Повторяя процесс, в пределе получим последовательность расстояний, сходящуюся к искомому расстоянию. Кроме того, каждую такую последовательность можно представить как последовательность чисел из {0, 1, 2, 3, 4, 5} и использовать это, например для определения цвета фрагмента. Напишем почти точную (точную в пределе) SDF октаэдра Серпинского.

Получим такое изображение:

Рассмотрим теперь другой, более эффективный метод построения IFS трёхмерных фракталов.

Длина пробега точки

Для простоты пока ограничимся рассмотрением IFS, каждая функция которой обратима. В случае октаэдра имеем систему гомотетий с теми же, что и ранее, центрами, но коэффициентами, равными 2. Для такой IFS октаэдр Серпинского будет отталкивающим множеством (репеллером).

Если точка принадлежит октаэдру, то её образ при действии гомотетии с центром ближайшим к ней также будет принадлежать октаэдру. Всякая другая точка будет удаляться от репеллера.

Если мы каждый раз действуем на точку ближайшей гомотетией, то расстояние до фрактала будет каждый раз увеличиваться вдвое. Для наглядности рассмотрим двумерный пример с салфеткой Серпинского, в трёхмерном варианте всё аналогично.

На рисунке изображена, в некотором приближении, салфетка Серпинского и точка , расстояние от которой до фрактала мы и хотим узнать. Ближайшая вершина для  — это вершина 1, поэтому действуем гомотетией 1. Точка переходит в красную точку 1, для неё ближайшая вершина 0, под действием гомотетии с центром в 0 точка переходит в точку 10; затем ближайшая вершина 2, точка 10 переходит в точку 102, снова ближайшая вершина 2, 102 переходит в 1022, и так далее.

Очевидно, что каждый раз расстояние до фрактала (длины красных отрезков) увеличивается вдвое. Таким образом, расстояние от точки 10 222 до фрактала в 2⁵ раз больше исходного искомого расстояния. Тогда можно оценить снизу это расстояние.

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

Коэффициент гомотетий .

В нашем случае в качестве можно выбрать начало координат, и в качестве взять половину диаметра = 1.

Таким образом, получим:

Так, например, если мы хотим иметь величину ошибки не больше, чем 0,00001, то нужно проитерировать точку 17 или более раз.

Для оптимизации вычислений и для получения большего разнообразия форм воспользуемся симметриями октаэдра. Идея состоит в том, что вместо того, чтобы вычислять расстояния до вершин октаэдра и находить меньшее из них, иметь дело всегда только с одной выбранной вершиной (например, (1, 0, 0)). Для этого всякий раз, когда ближайшая вершина не (1, 0, 0), симметрично отражать точку P так, чтобы ближайшая к ней вершина отразилась в (1, 0, 0).

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

Икосаэдр Серпинского

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

Получим, например, такие изображения:

Додекаэдр Серпинского

Полностью аналогично напишем SDF для додекаэдра.

Получим, например, такие изображения:

Орбитальные ловушки

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

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

Идея орбитальных ловушек состоит в следующем. Выбираем какое‑то множество в качестве ловушки (сферу, плоскость, точку или даже шум, фрактал и так далее) и фиксируем, насколько близко к ловушке проходит орбита точки. Дале, в зависимости от этого расстояния, красим точку. Также мы можем не просто красить точку фрактала, а считать её принадлежащей нашему объекту, даже если она не лежит на фрактале.

Для примера рассмотрим IFS тетраэдра Серпинского:

Получим изображение тетраэдра:

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

Возвращать будем не просто  — расстояние до фрактала, а расстояние до фрактала с повторяющимися образами ловушки.

SDF с ловушкой не является точным, для большей точности его можно поделить на градиент поля, или уменьшить шаг сэмпла луча, или просто подобрать скаляр, на который поделить расстояние от орбиты до ловушки (в данном примере с тетраэдром поделить на 5).

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

Естественно, мы можем менять норму пространства и получать большее разнообразие форм.

Давайте сделаем какие-нибудь преобразования над тетраэдром. Например, можем получить такое изображение:

А теперь то же самое, но с орбитальной ловушкой.

Добавим цвет ловушке и фракталу.

Мандельбокс

В феврале 2010 года Том Лоу (Tom Lowe) представил найденный им фрактал — коробку Мандельброта. Этот фрактал, как и фрактал Мандельброта, является картой для соответствующих множеств Жулиа, но, в отличие от множества Мандельброта, естественным образом определяется для любого количества измерений.

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

где:

• — масштабный фактор, гомотетия с центром в 0 (все точки на рисунке ниже);

• — это симметрии относительно сторон коробки, если точка снаружи (серые точки), и тождественное преобразование, если она внутри коробки (не серые);

• — это гомотетия с центром в 0 и коэффициентом для точек, лежащих внутри сферы, длина радиус-вектора которых не больше, чем (красные точки), и инверсия, если длина радиус-вектора и (зелёные точки).

Рисунок для простоты и наглядности показывает двумерный случай, в трёхмерном всё аналогично.

, , (радиус большей сферы, на рисунке ) и  — параметры для фрактала.

Давайте теперь найдём SDF мандельбокса.

По построению очевидно, что мандельбокс симметричен относительно ядра (куба, сферы и 0). Для примера построим двумерный мандельбокс.

Пусть точка  — это точка фрактала, ближайшая к данной точке . Пусть и — образы точек и после ‑кратного применения преобразования (*) соответственно. Давайте оценим, как с каждой итерацией будет меняться расстояние между и . Если точка находится за пределами фрактального множества (за областью ), то в каждой итерации расстояние будет увеличиваться примерно в  раз, в пределе ровно в  раз.

Если точка внутри области, то при симметриях расстояние не будет меняться, при гомотетии будет увеличиваться в  раз, при инверсии будет увеличиваться примерно в (так как точки достаточно близки), и наконец, добавление первоначальных точек, увеличит расстояние на 1. То есть расстояние увеличится в  раз, где — скалярная производная нашего преобразования, которая неограниченно растёт с ростом .

После применения итераций, так как  — точка фрактала, то и — точка фрактала, тогда получим, например, такую картину:

Напишем функцию расстояния:

Получим изображение для значений параметров , , , .

Вот что, например, можно увидеть внутри ящика:

Меняя параметры фрактала и нормировку пространства, получим большее разнообразие форм.

Аналогично множеству Мандельброта можно построить множества Джулиа — Джулиабокс, оценку расстояния для этих множеств можно оставить такую же.

В следующей, заключительной части расскажу про построение алгебраических фракталов: оболочки Мандельброта, фракталов Джулиа и Мандельброта на кватернионах и о построении гибридных фракталов.

Благодарю вас, и до встречи! :-)