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

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

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

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

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

32

организации геометрических примитивов в пространствах 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), затем он рекурсивно делится на меньшие. Рассмотрим параллелепипед на одном из уровней рекурсии. Необходимо выбрать одну из сторон, построить перпендикулярную ей плоскость и разделить параллелепипед на два. Существуют два подхода для выбора расположения разделяющей плоскости: при первом разделяющая плоскость всегда делит объем пополам; при втором позиция разделяющей плоскости может варьироваться в пределах параллелепипеда. В случае, если разделяющая плоскость пересекает объект, он либо становится членом обоих подмножеств, либо разделяется на