автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Перспективные методы индексирования пространственно-временных данных

На правах рукописи

Золотое Владислав Александрович

ПЕРСПЕКТИВНЫЕ МЕТОДЫ ИНДЕКСИРОВАНИЯ ПРОСТРАНСТВЕННО-ВРЕМЕННЫХ ДАННЫХ

Специальность 05.13.11 Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

Автореферат

диссертации на соискание ученой степени кандидата физико-математических наук

12 ФЕВ 2015

Москва, 2014

005559050

005559050

Работа выполнена в Федеральном государственном бюджетном учреждении науки Институте системного программирования Российской академии наук.

Научный руководитель: Семенов Виталий Адольфович,

доктор физико-математических наук, профессор

Официальные оппоненты: Галактионов Владимир Александрович,

доктор физико-математических наук, профессор, заведующий отделом Федерального

государственного бюджетного учреждения науки Института прикладной математики им. М.В. Келдыша Российской академии наук

Когаловский Михаил Рувимович, кандидат технических наук, доцент, руководитель центра интернет-ресурсов Федерального государственного бюджетного учреждения науки Института проблем рынка Российской академии наук

Ведущая организация: Федеральное государственное автономное образовательное учреждение высшего профессионального образования «Московский физико-технический институт (государственный университет)»

Защита состоится «05» марта 2015 года в 16:00 часов на заседании диссертационного совета Д 002.087.01 при Федеральном государственном бюджетном учреждении науки Институте системного программирования Российской академии наук по адресу: 109004 г. Москва, ул. Александра Солженицына, д. 25..

С диссертацией можно ознакомиться в библиотеке Федерального государственного бюджетного учреждения науки Института системного программирования Российской академии наук.

Автореферат разослан «03» февраля 2015 года.

Ученый секретарь диссертационного совета, кандидат физ.-мат. наук,

/Зеленое С.В./

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность исследования

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

Популярные СУБД общего назначения, такие как Oracle, IBM DB2, Microsoft SQL Server, предоставляют дополнительные средства пространственного индексирования многомерных данных. Однако набор методов, как правило, ограничен сбалансированными ветвистыми деревьями, хранимыми во внешней памяти. К методам этого семейства относятся обобщения B-деревьев, а также различные варианты R-деревьев. Более подробно они описаны в работах следующих авторов: Kamel, I., Faloutsos, С., Guttman, A., Sellis, Т., Roussopoulos, N., Beckmann, N., Kriegel, H. P., Schneider, R., Seeger, В. Данные методы требуют значительных вычислений при построении и обновлении индексов и поэтому их применение к динамическим данным крайне ограничено.

Методы компьютерной графики, в частности, методы отсечений на основе k-D деревьев, октальных деревьев, XY-деревьев, puzzle-деревьев, treeMap-структур в основном используются для растеризации двумерных и трехмерных данных. С ними можно ознакомиться в работах следующих авторов: Bentley, J.L., Kedem, G., Nagy, G., Wagle, S., Dengel, A., Shneiderman, В. Однако эти методы не обеспечивают реализацию перечисленных выше функций при работе со сложно структурированными данными.

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

Целью работы являлась разработка и исследование новых перспективных методов индексирования многомерных данных,

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

Рисунок 1. Пример динамической сцены.

Главное внимание в работе уделяется семейству сцен, представляющему широкий практический интерес и обладающему следующими свойствами:

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

индивидуальными геометрическими и динамическими характеристиками;

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

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

Задачи исследования предусматривали:

сравнительный анализ существующих методов индексирования многомерных данных и выбор конструктивных принципов для индексирования обсуждаемых сцен;

построение и исследование схем пространственно-временного индексирования динамических сцен с учетом особенностей исследуемого целевого семейства;

теоретический анализ вычислительной сложности операций моделирования, реализованных на основе предложенных схем индексирования;

проведение серий вычислительных экспериментов с синтезированными и реальными данными для подтверждения эффективности предложенных методов;

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

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

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

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

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

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

Апробация работы

