Программный рендеринг был широко распространён в играх на ПК до повсеместного распространения т. н. 3d-ускорителей (видеокарт). Каждая игра содержала свой собственный код рендеринга, каждая игра имела свои уникальные особенности в нём. Но с распространением видеокарт программный рендеринг в играх умер.

Я раньше задавался вопросом, а что было бы, если бы программный рендеринг был бы до сих пор распространён? В конечном итоге, я решил реализовать свой программный рендеринг, нацеленный на современные процессоры, чтобы это узнать.

Экскурс в историю

С самого начала IBM PC не имел столь продвинутых средств вывода графики, какими обладали специализированные игровые консоли. Максимум, что было — это видеокарты, которые умели выводить 4/16/256-цветную картинку, да и только. Поэтому всё рисование на этой платформе осуществлялось силами центрального процессора.

Поначалу игры были двухмерными, весь вывод графики сводился к заливке фона цветом/паттерном/изображением и рисованием спрайтов. Но с появлением всё более быстрых процессоров (286, 386) появлялись игры с некоторой степенью трёхмерности — Catacomb 3D, Wolfenstein 3D, чуть позже Doom и Duke Nukem. В этих играх всё рисование в конечном итоге сводилось к заливке строк пикселей для полов/потолков и столбцов пикселей для стен а также спрайтов для врагов и предметов.

Ближе к середине 90-х годов появились уже почти что полноценные трёхмерные игры — с более свободной геометрией уровня и трёхмерными моделями для отображения объектов. К примеру Quake, Descent, Tomb Raider, Terminator: Future Shock, чуть позже Thief: the Dark Project и Chasm: the Rift.

Но, несмотря на трёхмерность, в некоторых аспектах эти игры были ещё весьма примитивны. Работали они в весьма низком разрешении — 320x200, 640x480 — максимум. К тому же цвета были 8-битными. Освещение реализовывалось путём табличных преобразований из одного цвета в другой для его осветления/затемнения.

Первым звоночком конца эпохи программного рендеринга стал выход GLQuake — версии Quake, предназначенной для использования с 3D-ускорителями (3dfx Voodoo и прочими). После него другие игры тоже начали включать в себя поддержку 3D-ускорителей.

Тем не менее игры всё ещё включали в себя программный рендеринг, и даже более того, он был усовершенствован. Появилось цветное освещение и 16 и даже 32-битный рендеринг. Пример таких игр — Unreal, Half-Life, SiN. В Quake II программный рендеринг не сильно ушёл от Quake, но OpenGL-рендеринг включал в себя цветное освещение и 16-битный цвет.

Закат эпохи программного рендеринга пришёлся примерно на конец 1999-го года, когда вышла игра Quake III Arena с поддержкой только лишь OpenGL. Вышедшая почти одновременно с ним игра Unreal Tournament (и чуть позже Unreal Gold) ещё включала в себя программный рендеринг. Он сейчас является вершиной развития классического программного рендеринга в ПК играх. Игры, вышедшие после 1999-го года, в основном уже имели только аппаратный рендеринг, а в некоторых из них программный рендеринг даже был удалён в процессе разработки, как например в Daikatana или Soldier of Fortune, базирующихся на движке Quake II.

Последним отголоском эпохи программного рендеринга можно назвать Unreal Tournament 2004. В нём присутствует программный рендеринг, но он отключён по умолчанию, и показывает он весьма посредственную производительность, ибо контент игры создавался в расчёте на аппаратный рендеринг.

Предыдущий опыт

Я уже имел достаточный опыт написания программного рендеринга. Я написал программный рендеринг для Quake II с поддержкой цветного освещения. Для PanzerChasm я тоже написал программный рендеринг, пусть и не столь продвинутый.

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

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

Основная структура данных

Главная проблема программного рендеринга заключается в минимизации процессорного времени, требующегося для построения кадра, ибо мощность процессора сильно ограничена в сравнении с видеокартой. На видеокарту иногда можно отправить на отрисовку всю сцену (что, конечно, делать не стоит) и видеокарта даже сможет её как-то показать, если сложность геометрии и шейдеров несколько отстаёт от текущего уровня AAA игр.

С программным рендерингом ситуация иная. Растеризация и подготовка геометрии занимают весьма много времени. Посему стоит минимизировать количество отображаемой для данного кадра геометрии — не рисовать то, что не видно (находится за спиной, за стенами), использовать LODы.

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

