Тень на плетень, или 25 елок для Адама Дженсена

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

7c99036ab6864078b2a2437404178b06.png

Предыстория


Во время подготовки к очередному Ludum Dare я решил попробовать набросать несколько игр разных жанров. Опыта в гейм-девелопменте у меня в целом нет, поэтому я рассматривал только 2D игры и только движок Phaser.js. Одной из идей был »2D-стелс». А где стелс, там и работа со светом и тенью. Погуглив немного и найдя, между прочим, вот такие хорошие статьи на Хабре (раз и два), я взял библиотеку Illuminated.js, случайный набор ассетов с OpenGameArt.org и вскоре получил вот такую картинку:
af8d3ab8b7fd4187a8bcfb0133000c94.png

Картинка мне понравилась. Благодаря свету и теням сразу в ней появилось какое-то настроение, какая-то глубина. Расстраивало только то, что тени выглядели не совсем натурально. И немудрено, ведь illuminated.js работает с чисто 2D-окружением (читай — вид сверху или сбоку), а у меня тут — псевдо-3D (вид спереди/сверху). А хочется и конечных теней вместо бесконечных (если источник света высоко), и чтобы свет через прорези в заборе проходил. В общем, чтобы красиво было.

Итого, постановка задачи выглядела так:

  • есть нарисованный набор спрайтов (это важно, т.к. сам я рисовать особо не умею и мне проще генерировать изображения из исходных материалов)
  • перспектива — сверху/спереди, псевдо-3D. Если просто сверху/сбоку, то подходят и illuminated.js и способы упомянутые выше.
  • при этом движок 2D. Все-таки логику проще делать в двух измерениях, уровни проще составлять, инструментарий есть — для ludum dare это все довольно важно.

Примечание для читателей
Опытные разработчики игр и 3D-приложений вряд ли найдут для себя что-то новое. Если вам просто важен результат и/или ближе разработка на Unity, то такую сцену проще составить в нем — и свет, и тени будут работать из коробки. Эту статью можно рассматривать как эксперимент, а так же как небольшой совет для тех кто, как и я, не дружит с карандашами и фотошопом: даже без навыков рисования, можно сделать красиво другими средствами.

Решение 1. Наивный raycasting


(ссылка на пример)

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

2cd7ceac12824febb69b21322d9eca5b.png

Делать такое javascript-ом очевидно не стоило, поэтому на помощь пришли WebGL fragment shader-ы. Fragment Shader выполняется видеокарточкой для каждого пикселя внутри рисуемого полигона (в нашем случае — прямоугольника размером с игровой canvas), что как раз совпадает с нашими целями. Осталось передать в шейдер сведения об источниках света и препятствиях.
Если интересно как работать с шейдерами в Phaser.js
Вот тут можно посмотреть простой пример: http://phaser.io/examples/v2/filters/basic

Если с источниками света более-менее ясно, то препятствия нужно перенести в три измерения. Скажем, елка 16×16 должна стать чем-то вроде конуса с радиусом основания 8 и высотой 16. Такой конус можно получить вращением оригинального спрайта. А забору достаточно добавить толщину 2–3 пикселя.

В итоге, все используемые спрайты превратились в 3D модели выполненные в виде текстуры — 16 изображений на 1 спрайт, срезы для каждой высоты. Можно назвать это воксельной моделью, но на тот момент я такого слова еще не знал :)

0cfae7cedd1f43df8e17a7689d93002d.png

Шейдер получал на вход эту текстуру, а так же карту сцены с отметками где какой спрайт отрисован (номер спрайта закодирован цветом). В итоге алгоритм сводился к следующему:
b4680e8744a74a9bb1c33a9b844a88d4.png
  1. берем текущую точку (x, y, z), где z == 0 (земля)
  2. определяем направление к источнику света. нормализуем этот вектор, чтобы на 1 шаг двигаться не более чем на 1 пиксель в любом направлении.
  3. выполняем N шагов в сторону источника света. Для каждого шага:
    1. смотрим текстуру с отметками. Если для текущей (x, y) координаты отмечено, что там есть спрайт, берем его номер. Иначе точка пуста, продолжаем движение.
    2. смотрим воксельную модель для данного спрайта. Если для наших текущих (x, y, z) там находится непрозрачный пиксель, то останавливаемся и отмечаем, что пиксель затенен.


Как ни странно, все завелось почти сразу, дав такую картинку:
7d52db4986614e3197b9cafee8fa87f4.png
cc2203cd3cd84f9aadc9f85856985849.png

