На пути к эффективному алгоритму Global Illumination, часть 1

Автор: Александр Санников

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

Исторический экскурс
На каком этапе здесь находится индустрия?
Почему именно screenspace?
  We need to go deeper
  Even deeper
Алгоритмическая сложность трассировки одного луча
Заключение

Исторический экскурс

В компьютерной графике сложилась интересная ситуация — в то время как для растеризации геометрии на экране уже последние несколько десятков(!) лет де-факто стандартным представлением является полигональное представление геометрии, для представления global illumination используется огромное количество самых разных, часто не имеющих ничего общего друг с другом, структур данных: light propagation volumes, sparse voxel trees, imperfect shadow maps, итп. Получается так в первую очередь потому, что полигональное представление очень эффективно справляется с задачей растеризации, в которой каждому фрагменту трёхмерной геометрии ставится в соответствие единственый фрагмент на экране, в который он проецируется. Это достигается через проецирование вершин треугольника на экранную плоскость и дальнейшей растеризацией каждого треугольника уже в экранных координатах. Этот способ исторически себя настолько хорошо себя зарекомендовал, что после того, как первые аппаратные ускорители графики реализовали эти преобразования в "железе" в начале 90-х, до момента написания этой статьи, в них по большому счёту ничего принципиально не менялось.

Взглянем на основное уравнение рендеринга, определяющее освещённость фрагмента:
\(L_0(\vec x, \vec \omega_0) = L_e(\vec x) + \int_{\Omega} f(\vec x, \vec \omega_0, \vec \omega_i) L_i(\vec x, \vec \omega_i,) (\vec w_i \cdot \vec n) d\vec \omega_i\) (1)
Для простоты я выбросил из уравнения зависимость от длины волны \(\lambda\) и от времени \(t\). К сожалению, это уравнение не только выглядит страшновато, но история также показала, что его исключительно трудно решать даже численно. Более того, все существующие подходы в компьютерной графике являются в той или иной степени его различными аппроксимациями. Если вы не совсем понимаете смысл этого уравнения, то ничего страшного, далее мы будем рассматривать его упрощённые формы с подробными пояснениями, пока не придём к нему в изначальном виде для моделирования полного GI. Например, растеризацию объектов без учёта освещения можно описать как уравнение рендеринга, в котором полностью пренебрегли существованием интеграла и свели его к следующему виду:
\(L_0(\vec x, \vec \omega_0) = L_e(\vec x)\) (2)
Интуитивно это выражение можно понять следующим образом — светимость фрагмента на экране определяется собственной светимостью этого самого фрагмента и больше ни от чего не зависит.

Расчёт прямого освещения объектов точечных (или направленных) источников также можно свести к растеризации, добавив технологию расчёта видимости фрагментов для каждого источника (для учёта теней), что делается через алгоритмы shadow mapping'а, которые хоть и улучшаются со временем, но идейно остаются теми же самыми уже много лет. Это позволяет получить более точную аппроксимацию решения уравнения рендеринга, используя одну лишь растеризацию:
\(L_0(\vec x, \vec \omega_0) = L_e(\vec x) + \sum_{j=1}^{N}f(\vec x, \vec \omega_0, \vec \omega_j) L_j V_j(x) (\vec w_j \cdot \vec n)\) (3)
Можно заметить, что классический расчёт множества источников света аппроксимирует интеграл освещения как сумму освещения от N источников. В этой формуле под знаком суммы стоит BRDF поверхности \(f(\vec x, \vec \omega_0, \omega_j)\), который определяет, какая доля энергии, падающей на поверхность в точке \(x\) под направлением \(\vec \omega_j\) отражается в рассеивается в направлении \(\vec \omega_0\). Типично для аппроксимации этого параметра используются разные модели микрорельефа поверхности вроде lambert или GGX, однако, их рассмотрение выходит за рамки этой статьи. Под \(\vec \omega_j\) понимается направление на источник света под номером \(j\), \(L_j\) — его яркость, а \(V_j(\vec x)\) — функция видимости точки \(\vec x\) для источника j, что типично реализуется через shadow mapping.

