РЕДАКТИРОВАТЬ: Как играть: Установите виртуальную консоль TIC-80 на свой компьютер. Запустите TIC-80 и введите команду surf. Выберите [tic.computer/play] и нажмите Z, чтобы выбрать его. Найдите FPS80 в списке и нажмите Z, чтобы начать. Также можно поиграть на сайте ТИЦ-80 (но звук битый).

Мне всегда нравились классические шутеры от первого лица 90-х годов. Раньше я часами сидел перед своим 386, играя в Doom, удивляясь тому, как кто-то мог написать код, который рисовал бы трехмерную графику в реальном времени на моем экране в реальном времени с потрясающим разрешением 320x200. Я немного разбирался в программировании (я только начал изучать BASIC), поэтому я понял, что в глубине души все это было кучей математики и байтов, записываемых в видеопамять. Но в то время массивы были для меня достаточно сложной концепцией, поэтому я даже не мог понять сложность 3D-рендеринга.

В то время все писали свои 3D-движки с нуля, потому что другого выхода не было. Но в настоящее время писать логику 3D-рендеринга с нуля, вероятно, действительно плохая идея. Действительно плохо. Поговорим об изобретении велосипеда! С таким количеством 3D-движков и библиотек, которые намного лучше протестированы и оптимизированы, чем все, что вы могли придумать, нет причин, по которым какой-либо разумный разработчик мог бы оправдать написание собственного собственного движка.

Если…

Предположим, вы можете вернуться на машине времени в 90-е годы, время до OpenGL и DirectX, до графических процессоров. Все, что у вас было, это процессор и экран, полный пикселей, и вам приходилось писать все с нуля.

Если это ваше представление о развлечениях, вы не одиноки: это именно то, что вы можете делать с фэнтезийной консолью, такой как TIC-80.

После того, как я написал 8-bit panda, свою первую игру для этой консоли (вы можете прочитать об этом в моей предыдущей статье), я стал искать идею для новой игры. Поэтому я решил с нуля написать простой 3D-движок и сделать на его основе минималистичный шутер от первого лица.

Так я начал писать FPS80.

В этой статье я опишу, как работает 3D-рендеринг в FPS80, и немного расскажу обо всех компромиссах производительности (и многочисленных ужасных хитростях!) Для реализации быстрого 3D-рендеринга на этой ограниченной машине.

Основы 3D графики

Если вы уже знаете, как работает 3D-рендеринг, этот раздел будет скучным. Не стесняйтесь переходить к следующему разделу!

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

Фундаментальная идея трехмерной графики - отображение трехмерного пространства на двумерной поверхности (на вашем экране). Другими словами, одна из самых простых вещей, которую должен сделать 3D-движок, - это найти по координатам (x, y, z) точки в пространстве 2D-координаты (x , y) там, где эта точка должна быть на экране.

Для этого 3D-движки используют серию преобразований. Преобразование - это просто причудливый способ сказать «отображение одной системы координат в другую». Они могут представлять движение (перемещение, вращение, масштаб) и проекцию. Обычно они представлены матрицами.

Чтобы вычислить положение точки на экране, мы сначала преобразуем ее по матрице модели M, которая переносит ее в мировое пространство. Затем мы умножаем его на матрицу обзора V, чтобы учесть положение камеры, которое переводит ее в пространство камеры (или глаза). После этого мы применяем матрицу проекции P, которая выполняет перспективное преобразование, ответственное за то, чтобы более близкие объекты выглядели больше, а удаленные объекты - меньше. После этого идет разделение перспективы, которое приводит нас к фактическим координатам экрана (области просмотра):

p’ = P * V * M * p

Применение этой последовательности операций к точке часто называют «проецированием» точки. Но сцены состоят из объектов, а не точек, так что это еще не все, что делает 3D-движок.

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

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

Нужен ли нам полный 3D?

На самом деле я начал реализовывать полный рабочий процесс для 3D-графики, описанный выше, но понял, что на TIC-80 это будет слишком медленно. Как и на старых компьютерах, математика и рисование могут легко утяжелить процессор и быстро замедлить игру. Я написал образец, который нарисовал всего 4 вращающихся куба с наложенной текстурой, и даже этого было достаточно, чтобы снизить частоту кадров ниже 10 кадров в секунду. Ясно, что переход в «полное 3D» не сработал. В частности, узким местом является скорость заполнения, то есть проблема не столько в математике для проецирования точек, сколько во времени, которое требуется, чтобы нарисовать на экране все пиксели последних треугольников, особенно когда вам приходится делать это несколько раз из-за того, что несколько полигонов занимают перекрывающиеся области экрана.

Но действительно ли нам нужно полное 3D? На самом деле, оказывается, что многие старые игры 90-х не поддерживают «полное 3D». Вместо этого они реализуют некоторые хитрые механизмы для ограничения графики, чтобы ее было проще и дешевле обрабатывать.

Итак, вот ограничения, которые я наложил:

  • Весь уровень плоский: ни лестниц, ни ям, ни балконов, ни вторых этажей, ни чего-то подобного. То есть пол и потолок находятся на фиксированной высоте.
  • Все стены одинаковой высоты, от пола до потолка. И все они непрозрачные.
  • Игрок может повернуться лицом в любом направлении, но не может наклонять голову вверх или вниз или наклонять ее вбок. Другими словами, камера имеет только одну степень свободы вращения: курс или рыскание.
  • Все объекты нарисованы как «рекламные щиты», то есть двухмерные изображения, нарисованные в трехмерном пространстве так, что они всегда обращены к камере.
  • Есть только точечные огни. Один из них всегда находится перед камерой (как ручной фонарик, который носит игрок). Другие могут быть созданы на короткое время для определенных эффектов, таких как взрывы.

Как эти ограничения нам помогают?

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

