[Перевод] Порталы: как осуществляется расчёт видимости в Quake

Вы когда-нибудь хотели узнать, как работала предварительно вычисленная видимость в Quake? Я хотел, поэтому написал программу vis.py, воссоздающую этот алгоритм на Python. В этой статье представлена вся информация, необходимая для понимания vis, — инструмента, применявшегося в Quake, Half-Life и играх на Source Engine.

В процессе разработки Quake возникла проблема перерисовки (overdraw), то есть многократной записи одного и того же пикселя во время рендеринга кадра. Видимым остаётся лишь последний цвет, а все предыдущие записи оказываются лишней тратой ресурсов. Это плохо, если в вашей игре используется программный рендеринг, и так выжимающий последние соки из компьютера середины 90-х годов.

Как снизить объём перерисовки? Давайте начнём с высокоуровневого обзора возможных решений.

С перерисовкой помогает усечение по порталам

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

Frustum culling всё равно не до конца оптимизирует производительность. Многие объекты могут находиться в поле зрения камеры, но никак не влиять на пиксели готового изображения. Это не катастрофа с точки зрения производительности, если всё рендерится спереди вдаль. Здесь поможет ранний Z-тест (early z-testing) GPU. Однако на больших картах всё равно будет быстрее вообще не отправлять эти объекты на рендеринг.

Occlusion culling — это процесс отбрасывания объектов, которые алгоритм считает находящимися за другими объектами сцены. Его задача — отбросить максимальное количество перекрытых (occluded) объектов. Это необязательно, потому что мы всё равно получим корректное изображение благодаря Z-буферу. Существует несколько способов реализации этого процесса: иерархический Z-буфер, очереди перекрытия, усечение по порталам и потенциально видимые множества (potentially visible set, PVS). В этой статье мы поговорим о двух последних: порталах и PVS.

При усечении по порталам (portal culling) мир делится на пространства, в которых может перемещаться виртуальная камера, и отверстия между ними. Пространства называются cell, viewcell, zone, cluster  или sector, а отверстия — portals (порталами). Такое разбиение особенно полезно в архитектурных моделях, в которых чётко разделённые помещения соединены дверями или окнами. Подходит оно и для уровней видеоигр, действие которых в основном разворачиваются внутри помещений.

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

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

Движок Quake использует порталы, но только на этапе подготовки карт. Во время выполнения игры порталов не видно. Эта техника стала разновидностью PVS-методики Сета Теллера, представленной в его диссертации 1992 года, работавшей только со стенами, расположенными вдоль координатных осей.

Исчезновение порталов с карт Quake

Часто порталы вручную размещаются дизайнером уровней. Инструмент компиляции карт bsp из Quake располагает порталы автоматически, что удобно. К сожалению, их получается очень много!

Ячейки в Quake очень малы. Но ни один портал не тестируется в среде выполнения: у каждой ячейки есть заранее вычисленный список ячеек, которые из неё видны. Это Potentially Visible Set (PVS) ячейки.

Ячейка — это маленький выпуклый объём пространства, поэтому одно помещение обычно разбивается на несколько ячеек. Эти ячейки соответствуют листьям дерева двоичного разбиения пространства (binary space partitioning, BSP). BSP-дерево использовалось для разбиения карты на ячейки и порталы. Конкретный способ разбиения нам не важен, главное, что BSP упрощает нахождение ячейки, в которой находится камера в среде выполнения.

Так как мы перешли в наших исследованиях к Quake, в дальнейшем мы будем называть ячейку листом (leaf). Этот термин используется во всём исходном коде, редакторе уровней, сообщениях об ошибках и других ресурсах Quake. Но его значение остаётся тем же — это всего лишь выпуклая ячейка, соединённая с другими ячейками через порталы. Вот, как выглядят листья в нашем примере уровня:

Порталы привычно располагаются между листьями:

