Изменения

[[Файл:triangle_cycle.png|150px|left]] Чтобы успешно применять данный метод, нужно уметь быстро сортировать объекты. К сожалению, это не всегда просто. Кроме того, порядок глубины не всегда существует: отношение "перед" может содержать циклы. Когда такое цикличное перекрытие происходит, объекты не могут быть корректно отсортированы. В таком случае мы должны разорвать циклы, разбив один или более объектов на части. (Картинка с примером)

Данную задачу можно элегантно решить при помощи техники '''двоичного разбиения пространства''' (англ. ''binary space partionpartitioning, BSP'').

{{TODO [[Файл:bsp_plane1.png| t = Картинка про прямые и про дерево}}300px]][[Файл:bsp_tree1.png|300px]]

Пусть <tex>S</tex> {{---}} множество объектов, для которого мы строим забиение разбиение в <tex>d</tex>-мерном пространстве.

Пусть <tex>v</tex> {{---}} какая-то вершина дерева, тогда обозначим за <tex>S(v)</tex> множество объектов (возможно пустое), хранимых в этой вершине.

**левый ребенок <tex>v</tex> является корнем BSP -дерева <tex>T^-</tex> на множестве объектов <tex>S^- = \{h_v^- \cap s \mid s \in S\}</tex>;**правый ребенок <tex>v</tex> является корнем BSP -дерева <tex>T^+</tex> на множестве объектов <tex>S^+ = \{h_v^+ \cap s \mid s \in S\}</tex>.

{{TODO [[Файл:bsp_plane2.png| t = Рисунок про соответсвие нодов и регионов}}300px]][[Файл:bsp_tree2.png|300px]]

Таким образом, серая область на рисунке соответствует региону <tex>l_1^+ \cap l_2^+ \cap l_3^+-</tex>.

| definition = В двухмерном двумерном случае для множества отрезков разбиение, в котором используются разбивающие прямые, проходящие через один из данных отрезков, называется '''авто-разбивающим''' (англ. ''auto-partition'').

Однако [[Файл:bsp_n2.png|130px]] Как видно из рисунка, размер авто-разбивающего дерева может быть не минимальным. Возможен случай, когда размер BSP-дерева может составлять <tex>\mathcal{O}(n^2) </tex>, где <tex> n = |S| </tex>.{{TODO | t = Картинка, когда может быть n^2}}

Заметим, что мы не рисуем объекты из <tex>S(v)</tex>, когда <tex>p_{view}</tex> лежит на разбивающей плоскости <tex>h_v</tex>, потому что они являются плоскими двумерными полигонаполигонами.

BSP-деревья интересны тем, что позволяют достичь быстрой реализации удаления скрытых поверхностей для отрисовки сцены (будь то симулятор полёта или персонаж в игре, осматривающий окружающий мир). Так как скорость {{---}} главная цель, следует упростить вид объектов рассматриваемого пейзажа, поэтому далее будем считать, что в 3D мы работаем только с многогранниками, грани которых уже [[Триангуляция полигонов (ушная + монотонная) | триангулированы]]. Таким образом множество <tex>S</tex> в трёхмерном пространстве будет состоять только из треугольников.

При решении задач Прежде чем переходить к задаче отрисовки сцены в трехмерном пространстве бывает полезно сначала рассмотреть трёхмерном случае, рассмотрим для простоты аналогичную задачу на плоскости, что мы и сделаем.

На вход алгоритму подается <tex>S = \{s_1, \ s_2, ... \ \dots , \ s_n\}</tex> {{---}} множество отрезков.

