Изменения

=== Алгоритм z-буфера (z-buffer algorithm) ===Для удаления невидимых частей объектов существует простой, но длительный метод {{--- }} алгоритм z-буфера.

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

=== Алгоритм художника (painter's algorithm) ===[[Файл:painters_algo.png|500px|right]]Алгоритм художника избегает дополнительных затрат памяти, изначально сортируя объекты по расстоянию от них до точки обзора. Тогда объекты проверяются в так называемом порядке глубины, начиная от самого дальнего. В таком случае при проверке рассмотрении объекта уже не нужна проверка его z-координаты, мы всегда пишем цвет в буфер кадра. Значения, хранимые в буфере ранее , просто перезаписываются.

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

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

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

== Определение ==Чтобы понять, что из себя представляет BSP-дерево, рассмотрим рисунок. На нем показано двоичное разбиение множества объектов на плоскости и дерево, которое этому разбиению соответствует.BSP строится с помощью рекурсивного разбиения плоскости прямыми: сначала l1, затем разбиваем полуплоскость выше l1 прямой l2, а ниже - прямой l3 и так далее.Прямые разбивают на фрагменты не только плоскость, но и объекты, расположенные на ней. Разбиение продолжается до тех пор, пока внутри каждого фрагмента плоскости окажется не более одного фрагмента объекта.Этот процесс Данную задачу можно представить с помощью элегантно решить при помощи техники '''двоичного дерева. Каждый лист дерева соответствует фейсу разбиения, в нем хранится фрагмент объекта, находящийся внутри этого фейсапространства''' (англ. Каждый узел дерева соответсвует разбивающей прямой''binary space partitioning, которая хранится в этом узле.Если сцене присутствуют 1D-объекты (отрезкиBSP''), то они могут лежать на прямой разбиения, в таком случае соответсвующий узел хранит их в листьях.

Рассмотрим гиперплоскость h: a_1*x_1 + a_2*x_2 + ... + a_d*x_d + a_{d + 1} = 0.= Структура BSP-дерева ==Пусть h^+ - положительная полуплоскостьЧтобы понять, а h^- - отрицательная:h^+ = {(x_1что из себя представляет двоичное разбиение пространства, x_2 рассмотрим рисунок.На нем показано двоичное разбиение множества объектов на плоскости и дерево, которое этому разбиению соответствует.В двумерном случае BSP строится с помощью рекурсивного разбиения плоскости прямыми. x_d) В данном примере это происходит так: a_1*x_1 + a_2*x_2 + ... + a_d*x_d + a_{d + 1} сначала проводим прямую <tex>l_1</tex>, разбивая полуплоскость выше <tex>l_1</tex> прямой <tex>l_2</tex> 0}h^- = , а ниже {(x_1, x_2 ... x_d) : a_1*x_1 + a_2*x_2 + ... + a_d*x_d + a_{d + 1---}} прямой <tex>l_3< 0}/tex> и так далее.

Пусть S - множество объектов, для которого мы строим забиение в d-мерном пространстве[[Файл:bsp_plane1.Пусть v - какая-то вершина дерева, тогда обозначим S(v) множество объектов (возможно пустое), хранимых в этой вершине.BSP-дерево T для этого множества обектов обладает следующими свойствамиpng|300px]][[Файл:*Если |S| <= 1, то T - лист. Фрагмент объекта в S, если он существует, хранится в этом листеbsp_tree1.*Если png|S| > 1, то в корне дерева v хранится гиперплоскость h_v и множество S(v) объектов, которые полностью содержатся в h_v. * левый ребенок v является корнем BSP дерева T^- на множестве объектов S^- = {h_v^- \пересечь s : s \in S} * правый ребенок v является корнем BSP дерева T^+ на множестве объектов S^+ = {h_v^+ \пересечь s : s \in S}300px]]

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

И еще рисунок про соответсвие нодов Этот процесс можно представить с помощью двоичного дерева. Каждый лист дерева соответствует грани разбиения, в нем хранится фрагмент объекта, находящийся внутри этой грани. Каждый узел дерева соответсвует разбивающей прямой, которая хранится в этом узле.{{Определение| definition = '''BSP-дерево''' (англ. ''binary space partition tree'') {{---}} дерево, отвечающее заданному двоичному разбиению пространства.}}Опишем подробней свойства 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-дерево не содержит бесполезные прямые (прямые, которые разбивают пустую грань), то количество узлов пропорционально размеру дерева. [[Файл:bsp_plane2.png|300px]][[Файл:bsp_tree2.png|300px]] Листья BSP-дерева соответствуют граням, то есть мы можем каждой вершине <tex>v</tex> сопоставить полигональную область на плоскости, которая определяется как пересечение полуплоскостей <tex>h_{\mu}^{\Diamond}</tex>, где <tex>\mu</tex> {{---}} предок <tex>v</tex>, и регионов <tex> \Diamond = \left\{\begin{array}{llcl}- & \mathrm{if}\ v\ - \ \mathrm{left}\ \mathrm{child} \\+ & \mathrm{if}\ v\ - \ \mathrm{right}\ \mathrm{child} \\\end{array}\right.</tex>

Таким образом, серая область на рисунке соответствует региону <tex>l_1^+ \cap l_2^+ \cap l_3^-</tex>. При построении BSP-дерева могут использоваться любые разбивающие гиперплоскости. В целях упрощения вычислений может быть удобно ограничить множество доступных разбивающих гиперплоскостей. Обычно используют авто-разбиения.Обычно ограничивают следующим образом:{{ОпределениеПредположим, что мы хотим построить BSP-дерево | definition = В двумерном случае для множества отрезков на плоскости. Очевидноразбиение, в котором используются разбивающие прямые, что лучшими кандидатами разбивающих прямых являются продолжения проходящие через один из данных отрезков. BSP-дерево, которое использует разбивающие прямые только такого вида, называется '''авто-разбивающим''' (англ. ''auto-partition''). Для множества плоских полигонов в трехмерном пространстве }} В трёхмерном случае авто-разбивающим является BSP-дерево, которое разбиение использует только полоскостиплоскости, на которых лежат данные полигоныкоторые содержат грани многогранников. [[Файл:bsp_n2.png|130px]] Но Как видно из рисунка, размер авто-разбивающие деревья деревья имеют минимальный разбивающего дерева может быть не минимальным. Возможен случай, когда размерBSP-дерева может составлять <tex>\mathcal{O}(n^2) </tex>, где <tex> n = |S| </tex>.

Предположим, что мы построили 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>, потому что они являются плоскими двумерными полигонами.

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

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

При решении задач Прежде чем переходить к задаче отрисовки сцены в трехмерном пространстве бывает полезно сначала рассмотреть трёхмерном случае, рассмотрим для простоты аналогичную задачу на плоскости, что мы и сделаем. Пусть <tex>S </tex> {{--- }} множество из <tex>n </tex> непересекающихся отрезков на плоскости. Ограничимся авто-разбиением, рассматривая только прямые, содержащие один из отрезков.  Пусть <tex>l(s) </tex> {{-- -}} прямая, содержащая отрезок <tex>s</tex>. На вход алгоритму подается <tex>S = \{s1s_1,\ s_2, s2\ \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> пересекает наименьшее число отрезков. Но такой жадный алгоритм работает не на всех конфигурациях отрезков. snКроме того, поиск такого отрезка {{---}} занятие затратное. Как и в других алгоритмах, когда нужно сделать сложный выбор, сделаем рандомный выбор. Это означает, что для разбиения мы будем использовать случайно выбранный отрезок. Для этого перед тем, как начинать построение дерева, расположим отрезки в <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- множество отрезковдерева.

BSPTree 2D_BSP_tree(S)[[Файл:bsp_free.png|300px|right]]if |Рассмотрим одну из таких граней <tex>f</tex>. В <tex>S| <= 1 then Create a tree T consisting of a single leaf node/tex> могут быть отрезки, where the set S is stored explicitlyкоторые полностью пересекают <tex>f</tex>. return T else Выбор одного из таких отрезков для разбиения <tex>f</* Use l(s1) as the splitting line *tex> не вызовет фрагментации других отрезков внутри <tex>f</ 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 νtex>, left subtree T−, right subtree T+, and with S(ν) = {s \in S : s \subset l(s1)}так как данный отрезок исключается из дальнейшего рассмотрения. Назовем такое свободным разбиением. return T

Понятно, что алгоритм создает BSP-дерево для множества S, но Нашей улучшенной стратегией будет ли оно наименьшим?Наверноеиспользование свободных разбиений везде, стоит тщательней выбирать прямую разбиениягде только можно, а не просто брать l(s1)и использование случайных разбиений в противном случае. Возможным подходом является выбор отрезка s \in SДля реализации данной оптимизации нужно уметь определять, такого что l(s) пересекает наименьшее число отрезковвызывает ли отрезок свободное разбиение.Но этот жадный алгоритмДля этого сопоставим каждому отрезку две булевых переменных, работает не на всех конфигурациях отрезков. Кроме тогокоторые покажут, поиск такого лежат ли правый и левый концы отрезка на какой- занятие затратноето из уже добавленных разбивающих прямых.Как и в других алгоритмахОбе переменных истинны, когда нужно сделать сложный выбор, просто выберем случайно. Это означает, что для разбиения мы будем использовать рандомный отрезок.Для этого расположим отрезки в S случайном порядке перед тем, как начинать построение деревавызывает свободное разбиение.

Теперь оценим производительность алгоритма '''2D_random_BSP_tree'''. Для упрощения рассуждений будем анализировать версию без свободных разбиений (Sасимптотической разницы между ними нет) Generate a random permutation S' = s1. Начнем с анализа размера BSP-дерева, равного числу полученных фрагментов, которое зависит от сгенерированной перестановки отрезков. . . Некоторые перестановки могут породить маленькие деревья, sn of the set Sа другие {{---}} большие. T \leftarrow 2D_BSP_tree(S�) return T

Перед тем, как анализировать рандомизированный алгоритм, отметим, что здесь возможна одна простая оптимизация. Предположим, что мы выбрали несколько первых разбивающих прямых. Эти прямые порождают разбиение плоскости, фейсы которой соответствуют каким-то узлам BSP-дерева. Рассмотрим одну из таких поверхностей f. В S могут быть отрезки, которые полностью пересекают f. Выбор одного из таких отрезков для разбиения f не вызовет фрагментации других отрезков внутри f, так как данный отрезок исключается из дальнейшего рассмотрения.Назовем такое свободным разбиением.Нашей улучшенной стратегией будет использование свободных разбиений везде, где только можно, и использование случайных разбиений в противном случае. Для реализации данной оптимизации нужно уметь определять, вызывает ли отрезок свободное разбиение.Для этого сопоставим каждому отрезку две булевых переменных, которые покажут, лежат ли правый и левый концы отрезка на какой-то из уже добавленных разбивающих прямых.Обе переменных истинны, когда отрезок вызывает свободное разбиение[[Файл:bsp_three_segments.png|500px]]

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

Теперь проанализируем время работы алгоритма. Понятно, что оно зависит от используемой перестановки, так что опять рассмотрим ожидаемое время работы. Нахождение рандомной перестановки занимает <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