Основные положения работы обсуждались на семинарах ИСП РАН, семинаре им. М.Р. Шура-Бура ИПМ им. М.В. Келдыша РАН, заседании кафедры «Алгоритмов и технологий программирования» факультета инноваций и высоких технологий Московского физико-технического института (государственного университета), а также докладывались на следующих российских, европейских и международных научных форумах: — международная конференция "XIII International Conference on Computing in Civil and Building Engineering", Ноттингем, Великобритания, 2010;

— европейская конференция "VIII European Conference on Product and Process Modeling in the Building Industry", Корк, Ирландия, 2010;

— международная конференция "XXI International Conference on Computer Graphics and Vision", Москва, 2011;

— международная конференция "XI International Conference on Construction Applications of Virtual Reality", Веймар, Германия, 2011;

— международная конференция "XIV International Conference on Computing in Civil and Building Engineering", Москва, 2012;

— международная конференция "XII International Conference on Construction applications of Virtual Reality", Тайбей, Тайвань, 2012;

— европейская конференция "IX European Conference on Product and Process Modeling in the Building Industry" Рейкьявик, Исландия, 2012;

— европейская конференция "X European Conference on Product and Process Modeling in the Building Industry", Вена, Австрия, 2014;

— XIX Байкальская Всероссийская конференция "Информационные и Математические Технологии в Науке и Управлении", Улан-Удэ, Максимиха, 2014.

Публикации

По теме диссертации опубликовано 13 работ, в том числе 3 статьи [1

— 3] в реферируемых научных журналах из списка изданий, рекомендованных ВАК РФ.

В работах [1-3] все научные результаты принадлежат автору. Научным руководителем Семеновым В.А. осуществлялась постановка и формализация задач, а также проводилась редакторская правка. В работе [4] автором предложены альтернативные схемы пространственно-временного индексирования, а также выполнен анализ сложности выполнения запросов с их использованием. В совместных работах [5-13] автором рассмотрены вопросы применения методов и схем индексирования для эффективного решения прикладных задач.

Личный вклад автора

Все представленные в работе результаты получены лично автором.

Объем и структура диссертации

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

СОДЕРЖАНИЕ РАБОТЫ

Во введении обоснована актуальность темы исследования, описаны цели и основные задачи работы.

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

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

— сбалансированные ветвистые деревья во внешней памяти и, прежде всего, семейства В- и Я-деревьев;

— бинарные деревья пространственной декомпозиции (к-с! деревья);

— регулярные многоуровневые сетки на основе октантных, квадрантных деревьев, а также вложенных тетраэдральных и гексагональных блоков;

— метрические деревья для быстрого поиска соседних элементов данных в метрических пространствах (¡01з1апсе-структуры, деревья покрытий и ВК-деревья);

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

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

Рисунок 2. Пример пространственной декомпозиции и соответствующего ей октального дерева.

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

Определение. Октальное дерево со строгой многоуровневой локализацией объектов и верхней границей кардинальности ячеек т назовем регулярным и обозначим Ос£гее(т).

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

Определение. Набор п одинаковых кубов с ребрами, ориентированными вдоль главных координатных осей и имеющими размер О < -, назовем модельным и обозначим как S(n, I), если они независимым и случайным образом помещены в единичный куб.

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

Лемма 1. Пусть регулярное октальное дерево глубиной h < ^log2 yj

построено для модельного набора S(n, I), тогда математическое ожидание числа объектов в октанте i-го уровня есть

Ni =

(1 — 2 1) — (1 — 2 Í) п ------— 15t г < h

(1-21~Ч)3

Теорема 1. Ожидаемая глубина регулярного октального дерева 0с1гее(т), построенного для модельного набора данных Б(п,Г) с

фактором пространственной наполненности р(п,Г) = , определяется

следующим выражением:

h =

log2-

