Двоичное разбиение пространства (англ. binary space partitioning) — метод рекурсивного разбиения евклидова пространства в выпуклые множества и гиперплоскости. В результате объекты получают представление в виде структуры данных, называемой BSP-деревом.
BSP-дерево используется для эффективного выполнения следующих операций в трёхмерной компьютерной графике:
BSP-деревья были впервые применены специалистами компании LucasArts в начале 80-х годов. Популярность у разработчиков они завоевали благодаря компании id Software, разработавшей движки Doom (1993) и Quake (1996).
В BSP-дереве каждый узел связан с разбивающей прямой или плоскостью в 2-мерном или 3-мерном пространстве соответственно. При этом все объекты, лежащие с фронтальной стороны плоскости, относятся к фронтальному поддереву, а все объекты, лежащие с оборотной стороны плоскости, относятся к оборотному поддереву. Для определения принадлежности объекта к фронтальной или оборотной стороне разбивающей прямой или плоскости необходимо исследовать положение каждой его точки. Положение точки относительно плоскости определяется скалярным произведением нормали плоскости и координат точки в однородных координатах. Возможно три случая:
Если для всех точек объекта скалярное произведение больше или равно 0, то он относится к фронтальному поддереву. Если для всех точек объекта скалярное произведение меньше или равно 0, то он относится к оборотному поддереву. Если для всех точек объекта скалярное произведение равно 0, то не играет роли, к какому поддереву он принадлежит. Если скалярные произведения для точек объекта имеют разный знак, то он рассекается разбивающей плоскостью так, чтобы полученные объекты лежали только с фронтальной или только с оборотной стороны. Для каждого подузла BSP-дерева справедливо вышеприведенное утверждение, с тем исключением, что рассмотрению подлежат только те объекты, которые принадлежат к фронтальной или оборотной стороне разбивающей плоскости родительского узла.
Вышеприведенное определение описывает только свойства BSP-дерева, но не говорит как его построить. Как правило, BSP-дерево строится для набора отрезков на плоскости или полигонов в пространстве, представляющих некоторую фигуру или сцену. Рассмотрим алгоритм построения BSP-дерева для набора полигонов в пространстве: