Летом накануне пандемии ударила как‑то раз мне в голову блажь.

Почему бы не взять движок типа Wolf3D/ROTT и не доработать его до уровня, способного тянуть Minecraft, максимально сохранив при этом производительность? А в жертву при этом можно принести все «красивости», сведя задачу к максимально узкому случаю. Пусть герой, в стиле ретро, смотрит всегда строго перпендикулярно одной из координатных осей (как правило, это вертикальная ось, то есть взгляд направлен строго горизонтально), угол зрения по вертикали пусть составляет 45 градусов (это важно, но об этом ниже), а всё остальное решаем лютыми костылями — вертикальный прицел делаем просто смещением крестика прицела на экране вверх‑вниз, а возможность посмотреть себе строго под ноги или, наоборот, в зенит — не менее элементарным переключением осей. За счёт такого «удушения» возможностей движка — оптимизируем всё под набор допустимых случаев, добиваемся максимальных FPS при максимальной дистанции рендера и гордимся собой. В плане железа, естественно, речь идёт не только и не столько о скудных гигафлопсах, но и об ограничении используемых технологий. «Весь этот тюнинг в зоопарке на фиг не нужен», то есть, например, «вычислительные шейдеры» мы использовать не можем — карта, поддерживающая такие технологии, всё может и грубой силой вытянуть. А слабо, допустим, на встроенке какого‑нибудь Lenovo X201i, или чего‑то из того же поколения? Ээээ, то‑то же.

Прикидочный алгорим, для CPU, элементарен до детскости. Там всё просто. Берём обычную сетку типа Wolf3D, просто добавляем третью координату. У нас есть набор лучей, экранная плоскость и четыре параметра каждого луча: dx, dy, dzu и dzd. То есть шаг по x, y (классические, в горизонтальной плоскости) и два шага по вертикали — вверх и вниз (up and down, если кто не понял индексы). Самое интересное, что мы можем смело шагать лучом только по x и y, игнорируя возможные пересечения по z: поскольку модуль угла не более 45 градусов, пропустить блок мы таким образом не сможем. Так что смело используем алгоритм старого доброго «Брезентыча» (ну, не совсем его, но очень‑очень близкий), сводя задачу практически к «Вольфенштайну».

Как легко видеть, столбец мы проверяем дважды: на входе в блок и на выходе из него. Фактически, поскольку шаг мы сделали до стенки, нужно только проверить каждый раз столбец, из которого мы выходим, и столбец, в который мы входим. Никаких лишних шагов по координатам делать не нужно. Если столбец, округлённый (разумеется, с учётом направления луча) в меньшую сторону (то есть столбец, который каст покидает) имеет на протяжении от zd до zu блоки, значит, произошла коллизия луча с полом или с потолком. Если коллизии у столбца, x y которого округлены в большую сторону (столбец, в который каст входит) — значит, впилились в стенку. Осталось вызвать тот или иной вариант скалера и продолжить каст, если по итогам рендера луч не схлопнулся в zd=zu (оно же dzd=dzu). На 1г сверху показана ситуация, когда блок найден на округлении от границы в плюс (стенка), а снизу — от границы в минус (пол, потому что dzd был отрицательный). После отрисовки соответствующих пикселов значения текущего положения по z (верхнее zu и нижнее zd) меняются вместе с дельтами (dzu и dzd), а вот x и y в этом не нуждаются — как сам шаг продолжается своим чередом, так и дельты тоже остаются постоянными. На 1в, правда, показана ситуация, где колонна занимала всё поле зрения по вертикали и каст на этом прекратился (zd=zu). И да, после стенки на уровне глаз dzu и dzd будут иметь одинаковый знак (просматривается только пространство над или под стенкой) — но это мало на что влияет.

Ну, и два случая требуют особенных костылей: это мосты (пространство над пространством, между ними — перегородка) и пресловутый взгляд вверх или вниз. С первым случаем надо быть особо внимательными, потому что у нас не первый Doom, у нас должна быть полная трёхмерность на 2.5D движке, поэтому задачка получается, скажем так, занимательная. Компромиссное решение, которое я счёл допустимым — рекурсивный вызов рейкаста с ограничением глубины рекурсии. Если есть риск положить движок — лепим артефакты, рандомно жертвуя тем или другим лучом. Но у рекурсии есть тот недостаток, что таки придётся повторно проходить «по Брезентычу» луч, который уже прошли, с теми же dx и dy, но с другими dzu и dzd! Что ж, сделаем себе пометку на полях и двинемся дальше. А дальше у нас — взгляд прямо под ноги, который потребует пост‑обработки, потому что рендер у нас квадратно‑гнездовой. Ему потребуется пост‑обработка с поворотом кадра, потому что взгляд под ноги не означает невозможности вертеться вокруг своей оси. Что ж, на сдачу появилась возможность наклонять голову набок, как в «Дюке».