l + (1

о3р

772 > р(п, I)

log2 \

т < р(п, I)

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

Теорема 2. Трудоёмкость построения регулярного октального дерева Octree(m) для модельного набора данных S(n, Г), выраженная в операциях определения принадлежности объекта одному из восьми дочерних октантов, равна Qdeploy = q(n,m, I) ■ п, причем коэффициент q(n,m,L) удовлетворяет следующим соотношениям:

q(п, т, Г) = [ilog2n -^log2m| при I = О, q (п, т, I) < log2 - при I > О

Теорема 3. Пусть регулярное октальное дерево Octree(m) глубиной h развернуто для модельного набора данных S(n, Г). Тогда вычислительная трудоемкость поиска столкновений, выраженная в операциях пересечения между ограничивающими объемами, может оцениваться следующим образом:

/тп 4 2 /451 \ \

Qclash < (-у- + пзтз + 186/ J + 571 п J + о(12), I О

Qciash <n2,V/e[0; 1], где пит ограничены.

(я -1) и 1.0 ■

0.8 -

0.6 -

0.4 -

0.2 -

а б

Рисунок 3. Графики приведенной стоимости определения столкновений в модельном наборе данных в зависимости от габаритов объектов: а) функция стоимости на всем диапазоне изменения габаритов объектов; б) функция стоимости при относительно небольших габаритах объектов.

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

2 Ur.l'sL

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

На рисунках 4а и 46 приведены графики, иллюстрирующие характер зависимости при разных значениях порога наполнения октантов т = 10 и т = 100 и вариации габаритов объектов 1 — 0,1 = 0.001 и I = 0.003. Видно, что сложность возрастает с увеличением числа объектов и их размеров. Нижние прямые на графиках соответствуют точечным данным, а средние и верхние кривые — протяженным объектам соответствующих размеров. Хотя анализ совпадений точечных данных имеет линейную сложность, а поиск столкновений протяженных объектов — квадратичную, для разреженных сцен различия оказываются не столь существенным даже для значительного числа объектов, составляющего на приведенных графиках 100000. Это обстоятельство оказывается чрезвычайно важным для применения обсуждаемых алгоритмов в индустриальных приложениях, оперирующих большими данными и подверженных быстрой деградации производительности даже при использовании алгоритмов невысокой полиномиальной сложности. Согласно приведенным графикам параметр наполнения октантов также влияет на стоимость поиска столкновений, однако принципиально не меняет характер исследуемых зависимостей.

3.5х 10« З.Ох 10й 2.5х 10б 2 .Ох 1С6 1.5х 10б 1.0х 10б 500 000

Рисунок 4. График стоимости локализации столкновений в зависимости от количества объектов при различных значениях габаритов (1 = 0, I = 0.001, I = 0.003) а) при пороге наполнения октантов т = 10 б) при пороге наполнения октантов т = 100.

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

пространственной и пространственно-временной декомпозиции, а также схема событийного индексирования.

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

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

Пространственный индекс Временной индекс

Рисунок 5. Схема временно-пространственной декомпозиции.

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

разрешения пространственных запросов необходимо поддерживать в октантах динамические списки локализуемых в них объектов. Такая схема также допускает несогласованные обновления этих списков.

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

— реконструкцию сцены на заданный момент времени;

— выборку объектов, лежащих в области видимости;

— анимацию выполнения проекта с изменением положения камеры.

Иерархия объектов сцены Пространственные индексы

Рисунок 6. Структура индекса для иерархически организованных данных.

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

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

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

Для анализа предложенного метода понятие модельного набора данных было обобщено следующим образом:

Определение: Модельным набором 5(п, I, К) назовем иерархически организованный набор данных, обладающий следующими свойствами:

— Каждый составной объект содержит ровно п > 1 дочерних объектов;

— Ограничивающие объемы (ААВВ) всех объектов представляют собой кубы с размерами 1,0 < I < 1/2 относительно родителей, независимым случайным образом помещенные в их объем;

— Дерево объектной иерархии сбалансировано и имеет глубину /г > 1.

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

Теорема 4. Отношение вычислительной трудоемкости построения комбинированного индекса для модельного иерархически организованного набора данных 5(п, I, К) к трудоемкости построения регулярного октального дерева для эквивалентного набора данных 5(пн, 1п) ограниченно сверху величиной 1 +

Теорема 5. Отношение суммарного количества октантов в комбинированном индексе, развернутом для модельного набора 5(п, I, к), к количеству октантов в регулярном октальном дереве, построенном для

эквивалентного набора данных I11), ограниченно сверху величиной Рпь™> где р — п13.

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

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

2,5 2 1,5 1 0,5 0