В целом, неплохо. Но явно не хватает освещенности/затенения самих предметов. Скажем, елки «ниже» источника света находятся по факту ближе к нам и должны быть затенены. Елка справа должна быть освещена наполовину. А надгробный камень на скриншоте справа должен быть частично затенен забором.

Попробуем решить обе проблемы сразу. В шейдере мы всегда бросаем луч от земли. Однако у нас есть 3D-модели спрайтов, и мы знаем какая точка спрайта на какой высоте располагается. Воспользуемся этим знанием.

9724456603b24ba1bfe16802c550a0bd.png
23e0f5e05f7f436787686a0460efa479.png
Совсем другое дело.

Можно заметить, что тени у нас довольно резкие — что на земле, что на самих объектах в силу их «пикселизованности». Я тоже обратил на это внимание и уже стал думать как решать эту проблему, пока не столкнулся с проблемой иного рода:

126fcba80f354bcf9c1d45b5bb852925.png

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

Так появилось второе решение.

Решение 2: улучшенный рейкастинг


(ссылка на пример)

Чтобы устранить каскадное обращение к текстурам было решено сделать одну текстуру с 3D картой всего мира. Модельки у нас невысокие, от 16 до 32 пикселей. Решением в лоб было бы построить 32 «среза» мира и положить их друг за другом в одну картинку-текстуру. Но так сделать не получится: при размере мира 640×640 получаем размер текстуры в 32 раза больше, а WebGL столько не переваривает. Вернее, как я подозреваю, может и переварить в зависимости от сочетания ОС/Браузер/Видеокарта, но лучше на это не рассчитывать.

Что ж, надо подумать как это все ужать. В целом, нам ни к чему информация о цвете пикселя, только его наличие/отсутствие в заданной точке.

В WebGL при загрузке текстуры мы можем указывать ее формат (целочисленные компоненты цвета, или с плавающей точкой, наличие/отсутствие alpha-канала). Но т.к. мы работаем через Phaser, тот по-умолчанию использует однобайтовые компоненты цвета. У нас 3 цветовых байта на пиксель, можно уместить в них информацию о 24 пикселях. Если упаковывать таким образом «высоту», то нам понадобится текстура в 2 раза больше по размеру чем мир — половина для высот с 0 до 23 и половина для высот с 24 до 31. Или, для простоты, лучше разбить ровно напополам — ниже 16 и выше 16 соответственно.

c87e77d667ba411f9493e366e8f0ed7d.png

А как же альфа-канал?
Вообще у нас помимо цветовых компонентов есть еще альфа-канал — целый байт. Однако тут все упирается в наличие/отсутствие «предварительного перемножения» (premultiplied alpha). Если этот режим включен (он по-умолчанию включен, кроме того в IE невозможно его отключить), то компоненты цвета не могут быть по значению больше значения альфа-канала, такой цвет считается некорректным и, судя по всему, принудительно приводится к нужному виду. Это приводит к искажению трех цветовых байт при некоторых значениях альфа-байта. Поэтому на всякий случай я не задействую альфа-канал.

Создание такой карты в javascript особого труда не представляет, благо побитовые операции есть. А вот в шейдере ждала засада.
2a073c0d9aba447d92f7460a9ece53bc.png

Делать нечего — придется заниматься вычислениями. По сути мне нужна только одна операции — проверка того что бит установлен в нужной позиции (позиция = координата z). С побитовыми операциями это был бы AND по маске, а так пришлось написать вот такую функцию:
float checkBitF(float val, float bit) {
     float f = pow(2., floor(mod(bit, 16.)));
     return step(1., mod(floor(val/f),2.));
}

Если перевести на человеческий язык (ну или хотя бы js), то получится вот что:
 function checkBitF(val, bit) {
  f = Math.pow(2, bit % 16); // Равносильно f = 1 << bit;
  f1 = Math.floor(val / f); // равносильно сдвигу вправо, f1 = val >> bit
  if (f1 % 2 < 1) return 0; else return 1; //если бит установлен, вернется 1. иначе 0.
}

Кстати, если вдруг вы думаете что mod в шейдерах всегда возвращает целое число — это не так.

Избавиться от условных операторов можно при помощью built-in функций — mix, step, clamp. Их использование позволяет GPU лучше оптимизировать код.

Небольшой пример
Посмотрите вот на такой шейдер: www.shadertoy.com/view/llyXD1.
Сверху вы увидите такие строчки:
#define MAX_STEPS 1500
#define STEP_DIV MAX_STEPS
#define raycast raycastMath

Для начала настройте число MAX_STEPS так, чтобы иметь средний fps чуть ниже 60 (учтите что значения больше 60 не показываются). После этого поменяйте третью строчку на
#define raycast raycastIf