Обратим внимание, что формула (3) удобно ложится на механизм растеризации, так как функцию \(V_j(\vec x)\) для каждого источника можно рассчитать, используя растеризацию shadow map'ы, а потом, используя её, растеризовать сам объект на экран, рассчитав формулу (3) в явном виде в шейдере. Из-за того, что в формуле присутствует цикл по всем источникам, она эффективнее всего работает, если этих самых источников света достаточно мало и производительность будет линейно убывать с количеством источников.

Принципиальная же особенность расчёта непрямого освещения (формула (1)) от прямого (формула (3)) заключается в том, что непрямое освещение эквивалентно расчёту прямого освещения от бесконечного количества источников прямого освещения. То есть рассчитать его трудно не просто потому, что источников бесконечное количество, но ещё и потому, что производительность алгоритмов прямого освещения линейно падает с количеством источников. Один из первых подходов к аппроксимации GI — reflective shadow maps. В этом подходе непрямое освещение моделируется как прямое освещение от большого количества вторичных источников света с яркостью, определяющейся их первичным освещением. То есть после расчёта первичного освещения на все фрагменты, на которое попал первичный свет, ставятся вторичные источники света и по формуле (3) рассчитывается их влияние на сцену. Уравнение рендеринга для этого подхода можно описать так:
\(L_0(\vec x, \vec \omega_0) = L_e(\vec x) + \sum_{j=1}^{N}f(\vec x, \vec \omega_0, \vec \omega_j) L_j V_j(x) (\vec w_j \cdot \vec n) +\)
\(+ \sum_{k=1}^{N_d}f(\vec x, \vec \omega_0, \vec \omega_k) L_k \cdot (\vec w_k \cdot \vec n)\) (4)
здесь \(N_d\) — количество вторичных источников, которые расставляются в область прямого освещения, а \(L_k\) определяет их яркость.

Это был одним из первых алгоритмов, которые я реализовал, это выглядело примерно так:

Мало того, что этот подход является очень неэффективным(итерирование через сотню источников в шейдере очень долго считать), в нём также полностью игнорируется существование множителя \(V_j(\vec x)\), отвечающего за тени от вторичного освещения, поэтому они полностью отсутствуют.

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

Конечно же, к такому выводу пришёл не я один. Огромное количество исследователей пробовали побороть уравнение рендеринга. И самое, на мой взгляд, интересное — то, насколько разными путями они шли. Кто-то представлял  сцену как дискретную трёхмерную сетку и выпускал по ней лучи (vxgi), кто-то представлял сцену как множество элементарных элементов поверхности и рассчитывал их видимость для источников вторичного освщещения (imperfect shadow mapping), кто-то рассчитывал распространение светового фронта как функцию направления для сцены (light propagation volumes), кто-то предрассчитывал излучение каждого фрагмента сцены на основе его окружения (precomputed radiance transfer). Единственное, что объединяет все эти подходы — что в них нет растеризации треугольников. То есть исследователи уже смирились, что для реализации GI нужно альтернативное представление сцены, которое позволит рассчитать влияние вторичного освещения более эффективно, чем через растеризацию. Вопрос лишь в том, какое это должно быть представление. На момент написания этой статьи это — по-прежнему открытый и, на мой взгляд, очень острый вопрос. Сразу скажу, что я не смогу дать на него однозначного ответа. Но я потратил на его обдумывание тысячи часов и хотел бы поделиться некоторыми выводами.

На каком этапе здесь находится индустрия?

Часто если людям, даже плотно занимающимся разработкой графики, показать программу и сказать, что это — unbiased screenspace GI, их первый вопрос бывает вроде "а как оно рендерит источники света за экраном"? Но господа, постойте. То есть вас не удивляет сама возможность существования unbiased solver'а (напомню, unbiased solver сходится к точному решению уравнения (1)) хотя бы в screenspace'е? Здесь и далее, если применяется термин unbiased в контексте screenspace, это обозначает, что метод сходится к точному решению при увеличении параметра точности метода и условии, что вся геометрия помещается на экране без загораживания. Также я буду рассматривать только вторичное освещение, так как третичное и далее считается по аналогии и не влияет на общую алгоритмическую сложность.

