Оптимизация доступа к пространственным данным

А. С. Тотмаков А.С. (totmakov@mail.ru) OOO Luxoft

Рассмотрены структуры данных, используемые в системах визуализации реального времени для хранения геометрических объектов

Производительность системы визуализации реального времени характеризуется тремя параметрами: числом кадров в секунду (ps), разрешением (размером рассчитываемого изображения), и сложностью сцены (сложность определяется числом деталей в сцене). Если скорость вывода 60 - 85 кадров в секунду и разрешение 1600х1200 в настоящее время удовлетворяют требования пользователя, то ограничения на сложность сцены отсутствует. Поэтому задача разработки алгоритмов оптимизации актуальна.

Структурирование пространственных данных представляет собой механизм

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

Организация структур пространственных данных обычно иерархическая. Основная причина использования иерархии - ускорение выполнения различных операций. Использование рассматриваемых структур позволяет снизить сложность некоторых алгоритмов с O(n) до O(log n). Следует отметить, что построение большинства структур пространственных данных - довольно ресурсоемкая операция, которая обычно осуществляется вне реального времени. Для некоторых структур возможно инкрементальное обновление в реальном времени.

Используются следующие пространственные структуры данных: иерархия ограничивающих объемов (Bounding Volume Hierarchies - BVH), BSP-дерево (Binary Space Partition - Бинарное разбиение пространства), октарное дерево (octree). BSP-дерево и октарное дерево - структуры данных, основанные на пространственном разбиении: все пространство сцены разбивается на подпространства, которые записываются в структуру данных. Объединение всех подпространств, содержащихся в листьях дерева, эквивалентно всему пространству сцены (листья не пересекаются). BSP-дерево - с нерегулярной структурой, что означает возможность произвольного деления пространства. Октарное дерево - с регулярной структурой, что означает постоянно одинаковое деление пространства. Иерархия ограничивающих объемов не основывается на разбиении пространства. Вместо этого, структура содержит ограничивающие пространства для всех геометрических объектов, составляющих сцену. В дополнение к ускорению операции поиска пересечений геометрических сущностей эта структура данных описывает связи геометрических объектов.

Иерархия ограничивающих объемов (BVH)

Ограничивающий объем (Bounding Volume) содержит некоторый набор объектов; его особенность состоит в том, что он представлен более простой геометрической формой по сравнению с содержащимся в нем объектом. Использование простого ограничивающего объема вместо самого объекта позволяет значительно ускорить операцию проверки пересечения. Примерами ограничивающих объемов могут служить сферы, выровненные по осям, прямоугольные параллелепипеды (Axis-aligned Bounding

Box), а также ориентированные прямоугольные параллелепипеды (Oriented Bounding Box). Ограничивающий объем никак не отображается на рассчитываемом изображении, а используется для увеличения скорости расчета изображения и некоторых вспомогательных операций.

Для визуализации трехмерных сцен, иерархия BVH - вероятно, самая распространенная структура пространственных данных. Эта структура, например, используется в алгоритме иерархического отсечения областью видимости. Сцена представляет собой иерархическую древовидную структуру, состоящую из корня, внутренних узлов и листьев. Верхний узел, он же корень, не имеет родителей . Листья содержат геометрические объекты, которые необходимо отобразить и не имеют детей . Внутренние узлы, напротив, имеют одного или несколько детей. Каждый узел дерева, включая листья, имеет ограничивающий объем, содержащий все геометрические объекты поддерева. Отсюда такое название - иерархия ограничивающих объемов. Ограничивающий объем корневого узла дерева содержит все геометрические объекты, составляющие сцену (рис. 1).

Рис. 1. Иерархия ограничивающих объемов

Рассмотрим рисунок 1. Его левая часть - простейшая сцена, состоящая из шести объектов. Каждый объект заключен в ограничивающий объем - сферу. Далее сферы группируются в большие сферы до тех пор, пока все объекты не будут находиться внутри одной большой сферы. Правая часть рисунка - иерархия ограничивающих объемов для сцены, представленной слева. Ограничивающий объем корневого узла включает все объекты, составляющие сцену.

В основе иерархии ограничивающих объемов лежит хорошо известная структура данных - дерево. Эта структура широко представлена в литературе, например, в работе [1], поэтому здесь подробно не рассматривается.