Для SquareWheel я выбрал структуру данных — дерево двоичного разбиения пространства (BSP-дерево). Данная структура данных использовалась (и до сих пор используется) много где — в Doom, Quake, Thief, Unreal и многих других играх. Конкретно я выбрал листовое BSP-дерево — это когда узлы дерева не содержат полигонов, а полигоны содержатся только в листьях. Лист образуется набором обращённых друг к другу полигонов. Объём листа представляет собой выпуклый многогранник, полученный из плоскостей рассечения BSP-дерева и полигонов этого листа.

Главное предназначение данной структуры данных — упорядочивание полигонов от дальних к ближним (или наоборот). Вспомогательное предназначение — пространственная организация динамических объектов. Но главную проблему программного рендеринга сама по себе эта структура не решает, просто BSP-дерево не даст уменьшить количество отображаемой геометрии.

Дополнительной структурой данных поверх BSP-дерева является граф связности листьев BSP-дерева друг с другом. В этом графе вершинами являются листья BSP-дерева а рёбрами — порталы. Портал — это выпуклый полигон (не отображаемый), который лежит на плоскости, общей для двух сообщающихся листьев BSP-дерева. Строятся порталы после построения BSP-дерева на плоскостях его узлов. Там, где между листьями BSP-дерева лежат полигоны, порталы не создаются.

Подобный граф листьев и порталов позволяет вычислить очень важную информацию — видимость одних листьев BSP-дерева из других. Имея такую информацию можно при рисовании кадра определить текущий лист BSP-дерева, в котором расположена камера и нарисовать только ту геометрию, что расположена в листьях, видимых из текущего.

Можно строить информацию о видимости заранее и сохранять её в матрицу видимости. Так делал, например, Quake. Утилита VIS строила порталы и по ним итоговую матрицу видимости. Но я выбрал иной способ определения видимости. Позаимствовал я его из игры Thief: the Dark Project. Этот способ описан в данной статье (перевод на Хабре).

Вкратце, суть метода следующая: при построении кадра на экран проецируются порталы текущего листа BSP-дерева. Листья, видимые через эти порталы, помечаются как видимые. Далее проецируются уже порталы этих листьев и эта проекция пересекается с проекциями предыдущих порталов. Если пересечение пустое — следующие листья уже не видны, иначе — поиск продолжается рекурсивно.

Для ускорения поиска видимых листьев вместо честного нахождения пересечения полигонов порталов используется аппроксимация — нахождение пересечений ориентированных по осям восьмиугольников в пространстве экрана. Это как ориентированный по осям прямоугольник, но с дополнительными гранями, перпендикулярными осям X + Y и X — Y. Использование восьмиугольника в противовес прямоугольнику позволяет повысить точность нахождения пересечения порталов, что в конечном итоге сводится к меньшему количеству ложно-положительных срабатываний алгоритма поиска видимых листьев.

Достоинство данного метода над предрасчётом как в Quake состоит в том, что видимость более точная, а значит, в данном кадре рисуется в целом меньше геометрии. Ещё достоинство — в процессе определения видимости строится ограничивающий восьмиугольник, который можно использовать для отсечения полигонов листа BSP-дерева, что снижает площадь растеризации.

Недостаток данного метода состоит в том, что он не очень быстрый, в некоторых случаях. Автор оригинальной статьи тоже на это жалуется. В случае очень детальной геометрии или открытых пространств поиск занимает существенно много времени (порядка миллисекунды на современных CPU). Но в не сильно детальных сценах и помещениях это не проблема.

Растеризация

Имея листовое BSP-дерево и механизм определения видимости можно уже что-то нарисовать.

Алгоритм рисования сцены следующий: сначала определяется текущий лист BSP-дерева, в котором находится камера. Осуществляется поиск видимых листьев BSP-дерева, включая построение ограничивающего восьмиугольника в экранном пространстве для каждого листа. Далее осуществляется рекурсивный обход BSP-дерева от дальних листьев к ближним с рисованием геометрии в них. Геометрия в невидимых листьях не рисуется, геометрия в видимых листьях обрезается по имеющемуся восьмиугольнику.

Растеризация геометрии осуществляется как есть — без какого-либо теста глубины или чего-то подобного. Это не нужно, т. к. BSP-дерево даёт правильный порядок отрисовки. При этом присутствует некоторая перерисовка (пиксель может быть закрашен более одного раза), но в целом она небольшая, ибо обрезка полигонов по восьмиугольнику уменьшает перерисовку. К тому же подход с рисованием от дальних поверхностей к ближним автоматически ведёт к правильному порядку отрисовки поверхностей со смешиванием и с альфа-тестом.

