Порталы и Quake

Это первая часть серии «Демистификация PVS».

1. Порталы и Quake
2. Грубая базовая видимость
3. Хорошая видимость благодаря обрезке
4. Portal Flow объединяет все это (будет опубликовано)

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

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

Как уменьшить перерисовку? Начнем с очень общего обзора ландшафта решений.

Удаление порталов помогает при перерисовке

В 3D-играх рекомендуется уменьшить количество рисуемых объектов.

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

Отбраковка Frustum по-прежнему оставляет некоторую производительность под вопросом. Многие объекты могут по-прежнему находиться в поле зрения камеры, даже если они не добавляют пикселей в окончательное изображение. Это не катастрофа производительности, если все рендерится спереди назад. Здесь поможет раннее тестирование графического процессора. Тем не менее, в больших мирах было бы быстрее вообще не отправлять эти объекты на рендеринг.

Отсечение окклюзии — это процесс, в котором вы отбрасываете объекты, которые, по вашему мнению, лежат за другими объектами на сцене. Его цель – отбросить как можно больше закупоренный объекты, насколько это возможно. В этом нет особой необходимости, так как вы в любом случае получите правильное изображение благодаря z-буферу. Есть несколько способов сделать это, например, иерархический z-буфер, запросы окклюзии, отсечение порталов и потенциально видимые наборы (PVS). В этой статье я говорю о последних двух: порталах и ПВС.

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

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

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

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

Порталы на карте Quake исчезают

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

Видите ли, в Quake ячейки очень маленькие. Но ни один портал не тестируется во время выполнения. Вместо этого каждая ячейка получает заранее вычисленный список других ячеек, которые можно увидеть из нее. Это Потенциально видимый набор (PVS) для этой ячейки.

В Quake ячейка представляет собой небольшой выпуклый объем пространства, поэтому одна комната обычно делится на несколько ячеек. Эти ячейки соответствуют листьям дерева разделения двоичного пространства (BSP). Дерево BSP использовалось для разделения карты на ячейки и порталы. Однако для нас точный метод не имеет значения. Но BSP позволяет легко найти ячейку, в которой находится камера, во время выполнения.

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

Как и ожидалось, порталы появляются между листьями:

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

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

Общий обзор vis

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

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

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

1. Базовая видимость. Оцените приблизительную видимость от листа до портала.
2. Полная видимость. Уточните грубые результаты с помощью обрезки портала.
3. Решать. Объедините уточненные результаты перехода от портала к листу с окончательной видимостью между листами.

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

Порталы имеют направление

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

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

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 ) 

Каждый портал представляет собой цикл трехмерных точек:

┌ the number of points
│ 
▽      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 ) 
  △ △ 
  └─┴─ the two leaves the portal is in between

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

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

Теперь один входной портал становится двумя направленными порталами:

Поэтому вместо этого граф теперь будет иметь направленные ребра:

График в коде

Теперь пришло время представить основные структуры данных вис.py, Портал и Лист занятия:

class Portal:
  winding: list[np.ndarray]   # polygon's 3D points
  leaf: int                   # the leaf this portal leads to
  plane: Plane                # plane normal points to destination leaf
  ...                         # (other class attributes omitted)

class Leaf:
  portals: list[int]    # indices of portals leading away from this leaf

В следующая часть мы будем использовать график для быстрых проверок.

Я тоже думаю написать книгу. Зарегистрируйтесь здесь если вам интересно.