Разбор рендера фейковых теней (и не только) в Танки Онлайн

Привет! Меня зовут Артур, я работаю разработчиком в команде Unity компании Альтернатива Гейм. В этой статье я расскажу, как мы реализовали технику фейковых blob-теней в нашей игре Танки Онлайн на Nintendo Switch, используя проекционные меши, а также о том, какие еще применения мы нашли для этой техники.

Совсем недавно мы релизнулись на Свитч. Одна из проблем, с которой мы столкнулись при разработке, заключается в рисовании теней. Тени являются неотъемлемой частью 3D рендерера. Они делают картину более внятной, позволяют лучше понять, как расположены объекты в пространстве друг относительно друга. Свитч — весьма ограниченная железка с не очень высокими мощностями, и, чтобы выжать как можно больше производительности, мы решили попробовать реализовать хак для рисования теней, который успешно применялся в веб-клиенте игры еще давно, до перехода с Флэша на HTML5.

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

Способы отрисовки теней

Существует множество разных способов визуализировать тени при помощи разных технологий. Это можно сделать как в режиме реального времени, так и при оффлайн рендере или при запекании теней в заранее подготовленные текстуры. 

Более того, с расцветом мощностей GPU и технологий рейтрейсинга появилась техника Raytraced Shadows — отрисовка теней с помощью трассировки лучей. Данный способ затратный и требует дополнительного “денойза” (убирания шума вследствие недостаточного количества выборок лучей), но реалистичный. Какие же способы отрисовки теней распространены в видеоиграх, где нужно делать это быстро в рамках бюджета кадра и/или с широким спектром разного таргет железа?

Давайте рассмотрим самые популярные способы отрисовки теней и причины, по которым мы решили их пропустить:

• Shadow volume (стенсильные тени)
  В Doom 3, старых GTA, Neverwinter и других играх тени рисовались при помощи дополнительного буфера данных — Stencil buffer‘а. С его помощью можно отрисовать жесткие тени с четким контуром. Это техника называется Shadow Volume. Она включает в себя этап формирования этого самого «объёма тени». Для построения объема требуется рисовать увеличенную (обычно геометрическим/вертексным шейдером или на ЦПУ) геометрию вдобавок к основному проходу.

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

  Про них можно почитать еще тут: Стенсильные тени изнутри. / Графика / Статьи / Программирование игр / GameDev.ru — Разработка игр

  Жесткие уродливые тени и необходимость в частичном доделывании контента и его внедрения заставили нас отказаться от данной техники.

• Shadow mapping
  Другим, одним из самых распространенных способов на сегодня, является способ Shadow mapping. Геометрия рисуется в специальную текстуру с позиции источника света (как с камеры), в так называемые “шедоумапы”. Далее shadow receiver’ы (геометрия, принимающая тень) получают из них информацию о наложенной тени.

  Хорошие тени без лесенок у нас требуют высокого разрешения шедоумапы (1024×1024/2048×2048+), а мягкие тени тоже имеют свои накладные расходы. Увеличения GPU time нам хотелось не допустить.

Немного философии

С учетом различных ограничений в 3D графике (да и в программировании в целом) всегда открываются новые возможности для оптимизаций, не подходящие для общих универсальных случаев. Например, если вы точно знаете, что все поверхности в игре плоские и горизонтальные, вы можете просто второй раз отрисовать сплющенный шедоу кастер в отдельный Render Target (таргет, в который рендерим), сгладить, наложить на фреймбуфер и получить тени.

Подробнее об этом можно почитать тут: Cg Programming/Unity/Shadows on Planes — Wikibooks, open books for an open world

Blob shadows

Нам требовалось быстрое решение для общего случая, где поверхность произвольная. Здесь на помощь приходят blob shadows с процедурными проекционными мешами — фейковые тени в виде темного полупрозрачного объекта, повторяющие форму поверхности. Давайте по порядку.

Отклоненные методы фейковых теней

Наши ранние версии реализации теней в Танках на Юнити являлись шейдерными решениями и исполнялись на видеокарте. 

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

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

