Изменения

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

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

== Определение Структура 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}}

<code> '''void''' painters_algorithm(<tex>T</tex>, <tex>p_{view}</tex>): <tex>v \leftarrow T.root</tex> '''if ''' <tex>v</tex> is a leaf{{---}} лист отрисовать фрагменты объектов из <tex>S(v)</tex>. '''else if ''' <tex>p_{view} \in h_v^+</tex> painters_algorithm(<tex>T^-</tex>, <tex>p_{view}</tex>) отрисовать фрагменты объектов из <tex>S(v)</tex>. painters_algorithm(<tex>T^+</tex>, <tex>p_{view}</tex>) '''else if ''' <tex>p_{view} \in h_v^-</tex> painters_algorithm(<tex>T^+</tex>, <tex>p_{view}</tex>) отрисовать фрагменты объектов из <tex>S(v)</tex>. painters_algorithm(<tex>T^-</tex>, <tex>p_{view}</tex>) '''else ''' <font color="green">/∗ <tex>p_{view} \in h_v</tex> ∗/</font> painters_algorithm(<tex>T^+</tex>, <tex>p_{view}</tex>) painters_algorithm(<tex>T^-</tex>, <tex>p_{view}</tex>)</code> Заметим, что мы не рисуем объекты из <tex>S(v)</tex>, когда <tex>p_{view}</tex> лежит на разбивающей плоскости <tex>h_v</tex>, потому что они являются плоскими двумерными полигонами. Эффективность данного алгоритма, как и любого другого алгоритма для BSP-деревьев, зависит от размера BSP-дерева. То есть необходимо выбирать разбивающие плоскости таким образом, чтобы фрагментация объектов была минимальной. BSP-деревья интересны тем, что позволяют достичь быстрой реализации удаления скрытых поверхностей для отрисовки сцены (будь то симулятор полёта или персонаж в игре, осматривающий окружающий мир). Так как скорость {{---}} главная цель, следует упростить вид объектов рассматриваемого пейзажа, поэтому далее будем считать, что в 3D мы работаем только с многогранниками, грани которых уже [[Триангуляция полигонов (ушная + монотонная) | триангулированы]]. Таким образом множество <tex>S</tex> в трёхмерном пространстве будет состоять только из треугольников. == Построение BSP-дерева ==Прежде чем переходить к задаче отрисовки сцены в трёхмерном случае, рассмотрим для простоты аналогичную задачу на плоскости. Пусть <tex>S</tex> {{---}} множество из <tex>n</tex> непересекающихся отрезков на плоскости. Ограничимся авто-разбиением, рассматривая только прямые, содержащие один из отрезков.  Пусть <tex>l(s)</tex> {{---}} прямая, содержащая отрезок <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> '''BSPTree'''(<tex>S</tex>) <font color="green">/* <tex>T</tex> будет листом, в котором хранится данное множество */</font> '''return''' <tex>T</tex> '''else''' <font color="green">/* используем <tex>l(s_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> '''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>, такого что <tex>l(s)</tex> пересекает наименьшее число отрезков. Но такой жадный алгоритм работает не на всех конфигурациях отрезков. Кроме того, поиск такого отрезка {{---}} занятие затратное. Как и в других алгоритмах, когда нужно сделать сложный выбор, сделаем рандомный выбор. Это означает, что для разбиения мы будем использовать случайно выбранный отрезок. Для этого перед тем, как начинать построение дерева, расположим отрезки в <tex>S</tex> случайном порядке.

Заметим, что мы не рисуем полигоны из<code> '''void''' 2D_random_BSP_tree(<tex>S</tex>): <tex>S \leftarrow </tex> random_permutation(v<tex>S</tex>) <tex>T \leftarrow </tex>, когда 2D_BSP_tree(<tex>p_{view}S</tex> лежит на разбивающей плоскости ) '''return''' <tex>h_vT</tex>, потому что полигоны являются плоскими двумерными объектами</code>Перед анализированием рандомизированного алгоритма рассмотрим одну простую оптимизацию.

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

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

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

== Построение Теперь оценим производительность алгоритма '''2D_random_BSP_tree'''. Для упрощения рассуждений будем анализировать версию без свободных разбиений (асимптотической разницы между ними нет). Начнем с анализа размера BSP-дерева ==, равного числу полученных фрагментов, которое зависит от сгенерированной перестановки отрезков. Некоторые перестановки могут породить маленькие деревья, а другие {{---}} большие.  [[Файл:bsp_three_segments.png|500px]] При решении задач В качестве примера рассмотрим три отрезка, изображенные на рисунке. Если они рассматриваются в трехмерном пространстве бывает полезно сначала рассмотреть задачу на плоскостипорядке (a), что то мы и сделаемполучаем пять фрагментов, если же в порядке (b) {{---}} то всего три фрагмента.Пусть S Так как размер BSP-дерева зависит от сгенерированной перестановки, будем анализировать ожидаемый размер BSP-дерева {{--- множество из }} средний размер для всех <tex>n непересекающихся отрезков на плоскости!</tex> перестановок. Ограничимся авто-разбиением {{Лемма| statement = Ожидаемое число фрагментов, рассматривая только прямые, содержащие один из отрезковсгенерированных алгоритмом '''2D_random_BSP_tree''' есть <tex>\mathcal{O}(n \log n)</tex>. |proof = Пусть <tex>s_i</tex> {{---}} фиксированный отрезок из <tex>S</tex>. Проанализируем [[Математическое ожидание случайной величины | ожидаемое]] количество отрезков, которые мы разрежем, когда <tex>l(ss_i) - </tex> будет добавлена алгоритмом как следующая разбивающая прямая. Рассмотрим рисунок и постараемся понять, содержащая разрезается ли отрезок s<tex>s_j</tex> при добавлении прямой <tex>l(s_i)</tex>, в зависимости от отрезков, которые разрезаны <tex>l(s_i)</tex>, но находятся между <tex>s_i</tex> и <tex>s_j</tex>.На вход алгоритму подается S = {s1В частности, когда прямая, пересекающая такой отрезок, s2добавляется раньше <tex>l(s_i)</tex>, она закрывает <tex>s_j</tex> от <tex>s_i</tex>.На рисунке (b) так происходит с отрезком <tex>s_3</tex>, который защищен отрезком <tex>s_1</tex> от <tex>s_2</tex>.. sn}  Эти размышления приводят нас к определению расстояния от какого- множество отрезковто отрезка до фиксированного отрезка <tex>s_i</tex>.

BSPTree 2D_BSP_tree(S)if [[Файл:bsp_dist.png|S300px| <= 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]]

Понятно<tex> \mathrm{dist}(s_i, что алгоритм создает BSP-дерево для множества S, но будет ли оно наименьшим?s_j) = \left\{\begin{array}{llcl}Наверное, стоит тщательней выбирать прямую разбиения, а не просто брать |\{s\ \mathrm{between}\ s_i\ \mathrm{and}\ s_j \mid l(s1s_i). Возможным подходом является выбор отрезка \cap s \in S, такого что ne \varnothing \}| & \mathrm{if}\ l(ss_i) пересекает наименьшее число отрезков.\cap s_j \ne \varnothing \\Но этот жадный алгоритм, работает не на всех конфигурациях отрезков. Кроме того, поиск такого отрезка - занятие затратное.\infty & \mathrm{otherwise} \\Как и в других алгоритмах, когда нужно сделать сложный выбор, просто выберем случайно. Это означает, что для разбиения мы будем использовать рандомный отрезок\end{array}\right.Для этого расположим отрезки в S случайном порядке перед тем, как начинать построение дерева.</tex>

2D_random_BSP_tree(S) Generate a random permutation S' = s1Для всех конечных расстояний до отрезка <tex>s_i</tex> может быть только два отрезка с одинаковым расстоянием {{---}} те, что лежат по разные стороны от <tex>s_i</tex>. . . , sn of the set S. T \leftarrow 2D_BSP_tree(S�) return T

Перед темПусть <tex>k = \mathrm{dist}(s_i, как анализировать рандомизированный алгоритмs_j)</tex> и <tex>s_{j_1}, отметим\ s_{j_2}, что здесь возможна одна простая оптимизация. Предположим\ \ldots , что мы выбрали несколько первых разбивающих прямых. Эти прямые порождают разбиение плоскости, фейсы которой соответствуют каким\ s_{j_k}</tex> {{--то узлам BSP-дерева. Рассмотрим одну из таких поверхностей f. В S могут быть }} отрезки, которые полностью пересекают f. Выбор одного из таких отрезков для разбиения f не вызовет фрагментации других отрезков внутри f, так как данный отрезок исключается из дальнейшего рассмотрения.Назовем такое свободным разбиением.Нашей улучшенной стратегией будет использование свободных разбиений везде, где только можно, между <tex>s_i</tex> и использование случайных разбиений в противном случае. Для реализации данной оптимизации нужно уметь определять, вызывает ли отрезок свободное разбиение.Для этого сопоставим каждому отрезку две булевых переменных, которые покажут, лежат ли правый и левый концы отрезка на какой-то из уже добавленных разбивающих прямых.Обе переменных истинны, когда отрезок вызывает свободное разбиение<tex>s_j</tex>.

Теперь оценим производительность алгоритма 2D_random_BSP_tree. Для упрощения рассуждений будем анализировать версию без свободных разбиений Найдём вероятность того, что при добавлении <tex>l(асимптотической разницы они не даютs_i)</tex> разрежет <tex>s_j</tex>.Начнем с анализа размера BSP-дереваЧтобы это произошло, равного числу полученных фрагментов<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, изображенные на рисунке. Если они рассматриваются в порядке (a)\ j, то мы получаем пять фрагментов\ j_1, если же в порядке (b) - то всего три фрагмента.Так как размер BSP-дерева зависит от сгенерированной перестановки\ \ldots , будем анализировать ожидаемый размер BSP-дерева - средний размер для всех n! перестановок\ j_k\}</tex> индекс <tex>i</tex> должен быть наименьшим.

<tex>P(l(s_i) разрезает \cap s_j\ne \varnothing) <= \leqslant \genfrac{}{}{}{0}{1 / (}{k + 2)}</tex> Так как существуют Существуют отрезки, которые не разрезаются <tex>l(s_i)</tex>, но расширение которых защитит <tex>s_j</tex>, так что выше записано неравенство. Теперь мы можем ограничить ожидаемое число разрезов, происходящих при добавлении <tex>s_i</tex>: <tex>E(</tex>число разрезов, происходящих при добавлении <tex>s_i) <= \leqslant \sum(\limits_{j \ne i != j, } \genfrac{}{}{}{0}{1 / }{\mathrm{dist}(k s_i, s_j) + 2)) <= } \leqslant 2 * \cdot \sum(\limits_{k=0..}^{n - 2, } \genfrac{}{}{}{0}{1/ (}{k + 2)) <= } \leqslant 2 * \ln n</tex>. По линейности ожиданий мы можем заключить, что ожидаемое число разрезов, вызванных добавлением всех отрезков составляет не более 2nlogn<tex>2n\log n</tex>.Так как изначально даны <tex>n </tex> отрезков, ожидаемое число фрагментов ограничено <tex>n + 2nlogn2n\log n</tex>.}} Было показано, что ожидаемый размер BSP-дерева, построенного с помощью алгоритма '''2D_random_BSP_tree''', составляет <tex>n + 2n\log n</tex>. Следовательно, мы доказали, что BSP-дерево размера <tex>n + 2n\log n</tex> существует для любого множества <tex>n</tex> отрезков. Кроме того, хотя бы половина перестановок приводит к BSP-дереву размера <tex>n + 4n\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^2\log n)</tex>. {{Теорема| statement = В двумерном пространстве BSP-дерево размера <tex>\mathcal{O}(n\log n)</tex> может быть построено за ожидаемое время <tex>\mathcal{O}(n^2logn2\log n)</tex>.}} Описанный выше алгоритм легко обобщается на трёхмерное пространство. Как было упомянуто выше, мы считаем, что работаем в 3D с триангуляцией граней многранников. Пусть <tex>S</tex> {{---}} множество непересекающихся треугольков в <tex>\mathbb{R}^3</tex>.  Снова ограничимся только авто-разбиениями, разбивая пространство плоскостями, содержащими какой-то из треугольников. Для треугольника <tex>t</tex> обозначим плоскость, содержащую его, как <tex>h(t)</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>)BSP <tex>S^- \leftarrow \{t \cap h^-(t_1) \mid t \in S\}</tex> <tex>T^- \leftarrow</tex> 3D_BSP_tree(<tex>S^-дерево размера O</tex>) <tex>S_v \leftarrow \{t \in S \mid t \subset h(nlognt_1) может быть построено за ожидаемое время O\}</tex> <tex>T \leftarrow</tex> '''BSPTree'''(n<tex>S_v,\ T^2logn-,\ 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>

Описанный выше алгоритм легко распространяется с двухмерного пространства на трехмерное. Пусть S Размер полученного BSP- множество непересекающихся треугольков в 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[[Перечисление точек в произвольном прямоугольнике за n * log ^(t1d - 1) as the splitting plane. */ S+ \leftarrow {t \пересечь hn (t1range tree)+ : t ∈ S}]] T+ \leftarrow 3DBSP* [[Дерево интервалов (S+interval tree)и пересечение точки с множеством интервалов]] S− \leftarrow{t \пересечь h* [[Пересечение прямоугольника с множеством непересекающихся отрезков (t1segment tree)− : t ∈ S}]] T− \leftarrow 3DBSP(S−)== Источники иформации == Create a BSP tree T with root node ν* Mark de Berg, left subtree T−Marc van Kreveld, right subtree T+Mark Overmars, and with SOtfried Schwarzkopf (ν2000) = {t ∈ S : t ⊂ h, Computational Geometry (t12nd revised ed.)}, Springer-Verlag, ISBN 3-540-65620-0 Chapter 12: Binary Space Partition: pp.259–267. return T