Рассмотрим к-нарное дерево. Каждый внутренний узел такого дерева имеет к детей . Дерево, состоящее только из одного узла - корня - имеет глубину ноль. Если к этому дереву добавить лист, то он будет находиться на глубине один. Дерево считается сбалансированным, если глубина всех листьев равняется h либо h-1. В общем случае, глубина сбалансированного дерева равняется h = logk n, где n - общее число узлов (включая листья) в дереве.

Чем больше значение к, тем меньше глубина дерева, что, в свою очередь, сокращает время на спуск по дереву, но увеличивает время на обработку каждого узла. Довольно часто использование бинарного дерева оказывается самым простым, и в целом дает неплохую производительность. Однако существуют доказательства, что использование большего к (к = 4, к = 8) предпочтительнее в некоторых приложениях [2].

Использование иерархии ограничивающих объемов позволяет оптимизировать многие операции. Рассмотрим, например, операцию пересечения луча со сценой и поиск

ближайшего пересечения. Тест на пересечения необходимо начать с корневого узла. Если луч не пересекает его ограничивающий объем, то также не пересекает ни одного объекта внутри этого ограничивающего объема. В противном случае тест продолжается рекурсивно, т.е. проверяются ограничивающие объемы узлов, являющихся детьми корневого узла. В случае непопадания луча в ограничивающий объем, можно прерывать тестирование всего поддерева. Если же луч пересекает ограничивающий объем листа, необходимо проверить сам геометрический объект, содержащийся в этом листе. Увеличение производительности происходит вследствие того, что проверка пересечения луча и ограничивающего объема происходит очень быстро. Поэтому в качестве ограничивающих объемов необходимо использовать простые объекты, такие, как сферы и прямоугольные параллелепипеды. Вложенность иерархии ограничивающих объемов позволяет избегать проверки больших областей по причине прерывания тестирования поддерева.

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

Иерархия ограничивающих объемов может также использоваться в динамически изменяющихся сценах [3]. При изменении позиции объекта внутри некоторого ограничивающего объема необходимо проверить, находится ли все еще объект в пределах этого объема. Если находится, то иерархия ограничивающих объемов остается неизменной. В противном случае узел, содержащий объект, удаляется, и родительский узел рассчитывается заново. Удаленный узел заново вставляется в дерево рекурсивно, начиная с корневого узла. Другой метод заключается в расширении родительского ограничивающего объема. При использовании обоих методов дерево становится менее несбалансированным и неэффективным при каждом редактировании.

BSP-дерево

В компьютерной графике существуют два вида дерева бинарного разделения пространства (Binary Space Partition Tree, BSP-tree), выровненные по координатным осям (axis-aligned BSP-tree) и по полигонам (polygon-aligned BSP-tree). В процессе создания дерева все пространство делится плоскостью на два подпространства. Затем все геометрические примитивы сортируются по принципу принадлежности к одному из подпространств. Деление и сортировка происходят рекурсивно. Одним из полезных свойств таких деревьев является возможность быстро производить сортировку полигонов по критерию удаленности от какой либо точки, например, от позиции виртуальной камеры.

Выровненное по координатным осям BSP-дерево

Создание выровненного по координатным осям BSP-дерева происходит следующим образом. Вся виртуальная сцена помещается в выровненный по координатным осям ограничивающий прямоугольный параллелепипед (Axis-aligned Bounding Box), затем он рекурсивно делится на меньшие. Рассмотрим параллелепипед на одном из уровней рекурсии. Необходимо выбрать одну из сторон, построить перпендикулярную ей плоскость и разделить параллелепипед на два. Существуют два подхода для выбора расположения разделяющей плоскости: при первом разделяющая плоскость всегда делит объем пополам; при втором позиция разделяющей плоскости может варьироваться в пределах параллелепипеда. В случае, если разделяющая плоскость пересекает объект, он либо становится членом обоих подмножеств, либо разделяется на

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

а

б

Рис. 2. Выровненное по координатным осям BSP-дерево с расположением разделяющей плоскости в любом месте (а) и структура дерева (б).

