Содержание к диссертации
Введение
Глава 1. Обзор существующих методов пространственного индексирования 16
1.1 Классификация методов пространственного индексирования 16
1.2 Композиция объектов 20
1.3 Декомпозиция пространства 31
1.4 Предварительные выводы 40
Глава 2. Регулярные октальные деревья 42
2.1 Пространственная декомпозиция на основе октальных деревьев 43
2.2 Теоретический анализ сложности метода декомпозиции
2.2.1 Анализ сложности построения регулярного октального дерева 50
2.2.2 Анализ сложности определения столкновений 53
2.2.3 Анализ сложности выборки объектов по заданной области 60
2.2.4 Анализ сложности поиска ближайших соседей 65
Глава 3. Схемы пространственно-временного индексирования 69
3.1 Альтернативные схемы пространственно-временного индексирования 72
3.1.1 Схема А. Временно-пространственная декомпозиция 74
3.1.2 Схема В. Событийное индексирование 76
3.1.3 Схема С. Пространственно-временная декомпозиция 77
3.2 Анализ сложности разрешения запросов с использованием различных схем пространственно-временного индексирования 78
3.2.1 Развертывание пространственно-временного индекса 79
3.2.2 Реконструкция сцены на заданный момент времени 79
3.2.3 Поиск объектов в области видимости 81
3.2.4 Анимационный запрос 81
3.3 Сравнительный анализ 82
Глава 4. Методы индексирования сложных иерархически организованных пространственных данных 84
4.1 Организация пространственных сцен 84
4.2 Проблемы исполнения запросов к иерархическим данным 84
4.3 Комбинированный метод индексирования 88
4.4 Модельный набор иерархически организованных данных 92
4.5 Сложность развертывания комбинированного индекса 92
4.6 Оценка затрат на хранение комбинированного индекса 95
Глава 5. Вычислительные эксперименты 97
5.1 Серия экспериментов с октальными структурами 97
5.2 Серия экспериментов с комбинированными структурами 103
5.3 Результаты экспериментов с реальными наборами данных 105
5.4 Результаты апробации и внедрения предложенных методов 111
Заключение 115
Список литературы
- Композиция объектов
- Теоретический анализ сложности метода декомпозиции
- Схема В. Событийное индексирование
- Комбинированный метод индексирования
Композиция объектов
Рассмотрим псевдокод алгоритм поиска объектов в заданной области сцены, изображенный на рис. 9а. Он незначительно отличается от приведенного для структур, использующих композицию объектов. Отличие связано с тем, что нелистовые вершины содержат ссылки на объекты подлежащие анализу. Как и в случае R-дерева, в наихудшем случае анализу подвергнутся все объекты, входящие в сцену, поэтому вычислительная сложность запроса составляет 0(N) .
Псевдокод алгоритма поиска ближайших соседних объектов приведен на рис. 96. Основная процедура FINDNEARESTNEIGHBOURS принимает в качестве аргумента объект и возвращает множество его ближайших соседей. Используемая в ней вспомогательная функция NODE по данному объекту находит ассоциированную с ним вершину V октального дерева. Для этого рекурсивный обход октального дерева сверху вниз продолжается до тех пор, пока данный объект целиком содержится в рассматриваемой вершине дерева. Последняя вершина, удовлетворяющая этому условию, является искомой. Вычислительная сложность такой процедуры составляет 0(D), где D — глубина октального дерева. Также существенной деталью является возможность задать начальную аппроксимацию расстояния до ближайших объектов. Действительно, если при построении октального дерева вершина была разбита, то в ней должен содержаться, по меньшей мере, М + \ объект. Следовательно, родитель вершины V содержит еще, как минимум, один объект, расстояние до которого не превышает удвоенной длины диагонали V. Это значение и выбирается в качестве начальной аппроксимации. В остальном алгоритм поиска ближайших соседей в октальных деревьях концептуально повторяет описанный алгоритм поиска ближайших соседей в R-деревьях. В наихудшем случае трудоемкость выполнения этого запроса составляет 0(N) .
Необходимо отметить схожесть приведенного алгоритма с алгоритмом поиска октантов, смежных данному. В работе [82] было показано, что для поиска соседних вершин заданной, лежащих на том же уровне иерархии, в среднем необходимо 4 раза проследовать по ссылке, связывающей родительскую и дочернюю вершины.
Вставка объекта в октальное дерево осуществляется процедурой INSERT, псевдокод которой приведен на рис. 9в. В качестве параметров она объект и вершину октального дерева, в которую он вставляется. Используемая в методе вспомогательная функция COUNTOVERLAPPEDCHILDREN возвращает число дочерних октантов заданного, пересекающихся с данным объектом. Если их более одного, то объект вставляется в текущую вершину дерева при помощи процедуры ADD, иначе вставка рекурсивно повторяется для дочерних вершин. Вычислительная трудоемкость процедуры ADD составляет 0(\ogN0) где N0 — количество объектов ассоциированных с данной вершиной (мы полагаем, что объекты, ассоциированные с вершинами октального дерева, проиндексированы для быстрого поиска). В наихудшем случае, когда все объекты сцены оказываются ассоциированными с единственной ячейкой, N0 = N, где N — число объектов в сцене. Функция SHOULDSPLIT принимает в качестве параметра вершину октального дерева и возвращает TRUE, если количество объектов, ассоциированных с ней, превышает допустимое, и ее разбиение приведет к тому, что как минимум один из дочерних узлов будет непустым. В противном случае возвращается значение FALSE. Процедура SPLIT выполняет разбиение октанта и переносит часть ассоциированных с ним объектов в дочерние вершины. При условии, что объекты, которые могут быть помещены в дочерние блоки, помечаются заранее, затрачиваемое время составит 0(М).
Таким образом, проведен сравнительный анализ современных методов поиска и индексирования многомерных данных в контексте приложений моделирования динамических сцен. В рамках двух фундаментальных подходов, реализующих принципы объектной кластеризации и пространственной декомпозиции, выделены основные семейства методов и обсуждены их алгоритмические особенности. Анализ методов проведен в контексте комплексных требований, предъявляемых к приложениям обсуждаемого класса, и прежде всего, требований эффективности исполнения типовых пространственных запросов в больших сценах с недетерминированной динамикой и жестким характером пространственно-временной когерентности. Проведенный сравнительный анализ вычислительной сложности позволяет сделать вывод о перспективности методов, основанных на декомпозиции пространства, и, в частности, октальных деревьев со строгой многоуровневой локализацией объектов (MX-CIF) и верхней границей кардинальности октантов. Данный вывод основывается на следующих фактах: — методы, основанные на пространственной декомпозиции, и методы, использующие объектную кластеризацию, имеют одинаковую асимптотическую сложность операций поиска объектов в заданной области и поиска соседей объектов, составляющую O(N). Вместе с тем, сложность операций добавления объекта в сцену и его удаления для методов декомпозиции выражается оценкой 0(logN + D+M), что более оптимистично, чем затраты 0(М log N), необходимые для методов кластеризации; — методы кластеризации в большей степени ориентированы на особенности страничной работы с внешней памятью, что приводит к требованию высокой наполненности вершин дерева и его сбалансированности. Однако эти требования не являются абсолютно критичными для скорости разрешения пространственных запросов. Более гибкие условия наполненности ячеек в методах декомпозиции могут приводить к некоторой разбалансировке дерева, однако позволяют более точно локализовать объекты уже на верхних уровнях и избежать дополнительных проверок на нижних уровнях; — кластеризация объектов приводит к чрезмерно высоким затратам в динамических сценах, связанным с необходимостью перманентной перебалансировки дерева и сложным пространственным анализом. Для обновления структур индекса в методах декомпозиции достаточно идентифицировать ячейку сцены, в которой произошли события, и соответствующим образом модифицировать ее и, возможно, ее локальных соседей; — наконец, структуры пространственной декомпозиции инварианты по отношению к порядку событий в сцене и определяются лишь ее текущим представлением. В методах кластеризации необходим дополнительный анализ для обработки потока событий, чтобы обеспечить требуемую инвариантность структур индекса и избежать их деградации при масштабных изменениях в сцене.
Теоретический анализ сложности метода декомпозиции
Рассмотрим случай / 0. Как было показано выше, имеет место общая оценка сложности построения дерева Qdepioy n(h— 1). По теореме 1 глубина дерева всегда может быть ограничена как h log2 - Следовательно, Qdepioy lg2 т п и теоРема доказана. Теорема 2 имеет важные следствия, связанные с разным асимптотическим ростом сложности построения октального дерева для точечных и протяженных данных. Для первых (/ = 0) сложность оценивается как 0(nlog2n), а для вторых (/ 0) — как 0(п). На рисунке 18 приведены графики сложности построения октального дерева от количества объектов в модельном наборе п при разных значениях порога наполненности октантов т, построенные на основе результатов леммы 3 для точечных (верхние кривые) и протяженных объектов (нижние кривые).
Примечательно, что в исследуемом диапазоне размерности задачи (до ста тысяч объектов) все кривые выглядят схожим образом, несмотря на наличие логарифмического фактора в асимптотической оценке сложности для точечных объектов. Согласно приведенным графикам сложность построения дерева для протяженных объектов несколько ниже, чем для точечных данных. Это объясняется тем обстоятельством, что при одинаковом общем количестве, часть объектов локализуются на более высоких уровнях октального дерева и не возникает необходимости в их дальнейшем анализе.
Перейдем к оценкам затрат на выполнение типовых запросов, связанных с поиском столкновений объектов в пространственно-трехмерных сценах. Как правило, точное пересечение двух геометрических объектов сложной формы требует большого объема вычислений. Поэтому более эффективной стратегией является предварительная локализация потенциальных столкновений с помощью простых тестов, основанных на сепарации пространства и пересечении ограничивающих объемов [14, 85]. Точная процедура определения столкновений применяется лишь в случае положительного вердикта, что происходит в приложениях относительно редко и, как результат, существенно уменьшает общее время поиска столкновений. Эффект особенно ощутим для сцен, объекты которых геометрически представлены сложными аналитическими кривыми, поверхностями или полиэдрами с большим числом граней [62, 63].
Обсудим алгоритмические варианты использования октального дерева для локализации столкновений в сценах и получим оценки сложности в предположении, что сцена представлена модельным набором данных S(n,l). Предположим, что октальное дерево развернуто и предстоит выявить все пары объектов, допускающие столкновения. В наивном алгоритме пришлось бы попарно пересечь все ограничивающие объемы объектов, что привело бы к выполнению -п(п — 1) операций поиска пересечения между объектами. Однако октальное дерево позволяет сделать это гораздо эффективнее с применением следующего алгоритма. PROCEDURE CLASH (octant, result)
Процедура CLASH принимает в качестве параметра указатель на текущий октант, а также указатель на коллекцию результатов, каждый из которых представлен в виде пары объектов, имеющих потенциальную коллизию. В теле этой процедуры происходит поиск коллизий среди объектов, принадлежащих текущему октанту, а затем проверяются пересечения этих объектов с объектами, принадлежащими дочерним октантам при помощи вспомогательной процедуры CLASHCHILDREN, принимающей в качестве параметра объект и, посредствам поиска в глубину, ищущей все объекты, имеющие пересечения с ним. Затем процедура CLASH рекурсивно повторяется для всех дочерних октантов текущего октанта.
Перейдем к оценкам сложности для описанного алгоритма. Пусть регулярное октальное дерево Octree(rn) глубиной h развернуто для модельного набора данных S(n,l). Тогда количество операций пересечения между ограничивающими объемами, необходимое для поиска столкновений Qciash, ограничено сверху в соответствии со следующей оценкой: объектов. Затем анализируются возможные столкновения внутренних объектов рассматриваемого октанта с объектами, приписанными дочерним октантам. Заметим, что каждый внутренний объект пересекается не более, чем с восемью дочерними октантами на каждом следующем уровне октального дерева, поэтому затраты ограничиваются выражением 8rij 2у_і+1Пу. Такая оценка априори не более чем в четыре раза превышает вычислительную сложность операции, поскольку в лучшем случае внутренний объект пересекается с двумя дочерними октантами. Таким образом, получаем следующую оценку стоимости локализации столкновений:
Подставляя щ и выполнив суммирование рядов, получим требуемое выражение для общей оценки. Как и следовало ожидать, сложность локализации столкновений в общем случае пропорциональна квадрату числа объектов. Особый случай составляют точечные объекты (/ = 0), для которых полученное выражение принимает вид — -. По построению регулярного октального дерева для точечных объектов выполняется соотношение —f т и, следовательно, имеет место оценка Qciash — Что и требовалось доказать. Важным следствием леммы является линейная сложность определения совпадений точечных данных с использованием регулярного октального дерева. Оценим эффект применения октального дерева для поиска столкновений протяженных объектов. На рисунке 20 представлены графики функции стоимости определения столкновений в модельном наборе данных в зависимости от относительных габаритов объектов. Графики построены на основе общей оценки леммы 4, а для наглядности значения стоимости отнесены к пессимистической оценке наивного поиска столкновении -п(п — 1).
Схема В. Событийное индексирование
Другим содержательным примером может служить поиск столкновений между двумя заданными составными объектами. Использование единого регулярного октального дерева в качестве пространственного индекса приводит к необходимости анализа пересечений для каждой пары листовых объектов (см. рис. 19). Очевидно, что такой подход приводит к чрезмерно высоким вычислительным расходам, особенно в случаях, когда выделенные объекты вовсе не пересекаются.
Наряду с указанными проблемами, связанными с эффективным разрешением пространственных запросов, важным фактором, препятствующим применению традиционных методов пространственного индексирования на практике, является необходимость масштабных обновлений индексов при появлении, исчезновении или перемещении сложных составных объектов. В конечном счете, это может приводить к существенной деградации производительности всего программного приложения. Примером подобной ситуации являются сложные сборки, состоящие из десятков и сотен тысяч деталей (например, эскалатор, кран или нефтяная платформа). При перемещении подобных объектов в сцене для того, чтобы поддерживать пространственный индекс в корректном состоянии, необходимо пересчитывать положение каждого из листовых объектов, составляющих сборку, в октальной регулярной структуре. Очевидно, затраты на подобные перманентные обновления пространственного индекса крайне высоки.
В качестве альтернативного метода индексирования, лишенной перечисленных недостатков, может выступать сама иерархия организации сцены, если только она отражает пространственные отношения, возникающие при последовательной объектной композиции. Его главным преимуществом является отсутствие необходимости развертывания дополнительных структур индекса и поддержания их в согласованном состоянии при изменениях в сцене. Вместе с тем, рассмотренные выше запросы, приводившие к высоким накладным расходам, допускают эффективное исполнение в рамках данного метода. В качестве примера рассмотрим запрос поиска объектов заданного типа в заданной области, приводимый выше (поиск оборудования в заданной области строительной площадки). Алгоритм его разрешения представлен на рисунке 30.
Алгоритм предполагает рекурсивный обход объектной иерархии сверху вниз и последовательный анализ объектов. Процесс обхода и дальнейший анализ не распространяются на объекты, находящиеся вне области поиска, целиком лежащие в ней (в этом случае анализируемый объект добавляется к результатам запроса), не принадлежащие заданному типу (соответствующая проверка выполняется вспомогательной функцией ISTYPEOF) или являющиеся листьями иерархии. Применение алгоритма позволяет локализовать поиск и избежать расходов на анализ объектов, заведомо не удовлетворяющих условиям поиска. Вместе с тем, существенным недостатком является невозможность принятия быстрого решения о пространственном распределении объектов без их последовательного обхода и полного анализа.
Подобно предыдущего алгоритму поиск коллизий предполагает рекурсивный обход иерархии объектов сверху вниз. Если коллизия найдена между парой составных объектов, процедура рекурсивно вызывается для всех возможных пар дочерних объектов. Таким образом, если исходные объекты не пересекаются или область их пересечения незначительна относительно габаритов объектов, можно ожидать высокую эффективность разрешения запроса. В противном случае анализ распространяется на все возможные пары дочерних объектов, что приводит к быстрой деградации производительности.
Основным недостатком данного метода является низкая эффективность для некоторых сцен, составные объекты которых содержат значительное число дочерних объектов. Действительно, при разрешении запросов последовательному анализу подвергаются все дочерние объекты, независимо от их пространственного распределения. Такая ситуация подобна случаю, когда вся сцена представлена линейным списком огромного числа объектов и разрешение запросов осуществляется наивным способом без использования каких-либо пространственных индексов. Таким образом, использование иерархического представления сцены в ряде случаев может приводить к высоким вычислительным затратам и, несомненно, неприемлемо при требованиях высокой равномерной эффективности разрешения пространственных запросов.
Для преодоления описанных проблем в работе предлагается комбинированный адаптивный метод индексирования, основанный на использовании иерархического представления сцены в сочетании с регулярными октальными деревьями. Регулярное октальное дерево предлагается разворачивать для каждого составного объекта, содержащего более т дочерних объектов. На рисунке 32 схематично показана структура индекса для иерархически организованных данных в визуальной нотации, примененной для рисунка 29. Каждое развернутое регулярное октальное дерево содержит только ААВВ соответствующих дочерних объектов родителя, для которого разворачивается пространственный индекс. Иерархия объектов сцены Пространственные индексы
Такой способ позволяет эффективно разрешать пространственные запросы, адресованные к составным объектам, а также запросы, имеющие дополнительный семантический контекст, связанный с иерархической организацией данных. В отличие от наивного метода, рассмотренного в предыдущем разделе, комбинированный метод нивелирует его недостатки в случаях, когда иерархическое представление сцены несбалансированно или слишком ветвисто. Действительно, в подобных случаях запросы к объектам, содержащим большое количество дочерних объектов, могут быть эффективно разрешены при помощи развернутых регулярных октальных деревьев. Рассмотрим алгоритмы разрешения основных пространственных запросов с использованием структуры комбинированного индекса.
Комбинированный метод индексирования
Необходимо отметить, что для разрешения этого запроса наивным способом потребовалось бы выполнить процедуру поиска расстояния между объектами п — 1 раз (для сцены, содержащей п объектов), что сопоставимо с затратами на построение регулярного октального дерева. Следовательно, применение октальных деревьев вполне мотивировано даже для случая однократного поиска ближайших соседей.
Таким образом, проведенные исследования показали, что регулярные октальные деревья могут эффективно применяться в качестве пространственного индекса для сцен, содержащих относительно небольшие объекты. С ростом габаритов следует ожидать деградацию производительности при разрешении вычислительно сложных пространственных запросов (в частности, при поиске коллизий или ближайших соседей), однако и в этом случае они практически не уступают наивным алгоритмам даже при однократном применении.
Перейдем к вычислительным экспериментам, связанным с исполнением пространственных запросов к иерархически организованным данным. Как и в предыдущих сериях экспериментов, модельные наборы данных генерировались случайным образом, а результаты усреднялись для эквивалентных тестов, соответствующих одним и тем же значениям параметров.
На рисунке 41 приведено семейство кривых зависимости времени построения комбинированного индекса от количества объектов в модельном наборе 5(100,0.01,3). В ходе экспериментов было установлено, что параметры модельного набора практически не влияют на соотношение затрат с использованием октальных и комбинированных структур. Примечательно, что время и объем памяти, необходимые для построения комбинированного индекса оказываются несколько ниже, чем соответствующие затраты на построение октального дерева. Это полностью согласуется с результатами, полученными в ходе теоретического исследования.
Результаты анализа затрат на поиск коллизий в иерархически организованных модельных наборах 5(100, 0.1,3) представлены в виде графиков на рисунке 42. Можно видеть, что применение комбинированного индекса оказывается несколько выгодней, чем применение регулярного октального дерева. Этот факт объясняется тем, что в модельном наборе данных организация иерархии отражает естественную пространственную композицию объектов. Результаты синтезированных тестов позволяют надеяться, что положительный эффект от применения комбинированного индекса сохранится и в реальных сценах, возникающих, частности, в приложениях визуального моделирования. В подобных приложениях ведется работа с масштабными сценами, иерархическая организация которых часто отражает и пространственную логику сборки объектов.
Для оценки временных затрат подсчитывалось количество вызовов элементарной функции пересечения двух прямоугольных параллелепипедов. График зависимости количества вызовов от числа объектов в сцене и показан на рисунке. Как и при использовании октальных структур, увеличение размеров области выборки приводит к росту затрат на разрешение запроса. Однако, если размер области приближается к габаритам всей сцены (L = 1), затраты резко снижаются, поскольку значительное число корневых составных объектов попадает в область выборки целиком и не требуется их дополнительный анализ. Сравнительный анализ трудоемкости выборки по области при помощи октальной (см. рис. 39) и комбинированной структуры также показывает преимущества последней. Значительный эффект достигается при больших областях выборки.
Таким образом, применение комбинированного индекса при поиске объектов в заданной области является эффективным для модельных наборов данных. Можно сделать вывод о целесообразности развертывания комбинированного индекса во всех случаях, связанных с разрешением рассмотренных запросов к иерархически организованным пространственным данным. Обсуждаемые в следующем разделе вычислительные эксперименты с реальными данными подтверждают это.
Обсудим результаты применения комбинированного индекса при разрешении запросов к реальным пространственно-временным данным. В качестве тестовых были выбраны модели реализации масштабных индустриальных проектов, представленные на рисунках 44а-в. Характеристики моделей, такие как количество листовых объектов, имеющих собственное геометрическое представление, минимальная и максимальная глубина иерархии, среднее и максимальное число дочерних объектов, общее количество активностей или событий в динамической сцене, пространственная наполненность сцены, указаны в таблице 2 и отражают довольно широкий спектр исследуемых данных.
Выбранные для тестирования модели содержат в себе десятки и сотни тысяч геометрических объектов, что позволяет отнести их к масштабным данным. Все объекты организованы в иерархии, однако их структуры оказываются крайне несбалансированными. Это выражается в значительной вариации уровней листовых объектов и числа дочерних объектов, принадлежащим общим родителям. Тем самым, случаи, когда один составной объект содержит в себе десятки тысяч дочерних объектов, оказываются довольно распространенными на практике. Это обстоятельство может служить еще одним аргументом в пользу развертывания вспомогательных пространственных индексов для отдельных составных объектов и использования комбинированных индексных структур.
