WWW.DISSERS.RU

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

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

Pages:     || 2 | 3 |

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

Подшивалов Алексей Юрьевич ИСПОЛЬЗОВАНИЕ ИНДУЦИРОВАННОЙ ВИРТУАЛЬНОЙ СРЕДЫ ДЛЯ АНАЛИЗА ВЗАИМОРАСПОЛОЖЕНИЯ ОБЪЕКТОВ 05.13.11 – математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ

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

Москва 2005 2

Работа выполнена в Московском государственном университете им.

М.В.Ломоносова.

Научный консультант: доктор физико-математических наук, профессор Томилин Александр Николаевич доктор физико-математических наук,

Официальные оппоненты:

профессор Михайлюк Михаил Васильевич кандидат физико-математических наук, доцент Баяковский Юрий Матвеевич

Ведущая организация:

Московский Физико-Технический Институт (МФТИ)

Защита состоится “_10_” _февраля_ 2006 г. в _11_ ч. _00_ мин. на заседании диссертационного совета Д 501.001.44 в Московском государственном университете им. М.В.Ломоносова по адресу: 119992, ГСП-2, г. Москва, Воробьевы Горы, МГУ им.

М.В. Ломоносова, 2-ой учебный корпус, факультет Вычислительной математики и кибернетики, аудитория 685.

С диссертацией можно ознакомиться в библиотеке факультета Вычислительной математики и кибернетики МГУ им. М.В. Ломоносова.

Автореферат разослан “_10_” _января_ 2006 г.

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

3

Общая характеристика работы

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

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

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

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

Цель работы 1. Исследовать возможности применения индуцированной виртуальной среды в системах управления с обратной связью.

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

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

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

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

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

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

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

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

• проводить анализ взаиморасположения для деформируемых объектов.

Практическая значимость Разработаны и реализованы методы и алгоритмы решения задач определения пространственного положения и анализа взаиморасположения объектов в системах моделирования в реальном времени. Программные реализации предложенных методов анализа взаиморасположения объектов удовлетворяет требованиям и ограничениям, сформулированным при постановке задачи, и используются в системе реального времени GL View.

Разработанные методы и алгоритмы позволяют:

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

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

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

Апробация работы и публикации Результаты работы докладывались и обсуждались на:

• научной конференции “Тихоновские чтения” (ф-т ВМиК МГУ);

• семинаре по компьютерной графике и машинному зрению под руководством Ю.М.Баяковского (ф-т ВМиК МГУ);

• семинаре «Научно-техническая визуализация» (ИМВС РАН) • научно – исследовательском семинаре по автоматизации программирования под руководством проф. М.Р.Шура-Бура (ф-т ВМиК МГУ);

Основные результаты работы изложены в 3-х научных публикациях.

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

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

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

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

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

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

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

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

Метод "перехват движений" (motion capture) технологии "Виртуальная реальность" можно использовать как базу при решении задачи определения положения объектов. В основе метода лежит слежение за относительно небольшим количеством опорных точек (маркеров). В большинстве случаев информация о моделях объектов известна априорно (конструкторская документация). Это означает, что рассмотренные выше подходы обладают высокой избыточностью, поскольку большой процент информации о положении объектов уже содержится в их моделях.

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

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

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

Величина зазора для ААВВ также зависит от начальной ориентации объекта.

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

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

Наиболее перспективным в нашем случае видится метод с использованием деревьев на основе ориентированных ограничивающих объемов (Oriented Bound Boxes - ОВВ). Основные мотивы выбора данного подхода как основы для разрабатываемых методов: достигается плотное облегание объекта, при этом глубина ОВВ деревьев меньше, чем у сферических или ААВВ деревьев.

Логически метод можно разделить на две составляюшие:

• построение ОВВ-дерева для объекта;

• проверка пары объектов, погруженных в ОВВ-деревья, на пересечение.

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

Тогда:

n m = ( pi + qi + ri ) 3n i=n i i i i i i C = j k jk ( p pk + q qk + r r ), 1 j, k j j 3n i=где Сjk - элементы ковариационной матрицы С, а векторы i i i p = pi - m, q = qi - m, r = ri - m Таким образом, получается симметрическая ковариационная матрица С. В качестве ортонормированного базиса, задающего оси объема в пространстве, используются нормированные собственные векторы полученной матрицы. Размеры параллелепипеда определяются вершинами принадлежащих ему треугольников.

Рис 1. Построение ОВВ-дерева. Двумерная проекция.

Для последующих дроблений объема применяется следующее правило.

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

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

Pages:     || 2 | 3 |






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