У меня fps 40 при raycastMath и 32 при raycastIf. Разница, по сути, состоит в следующих строчках:

Условный оператор:


bool isBlack(vec4 color) {
    if (color.r + color.b + color.g < 20./255.) {
        return true;
    }
    return false;
}

Вычисление:

float getBlackness(vec4 color) {
    return step(20./255., color.r + color.b + color.g);
}


Полученная в итоге картинка не особо отличалась от предыдущего решения, но fps был уже побольше раза в 1.5 — 2 (более подробные выкладки — в конце статьи).

0b3b5527ce844937980f55a162af2e0d.png

К этому времени я уже порядком начитался про тени и выяснил, что в 3D-мире чаще всего пользуются способом под названием shadow mapping. Суть его сводится к следующему:

  • сначала строим сцену с точки зрения источника света и запоминаем для каждого пикселя каждого треугольника расстояние от него до источника света.
  • далее полученную карту теней (shadow map) используем при построении сцены уже с точки зрения наблюдателя. Для каждого пикселя каждого треугольника сверяемся с соответствующей точкой на карте теней. Если есть пиксель расположенный ближе к источнику света — значит наш пиксель в тени.

Чтобы это работало как надо, нужно строить модели честными трехмерными полигонами, пиксельной текстурой тут уже не обойдешься. Phaser, будучи движком заточенным под 2D, не дает возможностей порулить вертексными шейдерами. Зато дает возможность отрисовать на себе произвольный canvas. Следовательно, мы можем построить 3D-сцену отдельно, сделать так чтобы рисовались только тени и затем нарисовать ее поверх нашей 2D-сцены.

Решение 3: 3D-тени


(ссылка на пример)

Для работы с трехмерными объектами я взял three.js, рассудив, что работая с webgl напрямую я провожусь значительно дольше.

Для начала надо было превратить спрайты в 3D-меши. На тот момент я познакомился с инструментом MagicaVoxel (хороший кстати инструмент для работы с вокселями), посмотрел как именно он делает экспорт в obj-файл и для начала решил повторить трансформацию. Алгоритм сводился к следующему:

  • берем воксельную модель (а ее строить я уже умел)
  • для каждого вокселя определяем грани, которые видимы, т.е. не граничат с другими вокселями
  • записываем по 2 треугольника для каждой грани + информацию о цвете. В three.js для своих кастомных геометрий хорошо подходит THREE.BufferGeometry. Я ради эксперимента попробовал было все воксели добавить на сцену как однопиксельные кубики (THREE.BoxGeometry)… в общем, не надо так делать.

Ради интереса, я конвертнул елку и посчитал количество треугольников. Оказалось, для одной маленькой елки 16×16х16 пикселей потребовалось около 1000 треугольников. Тогда друг дал мне вот такую ссылку — http://www.leadwerks.com/werkspace/topic/8435-rule-of-the-thumb-polygons-for-modelscharacter/ — где указаны размеры моделек некоторых персонажей популярных игр. Там я и нашел вот это:
4a3b7cf503f94123a6a6689fcbbd3722.png

Что ж, из 25 моих елок можно собрать целого Адама Дженсена!

В итоге я переделал конвертацию спрайтов, пропустив этап с «вокселями». Фигуры вращения (вроде елок) при этом получались более круглыми и освещались чуть более естественно (или неестественно — зависит от ваших взглядов на конусообразные елки). Для сокращения числа полигонов я перестал хранить информацию о цвете каждого из них (т.о. я смог объединять рядом лежащие полигоны в один), вместо этого я добавил исходный спрайт как текстуру материала и в полигонах ссылался на точки на этой текстуре (т.н. uv-mapping).

Все это привело к двукратному уменьшению числа треугольников но, что интересно, никак не повлияло на производительность. На производительность в этом решении влияли совсем другие вещи.

Решение работает, и даже рисует тени, не хуже чем мой raycasting.

082c06cb886647a380965341770a4db6.png

Конечно, теперь елки отрисовываются «сверху», т.к. для построения теней это их правильное положение, и мы частично потеряли «магию» двухмерного варианта… Но и эту проблему можно решить.

three.js (а может быть вообще любой 3D-движок, тут я пока не силен) для отрисовки одного объекта (mesh) требует наличия 2х вещей:

  • Geometry — информация о форме (читай — набор треугольников с различными аттрибутами — вектора нормалей, uv-координаты текстуры, цвет, и т.д.)
  • Material — информация о материале (читай — набор vertex/fragment shader-ов которые отрисовывают фигуру, применяя тени, освещение, дорисовывая блики и т.д. основываясь на свойствах материала). В three.js есть несколько доступных материалов, отличаются они внешним видом, поддержкой тех или иных функций (например, тени не все могут отрисовывать) и производительностью.

