Изменения
Нет описания правки
Чтобы использовать этот алгоритм в реальной жизни, например, в симуляторе полета, мы должны предпосчитать сцену так, чтобы можно было быстро найти корректный порядок отображения объектов для любой точки обзора.
Элегантная структура данных, которая позволяет это сделать {{---}} '''двоичное разбиение пространства''' или '''BSP-двоично разбивающее пространство дерево'''.
== Определение ==
{{Определение
| definition = '''Двоично разбивающее пространство дерево''' (англ. ''binary space partition tree'') или '''BSP-дерево''' {{---}} структура данных, хранящая множество объектов на плоскости, рекурсивно разбитой прямыми.
}}
Чтобы понять, что из себя представляет 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>.