В Quake, кстати, из-за грубо-просчитанной видимости (для целого листа, а не для конкретной позиции камеры в нём), перерисовка в целом заметно больше, из-за чего пришлось использовать span-buffer для её устранения. Думаю, из-за этого в Quake не было ни альфа-теста, ни какого либо смешивания. У меня же нужды в span-buffer-е нету, ибо излишняя перерисовка не является столь серьёзной проблемой.

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

Для интересующихся собственно растеризацией советую прочитать эту статью.

Результат растеризации по вышеописанному алгоритму:

А вот то же место, но в случае, если обратить порядок обхода BSP-дерева (рисовать полигоны от ближних к дальним):

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

Другой пример:

Здесь видно, что перерисовка в целом больше. Пространство за колоннами всё равно нарисовалось. Ну и за окнами, но там потому, что окна на самом деле сделаны из полупрозрачного материала.

Освещение

Золотой стандарт освещения в программном рендеринге — это просчитанные заранее светокарты. Ранее использовалось ещё посекторное освещение (Doom, Duke Nukem) или повершинное (Descent), но их качество было не очень. Динамическое попиксельное освещение не применялось, ибо его подсчёт был слишком затратным. Но использовалось динамическое изменение светокарт.

В SquareWheel я также реализовал освещение светокартами. Для их построения была создана отдельная утилита. Метод подсчёта — radiosity, cхожий с тем, что применялся в других играх. Важное отличие заключается в том, что светокарты в SquareWheel хранятся в расширенном диапазоне яркостей (16 бит), в противоположность (например) Quake, где на тексель светокарты отвадилось всего 8 бит и поэтому очень яркое освещение (с пересветом) не было возможно.

Поверхности

Вопрос — а как теперь нарисовать сцену с текстурами и светокартами? Наивное решение — при растеризации делать выборку из светокарты и из текстуры, модулировать текстуру значением светокарты и записывать получившееся значение в экранный буфер. И многие игры с аппаратным рендерингом так и делают, начиная с того же GLQuake.

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

Другой подход, который практиковался в Quake, Thief и много где ещё — метод поверхностей. Суть его следующая: для каждого полигона строится уникальная текстура, называемая поверхность, которая представляет собой результат применения светокарты к исходной текстуре. В растеризатор попадает уже эта поверхность. При этом поверхность может строиться не только в исходном разрешении текстуры, но и в пониженном (с дальними MIP-уровнями) для полигонов, расположенных вдалеке.

Статья о рендеринге в Quake II, излагающая суть подхода с поверхностями.

Преимущество метода в том, что за счёт разделения растеризации и освещения оба процесса могут быть существенно оптимизированы. Кроме того, сложность освещения в целом снижается, ибо как правило текселей поверхностей в кадре сильно меньше, чем пикселей экранного буфера — из-за того, что текстуры имеют конечное и весьма небольшое разрешение и потому, что на поверхностях, наклонённых под сильным углом к камере, включается более дальний MIP-уровень. Последнее — поверхности можно кешировать между кадрами. Правда кеширование в SquareWheel не используется, позже будет изложено — почему.

Пример рисования освещённых поверхностей:

Продвинутые поверхности

Просто затекстурированные и освещённые полигоны — это всё пока что уровень Quake или Unreal. В более продвинутом программном рендеринге должно быть что-то ещё.

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

Пример карты нормалей:

Для вычисления освещения с учётом карты нормалей нужно иметь направление источника (источников) освещения. Но где же это направление взять, если используются только светокарты? Решение — сохранять в светокартах информацию о направлении источника света. В том-же Half-Life 2 это делалось путём разложения входящего света по ортогональному базису из трёх векторов и сохранения отдельной интенсивности света для каждого из них. Способ рабочий, но обладает некоторыми недостатками, главный из которых, по-моему, это неточное сохранение преимущественного направления света, если таковое имеется. Поэтому я выбрал иной способ хранения направления света в светокартах. Входящий свет некоторой эвристикой разбивается на фоновый и направленный компоненты. Для обоих компонентов хранится цвет и интенсивность, а для направленной компоненты — ещё и вектор направления и разброс (в диапазоне [0; 1]).

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

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

Результат использования карт нормалей (без них/с ними):

Блики

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

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

