В данной статье я расскажу об адаптивном методе теневых карт под названием Rectilinear Texture Warping for Adaptive Shadow Maps, о его достоинствах и недостатках, а также о реальном опыте использования данного метода в проекте (и что из этого вышло).

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

Краткий экскурс в историю.

Если в случае теней от статических объектов довольно приемлемый результат получили еще в Quake 1 с использованием запечения освещения в lightmaps, то с тенями от динамических объектов долгое время всё было не так радужно. Вначале тенями вообще никто особо не заморачивался. Самые первые тени от персонажей были просто дополнительным спрайтом — размазанным пятном, которое проецировалось на геометрию под персонажем.

Потом довольно популярными стали shadow volumes (они же stencil shadows). Метод заключался в том, что для источника света геометрически находился «контур» объекта (edge считается границей объекта, если знак dot product нормали с light vector для двух примыкающих полигонов имеет разный знак), а затем из этого контура строился shadow volume, который, по сути, был вытянутым контуром объекта, а вектором «вытяжения» контура было направление света. Затем данный volume рисовался в stencil сначала с back culling, а затем вычитался из stencil с front culling. Таким образом в стенсиле у нас оставалась разница между front и back куллингами, что, по сути, являлось пересечением volume с геометрией, то есть с тенью.

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

Самое лучшее качество теней, разумеется, достигается с помощью честного просчета траекторий лучей света — ray tracing. Сейчас данная техника практически неприменима в real-time приложениях, так как стоимость данного подхода весьма велика. Однако же, в offline рендерах (CG заставках, фильмах, мультфильмах и т.п.) используется преимущественно именно она. Никаких сомнений нет в том, что данная техника является технологическим пиком лайтинга в компьютерной графике (и теней в частности), так как повторяет механизмы реального мира, не является приближением, и потому даёт визуальные результаты, которые наиболее близки к идеальным. И, если позволит производительность железа, рано или поздно, весь real-time рендер будет работать именно так.

Shadow mapping

Пока этого не произошло, используется аппроксимация, которая наиболее близка к рейтрейсингу — shadow mapping. Shadow mapping — это довольно старый метод для создания теней, ставший на данный момент золотым стандартом индустрии. Вряд ли сейчас можно встретить AAA-проект, в котором не используется данная техника. Вкратце, для каждого источника света, который должен отбрасывать тени, мы ставим камеру, в которую рисуем расстояние до всех объектов, которые у нас на пути. После чего полученный результат мы используем уже для рисования с позиции основной камеры, чтобы определить — освещён ли данный пиксель тем или иным источником света, или нет. Я не буду вдаваться в детали реализации данного метода, благо, информации на данную тему полно. О чём хочется поговорить — так это о минусах данного метода.

Главный минус данного метода по сравнению с ray tracing в том, что качество теней напрямую зависит от разрешения текстуры, в которую тени рендерятся (в то время, как качество ray traced теней всегда идеально). Что это означает де-факто для визуала? Например, у нас есть лампочка, которая использует shadow map (карту теней) разрешением 512х512. Издалека тени от данной лампочки кажутся четкими, но стоит «подлететь» поближе, как тень быстро теряет своё качество.

Конечно, есть методы борьбы с данным артефактом. Например, использовать алгоритмы для сглаживания и смягчения теней. Это помогает до определённой степени. Но что, если мы, например, не хотим мягкие тени? Если хотим, чтобы в точке контакта с поверхностью тень была жесткой? Если увеличить разрешение shadow map, то данный артефакт также исчезнет. (Ну не совсем — всегда можно найти зум, при котором пикселизация вновь вылезет). Но увеличение размера карты теней немедленно наказывает нас — FPS падает, количество памяти уменьшается. А память весьма ценный ресурс, особенно на консолях. К тому же, если теневых источников света в кадре 1000? Для каждого использовать шадоумапу 8192x8192 — эдак никаких ресурсов не хватит.

Адаптивные методы теневых карт

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

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

Но работает ли такой подход, если у нас spot или directional light? Ладно, для spot light можно находить расстояние до light volume, это не так тривиально как в случае point, но тоже не очень сложно и худо-бедно сработает.

Но как быть с солнцем? Солнце бесконечно удалено от главной камеры, оперировать расстояниями до источника света тут бессмысленно. Что можно придумать, чтобы более эффективно использовать пространство теневой карты для солнца? Для решения такой проблемы есть метод так называемых «каскадов». Есть несколько пермутаций данного метода, различающихся по имплементации, но общий подход у всех один. Пространство разбивается на «каскады» — в зависимоти от удаления от главной камеры. Каскады — это, по сути, несколько теневых карт (с точки зрения ресурсов чаще всего это одна большая текстура, поделенная на несколько участков) одинакового размера, в которые рисуются объекты в зависимости от попадания в «каскады». Таким образом получается, что, например, область вокруг камеры размерами 15м х 15м получает в теневой карте, например, участок 1024х1024, следующий каскад — уже значительно больше по размерам — 30м х 30м, но получает те же 1024х1024. Но, так как объекты данного каскада удалены от камеры, то разница с точки зрения главной камеры будет минимальна.