Ничто не мешает нам сгруппировать несколько листьев в более крупные ячейки с меньшим количеством порталов между ними. На самом деле, именно так сделано в Quake 2 с его «кластерами» (cluster) листьев.

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

Общее описание vis

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

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

Говоря простым языком, vis выполняет два рекурсивных обхода в глубину, за которым следует быстрый проход ресолвинга и запись результатов расчёта видимости в скомпилированный файл карт. Процесс состоит из трёх этапов:

1. Базовая видимость. Грубый расчёт видимости листьев через порталы.

2. Полная видимость. Уточнение грубых результатов отсечением порталов.

3. Ресолвинг. Объединяем результаты видимости листьев через порталы в структуру видимости листьев между собой.

Краткое визуальное описание можно посмотреть в отличном видео Мэттью Эрла о PVS игры Quake.

У порталов есть направленность

В системе порталов ячейки и порталы встроены в граф «ячейка-портал». Инструментарий работы с картами Quake следует этому паттерну, соединяя листья порталами, несмотря на то, что эта структура отсутствует в среде выполнения. Листья соединены порталами:

Каждый портал — это трёхмерный многоугольник. Инструмент bsp записывает их в текстовый файл с указанием кода версии, количества листьев и порталов, после чего построчно идут порталы. Это выглядит так:

PRT1
11
12
4 0 1 (880 -224 -8 ) (880 -272 -8 ) (880 -272 72 ) (880 -224 72 ) 
4 1 2 (832 -224 -8 ) (832 -272 -8 ) (832 -272 72 ) (832 -224 72 ) 
4 2 4 (768 -272 -8 ) (768 -320 -8 ) (768 -320 72 ) (768 -272 72 ) 
4 2 3 (768 -112 72 ) (768 -112 -8 ) (768 -160 -8 ) (768 -160 72 ) 
4 3 5 (720 -112 72 ) (720 -112 -8 ) (720 -160 -8 ) (720 -160 72 ) 
4 4 5 (720 -272 -8 ) (720 -320 -8 ) (720 -320 72 ) (720 -272 72 ) 
4 5 6 (640 -224 -8 ) (640 -288 -8 ) (640 -288 72 ) (640 -224 72 ) 
4 6 7 (592 -224 -8 ) (592 -288 -8 ) (592 -288 72 ) (592 -224 72 ) 
4 7 10 (384 -304 -8 ) (384 -368 -8 ) (384 -368 72 ) (384 -304 72 ) 
4 7 8 (384 -112 -8 ) (384 -176 -8 ) (384 -176 72 ) (384 -112 72 ) 
4 8 9 (240 -176 -8 ) (336 -176 -8 ) (336 -176 72 ) (240 -176 72 ) 
4 9 10 (240 -304 -8 ) (336 -304 -8 ) (336 -304 72 ) (240 -304 72 ) 

Каждый портал — это петля из 3D-точек:

┌ количество точек
│ 
▽      x    y    z   x     y    z    x    y   z     x    y   z
4 0 1 (880 -224 -8 ) (880 -272 -8 ) (880 -272 72 ) (880 -224 72 ) 
  △ △ 
  └─┴─ два листа, между которыми находится портал

Так как порталы — это интерфейсы между выпуклыми листьями, многоугольники тоже выпуклые. В 3D портал выглядит так:

Концептуально, каждый портал — это двустороннее отверстие. Можно смотреть через него в обоих направлениях. Однако удобнее сделать порталы направленными. Благодаря этому мы можем отслеживать то, что видно в разных направлениях. Мы добавляем каждому порталу вектор нормали, то есть направление, в котором можно смотреть через портал.

Тогда каждый входной портал превращается в два направленных портала:

У графа теперь возникают направленные рёбра:

Граф в коде

Настало время познакомиться с основными структурами данных vis.py — классами Portal и Leaf:

class Portal:
  winding: list[np.ndarray]   # 3D-точки многоугольника
  leaf: int                   # лист, в который ведёт этот портал
  plane: Plane                # точки нормали плоскости к конечному листу
  ...                         # (прочие атрибута класса пропущены)

