Компьютерная Графика и Мультимедиа Сетевой журнал

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

BSP-Деревья

Введение

Двоичное разбиение пространства (BSP - binary space partition) - это метод, который впервые был сформулирован в 1969 году [1]. Изначально предлагалось использовать метод для сортировки полигонов в сцене. В то время отсутствовала аппаратная поддержка буфера грубины (z-buffer), а программная реализация была слишком медленной. Однако метод двоичного разбиения пространства остался актуальным даже после создания аппаратного z-buffer-а (поскольку, к сожалению, метод z-buffer-а не решает многих проблем, например, отображение полупрозрачных объектов). Кроме сортировки, метод широко применяется и в других областях, к примеру, проверка на столкновение, в некоторых алгоритмах компьютерных сетей, в методе излучательности.

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

Алгоритм двоичного разбиения пространства 

Принцип работы алгоритма заключается в том, что все полигоны пространства (в общем случае n-мерного) разбиваются на группы, лежащие в разных выпуклых подпространствах относительно некоторой гиперплоскости (гиперплоскость - это пространство размерности n-1). Не нарушая общности рассуждений будем рассматривать 2-хмерное простраство (далее сделаем некоторые поправки для 3-хмерного пространства). В этом случае гиперплоскость будет представлять собой прямую линию. Для наглядности рассмотрим пример (Рис. 1):

Рис.1

У нас есть плоскость (пространство), на которой расположены отрезки (участки гиперплоскостей) с заданными нормалями. Первым этапом алгоритма является определение разделяющей плоскость прямой. Далее будут приведены основные приёмы выбора гиперплоскости, а пока, не вдаваясь в подробности, будем выбирать произвольный отрезок (например, отрезок "b") и дополнять его до прямой - это и будет наша гиперплоскость (Рис.2):

Рис.2

Благодаря прямой, мы получили плоскость, разбитую на две полуплоскости. Нормаль к прямой совпадает с нормалью отрезка, через который она проведена. По направлению нормали мы будем определять переднюю и заднюю полуплоскости: если нормаль находится в полуплоскости, то данная полуплоскость - передняя; иначе - задняя. Теперь нужно определить, каким полуплоскостям принадлежат отрезки. Таким образом все отрезки разбиваются на три группы: отрезки, лежащие в передней полуплоскости ("c" и "d"), отрезки, лежащие в задней полуплоскости ("e" и "f"), и отрезки, лежащие на прямой (только "b"). Если отрезок принадлежит обоим полуплоскостям, то он делится на два (так "a" делится на "a1" и "a2"). Если узлу двоичного дерева приписать прямую и все отрезки, лежащие на ней, а две оставшиеся группы приписать его дочерним поддеревьям, то получим образование следующей структуры (Рис. 3):

Рис.3

Теперь нужно рекурсивно повторить алгоритм для каждого поддерева. То есть, мы имеем в качестве пространства переднее полуподпространство (в него входят отрезки "d", "a1", "c"). Выбираем любой из этих отрезков, например, "a1" и проводим через него гиперплоскость: получаем в качестве переднего поддерева отрезок "d", а заднего - "c" (Рис. 4):

Рис.4

Получаем структуру следующего вида (Рис. 5):

Рис.5

Аналогичным образом поступаем с задним поддеревом узла "b". Например, если выбрать за гиперплоскость сначала "a2", а затем "e", то получим следующее разбиение исходной плоскости прямыми (Рис. 6):

Рис.6

Рис.7

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

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

·       Наоборот, если камера в задней полуплоскости, то обходим узел в порядке от переднего поддерева к заднему.

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

Удаление невидимых поверхностей с помощью BSP-деревьев

Введение

Несмотря на то, что на сегодняшний день аппаратно реализован z-buffer, количество полигонов в сцене растёт экпотенциально и интерактивная визуализация таких сцен становится проблематичной, так как только аппаратной поддержки не хватает. Поэтому имеет смысл использовать другие алгоритмы определения видимости в сцене, которые можно использовать вместе с аппаратным ускорением, что повышает скорость визуализации.

Алгоритм Нейлора удаления невидимых поверхностей для статических сцен.

Певым этапом алгоритма Нейлора является построение BSP-дерева. Далее делается обход дерева сверху вниз от ближнего полигона к дальнему. При этом для каждого полигона делается проекция его на экранную плоскость. Рекурсивный процесс обхода и вывода прекращается, когда всё поддерево будет перекрыто предыдущим спроектированным полигоном. Для лучшего понимания рассмотрим пример (Рис. 8)

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