Давайте выделим стены разными цветами, чтобы было легче увидеть:

Как видите, на этом кадре 6 стен (дверь также является «стеной»), и все они аккуратно расположены рядом на экране: каждая координата X на экране соответствует ровно одной стене.

Это очень полезно для нас, потому что мы можем визуализировать стены в два этапа:

  • Выясните, какая стена должна закончиться по каждой координате X (другими словами, постройте карту от координат X до стен).
  • Выполните итерацию (только один раз!) По всем координатам X, нарисовав для каждой правильный кусок стены.

Для таких сущностей (объектов), как монстры, снаряды, колонны, фонтаны, деревья и т.п., мы будем использовать общую технику, называемую рекламным щитом. Вместо того, чтобы иметь реальный 3D-объект, представляющий сущность, мы просто нарисуем плоское 2D-изображение в 3D-позиции, например вырез из картона. Рисовать это тоже очень дешево.

Наша процедура проецирования

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

Помните, что формула такая:

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 экрана и содержит информацию о том, какой кусок стены будет там нарисован. Чтобы упростить задачу, мы будем называть это не «кусок стены шириной в 1 пиксель», а «кусок стены». Таким образом, каждая позиция в H-Buf дает информацию о том, какой срез стены будет нарисован в каждой координате X на экране:

  • стена (объект): ссылка на стену, которая будет нарисована на этом срезе.
  • z (float): координата z (глубина) этого фрагмента в экранном пространстве.
  • и многое другое… но еще не все!

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

  • Используйте функцию проецирования по его четырем углам, чтобы определить, где он находится на экране: слева x, справа x, слева вверху y, слева внизу y, справа вверху y, справа внизу y, слева z (глубина), справа 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 is 1-indexed (because 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  -- depth test.
   hbx.z,hbx.wall=z,w  -- write new depth and wall slice
  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 is 1-indexed
  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 кадров в секунду в простых сценах и значительно снижает их в более сложных.

Как решить эту проблему?

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

Делаем так:

  • На четных кадрах рисуйте только четные координаты X.
  • На нечетных кадрах рисуйте только координаты X с нечетными номерами.

Это также известно как рендеринг с чередованием. Это означает, что в каждом кадре мы визуализируем только 120x136 пикселей, а не все 240x136 пикселей. Мы не очищаем экран в каждом кадре, поэтому пиксели, которые мы не рисуем, остаются остатками предыдущего кадра.

Это вызывает некоторые видимые сбои, особенно при быстром движении, но на самом деле это работает для игры, а не против нее, придавая ей ощущение ретро-телевизора.

Вот что мы на самом деле визуализируем каждый кадр (по крайней мере, так он выглядел бы, если бы другие столбцы еще не были заполнены пикселями из последнего кадра):

Визуализация среза стены

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

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

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

Отображение объектов (войдите в буфер трафарета!)

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

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

Как добиться этого эффекта?

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

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

Здесь мы должны ввести новый буфер: буфер трафарета. При 3D-рендеринге буфер трафарета представляет собой 2D-поверхность размером с экран, которая указывает, где вы можете, а где нельзя рисовать. Это как фильтр. Каждый пиксель в буфере трафарета может быть включен, что означает «заблокирован, не рисовать», или «выключен», что означает «бесплатно, нарисуйте». В зависимости от реализации значения могут меняться, но в нашем коде мы используем «истина», чтобы означать «занят, не рисовать».

Когда что-то «читает трафарет», это означает, что перед отрисовкой оно проверяет, включен ли буфер трафарета в каждой позиции, и не будет выполнять рендеринг поверх существующего пикселя.

Когда что-то «пишет трафарет», это означает, что всякий раз, когда оно визуализирует что-то в заданной позиции экрана, оно записывает в буфер трафарета, чтобы указать, что эта позиция теперь заполнена и больше не должна отрисовываться.

Итак, вот что мы делаем. Перед мы отрисовываем стены, но после вычисляем H-Buf, мы рисуем объекты. Полная последовательность такова:

  1. Очистить буфер трафарета.
  2. Вычислить H-Buf.
  3. Визуализация объектов от ближнего до дальнего (трафарет чтения / записи, проверка глубины по H-Buf).
  4. Визуализируйте стены с помощью 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 цветов, так как же мы можем создавать световые эффекты, делая пиксели светлее или темнее?

Техника, которую я использовал, заключалась в создании 3 разных «оттенков», которые имеют 4 разных оттенка, переходя от темного к светлому. Эти оттенки можно модулировать, выбрав один из этих 4 оттенков каждого, плюс черный (цвет 0) для самого темного. В итоге мы получаем 3 «рампы»: серый, зеленый и коричневый:

clrM={
 -- Gray ramp
 {1,2,3,15},
 -- Green ramp
 {7,6,5,4},
 -- Brown ramp
 {8,9,10,11}
},

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

А что насчет промежуточных цветов?

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

Эффекты частиц

Чтобы дать игроку приятную визуальную обратную связь при победе над монстрами или взрыве объектов, мы используем простые эффекты частиц:

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

Заключение

В этой статье мы кратко рассмотрели, как работает рендеринг в FPS80. У меня не было опыта написания 3D-движков с нуля, поэтому я уверен, что мог бы сделать многое лучше, и мои объяснения, вероятно, ошибочны во многих аспектах. Пожалуйста, не стесняйтесь поправлять меня (пишите в твиттере).

Разработка моей собственной логики 3D-рендеринга была интересной и поучительной. Потребность выжать каждый бит производительности из алгоритмов была особенно забавной и дала мне (маленькое) окно в то, как это было при создании 3D-движков 90-х годов!

Исходный код FPS80 и движка рендеринга доступны на github. Пожалуйста, не стесняйтесь повторно использовать в своих проектах!