<code> '''BSPTree ''' 2D_BSP_tree(<tex>S</tex>): '''if ''' <tex>|S| <= \leqslant 1</tex> <tex>T \leftarrow</tex> new '''BSPTree'''(<tex>S</tex>) <font color="green">/* <tex>T</tex> будет листом, в котором хранится данное множество */</font> '''return ''' <tex>T</tex> '''else ''' <font color="green">/* используем <tex>l(s1s_1)</tex> как разбивающую прямую */</tex></font> <tex>S^+ \leftarrow \{s \cap l^+(s_1) : \mid s \in S\}</tex> <tex>T^+ \leftarrow</tex> 2D_BSP_tree(<tex>S^+</tex>) <tex>S^− - \leftarrow \{s \cap l^-(s_1) : \mid s \in S\}</tex> <tex>T^- \leftarrow</tex> 2D_BSP_tree(<tex>S^−-</tex>) <tex>S_v \leftarrow \{s \in S : \mid s \subset l(s_1)\}</tex> <tex>T \ leftarrow</tex> new '''BSPTree'''(<tex>S_v, \ T^-, \ T^+</tex>) <font color="green">// создаем BSP-дерево c корнем в вершине <tex>v</tex>, левым поддеревом <tex>T^−-</tex> и правым поддеревом <tex>T^+</tex> </font> <font color="green">// и множеством хранимых объектов <tex>S_v</tex></font> '''return ''' <tex>T</tex> </code>Данный алгоритм создает BSP-дерево для множества <tex>S</tex>, но как уже известно, оно не будет наименьшим в общем случае.

ПонятноНеобходимо придумать стратегию выбора прямой разбиения, а не просто брать <tex>l(s_1)</tex>. Возможным подходом является выбор отрезка <tex>s \in S</tex>, такого что алгоритм создает BSP-дерево для множества <tex>Sl(s)</tex>пересекает наименьшее число отрезков. Но такой жадный алгоритм работает не на всех конфигурациях отрезков. Кроме того, но будет ли оно наименьшим?поиск такого отрезка {{---}} занятие затратное.

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

Как и в других алгоритмах, когда нужно сделать сложный выбор, просто выберем случайно. Это означает, что для разбиения мы будем использовать рандомный отрезок. Для этого перед тем, как начинать построение дерева, расположим отрезки в <tex>S</texcode> случайном порядке.  '''void''' 2D_random_BSP_tree(<tex>S</tex>) : <tex>S \leftarrow </tex> random_permutation(<tex>S</tex>). <tex>T \leftarrow </tex> 2D_BSP_tree(<tex>S</tex>) '''return ''' <tex>T</tex></code>Перед тем, как анализировать рандомизированный алгоритм, отметим, что здесь возможна одна простая оптимизацияанализированием рандомизированного алгоритма рассмотрим одну простую оптимизацию.

[[Файл:bsp_free.png|300px|right]]Рассмотрим одну из таких поверхностей граней <tex>f</tex>. В <tex>S</tex> могут быть отрезки, которые полностью пересекают <tex>f</tex>. Выбор одного из таких отрезков для разбиения <tex>f</tex> не вызовет фрагментации других отрезков внутри <tex>f</tex>, так как данный отрезок исключается из дальнейшего рассмотрения. Назовем такое свободным разбиением.

Теперь оценим производительность алгоритма '''2D_random_BSP_tree'''. Для упрощения рассуждений будем анализировать версию без свободных разбиений (асимптотической разницы они не даютмежду ними нет). Начнем с анализа размера BSP-дерева, равного числу полученных фрагментов, которое зависит от сгенерированной перестановки отрезков. Некоторые перестановки могут породить маленькие деревья, а другие {{---}} большие.  [[Файл:bsp_three_segments.png|500px]]

| statement = Ожидаемое число фрагментов, сгенерированных алгоритмом '''2D_random_BSP_tree ''' есть <tex>\mathcal{O}(nlognn \log n)</tex>.

Пусть <tex>s_i</tex> {{---}} фиксированный отрезок из <tex>S</tex>. Проанализируем [[Математическое ожидание случайной величины | ожидаемое ]] количество отрезков, которые мы разрежем, когда <tex>l(s_i)</tex> будет добавлена алгоритмом как следующая разбивающая прямая.

