Всем привет! Меня зовут Андрей Гринблат, я ИТ‑инженер в СберТехе, занимаюсь разработкой фронтенд‑интерфейсов приложений.

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

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

Каждая вершина должна была иметь подпись‑название и являлась управляющим элементом интерфейса. Одним из возможных вариантов решения, было использование методов компьютерной графики, «выход в 3D». И хотя в итоге удалось решить задачу, оставаясь в 2D, трёхмерный вариант решения имел свои достоинства.

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

В этой статье расскажу о том, как построить фотореалистичные изображения 3D‑фракталов с помощью математики и такой технологии, как ray marching.

Рассказ получился объемным, поэтому разделю его на три части. В этой расскажу про основные методы рендеринга и приведу примеры простых полей расстояний (SDF). Во второй части опишу построение геометрических и IFS 3D фракталов: губки Менгера, тетраэдра Серпинского и других, а также расскажу об использовании в построениях техники «орбитальные ловушки». В третей, завершающей части, расскажу о построении алгебраических фракталов: Джулиа на кватернионах, Мандельбоксе и других, а также о гибридизации как методе получения новых форм.

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

Введение

Компьютерная графика уже давно и прочно вошла в нашу повседневную жизнь — от отдельных спецэффектов до целых сцен в художественных фильмах и компьютерных играх.

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

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

С лета 2018 года появилась аппаратная поддержка трассировки лучей (в первую очередь в виде карт NVIDIA RTX), что позволило шире использовать эту технологию в режиме реального времени. Тем не менее даже при аппаратной реализации объём вычислений может быть столь велик, что достичь стабильных 60 кадров в секунду сложно даже при разрешении 2K, не говоря уже о 4K и выше.

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

В частности, для рендеринга трёхмерных фракталов чаще используется другой метод — ray marching, более подходящий для таких сложных поверхностей.

Ray marching

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

Например, если объект — это гладкое многообразие заданное выражением F(x, y, z) = 0. Тогда, находясь на луче в точке M(a,b,c), мы можем считать, что достигли поверхности, если значение функции F(M) по модулю становится меньше некоторого малого порога ε, например 0,0001. Эта идея и лежит в основе метода ray marching (пошаговой трассировки), хотя в наивной реализации алгоритм малопригоден для задач в реальном времени из‑за высокой вычислительной нагрузки.

Очевидно, что чем меньше шаг вдоль луча, тем точнее результат, но тем больше итераций потребуется, что увеличивает затраты вычислительных ресурсов.

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

Более продвинутая оптимизация предполагает использование динамически изменяющегося шага, величина которого зависит от расстояния до объекта в текущей точке. В идеале шаг определяется функцией, задающей скалярное поле. Значение поля в каждой точке пространства соответствует расстоянию до поверхности объекта. На самой поверхности это значение равно нулю, вне объекта — положительно, внутри — отрицательно (или, в альтернативных подходах, может быть равным нулю, внутри сплошного тела). Такое поле называют полем расстояний, а саму функцию — Signed Distance Function (SDF) или функцией расстояния со знаком. Если значение этой функции точно соответствует расстоянию до ближайшей поверхности, её называют точной SDF.

Ray marching с использованием SDF часто называют трассировкой сфер (sphere tracing). Это мощный и эффективный метод, позволяющий достигать фотореалистичного качества изображения, в том числе в реальном времени.

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

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

Примеры простых SDF и базовых оптических эффектов

Рассмотрим SDF двумерной сферы.

Очевидно, что расстояние от произвольной точки М до сферы с центром О, это

Запустим рендер, норму возьмём евклидову, сфера пусть будет единичного радиуса с центром в начале координат. Получим такую картинку, напоминающую флаг Японии.

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

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

Вот 6-точечная схема:

Для начала реализуем освещение по модели Ламберта (используем только фоновую и диффузную части освещения, источник света для простоты будет несобственным — очень далеким).

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

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

Смягчим тень — для ray marching это легко сделать. В отличие от классического рендеринга здесь нет необходимости использовать дополнительные ресурсы, такие как карты теней или карты глубины. Вместо этого можно воспользоваться естественным свойством алгоритма: лучи, проходящие вблизи границы объекта, сэмплируются наиболее интенсивно. Это поведение не только позволяет получить мягкие тени, но также используется для создания других визуальных эффектов — например, окружающей окклюзии (ambient occlusion), свечения (glow или halo) вокруг объектов.

Теперь дадим определение квази-SDF и рассмотрим несколько базовых операций с SDF объектов, которые нам понадобятся в дальнейшем.

Функцию F будем называть квази-SDF для объекта А, если она мажорируется точным SDF объекта A, причём если SDF(P) = 0, то и F(P) = 0.

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

Пусть даны SDF двух объектов — A и B, тогда легко получим SDF дополнения до объекта, SDF объединения объектов, SDF пересечения объектов и SDF разности.

Равенство (1) следует из того, что «внутри» и «снаружи» для А, соответственно, являются «снаружи» и «внутри» для дополнения к А, а значит SDF отличаются только знаком.

Равенство (2) говорит, что расстояние от произвольной точки до системы из двух объектов, есть расстояние до ближайшего из них.

Равенство (3) почти также очевидно, как и первые два. Строго говоря, максимум не является точным SDF пересечения, это квази-SDF (он мажорируется реальной SDF пересечения). Ну и главное — мы рисуем точку, и если SDF в этой точке обращается в 0 (на практике, конечно используем приближение — не в точности 0, а просто меньше, некоторого достаточно малого значения), а максимум двух чисел равен 0 (когда одно из них равно 0, а второе не больше 0), это означает, что наша точка лежит на поверхности одного и принадлежит второму. Таким образом, мы отрисуем поверхность пересечения объектов.

Ну и наконец, равенство (4) следует из (3) и (1).

С SDF можно выполнять и многие другие операции, например, добавлять немного шума, делать мягкие объединения, деформации, симметрии и др.

Рассмотрим еще две операции — «вытягивание» и «повторение домена».

Вытягивание, масштабирование

Пусть дана SDF объекта A, рассмотрим функцию

То есть поверхность описываемая функцией f растянута по оси z в раз.

Для примера выбрана ось z, естественно так можно делать по любому направлению.

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

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

Повторение домена

Часто приходится сталкиваться с необходимостью отрисовать большое количество одинаковых или похожих объектов. Ray marching позволяет это сделать почти бесплатно.

Приведу пример наивной реализации «повторения». Она имеет некоторые недостатки, но для наглядного представления вполне достаточна.

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

В этом примере пространство разбивается на квадратные бесконечные цилиндры.

Здесь каждой сфере можно поставить уникальный идентификатор, например, двумерный целочисленный вектор.

Если бы мы рендерили это изображение как объединение сфер, то конечно, ни о каком real time, не могло бы быть и речи.

Нормированные пространства

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

Конечномерное нормированное пространство ещё называют пространством Минковского. На таком пространстве естественным образом может быть введена метрика — расстояние между двумя векторами, есть норма разности этих векторов:

Для примеров будем рассматривать три Гёльдеровы нормы:

Здесь приведены нормы для трёхмерного пространства, для четырёхмерного нужно по аналогии добавить ещё одну координату.

И для разнообразия еще такую норму М1

Давайте теперь посмотрим на сферу в этих пространствах. Для этого в SDF-сферы будем подставлять эти выражения для нормы.

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

Теперь всё готово для рендеринга определенного типа 3D фракталов. В сдедующей части начну с самого простого для реализации геометрического фрактала — губки Менгера, — а затем перейду к более сложным, таким как тетраэдр и октаэдр Серпинского и другим IFS-фракталам.

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