Таким образом, за конкретную отрисовку у нас отвечает material, вернее его шейдеры. Мы вполне можем взять материал и поправить vertex shader таким образом, чтобы модель рисовалась повернутой, но все вычисления (тени, освещенность) применялись к ней как будто поворота нет.

В итоге, я взял все объекты сцены и в самый конец vertex shader-а каждого дописал такие строки:

gl_Position.z = gl_Position.y;
gl_Position.y += -position.y/${size/2}. + position.z/${size/2}.;

где
  • size — размер мира (gl_Position должен содержать координаты от -1 до 1, где точка (0,0,0) — это центр сцены)
  • position — относительная позиция точки внутри фигуры, аттрибут vertix-а.

При этом я не трогал varying-переменные, которые передаются дальше в fragment shader. Поэтому fragment shader будет применять освещение и тени по старому, как если бы объект не был повернут, а вот отображаться он будет повернутым.
f9a7491b55544369a8a57ca575fe04d6.png

Итоги


Давайте посмотрим как выглядят все три варианта:
Наивный raycasting Raycasting 3D
cba7bfe5b16b4ca3a3792cbe97890009.png

9285037425f945ec85f2530ca7d1c429.png

fbef84ae69c4426f8a188427b0ee3612.png

И сравним производительность разных вариантов.

Для оценки производительности я использовал показатель FPS, который считается в Phaser.js. При чтении результатов надо учитывать, что Phaser.js не отображает FPS выше 60. Я честно попытался найти как это исправить, но не преуспел и решил забить.

Легенда по рабочим станциям
  • Mac — Macbook Pro
    Chrome не рассматривался, т.к. в нем почти везде FPS 60
  • MSI — Ноутбук с GeForce GTX 760M, Win8.
    FF не рассматривался т.к. многие примеры на нем не работали совсем
  • IG1/IG2 — рабочие станции с интегрированной видеокартой (Intel HD Graphics), Win7


66dcbd0740224971ad74ea466c8be7c3.png
da1e167926944861b47ff556401f61cb.png
a202b331c866477e96fe312cdf28ed24.png
Что бросается в глаза: в FF вариант с 3D показывает себя как правило хуже варианта с RC. Судя по всему, проблема в этом:
0d0974b3c47b4c52a6048ed59819edf0.png

А результат это, похоже, вот такого бага в FF: Low performance of texImage2D with canvas.

К сожалению, именно такой сценарий у меня и используется: сначала на canvas отрисовывает сцену three.js, а затем этот canvas используется как текстура фазером. Увы, никакого workaround я пока не придумал. (Разве что строить всю сцену, да и вообще всю игру, в three.js, но это противоречит выставленным условиям).

В хроме вариант с 3D выигрывает у raycasting раза в 2 в среднем. Впрочем, надо понимать, что скорость raycasting во многом зависит от размера сцены (вернее от размера отображаемой ее части). Например, можно построить тени на текстуре меньшего размера (скажем, в 2 раза меньше — тогда придется пускать в 4 раза меньше лучей), а blur скроет огрехи от уменьшения качества теней. В свою очередь, для 3D варианта можно менять размер shadow map texture — по-умолчанию он 512×512.

Выводы


  • «наивный» raycasting давал хороший FPS только на топовых машинах, адски нагревая при этом видеокарту
  • «улучшенный» raycasting и 3D — давали не меньше 40 FPS для Хрома на всех протестированных машинах при следующих условиях:
    •  — один источник света
    •  — четыре источника света + уменьшение текстуры/карты теней в 2 раза

  • В FF пока все печально
  • В случае с raycasting мы получаем проблемы когда тени должны отбрасывать движущиеся предметы — для этого придется каждый кадр перерисовывать 3D-карту и отправлять оную в шейдер.
  • В случае с 3D-решением через three.js мы довольно сильно зависим от возможностей библиотеки. Скажем, сделать тени синими (не знаю зачем, правда) мы не сможем. И блик от источника света на «полу» (светлое пятно под ГГ) мне так и не удалось убрать.

На этом все. Надеюсь, было полезно.

Спасибо моим коллегам по LD Руслану и Толе за помощь в тестировании.

Комментарии (1)

  • 16 января 2017 в 01:38

    0

    Как-то не очень естественно получается тень. Если судить по отбрасываемой тени забора и кустиков, то источник света должен находиться раза в 2–3 выше человечка, который ростом с забор.

© Habrahabr.ru