Рассмотрим рисунок и постараемся понять , разрезается ли отрезок <tex>s_j</tex> при добавлении прямой <tex>l(s_i)</tex>, в зависимости от отрезков, которые разрезаны <tex>l(s_i)</tex>, но находятся между <tex>s_i</tex> и <tex>s_j</tex>.

[[Файл:bsp_dist.png|300px|right]] <tex>dist_\mathrm{s_idist}(s_i, s_j)</tex> = \left\{количество пересекаемых отрезков, если <tex>\begin{array}{llcl}|\{s\ \mathrm{between}\ s_i\ \mathrm{and}\ s_j \mid l(s_i) \cap s \ne \varnothing \}| & \mathrm{if}\ l(s_i)</tex> пересекает <tex>\cap s_j\ne \varnothing \\\infty & \mathrm{otherwise} \\\end{array}\right.</tex>; <tex>infinity</tex>, иначе}

Пусть <tex>k = dist_\mathrm{s_idist}(s_i, s_j)</tex> и <tex>s_{j_1}, \ s_{j_2}, ... \ \ldots , \ s_{j_k}</tex> {{---}} отрезки между <tex>s_i</tex> и <tex>s_j</tex>.

Какова Найдём вероятность того, что при добавлении <tex>l(s_i)</tex> разрежет <tex>s_j</tex>? . Чтобы это произошло, <tex>s_i</tex> должен быть рассмотрен перед <tex>s_j</tex> и перед любым из отрезков между <tex>s_i</tex> и <tex>s_j</tex>, иначе они бы защили защитили <tex>s_j</tex> от <tex>s_i</tex>. Другими словами, среди множества индексов <tex>\{i, \ j, \ j_1, ... \ \ldots , \ j_k\}</tex> индекс <tex>i</tex> должен быть наименьшим.

<tex>P(l(s_i)</tex> разрезает <tex>\cap s_j\ne \varnothing) <= \leqslant \genfrac{}{}{}{0}{1 / (}{k + 2)}</tex>

<tex>E(</tex>число разрезов, происходящих при добавлении <tex>s_i) \leqslant \sum\limits_{j \ne i} \genfrac{}{}{}{0}{1}{\mathrm{dist}(s_i, s_j) + 2} \leqslant 2 \cdot \sum\limits_{k=0}^{n - 2} \genfrac{}{}{}{0}{1}{k + 2} \leqslant 2 \ln n</tex>. По линейности ожиданий мы можем заключить, что ожидаемое число разрезов, вызванных добавлением всех отрезков составляет не более <tex>2nlogn2n\log n</tex>. Так как изначально даны <tex>n </tex> отрезков, ожидаемое число фрагментов ограничено <tex>n + 2nlogn2n\log n</tex>.

Мы показалиБыло показано, что ожидаемый размер BSP-дерева, построенного с помощью алгоритма '''2D_random_BSP_tree''', составляет <tex>n + 2nlogn2n\log n</tex>. Следовательно, мы доказали, что BSP-дерево размера <tex>n + 2nlogn2n\log n</tex> существует для любого множества <tex>n</tex> отрезков. Кроме того, хотя бы половина перестановок приводит к BSP-дереву размера <tex>n + 4nlogn4n\log n</tex>.

Теперь проанализируем время работы алгоритма. Понятно, что оно зависит от используемой перестановки, так что опять рассмотрим ожидаемое время работы. Нахождение рандомной перестановки занимает <tex>\mathcal{O}(n)</tex>при помощи [[Метод генерации случайной перестановки, алгоритм Фишера-Йетса |алгоритма Фишера-Йетса]]. Если проигнорировать время рекурсивных вызовов, то время работы алгоритма линейно от количества фрагментов в <tex>S</tex>. Это число не превышает <tex>n</tex>, так как становится меньше с каждым рекурсивным вызовом. Число рекурсивных вызовов ограничено количеством сгенерированных фрагментов, которое составляет <tex>\mathcal{O}(nlognn\log n)</tex>. Таким образом, время построения дерева составляет <tex>\mathcal{O}(n^2logn2\log n)</tex>.

