Войти
ПрограммированиеСтатьиГрафика

Предрасчёт рейкаста для эффективного рендеринга травы и меха

Автор:

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

Ключевые особенности алгоритма
Базовый алгоритм
Дальнейшие улучшения
Как выбрать параметры текстуры предрасчёта
Заключение

Ключевые особенности алгоритма


- Алгоритмическая сложность — O(1). В моём подходе отсутствует классически применяемый в подобных случаях цикл шагания по лучу, ответ находится за одно чтение из предрассчитанной текстуры.
- Алгоритм разрабатывается для реалтайм работы на mid/low-gen видеокартах
- Скорость работы алгоритма не зависит прямым образом от количества волосинок шерсти/травинок. Однако, она косвенно зависит от локальности доступа к памяти, в которой хранятся предрассчитанные данные. То есть скорость зависит не от количества травинок, а от их детализации.
- На выходе алгоритма — глубина, нормаль, цвет и прочие параметры поверхности, то есть полученная геометрия корректно перекрывает всю остальную геометрию в буфере глубины.
- В случае рендринга геометрии, представленной выдавливанием (extrusion) произвольной двумерной маски, результат является аналитически точным. То есть параллельные волокна шерсти, параллельные травинки с произвольным сечением и под произвольным углом к горизонту рендерятся геометрически точно, погрешность в таком случае определяется только точностью дискретизации предрассчитанной текстуры.

Однако, важно понимать границы применимости алгоритма:
- Случай с непараллельными волокнами или волокнами переменного сечения можно рендерить приближённо. При некоторых ракурсах результат может выглядеть неестественно.
- Результат будет тайлиться. Тайлинг можно разными способами скрывать, но полностью от него избавиться вряд ли удастся.
- Предрасситанную текстуру можно интерполировать и использовать разные мипы, но результат интерполяции иногда может выглядеть странненько.

Базовый алгоритм

Рассмотрим сперва базовый алгоритм, который позволяет геометрически точно рендерить выдавленные тайлящиеся поверхности. Выдавливается двумерная геометрия, которая может выглядеть, например, так:
2d Extruded Tile | Предрасчёт рейкаста для эффективного рендеринга травы и меха
После выдавливания мы получим трёхмерное тело:
Single extruded 3d tile | Предрасчёт рейкаста для эффективного рендеринга травы и меха
Здесь синим показана поверхность, из которой производится выдавливание. В финальном рендере этой поверхностью будет меш отрисовываемой травы или меха.

Предрасчёт данных для рейкаста производится в 2д. Далее полученные данные будут переведены в 3д. Предрасчёт осуществляется в 3д текстуру, где первые две координаты означают (x, y) координаты внутри тайла, а третья — угол, нормализованный в диапазон [0..1). В цвет текселя предрассчитанной текстуры пишется путь луча до первого пересечения и нормаль в точке пересечения. Пересечения рассчитываются в предположении бесконечно повторяемой (тайловой) геометрии. Например, один из рассчитанных лучей может выглядеть так:
2d raycast example | Предрасчёт рейкаста для эффективного рендеринга травы и меха
Предрасчёт вычисляется на чём угодно и каким угодно алгоритмом, так как результат достаточно посчитать один раз, сохранить в текстуру и забыть. Нет смысла особо заморачиваться оптимизацией этой стадии.

Можно заметить, что полученные данные можно нехитрыми вычислениями использовать и в трёхмерном случае:
3d raycast example | Предрасчёт рейкаста для эффективного рендеринга травы и меха
Обратите внимание, что для расчёта трёхмерного луча OB достаточно знать луч OA(который предрассчитан) и угол между лучом OA и OB, который легко посчитать, назовём его [cht]\alpha[/cht]. Таким образом:
[cht]|OB| = \frac{|OA|}{\cos \alpha}[/cht]

Таким образом, работа алгоритма в рантайме сводится к тому, что мы рендерим меш-внешнюю оболочку, из которой будем выдавливать геометрию, а во фрагментном шейдере вместо глубины и нормали меша (они определяются точкой O), считаем глубину и нормаль по предрассчитанным данным (точка B). То есть в шейдере мы имеем полноценные 3д координаты точки пересечения view луча с геометрией, которую можно использовать для трипланарного текстурирования, расчёта карт теней, ambient occlusion'а и любых других техник, работающих с непрозрачной геометрией.

Дальнейшие улучшения


На этом этапе геометрия, которую мы можем рендерить — это вертикальные призмы всевозможных форм. Достаточно легко расширить алгоритм до обработки наклонных(но параллельных) призм, для этого достаточно построить косоугольную матрицу перехода из мировых координат в TBN базис поверхности(*). Текстура с предрассчитанными данными может хранить их именно в TBN-пространстве (то есть в пространстве, в котором ширина тайла по определению равна 1), тогда чтобы перевести точку пересечения обратно в мировые координаты, достаточно помножить её на обратную матрицу перехода. Этот способ позволяет даже описывать поверхности с изменяемым наклоном волокон, хоть и с некоторой погрешностью:

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

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


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

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

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

(*) Под TBN базисом здесь понимается не TBN базис, который типично используется для перевода нормали из текстуры в мировые координаты, а честный базис, составленный из частных производных [cht]\frac{\vec{duv}}{\vec{dp}}[/cht]. Разница в том, что в первом случае TBN базис нормализован, а во втором случае базисные векторы обозначают, на сколько меняются u и v текстурные координаты при перемещении по мировым координатам. Обращу внимание, что для целей этой статьи ошибочно полагать ортогональность или нормированность TBN-базиса, он будет точно не нормализован, так как масштаб uv не будет совпадать с мировыми координатами и не ортогонален, если волокна не перпендикулярны поверхности. Этот базис можно рассчитать разными способами, более подробно про это можно почитать, например, здесь: http://www.thetenthplanet.de/archives/1180

Как выбрать параметры текстуры предрасчёта


Для предрасчёта можно использовать текстуру очень разного размера. Стоит учесть, что чем больше текстура, тем более детализированные тайлы можно в неё запечь, но тем хуже будет локальность данных и тем дороже будет операция чтения из текстуры в соседних фрагментах из-за нелокальности и недружественности к кешу. Наилучшие результаты даёт соотношение примерно 1 текселя слоя текстуры по пространственным осям к 1 пикселю на экране. 32х32 — минимальный размер слоя, при котором можно с переменным успехом скрыть тайлинг, при тайлах размера 512х512 нелокальность доступа серьёзно сказывается на производительности, поэтому текстуру имеет смысл брать где-то в этом диапазоне. По третьей размерности (количество углов) можно брать от 8 до 64 в зависимости от применения. Я обычно использу текстуры 64х64х8. Особое внимание следует уделить формату текселя текстуры, так как он напрямую определяет время чтения — чем меньше памяти занимает тексель, тем быстрее он будет читаться, тем быстрее будет работать шейдер. Я использую формат RGBA8, где в R компоненте хранится нормализованная глубина (по формуле 1/(1+d)), GBA — трёхкомпонентная нормаль.

Заключение


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

#fur rendering, #grass rendering, #raycast, #Realtime Rendering

18 августа 2019

Комментарии [24]