Главная > Программирование > Программирование графики >

Основы использования BSPT в 3D играх

A1: (Dmitry Tjurev 2:5061/15.49)

Основы использования BSPT в 3d играх
для сортировки полигонов и объектов.

BSPT (Binary Space Partition Tree) - Дерево двоичного разбиения
пространства. Это тип структур данных часто используемый в современных
компьютерных играх, основанных на трёхмерной технологии. Области его
применения весьма разнообразны. Я расскажу о тех которые известны мне.
Буду рад, если кто-нибудь дополнит это описание.

Итак, трёхмерная технология. Она, как известно, основана на хранении
сцены в виде набора полигонов, "растянутых" по опорным точкам, заданным в 3d
пространстве. Прорисовка текущего кадра сводится к следующим этапам:

1. Определение подмножества полигонов, видимых в данный момент.
2. Приведение опорных точек в систему координат наблюдателя.
3. Проецирование опорных точек на плоскость экрана.
4. Сортировка видимых полигонов.
5. Прорисовка видимых полигонов.

В том или ином виде эти действия присутствуют в любой игре,
использующей трёхмерную технологию.
Остановимся подробнее на пункте номер 4, т.к. остальные не имеют
прямого отношения к рассматриваемому вопросу. Итак, сортировка полигонов. Её
выполняют в одном из двух порядков front-to-back (от наблюдателя) и
back-to-front (к наблюдателю). Порядок сортировки выбирается в зависимости
от механизма вывода полигонов. Например, в таких играх как DOOM, DUKE3D
используется порядок front-to-back. Это связано с тем, что вновь выводимые
полигоны отсекаются по тем, которые уже были выведены перед ними. В игре
QAUKE, насколько мне известно, используется обратный порядок вывода
полигонов - back-to-front. При таком стиле прорисовки новые полигоны
накладываются на уже отрисованные. Но и в первом и во втором случае для
определения порядка вывода используется BSPT. Здесь мы видим применение BSPT
в "лабиринтовой" графике, однако с равным успехом его можно использовать и
для небольших объектов. Например, для сортировки полигонов космического
корабля в лётном симуляторе. Однако, нужно подчеркнуть вот что. Объект в
рамках которого используется BSPT должен иметь статичную форму. Так
лабиринты имеют постоянную форму (динамические объекты внутри них
прорисовываются другими способами), космический корабль также не должен
менять форму на протяжении игры (изменение формы можно сделать заменой
объектов). Связано это с тем, что BSPT - это, так называемая,
предвычисленная структура, которая формируется на этапе создания игры.
Опять же, хочу подчеркнуть что вариантов использования BSPT множество,
и некоторые из них могут строить его динамически. Но здесь мы рассмотрим
лишь статический вариант BSPT, применяемый для определения порядка вывода
полигонов. Но довольно предисловий, перейдём к делу. Рассмотрим подробнее
что такое BSPT, как оно строится и используется. Рассматривать все примеры
будем на плоскости, но обобщение для трёхмерного случая никаких проблем не
вызывает.

Посмотрим на рисунок:

+-----+
+-----+

+---+
| |
+---+