Одним из таких способов является метод временных ограничивающих объёмов [2]. Этот метод может являться дополнением для любого алгоритма удаления невидимых поверхностей в статических сценах. Изначально все объекты сцены (состоящие из полигонов) разбиваются на две группы - статические и динамические. Для статических строится отдельное дерево и это дерево обрабатывается посредством, например, алгоритма Нейлора или любого другого аналогичного алгоритма. Для каждого динамического объекта строится объём (на основе знания о поведении динамического объекта - например, траектории движения), который гарантировано будет содержать данный объект в течении некоторого промежутка времени. Далее строится BSP-дерево, но в узлы вставляются не полигоны объекта, а полигоны ограничивающего объёма. Динамический объект игнорируется пока не истечёт время действия его ограничивающего объёма, либо пока его ограничивающий объём не станет видимым.

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

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

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

Реализация алгоритма в библиотеке BSPlib.

Алгоритм построения и обхода BSP дерева был реализован в виде библиотеки классов, написанной на C++. Скачать библитеку можно здесь.

Библиотека позволяет описывать входные данные алгоритма, строить по ним дерево двоичного разбиения пространства и обходит его в различных направлениях. Исходная геометрия сцены описывается множеством всех многоугольников, из которых она состоит. Каждый многоугольник представлен списком своих вершин, перечисленных так, что каждая следующая вершина соединена с предыдущей, а последняя соединена еще и с первой. При этом многоугольник должен обязательно быть выпуклым. Список полигонов сцены передается конструктору класса, представляющего BSP дерево. Конструктор строит структуру даных, представляющую дерево, рекурсивным алгоритмом, описанным выше. Для обхода дерево от ближнего полигона к дальнему или в обратном порядке используются методы класса, которым передается функтор (объект класса с перегруженным оператором функции), обрабатывающий каждый многоугольник.

Прежде чем приступить к подробному описанию классов, входящих в библиотеку, необходимо заметить, что почти в каждом из них так или иначе используется STL, стандартная библиотека, входящая в состав ANSI C++ (1998 год). В частности, используются векторы, для представления списков вершин и многоугольников, пары для разбиения многоугольника на два и некоторые другие возможности, предоставляемые стандартной библиотекой шаблонов. Использование STL обусловлено двумя причинами: во-первых, библиотека позволяет избежать многих утечек памяти, связанных, например, с передачей указателей на массив и его размера отдельно друг от друга, а во-вторых, то, что эта библиотека входит в стандарт языка С++, фактически, позволяет пользователю библиотеки описать входные данные для BSPlib, используя только средства языка С++. Все это позволяет избежать многих сложностей и сохранить  при переходе от внутреннего представления сцены, используемого клиентом, к представлению, требуемому данной библиотекой.

Все классы библиотеки описаны в пространстве имен BSP, чтобы предотвратить возможные конфликты имен (например, класс Polygon, представляющий многоугольник сцены, мог вызвать конфликт с одноименной функцией из WinAPI). В первую очередь, для работы с любым геометрическим объектом необходимо определение вектора. Библиотека содержит два класса Vector2D и Vector3D, для векторов двумерного и трехмерного пространств соответственно, объявленные в заголовочном файле vector.h. Данные классы переопределяют арифметические операторы C++ для осуществления стандартных алгебраических операций над векторами, как то: сложение, вычитание, умножение и деление на число, инвертирование. Также в том же заголовочном файле содержатся объявления функций, вычисляющих длину вектора, скалярное произведение двух векторов, векторное поизведение двух векторов трехмерного пространства. Есть функция интерполирующая два вектора в заданном соотношении (она необходима, например, при делении многоугольника на два, лежащие в разных полупространствах).

Следующее важное понятие вводимое библиотекой – это вершина. Класс Vertex, определенный в файлах vertex.h и vertex.cpp, содержит положение вершины в пространстве, заданное ее радиус-вектором (объект класса Vector3D).  Кроме этого, каждая вершина, объявленная в программе клиента библиотеки, содержит список атрибутов этой вершины (возможно пустой). Стандартными атрибутами вершины являются нормаль, текстурная координата, цвет и материал. Для каждого такого атрибута в библиотеке определен специальный класс, все эти классы – наследники класса VertexAttribute. Указатели на этот базовый класс и содержатся в списке атрибутов вершины. В классе Vertex определены методы рисования вершины, получения ее радиус-вектора и линейного интерполирования двух вершин.

