ray marching что это

Что такое Рэй Маршинг? Сфера отслеживает одно и то же?

Многие демоверсии ShaderToy используют алгоритм Ray Marching для рендеринга сцены, но они часто написаны в очень компактном стиле, и я не могу найти простых примеров или объяснений.

Так что же такое Рэй Маршинг? Некоторые комментарии предполагают, что это разновидность отслеживания сфер. Каковы вычислительные преимущества такого подхода?

TL; DR

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

Raymarching определение

Это может быть полезно, если вы:

Трассировка сферы

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

Рисунок 2. Трассировка сферы * в действии. Обратите внимание на адаптивный размер шага.

* Возможно, в 2d это следует называть круговой трассировкой 🙂

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

Трассировка сферы может относиться к неявному тесту пересечения луча и сферы, но это также название техники космического прыжка Джона Харта, как упоминает @joojaa, и используемой Уильямом Доннелли ( Отображение смещения на пиксель с функциями расстояния ), где 3D текстура кодирует радиусы сфер, в которых не существует геометрии.

Источник

Функции расстояний

Алгоритм Distance-aided Ray Marching

Пусть существует функция f(x,y,z), задающая поверхность уравнением вида f(x,y,z) = 0. Для краткости можно будем писать f(p) = 0.

Если в функцию f вместо p подставить, некоторую точку, не лежащую на поверхности, мы получим некое не равное нулю число. Нетрудно заметить, что это число будет представлять собой знаковое (хотя это может зависеть от формулы) расстояние до поверхности.

Рисунок 2. Distance-aided ray marching.

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

Еще одна тонкость, для того чтобы не продолжать реймарчинг до бесконечности, вам необходимо в самом начале найти пересечение луча и ограничивающего всю сцену bounding box-а. Как только вы выходите за этот бокс (t > tmax) – остановить реймарчинг. Либо вы просто можете ограничить максимальное число шагов по лучу какой-либо достаточно большой константой.

Вычисление нормали

Нормаль есть не что иное, как градиент к поверхности. Вычисляем ее численно.

float3 EstimateNormal(float3 z, float eps)

float3 z1 = z + float3(eps, 0, 0);

float3 z3 = z + float3(0, eps, 0);

float3 z5 = z + float3(0, 0, eps);

return normalize(float3(dx, dy, dz) / (2.0*eps));

Источник

[процедурная геометрия] Signed Distance Function & Ray Marching

Поговорим о SDF и марчинге. Как известно, суть этот подхода заключается в следующем:

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

P.S.: если стена будет длинной, а луч будет идти очень близко к стене, это вообще капец 🙂

P.P.S: я неправильно нарисовал окружности на нижнем рисунке, там их должно быть больше, из каждого «конца» окружности должна стартовать новая, но да не суть, смысла это не меняет.

-=MASTER=-
если рассмотреть идеальную функцию рейкастинга, которая возвращает для луча (origin, dir) расстояние до геометрии:
\(D(\vec o, \vec d)\)
то функцию дистанс филда можно трактовать как оценку этой функции снизу, её минимом по всем направлениям dir:

\(D(\vec o, \vec d) \leq SDM(\vec o) = \min \limits_<\vec d>\left(D\left(\vec o, \vec d \right) \right)\)

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

по сути этот способ эквивалентен замене сферы эллипсоидом.

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

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

можно ещё ввести понятие обобщенной производной. 🙂

Источник

Трехмерный движок на формулах Excel для чайников

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

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

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

Осторожно: 19 картинок и 3 анимации под катом.

В случае скачивания своего Excel-файла с ObservableHQ, ячейки необходимо раскрасить вручную. Нужно выделить все маленькие квадратные ячейки и выбрать «Условное форматирование» → «Цветовые шкалы».

Ray marching

Алгоритм Ray Marching был популяризован Iñigo Quilez в 2008 году после презентации «Rendering Worlds with Two Triangles» о компактном трехмерном движке для демосцены.

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

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

Принцип работы движка

Описание объекта

Можно придумать три способа описания трехмерного объекта:

SDF получает на вход точку пространства и возвращает расстояние до ближайшей точки объекта. Для точек внутри она равна расстоянию до границы объекта со знаком «минус»

Нахождение пересечения луча и объекта

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

В голову приходит несколько способов найти эту точку:

Это простой алгоритм, который работает только с SDF.

Давайте параметризуем луч по расстоянию от его начала функцией .
Тогда — это сама камера. Вот алгоритм:

Число это расстояние от камеры, в пределах которого мы ожидаем найти объект.

Почему алгоритм работает

С другой стороны, если алгоритм сошелся к некоторой точке, то расстояние между соседними итерациями стремится к нулю SDF (расстояние до ближайшей точки объекта) тоже стремится к нулю в пределе алгоритм сходится к точке пересечения луча с объектом.

Получение цвета пикселя по точке пересечения

Представим, что для каждого пикселя мы нашли точку пересечения с объектом. Мы можем нарисовать эти значения (то есть расстояние от камеры до точки пересечения) напрямую и получить такие картинки:

С учетом того, что это было получено при помощи Excel, неплохо. Но хочется узнать, нельзя ли сделать цвета больше похожими на то, как мы видим предметы в жизни.

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

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

Искомый угол я обозначил одной дугой на чертеже. Значение его синуса обозначено как .

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

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

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

Нарисуем чертеж. Обозначим и — точки, полученные на соседних итерациях алгоритма. Предположим, что точки находятся достаточно близко к объекту, что его можно заменить на плоскость, угол с которой мы хотим найти. Пусть , — расстояния от точек и до плоскости. Тогда, согласно алгоритму, расстояние между и равно .

С другой стороны, если обозначить — точку пересечения луча и фигуры, то
, а , следовательно

То есть интенсивность пикселя равна единица минус отношение функций SDF соседних итераций!

Описываем простые фигуры

Примеры SDF для сферы, куба и тора:

Фигуры можно перемещать и сжимать вдоль осей:

Фигуры также можно объединять, пересекать и вычитать. То есть SDF поддерживает основные операции конструктивной сплошной геометрии:

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

Это малая часть того, что можно делать при помощи SDF, полный список фигур и операций можно найти на странице www.iquilezles.org/www/articles/distfunctions/distfunctions.htm

Совмещая все приведенные формулы, получаем первую фигуру:

Формула чайника

С чайником немного сложнее: нужен план

Аккуратно записываем формулу:

И подбираем нужный ракурс. Готово:

Камера

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

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

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

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

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

При помощи WolframAlpha находим матрицу поворота:

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

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

У экрана нет точного местоположения и размера. Точнее, они зависят от расстояния до камеры: если экран отодвинуть дальше, его потребуется сделать больше. Поэтому условимся, что расстояние от камеры до экрана равно 1. Тогда мы можем вычислить значение вектора , соединяющего точку камеры и центр экрана (он такой же как и у центра камеры, только домноженный не на , а на ):

Теперь нам надо определить размер экрана. Он зависит от угла обзора камеры, который измеряется в градусах и соответствует тому, что в видеокамерах называется «zoom». Пользователь задает его при помощи переменной (field of view). Так как экран не квадратный, необходимо уточнить, что имеется в виду вертикальный угол обзора.

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

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

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

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

Так мы получили искомую функцию , которая возвращает точку луча на расстоянии от его начала, соответствую пикселю с координатами .

Excel

Файл Excel, который получается в результате, является книгой, состоящей из >6 листов:

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

Источник