class Leaf:
  portals: list[int]    # индексы порталов, ведущих из этого листа

Отметим, что лист хранит только индексы порталов, ведущих наружу. Граф хранится в двух глобальных массивах portals и leaves, в которых находятся объекты соответствующих типов. Так как доступ к графу выполняется и по индексам, и по прямым ссылкам на объекты, я придумал следующий стандарт наименований:

• pi — индекс портала, Pi — сам объект Pi = portals[pi]

• li — индекс листа, Li — сам объект Li = leaves[li].

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

Грубый базовый расчёт видимости

Теперь у нас есть направленный граф, где листья соединены порталами.

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

Я буду говорить, что портал A может «видеть» лист, если существует линия видимости через портал B, ведущая к этому листу. Линия видимости должна пересекать порталы в нужном направлении:

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

Для остальных порталов нам нужно выполнять проверки.

Портал A может иметь линию видимости через портал B, если как минимум выполняются следующие условия:

1. Многоугольник B имеет хотя бы одну точку перед A,

2. Многоугольник A имеет хотя бы одну точку позади B, и

3. A и B не смотрят напрямую друг на друга.

Все три условия проиллюстрированы ниже. Можно представить, как линия видимости проходит через A, и заметить, что она не может пройти через B вперёд.

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

Рекурсивная заливка с геометрическими проверками

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

Допустим, мы выполняем грубый расчёт видимости для портала A, ведущего в лист 9.

Грубый расчёт видимости для портала A:

• Сначала мы входим в лист 9 и помечаем его как видимый.

• Затем мы рассматриваем вход в два портала B и D листа 9:

  • B находится на одной плоскости с исходным порталом A, то есть тривиально проваливает грубую проверку 2. Пропускаем его.

  • D выглядит хорошо, поэтому рекурсия входит в лист 8.

• Лист 8 помечается как видимый.

• Затем мы рассматриваем каждый портал листа 8: C, F и G:

  • C ведёт обратно в видимый лист 9. Пропускаем его.

  • F находится позади исходного портала A (грубая проверка 1). См. пунктирную оранжевую линию. Пропускаем его.

  • G в той же ситуации, что и F. Пропускаем.

• Мы вернулись к листу 9, но больше не осталось порталов, в которые можно войти. Обход завершён.

Результаты для портала A: листья 9 и 8 могут быть видимыми. Здорово, что простыми геометрическими проверками мы можем скрыть остальную часть карты за порталом F.

Код грубого расчёта видимости

Вот, как описанный выше процесс выглядит на Python:

# Стандарт наименований:
# 'pi' - это индекс портала в глобальном массиве 'portals'
# 'Pi' - экземпляр объекта Portal

def base_portal_flow(pi: int) -> np.ndarray:
  mightsee = np.zeros(num_leaves, dtype=bool) # Массив результатов

  def simple_flood(leafnum: int):
    if mightsee[leafnum]:
      return

    # Портал 'pi' видит лист 'leafnum'
    mightsee[leafnum] = True

    # Выполняем три грубых проверки видимости pi->pk для каждого портала'pk'
    for pk in leaves[leafnum].portals:
      if portal_might_see_other(portals[pi], portals[pk]):
        simple_flood(portals[pk].leaf)

  # Начинаем поиск в глубину от целевого листа этого портала
  simple_flood(portals[pi].leaf)
  return mightsee

# Грубое вычисление видимости для всех порталов
for pi, Pi in enumerate(portals):
  Pi.mightsee[:] = base_portal_flow(pi)

Каждый портал имеет массив bool, в котором хранится информация о том, какие листья он может видеть:

class Portal:
  ...
  mightsee: np.ndarray  # массив bool для листьев, видимых согласно грубому расчёту
  ...                   # (другие атрибуты класса пропущены)

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

Каркасная модель подтверждает, что это правда:

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

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

 

Источник