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

а

б

Рис. 2. Выровненное по координатным осям BSP-дерево с расположением разделяющей плоскости в любом месте (а) и структура дерева (б).

Одна из стратегий разбиения ограничивающего параллелепипеда - разбиение по координатным осям: т.е. корень дерева всегда делится по оси x, его "дети" делятся по оси y, а "внуки" по оси z. Далее цикл повторяется. BSP-дерево, построенное с использованием этой стратегии разбиения, иногда называют (к)-дерево [4]. Другая стратегия заключается в нахождении наибольшей стороны параллелепипеда и разделении по ней. Предположим, что наибольшая сторона лежит вдоль оси y. Тогда разделяющая плоскость будет иметь вид y = d, где d - некоторая константа. Для выполнения условия сбалансированности дерева константа d должна выбираться таким образом, чтобы количество примитивов в обеих частях параллелепипеда было одинаковым. Это операция является ресурсоемкой, поэтому часто параллелепипед делится просто пополам.

Примером использования выровненного по осям BSP-дерева может служить решение задачи сортировки примитивов от ближнего к дальнему (front-to-back sorting). Такая задача может возникнуть при реализации алгоритма отсечения объектов, закрытых от виртуальной камеры другими объектами (occlusion culling). Предположим, что спуск по дереву начинают с узла N. Проверяется положение наблюдателя относительно разделяющей плоскости, соответствующей узлу N. Спуск по дереву продолжается в сторону, соответствующую позиции наблюдателя. Только после того как просмотрена половина поддерева узла N, необходимо переходить к спуску во вторую половину. В результате листья дерева будут просмотрены в порядке удаления от наблюдателя. Этим методом не решается задача полной сортировки примитивов, поскольку содержание листьев все еще остается несортированным, и один примитив может принадлежать нескольким листьям. Однако такая грубая сортировка часто бывает достаточна для решения многих задач. Если при спуске постоянно переходить на сторону, противоположную наблюдателю, получится сортировка от дальнего к ближнему (back-to-front sorting). Этот способ можно использовать при отображении полупрозрачных

примитивов. Таким же образом можно проверять пересечения луча со сценой и отсечение объемом видимости (frustum culling).

Выровненное по полигонам BSP-дерево

Создание выровненного по полигонам BSP-дерева происходит несколько по-иному [5 - 8]. В этом случае разделяющей плоскостью является некоторый полигон, содержащийся в сцене, т.е. в корневом узле дерева выбирается полигон и вся сцена делится на две части плоскостью, в которой лежит выбранный полигон. Любой полигон, пересекающий разделяющую плоскость, делится на две независимые части по линии пересечения. В каждом полупространстве выбирается полигон, снова разделяющий полупространство на две части. Следует отметить, что разделение двух полупространств происходит независимо, различными плоскостями. Далее процесс происходит рекурсивно. Создание эффективного, выровненного по полигонам BSP-дерева - процесс ресурсоемкий, поэтому дерево создается обычно один раз (рис. 3).

аб

Рис. 3. Выровненное по полигонам методом деления сцены плоскостью BSP-дерево (а),

справа представлена структура дерева (б).

В большинстве случаев необходимо создать сбалансированное дерево, т.е. чтобы глубина любых двух листьев различалась максимум на единицу. Совершенно несбалансированное дерево неэффективно. Примером может служить дерево, каждое разделение в котором делило пространство на пустое и содержащее все примитивы. Существует множество стратегий поиска полигона, разделение которым приведет к построению эффективного дерева. Одной из них является использование критерия наименьшего пересечения (least-crossing criteria) [6]. Суть этой стратегии заключается в следующем. Произвольно выбираются несколько полигонов. Для каждого их них определяется количество полигонов, пересекающих разделяющую плоскость. Выбирается тот, чья плоскость имеет наименьшее число пересечений. Эмпирически было доказано [6, 9], что для сцены из тысячи полигонов для получения хорошего дерева необходимо протестировать только пять. Тестирование более пяти полигонов лишь не намного улучшает результат. Естественно, что с увеличением числа полигонов в сцене число тестируемых полигонов тоже должно быть увеличено.

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

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

Октарное дерево (octree)

Термин octree (октарное дерево) в дословном переводе с английского означает дерево, получающенное в результате рекурсивного деления объемного пространства на восемь кубических субпространств.

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

Для построения октарного дерева необходимо найти выровненный по осям ограничивающий прямоугольный параллелепипед, содержащий всю сцену. Дальнейший алгоритм - рекурсивный и повторяется до тех пор, пока не будет выполнено одно из условий выхода из рекурсии. Этим условием может являться достижение максимального уровня рекурсии или минимального количества примитивов в узле [4, 10]. В случае остановки рекурсии узел становится листом и с ним связываются примитивы, лежащие внутри этого узла. В противном случае узел делится по координатным осям тремя плоскостями. Тем самым формируются восемь прямоугольных параллелепипедов одинакового размера. Каждый новый параллелепипед проверяется на условие завершения рекурсии и, если оно отрицательно, опять делится на восемь частей. В двумерном пространстве октарное дерево превращается в квадро-дерево (рис. 4).

б

а

в

г

Рис. 4. Построение квадро-дерева - двумерной версии октарного дерева.

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

Октарное дерево может быть использовано точно так же как и ориентированное по координатным осям BSP-дерево. Оно позволяет оптимизировать те же самые операции.

При описанном способе построения дерева возникают ситуации, при которых один объект должен соответствовать двум или более листьям. Как вариант, можно сопоставить объект с наименьшим узлом, в который он полностью помещается. Такой вариант имеет один веский недостаток. Объект, расположенный в центре октарного дерева, попадет в корень дерева. Это неэффективно, так как такой объект будет участвовать во всех