1632
правки
Изменения
м
[[Файл:bsp_n2.png|200px|right]]
Однако [[Файл:bsp_n2.png|130px]] Как видно из рисунка, размер авто-разбивающего дерева может быть не минимальным. Возможен случай, когда размер BSP-дерева может составлять <tex>\mathcal{O}(n^2) </tex>, где <tex> n = |S| </tex>.
rollbackEdits.php mass rollback
Алгоритм художника избегает дополнительных затрат памяти, изначально сортируя объекты по расстоянию от них до точки обзора. Тогда объекты проверяются в так называемом порядке глубины, начиная от самого дальнего. В таком случае при рассмотрении объекта уже не нужна проверка его z-координаты, мы всегда пишем цвет в буфер кадра. Значения, хранимые в буфере ранее, просто перезаписываются.
[[Файл:triangle_cycle.png|150px|left]] Чтобы успешно применять данный метод, нужно уметь быстро сортировать объекты. К сожалению, это не всегда просто. Кроме того, порядок глубины не всегда существует: отношение "перед" может содержать циклы. Когда такое цикличное перекрытие происходит, объекты не могут быть корректно отсортированы. В таком случае мы должны разорвать циклы, разбив один или более объектов на части. (Картинка с примером)
Определение, какие объекты нужно разбить и где, затем сортировка их фрагментов {{---}} дорогой процесс, так как порядок зависит от положения точки обзора, и мы должны пересчитывать все при каждом ее смещении.
Чтобы использовать этот алгоритм в реальной жизни, например, в симуляторе полета, мы должны предпосчитать сцену так, чтобы можно было быстро найти корректный порядок отображения объектов для любой точки обзора.
Данную задачу можно элегантно решить при помощи техники '''двоичного разбиения пространства''' (англ. ''binary space partionpartitioning, BSP'').
== Структура BSP-дерева ==
<tex>h^- = \{(x_1,\ x_2,\ \dots,\ x_d) \mid a_1 \cdot x_1 + a_2 \cdot x_2 + \ldots + a_d \cdot x_d + a_{d + 1} < 0\}</tex>
Пусть <tex>S</tex> {{---}} множество объектов, для которого мы строим забиение разбиение в <tex>d</tex>-мерном пространстве.
Пусть <tex>v</tex> {{---}} какая-то вершина дерева, тогда обозначим за <tex>S(v)</tex> множество объектов (возможно пустое), хранимых в этой вершине.
BSP-дерево <tex>T</tex> для этого множества обектов обладает следующими свойствами:
*Если <tex>|S| \leqslant 1</tex>, то <tex>T</tex> {{---}} лист. Фрагмент объекта в <tex>S</tex>, если он существует, хранится в этом листе.
*Если <tex>|S| > 1</tex>, то в корне дерева <tex>v</tex> хранится гиперплоскость <tex>h_v</tex> и множество <tex>S(v)</tex> объектов, которые полностью содержатся в <tex>h_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>.
Размер BSP-дерева равен суммарному размеру множеств во всех узлах. Другими словами, размер BSP-дерева {{---}} число фрагментов, на которые были разбиты объекты. Так как BSP-дерево не содержит бесполезные прямые (прямые, которые разбивают пустую грань), то количество узлов пропорционально размеру дерева.
Корню дерева соответсвует все пространство.
Таким образом, серая область на рисунке соответствует региону <tex>l_1^+ \cap l_2^+ \cap l_3^+-</tex>.
При построении BSP-дерева могут использоваться любые разбивающие гиперплоскости. В целях упрощения вычислений может быть удобно ограничить множество доступных разбивающих гиперплоскостей. Обычно используют авто-разбиения.
{{Определение
| definition = В двухмерном двумерном случае для множества отрезков разбиение, в котором используются разбивающие прямые, проходящие через один из данных отрезков, называется '''авто-разбивающим''' (англ. ''auto-partition'').
}}
В трёхмерном случае авто-разбиение использует плоскости, которые содержат грани многогранников.
== BSP-деревья и алгоритм художника ==
</code>
Заметим, что мы не рисуем объекты из <tex>S(v)</tex>, когда <tex>p_{view}</tex> лежит на разбивающей плоскости <tex>h_v</tex>, потому что они являются плоскими двумерными полигонаполигонами.
Эффективность данного алгоритма, как и любого другого алгоритма для BSP-деревьев, зависит от размера BSP-дерева. То есть необходимо выбирать разбивающие плоскости таким образом, чтобы фрагментация объектов была минимальной.
'''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>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>
| statement = Ожидаемое число фрагментов, сгенерированных алгоритмом '''2D_random_BSP_tree''' есть <tex>\mathcal{O}(n \log n)</tex>.
|proof =
Пусть <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>.
В частности, когда прямая, пересекающая такой отрезок, добавляется раньше <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>.
<tex>
\mathrm{dist}(s_i,\ s_j) = \left\{\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) \cap s_j \ne \varnothing \\
\infty & \mathrm{otherwise} \\
Для всех конечных расстояний до отрезка <tex>s_i</tex> может быть только два отрезка с одинаковым расстоянием {{---}} те, что лежат по разные стороны от <tex>s_i</tex>.
Пусть <tex>k = \mathrm{dist}(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>s_i</tex>:
<tex>E(</tex>число разрезов, происходящих при добавлении <tex>s_i) \leqslant \sum\limits_{i j \ne ji} \genfrac{}{}{}{0}{1}{k \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>2n\log n</tex>. Так как изначально даны <tex>n</tex> отрезков, ожидаемое число фрагментов ограничено <tex>n + 2n\log n</tex>.
{{Теорема
| statement = В двумерном пространстве BSP-дерево размера <tex>\mathcal{O}(n\log n)</tex> может быть построено за ожидаемое время <tex>\mathcal{O}(n^2\log 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>
'''return''' <tex>T</tex>
Размер полученного BSP-дерева снова зависит от порядка треугольников. Как и в двухмерном двумерном случае, мы можем попытаться получить хороший ожидаемый размер дерева, переставив треугольники в случайном порядке. На практике это дает хорошие результаты.
== См. также ==
== Источники иформации ==
* Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf (2000), Computational Geometry (2nd revised ed.), Springer-Verlag, ISBN 3-540-65620-0 Chapter 12: Binary Space Partition: pp.259–267.
[[Категория: Вычислительная геометрия]]
[[Категория: Аффинное пространство]]
[[Категория: Структуры данных]]