Одна из стратегий разбиения ограничивающего параллелепипеда - разбиение по координатным осям: т.е. корень дерева всегда делится по оси x, его дети делятся по оси y, а внуки по оси z. Далее цикл повторяется. BSP-дерево, построенное с использованием этой стратегии разбиения, иногда называют (к^)-дерево [4]. Другая стратегия заключается в нахождении наибольшей стороны параллелепипеда и разделении по ней. Предположим, что наибольшая сторона лежит вдоль оси y. Тогда разделяющая плоскость будет иметь вид y = d, где d - некоторая константа. Для выполнения условия сбалансированности дерева константа d должна выбираться таким образом, чтобы количество примитивов в обеих частях параллелепипеда было одинаковым. Это операция является ресурсоемкой, поэтому часто параллелепипед делится просто пополам.

Примером использования выровненного по осям BSP-дерева может служить решение задачи сортировки примитивов от ближнего к дальнему (front-to-back sorting). Такая задача может возникнуть при реализации алгоритма отсечения объектов, закрытых от виртуальной камеры другими объектами (occlusion culling). Предположим, что спуск по дереву начинают с узла N. Проверяется положение наблюдателя относительно разделяющей плоскости, соответствующей узлу N. Спуск по дереву продолжается в сторону, соответствующую позиции наблюдателя. Только после того как просмотрена половина поддерева узла N, необходимо переходить к спуску во вторую половину. В результате листья дерева будут просмотрены в порядке удаления от наблюдателя. Этим методом не решается задача полной сортировки примитивов, поскольку содержание листьев все еще остается несортированным, и один примитив может принадлежать нескольким листьям. Однако такая грубая сортировка часто бывает достаточна для решения многих задач. Если при спуске постоянно переходить на сторону, противоположную наблюдателю, получится сортировка от дальнего к ближнему (back-to-front sorting). Этот способ можно использовать при отображении полупрозрачных

примитивов. Таким же образом можно проверять пересечения луча со сценой и отсечение объемом видимости (frustum culling).

Выровненное по полигонам BSP-дерево

Создание выровненного по полигонам BSP-дерева происходит несколько по-иному [5 - 8]. В этом случае разделяющей плоскостью является некоторый полигон, содержащийся в сцене, т.е. в корневом узле дерева выбирается полигон и вся сцена делится на две части плоскостью, в которой лежит выбранный полигон. Любой полигон, пересекающий разделяющую плоскость, делится на две независимые части по линии пересечения. В каждом полупространстве выбирается полигон, снова разделяющий полупространство на две части. Следует отметить, что разделение двух полупространств происходит независимо, различными плоскостями. Далее процесс происходит рекурсивно. Создание эффективного, выровненного по полигонам BSP-дерева - процесс ресурсоемкий, поэтому дерево создается обычно один раз (рис. 3).

а б

Рис. 3. Выровненное по полигонам методом деления сцены плоскостью BSP-дерево (а),

справа представлена структура дерева (б).

В большинстве случаев необходимо создать сбалансированное дерево, т.е. чтобы глубина любых двух листьев различалась максимум на единицу. Совершенно несбалансированное дерево неэффективно. Примером может служить дерево, каждое разделение в котором делило пространство на пустое и содержащее все примитивы. Существует множество стратегий поиска полигона, разделение которым приведет к построению эффективного дерева. Одной из них является использование критерия наименьшего пересечения (least-crossing criteria) [6]. Суть этой стратегии заключается в следующем. Произвольно выбираются несколько полигонов. Для каждого их них определяется количество полигонов, пересекающих разделяющую плоскость. Выбирается тот, чья плоскость имеет наименьшее число пересечений. Эмпирически было доказано [6, 9], что для сцены из тысячи полигонов для получения хорошего дерева необходимо протестировать только пять. Тестирование более пяти полигонов лишь не намного улучшает результат. Естественно, что с увеличением числа полигонов в сцене число тестируемых полигонов тоже должно быть увеличено.

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

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

Октарное дерево (octree)

Термин octree (октарное дерево) в дословном переводе с английского означает дерево, получающенное в результате рекурсивного деления объемного пространства на восемь кубических субпространств.

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

