BSP-дерево

Описание

Одной из важных задач вычислительной геометрии является визуализация объектов, когда точка обзора находится над плоскостью с 3D или 2D объектами. Определение местоположений объектов и их теней занимает много времени. Для удаления невидимых частей объектов существует простой, но длительный метод - алгоритм z-буфера. В направлении просмотра проводится ось z-координат, затем определяется, какие пиксели покрывают проекции объектов. Алгоритм хранит информацию об уже обработанных объектах в двух буферах: буфере кадра и z-буфере. В буфере кадра для каждого пикселя хранится информация об интенсивности объекта, отображаемого им на данный момент, то есть тот объект из обработанных ранее, который виден в данной области. В z-буфере для каждого пикселя хранится z-координата видимого на данный момент объекта, точнее, в нем хранится z-координату точки такого объекта. Предположим, что мы выбрали пиксель и преобразовываем объект. Если z-координата объекта в этом пикселе меньше, чем z-координата, хранимая в z-буфере, тогда новый объект лежит перед видимым на данный момент. Тогда запишем интенсивность нового объекта в буфер кадра, а его координату - в z-буфер. Если z-координата объекта в этом пикселе больше, чем z-координата, хранимая в z-буфере, то новый объект не видим, и буферы останутся без изменений. Алгоритм z-буфера легко реализовать, и он быстро работает. Поэтому именно этот метод используют чаще всего, но у него есть свои недостатки: Для хранения z-буфера требуется большое количество памяти, кроме того, требуется дополнительная проверка каждого пикселя, покрываемого объектом.

Алгоритм художника избегает дополнительных затрат, изначально сортируя объекты по расстоянию от них до точки обзора. Тогда объекты проверяются в так называемом порядке глубины, начиная от самого дальнего. В таком случае при проверке объекта уже не нужна проверка его z-координаты, мы всегда пишем интенсивность в буфер кадра. Значения, хранимые в буфере ранее просто перезаписываются. Чтобы успешно применять данный метод, нужно уметь быстро сортировать объекты. К сожалению, это не всегда просто. Кроме того, порядок глубины не всегда существует: отношение "перед" может содержать циклы. Когда такое цикличное перекрытие происходит, объекты не могут быть корректно отсортированы. В таком случае мы должны разорвать циклы, разбив один или более объектов на части. (Картинка с примером) Определение, какие объекты нужно разбить и где, затем сортировка их фрагментов - дорогой процесс, так как порядок зависит от положения точки обзора, и мы должны пересчитывать все при каждом ее смещении. Чтобы использовать этот алгоритм в реальной жизни, например, в симуляторе полета, мы должны предпосчитать сцену так, чтобы можно было быстро найти корректный порядок отображения объектов для любой точки обзора. Элегантная структура данных, которая позволяет это сделать - двоичное разбиение пространства (англ. binary dpace partition) или BSP-дерево.

Определение

Чтобы понять, что из себя представляет BSP-дерево, рассмотрим рисунок. На нем показано двоичное разбиение множества объектов на плоскости и дерево, которое этому разбиению соответствует. BSP строится с помощью рекурсивного разбиения плоскости прямыми: сначала l1, затем разбиваем полуплоскость выше l1 прямой l2, а ниже - прямой l3 и так далее. Прямые разбивают на фрагменты не только плоскость, но и объекты, расположенные на ней. Разбиение продолжается до тех пор, пока внутри каждого фрагмента плоскости окажется не более одного фрагмента объекта. Этот процесс можно представить с помощью двоичного дерева. Каждый лист дерева соответствует фейсу разбиения, в нем хранится фрагмент объекта, находящийся внутри этого фейса. Каждый узел дерева соответсвует разбивающей прямой, которая хранится в этом узле. Если сцене присутствуют 1D-объекты (отрезки), то они могут лежать на прямой разбиения, в таком случае соответсвующий узел хранит их в листьях.

Рассмотрим гиперплоскость h: a_1*x_1 + a_2*x_2 + ... + a_d*x_d + a_{d + 1} = 0. Пусть h^+ - положительная полуплоскость, а h^- - отрицательная: h^+ = {(x_1, x_2 ... x_d) : a_1*x_1 + a_2*x_2 + ... + a_d*x_d + a_{d + 1} > 0} h^- = {(x_1, x_2 ... x_d) : a_1*x_1 + a_2*x_2 + ... + a_d*x_d + a_{d + 1} < 0}

Пусть S - множество объектов, для которого мы строим забиение в d-мерном пространстве. Пусть v - какая-то вершина дерева, тогда обозначим S(v) множество объектов (возможно пустое), хранимых в этой вершине. BSP-дерево T для этого множества обектов обладает следующими свойствами:

