BSP процесс и видимость

Пара слов от себя:
Предлагаю перевод статьи, которую я в свое время (много-много лет назад) читал просто как откровение. Несмотря на то что много чего было понаписано с тех пор, она все еще актуальна (на мой взгляд). И возможно для кого-то приоткроет таинства bsp процесса, а так же станет ясно что это такое – портал и с чем его едят. На перевод статьи меня сподвиг один интернет спор. Мой оппонент утверждал, что Half-Life engine был сделан Valve полностью автономно, ну разве что купленные исходники Quake 1 слегка помогли. Читая данную статью, можно безболезненно заменять Quake 2 на Half-Life. А так же одно мнение на формуме, где говорилось, что HL – это дар божий, а Quake – так, яичница. Как говорится – думайте сами, решайте сами.


КАРТА

Для примера в этом туториале будем использовать карту, состоящую из 4 стен и 2 объектов в середине:



Будем использовать вид сверху:



Это двухмерное представление уровня. Линии соответствуют полигонам в трехмерной карте. Полигоны в 2D карте соответствуют брашам в 3D карте.


BSP процесс

Для упрощения давайте исключим двенадцать внешних полигонов (что случится в любом случае при BSP-разделении если карта не имеет утечек).



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

В течение BSP процесса qbsp3 берет каждый полигон один за другим и вставляет их в BSP дерево. Термином «дерево» описывается структура данных, где хранится информация о BSP узлах (BSP nodes). Если эту структуру представить в графическом виде получится что-то похожее на дерево или куст (BSP дерево определяет порядок отрисовки полигонов в игре). Как только полигон вставляется в дерево, пространство карты будет делиться на все меньшие и меньшие области, как показано ниже.



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

В реальности, qbsp3 использует определенные правила относительно порядка вставки полигонов. Во-первых, назначается высокий приоритет осевым полигонам (полигоны, параллельные осям x, y, z). Затем ищутся полигоны, которые будут разделять оставшиеся невставленные полигоны.

Синие толстые линии и черные тонкие лежат в плоскости, известной как плоскость разделения (split plane). Они (плоскости разделения) разбивают карту на маленькие (иногда не такие и маленькие) области. Каждая из этих областей - это bsp узел (bsp node). Движущиеся объекты, предметы и т.д. не являются частью bsp дерева и считаются отдельно.

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

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



Стрелками показано в какую сторону смотрит поверхность портала. Закрашенная область это узел к которому относится данный портал.

Когда полигон попадает между двумя узлами он разбивается на части так, что каждая из частей принадлежит соответствующему узлу. Однако позже qbsp3 попытается объеденить грани с идентичными свойствани если это возможно (так что вы можете иметь один полигон, присвоенный нескольким bsp узлам). Вы можете видеть проявление этого эффекта если включите gl_showtris (смотри обсуждение gl_showtris ниже).

Рисунок ниже это представление карты в Quake 2:



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

В отличии от qbsp3, который разбивает полигон на части и позже пытается объеденить их, q3map для Quake 3 оставляет полигоны целыми и не делает попыток объединить их позже. Общих эффект приблизительно тот же самый. Bsp дерево будет строится как обычно.


Узлы видимости (visibility nodes)

Давайте рассмотрим следующее возможное bsp разделение из примера выше.



Как уже сказано выше, каждая из белых областей это bsp узел. Bsp узлы используются также для определения видимости. Qvis3 анализирует bsp дерево и определяет, какие узлы видимы из других. Возьмем следующие 2 точки: одна наблюдатель, другая - точка на которую мы смотрим.



Как видно посредством проведения линии между ними (обозначена красным), две дочки невидимы друг для друга). Однако, с данным bsp разделением, qvis3 (а следовательно и Quake 2) считает, что они видимы друг для друга. Почему? Qvis3, когда проверяет видимость, проверяет каждый портал на предмет присутствия напротив других порталов. Если он находит два портала, котрые «видят» друг друга, тогда bsp узлы объявляются видимыми и соответственно все точки обзора, которые в них находятся видят друг друга. На следующем рисунке порталы, которые видят друг друга обозначены желтым.



Из этого, кстати, проистекает и злополучное предупреждение «leaf portals saw into leaf». Когда это случается, это значит, что qvis3 пытается сравнить на предмет видимости два портала, принадлежащие одному и тому же bsp узлу. Этим багом грешил оригинальный qbsp (да, я не оговорился, баг проистекает именно из qbsp3, а qvis3 только имеет с ним дело). Однако, большинство последующих версий qbsp3 благополучно от этого излечились.



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



Углы наклона чрезвычайно преувеличены. Пунктирная линия показывает как узел видит сам себя. В ситуации на рисунке данная ошибка безвредна. Есть еще несколько подобных ситуаций, когда вы можете видеть данное предупреждение. Если у вас пофиксенная qbsp3, можно об этом не беспокоится.

Если портал осевой, этого не будет случаться.


Проверка видимости

Итак, вы запустили вашу карту и хотите посмотреть как работает видимость или вы имеете проблемы со скоростью (низкий fps). Главный способ состоит в том, чтобы использовать OpenGL рендер с установкой gl_showtris 1 (3dfx минидрайвер не поддерживает ql_showtris). Взгляните на следующий вид уровня base64.



Теперь с установкой gl_showtris 1:



Это показывает нам, что Quake 2 верит (т.е. просчитывает) гораздо больше полигонов, чем видно на самом деле.

