Программный рендер в стиле игры Doom

Расскажу о небольшом домашнем проекте по написанию программного рендера. Всё началось со случайного видео на Youtube с записью геймплея игры Doom (93 года). Появилась идея сделать похожий рендер на С++ без использования библиотек. В статье описаны шаги его разработки. В конце есть ссылка на видео с демонстрацией работы рендера.

Вместо вступления. Современную игровую 3d-графику рисуют специализированные чипы, но в начале 90-х годов этим занимался движок игры. То есть, в коде движка был цикл отрисовки отдельных пикселов игрового мира. Учитывая скромную скорость процессоров того времени, авторам Doom’а пришлось постараться, чтобы их игра рисовала игровой мир в реальном времени. Для этой цели они подобрали оптимальные структуры данных и алгоритмы визуализации. Попробуем и мы сделать нечто подобное. Итак, поехали.

Формат игрового уровня

Сначала придумаем в каком виде хранить игровой уровень - его геометрию. Если посмотреть видео с записью геймплея Doom’а, можно заметить особенность: пол и потолок всегда горизонтальные, а стены всегда вертикальные

Попробуем начертить минимальный фрагмент уровня (одну прямоугольную комнату) по схожему принципу и посмотрим какие данные для этого нужны. Схему будем чертить в проекции сверху, как рисуют план квартиры. Выберем систему координат. Ось X будет идти вправо, ось Z вперёд, а ось Y - вверх. На плоской схеме мы не видим ось Y, но подразумеваем, что она поднимается из схемы вверх. Вот так

Назовём эту систему координат “мировой”. В ней по XZ будем задавать позиции вершин уровня в плоскости, а по оси Y будем откладывать высоту пола и потолка в разных комнатах. В этой же системе координат зададим позицию камеры, которая будет перемещаться по уровню и поворачиваться влево-вправо. Задача рендера - строить на экране картинку, которую “видит” камера из своей текущей позиции.

Нарисуем первую комнату уровня на схеме в виде прямоугольника. Зададим для него Y-координаты пола и потолка. Например, yFloor=1000, yCeil=1200. Вот наша схема:

Если смотреть на этот объект сбоку в 3d, мы должны увидеть два прямоугольника: нижний - это пол будущей комнаты, верхний - её потолок. Стен у комнаты пока нет, их добавим позже.

Вместо слова “прямоугольник” будем дальше использовать слово “полигон” - потому, что его форма не всегда будет прямоугольная, да и количество вершин в нём не всегда 4. Усложним комнату. Дорисуем справа небольшой полигон и укажем у него высоту пола чуть повыше (1010). Потолок оставим на прежнем уровне 1200.

Снова посмотрим сбоку: появилась ступенька

 Добавим ещё несколько полигонов, повышая высоту пола.

Теперь это уже целая лестница.

Но есть одна проблема - между ступеньками видны дырки, а их там быть не должно.

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

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

Осваиваемся с форматом уровня

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

Центральный узкий полигон (который будет стенкой) разбиваем ещё на три полигона: A, B, C

Полигон B будет дверным проёмом. Осталось каждому полигону присвоить высоту пола и потолка. Чтобы полигоны A,C стали стенами, зададим высоту их пола выше, чем высоту потолка остальной комнаты. У полигона B уровень пола оставим без изменений, но уменьшим высоту потолка и получится дверной проём. Теперь комната должна выглядеть так.

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

Наружние стены сделаем аналогично стене посреди комнаты: просто добавим полигоны по периметру и укажем у них высоту пола выше, чем у потолка комнаты. Наш первый уровень готов!

О смежных полигонах

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

На картинке ребро полигона отмеченное стрелками, стыкуется одновременно с двумя соседними полигонами. Из-за этого при рендеринге рёбра полигонов могут неплотно прилегать друг к другу из-за погрешности растеризации смежных рёбер. А в нашем случае, это ещё и усложнило бы алгоритм рендера. К счастью, такую геометрию легко исправить - достаточно разбить полигон на два поменьше, добавив ребро (нижняя картинка). Вернёмся к схеме уровня и исправим её аналогичным образом. Вот, теперь всё правильно!

