Мне всегда нравились классические шутеры от первого лица 90-х. Я часами просиживал за моим 386-м, играя Doom, потрясённый тем, как кому-то удалось написать код, отрисовывающий на моём экране 3D-графику в реальном времени с отличным разрешением 320x200. Я немного знал программирование (только что начал изучать BASIC), поэтому осознавал, что глубоко внутри это всего лишь куча математики и байтов, записываемых в видеопамять. Но в то время даже массивы для меня были довольно сложным понятием, поэтому я не мог даже начать постигать всю сложность 3D-рендеринга.
В то время все писали 3D-движки с нуля, потому что другого способа не было. Но сегодня написание логики 3D-рендеринга с нуля скорее всего окажется плохой идеей. Очень плохой. Почти как изобретение колеса! При наличии огромного количества 3D-движков и библиотек, намного более хорошо протестированных и оптимизированных, чем то, что вы можете сделать сами, нет никаких причин для разумного разработчика начинать писать собственный движок.
Если только…
Представьте, что вы можете вернуться в машине времени назад в 90-е, когда ещё не было OpenGL и DirectX, не было видеопроцессоров. Всё что у вас есть — ЦП и экран, заполненный пикселями. Вам всё придётся писать самому.
Если эта идея кажется вам интересной, то вы не одиноки: это именно то, что можно сделать на такой выдуманной консоли, как TIC-80.
После того, как я написал 8-bit panda, мою первую игру для этой консоли (о ней можно прочитать в моей предыдущей статье), я начал искать идею для новой игры. Поэтому я решил поставить перед собой задачу по написанию с нуля простого 3D-движка и созданию в нём минимального шутера от первого лица.
Вот так я начал писать FPS80.
В этой статье я опишу процесс 3D-рендеринга в FPS80 и немного расскажу о всех компромиссах для обеспечения скорости (и бесконечных ужасных хаках!) при реализации быстрого 3D-рендеринга на этой слабой машине.
Основы 3D-графики
Если вы уже знаете, как работает 3D-рендеринг, то этот раздел покажется вам скучным. Можете сразу приступать к следующему разделу!
Полное объяснение 3D-графики слишком объёмно для этой статьи, так что мы только вкратце рассмотрим то, что важно для наших целей.
Фундаментальная идея 3D-графики — проецирование 3D-пространства на 2D-поверхность (экран компьютера). Иными словами, одна из основных задач 3D-движка — найти для заданных координат (x, y, z) точки в пространстве 2D-координаты (x, y) места, в котором точка должна находиться на экране.
Для этого 3D-движки выполняют серию трансформаций. Трансформация — это краткое определение выражения «преобразование из одной системы координат в другую». Преобразования могут представлять движение (перемещение, поворот, масштаб) и проецирование. Обычно они представляются матрицами.
Для вычисления экранного положения точки нам сначала нужно трансформировать её по её модельной матрице M, переведя её в пространство мира. Затем мы умножаем её на матрицу вида V , чтобы учесть положение камеры, что переводит её в пространство камеры (или глаза). Затем мы применяем матрицу проекции P, которая выполняет перспективную трансформацию, делающую близкие объекты большими, а удалённые объекты — маленькими. После этого выполняется перспективное деление, переводящее точки в координаты экрана (окна просмотра):
p’ = P * V * M * p
Применение этой последовательности операций к точке часто называется «проецированием» точки. Но сцены состоят из объектов, а не точек, поэтому 3D-движок занимается не только этим.
3D-объект состоит из полигонов. Для их отрисовки движок обычно разделяет полигон на треугольники, затем проецирует каждую вершину каждого треугольника с помощью представленной выше формулы, а потом отрисовывает получившиеся треугольники экранного пространства на экране. Этот процесс называется растеризацией: это преобразование из векторной формы (треугольника) в растровую (сами пиксели экрана). Но отрисовка треугольников в случайном порядке не даст хороших результатов. потому что может оказаться, что дальний треугольник отрисуется поверх ближнего, поэтому движок должен использовать стратегию решения такой проблемы. Обычно она решается или предварительной сортировкой полигонов, или созданием буфера глубин, в который записывается глубина каждого пикселя для вывода на экран, чтобы можно было знать, когда нужно и когда не нужно отрисовывать пиксель.
Добавьте наложение текстур и освещение, а это ещё один целый слой математики, которую вычисляет движок, чтобы выяснить окончательный цвет пикселя.
Нужно ли нам полное 3D?
Честно говоря, я начал реализовывать полный процесс создания 3D-графики, описанный выше, но осознал, что на TIC-80 он будет слишком медленным. Как и на старых ПК, все математические вычисления и отрисовка запросто могут перегрузить ЦП и сделать игру тормозной. Я написал пример, в котором отрисовывались всего лишь четыре вращающихся куба с наложенными текстурами, и даже этого было достаточно, чтобы частота кадров опустилась ниже 10 fps. Стало очевидно, что «полное 3D» работать не будет. В частности, «бутылочным горлышком» стал fill rate, то есть проблема в основном была не с математикой проецирования точек, а со временем, которое требовалось для отрисовки всех пикселей треугольников на экран, особенно когда это делать несколько раз из-за того, что полигоны занимают перекрывающиеся части экрана.
Но нужно ли нам полное 3D? На самом деле, оказывается, что многие старые игры 90-х не реализуют «полное 3D». Вместо него они реализуют хитрые механизмы ограничения графики, чтобы её рендеринг был менее затратным.
Итак, вот ограничения, которые я ввёл:
- Весь уровень является плоским: никаких лестниц, ям, балконов, вторых этажей и всего подобного. То есть пол и потолок находятся на постоянной высоте.
- Все стены имеют одинаковую высоту, от пола до потолка. И все они непрозрачные.
- Игрок может повернуться в любом направлении, но не может наклонять голову вверх и вниз, а также вбок. Другими словами, камера имеет только одну степень свободы вращения: курс или рыскание.
- Все объекты отрисовываются как «биллборды», то есть 2D-изображения, отрисованные в 3D-пространстве таким образом, что всегда направлены на камеру.
- Существуют только точечные источники света. Один из них всегда находится в камере (как факел в руках игрока). Другие могут создаваться на короткий промежуток времени, например, для эффектов взрывов.
Как нам помогут эти ограничения?
То, что пол и потолок имеют постоянную высоту и что все стены идут от пола до потолка (а игрок не может смотреть вверх/вниз) создаёт замечательное свойство, которое очень нам поможет: в каждой позиции X экрана будет не более одной стены. Другими словами, все видимые стены занимают среднюю часть экрана и две разные стены никогда не будут занимать одну координату X:
Выделим стены разными цветами, чтобы их было заметнее:
Как вы видите, на скриншоте шесть стен (дверь тоже является «стеной»), и все они очень удобно расположены на экране: каждая координата X экрана соответствует только одной стене.
Это очень полезно для нас, потому что мы можем рендерить стены в два этапа:
- Определяем, какая стена должна оказаться в каждой координате X (другими словами, строим карту из координат X к стенам).
- Обходим (только один раз!) все координаты X, отрисовывая для каждой нужную часть стены.
Для сущностей (объектов) — монстов, снарядов, колонн, фонтанов, деревьев и подобного — мы воспользуемся часто используемой техникой биллбординга. Сущности будут представлены не настоящим 3D-объектом, мы просто будем отрисовывать плоское 2D-изображение в 3D-координате как вырезанную из картона фигуру. Этот способ очень малозатратен при отрисовке.
Наша процедура проецирования
Даже в нашем очень упрощённом 3D-мире нам всё равно потребуется проецировать точки из 3D-пространства в 2D. Однако наши ограничения делают математические расчёты намного проще и быстрее в обработке. Вместо выполнения полного матричного умножения мы можем обойтись гораздо более простым способом: мы определяем неизменяемые части матричных вычислений (те, которые не зависят от положения игрока или объекта), а потом просто вставляем в код заранее вычисленные значения. Я рассмотрю всё это вкратце, но если вам интересны подробные вычисления, то вот как они выводятся.
Вспомните формулу:
p’ = P * V * M * p
Где p’ — это экранные координаты (выходные данные), а p — мировые координаты (входные данные). В нашей простой модели M — это единичная матрица (всё представлено в мировом пространстве), то есть она превращается в:
p’ = P * V * p
Матрицу видимости V можно вычислить простым перемещением и вращением камеры, которые ограничены вращением только по оси Y. Если вращение — это R, а перемещение — T, тогда:
p’ = P * R * T * p
Матрицу проецирования P можно вычислить заранее, потому что она зависит только от области видимости и ближней/дальней плоскостей отсечения, которые на протяжении всей игры постоянны. Упростив вычисления, мы в результате придём к довольно прямолинейной (если всё максимально жёстко задать в коде) функции проецирования:
function S3Proj(x,y,z)
local c,s,a,b=S3.cosMy,S3.sinMy,S3.termA,S3.termB
local px=0.9815*c*x+0.9815*s*z+0.9815*a
local py=1.7321*y-1.7321*S3.ey
local pz=s*x-z*c-b-0.2
local pw=x*s-z*c-b
local ndcx,ndcy=px/abs(pw),py/abs(pw)
return 120+ndcx*120,68-ndcy*68,pz
end
Посмотрите на эти магические числа: 0.9815, 1.7321 и т.д. Все они взяты из заранее подготовленных матричных вычислений. Сами по себе они не имеют интуитивно понятных значений (поэтому я даже не стал превращать их в константы).
Переменные cosMy, sinMy, termA и termB вычисляются из текущего перемещения и вращения камеры перед вызовом функции, потому что их достаточно вычислить только один раз для всех точек.
Рендеринг стен
На первом этапе мы будем использовать массив, который назовём H-Buf (горизонтальный буфер), определяющий то, что будет отрисовываться в каждой координате X экрана. «H-Buf» — это нестандартное обозначение, я придумал его сам. Он называется H-Buf, потому что он H (горизонтальный) и он Buf (буфер). Я не очень оригинален при выдумывании имён.
Экран TIC-80 содержит 240 столбцов (240x136), поэтому H-Buf имеет 240 позиций. Каждая позиция соответствует координате X экрана, и содержит информацию о том, какая часть стены должна быть там отрисована. Чтобы всё упростить, я буду называть это не «куском стены шириной в один пиксель», а «срезом стены». То есть каждая позиция в H-Buf даёт информацию о том, какой срез стены нужно отрисовывать в каждой координате X экрана:
- wall (object): — это ссылка на стену, которая будет отрисована в этом срезе.
- z (float): — координата z экранного пространства (глубина) этого среза.
- и многое другое… но пока не будем об этом!
Этого нам достаточно, по крайней мере, для первого этапа! Итак, нам нужно обойти все стены уровня (скоро мы поговорим о том, как сделать эту операцию более эффективной). Для каждой стены мы:
- Используем функцию проецирования на четырёх её углах для определения того, где она окажется на экране: left x, right x, left-top y, left-bottom y, right-top y, right-bottom y, left z (глубина), right z (глубина).
- Обходим каждую координату X (от left_x до right_x) стены и записываем срез стены в H-Buf, когда его глубина меньше, чем существующий срез в этой позиции в H-Buf.
Первый тест «глубина этого среза меньше, чем у существующего среза» называется тестом глубин. Он позволяет нам рендерить стены в правильном порядке — ближайшие к игроку перекрывают дальние. Вот соответствующий фрагмент кода:
function _AddWallToHbuf(hbuf,w)
local startx=max(S3.VP_L,S3Round(w.slx))
local endx=min(S3.VP_R,S3Round(w.srx))
local step
local nclip,fclip=S3.NCLIP,S3.FCLIP
startx,endx,step=_S3AdjHbufIter(startx,endx)
if not startx then return end
for x=startx,endx,step do
-- индексы hbuf начинаются с 1 (потому что это Lua)
local hbx=hbuf[x+1]
local z=_S3Interp(w.slx,w.slz,w.srx,w.srz,x)
if z>nclip and z<fclip then
if hbx.z>z then -- тест глубины.
hbx.z,hbx.wall=z,w -- запись новой глубины и среза стены
end
end
end
После выполнения этой операции для каждой стены в H-Buf будет содержаться правильная информация о том, какой срез нужно рендерить в каждой координате X, то есть для рендеринга нам нужно просто циклически отрендерить правильную часть нужной стены. Благодаря этому такой подход оказывается быстрым: когда мы рисуем стены, нет ни промедления, ни лишней рабты, мы точно знаем, что здесь нужно отрисовывать и касаемся только пикселей, которых нужно касаться. У нас никогда не бывает так, что сначала мы отрисовываем часть стены, а потом рисуем поверх неё другую стену (нет перерисовки).
Вот код рендеринга. Заметьте, насколько он прост: для каждой X мы просто рендерим столбец текстуры в этой координате X, и ничего больше:
function _S3RendHbuf(hbuf)
local startx,endx,step=_S3AdjHbufIter(S3.VP_L,S3.VP_R)
if not startx then return end
for x=startx,endx,step do
local hb=hbuf[x+1] -- индексы hbuf начинаются с 1
local w=hb.wall
if w then
local z=_S3Interp(w.slx,w.slz,w.srx,w.srz,x)
local u=_S3PerspTexU(w,x)
_S3RendTexCol(w.tid,x,hb.ty,hb.by,u,z,nil,nil,
nil,nil,nil,w.cmt)
end
end
end
Удваиваем частоту кадров с помощью очень странного трюка
Даже несмотря на то, что TIC-80 имеет разрешение всего лишь 240x136, заполнение всего экрана по-прежнему отнимает довольно большую часть мощности ЦП, даже если мы совсем не тратим время и точно знаем, что отрисовывать. Даже самый быстрый алгоритм рендеринга на простых сценах выдаёт около 30 fps, а на более сложных сценах частота значительно падает.
Как нам обойти эту проблему?
Нам нужно задаться вопросом: действительно ли требуется заполнять весь экран? Нет, не требуется. Глаз человека «сглаживает» огрехи происходящих быстро событий (а люди, играющие в ретро-игры, очень снисходительны к небольшим визуальным «глюкам»!), поэтому мы можем ускорить рендеринг, заполняя в каждом кадре только половину экрана.
Мы сделаем следующее:
- В чётные кадры мы будем отрисовывать только чётные координаты X.
- В нечётные кадры мы будем отрисовывать только нечётные координаты X.
Этот процесс также известен как чересстрочный рендеринг. Это означает, что в каждом кадре мы будем на самом деле рендерить только 120x136 пикселей, а не полные 240x136. Мы не очищаем экран в каждом кадре, поэтому пиксели, которые мы не будем отрисовывать, просто сохранятся как остатки предыдущего кадра.
Это вызывает небольшие видимые «глитчи», особенно при быстром движении, но на самом деле это работает на игру, а не против неё, придавая ретро-ощущение телевизионного экрана.
Вот что на самом деле мы будем рендерить каждый кадр (по крайней мере, это мы видели бы, если бы другие столбцы ещё не были заполнены пикселями из предыдущего кадра):
Один кадр чересстрочного рендеринга. Неотрендеренные столбцы для наглядности оставлены пустыми. На самом деле они будут заполнены результатами рендеринга предыдущего кадра.
Рендеринг среза стены
Отлично, теперь мы переходим к рендерингу среза стены. Мы уже знаем, какой срез нужно рендерить, и знаем, где. Всё, что нужно сделать — определить, какие пиксели нужно рендерить в этом столбце и какого цвета они должны быть. Как это сделать?
Срез стены (вертикальный столбец стены толщиной в один пиксель).
- Вычислить освещение, падающее на этот срез, учтя источники света и расстояния.
- Вычислить горизонтальную координату текстуры для среза стены (с коррекцией перспективы).
- Вычислить верхнюю и нижнюю координаты Y среза, проинтерполировав конечные точки стены.
- Заполнить каждый пиксель сверху донизу, что означает определение вертикальной координаты текстуры (афинное преобразование), сэмплирование текстуры, потом модулирование по освещению, и, наконец, запись пикселя на экран.
Мы можем обойтись афинным преобразованием (вместо преобразования, корректного с точки зрения перспективы) для вертикальной координаты текстуры потому что стены относительно экрана всегда стоят вертикально (это гарантировано, потому что игрок не может поворачивать голову вверх и вниз, а также вбок). Если бы ситуация была иной, нам бы пришлось реализовать верное с точки зрения перспективы наложение текстур и для горизонтальных, и для вертикальных координат текстур, что было бы медленнее.
Рендеринг сущностей (добавляем стенсил-буфер!)
Ну ладно, стены — это забавно, но движок не будет игрой без врагов. Как я сказал ранее, враги рендерятся как биллборды, то есть как плавающие изображения, всегда направленные в сторону игрока.
Сущности, отрисованные как биллборды (всегда направленные в сторону камеры).
Однако эти изображения не являются просто двухмерными: они отрисовываются в определённой точке пространства, поэтому у них есть глубина. Если враг заходит за стену, стена должна рендериться перед врагом (враг должен перекрываться стеной), и никак иначе.
Как добиться этого эффекта?
Если бы мы хотели всё упростить, мы могли бы воспользоваться алгоритмом художника (который больше походит на отсутствие алгоритма): просто отрисовывать объекты сзади вперёд, при этом объекты на переднем плане естественным образом отрисовывались бы поверх объектов с заднего плана, обеспечивая нужный эффект.
Что же в нём плохого? Его просто понять. Его просто написать. Но… он очень медленный, особенно на TIC-80, ограниченной по скорости заполнения. При такой реализации мы бы потратили много ресурсов на отрисовку красиво затекстуренных и освещённых пикселей, которые бы позже были просто перекрыты другими пикселями.
И здесь нам нужно ввести новый буфер: стенсил-буфер. В 3D-рендеринге стенсил-буфером называется 2D-поверхность размером с экран, которая показывает, где можно и где нельзя рисовать. Он похож на фильтр. Каждый пиксель в стенсил-буфере может быть «включен», то есть говорить «заблокировано, не рисовать» или «выключен», то есть говорить «свободно, можно рисовать». В зависимости от реализации значения могут быть обратными, но в нашем коде мы будем использовать значение «истина» для обозначения состояния «занято, не рисовать».
Когда программа «считывет стенсил-буфер», это означает, что перед отрисовкой она проверяет, «включен» ли стенсил-буфер в каждой позиции. Если это так, то она не будет рендерить пиксели над существующем пикселем.
Когда программа «записывает в стенсил-буфер», это означает, что когда она рендерит что-то в заданной позиции экрана, она выполняет запись в стенсил-буфер, чтобы обозначить, что эта позиция уже занята и не должна перерисовываться заново.
Итак, вот что мы сделаем. Перед рендерингом стен, но после вычисления H-Buf мы отрисовываем сущности. Полный алгоритм будет следующим:
- Очищаем стенсил-буфер.
- Вычисляем H-Buf.
- Рендерим сущности спереди назад (считываем/записываем стенсил, тест глубины в H-Buf).
- Рендерим стены с помощью H-Buf (считываем стенсил).
При рендеринге каждого пикселя каждой сущности мы записываем в стенсил-буфер, запрещая рендерить поверх него всё остальное. Так что нам нужно рендерить в порядке спереди назад. Это значит, что всё, что мы отрисовываем, является окончательным. Это означает отсутствие перерисовки, мы никогда не тратим зря пиксели, отрисовываемые на экран.
При отрисовке сущностей мы знаем их глубину в экранном пространстве и знаем глубину стены в этой позиции X (благодаря H-Buf!), поэтому мы можем также выполнить тест глубины этого столбца. Это значит, что мы правильным образом отказываемся от рендеринга частей сущности, которые потом будут скрыты за стеной (даже несмотря на то, что на этом этапе рендеринга стены ещё нет!). Мы снова не хотим тратить ни одного лишнего пикселя. Они для нас очень затратны.
Вот пример сцены с четырьмя перекрывающими друг друга биллбордами и порядком, в котором они рендерятся. Первым идёт фонтан (цифра 1, самый ближний), потом дерево (2), затем зелёный монстр (3) и оранжевый монстр (4, самый дальний).
А что насчёт пола и потолка?
Пол и потолок рендерятся на последнем этапе процесса, потому что они являются единственными пикселями, оставшимися после рендеринга сущностей и стен. С потолком всё просто: он просто полностью чёрный, мы заполняем эти пиксели, просматривая H-Buf и определяя, где начинается стена. Каждый пиксель над ней является чёрным (но мы всё равно проверяем стенсил-буфер). Готово.
Пол более сложен, потому что необходимо применить эффект освещения: мы хотим, чтобы отдалённые от игрока части пола были более тёмными.
Но для вычисления освещения нам нужно знать глубину каждого пикселя пола. Определить её для каждого пикселя на удивление просто, потому что мы начинаем в обратном порядке с координат экранного пространства для определения координат мирового пространства, а потом определяем расстояние от игрока до них. Более того: мы можем заранее вычислить всё вручную и ввести эти магические числа, чтобы процедура была очень простой:
function _S3FlatFact(x,y)
local z=3000/(y-68)
return _S3LightF(x,z)
end
Для заданных координат x,y пикселя на полу соответствующая координата Z на полу будет всего лишь 3000/(y-68). Я понятия не имею, почему, так просто получилось из вычислений на бумаге. И мы используем это в _S3LightF для вычисления количества освещения, падающего на эту точку, соответствующего модулирования цвета пола.
Вот как выглядит палитра освещения пола. Заметьте, что она постепенно темнеет при удалении от игрока:
Дополнительные точечные источники света
Мы обеспечим поддержку временных точечных источников света для эффектов освещения, например, когда игрок бросает огненный шар и тот взрывается:
Принцип тот же: мы вычисляем расстояние в экранном пространстве от отрисовываемой точки до вторичного источника освещения (взрыва) и учитываем его влияние.
Учтите, что мы не используем этот эффект для постоянного освещения (например, факелов на стенах), потому что он затратен и не слишком надёжен. Поскольку он вычисляется в экранном пространстве, то на самом деле не учитывает вращение и перемещение камеры, и у него возникают неприятные особенности и деления на ноль, когда источник находится слишком близко к игроку.
Модуляция и дизеринг цвета
TIC-80 позволяет работать только с 16 цветами, так какже нам создать эффекты освещения, делая пиксели ярче или темнее?
Я использовал следующую технику: создал три различных «тона», имеющих четыре различных оттенка, от тёмного к светлому. Эти тоны можно модулировать, выбирая один из четырёх оттенков каждого, плюс чёрный (цвет 0) в качестве самого тёмного. В результате у нас получится три «линейных изменения» — серое, зелёное и коричневое:
clrM={
-- Серый "градиент"
{1,2,3,15},
-- Зелёный "градиент"
{7,6,5,4},
-- Коричневый "градиент"
{8,9,10,11}
},
Они задаются как простые массивы, так что когда нам нужно модулировать цвет на определённое количество освещения, нам всего лишь нужно найти цвет и определить, какой другой цвет того же линейного изменения надо выбрать.
А как насчёт промежуточных цветов?
Для них я применил стратегию, которая использовалась в старом графическом оборудовании: дизеринг. Поскольку у нас не может быть одного пикселя промежуточного цвета, мы нарисуем узор, в котором часть пикселей будет иметь один цвет, а другая часть — другой цвет. В результате глаз будет воспринимать их как промежуточный цвет:
Эффекты частиц
Чтобы дать игроку приятную обратную связь при убийстве монстров или уничтожении объектов, мы воспользуемся простыми эффектами частиц:
Это просто небольшие прямоугольники, симулируемые в мировом пространстве и преобразуемые в экранное пространство на этапе рендеринга. Из соображений скорости они не обрезаются и не учитываются в стенсил-буфере, а просто отрисовываются поверх всего остального (небольшое отклонение от принципа «не тратить лишних пикселей»). К счастью для нас чересстрочный рендеринг маскирует тот факт, что они являются прямоугольниками: посколько они быстро двигаются и рендерятся каждый кадр в разных позициях, то разбиваются чересстрочностью на части и выглядят более «органичными».
Заключение
В этой статье мы вкратце рассмотрели процесс рендеринга в FPS80. У меня не было никакого опыта в написании 3D-движков с нуля, поэтому я уверен, что многое можно было сделать лучше, а мои объяснения во многом ошибочны. Свяжитесь со мной, если найдёте ошибку (мне можно написать в Twitter).
Разработка собственной логики 3D-рендеринга оказалась очень интересной и познавательной. Особенно забавной была необходимость выжимать каждую каплю скорости из алгоритмов. Это дало мне (небольшое) представление о том, как создавали 3D-движки в 90-х!
Исходный код FPS80 и движок рендеринга выложены на github. Можете свободно использовать их в своих проектах!
Примечание. Как играть: Установите на компьютер виртуальную консольTIC-80. Запустите TIC-80 и введите команду
surf
. Выберите [tic.computer/play]
и нажмите Z для выбора. Найдите в списке FPS80
и нажмите Z для запуска. Также можно поиграть в игру на веб-сайте TIC-80 (но звук там сломан).
Автор: PatientZero