Precomputed visibility in Quake’s first level. The camera location is shown in red.
Предварительно вычисленная видимость на первом уровне 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) мир делится на пространства, в которых может перемещаться виртуальная камера, и отверстия между ними. Пространства называются cellviewcellzonecluster  или sector, а отверстия — portals (порталами). Такое разбиение особенно полезно в архитектурных моделях, в которых чётко разделённые помещения соединены дверями или окнами. Подходит оно и для уровней видеоигр, действие которых в основном разворачиваются внутри помещений.

The floorplan of our example level with three hand-placed portals shown. Cells have the color of their entry portal. In this case also the cell where the camera lies is visible.
План примера уровня с тремя вручную расположенными порталами. Ячейки (cell) имеют цвет своего входного портала. В данном случае видима также ячейка, где находится камера.

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

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

This is how three portals could look in game. Portal openings are shown as colored polygons and their screenspace bounding boxes are in white. Objects have dashed bounding boxes. The star object is culled because it doesn’t overlap with the red portal.
Вот, как могут выглядеть в игре три портала. Отверстия порталов показаны цветными многоугольниками, а их ограничивающие прямоугольники в экранном пространстве — белым. Объекты имеют пунктирные ограничивающие прямоугольники. Объект-звезда отсечён, потому что не пересекается с красным порталом.

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

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

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

Quake’s first map viewed in the TrenchBroom map editor with portals shown in red. As you can see, not just doorways act as portals.
Первая карта Quake в редакторе карт TrenchBroom; красным показаны порталы. Как видите, порталами работают не только дверные проёмы.

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

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

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

The example map divided to convex leaves. Leaf colors are random.
Цвета листьев выбраны случайным образом.

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

Portals placed automatically by the bsp tool. This map is pretty much 2D but everything discussed works just fine in 3D too. Leaf indices are shown in white.
Порталы располагаются автоматически инструментом bsp. Эта карта практически двухмерная, но всё рассказанное здесь вполне действует и 3D. Белым показаны индексы листьев.

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

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

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

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

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

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

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

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

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

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

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

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

Leaves (nodes) connected by portals (edges) in a cell-and-portal graph.

Каждый портал — это трёхмерный многоугольник. Инструмент 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 портал выглядит так:

Each portal is stored as a convex polygon.

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

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

Each input portal is split into a so called forward (red) and backward (yellow) portal before processing. There’s a small gap here for demonstration purposes but actually they overlap. The arrows show the directions the portals can be seen through.
Перед обработкой каждый входной портал разделяется на так называемый передний (красный) и задний (жёлтый) порталы. На иллюстрации между ними есть небольшой зазор, но на самом деле они наложены друг на друга. Стрелки показывают направления, в которых можно смотреть через порталы.

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

Each portal is represented by two edges in the graph. The earlier forward and backwards portal edges are highlighted with red and gold, respectively.

Граф в коде

Настало время познакомиться с основными структурами данных 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, ведущая к этому листу. Линия видимости должна пересекать порталы в нужном направлении:

The fact that we can draw a sightline (the dashed arrow) first through portal A and then through B proves that it’s possible to see through both A and B at the same time.
То, что мы можем отрисовать линию видимости (пунктирная линия) сначала через портал A, а затем через портал B, доказывает, что можно одновременно смотреть через A и B.

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

Coplanar portals A and C in our example map. Any sightline through A can’t pass through C in the right direction. That’s why leaf 4 can’t possibly see leaf 5 through portals A and C.
Находящиеся на одной плоскости порталы A и C из нашего примера карты. Любая линия видимости через A не может пройти через C в нужном направлении. Поэтому лист 4 не может увидеть лист 5 через порталы A и C.

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

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

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

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

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

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

Failure cases for each of the three conditions. 1. Portal B is behind A, so A can’t see through it.  2. B is in front of A,, but A is not behind B.  3. Portals face each other.
Случае не удовлетворяющие всем трём условиям.1. Портал B позади A, поэтому A не может видеть через него 2. B находится впереди A, но A не находится позади B.3. Порталы смотрят друг на друга.

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

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

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

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

How coarse tests help during traversal.

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

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

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

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

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

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

  • Затем мы рассматриваем каждый портал листа 8CF и 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 (жёлтый), то листья позади оранжевого портала не должны рендериться:

Camera is in the yellow leaf looking to the right.
Камера находится в жёлтом листе и смотрит вправо.

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

Anything beyond the orange portal is hidden, as expected.

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

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

Комментарии (1)


  1. Jijiki
    26.01.2025 09:19

    получается рендерятся комнаты, которые видны, кубы кстати попроще вроде генерировать