for (int i = 0; i <= _PositionsCount; i++) {     float3 center = _Positions[i].xyz;     half radius = 5;     float shadowBlob = saturate(distance(input.positionWS.xz, center.xz) / radius);     float yDiff = abs(center.y - input.positionWS.y);     float heightDifferent = step(radius / 3, yDiff);     shadowBlob = saturate(shadowBlob + heightDifferent);     color *= shadowBlob; }

Можно попробовать реализовать эффективный per-pixel куллинг теней при помощи компьют-шейдера или ЦПУ и многопоточности, разделив фрустум камеры на тайлы, как это делают для источников света в Forward+ освещении, но это тоже усложнило бы технику.

По сути отрисовка декалей — это такие же расходы производительности, как на источники света, что по CPU, что по GPU.

Полупрозрачные проекционные меши

А что, если строить геометрию на ЦПУ и рисовать ее как обычную полупрозрачную мешку?

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

Подход с проекционными мешами был успешно реализован в первых версиях Танков на Flash. Алгоритм был придуман и разработан программистом графики Владимиром Бабушкиным в первой версии Танков Онлайн, вдохновленным реализацией техники в Half Life 2. Задача была портировать его на Юнити.

Построение тени можно разделить на 3 этапа: 

• сбор треугольников

• аналитическое построение геометрии

• заливка данных меша (vertex, index buffers) на GPU.

Ускоряющая структура

Поскольку треугольников на сцене много, необходимо сформировать ускоряющую структуру, позволяющую быстро искать нужные близкие треугольники по баунду. Выбор делался между 2 структурами данных — регулярной сеткой (spatial hash) и KD-деревом.

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

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

Регулярная сетка

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

Как она строится? В физических движках при определении коллизий в реальном времени существуют такие понятия определения пересечения геометрических фигур как: “broad phase” (широкая фаза поиска) и “narrow phase” (узкая фаза поиска). Широкая фаза содержит простые, грубые проверки и нужна для раннего выхода в случае, если пересечения точно нет. Узкая фаза более сложная и дает точные результаты. Так вот, у нас похожая история с фазами.

При построении сетки мы смотрим по AABB треугольника, в какие ячейки сетки он попадает — это можно сравнить с “broad phase” — широкой фазой определения пересечения геометрических фигур. Далее по теореме о разделяющей оси мы проверяем пересечение известных после широкой фазы ячеек с треугольником, что можно назвать “narrow phase” определения пересечения. После данного этапа мы знаем, в каких ячейках находится треугольник.

Построение геометрии работает с треугольниками, полученными с ускоряющей структуры — регулярной сетки. По сути мы просто отсекаем треугольники для того, чтобы тень четко проходила по контуру баунда тени. Все это исполняется в джобах, которые создаются в нужное время в кадре и принудительно комплитятся в конце (в LateUpdate). Таким образом, мы не только распараллелили работу построения теней с главным потоком, мы также распараллелили все джобы между собой, благодаря чему они работают одновременно и параллельно от главного потока. Также джобы «обмазаны» SIMD-математикой и Burst’ом, чтобы выжать как можно больше производительности.

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

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

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

