Изменения

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

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

Чтобы понять, что из себя представляет двоичное разбиение пространства, рассмотрим рисунок. На нем показано двоичное разбиение множества объектов на плоскости и дерево, которое этому разбиению соответствует.

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

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

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

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

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

}}

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

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

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

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

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

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

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