Ну, и последнее, о чём надо подумать заранее — это чанки и LOD. В принципе, оно не должно сильно отличаться для CPU и GPU, но оговорить его всё равно надо: мы не хотим получить одновременно муар и просадку производительности. Поэтому, по мере прохождения лучом ключевых значений длины, мы делаем следующие вещи:

1. Вырубаем скалеры. Если куб по размеру стал в пару‑тройку пикселов — он будет лучше смотреться в однотонной заливке. Это потребует хранить заранее вычисленные значения среднего цвета и обновлять их по мере обновления блоков.

2. Укрупняем столбцы. Начиная с какого‑то момента, можно перепрыгивать сразу на несколько столбцов — всё равно они вместе тянут на один‑два пиксела. То же касается и высоты шага, разумеется — кубы должны оставаться кубами, не только ради производительности, но и ради сохранения «правила 45 градусов». Так что добавляем заранее вычисленные «октальники» на какую‑то разумную глубину и тоже вовремя обновляем (труд невелик, средний цвет текстуры есть заранее, сложили несколько чисел и всё).

3. Прощаемся с загруженной областью! Добро пожаловать в выгруженные чанки, лежащие на жёстком диске. Сюда можно заглядывать пореже, допустим, рисуя понемногу скайбокс и крутя уже его. Для этого мы должны подгружать какую‑то микроскопическую часть чанка, описывающую его «вид издалека». Ну, или вовсе их загрузить и не трогать диск — они же микроскопические, в этом случае можно и без скайбокса. Или ближние чанки выгружать не до конца, оставив в памяти «вид издалека», а дальние — рендерить прямо с харда в скайбокс, всё равно скайбокс на таких дистанциях сохраняет актуальность несколько минут. Или настройками (хардовый режим и SSDшный режим).

Тут, однако, придётся подумать о прозрачности. Она тут вообще не очень приятная штука — требует многократно вызывать скалер по одному и тому же месту, суммируя результаты, да ещё и с переменным коэффициентом — рендерим‑то мы от камеры наружу, а простое суммирование по альфе, наоборот, должно идти от первой непрозрачной текстуры сквозь все прозрачные, в направлении камеры! Видимо, придётся делать только один уровень прозрачности, или с производительностью возникнут проблемы. Но прозрачности не избежать — в любом уважающем себя движке должны быть стёкла и вода, а начиная со второго пункта LOD, банальное наличие рядом занятых и свободных кубов уже потребует её само по себе, иначе мы столкнёмся с тем, что все сетки, решётки и колоннады станут на такой дистанции полностью непрозрачными. Самая же жесть возникает на пункте 3, потому что прозрачность чанка зависит от того, под каким углом мы на него смотрим — там уже нельзя пренебречь формой содержащейся в нём архитектуры, как мы делали в «октальниках». Усреднение 2–8 кубов и 16+ — переход количественных проблем в качественные!

Что ж. Видимо, выгружая чанк, придётся по‑быстрому пробивать его несколькими рендерами и хранить какое‑то простое формульное описание зависимости RGBA‑цвета (три канала и прозрачность) от точки на чанке и значений dx, dy, dz. По крайней мере, если чанк был сильно изменён, пока был загружен. Радует только то, что таким образом можно одним махом описать очень крупные куски пейзажа! Тут и простенький полином можно приладить...

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

Начнём с того, что из одного шейдера, особенно на целевых (старых) ускорителях, не так уж и много информации можно вытащить. Во всяком случае, весь экранный столбец вряд ли получится! Значит, не избежать нам множественных «брезентычей» по каждому из лучей. В плюсе — реже встречается рекурсия, и её можно будет заменить на небольшой список пар dzu/dzd, что тоже хорошо (рекурсия и шейдеры — вещи трудносовместимые, хотя при очень больной фантазии, наверное, и такое возможно). Второе — шейдеры, особенно на целевых ускорителях, страсть как не любят ветвлений! А их тут у нас ой как много. Но, с другой стороны, в любой ближний куб втыкается сразу куча лучей, следовательно, столь любимая всеми SIMD‑системами похожесть данных у нас таки есть. Осталось только переписать её так, чтобы шейдеры могли дружно достигать одной и той же точки следования (по наихудшему случаю) и не сходили с ума, путаясь в дереве ветвлений. Для этого достаточно в уме заменить мышление в терминах «если» на мышление в терминах «когда», и всё сразу станет ясно и понятно :)

Если записать то же самое псевдокодом, получится примерно следующее (передаю лучи поноса «умному» редактору, который буквально запрещает мне написать то, что я хочу, и перекорявливает всё по своему разумению):