• Если |S| <= 1, то T - лист. Фрагмент объекта в S, если он существует, хранится в этом листе.
• Если |S| > 1, то в корне дерева v хранится гиперплоскость h_v и множество S(v) объектов, которые полностью содержатся в h_v.

* левый ребенок v является корнем BSP дерева T^- на множестве объектов S^- = {h_v^- \пересечь s : s \in S} * правый ребенок v является корнем BSP дерева T^+ на множестве объектов S^+ = {h_v^+ \пересечь s : s \in S}

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

И еще рисунок про соответсвие нодов и регионов.

Листья BSP-дерева соответствуют фейсам, то есть мы можем каждой вершине v сопоставить полигональную область на плоскости, которая определяется как пересечение полуплоскостей h_mu^ромбик, где mu - предок v, а ромбик = {-, если v левый ребенок; +, если v правый ребенок} Корню дерева соответсвует все пространство. Таким образом, серая область на рисунке соответствует региону l_1^+ \пересечь l_2^+ \пересечь l_3^+.

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

BSP-деревья и алгоритм художника

Предположим, что мы построили BSP-дерево T для множества объектов S в трехмерном пространстве. Как нам следует использовать его, чтобы получить порядок глубины для алгоритма художника? Пусть p_view - точка обзора, и она лежит над разбивающей плоскостью, хранимой в корне T. Тогда ни один из объектов, лежащих под этой плоскостью, не может затемнить (мб перекрыть?) ни один из объектов, лежащих выше нее. Таким образом, мы можем безопасно показать фрагменты объектов из поддерева T^- до показа объектов из поддерва T^+. Порядок фрагментов объектов в поддеревьях определяется таким же способом.

painters_algorithm(T, pview)

Let ν be the root of T.
if ν is a leaf

then Scan-convert the object fragments in S(ν). else if pview in h+ν then painters_algorithm(T−, pview) Scan-convert the object fragments in S(ν). painters_algorithm(T+, pview) else if pview in h−ν then painters_algorithm(T+, pview) Scan-convert the object fragments in S(ν). painters_algorithm(T−, pview) else (∗ pview in hν ∗) painters_algorithm(T+, pview) painters_algorithm(T−, pview)

Заметим, что мы не рисуем полигоны из S(v), когда p_view лежит на разбивающей плоскости h_v, потому что полигоны являются плоскими двумерными объектами.

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

Построение BSP-дерева

При решении задач в трехмерном пространстве бывает полезно сначала рассмотреть задачу на плоскости, что мы и сделаем. Пусть S - множество из n непересекающихся отрезков на плоскости. Ограничимся авто-разбиением, рассматривая только прямые, содержащие один из отрезков. Пусть l(s) - прямая, содержащая отрезок s. На вход алгоритму подается S = {s1, s2, ... sn} - множество отрезков.

BSPTree 2D_BSP_tree(S) if |S| <= 1 then Create a tree T consisting of a single leaf node, where the set S is stored explicitly. return T else /* Use l(s1) as the splitting line */ S+ \leftarrow {s \пересечь l(s1)+ : s \in S}; T+ \leftarrow 2D_BSP_tree(S+); S− \leftarrow {s \пересечь l(s1)− : s ∈ S}; T− \leftarrow 2D_BSP_tree(S−); Create a BSP tree T with root node ν, left subtree T−, right subtree T+, and with S(ν) = {s \in S : s \subset l(s1)}. return T

Понятно, что алгоритм создает BSP-дерево для множества S, но будет ли оно наименьшим? Наверное, стоит тщательней выбирать прямую разбиения, а не просто брать l(s1). Возможным подходом является выбор отрезка s \in S, такого что l(s) пересекает наименьшее число отрезков. Но этот жадный алгоритм, работает не на всех конфигурациях отрезков. Кроме того, поиск такого отрезка - занятие затратное. Как и в других алгоритмах, когда нужно сделать сложный выбор, просто выберем случайно. Это означает, что для разбиения мы будем использовать рандомный отрезок. Для этого расположим отрезки в S случайном порядке перед тем, как начинать построение дерева.

2D_random_BSP_tree(S) Generate a random permutation S' = s1, . . . , sn of the set S. T \leftarrow 2D_BSP_tree(S�) return T

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

Теперь оценим производительность алгоритма 2D_random_BSP_tree. Для упрощения рассуждений будем анализировать версию без свободных разбиений (асимптотической разницы они не дают). Начнем с анализа размера BSP-дерева, равного числу полученных фрагментов, которое зависит от сгенерированной перестановки отрезков. Некоторые перестановки могут породить маленькие деревья, а другие - большие. В качестве примера рассмотрим три отрезка, изображенные на рисунке. Если они рассматриваются в порядке (a), то мы получаем пять фрагментов, если же в порядке (b) - то всего три фрагмента. Так как размер BSP-дерева зависит от сгенерированной перестановки, будем анализировать ожидаемый размер BSP-дерева - средний размер для всех n! перестановок.