Данный подход, в целом, неплохо работает и по сей день. Для него придумано немало оптимизаций, которые позволяют еще немного улучшить данный подход. Но даже с «каскадами» у данного подхода остаётся всё тот же классический недостаток — tradeoff пикселизация / перформанс. Всё-таки 15м х 15м — это много, а 1024х1024 — не очень. Можно увеличивать разрешение шадоумапы, играться с размерами каскадов, пока не найдётся приемлемое сочетание перформанс / качество. Тут всё зависит и от специфики проекта и от того, какой уровень детализации теней необходим. Понятно, что в FPS данная проблема стоит более остро, чем, например, в TPS или стратегиях. В более или менее современных играх эта проблема так и решается — находится приемлимый баланс в регулировке каскадов.

Каковы же недостатки классических каскадов в целом? Их несколько.

Первый фундаментальный недостаток — рисование объектов несколько раз. Тогда как более мелкие объекты можно однозначно отнести к какому-то каскаду и рисовать 1 раз, то более крупные попадают сразу в несколько каскадов и вызывают дополнительные дипы (к таким крупным объектам, как правило, относятся terrain, здания, транспортные средства и т.п.)

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

Rectilinear Texture Warping (for Fast Adaptive Shadow Mapping)

Наконец-то переходим из обзорной части к обсуждаемой теме. Автором данного метода, насколько мне известно, является Paul Rosen из University of South Florida (информацию можно найти тут: http://www.cspaul.com/wordpress/projects-rtw/).

Итак, метод shadow map warping преследует те же цели, что и, например, каскады — позволяет использовать пространство более эффективно. Но с более высокой степенью адаптивности, чем каскады. Каскады для адаптирования используют лишь положение и направление взгляда главной камеры, в то время как SMW использует еще и актуальный буфер глубины (depth buffer), позволяя в точности определить, какая часть теневой карты будет видна, а какая — нет.

Общий алгоритм метода таков:

1. Мы берем depth buffer (если есть earlyZ, то можно взять его, иначе — можно взять с прошлого кадра) 
2. Делаем репроекцию в light space, т.е. как бы источник света увидел в точности то, что видели мы. 
При репроекции в пиксели записывается importance информация, которая позволяет судить о том, насколько данный пиксель важен с 
точки зрения главной камеры. В качестве importance логично использовать какую-то функцию от расстояния до главной камеры. 
3. На основе репроекции и importance map создаётся warp buffer — буффер, в котором содержатся коэффициенты «сжатия» — насколько 
та или иная область теневой карты важна и должна быть расширена (ну или наоборот, неважна — и должна быть сужена). 
4. С помощью warp buffer выполняется эффективный рендер теней в один проход. На получившейся теневой карте те объекты (части 
объектов), тени от которых находятся близко к главной камере, будут занимать много места, а те объекты, тени от которых не видны, 
могут схлопнуться в один пиксель. 
5. С помощью того же warp buffer теневые карты резолвятся во front pass. 
6. Profit!

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

Детали имплементации

В данном разделе я опишу те места в моей реализации RTW, которые могут вызвать трудности и вопросы. Полный искодный код моей DX11 standalone тестовой версии RTW можно посмотреть вот тут: 
https://github.com/m10914/FETT_framework, ветка rectilinear_shadows

Итак, первое, что нужно сделать — это репроекцию depth buffer в пространство теневой камеры.

Делать это можно с помощью compute shader, с использованием атомарных операций, ведь несколько точек front buffer могут репроектиться в одну и ту же точку shadow buffer.

Код CS-шейдера репроекции:

SamplerState samplerDefault : register(s0);
Texture2D txDepthBuffer : register(t0);
RWStructuredBuffer<int> outBuffer : register(u0);

cbuffer cbDefault : register(b0)
{
 matrix matWorldViewInv;
 matrix matProjInv;
 
 matrix matWorldViewLight;
 matrix matProjLight;
};

[numthreads(16, 16, 1)]
void cs_main(uint3 Gid : SV_GroupID, uint3 DTid : SV_DispatchThreadID, 
 uint3 GTid : SV_GroupThreadID, uint GI : SV_GroupIndex)
{
 float2 texCoord = float2(float2(DTid.xy) / RTW_WIDTH);
 float depth = txDepthBuffer.SampleLevel(samplerDefault, texCoord, 0).r;

 // reconstruction
 float2 cspos = float2(texCoord.x * 2 - 1, (1-texCoord.y) * 2 - 1);
 float4 depthCoord = float4(cspos.xy, depth, 1);
 depthCoord = mul(matProjInv, depthCoord);
 depthCoord = mul(matWorldViewInv, depthCoord);
 depthCoord /= depthCoord.w;

 // reprojection
 float4 ncoord = mul(matWorldViewLight, depthCoord);
 ncoord = mul(matProjLight, ncoord);
 ncoord /= ncoord.w;
 ncoord.xy = mad(ncoord.xy, 0.5, 0.5);
 
 int indX = int(ncoord.x * RTW_WIDTH);
 int indY = int((1.0 - ncoord.y) * RTW_WIDTH);
 int index = indX + indY*RTW_WIDTH;
 
 //linearize
 float f = 1;
 float n = 0.1;
 float z = (2 * n) / (f + n - depth * (f - n));
 float intermediate = saturate(1-z);
 int rval = intermediate * 100000.0;

 if (indX < RTW_WIDTH && indX >= 0 && indY >= 0 && indY < RTW_WIDTH)
 {
 InterlockedMax(outBuffer[index], rval);
 }
}

Вначале реконструируем world position пикселя, потом делаем проекцию в light space, вычисляем importance и через атомарную операцию записываем в результирующий буффер. В данном случае importance обратно пропорционально линейной глубине, так как 0 глубины должен давать абсолютную важность (это означает, что данный пиксель находится ПРЯМО перед камерой), а 1 глубины — нулевую.

Второй этап — создание warp buffer. Тут важную роль играет слово rectilinear — прямоугольный. Особенность метода заключается в том, что варпинг происходит независимо только по двум осям x и y. Потому сам буфер состоит из двух одномерных массивов, которые соответствуют осям x и y теневой карты. Для создания warp buffer вначале из 2D importance map создаются два 1D importance array. Элементы независимо собираются по осям и фильтруются по max. Это означает, что вся линия, где есть хоть одна важная точка, будет считаться важной.

SamplerState samLinear : register(s0);
SamplerState samBackbuffer : register(s1);
SamplerState samDepth : register(s2);

//if x == y, we can do this trick - unite two buffers into one
RWStructuredBuffer<float2> outBuffer : register(u0);

StructuredBuffer<int> inBuffer : register(t0);

[numthreads(8, 1, 1)] // dispatch 128,1,1 - we have 1024 x calls
void CalcImportance(uint3 Gid : SV_GroupID, uint3 DTid : SV_DispatchThreadID, 
 uint3 GTid : SV_GroupThreadID, uint GI : SV_GroupIndex)
{
 float2 res = 0;
 for (int i = 0; i < WIDTH; i++)
 {
 res.x = max(res.x, float(inBuffer[int(DTid.x*WIDTH) + i]) / 100000.0);
 res.y = max(res.y, float(inBuffer[DTid.x + int(i*WIDTH)]) / 100000.0);
 }
 outBuffer[DTid.x] = res.xy;
}

Затем importance arrays конвертируются в warp buffers (которые тоже являют собой два одномерных массива). Чтобы варпинг не происходил скачками, неплохо бы сделать блюр получившегося warp buffer.

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

SamplerState samLinear : register(s0);
SamplerState samBackbuffer : register(s1);
SamplerState samDepth : register(s2);

RWStructuredBuffer<float2> outBuffer : register(u0);
StructuredBuffer<float2> inBuffer : register(t0);

[numthreads(8, 1, 1)] // dispatch 128,1,1 - we have 1024 x calls
void CalcWarp(uint3 Gid : SV_GroupID, uint3 DTid : SV_DispatchThreadID, 
 uint3 GTid : SV_GroupThreadID, uint GI : SV_GroupIndex)
{
 float2 totalSum = 0;
 float2 partialSum = 0;

 for (int i = 0; i < WIDTH; i++)
 {
 totalSum += inBuffer[i].xy;
 if (i == DTid.x)
 partialSum = totalSum;
 }
 
 outBuffer[DTid.x] = (partialSum / totalSum - float2(DTid.xx) / WIDTH);
}

[numthreads(8, 1, 1)]
void BlurWarp(uint3 Gid : SV_GroupID, uint3 DTid : SV_DispatchThreadID, 
 uint3 GTid : SV_GroupThreadID, uint GI : SV_GroupIndex)
{
 float coeffs[7] = { 0.127325, 0.107778, 0.081638, 0.055335, 0.033562, 0.018216, 0.008847 };
 float2 sum = inBuffer[DTid.x] *0.134598;

 [unroll]
 for (int i = 0; i < 7; i++)
 {
 int ind_pos = min(DTid.x + i + 1, WIDTH);
 int ind_neg = max(0, DTid.x - i - 1);

 sum += (inBuffer[ind_pos] + inBuffer[ind_neg])*coeffs[i];
 }
 
 outBuffer[DTid.x] = sum;
}

Теперь у нас готов warp buffer. Большая часть работы сделана. Теперь при рендере в шадоумапу необходимо использовать warp buffer:

StructuredBuffer<float2> warpMaps : register( t0 );

[vertex shader]
...
float4 rpos = mul(input.Pos, mul(World, mvpLight));
rpos /= rpos.w;
rpos.xy = mad(float2(rpos.x, rpos.y), 0.5, 0.5);

float2 indexS = rpos.xy * WIDTH;
float2 warps = float2(
 lerp(warpMaps[floor(indexS.x)].y, warpMaps[floor(indexS.x) + 1].y, frac(indexS.x)),
 lerp(warpMaps[floor(indexS.y)].x, warpMaps[floor(indexS.y) + 1].x, frac(indexS.y))
 );
rpos.xy += warps;

...
output.Pos = rpos;

Вначале мы получаем координаты пикселя на шадоумапе в NDC. Затем по этим координатам находим необходимые элементы массива warpMaps (отдельно по осям X и Y) — и затем выполняем варпинг — увеличение/уменьшение объекта в зависимости от его «важности». Вот и всё, теперь в shadow map у нас объекты, заполняющие пространство соответствии с их важностью.

При резолве shadow map мы также должны использовать warp buffer, чтобы корректно рассчитать текстурные координаты:

[pixel shader]
...
//obtain standart, non-warped shadowmap coords
float2 ncoord = GetShadowmapCoordinates();

// perform warping
float2 indexS = ncoord.xy * WIDTH;
 float2 warps = float2(
 lerp(warpMaps[ceil(indexS.x)].y, warpMaps[ceil(indexS.x) + 1].y, frac(indexS.x)),
 lerp(warpMaps[ceil(indexS.y)].x, warpMaps[ceil(indexS.y) + 1].x, frac(indexS.y))
 );
ncoord.xy += warps;

// sample shadowmap
float shadowDepth = txShadowMap.Sample(samDepth, float2(ncoord.x, 1-ncoord.y)).r;

Вот и всё. Как выглядит данный метод в работе можно посмотреть в видео выше.

Недостатки

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

Джиттеринг

Метод очень чувствителен к положению камеры. Из-за этого даже микро-движение камеры может вызвать передвижение объектов на shadowmap. И если на важных объектах этого не будет заметно, то на объектах, занимающих мало пикселей на shadow map, это изменение пикселей будет очень заметно. Особенно это видно на тенях от тонких или мелких объектов — веток и листьев. Из-за постоянных микроизменений камеры возникает постоянное мельтешение тени — иначе говоря, джиттеринг. Данным недостатком обладают, к сожалению, все адаптивные методы. Можно уменьшить джиттеринг с помощью снаппинга главной камеры — использовать для расчетов координаты и вращения камеры с сильно уменьшенной точностью, чтобы микроизменения камеры не вызывали перераспределения теневой карты. Но полностью от него избавиться невозможно — джиттеринг — неизбежный спутник всех адаптивных методов, которые зависят от содержимого depth buffer и положения камеры.

Некорректный резолв

В данном конкретном методе есть еще один «фатальный» недостаток. Дело в том, что применение warp buffer при рендерингде в теневую карту повертексное, а при резолве — попиксельное. По сути это означает, что, если большой полигон сильно растянулся, то он «не в курсе», какой варпинг происходит у него в середине. А при резолве этот варпинг применится, что означает, что в центре такого полигона будет некорректные тени. Для того, чтобы избежать данного артефакта, используется адаптивная тесселяция. Смысл в данном случае как можно сильнее приблизить повертексный варп к попиксельному. Данный метод был опробован и он действительно почти полностью убирает этот артефакт, но, к сожалению, на правильную адаптивную тесселяцию уходит очень много времени, что убивает практически весь профит, связанный с переходом на RTW. Как вариант, можно изначально делать мелкую геометрию, тогда тесселяция не понадобится. Но этот вариант не выглядит удачным, так как накладывает ограничения на ассеты, а это обычно не очень приветствуется.

Еще что-нибудь

Есть еще один адаптивный теневой метод, который достоен упоминания. Он лишён недостатка «некорректный резолв», но в нём по-прежнему есть джиттеринг. Называется он Sample Distribution Shadow Maps. 
https://software.intel.com/en-us/articles/sample-distribution-shadow-maps

По сути своей данный метод имеет много общего с RTW: он также использует репроекцию depth buffer, но, вместо того, чтобы строить warp buffers он просто модифицирует теневую, уменьшая её фрустум и, таким образом, теневая камера рендерит только то, что видит главная камера.

Визуальная демонстрация:

Полезные ссылки

http://www.gamedev.ru/code/articles/GPSM  - похожий адаптивный метод для теней от Аврелия 
http://www.cspaul.com/wordpress/projects-rtw/