Множество программных продуктов активно использует графику (это те же игры, CAD'ы и т.п.). При этом очень важна скорость и точность вывода на экран различных объектов. Может возникнуть вопрос: "Ну причем здесь точность?" Тем не менее, это тоже играет очень важную роль. Представим, что необходимо вывести на экран серию перекрывающих друг друга фигур. Тогда фигура, прорисованная последней, будет частично перекрывать некоторые из предыдущих. Но как в таком случае можно правильно изобразить две фигуры на рис.1? Эта задача весьма легко и элегантно решается с помощью BSP-дерева.

Рис.1

Другая задача, при решении которой BSP-дерево трудно заменить, это ускорение вывода на экран графической информации, что достигается путем радикального сокращения объема выводимых данных.

А что представляет собой BSP-дерево?

Что это такое

Заранее оговорюсь о термине "гиперплоскость". В данном случае гиперплоскость в n-мерном пространстве - это некий (n-1)-мерный объект, который может быть использован для разделения участка пространства на два полупространства. К примеру, в трехмерном пространстве это плоскость, в двухмерном - прямая, в одномерном - точка.

В дословном переводе Binary Space Partitioning Tree - это "двоичное дерево для разбиения пространства (разбивающее пространство)". Вообще, BSP-дерево представляет собой структуру, показывающую рекурсивное, иерархическое деление n-мерного пространства на выпуклые подпространства с помощью гиперплоскостей.

Легче всего понять, что такое BSP-дерево, если ограничить разговор двумя измерениями. Мы будем строить дерево для фигуры (рис.2).

Рис.2

Для разбиения пространства возьмем прямые параллельные оси Х или оси Y и с каждым шагом будем делить пространство пополам. Теперь взгляните на рис.3, там показано несколько шагов построения дерева.

Рис.3

Мы взяли квадрат произвольных размеров где-то на плоскости, разделили его пополам прямой, проведенной перпендикулярно оси Х. Потом выбрали прямую иного направления (по нашей договоренности это прямая, перпендикулярная оси Y) и повторили ту же операцию. Процесс может продолжаться до тех пор, пока деление станет невозможным.

На каждом "уровне" дерева хранятся координаты секущей гиперплоскости (у нас это прямые) и угол наклона. В некоторых случаях там также могут оказаться и целые элементы изображения.

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

Применение BSP-дерева

Теперь вернемся к фигурам на рис.1. Как их все же нарисовать? Очевидно, что если сначала изобразить фигуру А, а затем фигуру В (или наоборот), то мы не добьемся желаемого результата.

Для правильной обработки эти фигуры должны быть разбиты на несколько более мелких (рис.4).

Рис.4

Здесь как раз и проявляется вся прелесть BSP-дерева, так как подобное разбиение осуществляется автоматически при создании дерева. Теперь только остается идти от корня дерева (т.е. сначала изображать ближайшие к глазу предметы) все ниже и ниже - до тех пор, пока экран не заполнится или не закончится дерево. Также, если элемент дерева указывает на то, что необходимо заполнить уже прорисованную область, то обработка данной ветви BSP-дерева далее просто не производится. Объем выводимой информации сильно сокращается.

С небольшими доработками такой алгоритм используется и для динамических (перемещающихся) объектов (3D-игpы и т.п.)

Остановимся на DOOM'e. Когда кто-нибудь создает уровень в редакторе уровней, то он рисует его в двухмерном пространстве. Все линии, формирующие уровень, образуют замкнутые многоугольники. Когда созданный уровень сохраняют, то к нему автоматически добавляется новая информация. В частности, для уровня создается BSP-дерево. В процессе его создания уровень разбивается на подсекторы. Имея точку на двухмерной игровой карте, программа рендеринга определяет с помощью BSP-дерева ближайшие к игроку и попадающие в его поле зрения подсекторы и начинает заполнение экрана по вышеупомянутому методу. Перед этим перемещающиеся объекты вставляются в дерево и, в результате, отображаются обычным способом. Как только экран заполнен, программа рендеринга прекращает дальнейшую обработку данной ветви. Производительность программы таким образом повышается во много раз.

BSP-дерево - это гибкий и мощный инструмент, который использует множество программ. Его применение позволяет резко сократить необходимый объем вычислений, а следовательно, и затраты времени. А вpемя - это деньги!

Андрей КОНОНОВИЧ