public void Finish() {     Profiler.BeginSample("GridFinalize");     faceReps = new bool[_trianglesCount];          for (var i = 0; i < earlyPositionsList!.Length; i++) {         var list = earlyPositionsList[i];          if (list == null)         {             continue;         }         if (list.Count == 0)         {             continue;         }                  var count = 0;         var trianglesCount = positions.Count; // start         for (var j = 0; j < list.Count; j++) {             positions.Add(list[j]);             count++;         }                  cells[i] = new StartRangeTriangles {Start = trianglesCount, Range = count};     }          positions.Capacity = positions.Count; // мы уменьшаем капасити списка до количества      earlyPositionsList = null;     IsReady = true;     GC.Collect();     Profiler.EndSample(); }

При добавлении треугольников в сетку мы также сохраняем у них идентификатор, который потом будет использоваться для проверки повторного вхождения в сетку. Кстати, существенный прирост построения мы получили, реализовав проверку на вхождение треугольника в одну ячейку. Если он входит только в одну, то не нужно по теореме о разделяющей оси искать его пересечение с другими. Потому и идентификатор их равен -1. Так выглядит код получения треугольников по координатам:

[Il2CppSetOption(Option.ArrayBoundsChecks, false)] [Il2CppSetOption(Option.NullChecks, false)] [Il2CppSetOption(Option.DivideByZeroChecks, false)] public void GetTriangles(Int3 minCoords, Int3 maxCoords, ref SimpleList<FacePositions> results, bool shadow = false) {     for (var x = minCoords.x; x <= maxCoords.x; x++) {         for (var y = minCoords.y; y <= maxCoords.y; y++) {             for (var z = minCoords.z; z <= maxCoords.z; z++) {                 var idx = CalculateHash(x, y, z);                 if (idx < 0 || idx >= cells.Length)                 {                     continue;                 }                  var packed = cells[idx];                 for (int i = packed.Start; i < packed.Start + packed.Range; i++) {                     var face = positions[i];                     if (shadow && !face.InShadow) {                         continue;                     }                      // если -1 то не нужно добавлять треугольник в массив повторений                     if (face.Id == -1) {                         results.Add(positions[i]);                     }                     else if (!faceReps![face.Id]) {                         results.Add(positions[i]);                         faceReps[face.Id] = true;                         repeatedFacesIndices.Add(face.Id);                     }                 }             }         }     }     ClearRepeatedFaces(); }

Итоги

Тень выглядит вполне естественно и рисуется с Multiply бленд режимом.

Но…

Мы столкнулись с некоторыми трудностями.

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

У нас в игре для игроков есть два вида карт, на которых проходят танковые сражения: Legacy и Remaster. Legacy были созданы около 10 лет назад, а Remaster — современные. На Legacy картах у нас мало геометрии и там подрезка треугольников очень быстрая, но на Remaster картах количество треугольников существенно выше, что требует больше времени на построение теней. Для единоразового построения это норм, но для построения тени каждый кадр может требоваться слишком много времени. Мы реализовали механизм кэширования запросов регулярной сетки — если координаты баундов не меняются, не надо делать поиск снова, но подрезку надо делать всегда, поскольку танк почти всегда движется.

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

Шедоумапа с разрешением 2048×2048 и средним качеством мягких теней добавляет где-то 3.5 ms к GPU Time. Построение одной фейковой тени занимает 0.1-0.3 ms — сложно сказать точно, потому что построение происходит параллельно, да и зависит от размеров баунда, а это, в свою очередь, зависит от выбранного игроком корпуса. Не стоит забывать и про потребление памяти — регулярная сетка на Remaster карте Forest MM Remaster занимает 44 МБ оперативной памяти. Да, это не так уж и много, но на Свитче всего 3 ГБ оперативной памяти выделено на игру, а ведь эта память может быть сильно фрагментирована, а GC в Unity не двигающий (по крайней мере, пока что), и поэтому это число весьма ощутимо.

Оптимизации

Довольно много времени было выделено на оптимизации. Давайте поговорим о них подробнее.

Построение по AABB

Можно строить меш по выровненному баунду, а не по ориентированному. Тогда не нужен перевод в локальные координаты при подрезке, но есть недостаток: в горизонтальной проекции баунд должен быть квадратным (x=z), а в шейдере нужен поворот UV-шек. Баунды становятся больше, особенно если танк повернут по диагонали относительно мировых осей координат.

Отключение подрезки (частичное или полное)

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

Куллинг теней

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

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

По итогу мы извлекли больше выгоды из проекционных мешей для декалей и источника света-линии, чем для теней, поскольку строить тени каждого танка слишком дорого на Remaster картах и выжирает много CPU Time, а единоразовые построения не занимают много времени и выполняются за кадр, и меши рисуются как просто полупрозрачные объекты.

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

Дальнейшие улучшения технологии

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

Так как мы не успели протестировать рендер в текстуру, он не вошел в релиз, но мы еще вернемся к этой идее!

Вывод

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

Скорость оказалась не такой высокой на Remaster картах, но все же и не слишком низкая. К тому же, симплификация пропов на картах позволит очень ускорить построение теней и проекционных мешей в принципе.

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