Когда с определением видимости вопрос был более или менее закрыт, встал вопрос о типе используемого дерева для отсечения видимости. Впрочем, на этот вопрос я уже много лет отвечаю однотипно - только BSP. Его объявили нежелательным примерно с 2002-го года, когда игровые движки начали постепенно уходить от брашей к полигональной геометрии, после чего мы увидели Doom3 и Half-Life 2, еще с использованием BSP-дерева, а так же все игры на UE3. В 2006-2007-м году вышли Сталкер и Кризис, в которых BSP-дерево уже не использовалось. На самом деле рекомендации по нежелательности использования BSP-дерева основаны на буквальном его способе использования, который применялся в Quake1. Когда абсолютно вся геометрия проходит сквозь дерево и каждый полигончик ложится точно на ноду. Дерево при этом получается чудовищно избыточным и его размер может запросто превышать размер геометрии, которую оно индексирует. Естественно, что такой подход вместо оптимизации, наоборот сделает только хуже. Однако уже с Quake2, Кармак ввёл понятие т.н. детальной геометрии, т.е такой, которая не участвует в разбиении дерева. На самом деле многое определялось еще и тем фактом, что для коллизии и нахождения видимости использовалось одно и тоже дерево, поэтому постоянно приходилось искать компромиссы. Очевидно, что для физики нам требуется, как раз точное дерево, позволяющее, быстро найти нужный полигон. А для рендеринга - наоборот, найти видимый лист и отправить на отрисовку его содержимое (обычное это большие VBO-мешы).

Второй немаловажный момент заключается в подготовке геометрии. Раньше считалось вполне достаточным пропустить её через дерево и геометрия считалась оптимизированной. Но, как вы понимаете, это условие еще соблюдалось для программного рендеринга, где рисовать следовало как можно меньше. Для аппаратного рендеринга нам нужно стремиться к уменьшению потока данных по PCIex шине. А если при этом и нарисуется что-то лишнее, это уже не так критично. Значит нам нужны большие DIP-ы и минимальное их кол-во. Впрочем, это правило сохраняется для любого современного 3D движка и любой 3D-артист об этом знает. Меньше DIP-ов - выше фпс.

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

1. в дерево вводятся дополнительные секущие плоскости, если размер ноды по одному из измерений превышает какой-то заданный лимит, как правило это 10-15 метров. Таким образом дерево легко адаптируется как к коридорам, так и к ландшафтам, превращаясь на открытых пространствах в подобие регулярной сетки.

2. видимую геометрию ни в коем случае нельзя разделять секущими плоскостями полученного дерева. То есть, в принципе, можно, но для неаксиальной геометрии с очень высокой вероятностью в ней появятся длинные тонкие щели и другие артефакты. К счастью, нам это и не требуется. Ведь полученное дерево используется только для определения видимости. Достаточно профильтровать все видимые полигоны в дерево, чтобы они "приклеились" к соответствующим листам в пространстве. Во время рендеринга, используя пирамиду отсечения, мы находим видимые листы и добавляем все поверхности из них на отрисовку. Правда в разных листах могут быть ссылки на одну и ту же геометрию, этот момент следует учитывать. Правда при таком подходе остаётся вопрос -а как же пространственно разделить геометрию, если мы не сделали этого при помощи дерева?

Используя регулярную сетку мы просто строим выпуклые примитивы наиболее простой формы, обычно кубы и добавляем в этот куб все поверхности, которые оказались в его объеме. Здесь важно понимать, что мы ничего не режем, если речь идёт о ландшафте, то геометрия, как правило, уже заранее претесселирована. Если же нет, то это легко сделать средствами самого компилятора. Поэтому у получившихся батчей будут "рваные" края, соответствующие треугольникам на границе, но нам ведь важно заботиться не о том, как выглядят единичные куски, а о неразрывности лайтмапы и TBN-пространства. Получившиеся батчи легко фильтруются в наше дерево. Вполне естественно, что пространственная сетка которой мы разделяли геометрию и шаг секущих плоскостей BSP-дерева необязательно совпадут. Но это в сущности не так уж и важно и практически не влияет на скорость рендеринга.

