Итак, теперь у нас есть первая приблизительная оценка видимости листьев из порталов, хранящаяся в массиве mightsee каждого портала. Вычислять, что именно видно через последовательность порталов, сложно, поэтому мы вместо этих вычислений используем «консервативную» оценку. Она ни за что не скроет лист, который должен оставаться видимым.
«Это просто задача отсечения»
Свет внезапно выключается. Вы сидите в огромном конференц-зале. Кто-то включает проектор. На экране сам Майкл Абраш! Похоже, это знаменитый доклад Quake Postmortem с GDC 1997.
Он говорит о порталах.
Мы берём плоскости отсечения, ограничивающие максимальный объём видимого, и отсекаем их по всё более дальним порталам, пока они не пропадут
Затем он рисует вот такую схему:
Он рисует две линии, проходящие через противоположные грани двух порталов, и закрашивает область между линиями, находящуюся справа от второго портала:
Закрашенная область видима из первых двух порталов. Она становится плотнее. Далее он рисует две новые линии через грани второго и третьего порталов:
Лист, в который ведёт второй портал, помечен буквой P как видимый. Однако две закрашенные области не пересекаются, поэтому третий портал невидим из первого, и процесс завершается:
но верхнее пространство полностью исключено из нижнего пространства, поэтому мы не видим нижнего и оно не находится в potentially visible set, мы не проходим через этот портал и завершаем работу. Вот, практически, и всё.
Гром аплодисментов. Сидящий рядом с вами человек встаёт и начинает топать ногами от восхищения. Так, он что, поёт We Are the Champions?
Впрочем, достаточно. Вернёмся в настоящее.
Так неужели это всё? Майкл сказал, что «реализация чуть сложнее», но добавил, что «это всего лишь задача отсечения». Разберёмся, что это значит.
Отсечение по порталам в 2D
Фундаментальная идея заключается в построении объёма, который точно содержит все линии видимости, проходящие через последовательности порталов. Если портал находится вне объёма, то его нельзя увидеть через порталы в последовательности.
Отсечение происходит, когда портал видим только частично. Это показано на схеме ниже. Есть три портала: исходный портал начального листа, портал прохода, через который мы смотрим, и целевой портал, невидимость которого мы по возможности хотим доказать.
Как и на схемах выше, у нас есть две линии, проходящие через противоположные грани исходного и проходного портала. Через оба портала видна только жёлтая область, поэтому мы можем отсечь те части целевого портала, которые точно будут невидимыми.
Как показал выше Майкл Абраш, процесс продолжается, пока целевой портал полностью не будет усечён. Мы рассматриваем усечённый целевой портал как новый проходной портал и выбираем новый целевой портал дальше по графу.
Это аппроксимация. Мы никогда не тестируем видимость через более чем три портала, даже если на пути от исходного до целевого портала их больше. Три портала действительно становятся меньше из-за усечения, но всё равно есть ложноположительные срабатывания — линии видимости, которые на самом деле не проходят через каждый портал. Именно поэтому мы выполняем большое количество усечений, как будет показано ниже.
Как найти разделительные плоскости
В двухмерном случае достаточно было просто отрисовать линию через противоположные концы порталов. Очевидно, что два портала будут проходить по разным сторонам линии. В 3D всё сложнее, потому что мы должны генерировать плоскости вместо линий.
На диаграмме ниже показано, как это можно сделать. Сначала выбираем грань исходного портала (отрезок AB). Затем выбираем вершину проходного портала (C). Создаём плоскость по трём точкам A, B и C.
Плоскость должна поместить исходный и проходной портал по разные стороны. После размещения плоскости мы проверяем каждую точку проходного портала относительно плоскости. Ни одна из точек не должна находиться за плоскостью и хотя бы одна должна быть перед ней. Исходный портал будет находиться за ней, исходя из принципа построения.
Мы не знаем заранее, какие плоскости окажутся разделительными, так что нам нужно проверить каждую комбинацию грани и вершины двух порталов. Целевой портал усекается каждой найденной разделительной плоскостью. На схеме ниже показана ещё одна плоскость.
Иногда точка C может оказываться позади исходного портала. Это не ошибка, но может происходить, если проходной портал только частично находится перед исходным:
В этом случае достаточно сменить направление нормали плоскости.
Мы можем создать ещё больше разделительных плоскостей, если поменяем ролями исходный и проходной порталы. Теперь мы выбираем грань AB проходного портала и точку C исходного портала. Так как аргументы функции усечения поменялись местами, она будет некорректно, но согласованно ориентировать плоскость по направлению исходного портала. Возможно, вы уже догадались, к чему мы ведём.
Перед усечением есть ещё одна (опциональная) смена направления нормали плоскости.
Это может сбить с толку, но я объясню, как это работает.
Разделительные плоскости на Python
Ниже показан код. Два вложенных цикла for — главное изобретение алгоритма. По крайней мере, мне не удалось упоминаний этого в работе Теллера. Мой код на Python довольно близок к коду на C++ в ericw-tools. Аргумент otherside принимает значение true, когда исходный и проходной портал меняются местами.
# Выбор разделительной плоскости и усечение
def clip_to_separators(
first_poly: Winding,
first_plane: Plane,
second_poly: Winding,
clipped_poly: Winding,
otherside=False,
) -> Winding:
clipped = clipped_poly
for i in range(len(first_poly)):
j = (i + 1) % len(first_poly)
A = first_poly[i]
B = first_poly[j]
AB = B - A
# Пробуем другие точки C на втором портале
for k, C in enumerate(second_poly):
# Проверяем, на какой стороне первого портала находится точка C
d = first_plane.distance_to(C)
if d < -ON_EPSILON:
# Разделительная плоскость по определению должна иметь второй портал
# на своей передней части. Здесь C находится позади первого портала,
# так что это будет не так после выполнения ниже
# normal = cross(AB, AC)
# и нам придётся позже поменять направление нормали.
flip_towards_first = True
elif d > ON_EPSILON:
flip_towards_first = False
else:
continue # Точка C находится на плоскости первого многоугольника
AC = C - A
normal = np.cross(AB, AC)
mag = np.linalg.norm(normal)
if mag < ON_EPSILON:
continue # Порталы могут иметь общие вершины, так что плоскость отсутствует
normal /= mag
plane = Plane(normal, normal.dot(C))
if flip_towards_first:
plane = -plane
# Проверяем, является ли плоскость разделительной
if not test_if_points_in_front(second_poly, plane):
continue
# Флаг 'otherside' устанавливается, если исходный и проходной порталы поменялись местами.
# В таком случае second_poly == source_poly, поэтому нормаль плоскости направлена
# на исходный, а не на проходной портал!
# Ниже мы переворачиваем нормаль, чтобы усекалась нужная сторона.
if otherside:
plane = -plane
clipped = clip_winding(clipped, plane)
if not clipped:
return None
return clippedУсечение и исходного портала
Последним расширением нам также нужно усечь исходный портал. Целевой портал теперь используется в качестве исходного. Проходной портал остаётся тем же. В конечном итоге усечение выполняется в четырёх комбинациях, когда мы комбинируем это со сменой ролей исходного и проходного портала.
Уровень проверок |
Первый |
Второй |
Усечение |
|---|---|---|---|
1 |
Исходный |
Проходной |
Целевой |
2 |
Проходной |
Исходный |
Целевой |
3 |
Целевой |
Проходной |
Исходный |
4 |
Проходной |
Целевой |
Исходный |
Куча плоскостей и усечений! Но нам всё ещё нужно обработать всю первую карту Quake с помощью vis.py, потому что он очень медленный.
Соединяем всё вместе при помощи потока по порталам
Итак, что у нас пока есть:
мы создали граф с направленными порталами,
вычислили список потенциально видимых листьев для каждого портала
научились определять видимость через последовательность трёх порталов.
Всё почти готово! Мы объединим эти три ингредиента, чтобы получить окончательную видимость между листьями. Воспользуемся тем же способом, что и в проходе грубых расчётов: обходом в глубину из конечного листа портала, рекурсивно посещающим соседние листья через порталы. Только дополним это более точными проверками видимости.
После того, как все порталы готовы, каждый лист смотрит на свои порталы и добавляет все потенциально видимые листья из каждого в собственное PVS. И на этом мы закончили.
Рекурсивное усечение на примере
Подведём итог описанному ранее: у нас есть три портала (исходный, проходной и целевой) Исходный портал — первый из видимых, в нём начинается обход. Проходной портал представляет собой отверстие, которое точно видимо из исходного портала. Через два этих портала проверяется видимость целевого портала. Это выполняется отсечением.
Для каждого исходного портала проверяется множество возможных последовательностей порталов. Это непохоже грубый расчёт видимости, при котором было достаточно быстрой геометрической проверки. На этот раз видимость через всю последовательность порталов фиксируется в уменьшающемся проходном портале.
Ниже показан пошаговый разбор примера работы алгоритма. Порталы я пометил именами переменных, используемых в коде.
Усечение последовательности порталов
Движемся по порталам на Python
Как я и говорил, обход происходит так же, как в случае грубого расчёта видимости. Код выглядит примерно так:
# Упрощённый набросок кода полного расчёта видимости.
# Работать не будет!
# Вызывается один раз для каждого портала 'Ps'
def portal_flow(Ps: Portal):
# Функция рекурсивного посещения листьев
def leaf_flow(leafnum: int, mightsee: np.ndarray)
Ps.vis[leafnum] = True # Mark leaf visible
for pt in leaf.portals:
Pt = leaves[pt]
# Может ли предыдущий портал потенциально видеть целевой лист?
if not mightsee[Pt.leaf]:
continue
# [Выполняем усечение порталов]
# Если портал 'Pt' не был отсечён, выполняем рекурсию через него
if Pt is not None:
leaf_flow(...)
# Начинаем обход с конечного листа Ps
leaf_flow(Ps.leaf, Ps.mightsee)
# Вызываем для каждого портала
for prt in portals:
portal_flow(prt)
# Массив 'vis' каждого портала заполнен.Функция portal_flow начинает обход точно так же, как base_portal_flow делала это в грубом расчёте. Стек вызовов выглядит примерно так.
Результаты определения видимости зависят от всего обойденного на данный момент пути. Именно поэтому в наброске кода leaf_flow получает аргумент mightsee — отфильтрованный массив видимости листьев из порталов.
В начале mightsee содержит результат грубого расчёта видимости из исходного портала: листья, которые могут быть видимы из него. В процессе выполнения рекурсии массив становится всё меньше. Для показанного выше примера последовательности это выглядит так:
шаг лист mightsee (x = видимый)
---- ----- -------------------------
1. 8 [ x x x x x x x x . . . ]
2. 7 [ x x x x x x x . . . . ]
3. 6 [ x x x x x x . . . . . ]
4. 5 [ x x x . x . . . . . . ]
5. 3 [ x x x . . . . . . . . ]
1 2 3 4 5 6 7 8 9 1011 листОбратите внимание, что на последнем шаге в листе 3 мы не можем вернуться в лист 5 , потому что в mightsee он больше не помечен как видимый. Рекурсия может завершиться, только если массив станет настолько разреженным, что больше ни в какие порталы нельзя будет войти. Другой способ — полное отсечение портала.
Полная реализация
А вот код целиком. По сравнению с представленным выше наброском, здесь происходит больше усечения, фильтрация массива might и новая проверка раннего выхода для порталов, которые не ведут к листьям, которые мы ещё не видели.
# Рекурсивное отсечение порталов vis.py
# Распределяем матрицу видимости портал->лист
portal_vis = np.zeros((num_portals, num_leaves), dtype=bool)
# Назначаем каждому порталу строку в матрице
for pi, Pi in enumerate(portals):
Pi.vis = portal_vis[pi, :]
# Мы можем немного ускорить обработку, если будем знать, какие порталы
# уже достигли своей окончательной видимости
portal_done = np.zeros(num_portals, dtype=bool)
def portal_flow(ps: int, Ps: Portal):
def leaf_flow(
leafnum: int,
mightsee: np.ndarray,
src_poly: Winding,
pass_plane: Plane,
pass_poly: Union[Winding, None],
):
Ps.vis[leafnum] = True
# Проверяем каждый портал, ведущий из этого листа
for pt in leaves[leafnum].portals:
Pt = portals[pt] # Целевой портал-кандидат
# Может ли предыдущий портал потенциально видеть целевой лист?
if not mightsee[Pt.leaf]:
continue
# Используем массив окончательной видимости, если портал был обработан
if portal_done[pt]:
test = Pt.vis
else:
test = Pt.mightsee
# Отфильтровываем все листья, которые нельзя увидеть из предыдущих порталов
might = np.bitwise_and(mightsee, test)
# Пропускаем, если мы можем видеть только листья, которые уже точно видимы
if not any(np.bitwise_and(might, np.bitwise_not(Ps.vis))):
continue
# Усекаем целевой портал плоскостью исходного портала
if not (target_poly := clip_winding(Pt.winding, Ps.plane)):
continue
# Непосредственные соседи не требуют дополнительных проверок
if pass_poly is None:
leaf_flow(Pt.leaf, might, src_poly, Pt.plane, target_poly)
continue
# Убеждаемся, что целевой и исходный порталы находятся, соответственно, впереди и позади
# от проходного портала
if not (target_poly := clip_winding(target_poly, pass_plane)):
continue
if not (src_clipped := clip_winding(src_poly, -pass_plane)):
continue
# Усекаем целевой и исходный многоугольники разделительными плоскостями
if test_level > 0:
target_poly = clip_to_separators(
src_clipped, Ps.plane, pass_poly, target_poly)
if not target_poly:
continue
if test_level > 1:
target_poly = clip_to_separators(
pass_poly, pass_plane, src_clipped, target_poly, backside=True
)
if not target_poly:
continue
if test_level > 2:
src_clipped = clip_to_separators(
target_poly, Pt.plane, pass_poly, src_clipped)
if not src_clipped:
continue
if test_level > 3:
src_clipped = clip_to_separators(
pass_poly, pass_plane, target_poly, src_clipped, backside=True
)
if not src_clipped:
continue
# Если все проверки пройдены, то мы входим в лист позади портала 'Pt'.
# Старый целевой портал становится новым целевым. Список 'might'
# теперь ещё больше фильтруется. Многоугольники 'src_clipped' и 'target_poly'
# могут быть усечены и стать меньше.
leaf_flow(Pt.leaf, might, src_clipped, Pt.plane, target_poly)
leaf_flow(Ps.leaf, Ps.mightsee, Ps.winding, Ps.plane, None)
portal_done[ps] = TrueЭтот код непосредственно взят из vis.py с добавлением пары комментариев. В конечном итоге он оказался ненамного проще, чем исходная функция RecursiveLeafFlow.
Поначалу нас может обеспокоить то, что у графа есть петли, но обход может посетить листья много раз. На практике это не бывает проблемой, потому что постепенно уменьшающийся массив mightsee останавливает обход до того, как он застрянет в цикле.
Сначала обрабатываем более простые порталы
Теперь давайте поговорим о важной оптимизации производительности. Мы вызываем portal_flow для каждого портала по порядку «сложности». В этом случае «сложность» портала означает, как много листьев потенциально оказались видимы на этапе грубого расчёта. Порталы с малыми значениями обрабатываются первыми.
Это та часть приведённого выше кода, в которой используется строгий массив vis вместо более свободных результатов mightsee:
# Используем массив окончательной видимости, если портал был обработан
if portal_done[pt]:
test = Pt.vis
else:
test = Pt.mightsee
# Отфильтровываем все листья, которые нельзя увидеть из предыдущих порталов
might = np.bitwise_and(mightsee, test)В целом идея заключается в том, что порталы, ведущие к меньшим областям, должны обрабатываться раньше, чтобы бо́льшие области могли использовать их окончательные результаты для раннего выхода.
Видимость листьев через порталы
Каждый лист может видеть другие листья только через свои порталы. Поэтому potentially visible set листа — это объединение PVS исходящих из него порталов.
Ниже показана промежуточная матрица portal_vis. В ней символ x обозначает видимость.
Портал
1 . x x . x x x x . . x
2 x . . . . . . . . . .
3 . . x x x x x x . . x
4 x x . . . . . . . . .
5 . . . . x x x x x . x
6 x x x . . . . . . . .
7 . . . x . x x x . . x
8 . x x . . . . . . . .
9 . . . . . x x x . . .
10 . . x x . . . . . . .
11 . . . . . x x x x . x
12 x x x . x . . . . . .
13 . . . . . . x x x . x
14 x x x x x x . . . . .
15 . . . . . . . x x . x
16 x x x x x x x . . . .
17 . . . . . . . . . . x
18 x x x . x x x x . . .
19 . . . . . . . . x x .
20 . . x . x x x x . . .
21 . . . . . . . . . x x
22 . . . . . . . x x . .
23 . . . . . . . x . . x
24 . . . . . . . . x x .
1 2 3 4 5 6 7 8 91011 лист
Получившаяся видимость между листьями представлена квадратной булевой матрицей, которую я назвал final_vis:
лист
1 x x x . x x x x . . x
2 x x x x x x x x . . x
3 x x x x x x x x x . x
4 . x x x . x x x . . .
5 x x x . x x x x x . x
6 x x x x x x x x x . x
7 x x x x x x x x x . x
8 x x x x x x x x x x x
9 . . x . x x x x x x x
10 . . . . . . . x x x x
11 x x x . x x x x x x x
1 2 3 4 5 6 7 8 91011 лист
Окончательная матрица видимости между листьями.
Объединение множеств, представленных в виде булевых массивов или битовых векторов, можно выполнить логической операцией OR. Мы обходим в цикле строки portal_vis и выполняем OR результатов для каждого портала со строками каждого листа в массиве final_vis, записываемого в файл BSP.
# Вычисляем окончательную видимость для каждого листа
final_vis = np.zeros((num_leaves, num_leaves), dtype=bool)
for li, leaf in enumerate(leaves):
for pi in leaf.portals:
np.bitwise_or(final_vis[li], portal_vis[pi], out=final_vis[li])
final_vis[li, li] = True # leaf is visible to itselfВ игре
Инструмент vis записывает окончательную матрицу видимости между листьями напрямую в уже скомпилированный файл mapname.bsp. Код сериализации сначала упаковывает строки матрицы в последовательность битовых векторов, а затем сжимает каждый кодированием RLE, пропускающим повторяющиеся нулевые байты.
В игре распаковка выполняется по необходимости. Поэтому полная матрица никогда не загружается в память целиком.
Наслаждаемся результатами
Очень здорово наблюдать, как несколько порталов, загруженных в программу на Python
попадают в реальную игру!
Также я записал низкокачественное видео PVS примера карты. К сожалению, я пока не обработал карту E1M1 целиком при помощи vis.py, потому что это очень медленно.
Ускоряем код
Должен признать, что vis.py очень медленный. Можно внести ещё некоторые оптимизации.
Во-первых, добавить многопроцессорную обработку. То есть каждый портал будет обрабатываться параллельно. Это уже было сделано в исходном vis, работавшем на четырёхъядерном сервере DEC Alpha. На Python это можно сделать при помощи пула воркеров стандартной библиотеки и массива общей памяти, передаваемого как хранилище массивов numpy с помощью np.frombuffer
В файлах vis.cc и flow.cc ericw-tool мы можем найти и другие трюки:
Тесты ограничивающих сфер порталов, чтобы не проверять все их точки.
Ускорение фильтрации массивов mightsee. Время от времени во время обхода для определения точной видимости каждый портал тестируется с текущей последовательностью исходного-проходного порталов. Такой подход частично схож с более простыми PVS из Doom 3, о которых мы расскажем в следующем разделе.
Кэширование: в исходном коде игры усечение разделительными плоскостями повторно использует некоторые плоскости из предыдущих проверок. Не совсем понятно, как это работает.
В реализациях на C и C++ управление стеком рекурсии выполняется вручную. Однако я не уверен, будет ли это выгодно в коде на Python.
Оглядываясь назад
Благодаря предварительно вычисляемой видимости на картах Quake возможно стало разместить больше полигонов со стабильными частотами кадров. Это не устранило перерисовку полностью, но обеспечило её приемлемый уровень с минимальными затратами в среде исполнения.
Хотя в диссертации Сета Теллера за 1992 год уже был представлен способ генерации статической предварительно вычисленной видимости (и в работе Джона Эйри за 1990 год), в Quake он появился не сразу. Изначально разработчики решили, что BSP-дерево будет выполнять рендеринг спереди назад при помощи лучевого дерева, но в конечном итоге было выбрано разбиение мира на PVS и выполнение проверки коллизий. BSP-дерево можно обходить в порядке видимости, но это свойство вообще не требовалось, потому что рендерер линий сканирования в Quake всё равно ресолвил видимость собственным способом.
PVS долгое время использовались и в сиквелах Quake, а также в других сериях игр, например, в Half-Life и Counter-Strike. Даже сегодня можно вычислять нечто подобное в Unreal Engine 5.
PVS — хорошая идея?
С точки зрения рабочего процесса PVS неидеальны. Дизайнерам уровней всегда приходится ждать, прежде чем они увидят скорость работы карты в игре. Ещё им приходится думать о не относящихся к ним технических концепциях наподобие hint brush. Кроме того, инструменты Quake ожидают, что карта будет идеально герметичной, разделённой на внутреннюю и внешнюю части. Если это не так, то возникают ошибки с «протечками», из-за которых вычисление PVS завершается сбоями. Думаю, о них никто не ностальгирует.
С точки зрения маркетинга такой подход обеспечивает высокое качество графики. Очевидно, разработчики Quake хотели, чтобы игра стала хитом благодаря своим красивым 3D-мирам с наложенными текстурами. Стабильная частота кадров помогает продать эту иллюзию. Так как инженерная работа — это всегда поиск компромиссов, мирам пришлось быть статичными, а дизайнерам уровней — терпеливыми. Возможно, низкая скорость итераций сделала дизайн игры менее амбициозным, ухудшив продукт. Как бы то ни было, разработка игры сопровождалась проблемами, поэтому непонятно, улучшила ли бы ситуацию более высокая скорость компиляции карт.
Что, если мы будем вычислять PVS очень быстро?
Очевидно, в Doom 3 разработчики начали использовать размещаемые вручную порталы с тестированием в среде исполнения и PVS, создаваемые во время загрузки уровня. Проход грубого расчёта видимости схож с алгоритмом в Quake, но проход точного расчёта выполняется быстрее.
Сначала код предварительно вычисляет, какие порталы потенциально видимы через любую пару исходного и проходного порталов. В коде этот массив пар порталов называется passage; он вычисляется при помощи разделительных плоскостей и усечения, как в Quake. Когда настаёт время рекурсивной заливки графа порталов, никакого усечения уже не требуется. Вместо этого в массивах passage выполняется проверка того, можно ли увидеть целевой портал через текущий исходный и проходной портал. В процессе рекурсии множество потенциально видимых порталов становится разреженнее, как это было с массивом mightsee.
Весь процесс в целом выполняется очень быстро. Я поискал онлайн отладочные сообщения логов и нашёл результат за 2007 год для карты game/erebus1:
512 bytes passage memory used to build PVS
1 msec to calculate PVS
36 areas
60 portals
6 areas visible on average
288 bytes PVS dataВсего 60 порталов! Для сравнения: первая карта Quake содержит 3077 порталов. Миллисекундное ожидание в процессе загрузки лучше, чем часы во время компиляции карты. Разумеется, дизайнеры уровней теперь отвечают за размещение порталов и герметичность уровней.
Было бы очень любопытно узнать, как решение из Doom 3 работало бы в Quake. В сложных геометриях всё равно бы пришлось усекать множество порталов, здесь бы помогло PVS и уменьшение общего количества порталов. Это был бы отличный исследовательский ретро-проект. В конце статьи приведены релевантные ссылки на исходный код.
Итог
Лично для меня написание vis.py оказалось очень информативным процессом. Мне пришлось учиться работать с уравнениями плоскостей, считывать порталы и прокачать мои навыки отладки. Необходимость удобства чтения кода и его описания заставила меня сделать многие подробности более понятными, чего бы не случилось, если бы я просто читал какой-то код.
Надеюсь, эта серия статей была для вас полезной, вдохновляющей, а может, и увлекательной. Даже если вы не реализуете собственный vis, теперь вы будете понимать, откуда и почему он появился. Компьютерная графика была и остаётся отличной областью для изобретений.
Ресурсы для разработки
Репозиторий vis.py выложен на GitHub. Локальная копия: vis_py.zip.
TrenchBroom для редактирования уровней.
ericw-tools для компиляции карт.
Исходный код оригинала vis с комментариями Фабьена Санглара.
Black Book Майкла Абраша, главы 59–70
Видео: BSP Trees: The Magic Behind Collision Detection in Quake
Видео: Excerpt: Quake Postmortem - Optimizing Level Viewing (original)
Немного ссылок на реализации порталов и PVS в Doom 3. В коде используется термин area вместо leaf, потому что им обозначаются не всегда выпуклые ячейки.
Тестирование порталов в среде выполнения при помощи усечения. Прямоугольники экранного пространства отслеживаются только для «ножничных» тестов графического API.
Функция init PVS даёт общее представление о процессе.
Проход грубого расчёта PVS должен показаться вам знакомым.
Предварительное вычисление passage. Стоит отметить, что проходной портал называется целевым (target), а усекается портал
p.Поиск разделительных плоскостей при помощи алгоритма, описанного в начале этой статьи.
Ресолвинг окончательного PVS. В нём хранятся и видимые области, и порталы.
Данные карт и порталов
Ниже представлены две созданные мной тестовые карты. Обратите внимание, что в этих файлах индексация порталов и листьев начинается с нуля. В этой серии статей я использовал в схемах индексацию с единицы.
Пример карты
example.map для TrenchBroom
example.prt — экспортированные порталы
example.bsp — экспортированное BSP
Первые комнаты E1M1
Здесь я поломал скорость дверей, простите.
e1m1_opening.map для TrenchBroom
e1m1_opening.prt — экспортированные порталы
e1m1_opening.bsp — экспортированное BSP