Лемма. Ожидаемое число фрагментов, сгенерированных алгоритмом 2D_random_BSP_tree есть O(nlogn). Доказательство. Пусть s_i - фиксированный отрезок из S. Проанализируем ожидаемое количество отрезков, которые мы разрежем, когда l(s_i) будет добавлена алгоритмом как следующая разбивающая прямая. Рассмотрим рисунок и постараемся понять разрезается ли отрезок s_j при добавлении прямой l(s_i), в зависимости от отрезков, которые разрезаны l(s_i), но находятся между s_i и s_j. В частности, когда прямая, пересекающая такой отрезок, добавляется раньше l(s_i), она закрывает s_j от s_i. На рисунке (b) так происходит с отрезком s_3, который защищен отрезком s_1 от s_2. Эти размышления приводят нас к определению расстояния от какого-то отрезка до фиксированного отрезка s_i. dist_s_i(s_j) = {количество пересекаемых отрезков, если l(s_i) пересекает s_j; +inf, иначе} Для всех конечных расстояний до отрезка s_i может быть только два отрезка с одинаковым расстоянием - те, что лежат по разные стороны от s_i. Пусть k = dist_s_i(s_j) и s_j_1, s_j_2, ... s_j_k - отрезки между s_i и s_j. Какова вероятность того, что при добавлении l(s_i) разрежет s_j? Чтобы это произошло, s_i должен быть рассмотрен перед s_j и перед любым из отрезков между s_i и s_j, иначе они бы защили s_j от s_i. Другими словами, среди множества индексов {i, j, j_1, ... , j_k} i должен быть наименьшим. Так как отрезки расположены в случайном порядке, получаем: P(l(s_i) разрезает s_j) <= 1 / (k + 2) Так как существуют отрезки, которые не разрезаются l(s_i), но расширение которых защитит s_j, выше записано неравенство. Теперь мы можем ограничить ожидаемое число разрезов, происходящих при добавлении s_i: E(число разрезов, происходящих при добавлении s_i) <= sum(i != j, 1 / (k + 2)) <= 2 * sum(k=0..n - 2, 1/ (k + 2)) <= 2 * ln n. По линейности ожиданий мы можем заключить, что ожидаемое число разрезов, вызванных добавлением всех отрезков составляет не более 2nlogn. Так как изначально даны n отрезков, ожидаемое число фрагментов ограничено n + 2nlogn.

Мы показали, что ожидаемый размер BSP-дерева, построенного с помощью алгоритма 2D_random_BSP_tree, составляет n + 2nlogn. Следовательно, мы доказали, что BSP-дерево размера n + 2nlogn существует для любого множества n отрезков. Кроме того, хотя бы половина перестановок приводит к BSP-дереву размера n + 4nlogn. Мы можем использовать этот факт, чтобы найти дерево такого размера: после запуска алгоритма сравним размер дерева с данной оценкой, если он превышает оценку, просто построим BSP-дерево еще раз, но для новой перестановки. Ожидаемое число запусков равняется двум.

Теперь проанализируем время работы алгоритма. Понятно, что оно зависит от используемой перестановки, так что опять рассмотрим ожидаемое время работы. Нахождение рандомной перестановки занимает O(n). Если проигнорировать время рекурсивных вызовов, то время работы алгоритма линейно от количества фрагментов в S. Это число не превышает n, так как становится меньше с каждым рекурсивным вызовом. Число рекурсивных вызовов ограничено количеством сгенерированных фрагментов, которое составляет O(nlogn). Таким образом, время построения дерева составляет O(n^2logn).

Теорема. BSP-дерево размера O(nlogn) может быть построено за ожидаемое время O(n^2logn)

Описанный выше алгоритм легко распространяется с двухмерного пространства на трехмерное. Пусть S - множество непересекающихся треугольков в R^3. Снова ограничимся только авто-разбиениями, разбивая пространство плоскостями, содержащими какой-то из треугольников. Для треугольника t обозначим плоскость, содержащую его, как h(t). На вход алгоритму подается множество треугольников S = {t1, t2, . . . ,tn}, заданных в трехмерном пространстве.

BSPTree 3DBSP(S) if |S| <= 1 then Create a tree T consisting of a single leaf node, where the set S is stored explicitly. return T else /* Use h(t1) as the splitting plane. */ S+ \leftarrow {t \пересечь h(t1)+ : t ∈ S} T+ \leftarrow 3DBSP(S+) S− \leftarrow{t \пересечь h(t1)− : t ∈ S} T− \leftarrow 3DBSP(S−) Create a BSP tree T with root node ν, left subtree T−, right subtree T+, and with S(ν) = {t ∈ S : t ⊂ h(t1)}. return T

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