Введение в BSP деревья или BSP для самых «маленьких». Часть первая, теоретическая. (2 стр)
Автор: Антон В. Звягинцев
Строим дерево на примерах
Так как проще всего информация воспринимается именно на примерах, рассмотрим простейший пример создания такого дерева. Поскольку генерация BSP дерева в двумерном пространстве ничем не отличается от генерации BSP дерева в трехмерном, в примерах мы рассмотрим именно «двумерный случай», хотя терминология будет соответствовать трем измерениям.
На рисунке 1 представлен «типичный игровой» уровень. Вид сверху. Красная точка — положение игрока или камеры в сцене. В данном случае нам не важна его ориентация (направление «взгляда камеры»). Синим обозначены стены и направление их нормалей. В нашем «двумерном» мире нас не интересует высота этих стен просто потому, что у нас нет высоты :) Начнем...
В основе построения BSP дерева лежит разбиение пространства плоскостью, на которой расположен тот или иной полигон. Опять же, для простоты примем еще одно допущение - каждая из наших "стен" на рисунке 1 представляет собой единый полигон. В качестве первого разделителя возьмем полигон b. Перед плоскостью, на которой лежит наш новоиспеченный сплиттер (далее по тексту я буду звать "разделяющий" полигон или кандидата в таковой именно так), находятся полигоны d и e. Полигон a располагается позади. Полигон c рассекается сплиттером.
Рассечение плоскостью сплиттера достаточно важный момент, позволяющий решить проблему, которая может возникать в простейших алгоритмах сортировки полигонов по глубине, например, в алгоритме художника. Алгоритм художника — простейший алгоритм, сортирующий полигоны в сцене по их удаленности. Однако, ситуация с двумя перекрывающимися полигонами, изображенная на рисунке 2, не может быть корректно решена этим алгоритмом.
Проблему с перекрывающимися полигонами ранее могли наблюдать любители авиа симуляторов уважаемой мною фирмы Digital Integration (Tornado, Ah-64 Apache, Mi-24 Hind и другие). В играх с программным рендерингом, например Hind, включив внешний вид на вертолет и немного повертев камеру, игрок мог порой наблюдать "наезд" шасси и некоторых других деталей вертолета на каркас даже тогда, когда эти детали, казалось бы, должны находиться позади каркаса.
Рассмотрим рисунок 3:
В результате первого разбиения пространства полигон c был рассечен плоскостью нашего сплиттера на два: c1 и c2. Оба полученных полигона унаследовали от предка направление. После первого рассечения пространства мы имеем два списка полигонов:
•расположенные перед плоскостью сплиттера: c2, d и e
•расположенные позади плоскости сплиттера: a и c1
Что же теперь? Как уже отметил для себя читатель, в качестве входных параметров для построения дерева служат полигоны (списки полигонов). После первого разбиения мы "убираем" полигон b из кандидатов для последующего разделения (удаляем полигон из входных параметров) пространства и заносим его в "узел" дерева. У тебя ведь есть представление о такой структуре данных как дерево? Если нет, попробуй забежать немного вперед и рассмотри рисунок 4. Надеюсь, мои рассуждения уже натолкнули тебя, читатель, на последующие действия, а именно: мы продолжаем разбивать пространство плоскостью полигона, выполнять все те действия, что мы выполнили до этого до тех пор, пока во входных параметрах у нас не останется полигонов. Но тут есть одно НО — после первого разбиения мы имеем уже целых два списка входных параметров. Ты наверняка уже догадался. Да, именно! Это те самые две группы полигонов, расположенные перед плоскостью сплиттера и позади него. Начнем с первой группы, в которую входят c2, d и e. В качестве претендента-сплиттера на дальнейший процесс разбиения я выбираю полигон c2 (Конечно же, кандидат в сплиттеры выбирается из самого списка).
Выбор оптимального полигона для разбиения пространства плоскостью, на которой он лежит, не случаен. В примере я использую эмпирический метод :) В дальнейшем мы поговорим о том, как выбрать наиболее подходящий сплиттер.
После второго разбиения пространства мы имеем следующую картину:
•расположенные перед плоскостью сплиттера: d
•расположенные позади плоскости сплиттера: e
Третье разбиение пространства мы выполним для входных параметров a и c1. Это второй набор полигонов, который возник у нас при первом разбиении пространства полигоном b. В качестве сплиттера я выберу a:
•расположенные перед плоскостью сплиттера: c1
•расположенные позади плоскости сплиттера: отсутствуют
Дальнейший процесс разбиения не должен вызвать у тебя каких-либо проблем, поэтому я опущу его. Мы рекурсивно продолжаем процесс разделения пространства с все возникающими новыми наборами входных параметров, продолжая строить дерево. В результате всех наших действий должно выйти дерево, графически представленное на рисунке 4. Это и есть BSP дерево.
По правую сторону от узлов на рисунке изображены дочерние сплиттеры, расположенные перед сплиттером-предком, по левую — позади него. В корневом узле располагается полигон b. Уфф! Мы это сделали! По сути, мы выполнили работу BSP компилятора, создающего bsp дерево из набора полигонов. Именно в его задачи входит построение дерева в пространстве, решение "конфликтных" ситуаций с перекрывающимися полигонами, полигонами, лежащими на одной плоскости, выбор оптимальной сплиттер-плоскости.
Довольно часто может возникнуть картина, когда несколько полигонов лежат на одной плоскости. В случае, если один из этих полигонов будет использоваться в качестве сплиттера, может возникнуть еще одна спорная ситуация. В данном случае она решается достаточно просто – полигоны, лежащие со сплиттером в одной плоскости, добавляются вместе со сплиттером в узел. Случай, когда полигоны лежат на одной плоскости, но их нормали противоположны, мы рассмотрим немного позже, когда будем рассматривать, собственно, процесс рендеринга и проектирования структур данных.
Оптимальный сплиттер и сбалансированное дерево
Выбор оптимального сплиттера — достаточно сложный вопрос. С одной стороны, в угоду процедуре рендеринга мы должны минимизировать количество «распиливания» полигонов плоскостью выбранного сплиттера, поскольку это увеличивает число полигонов в сцене, и соответственно полигонов, которые затем нужно отобразить. Во многих источниках именно минимизация количества полигонов и снижение количества узлов ставится во главу угла создания оптимального BSP дерева. В то же время возникает необходимость построения сбалансированного дерева. Под сбалансированным деревом подразумевается дерево, по возможности, с равным количеством узлов по обе стороны от корневого узла. Кроме того, это же правило справедливо и для узлов-потомков, т.к. они также являются корневыми узлами для своих потомков. Чем же чревата несбалансированность дерева? Дело в том, что при несбалансированном дереве частота кадров в разных участках игрового мира будет достаточно сильно "скакать". Отмечу, что классическое BSP дерево, используемое ТОЛЬКО для рендеринга без каких либо модификаций самого алгоритма, не будет этому подвержено, т.к. независимо от того, какую структуру имеет дерево, мы в любом случае должны его обойти целиком и отрисовать ВСЕ полигоны в мире. Совершенно иная ситуация складывается при усовершенствовании алгоритма или, скажем, использовании его для контроля столкновений в Solid BSP варианте, о котором подробнее мы поговорим позже. За счет того, что для проверки столкновения с полигоном в разных частях уровня мы должны будем опуститься на разную "глубину" по узлам дерева, в одной части уровня мы будем иметь частоту кадров, к примеру, 60+, а в другой его части менее 10. Слишком утрировано? Возможно, но проблема все же есть. Если бы мы использовали сбалансированное дерево, частота кадров была бы приблизительно постоянна и держалась бы, к примеру, около 30 кадров в секунду.
В целом, мы можем выбирать наилучший сплиттер не только исходя из критерия построения им сбалансированного дерева. Существует достаточно много рекомендаций и общих принципов, и я постараюсь рассмотреть большую их часть.
Наилучший результат достигается при помощи построения ВСЕХ возможных BSP деревьев на заданном входном количестве полигонов и выборе наиболее оптимального из построенных, исходя из наименьшего количества полученных узлов в дереве. Но, увы... При текущих вычислительных мощностях это просто нереально и очень долговременно. Речь, конечно, идет о среднего размера игровых уровнях (и более). Приходится использовать определенные упрощения. Общепринятым способом является последовательный проход по всем потенциальным сплиттер полигонам, и подсчете неких баллов. Причем, мы никоим образом не учитываем дальнейшие попытки разбиения с заново полученными двумя списками входных параметров, а значит, мы не можем гарантировать, что выбор именно этого, на данный момент "оптимального", исходя из наших вычислений, сплиттера, не окажет негативное влияние на построение дерева в дальнейшем. Перейдем к вычислениям. Вот одна из таких формул:
Score = abs(front – back)
В данном случае, front и back - количество полигонов по обе стороны от сплиттера. Front — перед сплиттером, back — позади него. Исходя из данной формулы, сплиттер с НАИМЕНЬШИМ количеством очков признается наиболее оптимальным. Тут мы пытаемся удовлетворить требование сбалансированности для данной глубины дерева.
Пойдем немного дальше. Предыдущая формула не учитывает того факта, что сплиттер может «разрезать» полигоны, которые он пересекает. Чтобы понизить количество таких «распиливаний» и понизить увеличение количества полигонов в уровне, мы усовершенствуем формулу, к примеру, следующим образом:
Score = abs(front – back) + (splits * 8)
Splits в этом примере — как раз количество этих самых распиливаний. Цифра восемь в данном случае является коэффициентом «веса». Условие выбора то же — полигон с наименьшим количеством очков будет признан лучшим сплиттером.
Займемся дальнейшим усовершенствованием? Мы забыли о полигонах лежащих на одной плоскости со сплиттером. Хорошо это или плохо — вопрос открытый, поэтому в формуле я ставлю знак ±:
Score = abs(front - back) + (splits * 8) ± coplanar
где coplanar — количество полигонов лежащих на одной плоскости с потенциальным сплиттером. Если использовать знак минус, сплиттер с большим количеством компланарных полигонов будет иметь больше шансов на «выигрыш».
Осталось лишь обобщить предложенную формулу до общего вида:
Score = w1*abs(front – back) + splits*w2 + coplanar*w3
где w1, w2 и w3 «вес» того или иного фактора. Кроме того, не стоит забывать, что «вес» может принимать и отрицательное значение (например: w3 = –1).
7 мая 2004 (Обновление: 6 июля 2009)