1=0

--1=0.001

------1=0.003

о О О о о

о О о о о

о О о о о

о О о о о

и! 1Л 1Л 1Л 1Л

ГЧ1 ■ч- ю 00

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

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

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

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

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

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

В другой серии экспериментов использовались реальные масштабные индустриальные модели, содержащие в себе ~ 100000 сложных геометрических объектов и имеющие развитую иерархическую организацию (см. рис. 8). Модель (а) — детальная пространственно-временная модель, описывающая ход строительных работ по возведению небоскреба в соответствии с принятым календарно-сетевым графиком. Для данной модели характерно наличие множества мелких деталей, каждая из которых обладает собственным динамическим поведением. Модель (б) описывает крупноблочный план застройки парка, состоящий из нескольких частей и не конкретизирующий детали их реализации. Визуально, выполнение каждой части плана приводит к одномоментному появлению в сцене самостоятельной проектной модели, состоящей из большого числа объектов. Модель (в) реализует план возведения моста учетом размещения и применения строительного оборудования. Особенностью модели является протяженность отдельных элементов конструкции. Наконец, модель (г) описывает план возведения и оборудования складского помещения в порту. Специфика модели состоит в развитом сценарии логистического обеспечения, подразумевающем перемещение большого количества грузов и портового оборудования.

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

(а)

(б)

(в) (г)

Рисунок 8. Индустриальные модели, используемые в вычислительных экспериментах: (а) — модель сооружения небоскреба, (б) — крупноблочный план застройки парка, (в) — план строительства моста, (г) — план оборудования приморского склада.

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

Трудоемкость развертывания индекса

I

§ т—I И '—'

и IX ? |

I |

О I

и 01 о. ш с

10 8 6 4 2 О

Октальное дерево

I Комбинированный индекс

(а)

(б)

(в)

(г)

Зат

т О

О о

"-> й. 1 <1( — Т

с: о

п

раты памяти для представления индексов

Октальное дерево

_■_■_I

I Комбинированный индекс

I

01

1

(а) (б) (в) (г)

Трудоемкость поиска коллизий

Октальное дерево

I Комбинированный индекс

I, - I

(а)

(б)

(в)

(г)

Рисунок 9. Сравнение трудоемкости развертывания индексов, затрат памяти для их представления и трудоемкости поиска коллизий с использованием октальной и комбинированной структур для тестовых моделей (а), (б), (в), (г).

0,12 ОД 0,08 8 0,06

---- Octree

■ Combined . _ Л/

0,6 0,5 0,4

<u

u 0,3 н

0,2 0,1 О

---- Octree

■ Combined

LT> ГМ m 1Л Ln 00 LD о m ID CT1

I П! I i ! I i :i 1 I I MI!

О О l О "i о

ООО

0,12 ОД 0,08 So,06

к

0,04 0,02 0

'---Octree

i

Combined

0,4 0,3

X

Ш n 1

u 0,2

i

i---Octree

■ Combined

1Л ГМ LO Ln 1Л 00 LO

Рисунок 10. Зависимость трудоемкости выборки от габаритов области для различных тестовых моделей.

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

В заключении подводятся итоги проведенного исследования.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

— Предложены и исследованы перспективные схемы пространственно-временного индексирования динамических сцен. Сформулированы и доказаны конструктивные утверждения о вычислительной сложности базовых операций моделирования и о требованиях к объему памяти для представления структур индексов;

— Предложенные схемы индексирования реализованы в виде приложения на языке программирования С++. Данная реализация послужила основой для проведения вычислительных экспериментов. На основе проведенных вычислительных экспериментов с синтезированными и реальными сценами подтверждена высокая эффективность предложенных методов индексирования;

— Проведена апробация предложенных методов индексирования в составе системы гЮ-моделирования и планирования индустриальных проектов. Применение методов позволило существенно (в некоторых случаях на несколько порядков) повысить эффективность системы и расширить ее возможности в условиях перманентно растущей сложности визуальных моделей.

СПИСОК ОПУБЛИКОВАННЫХ РАБОТ