for (0, максимальная дистанция луча)
{
while (ничего не нашли в колонке)
{
? Шаг до границ блоков Брезенхемом (ну, почти им)
}

?
for (0, сколько нашли блоков в покинутом)
{
?Рисовать полы-потолки
}
for (0, сколько нашли блоков в новом)
{
?Рисовать стены
}


if (заполнили все пикселы нашего участка столбца) break;
}

В норме, конечно, надо ещё раз перейти от «если» к «когда» и сделать общий цикл for, у которого в какой‑то момент меняется величина заданного векторно шага, что позволяет одному шейдеру ещё дорисовывать пол или потолок, а соседнему — уже переходить к стене, не дожидаясь, когда первый шейдер завершит первый for. Думаю, это довольно тривиально.
Есть, правда, ещё и та проблема, что по вертикали (экранной) условия работы шейдеров сильно отличаются — это только по горизонтали разница между лучами в один пиксел и они почти наверняка попадут в какой‑то блок на примерно похожих дистанциях. По вертикали разница равна тому числу пикселов, которые мы сумеем со всеми ухищрениями запихнуть в один шейдер! То есть верхние улетают в небо на километры, нижние — втыкаются в землю. Ну что ж, сделаем одномерную псевдотекстуру (раз всё равно без псевдотекстуры нам не обойтись, надо ведь как‑то превратить один выход одного шейдера в кучу реальных пикселов столбца) и в неё сложим наши отрезки построчно. Ну, или ещё как‑то перегруппируем, чтобы все соседние выходные пикселы псевдотекстуры, охваченные общим SIMD смежных шейдеров, были в одинаковых условиях.
Ну и, наконец, проверять вот это вот «(ничего не нашли в колонке)» лучше с того конца колонки, в котором что‑то нашли в прошлый раз. Если уткнулся zu — проверяем от zu до zd с отрицательным шагом, если zd — от zd до zu с положительным. Большие шансы сразу же наткнуться на блок и без лишних раздумий перейти к подсчёту. Или... вовсе совместить все три операции — шаг по dx, dy, dzu и dzd, рисование стен и рисование потолков/полов! Просто инициализируем нулём (прозрачным цветом) все N пикселов, которые сумели впихнуть в выхлоп одного шейдера (вероятно, это будет очень зависящая от видеокарты величина!), и на каждом шаге накладываем на них те цвета, которые нашлись в колонке блоков, пока они все не перестанут быть прозрачными. В этот момент алгоритм начинает напоминать самое лобовое решение — рэйкаст на шейдерах, но вот только у нас одновременно шагает целая куча лучей, описанных пресловутыми d‑чего‑то‑там, поэтому скорость примерно в N раз больше — ценой всё той же Doom‑образной вертикальности стен, с которой мы начали в самом‑самом начале. Зато с проблемой рекурсии мы покончили радикально!

Всё стало настолько просто, что даже уже сложно. Смотрите: шейдер отвечает за N пикселов, получает их дельты и начинает шагать. Верх и низ знаем — легко можем посмотреть, есть ли что в колонке. Если колонка стала слишком длинная — сначала проверяем «октальники», которые вдобавок вообще однобитные, не суть (выше уже это всё разбирали). Важно, что мы потыкали всеми N пикселами, не заморачиваясь расчётом N индивидуальных лучей — точно как и в первичном алгоритме. Просто перебрали их от 0 до N, линейно. Что происходит, если... то есть когда мы найдём ненулевую колонку? Для каждого пиксела устанавливается цвет по простой формуле приоритетов, то есть без ветвлений. Если цвет уже установлен — он и остаётся (хе‑хе, прозрачность в эту логику добавить — раз плюнуть...) Если не установлен, то берётся цвет по логике «покидаемого блока». Если он тоже прозрачный — по логике «нового встреченного блока». Если и он прозрачный — прозрачным ему и быть, это был разрыв во встреченной колонке. А дальше мы, чтобы не перебирать до посинения уже установленные верхние и нижние пикселы, «подрезаем» границы перебора, от 0..N они становятся N1..N2 (естественно, дельты мы тоже меняем).

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

Статья публикуется по просьбе коллег с gamedev.ru, интересовавшихся алгоритмами быстрого определения видимости блоков. Может, хотя бы для этого оно сгодится?

P.S.: я в курсе, что «пресловутый» — это не просто «навязнувший в зубах», а «печально известный и навязнувший в зубах». Это было немного горькой иронии, ибо толку‑то в итоге с пресловутых дельт...

P.S.S.: 3D‑мипмапы на целевом видеоядре не работают. Генерируйте «октальники» руками, тем более, что там желательно прийти к одному биту.