После вышеописанного, у вас может возникнуть ощущение, что BSP-дерево в этой схеме вообще лишнее, куда проще построить какое-нибудь BVH или Octree для тех же самых целей. Однако, вот тут у нас и выходит то, ради чего всё затевалось - определение видимости.

У BSP-дерева есть одна замечательная особенность - объем, полученный в листе, всегда будет выпуклым, я использовал это в своих первых экспериментах по построению коллизии, но эта тема для будущих статей. Так вот, благодаря этой особенности, мы можем превратить мир в очень грубое подобие кубиков, плотно соединённых между собой. В местах, где между кубиками нет геометрии, мы вставляем портал. И что характерно - генерация порталов создаёт иерархию, обратную иерархии дерева. Иными словами, из случайно взятого лифа, двигаясь вверх по нодам, к которым прилинкованы порталы, мы можем выйти в корень дерева. При условии, что нам на пути не встретится "opaque" - нода. Т.е. непрозрачная. Корневой узел так же является и outside, внешним. Если из внутренней геометрии уровня во внешнюю допущено небольшое окошко, то в этом месте будет создан портал и произойдет та самая утечка, хорошо знакомая левел-дизайнерам под движки, семейства Quake. Может возникнуть вопрос, так ли нужны эти утечки сейчас, в 2021-м году, когда практически все движки предоставляют возможность делать уровни на плоскости, висящей в бесконечности. Отвечу на это так: это простой и быстрый способ отсечения внешней невидимой геометрии, которая может составлять до 40% от общего кол-ва. И если для отрисовки это будет не слишком критично, то лайтмапперу работы уж точно прибавится.

Впрочем, XashNT позволяет создавать уровни, висящие в пространстве, но вам придётся окружить их гигантской коробкой-скайбоксом. Это фундаментальная особенность движка. Скайбокс не только делает уровень герметичным, но на его геометрию также проецируется небо, лайтмаппер ориентируется на его полигоны, при вычислении теней от солнца, т.е. обойтись без него не получится в принципе. У тех левел-дизайнеров, которые начинали создавать уровни еще под Quake1 само слово "скайбокс" имеет резко выраженную негативную коннотацию, поскольку в учебниках по левел-дизайну того времени учили избегать такого способа "затыкания" утечек в геометрии. Бояться не нужно. То что было актуальным в 95-м году теперь не имеет никакого значения. Впрочем, вы сами это увидите на практике, как немного поработаете с движком.

Но вернёмся к порталам. Отсечение невидимой геометрии это хорошо, но это не единственная цель их создания. В предидущей заметке я также упоминал о порталах, на сей раз - расставленных дизайнером. Собственно для определения видимости этих порталов и нужен весь этот механизм. Портальные брашы - это единственный тип геометрии, которая иссекается плоскостями дерева, поскольку мы заранее не можем предугадать, как именно дизайнер их расставит. В нормальном случае у нас получаются герметически закупоренные сектора внутри уровня. Каждый сектор получает свой порядковый номер и режет геометрию точно по границам своего уровня (в XashNT есть команда визуализации отдельных секторов и вы сможете посмотреть как они выглядят).

И вот для этих секторов уже и строится Potential Visible Set. Но поскольку сектора обычно очень большие (как правило это целое помещение или коридор), то PVS-матрица занимает очень мало место (менее одного килобайта) и строится очень быстро. Так же есть возможность точного отсечения невидимых секторов с использованием пирамиды видимости (к слову, этот подход использовался в Doom3), но я им пока что не воспользовался.

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

Впрочем на открытых пространствах отсечение чего-либо практически бесполезный расход процессорного времени и в дело вступают совершенно другие механизмы - например динамический уровень детализации. Но об этом - в следующий раз.