1. В.А. Золотов, В.А. Семенов. Современные методы поиска и индексации многомерных данных в приложениях моделирования больших динамических сцен. // Труды Института системного программирования РАН том 24 / Под ред. В.П. Иванникова - М.: ИСП РАН, 2013, с. 381-416.

2. В.А. Золотов, В.А. Семенов. Исследование и развитие метода декомпозиции для анализа больших пространственных данных. // Труды института системного программирования, том 25 / Под ред. В.П. Иванникова -М.: ИСП РАН, 2013, с. 121-166, 2013.

3. В.А. Золотов, В.А. Семенов. Перспективные схемы пространственно-временной индексации для визуального моделирования масштабных индустриальных проектов. // Труды Института системного программирования РАН том 26, 2014, выпуск 2 / Под ред. В.П. Иванникова -М.: ИСП РАН, 2014, с. 175-196.

4. V.A. Semenov, K.A. Kazakov, S.V. Morozov, O.A. Tarlapan, V.A. Zolotov, T. Dengenis. 4D modeling of large industrial projects using spatiotemporal decomposition. // eWork and eBusiness in Architecture, Engineering and Construction, CRC Press, Taylor & Francis Group,London, UK, 2010, pp. 89-95.

5. V.A. Semenov, K.A. Kazakov, V.A. Zolotov, H. Jones, S. Jones. Combined strategy for efficient collision detection in 4D planning applications. // In Computing in Civil and Building Engineering, Proceedings of the International Conference, 2010, Nottingham, UK, Nottingham University Press, pp. 31-39.

6. V.A. Semenov, K.A. Kazakov, V.A. Zolotov. Topological Mapping Complex 3D Environments Using Occupancy Octrees. // Proceedings of the XXI International Conference on Computer Graphics and Vision, 2011, Moscow, Russia, p.l 11-114.

7. V.A. Semenov, S.V. Morozov, K.A. Kazakov, O.A. Tarlapan, V.A. Zolotov. Global Path Planning in Complex Environments using Metric and Topological Schemes. // Proceedings of the International CIB W078-W102 Conferences on Information Technology for Construction and Information and Knowledge Management in Building, 2011, Sophia-Antipolic, France, pp. 87-95.

8. V.A. Semenov, K.A. Kazakov, V.A. Zolotov, T. Dengenis. Virtual Construction: 4D Planning and Validation. // Proceedings of the XI International Conference on Construction Applications of Virtual Reality, 2011, Weimar, Germany, pp. 135-142.

9. B.A. Золотов, K.C. Петрищев. Локальное планирование движения на основе случайных деревьев. // Труды 54 научной конференции МФТИ. Том 2, 2011, Москва-Долгопрудный-Жуковский МФТИ, стр. 133-135.

10. V.A. Semenov, K.A. Kazakov, V.A. Zolotov. Global path planning in 4D environments using topological mapping. // eWork and eBusiness in Architecture, Engineering and Construction, CRC Press, Taylor & Francis Group, London, UK, 2012, pp. 263-269.

11. V.A. Semenov, K.A. Kazakov, V.A. Zolotov. Advanced spatiotemporal validation of construction schedules. // Proceedings of the 14'th International Conference on Computing in Civil and Building Engineering, 2012, Moscow, Russia, pp. 184-186.

12. V.A. Semenov, V.A. Zolotov, K.A. Kazakov. Spatio-temporal validation of construction projects against path conflicts. // Proceedings of 12th Conference on Construction Applications of Virtual Reality, National Taiwan University Press, 2012, Taipei, Taiwan, pp. 542-551.

13. K.C. Петрищев, B.A. Золотов, B.A. Семенов. Поиск ближайших соседей в сложных трехмерных сценах. // Труды XIX Байкальской Всероссийской конференции «Информационные и Математические Технологии в Науке и Управлении». Часть II. / Под ред. JI. В. Массель — Иркутск: ИСЭМ СО РАН, 2014, с. 56-62.

Заказ № 14-Р/01/2015 Подписано в печать 14.01.15 Тираж 100 экз. Усл. п.л. 1,0

ООО "Цифровичок", Москва, Большой Чудов пер., д.5 тел. (495)649-83-30 'Л *Jj www.cfr.ru; e-mail: zakpark@cfr.ru