WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

загрузка...
   Добро пожаловать!

Pages:     | 1 | 2 ||

3. Если объем является корнем дерева, то выполнение алгоритма заверщается.

Иначе, происходит переход к объему-родителю и повторение пункта 2.

Производится оценка сложности преобразования дерева. Пусть изменилиcь координаты m узлов сетки. Поскольку глубина дерева оценивается как O(lgn), необходимо выполнить O (m lgn) проверок объемов с возможной коррекцией.

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

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

T = NobbTobb + N Tpr + Tdef, где pr T – общее время работы алгоритма, Nobb - количество проверок для пар ограничивающих объемов, Tobb - время выполнения одной проверки для пары объемов, Npr - количество проверок пар треугольник - треугольник, T p - время выполнения одной проверки для пары треугольник- треугольник, Tdef - время коррекции ОВВ-деревьев после проведения деформаций.

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

Эффективность алгоритма проверки двух объемов на перекрывание также позволяет получить крайне малые величины Tobb, Tpr. Время Tdef коррекции ОВВ-деревьев после деформаций зависит от количества деформируемых узлов: при деформации m узлов требуется O(m lgn) операций.

Из приведенных оценок видно, что общее время, необходимое для проведения анализа столкновений, сильно зависит от конкретной сцены и характера поведения объектов, в первую очередь, от расстояния между объектами и количества деформируемых узлов. Поскольку при рассмотрении сложных сцен, основное время уходит на проверку пересечения двух объемов, достигается высокая общая эффективность работы алгоритма (при проведении испытаний с использованием персонального компьютера Pentium IV 1200 MHz среднее время работы алгоритма составило 0.022 сек).

В третьей главе описаны разработанные программные средства для решения задачи анализа взаимного расположения объектов. Для программной реализации был выбран язык С++. Состав средств анализа взаимного расположения объектов включает:

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

• библиотеку для решения задачи определения положения объектов;

• библиотеку для решения задачи анализа взаиморасположения объектов;

Модели объектов содержат следующую информацию:

• сеточную поверхность;

• ОВВ-дерево;

• список маркеров.

Базовым среди классов С++, спроектированных для описания структуры и поведения объектов, является CSceneObject (рис. 5). Этот класс содержит следующие данные: список вершин и треугольников, из которых состоит сеточная поверхность; указатель на ОВВ-дерево объекта; указатель на класс CDeformation для описания деформаций; список координат маркеров; вспомогательные структуры данных.

CSceneObject CDeformable COBBNode CDeformActiveStates CDeformMovableNotes Рис 5. Диаграмма основных классов подсистемы хранения моделей объектов.

Четвертая глава посвящена описанию испытаний разработанных программных средств и интерпретации результатов испытаний. Испытания методов анализа взаиморасположения объектов проводись при внедрении разработанных средств в систему GL View. Сеточные модели подготовлены с помощью пакета 3D Studio Max и представляют элементы Международной Космической Станции.

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

Были подготовлены модели объектов различных типов:

• жесткий объект, представляющий основной модуль Международной Космической Станции с большим числом узлов (порядка 10 тысяч узлов) и неоднородных элементов поверхности;

• жесткие объекты, представляющие стыкуемые со Станцией космические аппараты;

• деформируемые объекты с различными типами деформации (солнечные батареи, специальные «ворота» с изменяемой геометрии и др.).

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

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

Название показателя Результат Количество итераций работы системы Среднее время анализа сцены на каждой итерации 0.022 сек Количество зафиксированных точек пересечения объектов Общее количество проверок пар объемов Общее количество проверок пар треугольников Среднее время коррекции ОВВ-деревьев 0.005 сек Таблица 1. Быстродействие методов анализа взаиморасположения объектов без ограничений по затратам оперативной памяти.

Из таблицы видно, что среднее время анализа взаиморасположения для всех объектов сцены занимает примерно 1/50 секунды, а значит, позволяет применять предложенные методы в системах реального времени. Сравнение быстродействия различных методов приведено на рис. 6.

Рис. 6. Быстродействие методов анализа взаиморасположения объектов.

Зависимость быстродействия методов от ограничения по объему оперативной памяти приведена в таблице 2.

Ограничения по оперативной памяти Среднее время работы (сек) Без ограничения 0.10 Mb 0.3 Mb 0.1 Mb 0.Таблица 2. Зависимость быстродействия методов анализа взаиморасположения объектов от объема используемой оперативной памяти.

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

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

В заключении сформулированы основные результаты работы Основные результаты работы 1. Предложена концепция построения систем управления с обратной связью с использованием индуцированной виртуальной среды (за счет добавления стадии реконструкции виртуальной среды с совместным использованием априорной и оперативной информации об объектах).

2. Разработан новый алгоритм определения пространственного положения объектов по координатам маркеров.

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

4. Созданы программные средства для решения задачи анализа взаиморасположения объектов. Проведены испытания на моделях элементов космических станций в системе реального времени GL View. По результатам испытаний даны оценки быстродействия и точности применяемых методов.

Благодарности Автор выражает глубокую благодарность А.Н.Томилину за постоянную поддержку и внимание к работе, В.О.Афанасьеву за поддержку, ценные советы и замечания и М.А.Торгашеву за полезные замечания по программной реализации.

Публикации по теме диссертации [1] Подшивалов А.Ю. Определение пространственного расположения 3D объектов по маркерам. "Программные системы и инструменты №4", издательство МГУ, Москва, 2003.

[2] Подшивалов А.Ю. Эффективные алгоритмы анализа взаимного расположения сильно развлетвленных пространственных объектов. "Программные системы и инструменты №3", издательство МГУ, Москва, 2003.

[3] Подшивалов А.Ю. Использование индуцированной виртуальной среды для развития концепции управления с обратной связью. Электронный журнал "Исследовано в России", 38, стр. 411-418, 2005.

Рис. 7. Проведение испытаний по анализу взаиморасположения объектов на моделях элементов космических станций.

Pages:     | 1 | 2 ||






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»