На нём изображён наблюдатель (*) и два произвольных объекта. Зададимся
вопросом как определить порядок вывода этих двух объектов, чтобы при
прорисовке они правильно наложились один на другой (порядок "к
наблюдателю").

Проведём прямую так, чтобы она отделяла один объект от другого:

\ +-----+1
\ +-----+
\
2+---+ \
| | \
+---+ \

Объект 2 лежит в одной полуплоскости с наблюдателем, а объект 1 в
другой полуплоскости. И, заметьте, именно поэтому объект 1 _ни когда не
может_ экранировать объект 2. Наоборот - пожалуйста, а так - нет !
Попробуйте расположить объект 1 так чтобы он закрыл собой объект 2,
оставаясь при этом в другой полуплоскости. Это невозможно !

И тут мы подходим к свойству, которое лежит в основе всей концепции BSPT:

+======================================================================+
| Ни один из объектов, лежащих в полуплоскости где нет наблюдателя |
| не может экранировать ни одного объекта лежащего в полуплоскости |
| где находится наблюдатель. |
+======================================================================+

Очень важно понять это свойство. Подумайте немного, и вы поймёте что
так оно и есть на самом деле.
Теперь давайте подумаем как это свойство можно использовать. Перед нами
стоит задача отсортировать множество объектов так чтобы при прорисовке они
правильно наложились друг на друга. Что у нас уже есть ? Мы знаем, что если
провести прямую так, чтобы часть объектов осталась с одной стороны, а другая
часть - со второй стороны, то порядок вывода этих двух подмножеств понятен:
сначала нужно вывести все объекты, находящиеся в той полуплоскости где нет
наблюдателя, а потом все объекты из полуплоскости где есть наблюдатель.
Остаётся определить порядок вывода внутри каждого подмножества. Как это
сделать ? Ответ напрашивается сам собой. Нужно повторить то, что мы уже
делали - в каждом подмножестве провести новую прямую, разделяющую объекты
опять на две группы:

\ 2
3 \ +-----+ / Что мы тут имеем: сначала нужно вывести
+--+ \ +-----+ / подмножество {1,2}, затем {3,4}.
| | / \ / +--+ 1 В подмножестве {1,2} порядок: 2,1.
+--+/ +---+ \ | | В подмножестве {3,4} порядок: 3,4.
/ | | \ +--+
+---+ \ Итог сортировки: 2,1,3,4.
4 \
* Выводя объекты в таком порядке мы получим
корректное наложение их друг на друга.

Как теперь сформулировать всё это в общем виде, думаю, понятно. Те кто
имеет опыт программирования, наверняка, уже давно увидели классическую
рекурсию.
Итак рекурсивная формулировка: Если множество объектов разбить прямой
на два подмножества, то порядок вывода этих подмножеств зависит от того в
какой полуплоскости находится наблюдатель.
Проблема заключается в том, что в реальном времени производить такое
рекурсивное деление невозможно по причине медлительности процесса. Да,
собственно, это и не требуется. Эти разбиения можно произвести один раз,
заранее. Рассмотрим пример. Предположим, у нас имеется город объектами в
котором являются дома. И нужно исходя из положения наблюдателя определить
порядок вывода этих домов. В этом случае строится BSP дерево по уже
известному нам рекурсивному принципу: Выбирается прямая, разделяющая объекты
на две группы. У этой прямой помечаются стороны. Одна из них считается
лицевой, другая нелицевой (это необходимо для последующей организации
ссылок). В корень дерева поместим информацию об этой прямой. У корня два
потомка. Пусть к левому будут относиться все объекты, лежащие с лицевой
стороны от прямой, а к правому - с нелицевой. В каждом из этих подмножеств
снова выберем разделяющую прямую и сформируем узлы дерева второго уровня.
Повторим процесс до исчерпания объектов. В итоге получим двоичное дерево в
узлах которого будут разделительные прямые, а листьями его будут объекты.
Рассмотрим пример построения BSPT на рисунке, который мы уже использовали.

\+ 2 Имеем набор объектов. Проведём раздели-
3 \ +-----+ тельную прямую A. (лицевую сторону я
+--+ \ +-----+ обозначу плюсиком) Выбор лицевой стороны
| | \ +--+ 1 производится, в общем то, произвольно.
+--+ +---+ \ | | Главное один раз и навсегда это
| | \ +--+ зафиксировать. Поместим эту прямую
+---+ \ в корень будущего дерева:
4 \ A
A
/ \

Объекты 1 и 2 идут в лево (т.к. они с лицевой стороны), объекты 3 и 4
в право:

A
/ \
{1,2} {3,4}

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

\+ 2
3 \ +-----+ +/ B A
+--+ \ +-----+ / / \
| | / \ / +--+ 1 B C
+--+/ +---+ \ | | / \ / \
/+ | | \ +--+ 2 1 4 3
C +---+ \
4 \ A

Вот наше BSPT и готово. Разумеется, оно не единственно возможное для
данного рисунка- выбирая различные разделительные прямые и их ориентацию
можно получить совершенно различные BSPT.
Теперь о том как же собственно использовать построенное дерево. При
прорисовке кадра совершается обход BSPT в порядке право-корень-лево или
лево-корень-право в зависимости от того с лицевой стороны от прямой в
текущем узле или нет находится наблюдатель. В момент прохода листа дерева
осуществляется прорисовка соответствующего объекта.
Пример (* - наблюдатель):

Начинаем обход дерева с корня.
\+ 2 В корневом узле находится прямая А.
3 \ +-----+ +/ B Наблюдатель находится с лицевой стороны от
+--+ \ +-----+ / неё - значит в этом узле прядок: право-
| | / \ * / +--+ 1 корень-лево. Идём вправо. Узел с прямой С.
+--+/ +---+ \ | | Наблюдатель с лицевой стороны - порядок
/+ | | \ +--+ тот же. Идём вправо. Объект 3 - выводим
C +---+ \ его. Вернулись. Объект 4 - вывели.
4 \ A Вернулись. Спускаемся влево. Узел с
прямой В. Наблюдатель с лицевой стороны.
Выводим объект 1, и, наконец, последний объект 2.

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

/^\
|
|
---------------

и наблюдателя с вектором наблюдения

/\
/^\ /
| /
| *
---------------

Очевидно, что в этом случае наблюдатель никак не может видеть
поддерево, находящееся в нелицевой стороны от разделительной плоскости.
Правило тут такое: Если угол между вектором наблюдения и нормалью к
плоскости раздела (нормаль берётся с той стороны с которой находится
наблюдатель !) меньше 45 градусов, то поддерево, соответствующее
противоположной стороне плоскости раздела - невидимо, и при обходе может
быть отсечено. Угол 45 градусов взят для раствора пирамиды видимости 90
градусов, иначе его нужно будет изменить.

Вернуться в раздел "Программирование графики" - Обсудить эту статью на Форуме

Главная - Поиск по сайту - О проекте - Форум - Обратная связь