Декали на webGL.

Техническая часть.

Код не покажу, потому что это НДА и просто душно. Алгоритм расскажу, потому что это можно и круто. Всё это происходило давно, и все полезные на тот момент ссылки да ресурсы сейчас утеряны и/или неактуальны. Да и хуй с ними.

Что такое декали, если по какой-то причине твоя карьера прошла мимо них:

Мне нужно было их бахнуть на браузерном игровом движке Playcanvas. Требований было немного, вот они все трое:

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

И первым применением по плану должны были стать брызги крови на стенах, на полу, на любой геометрии, РАЗМАЗАТЬ ЭТО ДЕРЬМО ПО ВСЕЙ СЦЕНЕ. И думая о кровище, я от себя добавил ещё немного требований:

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

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

Все перестрелки между игорьками происходят на стороне CPU, то есть высчитывать направление и позишен декали придётся именно там. А рендерить придётся на GPU. Другой поганый момент — на GPU мне не сделать какую-то угарную структуру данных, в которую можно было бы на расслабоне складывать и хранить прилетающие из CPU декальки, которые при рендере доставать и юзать не снимая свитер. Значит удобно складывать и хранить эти декали придётся тоже на стороне CPU. Учитывая требования выше, мне нужна структура данных, у которой максимально быстрая вставка нового элемента, адекватно быстрый поиск элемента и максимально сильное похуй всё остальное. Спецфичи, которые могут помочь — у декалей три координаты, значит моя структурка может быть трёхмерной. Сразу же в голову пришло ЕБЕЩЕЕ ОКТОДЕРЕВО, оно ведь будто бы рождено для этой задачи, мэтчинг по требованиям сто из ста. И я его сделал. Вот как это говно у меня работало (ячейки октодерева во всём этом длинночтене я буду называть вокселями).

1. ИНИШИАЛ СОСТОЯНИЕ.
Существует структурка декали, в ней лежит матрица и какая-то кастомная инфа, например таймстамп или цвет или что угодно.
Существует тупа массив декалей. При ините естеесн пустой.
Существует структурка вокселя, в ней лежат восемь интеджеров (ссылки на декали в предыдущем массиве либо на другие воксели в этом же массиве); чекбокс subdivided; какая-то техническая инфа, которая я уже и не помню для нахуя.
Существует тупа массив вокселей. Оба массива нужны отдельно для отправки всех этих данных на GPU, потому что октодерево туда не отправить.
И собсна само октодерево: в инишиал состояни это просто один большой воксель размером с весь левел.

2. СПАВН.
Спавнится первая декаль, вторая и вплоть до восьмой — массив декалей пополняется, в большом вокселе восемь сцылок заполняются. И тут спавнится предательская девятая декаль. В массив она конечно на изи попадает, но в вокселе для неё места нету, все ссылки заняты. И этот кедр просто делится на восемь вокселей поменьше. Они попадают в массив вокселей. Те восемь декалей, которые в большом папе, распихиваются по его дочкам, папа-воксель ставит себе чекбокс subdivided, и ссылки на декали заменяет ссылками на дочек.

Ни хуя не понятно, но очень интересно. Слева до деления вокселя, справа после.

3. ПОИСК. Позишен свежей декальки поступает в первый большой папа-воксель. Если этот воксель уже разбит, то он оценивает, с какого раена свежая декаль, и кому из дочек её отправить, и отправляет. Доча-воксель, принявшая эту декаль, поступает с ней точно так же. И так до тех пор, пока декаль не дойдёт до вокселя, который ещё не разбит на дочек, и в котором есть для неё место.

4. ПРОФИТ. Казалось бы ни хера себе тут работы, компуктер перегреется. Хотя если ты шаришь за O(n), то тебе не казалось бы. Тем не менее. На тестах декали вставляются не то что с лагом, а с ускорением нахуй. Фпс вверх подскакивает, когда декаль спавнится. Шучу конечно, фпс просто не дёргается, никакого лага нету, всё работает максимально с кайфом. Октодерево аппрувед.