1 / (roughness ( π sqrt(8) / 2 ((cos(angle) — 1) / roughness) ^ 2 + 2 π / sqrt(7)))

Где roughness — шероховатость поверхности с диапазоном (0; 1]. Эта функция вычислительно достаточно простая, даёт красиво-выглядящий результат, а также имеет почти что константный интеграл для всех углов и широкого диапазона шероховатости.

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

Пример карты шероховатости:

Вычисление бликового освещения вычислително весьма затратно. Для него приходится вычислять мировую позицию текселя поверхности и переводить вектор взгляда в пространство текстуры. Из-за этого применять бликовое освещение на всех поверхностях не целесообразно. Но местами оно может быть использовано.

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

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

Вот так выглядят блики на диэлектрической поверхности:

А вот так на металлической:

HDR рендеринг

Освещение в Quake и многих последующих играх, вплоть даже до Half-Life 2, было в низком диапазоне яркостей. Освещения на улице в солнечный день имело такую же интенсивность, как и искусственное освещение в помещениях. Это физически весьма некорректно, но оно было таковым из-за необходимости хранить данные освещения как можно более компактным образом и выводить итоговую сцену на экран, представляющий собою устройство вывода с достаточно низким диапазоном яркостей.

Прорыв в этом направлении сделала игра (техническая демонстрация) Half-Life 2: Lost Coast. Подробности. В ней исходное освещение имело гораздо более высокий диапазон яркостей. А чтобы его отобразить на экране, игра производила ужимание картинки в диапазон яркости монитора (тонирование), при этом автоматически вычисляя экспозицию на основе интегральной яркости кадра. Со времён этой демки большинство игр осуществляют рисование в расширенном диапазоне схожим образом.

В SquareWheel я решил реализовать нечто подобное. Я реализовал построение поверхностей в расширенном диапазоне яркостей — по 16 бит на цветовой канал, вместо обычных 8 бит, в итоге 64 бита на тексель (с учётом альфы). Далее эти поверхности растеризуются в 64-битный промежуточный экранный буфер того же формата. После рисования всей сцены этот буфер тонируется в 8 бит на канал для последующего вывода картинки на экран. Для тонирования для каждого канала используется функция тонирования: intensity / (intensity + 1 / exposure). Данная функция вычислительно достаточно проста и даёт сносный результат. Экспозиция вычисляется на основе суммарной яркости кадра, сглаживается по времени и ограничивается некоторым разумным диапазоном.

Кроме простого тонирования я также реализовал эффект bloom. Реализован он следующим образом: исходный 64-битный буфер уменьшается в 4-8 раз по сторонам (16 — 64 раз площади), в два прохода (по горизонтали и по вертикали) к нему применяется гауссово размытие, после чего получившееся размытое изображение складывается перед тонированием с исходным изображением. Вычисление в уменьшенном разрешении необходимо, т. к. размытие — процесс весьма вычислительно-затратный, в котором нужно на каждый пиксель делать по нескольку чтений соседних пикселей.

Внимательный читатель может спросить — а почему бы не производить тонирование сразу — при подготовке поверхностей и тем самым сэкономить память под поверхности и под промежуточный экранный буфер? Проблема заключается в том, что в таком подходе не будет корректно работать смешивание на полупрозрачных поверхностях (альфа-смешивание), а также совсем не будет работать эффект bloom.

Результат использования HDR рендеринга (без него/с ним):

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

Динамическая геометрия

Рисование статической геометрии уровня — это хорошо, но только этого не достаточно. Нужно ещё отображать что-то динамическое — как минимум двери, лифты, кнопки и т. д. В SquareWheel эти объекты представляют собою наборы таких же полигонов, что и у статичной геометрии, но эти полигоны не сохраняются в BSP-дереве.

Рисуются эти объекты следующим образом: для каждого объекта находится набор листьев BSP-дерева, в которых он находится. После рисования статичных полигонов листа BSP-дерева осуществляется рисование полигонов объектов, расположенных в нём. При этом полигоны обрезаются по границам текущего листа BSP-дерева, что необходимо для правильного упорядочивания.

Между собою полигоны динамического объекта сортируются тоже некоторым вариантом BSP-дерева, которое строится для каждого объекта. Кроме того, объекты внутри каждого BSP-листа сортируются относительно друг друга, чтобы обеспечить правильный порядок отрисовки.

