BSP-дерево — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Построение BSP-дерева)
м (rollbackEdits.php mass rollback)
 
(не показано 28 промежуточных версий 6 участников)
Строка 20: Строка 20:
  
 
=== Алгоритм художника (painter's algorithm) ===
 
=== Алгоритм художника (painter's algorithm) ===
 +
[[Файл:painters_algo.png|500px|right]]
 
Алгоритм художника избегает дополнительных затрат памяти, изначально сортируя объекты по расстоянию от них до точки обзора. Тогда объекты проверяются в так называемом порядке глубины, начиная от самого дальнего. В таком случае при рассмотрении объекта уже не нужна проверка его z-координаты, мы всегда пишем цвет в буфер кадра. Значения, хранимые в буфере ранее, просто перезаписываются.
 
Алгоритм художника избегает дополнительных затрат памяти, изначально сортируя объекты по расстоянию от них до точки обзора. Тогда объекты проверяются в так называемом порядке глубины, начиная от самого дальнего. В таком случае при рассмотрении объекта уже не нужна проверка его z-координаты, мы всегда пишем цвет в буфер кадра. Значения, хранимые в буфере ранее, просто перезаписываются.
  
Чтобы успешно применять данный метод, нужно уметь быстро сортировать объекты. К сожалению, это не всегда просто. Кроме того, порядок глубины не всегда существует: отношение "перед" может содержать циклы. Когда такое цикличное перекрытие происходит, объекты не могут быть корректно отсортированы. В таком случае мы должны разорвать циклы, разбив один или более объектов на части. (Картинка с примером)
+
[[Файл:triangle_cycle.png|150px|left]]
 +
 
 +
Чтобы успешно применять данный метод, нужно уметь быстро сортировать объекты. К сожалению, это не всегда просто. Кроме того, порядок глубины не всегда существует: отношение "перед" может содержать циклы. Когда такое цикличное перекрытие происходит, объекты не могут быть корректно отсортированы. В таком случае мы должны разорвать циклы, разбив один или более объектов на части.
  
 
Определение, какие объекты нужно разбить и где, затем сортировка их фрагментов {{---}} дорогой процесс, так как порядок зависит от положения точки обзора, и мы должны пересчитывать все при каждом ее смещении.
 
Определение, какие объекты нужно разбить и где, затем сортировка их фрагментов {{---}} дорогой процесс, так как порядок зависит от положения точки обзора, и мы должны пересчитывать все при каждом ее смещении.
 
Чтобы использовать этот алгоритм в реальной жизни, например, в симуляторе полета, мы должны предпосчитать сцену так, чтобы можно было быстро найти корректный порядок отображения объектов для любой точки обзора.
 
Чтобы использовать этот алгоритм в реальной жизни, например, в симуляторе полета, мы должны предпосчитать сцену так, чтобы можно было быстро найти корректный порядок отображения объектов для любой точки обзора.
  
Данную задачу можно элегантно решить при помощи техники '''двоичного разбиения пространства''' (англ. ''binary space partion, BSP'').
+
Данную задачу можно элегантно решить при помощи техники '''двоичного разбиения пространства''' (англ. ''binary space partitioning, BSP'').
  
 
== Структура BSP-дерева ==
 
== Структура BSP-дерева ==
 
Чтобы понять, что из себя представляет двоичное разбиение пространства, рассмотрим рисунок. На нем показано двоичное разбиение множества объектов на плоскости и дерево, которое этому разбиению соответствует.
 
Чтобы понять, что из себя представляет двоичное разбиение пространства, рассмотрим рисунок. На нем показано двоичное разбиение множества объектов на плоскости и дерево, которое этому разбиению соответствует.
 
В двумерном случае BSP строится с помощью рекурсивного разбиения плоскости прямыми. В данном примере это происходит так: сначала проводим прямую <tex>l_1</tex>, разбивая полуплоскость выше <tex>l_1</tex> прямой <tex>l_2</tex>, а ниже {{---}} прямой <tex>l_3</tex> и так далее.
 
В двумерном случае BSP строится с помощью рекурсивного разбиения плоскости прямыми. В данном примере это происходит так: сначала проводим прямую <tex>l_1</tex>, разбивая полуплоскость выше <tex>l_1</tex> прямой <tex>l_2</tex>, а ниже {{---}} прямой <tex>l_3</tex> и так далее.
{{TODO | t = Картинка про прямые и про дерево}}
+
 
 +
[[Файл:bsp_plane1.png|300px]][[Файл:bsp_tree1.png|300px]]
  
 
Прямые разбивают на части не только плоскость, но и объекты, расположенные на ней. Разбиение продолжается до тех пор, пока внутри каждой грани плоскости окажется не более одного фрагмента объекта.
 
Прямые разбивают на части не только плоскость, но и объекты, расположенные на ней. Разбиение продолжается до тех пор, пока внутри каждой грани плоскости окажется не более одного фрагмента объекта.
Строка 50: Строка 54:
 
<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>S</tex> {{---}} множество объектов, для которого мы строим разбиение в <tex>d</tex>-мерном пространстве.
  
Пусть <tex>v</tex> {{---}} какая-то вершина дерева, тогда обозначим <tex>S(v)</tex> множество объектов (возможно пустое), хранимых в этой вершине.
+
Пусть <tex>v</tex> {{---}} какая-то вершина дерева, тогда обозначим за <tex>S(v)</tex> множество объектов (возможно пустое), хранимых в этой вершине.
  
 
BSP-дерево <tex>T</tex> для этого множества обектов обладает следующими свойствами:
 
BSP-дерево <tex>T</tex> для этого множества обектов обладает следующими свойствами:
 
*Если <tex>|S| \leqslant 1</tex>, то <tex>T</tex> {{---}} лист. Фрагмент объекта в <tex>S</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>|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>;
**правый ребенок <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-дерево не содержит бесполезные прямые (прямые, которые разбивают пустую грань), то количество узлов пропорционально размеру дерева.
 
Размер BSP-дерева равен суммарному размеру множеств во всех узлах. Другими словами, размер BSP-дерева {{---}} число фрагментов, на которые были разбиты объекты. Так как BSP-дерево не содержит бесполезные прямые (прямые, которые разбивают пустую грань), то количество узлов пропорционально размеру дерева.
{{TODO | t = Рисунок про соответсвие нодов и регионов}}
+
 
 +
[[Файл:bsp_plane2.png|300px]][[Файл:bsp_tree2.png|300px]]
  
 
Листья BSP-дерева соответствуют граням, то есть мы можем каждой вершине <tex>v</tex> сопоставить полигональную область на плоскости, которая определяется как пересечение полуплоскостей <tex>h_{\mu}^{\Diamond}</tex>, где <tex>\mu</tex> {{---}} предок <tex>v</tex>, и
 
Листья BSP-дерева соответствуют граням, то есть мы можем каждой вершине <tex>v</tex> сопоставить полигональную область на плоскости, которая определяется как пересечение полуплоскостей <tex>h_{\mu}^{\Diamond}</tex>, где <tex>\mu</tex> {{---}} предок <tex>v</tex>, и
Строка 74: Строка 79:
 
Корню дерева соответсвует все пространство.
 
Корню дерева соответсвует все пространство.
  
Таким образом, серая область на рисунке соответствует региону <tex>l_1^+ \cap l_2^+ \cap l_3^+</tex>.
+
Таким образом, серая область на рисунке соответствует региону <tex>l_1^+ \cap l_2^+ \cap l_3^-</tex>.
  
 
При построении BSP-дерева могут использоваться любые разбивающие гиперплоскости. В целях упрощения вычислений может быть удобно ограничить множество доступных разбивающих гиперплоскостей. Обычно используют авто-разбиения.
 
При построении BSP-дерева могут использоваться любые разбивающие гиперплоскости. В целях упрощения вычислений может быть удобно ограничить множество доступных разбивающих гиперплоскостей. Обычно используют авто-разбиения.
 
{{Определение
 
{{Определение
| definition = В двухмерном случае для множества отрезков разбиение, в котором используются разбивающие прямые, проходящие через один из данных отрезков, называется '''авто-разбивающим''' (англ. ''auto-partition'').  
+
| definition = В двумерном случае для множества отрезков разбиение, в котором используются разбивающие прямые, проходящие через один из данных отрезков, называется '''авто-разбивающим''' (англ. ''auto-partition'').  
 
}}
 
}}
 +
 
В трёхмерном случае авто-разбиение использует плоскости, которые содержат грани многогранников.
 
В трёхмерном случае авто-разбиение использует плоскости, которые содержат грани многогранников.
  
Однако размер авто-разбивающего дерева может быть не минимальным. Возможен случай, когда размер BSP-дерева может составлять <tex>\mathcal{O}(n^2) </tex>, где <tex> n = |S| </tex>.
+
[[Файл:bsp_n2.png|130px]]
{{TODO | t = Картинка, когда может быть n^2}}
+
 
 +
Как видно из рисунка, размер авто-разбивающего дерева может быть не минимальным. Возможен случай, когда размер BSP-дерева может составлять <tex>\mathcal{O}(n^2) </tex>, где <tex> n = |S| </tex>.
  
 
== BSP-деревья и алгоритм художника ==
 
== BSP-деревья и алгоритм художника ==
Строка 111: Строка 118:
 
</code>
 
</code>
  
Заметим, что мы не рисуем объекты из <tex>S(v)</tex>, когда <tex>p_{view}</tex> лежит на разбивающей плоскости <tex>h_v</tex>, потому что они являются плоскими двумерными полигона.
+
Заметим, что мы не рисуем объекты из <tex>S(v)</tex>, когда <tex>p_{view}</tex> лежит на разбивающей плоскости <tex>h_v</tex>, потому что они являются плоскими двумерными полигонами.
  
 
Эффективность данного алгоритма, как и любого другого алгоритма для BSP-деревьев, зависит от размера BSP-дерева. То есть необходимо выбирать разбивающие плоскости таким образом, чтобы фрагментация объектов была минимальной.
 
Эффективность данного алгоритма, как и любого другого алгоритма для BSP-деревьев, зависит от размера BSP-дерева. То есть необходимо выбирать разбивающие плоскости таким образом, чтобы фрагментация объектов была минимальной.
  
BSP-деревья интересны тем, что позволяют достичь быстрой реализации удаления скрытых поверхностей для отрисовки сцены (будь то симулятор полёта или персонаж в игре, осматривающий окружающий мир). Так как скорость {{---}} главная цель, следует упростить вид объектов рассматриваемого пейзажа, поэтому далее будем считать, что в 3D мы работаем только с многогранниками, грани которых уже триангулированы. Таким образом множество <tex>S</tex> в трёхмерном пространстве будет состоять только из треугольников.
+
BSP-деревья интересны тем, что позволяют достичь быстрой реализации удаления скрытых поверхностей для отрисовки сцены (будь то симулятор полёта или персонаж в игре, осматривающий окружающий мир). Так как скорость {{---}} главная цель, следует упростить вид объектов рассматриваемого пейзажа, поэтому далее будем считать, что в 3D мы работаем только с многогранниками, грани которых уже [[Триангуляция полигонов (ушная + монотонная) | триангулированы]]. Таким образом множество <tex>S</tex> в трёхмерном пространстве будет состоять только из треугольников.
  
 
== Построение BSP-дерева ==
 
== Построение BSP-дерева ==
При решении задач в трехмерном пространстве бывает полезно сначала рассмотреть задачу на плоскости, что мы и сделаем.
+
Прежде чем переходить к задаче отрисовки сцены в трёхмерном случае, рассмотрим для простоты аналогичную задачу на плоскости.
  
 
Пусть <tex>S</tex> {{---}} множество из <tex>n</tex> непересекающихся отрезков на плоскости. Ограничимся авто-разбиением, рассматривая только прямые, содержащие один из отрезков.  
 
Пусть <tex>S</tex> {{---}} множество из <tex>n</tex> непересекающихся отрезков на плоскости. Ограничимся авто-разбиением, рассматривая только прямые, содержащие один из отрезков.  
Строка 124: Строка 131:
 
Пусть <tex>l(s)</tex> {{---}} прямая, содержащая отрезок <tex>s</tex>.
 
Пусть <tex>l(s)</tex> {{---}} прямая, содержащая отрезок <tex>s</tex>.
  
На вход алгоритму подается <tex>S = {s_1, s_2, ... ,  s_n}</tex> {{---}} множество отрезков.
+
На вход алгоритму подается <tex>S = \{s_1,\ s_2,\ \dots ,\ s_n\}</tex> {{---}} множество отрезков.
  
    BSPTree 2D_BSP_tree(<tex>S</tex>)
+
<code>
        if <tex>|S| <= 1</tex>
+
'''BSPTree''' 2D_BSP_tree(<tex>S</tex>):
            <tex>T \leftarrow</tex> new BSPTree(S) /* <tex>T</tex> будет листом, в котором хранится данное множество */
+
    '''if''' <tex>|S| \leqslant 1</tex>
            return <tex>T</tex>
+
        <tex>T \leftarrow</tex> '''BSPTree'''(<tex>S</tex>) <font color="green">/* <tex>T</tex> будет листом, в котором хранится данное множество */</font>
        else  /* используем <tex>l(s1)</tex> как разбивающую прямую */
+
        '''return''' <tex>T</tex>
                <tex>S^+ \leftarrow \{s \cap l^+(s_1) : s \in S\}</tex>
+
    '''else''' <font color="green">/* используем <tex>l(s_1)</tex> как разбивающую прямую */</tex></font>
                <tex>T^+ \leftarrow</tex> 2D_BSP_tree(<tex>S^+</tex>)
+
        <tex>S^+ \leftarrow \{s \cap l^+(s_1) \mid s \in S\}</tex>
                <tex>S^\leftarrow \{s \cap l^-(s_1) : s \in S\}</tex>  
+
        <tex>T^+ \leftarrow</tex> 2D_BSP_tree(<tex>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>S_v \leftarrow \{s \in S : s \subset l(s_1)\}</tex>
+
        <tex>T^- \leftarrow</tex> 2D_BSP_tree(<tex>S^-</tex>)
                <tex>T \ leftarrow</tex> new BSPTree(S_v, T^-, T^+)  
+
        <tex>S_v \leftarrow \{s \in S \mid s \subset l(s_1)\}</tex>
                // создаем BSP-дерево c корнем в вершине <tex>v</tex>, левым поддеревом <tex>T^</tex> и правым поддеревом <tex>T^+</tex>  
+
        <tex>T \leftarrow</tex> '''BSPTree'''(<tex>S_v,\ T^-,\ T^+</tex>)  
                // и множеством хранимых объектов <tex>S_v</tex>
+
        <font color="green">// создаем BSP-дерево c корнем в вершине <tex>v</tex>, левым поддеревом <tex>T^-</tex> и правым поддеревом <tex>T^+</tex> </font>
                return <tex>T</tex>
+
        <font color="green">// и множеством хранимых объектов <tex>S_v</tex></font>
 +
        '''return''' <tex>T</tex>                
 +
</code>
 +
Данный алгоритм создает BSP-дерево для множества <tex>S</tex>, но как уже известно, оно не будет наименьшим в общем случае.
  
Понятно, что алгоритм создает BSP-дерево для множества <tex>S</tex>, но будет ли оно наименьшим?
+
Необходимо придумать стратегию выбора прямой разбиения, а не просто брать <tex>l(s_1)</tex>. Возможным подходом является выбор отрезка <tex>s \in S</tex>, такого что <tex>l(s)</tex> пересекает наименьшее число отрезков. Но такой жадный алгоритм работает не на всех конфигурациях отрезков. Кроме того, поиск такого отрезка {{---}} занятие затратное.
  
Наверное, стоит тщательней выбирать прямую разбиения, а не просто брать <tex>l(s_1)</tex>. Возможным подходом является выбор отрезка <tex>s \in S</tex>, такого что <tex>l(s)</tex> пересекает наименьшее число отрезков. Но такой жадный алгоритм работает не на всех конфигурациях отрезков. Кроме того, поиск такого отрезка {{---}} занятие затратное.
+
Как и в других алгоритмах, когда нужно сделать сложный выбор, сделаем рандомный выбор. Это означает, что для разбиения мы будем использовать случайно выбранный отрезок. Для этого перед тем, как начинать построение дерева, расположим отрезки в <tex>S</tex> случайном порядке.
  
Как и в других алгоритмах, когда нужно сделать сложный выбор, просто выберем случайно. Это означает, что для разбиения мы будем использовать рандомный отрезок. Для этого перед тем, как начинать построение дерева, расположим отрезки в <tex>S</tex> случайном порядке.
+
<code>
 
+
'''void''' 2D_random_BSP_tree(<tex>S</tex>):
    2D_random_BSP_tree(<tex>S</tex>)  
+
    <tex>S \leftarrow </tex> random_permutation(<tex>S</tex>)
        <tex>S \leftarrow </tex> random_permutation(<tex>S</tex>).
+
    <tex>T \leftarrow </tex> 2D_BSP_tree(<tex>S</tex>)
        <tex>T \leftarrow </tex> 2D_BSP_tree(<tex>S</tex>)
+
    '''return''' <tex>T</tex>
        return <tex>T</tex>
+
</code>
 
+
Перед анализированием рандомизированного алгоритма рассмотрим одну простую оптимизацию.  
Перед тем, как анализировать рандомизированный алгоритм, отметим, что здесь возможна одна простая оптимизация.  
 
  
 
Предположим, что мы выбрали несколько первых разбивающих прямых. Эти прямые порождают разбиение плоскости, грани которой соответствуют каким-то узлам BSP-дерева.  
 
Предположим, что мы выбрали несколько первых разбивающих прямых. Эти прямые порождают разбиение плоскости, грани которой соответствуют каким-то узлам BSP-дерева.  
  
Рассмотрим одну из таких поверхностей <tex>f</tex>. В <tex>S</tex> могут быть отрезки, которые полностью пересекают <tex>f</tex>. Выбор одного из таких отрезков для разбиения <tex>f</tex> не вызовет фрагментации других отрезков внутри <tex>f</tex>, так как данный отрезок исключается из дальнейшего рассмотрения. Назовем такое свободным разбиением.
+
[[Файл: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-дерева, равного числу полученных фрагментов, которое зависит от сгенерированной перестановки отрезков. Некоторые перестановки могут породить маленькие деревья, а другие {{---}} большие.  
+
Теперь оценим производительность алгоритма '''2D_random_BSP_tree'''. Для упрощения рассуждений будем анализировать версию без свободных разбиений (асимптотической разницы между ними нет). Начнем с анализа размера BSP-дерева, равного числу полученных фрагментов, которое зависит от сгенерированной перестановки отрезков. Некоторые перестановки могут породить маленькие деревья, а другие {{---}} большие.  
 +
 
 +
[[Файл:bsp_three_segments.png|500px]]
  
 
В качестве примера рассмотрим три отрезка, изображенные на рисунке. Если они рассматриваются в порядке (a), то мы получаем пять фрагментов, если же в порядке (b) {{---}} то всего три фрагмента.
 
В качестве примера рассмотрим три отрезка, изображенные на рисунке. Если они рассматриваются в порядке (a), то мы получаем пять фрагментов, если же в порядке (b) {{---}} то всего три фрагмента.
Строка 167: Строка 179:
  
 
{{Лемма
 
{{Лемма
| statement = Ожидаемое число фрагментов, сгенерированных алгоритмом 2D_random_BSP_tree есть <tex>O(nlogn)</tex>.
+
| statement = Ожидаемое число фрагментов, сгенерированных алгоритмом '''2D_random_BSP_tree''' есть <tex>\mathcal{O}(n \log n)</tex>.
 
|proof =  
 
|proof =  
Пусть <tex>s_i</tex> {{---}} фиксированный отрезок из <tex>S</tex>. Проанализируем ожидаемое количество отрезков, которые мы разрежем, когда <tex>l(s_i)</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>.  
+
Рассмотрим рисунок и постараемся понять, разрезается ли отрезок <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>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>.
Строка 177: Строка 189:
 
Эти размышления приводят нас к определению расстояния от какого-то отрезка до фиксированного отрезка <tex>s_i</tex>.
 
Эти размышления приводят нас к определению расстояния от какого-то отрезка до фиксированного отрезка <tex>s_i</tex>.
  
<tex>dist_{s_i}(s_j)</tex> = {количество пересекаемых отрезков, если <tex>l(s_i)</tex> пересекает <tex>s_j</tex>; <tex>infinity</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>s_i</tex> может быть только два отрезка с одинаковым расстоянием {{---}} те, что лежат по разные стороны от <tex>s_i</tex>.
  
Пусть <tex>k = dist_{s_i}(s_j)</tex> и <tex>s_{j_1}, s_{j_2}, ... , s_{j_k}</tex> {{---}} отрезки между <tex>s_i</tex> и <tex>s_j</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, ... , j_k\}</tex> <tex>i</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>s_j) <= 1 / (k + 2)</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>l(s_i)</tex>, но расширение которых защитит <tex>s_j</tex>, так что выше записано неравенство.
  
 
Теперь мы можем ограничить ожидаемое число разрезов, происходящих при добавлении <tex>s_i</tex>:
 
Теперь мы можем ограничить ожидаемое число разрезов, происходящих при добавлении <tex>s_i</tex>:
<tex>E(</tex>число разрезов, происходящих при добавлении <tex>s_i) <= sum(i != j, 1 / (k + 2)) <= 2 * sum(k=0..n - 2, 1/ (k + 2)) <= 2 * ln n</tex>.
 
  
По линейности ожиданий мы можем заключить, что ожидаемое число разрезов, вызванных добавлением всех отрезков составляет не более <tex>2nlogn</tex>. Так как изначально даны n отрезков, ожидаемое число фрагментов ограничено <tex>n + 2nlogn</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>2n\log n</tex>. Так как изначально даны <tex>n</tex> отрезков, ожидаемое число фрагментов ограничено <tex>n + 2n\log n</tex>.
 
}}
 
}}
  
Мы показали, что ожидаемый размер BSP-дерева, построенного с помощью алгоритма 2D_random_BSP_tree, составляет <tex>n + 2nlogn</tex>. Следовательно, мы доказали, что BSP-дерево размера <tex>n + 2nlogn</tex> существует для любого множества <tex>n</tex> отрезков. Кроме того, хотя бы половина перестановок приводит к BSP-дереву размера <tex>n + 4nlogn</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-дерево еще раз, но для новой перестановки. Ожидаемое число запусков равняется двум.
 
Мы можем использовать этот факт, чтобы найти дерево такого размера: после запуска алгоритма сравним размер дерева с данной оценкой, если он превышает оценку, просто построим BSP-дерево еще раз, но для новой перестановки. Ожидаемое число запусков равняется двум.
  
Теперь проанализируем время работы алгоритма. Понятно, что оно зависит от используемой перестановки, так что опять рассмотрим ожидаемое время работы. Нахождение рандомной перестановки занимает <tex>O(n)</tex>. Если проигнорировать время рекурсивных вызовов, то время работы алгоритма линейно от количества фрагментов в <tex>S</tex>. Это число не превышает <tex>n</tex>, так как становится меньше с каждым рекурсивным вызовом. Число рекурсивных вызовов ограничено количеством сгенерированных фрагментов, которое составляет <tex>O(nlogn)</tex>. Таким образом, время построения дерева составляет <tex>O(n^2logn)</tex>.
+
Теперь проанализируем время работы алгоритма. Понятно, что оно зависит от используемой перестановки, так что опять рассмотрим ожидаемое время работы. Нахождение рандомной перестановки занимает <tex>\mathcal{O}(n)</tex> при помощи [[Метод генерации случайной перестановки, алгоритм Фишера-Йетса |алгоритма Фишера-Йетса]]. Если проигнорировать время рекурсивных вызовов, то время работы алгоритма линейно от количества фрагментов в <tex>S</tex>. Это число не превышает <tex>n</tex>, так как становится меньше с каждым рекурсивным вызовом. Число рекурсивных вызовов ограничено количеством сгенерированных фрагментов, которое составляет <tex>\mathcal{O}(n\log n)</tex>. Таким образом, время построения дерева составляет <tex>\mathcal{O}(n^2\log n)</tex>.
  
 
{{Теорема
 
{{Теорема
| statement = BSP-дерево размера <tex>O(nlogn)</tex> может быть построено за ожидаемое время <tex>O(n^2logn)</tex>.
+
| statement = В двумерном пространстве BSP-дерево размера <tex>\mathcal{O}(n\log n)</tex> может быть построено за ожидаемое время <tex>\mathcal{O}(n^2\log n)</tex>.
 
}}
 
}}
  
Описанный выше алгоритм легко распространяется с двухмерного пространства на трехмерное.  
+
Описанный выше алгоритм легко обобщается на трёхмерное пространство. Как было упомянуто выше, мы считаем, что работаем в 3D с триангуляцией граней многранников.
  
Пусть <tex>S</tex> {{---}} множество непересекающихся треугольков в <tex>R^3</tex>.  
+
Пусть <tex>S</tex> {{---}} множество непересекающихся треугольков в <tex>\mathbb{R}^3</tex>.  
  
 
Снова ограничимся только авто-разбиениями, разбивая пространство плоскостями, содержащими какой-то из треугольников.
 
Снова ограничимся только авто-разбиениями, разбивая пространство плоскостями, содержащими какой-то из треугольников.
  
 
Для треугольника <tex>t</tex> обозначим плоскость, содержащую его, как <tex>h(t)</tex>.
 
Для треугольника <tex>t</tex> обозначим плоскость, содержащую его, как <tex>h(t)</tex>.
На вход алгоритму подается множество треугольников <tex>S = \{t_1, t_2, ... , t_n\}</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>
+
* [[Перечисление точек в произвольном прямоугольнике за n * log ^(d - 1) n (range tree)]]
            <tex>T \leftarrow</tex> new BSPTree(S) /* <tex>T</tex> будет листом, в котором хранится данное множество */
+
* [[Дерево интервалов (interval tree) и пересечение точки с множеством интервалов]]
            return <tex>T</tex>
+
* [[Пересечение прямоугольника с множеством непересекающихся отрезков (segment tree)]]
        else /* используем <tex>h(t1)</tex> как разбивающую плоскость */
+
== Источники иформации ==
                <tex>S^+ \leftarrow \{t \cap h^+(t_1) : t \in S\}</tex>
+
* 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.
                <tex>T^+ \leftarrow</tex> 3D_BSP_tree(<tex>S^+</tex>)
 
                <tex>S^− \leftarrow \{t \cap h^-(t_1) : t \in S\}</tex>
 
                <tex>T^− \leftarrow </tex>3D_BSP_tree(<tex>S^−</tex>)
 
                <tex>S_v \leftarrow \{t \in S : t \subset h(t_1)\}</tex>
 
                <tex>T \ leftarrow</tex> new BSPTree(S_v, T^-, T^+)
 
                // создаем BSP-дерево c корнем в вершине <tex>v</tex>, левым поддеревом <tex>T^−</tex> и правым поддеревом <tex>T^+</tex>
 
                // и множеством хранимых объектов <tex>S_v</tex>
 
                return <tex>T</tex>
 
  
Размер полученного BSP-дерева снова зависит от порядка треугольников. Как и в двухмерном случае, мы можем попытаться получить хороший ожидаемый размер дерева, переставив треугольники в случайном порядке. На практике это дает хорошие результаты.
+
[[Категория: Вычислительная геометрия]]
 +
[[Категория: Аффинное пространство]]
 +
[[Категория: Структуры данных]]

Текущая версия на 19:31, 4 сентября 2022

Одной из важных задач является визуализация объектов, когда точка обзора находится над плоскостью с 3D или 2D объектами. Определение местоположений объектов и их теней занимает много времени.

Задача:
Дана сцена с 2D или 3D объектами и наблюдатель, который смотрит на сцену из своей точки обзора. Нужно отрисовать на сцене видимые наблюдателю части объектов.


Простейшие алгоритмы отрисовки сцены

Алгоритм z-буфера (z-buffer algorithm)

Для удаления невидимых частей объектов существует простой, но длительный метод — алгоритм z-буфера. В направлении просмотра проводится ось z-координат, затем определяется, какие пиксели покрывают проекции объектов. Алгоритм хранит информацию об уже обработанных объектах в двух буферах: буфере кадра и z-буфере.

  • В буфере кадра для каждого пикселя хранится информация о цвете объекта, отображаемого им на данный момент.
  • В z-буфере для каждого пикселя хранится z-координата видимого на данный момент объекта, точнее, в нем хранится z-координату точки такого объекта.

Предположим, что мы выбрали пиксель и преобразовываем объект.

  • Если z-координата объекта в этом пикселе меньше, чем z-координата, хранимая в z-буфере, тогда новый объект лежит перед видимым на данный момент. Тогда запишем цвет нового объекта в буфер кадра, а его координату — в z-буфер.
  • Если z-координата объекта в этом пикселе больше, чем z-координата, хранимая в z-буфере, то новый объект не видим, и буферы останутся без изменений.

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

Алгоритм художника (painter's algorithm)

Painters algo.png

Алгоритм художника избегает дополнительных затрат памяти, изначально сортируя объекты по расстоянию от них до точки обзора. Тогда объекты проверяются в так называемом порядке глубины, начиная от самого дальнего. В таком случае при рассмотрении объекта уже не нужна проверка его z-координаты, мы всегда пишем цвет в буфер кадра. Значения, хранимые в буфере ранее, просто перезаписываются.

Triangle cycle.png

Чтобы успешно применять данный метод, нужно уметь быстро сортировать объекты. К сожалению, это не всегда просто. Кроме того, порядок глубины не всегда существует: отношение "перед" может содержать циклы. Когда такое цикличное перекрытие происходит, объекты не могут быть корректно отсортированы. В таком случае мы должны разорвать циклы, разбив один или более объектов на части.

Определение, какие объекты нужно разбить и где, затем сортировка их фрагментов — дорогой процесс, так как порядок зависит от положения точки обзора, и мы должны пересчитывать все при каждом ее смещении. Чтобы использовать этот алгоритм в реальной жизни, например, в симуляторе полета, мы должны предпосчитать сцену так, чтобы можно было быстро найти корректный порядок отображения объектов для любой точки обзора.

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

Структура BSP-дерева

Чтобы понять, что из себя представляет двоичное разбиение пространства, рассмотрим рисунок. На нем показано двоичное разбиение множества объектов на плоскости и дерево, которое этому разбиению соответствует. В двумерном случае BSP строится с помощью рекурсивного разбиения плоскости прямыми. В данном примере это происходит так: сначала проводим прямую [math]l_1[/math], разбивая полуплоскость выше [math]l_1[/math] прямой [math]l_2[/math], а ниже — прямой [math]l_3[/math] и так далее.

Bsp plane1.pngBsp tree1.png

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

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

Определение:
BSP-дерево (англ. binary space partition tree) — дерево, отвечающее заданному двоичному разбиению пространства.

Опишем подробней свойства BSP-дерева.

Рассмотрим гиперплоскость [math]h: a_1 \cdot x_1 + a_2 \cdot x_2 + \ldots + a_d \cdot x_d + a_{d + 1} = 0[/math].

Пусть [math]h^+[/math] — положительное полупространство, а [math]h^-[/math] — отрицательное:

[math]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} \gt 0\}[/math]

[math]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} \lt 0\}[/math]

Пусть [math]S[/math] — множество объектов, для которого мы строим разбиение в [math]d[/math]-мерном пространстве.

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

BSP-дерево [math]T[/math] для этого множества обектов обладает следующими свойствами:

  • Если [math]|S| \leqslant 1[/math], то [math]T[/math] — лист. Фрагмент объекта в [math]S[/math], если он существует, хранится в этом листе.
  • Если [math]|S| \gt 1[/math], то в корне дерева [math]v[/math] хранится гиперплоскость [math]h_v[/math] и множество [math]S(v)[/math] объектов, которые полностью содержатся в [math]h_v[/math].
    • левый ребенок [math]v[/math] является корнем BSP-дерева [math]T^-[/math] на множестве объектов [math]S^- = \{h_v^- \cap s \mid s \in S\}[/math];
    • правый ребенок [math]v[/math] является корнем BSP-дерева [math]T^+[/math] на множестве объектов [math]S^+ = \{h_v^+ \cap s \mid s \in S\}[/math].

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

Bsp plane2.pngBsp tree2.png

Листья BSP-дерева соответствуют граням, то есть мы можем каждой вершине [math]v[/math] сопоставить полигональную область на плоскости, которая определяется как пересечение полуплоскостей [math]h_{\mu}^{\Diamond}[/math], где [math]\mu[/math] — предок [math]v[/math], и

[math] \Diamond = \left\{\begin{array}{llcl} - & \mathrm{if}\ v\ - \ \mathrm{left}\ \mathrm{child} \\ + & \mathrm{if}\ v\ - \ \mathrm{right}\ \mathrm{child} \\ \end{array}\right. [/math]

Корню дерева соответсвует все пространство.

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

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

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


В трёхмерном случае авто-разбиение использует плоскости, которые содержат грани многогранников.

Bsp n2.png

Как видно из рисунка, размер авто-разбивающего дерева может быть не минимальным. Возможен случай, когда размер BSP-дерева может составлять [math]\mathcal{O}(n^2) [/math], где [math] n = |S| [/math].

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

Предположим, что мы построили BSP-дерево [math]T[/math] для множества объектов [math]S[/math] в трехмерном пространстве. Как нам следует использовать его, чтобы получить порядок глубины для алгоритма художника?

Пусть [math]p_{view}[/math] — точка обзора, и она лежит над разбивающей плоскостью, хранимой в корне [math]T[/math].

Тогда ни один из объектов, лежащих под этой плоскостью, не может перекрыть ни один из объектов, лежащих выше нее. Таким образом, мы можем безопасно отрисовать фрагменты объектов из поддерева [math]T^-[/math] до отрисовки объектов из поддерва [math]T^+[/math]. Порядок фрагментов объектов в поддеревьях определяется таким же способом.

void painters_algorithm([math]T[/math], [math]p_{view}[/math]):
    [math]v \leftarrow T.root[/math]
    if [math]v[/math] — лист
        отрисовать фрагменты объектов из [math]S(v)[/math]
    else if [math]p_{view} \in h_v^+[/math]
        painters_algorithm([math]T^-[/math], [math]p_{view}[/math])
        отрисовать фрагменты объектов из [math]S(v)[/math]
        painters_algorithm([math]T^+[/math], [math]p_{view}[/math])
    else if [math]p_{view} \in h_v^-[/math]
        painters_algorithm([math]T^+[/math], [math]p_{view}[/math])
        отрисовать фрагменты объектов из [math]S(v)[/math]
        painters_algorithm([math]T^-[/math], [math]p_{view}[/math])
    else /∗ [math]p_{view} \in h_v[/math] ∗/
        painters_algorithm([math]T^+[/math], [math]p_{view}[/math])
        painters_algorithm([math]T^-[/math], [math]p_{view}[/math])

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

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

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

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

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

Пусть [math]S[/math] — множество из [math]n[/math] непересекающихся отрезков на плоскости. Ограничимся авто-разбиением, рассматривая только прямые, содержащие один из отрезков.

Пусть [math]l(s)[/math] — прямая, содержащая отрезок [math]s[/math].

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

BSPTree 2D_BSP_tree([math]S[/math]):
    if [math]|S| \leqslant 1[/math]
        [math]T \leftarrow[/math] BSPTree([math]S[/math]) /* [math]T[/math] будет листом, в котором хранится данное множество */
        return [math]T[/math]
    else  /* используем [math]l(s_1)[/math] как разбивающую прямую */</tex>
        [math]S^+ \leftarrow \{s \cap l^+(s_1) \mid s \in S\}[/math]
        [math]T^+ \leftarrow[/math] 2D_BSP_tree([math]S^+[/math])
        [math]S^- \leftarrow \{s \cap l^-(s_1) \mid s \in S\}[/math] 
        [math]T^- \leftarrow[/math] 2D_BSP_tree([math]S^-[/math])
        [math]S_v \leftarrow \{s \in S \mid s \subset l(s_1)\}[/math]
        [math]T \leftarrow[/math] BSPTree([math]S_v,\ T^-,\ T^+[/math]) 
        // создаем BSP-дерево c корнем в вершине [math]v[/math], левым поддеревом [math]T^-[/math] и правым поддеревом [math]T^+[/math] 
        // и множеством хранимых объектов [math]S_v[/math]
        return [math]T[/math]                 

Данный алгоритм создает BSP-дерево для множества [math]S[/math], но как уже известно, оно не будет наименьшим в общем случае.

Необходимо придумать стратегию выбора прямой разбиения, а не просто брать [math]l(s_1)[/math]. Возможным подходом является выбор отрезка [math]s \in S[/math], такого что [math]l(s)[/math] пересекает наименьшее число отрезков. Но такой жадный алгоритм работает не на всех конфигурациях отрезков. Кроме того, поиск такого отрезка — занятие затратное.

Как и в других алгоритмах, когда нужно сделать сложный выбор, сделаем рандомный выбор. Это означает, что для разбиения мы будем использовать случайно выбранный отрезок. Для этого перед тем, как начинать построение дерева, расположим отрезки в [math]S[/math] случайном порядке.

void 2D_random_BSP_tree([math]S[/math]): 
    [math]S \leftarrow [/math] random_permutation([math]S[/math])
    [math]T \leftarrow [/math] 2D_BSP_tree([math]S[/math])
    return [math]T[/math]

Перед анализированием рандомизированного алгоритма рассмотрим одну простую оптимизацию.

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

Bsp free.png

Рассмотрим одну из таких граней [math]f[/math]. В [math]S[/math] могут быть отрезки, которые полностью пересекают [math]f[/math]. Выбор одного из таких отрезков для разбиения [math]f[/math] не вызовет фрагментации других отрезков внутри [math]f[/math], так как данный отрезок исключается из дальнейшего рассмотрения. Назовем такое свободным разбиением.

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

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

Bsp three segments.png

В качестве примера рассмотрим три отрезка, изображенные на рисунке. Если они рассматриваются в порядке (a), то мы получаем пять фрагментов, если же в порядке (b) — то всего три фрагмента.

Так как размер BSP-дерева зависит от сгенерированной перестановки, будем анализировать ожидаемый размер BSP-дерева — средний размер для всех [math]n![/math] перестановок.

Лемма:
Ожидаемое число фрагментов, сгенерированных алгоритмом 2D_random_BSP_tree есть [math]\mathcal{O}(n \log n)[/math].
Доказательство:
[math]\triangleright[/math]

Пусть [math]s_i[/math] — фиксированный отрезок из [math]S[/math]. Проанализируем ожидаемое количество отрезков, которые мы разрежем, когда [math]l(s_i)[/math] будет добавлена алгоритмом как следующая разбивающая прямая.

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

В частности, когда прямая, пересекающая такой отрезок, добавляется раньше [math]l(s_i)[/math], она закрывает [math]s_j[/math] от [math]s_i[/math]. На рисунке (b) так происходит с отрезком [math]s_3[/math], который защищен отрезком [math]s_1[/math] от [math]s_2[/math].

Эти размышления приводят нас к определению расстояния от какого-то отрезка до фиксированного отрезка [math]s_i[/math].

Bsp dist.png

[math] \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. [/math]

Для всех конечных расстояний до отрезка [math]s_i[/math] может быть только два отрезка с одинаковым расстоянием — те, что лежат по разные стороны от [math]s_i[/math].

Пусть [math]k = \mathrm{dist}(s_i, s_j)[/math] и [math]s_{j_1},\ s_{j_2},\ \ldots ,\ s_{j_k}[/math] — отрезки между [math]s_i[/math] и [math]s_j[/math].

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

Так как отрезки расположены в случайном порядке, получаем: [math]P(l(s_i) \cap s_j \ne \varnothing) \leqslant \genfrac{}{}{}{0}{1}{k + 2}[/math]

Существуют отрезки, которые не разрезаются [math]l(s_i)[/math], но расширение которых защитит [math]s_j[/math], так что выше записано неравенство.

Теперь мы можем ограничить ожидаемое число разрезов, происходящих при добавлении [math]s_i[/math]:

[math]E([/math]число разрезов, происходящих при добавлении [math]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[/math].

По линейности ожиданий мы можем заключить, что ожидаемое число разрезов, вызванных добавлением всех отрезков составляет не более [math]2n\log n[/math]. Так как изначально даны [math]n[/math] отрезков, ожидаемое число фрагментов ограничено [math]n + 2n\log n[/math].
[math]\triangleleft[/math]

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

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

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

Теорема:
В двумерном пространстве BSP-дерево размера [math]\mathcal{O}(n\log n)[/math] может быть построено за ожидаемое время [math]\mathcal{O}(n^2\log n)[/math].

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

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

Снова ограничимся только авто-разбиениями, разбивая пространство плоскостями, содержащими какой-то из треугольников.

Для треугольника [math]t[/math] обозначим плоскость, содержащую его, как [math]h(t)[/math]. На вход алгоритму подается множество треугольников [math]S = \{t_1,\ t_2,\ \dots ,\ t_n\}[/math], заданных в трехмерном пространстве.

BSPTree 3D_BSP_tree([math]S[/math]):
    if [math]|S| \leqslant 1[/math]
        [math]T \leftarrow[/math] BSPTree([math]S[/math]) /* [math]T[/math] будет листом, в котором хранится данное множество */
        return [math]T[/math]
    else /* используем [math]h(t_1)[/math] как разбивающую плоскость */
        [math]S^+ \leftarrow \{t \cap h^+(t_1) \mid t \in S\}[/math]
        [math]T^+ \leftarrow[/math] 3D_BSP_tree([math]S^+[/math])
        [math]S^- \leftarrow \{t \cap h^-(t_1) \mid t \in S\}[/math]
        [math]T^- \leftarrow[/math] 3D_BSP_tree([math]S^-[/math])
        [math]S_v \leftarrow \{t \in S \mid t \subset h(t_1)\}[/math]
        [math]T \leftarrow[/math] BSPTree([math]S_v,\ T^-,\ T^+[/math]) 
        // создаем BSP-дерево c корнем в вершине [math]v[/math], левым поддеревом [math]T^-[/math] и правым поддеревом [math]T^+[/math] 
        // и множеством хранимых объектов [math]S_v[/math]
        return [math]T[/math]

Размер полученного 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.