Маленькай момент с максимальной глубиной дерева, доколе оно может делиться. Тут изи посчитать, на карте максимально может бегать x челиков, в каждого можо сделать максимум y попаданий до разлома кабины. Пусть карта отмывается от крови раз в z каток. Итого максимально может заспавниться x*y*z декалей. Первые два множителя это данность, константа, факт, принимаем это. Третий множитель на тестах регулируем так, чтобы и крови копилось нормально, и переполнений дерева не возникало. Но вообще для деления дерева до глубины всего лишь пять уже требуется восемь в пятой степени успешных ранений игорьков — это 32 тысячи выстрелов, тридцать две тысячи нажатий ЛКМ при условии что все ниибаца меткие. Поэтому эта тяга с дроблением дерева в бесконечность меня не кошмарила. Алсо в воксели можно записывать их поколение, и просто его ограничить, но я кажется забил хер либо забыл.

Теперь нужно передать массив декалек на GPU и начатьь уже рендорить. Не так быстро, молодой человек. В webGL на тот момент не было никаких буферов, webGPU не существовал даже в открытой бете, прямого пути переправить сраный массив данных из проца в видяху на вебе просто нету. Но есть косой путь — текстуры. Значит надо просто задекодить объекты декалек в наборы пикселей, а на стороне шейдера раздекодить обратно, хуль тут сложного. Тут я особо ничего не делал, собрал пару кодов со стакОверфлоу, они по какой-то причине не работали, починил, бахнул пивасика, посмотрел серик, в то время «дом дракона» только начинался. В общем трансфер данных налажен, остался рендер. И раз уж все брызги крови будут одним и тем же материалом — почему бы их все не рендерить за один дроколл. Просто взять шейдер крови, накинуть сразу на всю геометрию в сцене, а декали использовать как маску для этого шейдера. И как раз количество декалей не будет влиять не перфоманс вообще, и все требования получаются выполнены. Так и сделал, весь левел со старта облит кровью, просто с альфой. Когда кто-то cum blood — декаль затирает маску, и в этом месте материал крови становится непрозрачный.

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

Чёрным воксели, красным декаль, зелёным рендер декали.

Центр декали в левом вокселе, там шейдер её находит и рендерит. В правом вокселе шейдер её не находит и не рендерит. Значит вставка декалей в воксели должна происходить по другому принципу. Не в тот воксель, внутри которого находится её центр, а во все воксели, с которыми она интерсектится. Внёс эту правку, на перфоманс не повлияло, всё хорошо. Теперь шейдер всегда понимает в каком пикселе сколько декалей находится.

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

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

декали в браузере 60 фпс жесть смотреть.

Гуманитарная часть.

На момент, когда мне эту задачку поставили, я не знал о внутренности декалей ровно ничего. Знал только, что такая технология существует, юзал декальки когда-то давно в анриле. Полез гуглить как там в плейканвасе с декалями вопрос обстоит. Не нашёл ничего вообще, про это были вопросы на форуме, вопросы без ответов, вопросы с ответвами от разрабов, дескать функционала такого у нас нету и не предвидится, сасайте палка. После я полез гуглить как сделать декали на openGL, нашёл полезную инфу про мапинг декалей, какой-то видос с не очень полезной, но крутой инфой от графоноинженера какой-то трипл-инди хуйни. Но не нашёл ничего, что могло бы мне помочь. Зато начерпавшись вот этой всей рандомной хуерги со всего интернета по запросу «decals openGL», решение по-тихонечку начало формироваться как будто бы само собой. Я просто сижу, в носу ковыряю, ничего не делаю, а идея приходит. Ну не кайф ли. Кайф. Потом правда приходится эту идею реализовавыть, что в общем-то тоже кайф. А иногда в процессе реализации осознаётся, что идея не рабочая, и нужно ещё поковырять в носу, что снова кайф. Хоспаде, да какой этап разработки не возьми — всё кайф.
Игра, для которой это всё делалось в итоге переехала на юнити, и эти декали канули в хер. Никаких эмоций у меня по этому поводу не возникало, я свой балдёж высосал из разработки до дна.