Для построения октарного дерева необходимо найти выровненный по осям ограничивающий прямоугольный параллелепипед, содержащий всю сцену. Дальнейший алгоритм - рекурсивный и повторяется до тех пор, пока не будет выполнено одно из условий выхода из рекурсии. Этим условием может являться достижение максимального уровня рекурсии или минимального количества примитивов в узле [4, 10]. В случае остановки рекурсии узел становится листом и с ним связываются примитивы, лежащие внутри этого узла. В противном случае узел делится по координатным осям тремя плоскостями. Тем самым формируются восемь прямоугольных параллелепипедов одинакового размера. Каждый новый параллелепипед проверяется на условие завершения рекурсии и, если оно отрицательно, опять делится на восемь частей. В двумерном пространстве октарное дерево превращается в квадро-дерево (рис. 4).

б

а

в

г

Рис. 4. Построение квадро-дерева - двумерной версии октарного дерева.

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

Октарное дерево может быть использовано точно так же как и ориентированное по координатным осям BSP-дерево. Оно позволяет оптимизировать те же самые операции.

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

расчетах. Другим вариантом является разделение объекта на независимые части, что приводит в конечном счете к увеличению общего количества примитивов. Существует третье решение, лишенное этих недостатков, - свободное октарное дерево (loose octree).

[11]

Основная идея свободного октарного дерева такая же, как и обычного дерева, за исключением того, что размер каждого прямоугольного параллелепипеда не фиксирован, т.е. значение длины параллелепипеда / можно заменить на kl, где к>\ (рис. 5.)

б

а

Рис. 5. Сравнение октарного дерева (а) со свободным октарным деревом (б).

Рассмотрим рисунок 5. Объект звезда пересекает разделяющую плоскость октарного дерева (а). Справа,. Объект звезда целиком расположен в левом верхнем узле (б) при использовании свободного октарного дерева, k=1.5.

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

Граф сцены

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

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

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

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

При появлении у нескольких узлов общего ребенка , древовидная структура называется направленным ациклическим графом (Directed Acyclic Graph) [1]. Ациклический - означает отсутствие петли, направленный - означает, четкую заданность направления соединения двух соединенных узлов, (т.е. кто родитель , а кто ребенок ). Направленный ациклический граф часто используется в качестве графа сцены, так как позволяет производить инстанцирование (instancing) - операции получения нескольких

копий объекта без репродукции геометрии объекта (рис. 6.).

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

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

Заключение

Рассмотрены три типа структурирования пространственных данных: BVH, BSP-дерево, октарное дерево. Способ структурирования данных необходимо выбирать, основываясь на типе сцены, с которой придется работать, и задаче, которую придется решать.

Для решения задачи визуализации больших открытых пространств и определения столкновений на такой сцене использование структуры октарное дерево является

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

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

BVH целесообразно использовать если задача локализации объектов и групп объектов, ограничивающий объем которых необходимо найти, имеет простое решение. В случае представления виртуальной сцены одним набором примитивов (polygon soup) использование данного метода неэффективно.

Литература

1. Cormen, T.H., C.E. Leiserson, and R. Rivest, Introduction to Algorithms, MIT Press, Inc., Cambridge, Massachusetts, 1990.

2. Larsson, Thomas, and Tomas Akenine-Moller, Collision Detection for Continuously Deforming Bodies , Eurographics 2001.

3. Ratcliff, John W., Sphere Trees for Fast Visibility Culling, Ray Tracing and Range Searching , Game Programming Gems 2.

4. Samet, Hanan, The Design and Analysis of Spatial Data Structures, Adison-Wesley, Reading. Massachusetts, 1989.

5. Abrash, Michael, Michael Abrashs Graphics Programming Black Book, Special Edition, The Coriolis Group, Inc., Arizona, 1997.

6. Fuchs, H., Z.M. Kedem, and B.F. Naylor, On Visible Surface Generation by A Priori Tree Structure , Computer Graphics, (Siggraph 80 Proceeding).

7. Fuchs, H., G.D. Abram, and E.D. Grant, Near Real-Time Shader Display of Rigid Objects , Computer Graphics, (Siggraph 89 Proceeding).

8. Gordon, Dan, and Shuhong Chen, Front-to-back display of BSP trees , IEEE computer Graphics and Applications.

9. James, Adam, Binary Space Partition for Accelerated Hidden Surface Removal and Rendering of Static Environments, Ph. D. Thesis, University of East Anglia, August

1999.

10. Samet, Hanan, Application of Spatial Data Structures: Computer Graphics, Image Processing and GIS, Addison-Wesley, Reading. Massachusetts, 1989.

11. Ulrich, Thatcher, Loose Octrees , Game Programming Gems.