Если ты читал мою предыдущую статью, то знаешь, что для рендеринга открытых пространств применяются quad-деревья, в этой статье я расскажу тебе о самом популярном способе рендеринга закрытых indoor-окружений (см. DOOM, Quake, Half-life и т.д.). Речь пойдет о BSP-деревьях.
BSP (Binary Space Partitioning) дерево - это рекурсивное бинарное деление пространства, которое позволяет быстро решить вопросы сортировки полигонов, удаления невидимых поверхностей, трассировки лучей и т.п. вообще, всего того, что доставляет ужасную головную боль при написании игрового движка.
Построение BSP-дерева
Проще всего объяснить принцип работы BSP-деревьев на конкретном примере, поэтому давай рассмотрим примитивный игровой уровень, состоящий из прямоугольной комнаты и трех стен в центре. Всего у нас будет семь плоскостей: сама комната из четырех стен (A, B, C, D) и три перегородки (E, F, G) внутри. Стоит отметить, что стены комнаты (A, B, C, D) - это односторонние поверхности, а перегородки (E, F, G) двухсторонние. Стороны, помеченные одним штрихом ('), назовем внешними, а двумя штрихами ('') внутренними.
Очевидно, что данная конструкция полностью укладывается в понятия двухмерного пространства, но ничего страшного в этом нет, для полного 3D все принципы будут действовать точно так же, просто сам процесс, в общем, немного усложнится.
Итак, построение BSP-дерева начинается с выбора секущей плоскости, которая станет корнем дерева. Мы начнем с плоскости F (вообще, взять можно любую другую плоскость, но есть несколько причин, о которых я скажу позже). Далее с помощью этой плоскости, мы разбиваем все пространство на две части (показано пунктиром), и записываем плоскости, которые лежат на внешней стороне от F, в левое поддерево, а плоскости лежащие на внутренней стороне, в правое. Заметь, что при этом, каждую плоскость, пересекающуюся с секущей, мы разбиваем на две части по линии сечения и относим эти части в разные поддеревья. Так из двух поверхностей B и D, мы сделали четыре: B1, B2, D1, D2. В результате получили следующее:
Теперь нам нужно провернуть подобное разбиение в каждом поддереве. Как видишь, в левом поддереве делить нечего, потому что там все плоскости лежат по одну сторону друг от друга, т.е. образуют выпуклую форму, а вот с правым поддеревом нужно еще повозится. Опять выбираем одну плоскость (из тех, что имеются в правом поддереве), например, E и делим по ней все пространство на две части, разбив при этом плоскость C. В левую ветвь, как и раньше, помещаем плоскости лежащие с внешней стороны от секущей, а в правую, плоскости лежащие на внутренней стороне.
И снова в левом поддереве разбивать нечего, а из правого выбираем плоскость G и делим пространство по ней. В результате мы имеем готовое BSP-дерево, следующего вида:
Рендеринг BSP-дерева
Как я уже сказал, BSP-деревья позволяют рисовать полигоны уже отсортированными, т.е. без применения z-буффера. Попробуем это сделать. Представь, что игрок стоит на той же карте, в месте, помеченном красным крестиком, и смотрит на Север. Начинаем обход по нашему дереву. Заходим в корень дерева и смотрим, на какой стороне секущей плоскости мы находимся: если на внешней, то идем по ПРАВОЙ ветке, ели на внутренней, то по ЛЕВОЙ. Идем влево, мы достигли вершины дерева (дальше развилок нету), поэтому записываем в наш блокнот (вместо буфера 🙂 все поверхности, хранящиеся в этом узле: A, B1, D1. Возвращаемся на один уровень назад (т.е. в корень) и записываем в блокнот плоскость, которая там находится, причем мы уже знаем, что находимся на внутренней стороне плоскости F, поэтому имеем: A, B1, D1, F''.
Причем, если бы мы смотрели на Юг, то не видели бы ни саму плоскость F, ни то, что перед ней, т.е. могли вообще не опускаться в левое поддерево.
Теперь идем по правой ветке, пришли в узел E. Идем в левое поддерево, записываем, что там было, теперь у нас в блокноте: A, B1, D1, F'', D2, C1.
Возвращаемся на один уровень и добавляем в блокнот внутреннюю сторону E''.
Идем вправо к узлу G, снова, сначала в левое поддерево, дальше развилок нет поэтому назад к G и потом вправо, в результате имеем: A, B1, D1, F'', D2, C1, E'', C3, B2, G'', C2.
Теперь представь, что мы будем рисовать плоскости в том порядке, в каком они перечислены в блокноте, видишь, они уже отсортированы.
Теперь, представь, что мы стоим на зеленом крестике и смотрим на Юг, обойдем дерево еще раз. Заходим в корень F, мы стоим на внешней стороне, поэтому идем в правое поддерево, зашли в узел E, стоим на внутренней стороне, поэтому идем в левое поддерево, это вершина, записываем в блокнот: D2, C1. Возвращаемся на один уровень, дописываем E'', идем вправо в узел G, стоим на внешней стороне, поэтому сначала вправо, в блокноте: D2, C1, E'', C2. Возвращаемся в G, записываем G', т.к. мы еще не ходили в левое поддерево, то идем и записываем, получили: D2, C1, E'', C2, G', C3, B2. Снова возвращаемся на один уровень, в узле G мы все обошли, возвращаемся еще на один уровень, в узле E мы также все уже обошли, еще на один уровень назад, записываем F'. В узле F мы не ходили влево, идем, записываем, получаем: D2, C1, E'', C2, G', C3, B2, F', A, D1, B1. Рисуем...
Оптимизация BSP-дерева
Проблема оптимизации BSP-дерева намного сложнее, чем может показаться на первый взгляд, и к ней следует подойти с особом вниманием и аккуратностью. Есть несколько способов оптимизации дерева при его построении. Нужно стремиться строить дерево как можно уравновешенней и короче, т.е. надо постараться выбрать такую секущую плоскость, чтобы она делила свое подпространство примерно на равное количество плоскостей и при этом, делала не слишком много разбиений, т.е. нужно избежать добавления большого количества лишних полигонов.
Первое, что приходит в голову - это полный перебор всевозможных вариантов BSP-деревьев, но это, к сожалению, не реально, т.к. для N-полигонального уровня существует N! возможных деревьев, т.е. для 20 полигонов мы получим девятнадцатизначное (!!!) число вариантов.
Поэтому, часто, секущей плоскостью просто выбирают ту плоскость, которая делает меньше всего разбиений.
Трассировка лучей
Тут все проще некуда. Допустим нам нужно оттрассировать отрезок прямой, идущий из точки p1 в точку p2. Заходим в дерево и проверяем: если обе точки лежат на внутренней стороне от секущей, то идем в правое поддерево, а про левое забываем, если обе на внешней, то идем в левое, а если точки лежат по разные стороны, то значит, секущая разбивает наш луч, трассировка завершена. Так, рекурсивно, движемся по дереву, и если достигли вершины, то проверим пересечение всех плоскостей, которые там хранились, с нашим отрезком.
Потенциально видимые пространства
Когда мы рассматривали рендеринг BSP-деревьев, то обходили дерево и записывали в блокнот поверхности, которые необходимо нарисовать. Разумеется, если бы у нас был здоровенный уровень из нескольких тысяч полигонов, то и рисовать нам пришлось бы огромное количество этих самых полигонов, но, само собой, совсем не обязательно, что все эти полигоны будут видны на экране, добрая половина из них может быть вообще загорожена какой-нибудь стеной. Чтобы избежать отрисовки загороженных полигонов, на этапе компиляции уровня строят PVS (Potentially Visible Set), т.е. набор потенциально видимых пространств, с помощью которого можно определить какие части геометрии уровня видны из того или иного места. Буквально, PVS - это граф, определяющий для каждой вершины BSP-дерева, видимость других вершин.
Давай-ка попробуем соорудить PVS для такого вот простенького уровня.
Чтобы сделать это, поместим весь уровень в невидимую коробку, зачем это надо узнаешь потом.
Теперь начинаем строить BSP-дерево. Как всегда, выбираем секущую плоскость и делим пространство на две части. При этом нашу большую коробку мы также разбиваем на две других коробки по выбранной секущей. Повторяем разбиение до тех пор, пока не будет построено целое BSP-дерево. В результате наша первоначальная коробка, огораживающая уровень, окажется разбитой на несколько других коробок. Причем в результате коробок будет столько же, сколько и вершин у построенного BSP-дерева, и каждая коробка будет огораживать свою вершину. Короче, мы разбили наш уровень на четыре части и получили четыре коробки.
Теперь каждую стенку каждой коробки мы должны разбить на части плоскостью (в 3D) или линией (2D) определяемой каждой стенкой каждой другой коробки, т.е. получаем кучу раздробленных стенок.
Теперь из всего этого "супового набора" нам нужно оставить только те стенки, которые являются общими для вершин BSP-дерева, т.е. для наших четырех областей.
В результате, у нас имеется набор, так называемых, порталов, которые связывают между собой участки уровня. Теперь можно легко построить
PVS.
Определим видимые пространства для первой области. Так как области 1 и 2 имеют общий портал, то их видимость относительно друг друга устанавливается однозначно. Область 3 так же может быть видна из области 1, т.к. портал 2, объединяющий 2-ю и 3-ю области, легко проецируется на портал 1, объединяющий области 1 и 2. А вот портал 3 нельзя спроецировать на портал 1, чтобы не пересечь какую-нибудь стену, поэтому область 4 ни в коем случае не будет видна из области 1. Для всех остальных областей видимость определяется точно так же.
Кажется, это все, что я хотел тебе сегодня рассказать. Если ты всерьез задумал написать игрушку, использующую BSP-деревья и PVS, то советую тебе покопаться в Квейковских исходниках, которые валяются в сети на каждом углу (например
ftp.idsoftware.com).
