Изменения
→Определение
== Определение ==
Чтобы понять, что из себя представляет BSP-дерево, рассмотрим рисунок. На нем показано двоичное разбиение множества объектов на плоскости и дерево, которое этому разбиению соответствует.
BSP строится с помощью рекурсивного разбиения плоскости прямыми. В данном примере это происходит так: сначала проводим прямую l1, затем разбиваем полуплоскость выше l1 прямой l2, а ниже {{---}} прямой l3 и так далее.
Прямые разбивают на фрагменты не только плоскость, но и объекты, расположенные на ней. Разбиение продолжается до тех пор, пока внутри каждого фрагмента плоскости окажется не более одного фрагмента объекта.
Этот процесс можно представить с помощью двоичного дерева. Каждый лист дерева соответствует фейсу грани разбиения, в нем хранится фрагмент объекта, находящийся внутри этого фейсаэтой грани. Каждый узел дерева соответсвует разбивающей прямой, которая хранится в этом узле.
Если сцене присутствуют 1D-объекты (отрезки), то они могут лежать на прямой разбиения, в таком случае соответсвующий узел хранит их в листьях.
Рассмотрим гиперплоскость <tex>h: a_1*x_1 + a_2*x_2 + ... + a_d*x_d + a_{d + 1} = 0</tex>.
Пусть <tex>h^+ </tex> {{---}} положительная полуплоскость, а <tex>h^- </tex> {{---}} отрицательная:
<tex>h^+ = {(x_1, x_2 ... x_d) : a_1*x_1 + a_2*x_2 + ... + a_d*x_d + a_{d + 1} > 0}</tex>
<tex>h^- = {(x_1, x_2 ... x_d) : a_1*x_1 + a_2*x_2 + ... + a_d*x_d + a_{d + 1} < 0}</tex>
Пусть <tex>S </tex> {{- --}} множество объектов, для которого мы строим забиение в d-мерном пространстве.
Пусть <tex>v </tex> {{- --}} какая-то вершина дерева, тогда обозначим <tex>S(v) </tex> множество объектов (возможно пустое), хранимых в этой вершине.
BSP-дерево <tex>T </tex> для этого множества обектов обладает следующими свойствами:*Если <tex>|S| <= 1</tex>, то <tex>T </tex> {{--- }} лист. Фрагмент объекта в S, если он существует, хранится в этом листе.*Если <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 : s \in S}</tex>. * правый ребенок <tex>v </tex> является корнем BSP дерева <tex>T^+ </tex> на множестве объектов <tex>S^+ = {h_v^+ \пересечь cap s : s \in S}</tex>.
Размер BSP-дерева равен суммарному размеру множеств во всех узлах. То есть, размер BSP-дерева {{- --}} это число фрагментов, на которые были разбиты объекты. Так как BSP-дерево не содержит бесполезные прямые (прямые, которые разбивают пустой фейспустую грань), то количество узлов пропорционально размеру дерева.
В общем-то размер BSP-дерева ни о чем не говорит, так как мы не знаем ничего об объеме памяти, требуемой для его хранения, так как оно ничего не говорит об объеме памяти, требуемом для храния фрагмента объекта.
Но размер BSP-дерева {{- --}} неплохая мера для сравнения качества разных BSP-деревьев для данного множества объектов.
И еще рисунок про соответсвие нодов и регионов.
Листья BSP-дерева соответствуют фейсамграням, то есть мы можем каждой вершине v сопоставить полигональную область на плоскости, которая определяется как пересечение полуплоскостей h_mu<tex>h_{\mu}^ромбик{\Diamond}</tex>, где <tex>\mu </tex> {{- --}} предок <tex>v</tex>, а ромбик <tex>\Diamond</tex> = {-, если <tex>v </tex> {{---}} левый ребенок; +, если <tex>v </tex> {{---}} правый ребенок}
Корню дерева соответсвует все пространство.
Таким образом, серая область на рисунке соответствует региону <tex>l_1^+ \пересечь cap l_2^+ \пересечь cap l_3^+</tex>.
При построении BSP-дерева могут использоваться любые разбивающие гиперплоскости. В целях упрощения вычислений может быть удобно ограничить множество доступных разбивающих гиперплоскостей.
