Изменения

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

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

== Определение Структура BSP-дерева ==

В двумерном случае BSP строится с помощью рекурсивного разбиения плоскости прямыми. В данном примере это происходит так: сначала проводим прямую l1<tex>l_1</tex>, затем разбиваем разбивая полуплоскость выше l1 <tex>l_1</tex> прямой l2<tex>l_2</tex>, а ниже {{---}} прямой l3 <tex>l_3</tex> и так далее.

[[Файл:bsp_plane1.png|300px]][[Файл:bsp_tree1.png|300px]] Прямые разбивают на фрагменты части не только плоскость, но и объекты, расположенные на ней. Разбиение продолжается до тех пор, пока внутри каждого фрагмента каждой грани плоскости окажется не более одного фрагмента объекта.

Если сцене присутствуют 1D{{Определение| 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> множество объектов (возможно пустое), хранимых в этой вершине.

*Если <tex>|S| <= \leqslant 1</tex>, то <tex>T</tex> {{---}} лист. Фрагмент объекта в <tex>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>.

{{Определение| definition = '''Двоично разбивающее пространство дерево''' (англ. ''binary space partition tree'') или '''BSP-дерево''' {{---}} структура данных, хранящая множество объектов на плоскости, рекурсивно разбитой прямыми.}}Размер BSP-дерева равен суммарному размеру множеств во всех узлах. То естьДругими словами, размер BSP-дерева {{---}} это число фрагментов, на которые были разбиты объекты. Так как BSP-дерево не содержит бесполезные прямые (прямые, которые разбивают пустую грань), то количество узлов пропорционально размеру дерева. [[Файл:bsp_plane2.png|300px]][[Файл:bsp_tree2.png|300px]]

В общем-то размер Листья BSP-дерева ни о чем не говоритсоответствуют граням, так как то есть мы не знаем ничего об объеме памяти, требуемой для его храненияможем каждой вершине <tex>v</tex> сопоставить полигональную область на плоскости, так которая определяется как оно ничего не говорит об объеме памятипересечение полуплоскостей <tex>h_{\mu}^{\Diamond}</tex>, требуемом для храния фрагмента объекта.Но размер BSP-дерева где <tex>\mu</tex> {{---}} неплохая мера для сравнения качества разных BSP-деревьев для данного множества объектов.предок <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>.

| definition = В двухмерном двумерном случае для множества отрезков разбиение, в котором используются разбивающие прямые, проходящие через один из данных отрезков, называется '''авто-разбивающим'''(англ. }}{{Определение| definition = В трехмерном случае для множества полигонов разбиение, в котором используются разбивающие плоскости, проходящие через одну из данных плоскостей, называется '''автоauto-разбивающим'''. }}{{Определение| definition = BSP-дерево, построенное с применением авто-разбиения, называются '''авто-разбивающим'partition'').

АвтоВ трёхмерном случае авто-разбивающие деревья деревья имеют минимальный разбиение использует плоскости, которые содержат грани многогранников. [[Файл:bsp_n2.png|130px]] Как видно из рисунка, размеравто-разбивающего дерева может быть не минимальным. Возможен случай, когда размер BSP-дерева может составлять <tex>\mathcal{O}(n^2) </tex>, где <tex> n = |S| </tex>.

<code> '''void''' painters_algorithm(<tex>T</tex>, <tex>p_{view}</tex>): <tex>v \leftarrow T.root</tex> '''if ''' <tex>v</tex> is a leaf{{---}} лист отрисовать фрагменты объектов из <tex>S(v)</tex>. '''else if ''' <tex>p_{view} \in h_v^+</tex> painters_algorithm(<tex>T^-</tex>, <tex>p_{view}</tex>) отрисовать фрагменты объектов из <tex>S(v)</tex>. painters_algorithm(<tex>T^+</tex>, <tex>p_{view}</tex>) '''else if ''' <tex>p_{view} \in h_v^-</tex> painters_algorithm(<tex>T^+</tex>, <tex>p_{view}</tex>) отрисовать фрагменты объектов из <tex>S(v)</tex>. painters_algorithm(<tex>T^-</tex>, <tex>p_{view}</tex>) '''else ''' <font color="green">/∗ <tex>p_{view} \in h_v</tex> ∗/</font> painters_algorithm(<tex>T^+</tex>, <tex>p_{view}</tex>) painters_algorithm(<tex>T^-</tex>, <tex>p_{view}</tex>)</code> Заметим, что мы не рисуем объекты из <tex>S(v)</tex>, когда <tex>p_{view}</tex> лежит на разбивающей плоскости <tex>h_v</tex>, потому что они являются плоскими двумерными полигонами. Эффективность данного алгоритма, как и любого другого алгоритма для BSP-деревьев, зависит от размера BSP-дерева. То есть необходимо выбирать разбивающие плоскости таким образом, чтобы фрагментация объектов была минимальной.

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

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

Перед тем, как разрабатывать стратегии разбиения, которые порождают маленькие BSPПусть <tex>S</tex> {{---}} множество из <tex>n</tex> непересекающихся отрезков на плоскости. Ограничимся авто-деревьяразбиением, мы должны решитьрассматривая только прямые, какие типы объектов допустимысодержащие один из отрезков.

Мы заинтересовались BSP-деревьями потому, что нам нужена была быстрая реализация удаления скрытых поверхностей для симулятора полетов. Так как скорость Пусть <tex>l(s)</tex> {{---}} наша главная цель, мы должны упростить вид объектов нашего пейзажа: не будем использовать кривые поверхности, представив все с помощью полигонов.Предположимпрямая, что грани полигонов триангулированы, и мы хотим построить в трехмерном пространстве BSP-дерево наименьшего размера для данного множества треугольниковсодержащая отрезок <tex>s</tex>.

На вход алгоритму подается <tex>S =\{s_1,\ s_2,\ \dots ,\ s_n\}</tex> {{---}} множество отрезков. <code> '''BSPTree''' 2D_BSP_tree(<tex>S</tex>): '''if''' <tex>|S| \leqslant 1</tex> <tex>T \leftarrow</tex> '''BSPTree'''(<tex>S</tex>) <font color="green">/* <tex>T</tex> будет листом, в котором хранится данное множество */</font> '''return''' <tex>T</tex> '''else''' <font color="green">/* используем <tex>l(s_1)</tex> как разбивающую прямую */</tex></font> <tex>S^+ \leftarrow \{s \cap l^+(s_1) \mid s \in S\}</tex> <tex>T^+ \leftarrow</tex> 2D_BSP_tree(<tex>S^+</tex>) <tex>S^- \leftarrow \{s \cap l^-(s_1) \mid s \in S\}</tex> <tex>T^- \leftarrow</tex> 2D_BSP_tree(<tex>S^-</tex>) <tex>S_v \leftarrow \{s \in S \mid s \subset l(s_1)\}</tex> <tex>T \leftarrow</tex> '''BSPTree'''(<tex>S_v,\ T^-,\ T^+</tex>) <font color= Построение "green">// создаем BSP-дерева =дерево c корнем в вершине <tex>v</tex>, левым поддеревом <tex>T^-</tex> и правым поддеревом <tex>T^+</tex> </font> <font color="green">// и множеством хранимых объектов <tex>S_v</tex></font> '''return''' <tex>T</tex> </code>При решении задач Данный алгоритм создает BSP-дерево для множества <tex>S</tex>, но как уже известно, оно не будет наименьшим в трехмерном пространстве бывает полезно сначала рассмотреть задачу общем случае. Необходимо придумать стратегию выбора прямой разбиения, а не просто брать <tex>l(s_1)</tex>. Возможным подходом является выбор отрезка <tex>s \in S</tex>, такого что <tex>l(s)</tex> пересекает наименьшее число отрезков. Но такой жадный алгоритм работает не на плоскостивсех конфигурациях отрезков. Кроме того, поиск такого отрезка {{---}} занятие затратное. Как и в других алгоритмах, когда нужно сделать сложный выбор, сделаем рандомный выбор. Это означает, что для разбиения мы и сделаембудем использовать случайно выбранный отрезок. Для этого перед тем, как начинать построение дерева, расположим отрезки в <tex>S</tex> случайном порядке.Пусть <code> '''void''' 2D_random_BSP_tree(<tex>S</tex>): <tex>S \leftarrow </tex> random_permutation(<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>. Выбор одного из n непересекающихся таких отрезков для разбиения <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(ss_i) - </tex> будет добавлена алгоритмом как следующая разбивающая прямая. Рассмотрим рисунок и постараемся понять, содержащая разрезается ли отрезок s<tex>s_j</tex> при добавлении прямой <tex>l(s_i)</tex>, в зависимости от отрезков, которые разрезаны <tex>l(s_i)</tex>, но находятся между <tex>s_i</tex> и <tex>s_j</tex>.На вход алгоритму подается S = {s1В частности, когда прямая, пересекающая такой отрезок, s2добавляется раньше <tex>l(s_i)</tex>, она закрывает <tex>s_j</tex> от <tex>s_i</tex>.На рисунке (b) так происходит с отрезком <tex>s_3</tex>, который защищен отрезком <tex>s_1</tex> от <tex>s_2</tex>.. sn}  Эти размышления приводят нас к определению расстояния от какого- множество отрезковто отрезка до фиксированного отрезка <tex>s_i</tex>.

BSPTree 2D_BSP_tree(S)if [[Файл:bsp_dist.png|S300px| <= 1 then Create a tree T consisting of a single leaf node, where the set S is stored explicitly. return T else /* Use l(s1) as the splitting line */ S+ \leftarrow {s \пересечь l(s1)+ : s \in S}; T+ \leftarrow 2D_BSP_tree(S+); S− \leftarrow {s \пересечь l(s1)− : s ∈ S}; T− \leftarrow 2D_BSP_tree(S−); Create a BSP tree T with root node ν, left subtree T−, right subtree T+, and with S(ν) = {s \in S : s \subset l(s1)}. return T]]

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

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

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

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

<tex>P(l(s_i) разрезает \cap s_j\ne \varnothing) <= \leqslant \genfrac{}{}{}{0}{1 / (}{k + 2)}</tex> Так как существуют Существуют отрезки, которые не разрезаются <tex>l(s_i)</tex>, но расширение которых защитит <tex>s_j</tex>, так что выше записано неравенство. Теперь мы можем ограничить ожидаемое число разрезов, происходящих при добавлении <tex>s_i</tex>: <tex>E(</tex>число разрезов, происходящих при добавлении <tex>s_i) <= \leqslant \sum(\limits_{j \ne i != j, } \genfrac{}{}{}{0}{1 / }{\mathrm{dist}(k s_i, s_j) + 2)) <= } \leqslant 2 * \cdot \sum(\limits_{k=0..}^{n - 2, } \genfrac{}{}{}{0}{1/ (}{k + 2)) <= } \leqslant 2 * \ln n</tex>. По линейности ожиданий мы можем заключить, что ожидаемое число разрезов, вызванных добавлением всех отрезков составляет не более 2nlogn<tex>2n\log n</tex>.Так как изначально даны <tex>n </tex> отрезков, ожидаемое число фрагментов ограничено <tex>n + 2nlogn2n\log n</tex>.}} Было показано, что ожидаемый размер BSP-дерева, построенного с помощью алгоритма '''2D_random_BSP_tree''', составляет <tex>n + 2n\log n</tex>. Следовательно, мы доказали, что BSP-дерево размера <tex>n + 2n\log n</tex> существует для любого множества <tex>n</tex> отрезков. Кроме того, хотя бы половина перестановок приводит к BSP-дереву размера <tex>n + 4n\log n</tex>.

Теперь проанализируем время работы алгоритма. Понятно, что оно зависит от используемой перестановки, так что опять рассмотрим ожидаемое время работы. Нахождение рандомной перестановки занимает <tex>\mathcal{O}(n)</tex> при помощи [[Метод генерации случайной перестановки, алгоритм Фишера-Йетса |алгоритма Фишера-Йетса]]. Если проигнорировать время рекурсивных вызовов, то время работы алгоритма линейно от количества фрагментов в <tex>S</tex>. Это число не превышает <tex>n</tex>, так как становится меньше с каждым рекурсивным вызовом.Число рекурсивных вызовов ограничено количеством сгенерированных фрагментов, которое составляет <tex>\mathcal{O}(nlognn\log n)</tex>. Таким образом, время построения дерева составляет <tex>\mathcal{O}(n^2\log n)</tex>. {{Теорема| statement = В двумерном пространстве BSP-дерево размера <tex>\mathcal{O}(n\log n)</tex> может быть построено за ожидаемое время <tex>\mathcal{O}(n^2logn2\log n)</tex>.}} Описанный выше алгоритм легко обобщается на трёхмерное пространство. Как было упомянуто выше, мы считаем, что работаем в 3D с триангуляцией граней многранников. Пусть <tex>S</tex> {{---}} множество непересекающихся треугольков в <tex>\mathbb{R}^3</tex>.  Снова ограничимся только авто-разбиениями, разбивая пространство плоскостями, содержащими какой-то из треугольников. Для треугольника <tex>t</tex> обозначим плоскость, содержащую его, как <tex>h(t)</tex>.На вход алгоритму подается множество треугольников <tex>S = \{t_1,\ t_2,\ \dots ,\ t_n\}</tex>, заданных в трехмерном пространстве.

Теорема. '''BSPTree''' 3D_BSP_tree(<tex>S</tex>): '''if''' <tex>|S| \leqslant 1</tex> <tex>T \leftarrow</tex> '''BSPTree'''(<tex>S</tex>) <font color="green">/* <tex>T</tex> будет листом, в котором хранится данное множество */</font> '''return''' <tex>T</tex> '''else''' <font color="green">/* используем <tex>h(t_1)</tex> как разбивающую плоскость */</font> <tex>S^+ \leftarrow \{t \cap h^+(t_1) \mid t \in S\}</tex> <tex>T^+ \leftarrow</tex> 3D_BSP_tree(<tex>S^+</tex>)BSP <tex>S^- \leftarrow \{t \cap h^-(t_1) \mid t \in S\}</tex> <tex>T^- \leftarrow</tex> 3D_BSP_tree(<tex>S^-дерево размера O</tex>) <tex>S_v \leftarrow \{t \in S \mid t \subset h(nlognt_1) может быть построено за ожидаемое время O\}</tex> <tex>T \leftarrow</tex> '''BSPTree'''(n<tex>S_v,\ T^2logn-,\ T^+</tex>) <font color="green">// создаем BSP-дерево c корнем в вершине <tex>v</tex>, левым поддеревом <tex>T^-</tex> и правым поддеревом <tex>T^+</tex> </font> <font color="green">// и множеством хранимых объектов <tex>S_v</tex></font> '''return''' <tex>T</tex>

Описанный выше алгоритм легко распространяется с двухмерного пространства на трехмерное. Пусть S Размер полученного BSP- множество непересекающихся треугольков в R^3. Снова ограничимся только авто-разбиениями, разбивая пространство плоскостями, содержащими какой-то из дерева снова зависит от порядка треугольников.Для треугольника t обозначим плоскостьКак и в двумерном случае, содержащую егомы можем попытаться получить хороший ожидаемый размер дерева, как h(t)переставив треугольники в случайном порядке.На вход алгоритму подается множество треугольников S = {t1, t2, . . . ,tn}, заданных в трехмерном пространствепрактике это дает хорошие результаты.

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