Люди привыкли видеть демонстрации модных технологий вроде rtx или последних версий unreal engine которые выглядят так, будто в них уже давно считается unbiased освещение да ещё и не в screeenspace'е, то есть, можно подумать, в этом нет ничего особо удивительного. Так вот, сразу обозначу, что ключевых вопроса здесь два — масштабируемость технологии и общность.

Масштабируемость
Разумеется, можно бросить всю вычислительную мощность последней видеокарты от nvidia, чтобы рассчитать фотореалистично выглядящий cornell box даже с самым наивным monte-carlo path tracer'ом и её вычислительной мощности будет достаточно, чтобы рендерить такую сцену в реалтайме почти без шума. Это будет очень общий подход, который теоретически позволит рассчитать unbiased GI для любой сцены, но он будет масштабироваться чуть хуже, чем никак. Path tracer'ы в наивной реализации настолько неэффективно используют вычислительную мощность, что нет смысла говорить об их применении для серьёзных сцен. Причём, на мой взгляд, наивно полагать, что это только сейчас, пока у GPU не хватает мощности считать path tracing в реальном времени. Мол, завтра (через N лет) видеокарты станут мощнее и вполне потянут path tracing в реальном времени. Наивное суждение, так как если к тому времени у них хватит ресурсов на path tracing сегодняшних сцен, то представьте, какие сцены на них можно будет рендерить более продвинутыми алгоритмами. Каким бы мощным железо ни становилось со временем, его всегда рациональнее всего по возможности использовать с наиболее эффективными алгоритмами вместо брутфорсных.

Общность
Люди привыкли видеть выносящие мозг своей красотой демки rtx от nvidia, показывающие идеально выглядящие отражения:

И если человеку задать вопрос: "У них зеркальный пол, зеркальные штормтруперы и зеркальные стены. Как ты думаешь, почему?". Практически всегда люди отвечают что-то вроде : "Чтобы показать, как круто у них выглядят отражения!". На вопрос же : "Как ты думаешь, они могут так же здорово рендерить что-то кроме зеркальных поверхностей?", типичный ответ: "Ээ.. ну конечно! Наверное?". Стоит отдать должное, как принципиальное ограничение технологии nvidia с успехом выдаёт за фичу. Ответ на этот вопрос — нет, они не могут считать ни диффузные, ни glossy отражения достаточно эффективно. Если выписать уравнение рендеринга, которое эффективно позволяет считать rtx и подобные технологии, оно выглядит так:
\(L_0(\vec x, \vec \omega_0) = L_e(\vec x) + f(\vec x, \vec \omega_0, \vec \omega_r) L_i(\vec x, \vec \omega_r) (\vec w_r \cdot \vec n)\) (4)
Здесь \(\omega_r\) — направление отражённого луча. Да, надо отдать должное, рейтрейсинг действительно эффективно позволяет получить значение множителя \(L_i(\vec x, \vec \omega_r)\), но истина в том, что этот множитель эффективен лишь при расчёте зеркальных отражений. Для аппроксимации диффузных поверхностей в рейтрейсинге используется несколько лучей. Алгоритмы, которые я буду рассматривать далее, используют в среднем около 128 плоскостей на фрагмент в реалтайме на существующем железе. Каждую плоскость можно более-менее аппроксимировать через как минимум 8 (на самом деле — больше) лучей. То есть чтобы получить те же параметры сходимости, rtx или любой другой технологии, основанной на world-space лучах придётся выпустить около 1024 эффективных лучей на пиксел вместо 1. 1024 луча с использованием rtx будут работать в 1024 раза медленнее, чем железо для записи этого демо которое уже стоит как квартира его среднестатистического зрителя. И если вы сейчас подумали : "ну, значит надо подождать, когда видеокарты станут ещё в 1024 раза мощнее и вот тогда заживём!", то именно от этого я хотел предостеречь — к моменту, когда видеокарты станут в 1024 раза мощнее, на них можно будет либо гонять эту сцену с диффузными материалами и rtx, либо сцену в 1024 раза сложнее, если использовать более продвинутый алгоритм, чем rtx.

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

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