Рассмотрим подробнее атрибуты вершины. Базовый класс VertexAttribute объявляет минимальный интерфейс атрибута: метод, устанавливающий данный атрибут в графической системе, и метод, позволяющий интерполировать атрибуты двух вершин (он необходим при интерполяции этих вершин). Эти методы являются виртуальными и вызываются вершиной при выполнении соответствующих методов (отрисовки вершины и ее интерполяции) для каждого атрибута в списке. Например, класс Normal, определяющий нормаль в вершине, содержит вектор нормали, представленный объектом класса Vector3D, и в OpenGL-реализации первого виртуального метода класса VertexAttribute вызывает функцию glNormalfv, передавая ее в специальный метод вектора Apply. Такой подход позволяет хранить вместе с вершиной все необходимые ей атрибуты так, чтобы реализация самого BSP дерева от них никак не зависела.

Список вершин образует многоугольник, стороны которого определяются парами соседних вершин (включая первую и последнюю). Многоугольнику соответствует класс Polygon. Он содержит список вершин, из которых состоит, а также список атрибутов, подобный списку атрибутов вершин. Характерными атрибутами полигона являются: нормаль (если она одинакова для каждой вершины), цвет, материал и текстура. Атрибуты полигона являются объектами классов, унаследованных от абстрактного базового класса PolygonAttribute, отличающегося от VertexAttribute отсутствием метода интерполяции. Класс, описывающий многоугольник, имеет метод, возвращающий плоскость, в которой этот многоугольник лежит. Также определен интерфейс для определения положения полигона относительно произвольной плоскости (инцидентен плоскости, в положительном или отрицательном полупространстве, пересекается плоскостью) и для разделения его на два некоторой плоскостью. Метод, рисующий полигон также присутстсвует.

Следует заметить, что некоторые атрибуты (цвет, нормаль, материал) могут относиться как к одной вершине, так и к целому полигону. Классы, описывающие такие атрибуты, являются наследниками как VertexAttribute, так и PolygonAttribute. Оба этих класса, в свою очередь виртуально наследуются от общего класса Attribute, содержащего прототипы общих виртуальных методов классов атрибутов (фактически, метода, устанавливающего атрибут), что является стандартной схемой для множественного наследования в языке С++.

Класс Plane, описывающий плоскость, содержит вектор нормали к плоскости и расстояние от нее до начала координат, определяющие вместе четыре коэффициента уравнения плоскости в трехмерном пространстве. Перегруженный оператор функции  позволяют получить результат подстановки произвольного вектора в уравнение плоскости.

Для описания внутреннего представления BSP дерева – в частности, одного узла этого дерева – в библиотеку введен класс Node. При создании класса входным параметром является список многоугольников, которые принадлежат данному узлу. Конструктор класса выбирает один из полигонов в качестве разделителя для всех остальных и строит BSP дерево из данного набора многоугольников в соответствии с алгоритмом, описанным выше. Объекты класса при конструировании сами создают свои дочерние узлы, содержащие поддеревья. Таким образом, для работы с BSP деревом всей сцены, как с единым целым, достаточно хранить указатель на корень всего дерева, представленный объектом класса Node. Класс содержит поля, указывающие на два дочерних узла, на плоскость, которая является разделителем данного узла, и на список всех многоугольников, которые лежат в этой плоскости. Также класс определяет методы для обхода дочерних узлов в порядке от ближнего к дальнему и наоборот.

Класс Node берет на себя основные функции по обходу BSP дерева, поэтому класс Tree, который представляет именно дерево двоичного разбиения пространства, является просто фасадом (façade, класс, обощающий интерфейс некоторого набора объектов или классов) к интерфейсу корневого узла типа Node. Конструктор класса Tree получает в качестве параметра список многоугольников и передает его конструктору корневого узла. Помимо конструктора класс содержит указатель на тот самый корневой узел дерева и методы, осуществляющие обход дерева в одном из двух направлений: от ближнегок дальнему и от дальнего к ближнему. При этом обработка каждого узла производится наследником PolygonHandler: класса, содержащего виртуальный оператор функции, которым взаимодействие пользователя библиотеки с каждым полигоном сцены и осуществляется. Например, наследник по имени PolygonDrawer вызывает метод Draw для каждого полигона в сцене.

Литература

[1] Shumacker, R., Brand, R., Gilliland, M., Sharp, W. Study for Applying Computer-Generated Images to Visual Simulation 

[2] Sudarsky, C. Gotsman. Dynamic scene occlusion culling. IEEE Transactions on Visualization and Computer Graphics, vol. 5 no.1, January - March 1999.