Хранение уровня на С++

Во-первых, у нашего уровня есть вершины, у которых по две координаты X и Z. Каждую вершину будем хранить в такой структуре:

struct FPoint2D
{
	float x;
	float z;
};

В компьютерной графике принято вершины хранить отдельно от полигонов, так расходуется меньше памяти. Поэтому вершины уровня будем хранить в отдельном векторе:

std::vector<FPoint2D> verts;

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

struct Poly
{
	float yCeil;   // Y-координата потолка
	float yFloor;  // Y-координата пола 
	std::vector<int> vertIndices; // Индексы вершин, лежащих в векторе verts
};

Но, забегая вперёд, для рендера нам будет удобна отдельная сущность “ребро полигона”. Поэтому вместо вектора с индексами вершин, будем хранить в полигоне вектор с рёбрами.

struct Poly
{
	float yCeil;   // Y-координата потолка
	float yFloor;  // Y-координата пола 
	std::vector<Edge> edges; // Рёбра полигона
};

Где ребро содержит индекс первой вершины (из двух своих вершин)

struct Edge
{
	int firstInd;   // Индекс первой вершины ребра
};

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

Рендер

Геометрия уровня задана, теперь нужно её отрендерить. Для этого нам потребуется камера, которая будет смотреть на игровой мир. Положение камеры в мировой системе координат задаётся координатами X,Y,Z и углом поворота Alpha (влево-вправо). Представим, что это камера в виде сверху, а разрешение буфера экрана по-горизонтали всего 10 пикселей для наглядности.

Через центр каждого пикселя будем бросать луч, искать его пересечение с рёбрами полигонов уровня и рисовать одну колонку пикселей в буфере экрана. Буфер экрана - двумерный массив, где каждому пикселу соответствуют, например, три байта (если формат пиксела RGB). Заметьте, что поиск пересечения луча с рёбрами полигонов идёт не в 3D, а в 2D! Это намного быстрее. К тому же, мы трассируем луч не для каждого пиксела, а лишь для каждой колонки пикселов. Это значительно сокращает объём вычислений.

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

Представим как выглядит одна колонка пикселей такой сцены:

Сверху вниз это будут несколько отрезков:

• Потолок ближнего полигона

• Верхняя стенка

• Потолок дальнего полигона

• (Пустой промежуток)

• Пол дальнего полигона

• Нижняя стенка

• Пол ближнего полигона

Если мы будем знать начало и конец каждого вертикального отрезка (отмечены красными стрелками), мы сможем нарисовать эти отрезки.

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

Этап 1

XZ мы узнаем при пересечении луча с рёбрами полигонов. Напомню, это 2D-операция в плоскости

Y в мировой системе мы возьмём из Poly::yCeil и Poly::yFloor того полигона, к которому относится точка.

Этап 2

Остаётся из XYZ-координаты в мировой системе получить Y в экранной системе. Сначала надо преобразовать точку в “систему камеры”. Это такая система, где камера находится в начале координат (0,0,0) и смотрит в направлении положительной полуоси Z. 

Для перевода в эту систему, надо вычесть из позиции точки позицию камеры и повернуть точку в плоскости XZ относительно начала координат на угол противоположный углу камеры. Получим Ycam, Zcam - это позиция вершины уровня в системе камеры. Осталась проекция на экран. Посмотрим на схему

По схеме видно, что Yscr (в экранной системе) пропорционально Ycam и обратно пропорционально Zcam. Получается, что проекция это отношение Ycam/Zcam. Но надо домножить на константу, зависящую от угла обзора камеры. Удобно в качестве такой константы взять

kProj = xBufSize / 2 / tan(xFov / 2)

