Изменения
→Алгоритм художника (painter's algorithm)
=== Алгоритм художника (painter's algorithm) ===
[[Файл:painters_algo.png|500px|right]]
Алгоритм художника избегает дополнительных затрат памяти, изначально сортируя объекты по расстоянию от них до точки обзора. Тогда объекты проверяются в так называемом порядке глубины, начиная от самого дальнего. В таком случае при рассмотрении объекта уже не нужна проверка его z-координаты, мы всегда пишем цвет в буфер кадра. Значения, хранимые в буфере ранее, просто перезаписываются.
[[Файл:triangle_cycle.png|150px|left]] Чтобы успешно применять данный метод, нужно уметь быстро сортировать объекты. К сожалению, это не всегда просто. Кроме того, порядок глубины не всегда существует: отношение "перед" может содержать циклы. Когда такое цикличное перекрытие происходит, объекты не могут быть корректно отсортированы. В таком случае мы должны разорвать циклы, разбив один или более объектов на части. (Картинка с примером)
Определение, какие объекты нужно разбить и где, затем сортировка их фрагментов {{---}} дорогой процесс, так как порядок зависит от положения точки обзора, и мы должны пересчитывать все при каждом ее смещении.
Чтобы использовать этот алгоритм в реальной жизни, например, в симуляторе полета, мы должны предпосчитать сцену так, чтобы можно было быстро найти корректный порядок отображения объектов для любой точки обзора.
Этот процесс можно представить с помощью двоичного дерева. Каждый лист дерева соответствует грани разбиения, в нем хранится фрагмент объекта, находящийся внутри этой грани. Каждый узел дерева соответсвует разбивающей прямой, которая хранится в этом узле.
{{Определение
| definition = '''Двоичное разбиение пространстваBSP-дерево''' (англ. ''binary space partitiontree'') или '''BSP-дерево''' {{---}} структура данныхдерево, хранящая множество объектов на плоскости, рекурсивно разбитой прямымиотвечающее заданному двоичному разбиению пространства.
}}
Опишем подробней свойства BSP-дерева.
Рассмотрим гиперплоскость <tex>h: a_1*\cdot x_1 + a_2*\cdot x_2 + ... \ldots + a_d*\cdot x_d + a_{d + 1} = 0</tex>.
Пусть <tex>h^+</tex> {{---}} положительная полуплоскостьположительное полупространство, а <tex>h^-</tex> {{---}} отрицательнаяотрицательное:
<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>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 = В двухмерном двумерном случае для множества отрезков разбиение, в котором используются разбивающие прямые, проходящие через один из данных отрезков, называется '''авто-разбивающим'''(англ. }}{{Определение| definition = В трехмерном случае для множества полигонов разбиение, в котором используются разбивающие плоскости, проходящие через одну из данных плоскостей, называется '''автоauto-разбивающим'''. }}{{Определение| definition = BSP-дерево, построенное с применением авто-разбиения, называются '''авто-разбивающим'partition'').
}}
== BSP-деревья и алгоритм художника ==
Предположим, что мы построили BSP-дерево <tex>T </tex> для множества объектов <tex>S </tex> в трехмерном пространстве. Как нам следует использовать его, чтобы получить порядок глубины для алгоритма художника? Пусть p_view <tex>p_{view}</tex> {{- --}} точка обзора, и она лежит над разбивающей плоскостью, хранимой в корне <tex>T</tex>. Тогда ни один из объектов, лежащих под этой плоскостью, не может затемнить (мб перекрыть?) ни один из объектов, лежащих выше нее. Таким образом, мы можем безопасно показать отрисовать фрагменты объектов из поддерева <tex>T^- </tex> до показа отрисовки объектов из поддерва <tex>T^+</tex>.
Порядок фрагментов объектов в поддеревьях определяется таким же способом.
<code> '''void''' painters_algorithm(<tex>T</tex>, pview<tex>p_{view}</tex>): Let ν be the root of <tex>v \leftarrow T.root</tex> '''if ν is a leaf''' <tex>v</tex> {{---}} лист then Scan-convert the object fragments in отрисовать фрагменты объектов из <tex>S(νv).</tex> '''else if pview ''' <tex>p_{view} \in hh_v^+ν</tex> then painters_algorithm(T−<tex>T^-</tex>, pview<tex>p_{view}</tex>) Scan-convert the object fragments in отрисовать фрагменты объектов из <tex>S(νv).</tex> painters_algorithm(<tex>T^+</tex>, pview<tex>p_{view}</tex>) '''else if pview ''' <tex>p_{view} \in h−νh_v^-</tex> then painters_algorithm(<tex>T^+</tex>, pview<tex>p_{view}</tex>) Scan-convert the object fragments in отрисовать фрагменты объектов из <tex>S(νv).</tex> painters_algorithm(T−<tex>T^-</tex>, pview<tex>p_{view}</tex>) '''else (''' <font color="green">/∗ pview <tex>p_{view} \in hν h_v</tex> ∗)/</font> painters_algorithm(<tex>T^+</tex>, pview<tex>p_{view}</tex>) painters_algorithm(T−<tex>T^-</tex>, <tex>p_{view}</tex>)</code> Заметим, pviewчто мы не рисуем объекты из <tex>S(v)</tex>, когда <tex>p_{view}</tex> лежит на разбивающей плоскости <tex>h_v</tex>, потому что они являются плоскими двумерными полигонами.
== Построение BSP-дерева ==
Как и в других алгоритмах, когда нужно сделать сложный выбор, сделаем рандомный выбор. Это означает, что для разбиения мы будем использовать случайно выбранный отрезок. Для этого перед тем, как начинать построение дерева, расположим отрезки в <tex>S</tex> случайном порядке. <code> '''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-дерева. [[Файл: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]] В качестве примера рассмотрим три отрезка, изображенные на рисунке. Если они рассматриваются в порядке (a), то мы получаем пять фрагментов, если же в порядке (b) {{- --}} то всего три фрагмента. Так как размер 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(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>s_i</tex>. [[Файл:bsp_dist.png|300px|right]] <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} \\\end{array}\right.</tex> Для всех конечных расстояний до отрезка <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>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>.
Мы можем использовать этот факт, чтобы найти дерево такого размера: после запуска алгоритма сравним размер дерева с данной оценкой, если он превышает оценку, просто построим BSP-дерево еще раз, но для новой перестановки. Ожидаемое число запусков равняется двум.
Теперь проанализируем время работы алгоритма. Понятно, что оно зависит от используемой перестановки, так что опять рассмотрим ожидаемое время работы. Нахождение рандомной перестановки занимает <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>, заданных в трехмерном пространстве.