Упомянутое выше нахождение листьев BSP-дерева, в которых находится объект, выполняется с помощью того же BSP-дерева. Ограничивающий параллелепипед объекта рекурсивно тестируется относительно плоскостей разбиения дерева. Если все вершины ограничивающего параллелепипеда лежат по одну сторону плоскости разбиения, поиск листьев уходит только в одну сторону, иначе — в обе. В конечном итоге для каждого объекта находится список листов BSP-дерева, в которых он находится, а для каждого листа — список объектов в нём. Если не один из листьев BSP-дерева, в котором находится объект, не виден в данном кадре, то для этого объекта можно пропустить различные приготовления и даже не пытаться его отображать. Данный подход также используется для иных типов динамических объектов.

К сожалению, отображение динамических объектов обладает рядом недостатков. Светокарты на них статичны, из-за чего освещение вне исходной позиции будет смотреться не очень хорошо. Кроме того динамические объекты никак не ограничивают видимость, из-за чего сцена за закрытой дверью будет всё так же рисоваться. Но, проблемы эти не фатальны. Первую проблему можно минимизировать умелым дизайном уровней — делая освещение вдоль движения дверей/лифтов более-менее однородным. Вторую проблему, теоретически, можно решить, реализовав некоторый механизм блокировки порталов динамическими объектами.

Пример динамической геометрии:

Кстати, она ещё и теней не отбрасывает. Что (во-многом) логично.

Модели из треугольников

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

Модели из треугольников также размещаются в BSP-дереве, как и модели для дверей/лифтов и также рисуются с обрезкой по границам текущего листа и с сортировкой относительно друг-друга и относительно динамических объектов других типов.

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

Подход с сортировкой треугольников я считаю более подходящим для программного рендеринга. Он даёт возможность совсем отказаться от Z-buffer-а, заполнение которого и чтение которого рендеринг, мягко говоря, не ускоряют. Quake, например, использовал Z-buffer, который исходно заполнялся (но не читался) при рисовании геометрии уровня и заполнялся/читался при рисовании моделей. Для Quake это было особенно нелепо, ведь Z-buffer, служивший только для правильного рисования моделей, которые не занимали и 10% площади кадра, весил в два раза больше буфера цвета кадра (16 против 8 бит).

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

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

Вопрос — а как же вычисляется освещение моделей? Светокарты им явно не подойдут. Ответ следующий — световая сетка. Она применяется в играх ещё о времён Quake III Arena. Утилита построения светокарт также вычисляет пространственную сетку световых проб, с разрешением (по умолчанию) около двух метров. Это не очень точно и даёт некоторые артефакты в случаях тонких стен, но эту проблему можно обойти грамотным дизайном уровней. Каждый элемент световой сетки содержит куб освещения — интенсивность света со стороны шести направлений, кроме того содержится отдельно вектор и интенсивность преимущественного направления света.

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

Как выглядят модели из треугольников:

Обратите внимание, что модель, наполовину погружённая в воду, рисуется корректно — за счёт разрезки по листьям BPS дерева и упорядочивания. Также обратите внимание на освещение моделей в комнате с цветным освещением.

Поддерживаются также модели, привязанные к камере:

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

Спрайты

Для разнообразных эффектов также бывают полезны спрайты/биллборды. Без них было бы не очень хорошо, сравните полигональные взрывы из Quake II со спрайтовыми взрывами из Unreal. Сравнение будет не в пользу первого.

Рисование спрайтов схоже с моделями из треугольников — также происходит нахождение листьев BSP-дерева, также происходит упорядочивание, растеризация, так же используется световая сетка для освещения. Отличие — ориентация спрайта вычисляется на основе позиции камеры, свет для всего спрайта константный и не зависит от его направления (да и нету у него направления).

Декали

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

Исходно декаль представляет собою ориентированный параллелепипед с некоторой текстурой. Он так же, как и другие динамические объекты, размещается в BSP-дереве.

Рисвание декалей происходит довольно интересным способом. После рисования каждый полигон листа BSP-дерева (и дверей/лифтов), в котором расположена декаль, обрезается плоскостями параллелепипеда этой декали. Если получился непустой полигон — он рисуется с текстурой этой декали. Освещение декали берётся из светокарты полигона.

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

Сортировать декали каким-либо образом нужды нету, ибо они привязаны к полигонам, которые и так уже сортируются должным образом. Декали не применяются к моделям из треугольников, что (в целом) и не нужно.

Как выглядят декали:

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

Небо