| statement = В двумерном пространстве BSP-дерево размера <tex>\mathcal{O}(nlognn\log n)</tex> может быть построено за ожидаемое время <tex>\mathcal{O}(n^2logn2\log n)</tex>.

Описанный выше алгоритм легко распространяется обобщается на трёхмерное пространство. Как было упомянуто выше, мы считаем, что работаем в 3D с двухмерного пространства на трехмерноетриангуляцией граней многранников.

Пусть <tex>S</tex> {{---}} множество непересекающихся треугольков в <tex>\mathbb{R}^3</tex>.

На вход алгоритму подается множество треугольников <tex>S = \{t_1, \ t_2, ... \ \dots , \ t_n\}</tex>, заданных в трехмерном пространстве.  '''BSPTree''' 3D_BSP_tree(<tex>S</tex>): '''if''' <tex>|S| \leqslant 1</tex> <tex>T \leftarrow</tex> '''BSPTree'''(<tex>S</tex>) <font color="green">/* <tex>T</tex> будет листом, в котором хранится данное множество */</font> '''return''' <tex>T</tex> '''else''' <font color="green">/* используем <tex>h(t_1)</tex> как разбивающую плоскость */</font> <tex>S^+ \leftarrow \{t \cap h^+(t_1) \mid t \in S\}</tex> <tex>T^+ \leftarrow</tex> 3D_BSP_tree(<tex>S^+</tex>) <tex>S^- \leftarrow \{t \cap h^-(t_1) \mid t \in S\}</tex> <tex>T^- \leftarrow</tex> 3D_BSP_tree(<tex>S^-</tex>) <tex>S_v \leftarrow \{t \in S \mid t \subset h(t_1)\}</tex> <tex>T \leftarrow</tex> '''BSPTree'''(<tex>S_v,\ T^-,\ T^+</tex>) <font color="green">// создаем BSP-дерево c корнем в вершине <tex>v</tex>, левым поддеревом <tex>T^-</tex> и правым поддеревом <tex>T^+</tex> </font> <font color="green">// и множеством хранимых объектов <tex>S_v</tex></font> '''return''' <tex>T</tex> Размер полученного BSP-дерева снова зависит от порядка треугольников. Как и в двумерном случае, мы можем попытаться получить хороший ожидаемый размер дерева, переставив треугольники в случайном порядке. На практике это дает хорошие результаты.

BSPTree 3D_BSP_tree(<tex>S</tex>) if <tex>|S| <= 1</tex>= См. также == <tex>T \leftarrow</tex> new BSPTree(S) /* <tex>T</tex> будет листом, [[Перечисление точек в котором хранится данное множество произвольном прямоугольнике за n */ return <tex>T</tex> else /* используем <tex>hlog ^(t1d - 1)</tex> как разбивающую плоскость */ <tex>S^+ \leftarrow \{t \cap h^+n (t_1range tree) : t \in S\}</tex>]] <tex>T^+ \leftarrow</tex> 3D_BSP_tree* [[Дерево интервалов (<tex>S^+</tex>interval tree)и пересечение точки с множеством интервалов]] <tex>S^− \leftarrow \{t \cap h^-* [[Пересечение прямоугольника с множеством непересекающихся отрезков (t_1segment tree) : t \in S\}</tex>]]== Источники иформации == <tex>T^− \leftarrow </tex>3D_BSP_tree* Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf (<tex>S^−</tex>2000) <tex>S_v \leftarrow \{t \in S : t \subset h, Computational Geometry (t_12nd revised ed.)\}</tex> <tex>T \ leftarrow</tex> new BSPTree(S_v, T^Springer-Verlag, T^+) // создаем BSPISBN 3-540-65620-дерево c корнем в вершине <tex>v</tex>, левым поддеревом <tex>T^−</tex> и правым поддеревом <tex>T^+</tex> // и множеством хранимых объектов <tex>S_v</tex> return <tex>T</tex>0 Chapter 12: Binary Space Partition: pp.259–267.