Если вы все еще не видите треугольники попробуйте сначала следующие команды:

gl_ext_multitexture 1
vid_restart

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


HINT браши

В данном случае bsp разделения есть только 4 пары узлов, невидимых друг для друга (они показаны ниже)



Здесь всего 21 возможная пара узлов и только 4 пары скрытых друг для друга. Это нехорошо. В оригинальном Quake мапперы шли на различные ухищрения, чтобы держать видимость (visibility) в разумных пределах. К счастью, Quake 2 дает нам инструмент, с которым мы сможем сами контролировать bsp разбиение (bsp split): hint-текстура. Что она делает? hint текстура искусственно вызывает bsp разбиение, несмотря на то, что она невидима. Другая особенность hint текстуры заключается в том, что qbsp3 не будет изменять порядок вставки полигонов, которые получились в результате разделения hint текстурой.

Hint текстура обычно используется совместно со skip текстурой, которая игнорируется при bsp разделении. Т.е. берется браш, покрывается skip текстурой, затем одной грани назначается hint текстура. Это приведет к созданию одного hint полигона, чего обычно достаточно. Однако вы можете использовать браш, полностью затекстуренный текстурой hint, но это сделает bsp разделение более сложным.

Для нашего примера, мы попробуем следующее расположение hint плоскостей.



В редакторе (в данном случае шот взят из Qeradiant), это будет выглядеть так:



Вставка показывает область в районе пересечения. Тут у нас 5 skip граней и 1 hint грань. Число hint брашей можно уменьшить, используя браши, в которых более чем одна hint грань, но в этом примере мы этого делать не будем.

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



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

Перед тем как все заработает как надо будут множество попыток и ошибок. Определение места помещения hint плоскостей подобно какому-то виду искусства. Например хорошее размещение hint плоскости показано ниже



Вы можете не позволить игре видеть далеко за угол, посредством размещения hint плоскости поперек угла.



В данном случае вы можете быть уверенны в том, что находясь в одном коридоре, вы не видите второй.

Вы должны следить за тем, чтобы hint браш соприкасался всеми ребрами с брашами, составляющими уровень. Иначе, разделение будет не там, где вы планировали и результат будет не тот, которого ждали.

Как уже было сказано, порталы, лежащие в одной плоскости, могут стать источниками проблем (кроме порталов параллельных осям). Мы уверенно полагаем, что узлы, помеченные одинаковыми буквами в предыдущем примере невидимы друг для друга, несмотря на то что их порталы лежат в одной плоскости, потому что это ОСЕВЫЕ плоскости. Но давайте взглянем на рисунок ниже.



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



Угол ошибки сильно преувеличен. Когда искусственно создаем разделения в неосевой плоскости, одной hint плоскости может быть недостаточно. В этом случае вы можете использовать hint браш у которого hint текстура присвоена к двум противоположным граням, толщиной 8 или 16 юнитов, посередине которого расположен портал (в идеале).



На рисунке браш (желтый) имеет две грани с hint текстурой (тонкие красные линии), остальные грани имеют текстуру skip. Тонкая черная линия посередине – это оригинальный портал. Это исключит любую вышеописанную ошибку.

В добавок вы можете помещать hint браши там где вы хотите создать порталы не обращая внимания что браш идет через пустоту (void – имеется в виду пустота за пределами уровня) или твердую геометрию. Смотри пример с помещением hint браша через угол в коридоре – там hint браш пересекает твердую геометрию и создает два необходимых bsp – разделения.

Однако не следует забывать, что чрезмерное количество hint брашей сильно увеличивает время qvis3. Применяйте их только в случае проблем со скоростью. Часто геометрии уровня вполне достаточно, чтобы создать нормальное bsp разбиение. Так что не увлекайтесь.


Detail браши

Давайте возьмем нашу предыдущую карту и добавим в нее несколько маленьких брашей как показано ниже.



Как вы видите, число bsp узлов возросло с 7 до 13. Это увеличит время bsp вычисление почти в два раза, а объем информации о видимости увеличится в четыре раза. Однако новые браши практически не блокируют видимость, хотя делают информацию о видимости неоправданно сложной. В Quake 2 для этого случая есть подходящий инструмент: detail браш. В отличии от hint текстуры, которая применяется в выбранным граням, detail это свойство, которое применяется ко всему брашу целиком.

Посмотрим, что происходит с detail брашами. Во-первых, полигоны detail брашей вставляются в bsp дерево в последнюю очередь. Во-вторых, при вставке таких полигонов не происходит создание порталов, и результирующие bsp узлы будут на самом деле одним узлом. Давайте присвоим добавленным брашам свойство detail. В конечном итоге получим что-то вроде этого:



Пунктиром показаны bsp разделения, не содержащие порталов. Qvis3 считает закрашенную область одним узлом видимости в своих вычислениях. Это значительно упрощает и ускоряет qvis3 процесс. При определении, какие браши будут detail брашами, подумайте, какой вклад они вносят в информацию о видимости. Хорошими кандидатами будут, всевозможные мелочи, компьютерные терминалы и т.д.

Следите за тем, чтобы все грани браша имели свойство detail, имаче получите предупреждение о смешанном содержимом.

Detail браши в Quake 3 работают немного по другому. Они используются в аналогичных ситуациях, однако при bsp просчете их невидимые грани не удаляются в результате CSG операций и надо делать это вручную путем присвоения невидимым граням текстуры "caulk” , чтобы избежать лишних перерисовок в игре.