Небо необходимо рисовать особым образом, ибо оно (практически) бесконечно-удалено от наблюдателя. Просто натянуть на полигоны текстуру с облаками не получится.

В Doom небо рисовалось просто как текстура в верху экрана. Ему это было простительно, ибо не было возможности посмотреть вверх. В Quake небо реализовали специальным эффектом — когда при растеризации полигонов неба происходил сложный (и весьма затратный) пересчёт текстурных координат для получения эффекта купола неба. Но по сути это было просто рисование плоской текстуры облаков без какого-либо разнообразия. По-настоящему красивое небо появилось только в Quake II и Half-Life, реализовано оно было как небесный куб — шесть квадратных текстур для представления всего окружения. Благодаря этому стало возможным отображать весьма красивое окружение (космические уровни в Quake II, Xen в Half-Life).

Я для SquareWheel тоже выбрал рисование неба через небесный куб.

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

Данный подход даёт хорошие результаты, но он не лишён недостатков. Главных из них — статичность неба. В том же Unreal небо было с движущимися облаками, а в Half-Life 2 был небесный куб с динамическими объектами (той-же Цитаделью). Но, думаю, по необходимости можно доработать этот подход — рисовать поверх куба слой облаков, модели и т. д.

Пример рисования неба:

Какой участок экрана фактически заливается небом:

Динамическое освещение

К этому моменту уже есть достаточно красивая картинка, но ей не хватает динамики. Добавить динамики может динамическое освещение.

В Doom оно было реализовано просто изменением текущего освещения сектора. В Quake оно было реализовано динамическим изменением светокарт. При этом оно было достаточно тупое — не учитывалось затенение (свет проходил сквозь стены) и даже угол падения (освещались стены с обратной стороны).

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

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

Чтобы не уронить кратно производительность при наличии динамических источников освещения, реализован ряд оптимизаций. Динамические источники света имеют конечный размер (что физически некорректно). Они размещаются в BSP-дереве, чтобы определить, какие источники света влияют на какие листья BSP-дерева и соответственно полигоны, расположенные в них. Кроме того, для каждого полигона отдельно проверяется влияние на него источников света в его листе BSP-дерева, чтобы дополнительно минимизировать стоимость подготовки поверхностей.

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

В целом, динамические источники освещения могут быть использованы для различных эффектов — светящихся снарядов (ракет, выстрелов BFG), дульных вспышек выстрелов, фонарика у игрока. Но не более того, на освещение всей сцены динамическими источниками света пока что не хватает производительности.

Пример динамического фонарика:

Точечные источники освещения небольшого радиуса (для наглядности в центре рисуется спрайт):

Один большой точечный источник освещения с тенями:

Он заметно роняет производительность.

Как это всё вообще стало возможно?

К этому моменту читатель может задаться вопросом — как всё ЭТО возможно в программном рендеринге? За чей счёт банкет? Почему Quake и ему подобные игры такое не могут? Ответ следующий: прогресс центральных процессоров со времён смерти программного рендеринга в ПК играх не стоял на месте.

Во-первых, банально увеличилась частота работы процессора, как минимум, в несколько раз со времён Unreal Tournament.

Во-вторых, процессоры стали заметно быстрее в пересчёте на единицу частоты — за счёт суперскалярности, внеочередного исполнения инструкций и т. д.

В-третьих, современные процессоры с точки зрения набора команд гораздо более продвинутые, чем ранее. В процессоре архитектуры amd64 банально больше регистров общего назначения, чем было в Pentium, под который разрабатывался Quake, что местами ускоряет код за счёт уменьшения операций с памятью. Кроме того в этом процессоре нативно реализованы 64-битные инструкции сложения/умножения/деления, которые 32-битные процессоры не умели, или умели, но через пары регистров.

В-четвёртых, появилось много продвинутых инструкций — для векторных вычислений и не только. Unreal использовал MMX инструкции, что давало возможность реализации цветного освещения, но не освещения в широком диапазоне. Сейчас же есть SSE инструкции для работы с векторами float и инструкции для быстрых вычислений обратного значения, обратного квадратного корня, комбинированного умножения и сложения. SquareWheel активно использует эти инструкции.

В-пятых, современные процессоры многоядерные. Использование всех доступных ядер вместо только одного позволяет местами кратно увеличить производительность.

SquareWheel использует многопоточность где только можно.

Поверхности подготавливаются в несколько потоков. Для этого используется что-то вроде parallel for. Это возможно, т. к. поверхности независимы друг от друга. Аналогично независимым образом подготавливаются модели из треугольников (анимация, освещение, проекция, сортировка).

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

