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

Розповідь про те, як я спробував побудувати гарні тривимірні тіні не виходячи за рамки затишного двомірного гейм-девелопменту, і що з цього вийшло.



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


Картинка мені сподобалася. Завдяки світла та тіні відразу в неї з'явився якийсь настрій, якась глибина. Засмучувало тільки те, що тіні виглядали не зовсім натурально. І не дивно, адже illuminated.js працює з чисто 2D-оточенням (читай — вид зверху чи збоку), а у мене тут — псевдо-3D (вид спереду/зверху). А хочеться і кінцевих тіней замість нескінченних (якщо джерело світла високо), і щоб світ через прорізи в паркані проходив. Загалом, щоб красиво було.

Отже, постановка задачі виглядала так:

  • є намальований набір спрайтів (це важливо, тому що сам я особливо малювати не вмію і мені простіше генерувати зображення з вихідних матеріалів)
  • перспектива — зверху/спереду, псевдо-3D. Якщо просто зверху/збоку, то підходять і illuminated.js і способи згадані вище.
  • при цьому движок 2D. Все-таки логіку простіше робити в двох вимірах, рівні простіше складати, інструментарій є — для ludum dare це все досить важливо.
Примітка для читачівДосвідчені розробники ігор і 3D-додатків навряд чи знайдуть для себе щось нове. Якщо вам просто важливий результат і/або ближче розробка на Unity, то таку сцену простіше скласти в ньому — і світло, і тіні будуть працювати з коробки. Цю статтю можна розглядати як експеримент, а так само як невеликий порада для тих, хто, як і я, не дружить з олівцями і фотошопом: навіть без навичок малювання, можна зробити красиво іншими засобами.

Рішення 1. Наївний raycasting
посилання на приклад

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


Робити таке 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 спрайт, зрізи для кожної висоти. Можна назвати це воксельної моделлю, але на той момент я такого слова ще не знав :)


Шейдер отримував на вхід цю текстуру, а так само карту сцени з відмітками де який спрайт отрисован (номер спрайту закодований кольором). В результаті алгоритм зводився до наступного:

  1. беремо поточну точку (x, y, z), де z == 0 (земля)
  2. визначаємо напрямок до джерела світла. нормалізуємо цей вектор, щоб на 1 крок рухатися не більше ніж на 1 піксель в будь-якому напрямку.

  3. виконуємо N кроків у бік джерела світла. Для кожного кроку:
    1. дивимося текстуру з відмітками. Якщо для поточної (x,y) координати відзначено, що там є спрайт, беремо його номер. Інакше точка порожня, продовжуємо рух.
    2. дивимося воксельную модель для даного спрайту. Якщо для наших поточних (x,y,z) там знаходиться непрозорий піксель, то зупиняємося і відзначаємо, що піксель затінений.

Як не дивно, все завелося майже відразу, давши таку картинку:


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

Спробуємо вирішити обидві проблеми відразу. У шейдере ми завжди кидаємо промінь від землі. Однак у нас є 3D-моделі спрайтів, і ми знаємо яка точка спрайту на якій висоті знаходиться. Скористаємося цим знанням.


Зовсім інша справа.

Можна помітити, що тіні у нас досить різкі — що на землі, що на самих об'єктах в силу їх «пикселизованности». Я теж звернув на це увагу і вже став думати як вирішувати цю проблему, поки не зіткнувся з проблемою іншого роду:


Думаю, ті хто вже подивився код шейдера, побачили відразу купа проблем:

  • вкладені цикли (спочатку за джерелами світла, потім за «кроків» при raycasting)
  • каскадні звернення до текстур (спочатку до однієї щоб перевірити чи є в цій точці спрайт, потім до іншого — перевірити наявність пікселя в потрібній точці)
  • багато умовних операторів (if)
Так з'явилося друге рішення.

Рішення 2: покращений рейкастинг
посилання на приклад

Щоб усунути каскадне звернення до текстур було вирішено зробити одну текстуру з 3D картою всього світу. Модельки у нас невисокі, від 16 до 32 пікселів. Рішенням в лоб було б побудувати 32 «зрізу» світу і покласти їх один за одним в одну картинку-текстуру. Але так зробити не вийде: при розмірі світу 640х640 отримуємо розмір текстури в 32 рази більше, а WebGL стільки не перетравлює. Вірніше, як я підозрюю, може і переварити в залежності від поєднання ОС/Браузер/Відеокарта, але краще на це не розраховувати.

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

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


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

Створення такої карти в javascript особливих труднощів не представляє, благо побітові операції є. А ось в шейдере чекала засідка.


Робити нема чого — доведеться займатися обчисленнями. По суті мені потрібна тільки одна операції — перевірка того, що біт встановлений в потрібній позиції (позиція = координата 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 (більш детальні викладки — в кінці статті).



До цього часу я вже порядком начитався про тіні і з'ясував, що в 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/ — де вказані розміри модельок деяких персонажів популярних ігор. Там я і знайшов ось це:


Що ж, з 25 моїх ялинок можна зібрати цілого Адама Дженсена!

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

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

Рішення працює, і навіть малює тіні, не гірше ніж мій raycasting.


Звичайно, тепер ялинки відмальовує «зверху», т. к. для побудови тіней це їх правильне положення, і ми частково втратили «магію» двомірного варіанти… Але і цю проблему можна вирішити.

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 буде застосовувати освітлення і тіні по старому, як якщо б об'єкт не був повернений, а ось відображатися він буде повернений.


Підсумки
Давайте подивимося, як виглядають всі три варіанти:
Наївний raycasting Raycasting 3D



І порівняємо продуктивність різних варіантів.

Для оцінки продуктивності я використовував показник 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




Що кидається в очі: FF варіант з 3D показує себе, як правило, гірше варіанту з RC. Судячи з усього, проблема в цьому:


А результат це, схоже, ось такого бага в 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 — за замовчуванням він 512x512.

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

  • FF поки все сумно
  • У випадку з raycasting ми отримуємо проблеми коли тіні повинні відкидати рухомі предмети — для цього доведеться кожен кадр перемальовувати 3D-карту і відправляти її в шейдер.
  • У випадку з 3D-рішенням через three.js ми досить сильно залежимо від можливостей бібліотеки. Скажімо, зробити тіні синіми (не знаю навіщо, правда) ми не зможемо. І відблиск від джерела світла на «підлозі» (світле пляма під РР.) мені так і не вдалося прибрати.
На цьому все. Сподіваюся, було корисно.

Дякую моїм колегам по LD Руслану і Толі за допомогу в тестуванні.
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.