где xBufSize - число пикселов в экранном буфере по-горизонтали, а xFov - горизонтальный угол обзора камеры в радианах. Чтобы получить Y-координату в системе пикселов экранного буфера, осталось инвертировать ось (так как в системе камеры ось Y направлена вверх, а в экранном буфере вниз) и добавить половину размера экранного буфера (чтобы нулём был не центр экрана, а верх буфера). Финально:

Ysrc = Ycam / Zcam * kProj + yBufSize / 2

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

Про overdraw

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

Чтобы это реализовать, заведем две целочисленные переменные:

• yUp - это крайний Y, отрисованный на данный момент сверху кадра

• yDown - это крайний Y, отрисованный на данный момент снизу кадра

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

Детали реализации и оптимизация

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

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

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

Частные случаи

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

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

Наклон камеры

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

Однако, мы можем немного сжульничать и сделать фейковый наклон камеры путём добавления сдвига в формулу проецирования. Ноль - смотрим горизонтально, положительное число - картинка съезжает вниз (как будто мы смотрим вверх), отрицательное число - картинка съезжает вверх (как будто мы смотрим вниз). Такой фейковый наклон на 90 градусов не сделать - перспективные искажения станут слишком сильными, но в небольшом диапазоне выглядит вполне прилично. Именно так и делается в Doom like рендерах.

Субпиксельная точность

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

Один из примеров учёта субпиксельной точности мы уже встречали выше, когда говорили о сканирующем луче. Там луч выпускался из камеры через центр пиксела. Другой пример - нахождение нижнего и верхнего пиксела отрезков (см. выше, где мы искали Ysrc). Здесь мы готовимся к циклу отрисовки пикселов и нам нужны целочисленные координаты. Переход от дробных к целыми экранным координатам стоит делать с учётом субпиксельной точности. Это влияет на способ округления и тут нужно ответить на вопрос: экранные координаты (0,0) - это центр левого верхнего пиксела или его левый верхний угол? Вообще, это дело вкуса и разные движки работают с этим по-разному. Мне ближе второй вариант, чтобы на экране не было отрицательных значений. Рассмотрим пример нахождения начала и конца отрезка с субпиксельной точностью при проекции на экран.

Здесь красные риски - это дробные экранные координаты начала и конца отрезка. Например, 0.8 и 7.3. Я взял за правило, что рисую пиксел только, если его центр попадает внутрь интервала (дробного). Центр верхнего на рисунке пиксела имеет экранную координату 0.5, а это не попадает в интервал [0.8, 7.3], поэтому верхний пиксел не рисуем. Аналогично снизу. Руководствуясь этой идеей, я подобрал способ округления, который 0.8 округлит до 1. А 0.4 до 0.

Текстурирование

Описанного выше достаточно, чтобы рисовать уровень, но скорее всего мы хотим, чтобы стены/потолок/пол не были залиты одним цветом, а имели текстуры. Чтобы рисовать текстуру нам в каждом пикселе нужно знать текстурные координаты U и V. Причём, их расчёт должен быть быстрым, чтобы рендер остался реалтаймовым. Имея U и V, мы сможем получить цвет тексела  текстуры (используя U и V как индексы двумерного массива текстуры) и скопировать цвет в текущий пиксел экранного буфера.

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

Субтексельная точность

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

Здесь изображён луч пущенный из камеры (из правого нижнего угла) через центр пиксела экранного буфера. Этот луч упёрся в полигон, на который “наклеена” текстура. Так вот, расчёты с субтексельной точностью должны показывать в какую точку тексела пришёл луч. U,V координаты (0,0) - это левый верхний угол левого верхнего тексела текстуры, а координаты (1,1) - правый нижний угол правого нижнего тексела.

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

Текстурирование стен

Для хранения исходной информации о мэппинге стен (она задаётся при дизайне уровня) в структуру Edge добавим поля:

float u[2];      // U-координаты слева и справа полигона стены (в начале и в конце ребра)
float vWall;     // V-координата вверху полигона стены
float vWallAdd;  // Приращение V-координаты на каждый Unit в мировой системе