Тонирование тоже осуществляется в несколько потоков — независимо для каждого участка экрана.

При этом многопоточность не даёт кратного прироста производительности, главным образом потому, что местами процесс построения кадра банально упирается в доступ к шине памяти. Ибо поверхности и буфер кадра уж очень много весят. Тем не менее, время построения кадра может уменьшаться от использования многопоточности, например, раза в 2-2.5 на четырёхъядерном процессоре.

Немного о технических моментах

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

Логическое разделение компонентов

Проект SquareWheel состоит из утилиты построения карт map_compiler, утилиты построения освещения lightmapper, собственно библиотеки движка и тестовой недоигры, её использующей.

map_compiler производит компиляцию карт, как это делалось в каком-нибудь Quake. На вход подаётся файл в формате .map, аналогичный таковому в Quake. На выходе выдаётся файл карты с построенным BSP-деревом, графом порталов и прочим, но без освещения. Формат исходников карт, совместимый с Quake, позволяет использовать любой его редактор карт, вроде TrenchBroom.

lightmapper производит вычисление освещения. Делает он это на процессоре, а значит, процесс этот небыстрый. Освещение с достаточным качеством вычисляется для относительно-небольшой карты где-то за час на четырёхядерном процессоре. В сравнении с подобными утилитами для Quake или Quake III Arena времени это занимает много потому, что разрешение светокарт в SquareWheel больше, а также потому, что вычисление направленных светокарт и световой сетки — процесс весьма вычислительно-затратный, чтобы качество было достаточным.

Оптимизации циклов

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

Например, есть функция подготовки поверхностей (упрощено):

pub fn build_surface(
    surface_size: [u32; 2],
    texture: &Texture,
    lightmap_size: [u32; 2],
    lightmap_data: &[LightmapElement],
    out_surface_data: &mut [Color32],
    dynamic_lights: &[&DynamicLightWithShadow])
    {
        for y in 0 .. surface_size[1]
        {
            for x in 0 .. surface_size[0]
            {
                // Как-то вычисляем свет на основе светокарты
                // ...
                // Вычисляем свет от динамических источников
                for dynamic_light in dynamic_lights
                {
                    // ...
                }
            }
        }
    }

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

fn build_surface_impl<const USE_DYNAMIC_LIGHTS: bool>(
    surface_size: [u32; 2],
    texture: &Texture,
    lightmap_size: [u32; 2],
    lightmap_data: &[LightmapElement],
    out_surface_data: &mut [Color32],
    dynamic_lights: &[&DynamicLightWithShadow])
{
    for y in 0 .. surface_size[1]
        {
            for x in 0 .. surface_size[0]
            {
                // Как-то вычисляем свет на основе светокарты
                // ...
                // Вычисляем свет от динамических источников

                if USE_DYNAMIC_LIGHTS
                {
                    for dynamic_light in dynamic_lights
                    {
                        // ...
                    }
                }
            }
        }
}

pub fn build_surface(
    surface_size: [u32; 2],
    texture: &Texture,
    lightmap_size: [u32; 2],
    lightmap_data: &[LightmapElement],
    out_surface_data: &mut [Color32],
    dynamic_lights: &[&DynamicLightWithShadow])
{
    if dynamic_lights.is_empty()
    {
        build_surface_impl<false>(surface_size, texture, lightmap_size, lightmap_data, out_surface_data, dynamic_lights);
    }
    else
    {
        build_surface_impl<true>(surface_size, texture, lightmap_size, lightmap_data, out_surface_data, dynamic_lights);
    }
}

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

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

Использование специфичных инструкций процессора

Я использую специальные инструкции процессора явно — через функции компилятора, вроде _mm_mul_ps, а также явно использую векторные регистры через типы вроде __m128. Это необходимо, т. к. компилятор не всегда может автоматически выполнить векторизацию. А для случаев, когда данные функции не поддерживаются (старые процессоры, альтернативные платформы), я завернул использование этих инструкций в типы-обёртки с альтернативной реализацией без специальных инструкций.

Также явно используются инструкции _mm_rsqrt_ss и _mm_rcp_ss для вычисления обратного квадратного корня и обратного значения соответственно. Они существенно быстрее вычисления 1 / sqrt(x) и 1 / x, но не вполне точны, хотя в большинстве случаев их точность достаточна. Из-за недостаточной точности компилятор их автоматически и не использует (для тех случаев, когда точность всё же важна).