Почему именно screenspace?

Сегодняшние вычислительные мощности находятся на стадии, когда в общем случае рассчитать точный GI в world space в реальном времени просто невозможно. По крайней мере нет ни одного алгоритма, даже приближающегося к этому. Однако, это — очень интересный момент, так как именно сейчас у mid-end машин едва-едва хватает производительности, чтобы считать его в screenspace, если использовать ряд принципиальных свойств уравнения(1). У кого-то может сложиться впечатление, что "нуу, если screenspace, то это проосто". Так вот, дисклеймер — даже в скринспейсе это вообще не просто, иначе бы все это делали. Первая более-менее внятная реализация SSGI, которая появлась в индустрии — это, пожалуй в unigine:
https://developer.unigine.com/en/devlog/20170531-unigine-2.5

Они по понятным причинам не раскрывают деталей реализации, однако, судя по их презентации с последнего GDC, волшебства они не реализовали и у их алгоритма есть серьёзные ограничения — например, у их реализации сильно падает точность с увеличением радиуса действия GI, в моей же реализации радиус — всегда бесконечность(что физически корректно). Доступные публикации вроде https://www.in.tu-clausthal.de/fileadmin/homes/CG/data_pub/paper/SSDO_i3D09.pdf находятся в совершенно зачаточном состоянии, так как напрочь не умеют far-field global illumination и, следовательно, не являются unbiased.

Это я к тому, что даже в screenspace со всеми его недостатками, расчёт GI — вовсе не тривиальная задача и для этого на момент написания статьи по-прежнему не существует надёжных общепризнанных алгоритмов.

We need to go deeper

Есть более глубинная причина, по которой я считаю screenspace методы особенно интересными. Если вдуматься, какой именно размерности проблема, которую мы решаем? Другими словами, как именно может масштабироваться теоретически существующий оптимальный алгоритм расчёта global illumination? Для ответа на этот вопрос взглянем на самую сложную для расчёта часть уравнения (1) — интеграл:
\(\int_{\Omega} f(\vec x, \vec \omega_0, \vec \omega_i) L_i(\vec x, \vec \omega_i,) (\vec w_i \cdot \vec n) d\vec \omega_i\). Этот интеграл определяет влияние окружения на фрагмент в точке \(\vec x\). Самый наивный способ для расчёта этого интеграла — это численно разбить сферу на множество независимых лучей и от интеграла перейти к сумме, как это делает уравнение (4). Именно по такой схеме работают rtx и многие воксельные алгоритмы. Однако, этот способ не учитывает некоторые принципиальные особенности задачи, которую мы решаем, а именно:
— точки пересечения со сценой лежащих в одной плоскости лучей, также всегда лежат в одной плоскости
— точки пересечения почти параллельных лучей обычно лежат почти в одной плоскости
— параллельные лучи, выпущенные почти из одной точки, обычно пересекают сцену почти в одной точке

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

Более осязаемая количественная оценка. Рассчитаем, сколько лучей необходимо для расчёта источника вторичного освещения радиусом \(r\) на расстоянии \(R\) от текущего фрагмента. Если выпускать лучи по полусфере, то понадобится в среднем \(N \approx \frac{2\pi}{\Omega}\) лучей, чтобы его разрешить, где \(\Omega \approx \frac{\pi r^2}{R^2}\) — телесный угол, под которым виден источник, то есть
\(N_1 \approx \frac{2R^2}{r^2} \sim \frac{1}{r^2}\) (5)
Если же выпускать лучи в экранных координатах, то количество лучей можно оценить как \(N \approx {2\pi}{\alpha}\), где \(\alpha=\frac{r_p}{R_p}\approx\frac{r}{R_p^2}\) — угловой размер источника в экранных координатах (\(r_p\), \(R_p\) — размер и расстояние до источника в экранных координатах). Также заметим, что при использовании ортогональной проекции, \(R=R_p\). Другими словами, в экранных координатах нам понадобится
\(N_2 \approx \frac{2\pi R^2}{r} \sim \frac{1}{r}\) (6)
лучей, чтобы разрешить тот же самый источник.

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

Even deeper

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