Начнём с самого простого - расчёта U-координаты для текущей колонки пикселов.В обсуждённой выше части рендера мы находим пересечение сканирующего луча с рёбрами полигонов. А значит у нас уже есть число от 0 до 1, показывающее в каком соотношении рассеклось ребро. Назовём это число interp. Тогда U-координата для всех пикселов текущей колонки постоянна и равна

curU = (u[0] - u[1]) * interp + u[1]

С V-координатой сложнее. Она будет линейно меняться в цикле отрисовки вертикального отрезка. Значит нужно в начале отрезка рассчитать curV и addV такие, что для каждого пиксела будем использовать curV, а потом делать curV += addV для следующего пиксела.

Чтобы получить addV, сначала посчитаем коэффициент vDens равный отношению высоты отрезка в Unit’ах мировой системы к высоте отрезка в экранных пикселах (до их округления!). Тогда addV получим так:

addV = edge.vWallAdd * vDens

curV казалось бы можно просто взять из свойств ребра edge.vWall - ведь это поле как раз означает V-координату в  верхней части стены (см. рисунок выше). Но здесь требуется несколько важных корректировок. Посмотрим на рисунок

• A - пикселы нарисованные до текущего отрезка (они будут экранировать текущий отрезок)

• B - красные риски - это спроецированные дробные концы текущего отрезка

• C - пикселы текущего отрезка, если бы не было экранирования

• D - пикселы текущего отрезка с учётом экранирования

Тогда дробный интервал dy будет корректировкой в пикселах, а dy * addV корректировкой в текстурный единицах. Итого

curV = edge.vWall + dy * addV

Теперь curV и addV готовы к циклу отрисовки пикселов отрезка. Мы разобрали текстурирование стены возникающей при смене высоты пола. Верхняя стена (возникающая при смене высоты потолка) текстурируется аналогично. Для неё в структуру ребра добавляются поля аналоги vWall и vWallAdd.

Текстурирование пола

Для хранения исходной информации о мэппинге пола (задаётся при дизайне уровня) в структуру Edge добавим поля

float uFloor;
float vFloor;

Расчёт U и V для каждого пиксела имеет одинаковую логику, поэтому рассматривать будем на примере U. Координата U между пикселами столбца меняется нелинейно. К счастью, есть математический трюк, решающий эту проблему. Оказывается, что если по отрезку интерполировать не между U1 и U2, а между U1/Z1 и U2/Z2  (где U1,U2 - это U координаты на концах отрезка, а Z1,Z2 - это Z координаты концов отрезка в системе камеры), то эта величина изменяется как раз линейно. А значит для неё можно в начале отрезка один раз рассчитать приращение и для каждого пиксела просто прибавлять его.

Но поскольку для каждого пиксела нужна реальная U-координата, то её необходимо как-то получить. Для этого вместе с U/Z будем интерполировать ещё одно число между 1/Z1 и 1/Z2 (тоже линейно). Чтобы для пиксела получить U достаточно текущее U/Z поделить на текущее 1/Z.

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

Внезапная проблема возникает с U-координатой низа отрезка для полигона, в котором находится камера.

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

• Вводим понятие zNear - расстояние, ближе которого геометрия уровня не может находиться внутри пирамиды камеры.

• Находим две точки сечения проблемного полигона прямой z=zNear в системе координат камеры

• Эти две точки образуют отрезок, на концах которого считаем координаты U

• Находим сечение этого отрезка основным секущим лучом. В точке пересечения находим новую координату U

• Полученную точку проекцируем на экран

• Делаем коррекцию U, как мы это делали для V координаты стен при усечении отрезков

С мэппингом уровня закончили.

Собираем техно-демку

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

Всем добра и интересных домашних проектов!

Ссылки

Работа рендера в динамике

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

Домашний проект, тестовое задание при поступлении на работу: написать программу рисующую анимированный фейерверк