Кроме того явно используется, где можно, библиотечная функция f32::mul_add. Компилятор её разворачивает в соответствующую инструкцию процессора (если таковая поддерживается). Явно её использовать необходимо, т. к. выражение a * b + c будет давать немного различающийся результат в сравнении с f32::mul_add(a, b, c), из-за чего, опять-же, компилятор не использует эту инструкцию автоматически. В некоторых компиляторах всё-же можно включить флаги, которые бы включали подобные оптимизации, но лучше этого не делать и использовать, где надо, особые функции вручную, чтобы не поломать подобными оптимизациями библиотечный и сторонний код, где это критично.

Детали использования многопоточности

Под каждую небольшую задачу создавать отдельный поток — весьма накладно. Поэтому в SquareWheel используется пул потоков, который создаётся на старте. Далее все задачи исполняются в этом пуле. При этом важно ещё соблюдать баланс между распараллеливанием и атомизацией вычислительных задач. Их должно быть как минимум по числу потоков, но сильно много. Например — выделять задачу на построение поверхности одного полигона — в целом нормально, ибо полигонов в кадре как правило всего несколько сотен, но вот делать parallel for по текселям — уже перебор.

Итоговая производительность

На четырёхядерном процессоре Intel® Core(TM) i5-7500 CPU @ 3.40GHz в разрешении 1920x1080 демка показывает в среднем около 75 кадров в секунду, с показателями более 100 в некоторых местах и просадками до 60 — 50 в особо-тяжёлых случаях.

Время кадра распределяется приблизительно следующим образом: 4.5 мс — подготовка поверхностей, 5 мс — растеризация, 3.6 мс — постпроцессинг, 1.2 мс — прочее. Эти показатели могут варьироваться от кадра к кадру — в зависимости от его содержимого. Ещё миллисекунду-две занимает отправка картинки на видеокарту для последующего показа, что опять же может зависеть от ОС, драйверов и прочего.

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

Выводы

Опыт SquareWheel показывает, что программный рендеринг В ПК играх сейчас можно реализовать куда продвинутее, чем он был к моменту своей смерти в начале XXI века. Однако, он всё же значительно уступает по качеству выдаваемой картинки рендерингу на видеокарте. SquareWheel в 2022-м году показывает что-то близкое по уровню графики к игре Half-Life 2, вышедшей в 2004-м году. Кроме того, для вывода картинки в FullHD нужен достаточно мощный процессор. На ноутбуках программный рендеринг подобного качества вообще слабо применим, ибо ноутбучные процессоры быстро перегреваются и снижают частоту, что ведёт к сильному падению производительности.

Возможно ли практическое использование SquareWheel или чего-то подобного? Ответ — возможно, но только в редких случаях.

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

Но если цель состоит в том, чтобы создать игру в старомодном стиле, или где программный рендеринг как таковой является частью стиля игры, то программный рендеринг вполне подойдёт. Примеры относительно-современных игр, с нарочито-старомодной графикой это Ion Fury (есть программный рендеринг), DUSK (стилизация под программный рендеринг), STRAFE (стилизация под программный рендеринг), HROT (есть программный рендеринг).

Что касается конкретно SquareWheel, то этот движок (или нечто подобное) подошёл бы к играм в закрытых пространствах, вроде Quake или Doom 3. Открытые пространства ему отображать весьма сложно из-за того, что на них портальный алгоритм определения видимости сильно бы тормозил. Также не даёт возможности использовать открытые пространства световая сетка, размер которой был бы весьма большой. Возможно, в будущем, SquareWheel можно как-то доработать для отображения чего-то напоминающего открытые пространства (как в том-же Half-Life 2), но пока у меня даже нету идей, как это можно сделать.

Возможные улучшения

У меня есть ещё ряд идей, что можно было бы реализовать:

• Статичные модели из треугольников — для декораций. Заранее разрезанные по BPS-дереву, с предвычисленным повершинным освещением и с отбрасыванием теней.
• Более сложное небо (с облаками и сложными объектами).
• Текстуры с собственным свечением — экраны и т. д.
• Механизм блокировки порталов теми же дверьми — для устранения рисования геометрии за закрытыми дверьми.
• Более продвинутое рисование моделей из треугольников — с минимизацией разрезания по листьям BSP-дерева, когда это возможно.

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

Ссылки

Видео с демонстрацией:

Исходный код

Демонстрационная сборка