Использование индуцированной виртуальной среды для анализа взаиморасположения объектов тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат физико-математических наук Подшивалов, Алексей Юрьевич

• Подшивалов, Алексей Юрьевич
• кандидат физико-математических наук
• 2005

Оглавление диссертации кандидат физико-математических наук Подшивалов, Алексей Юрьевич

4

Глава 1. Проблемы анализа взаиморасположения объектов в системах 12 моделирования

1.1 Определение пространственного положения объектов.

1.2 Анализ взаиморасположения для 3D объектов.

1.2.1 Трехмерные модели объектов.

1.2.2 Обзор методов анализа взаиморасположения объектов.

1.2.3 Метод ориентированных ограничивающих объемов (ОВВ).

1.3 Виртуальная среда (ВиС) в системах моделирования. Автономная ВиС, 26 индуцированная ВиС.

Глава 2 Методы идентификации пространственного положения объектов на основе 29 регистрации координат опорных узлов

2.1 Развитие концепции управления с обратной связью с использованием 29 индуцированной виртуальной среды (ИВиС).

2.1.1 ИВиС - носитель обратной связи.

2.1.2 Роль априорной информации при реконструкции ИВиС.

2.1.3 Применение ИВиС в системах управления.

2.2 Определение пространственного положения объектов в ИВиС с 36 использованием высокоточных маркеров.

2.2.1 Определение положения объектов методом минимизации 36 функции невязки координат маркеров.

2.2.2 Исследование условий применимости метода.

2.3 Алгоритмы анализа взаиморасположения для 3D объектов высокой 41 сложности.

2.3.1 Применение метода ОВВ для анализа взаиморасположения 41 ЗО-объектов в условиях бортовых систем.

2.3.2 Адаптация алгоритмов анализа взаиморасположения для 42 деформируемых объектов.

2.3.3 Оценки качества предложенных методов.

Глава 3 Инструментальные средства анализа взаиморасположения объектов

3.1 Подсистема хранения трехмерных моделей объектов.

3.2 Библиотеки для решения задач определения положения объектов и 52 анализа их взаиморасположения.

3.3 Подсистема визуализации.

Глава 4 Применение методов идентификации пространственного положения 63 объектов с использованием инструментальных средств

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

4.2 Интерпретация результатов испытаний.

Основные результаты работы

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

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

В последнее время моделирование широко применяется для технических систем, в первую очередь, космических [12]. Космические технические системы отличаются как сложностью устройства самих систем, так и сложностью стоящих перед ними задач.

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

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

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

Новые подходы к построению систем могут быть получены с использованием методов технологии "виртуальная реальность" [17, 18]. Рассмотрим подробнее основное понятие, присущее системам моделирования, а именно, понятие «виртуальная среда» (ВиС). В виртуальную среду помещены модель наблюдаемой среды и модели находящихся в ней объектов.

Виртуальная среда может существовать независимо от существования реальной среды - в этом случае будем называть ее автономной.

К этому классу относятся разнообразные тренажерные системы, предназначенные, как правило, для обучения навыкам вождения, управления летательными аппаратами и т.п. [14]. Существует большое количество систем имитационного моделирования для изучения поведения так называемых «больших систем» из областей экономики, экологии, а также военных областей [8, 13]. Кроме того, к системам с автономной ВиС можно отнести и средства для создания виртуальных миров [16].

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

К классу систем с индуцированной ВиС относятся медицинские системы, позволяющие с помощью специальных инструментов наблюдать за состоянием внутренних органов без оперативного вмешательства [20]. К этому классу относятся большинство систем телеприсутствия. Они делятся на системы удаленного присутствия, в которых виртуальная среда отражает состояние удаленных объектов, например, роботов, работающих в опасных для человеческой жизни условиях [7, 17], и системы телеобщения, в которых человек тем или иным образом представлен в виртуальном пространстве и может взаимодействовать с искусственными агентами или личностями [18].

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

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

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

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

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

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

В современных системах моделирования такой подход зачастую является избыточным, поскольку имеется подробная априорная информация о поверхностях моделей объектов. Технология "виртуальная реальность" предоставляет качественно новые методы для решения задачи определения пространственного положения объектов. В основу нового подхода может быть положен метод motion capture ("перехват движений") [26]. Метод появился в 70-х годах и использовался для компьютерной анимации. Перехват движений базируется на слежении за относительно небольшим количеством опорных точек, прикрепленных к объекту. При условии, что объект (или его фрагмент) является "жестким", по известным координатам опорных точек можно восстановить пространственное положение всего объекта (фрагмента объекта). Основное применение метода связано с реалистичным воспроизведением человеческих движений и жестов [24, 25].

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

При использовании индуцированной виртуальной среды в системах моделирования вновь обретает актуальность задача создания и применения эффективных методов для решения проблемы анализа взаимного расположения объектов (в литературе данная проблема известна как «collision detection», interference detection») [29]. Актуальность задачи связана с появлением новых ограничений. Среди особенностей в постановке задачи выделим следующие: моделируется поведение объектов, поверхности которых обладают высокой степенью невыпуклости; к классу рассматриваемых объектов добавляются деформируемые объекты.

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

В разделе 2.3. автором предлагается подход к решению задачи анализа взаиморасположения объектов на основе метода ориентированных ограничивающих объемов [30].

Цели работы

Основными задачами данной работы являются:

• исследование возможностей применения индуцированной виртуальной среды (ИВиС) в системах управления с обратной связью;

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

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

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

Краткое содержание работы

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

В главе 2 изложены предлагаемые автором подходы к решению поставленных задач.

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

В разделе 2.2 предложено решение задачи определения пространственного положения моделей объектов в ИВиС с использованием находящихся на объектах маркеров. Задача была поставлена как определение положения произвольной точки модели объекта. Исходными данными является информация о координатах маркеров, находящихся на реальных объектах, и априорная информация о сеточных моделях объектов. Предложенный автором алгоритм минимизации функции невязки определения координат маркеров основан на методе наименьших квадратов. Исследована задача существования и единственности решения в зависимости от расположения маркеров в пространстве. Ключевым моментом для обеспечения эффективности предложенного автором подхода является совместное использование априорной информации о поверхностях объектов и метода "Motion Capture" [26], что позволяет избежать значительного усложнения вычислений при повышении сложности объектов.

В разделе 2.3 исследована проблема анализа взаиморасположения объектов сложной пространственной структуры в условиях ограниченных ресурсов, что характерно для бортовых вычислительных комплексов. Задача состояла в определении точек пересечения моделей объектов. К разрабатываемым алгоритмам были предъявлены следующие требования: высокое быстродействие, точность, эффективность работы в условиях с ограниченными вычислительными ресурсами. В основу предлагаемых алгоритмов был положен метод ориентированных ограничивающих объемов (ОВВ) [30]. В разделе 2.3.1 рассмотрены проблемы построения ОВВ-деревьев для объектов со сложной поверхностью, метод адаптирован к условиям малых ресурсов доступной оперативной памяти. В разделе 2.3.2 описано решение задачи для деформируемых объектов: предложена классификация типов деформации, для которых эффективно решается поставленная задача; показано, как с помощью совокупности различных типов деформации можно представить и исследовать произвольно деформируемые объекты. В разделе 2.3.3 даны оценки качества предложенных алгоритмов.

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

В рамках работ по внедрению разработанных программных средств в системе GL View [36] были проведены описанные в главе 4 испытания по анализу взаиморасположения элементов космических станций. Результаты испытаний показали, что предложенные методы удовлетворяют предъявленным к ним требованиям, а их быстродействие позволяет успешно использовать их в системах моделирования реального времени и в условиях бортовых вычислительных комплексов.

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Подшивалов, Алексей Юрьевич

Основные результаты работы

В процессе выполнения данной работы получены следующие результаты:

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

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

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Подшивалов, Алексей Юрьевич, 2005 год

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

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

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

4. Афанасьев В.О., Алешин В.И., Галис P.M., Дмитрущенков В.А., Томилин А.Н. Обратная трассировка на продолжении вектора сканирования картинной поверхности. "Вопросы кибернетики", Москва, 1995.

5. Афанасьев В.О., Алешин В.И., Галис P.M., Саночкин А.С., Томилин А.Н. Синхронизация погружения в виртуальную среду системы "Гипервизор". "Вопросы кибернетики", Москва, 1995.

6. Алешин В.И., Афанасьев В.О., Макаров-Землянский Н.В., Томилин А.Н., Чумаков В.А. Некоторые аспекты применения имитационных моделей с интерфейсом "Виртуальная реальность". "Вопросы кибернетики", Москва, 1995.

7. Шеннон Р. Дж. Имитационное моделирование систем искусство и наука.-М.:Мир,1978

8. Мухин В.И. Основы теории управления. Москва, Экзамен, 2002.

9. Ильин В.А., Садовничий В.А., Сендов Бл.Х. Математический анализ. Издание Московского Университета, 1985.

10. Ильин В.А., Поздняк Э.Г. Линейная алгебра. Москва, "Наука", 1984.

11. Тарасюк В.П. Математическое моделирование технических систем. Минск, 2004.

12. Гринин. Математическое моделирование в экологии. Юнити, 2003.

13. Системы моделирования: тренажеры и симуляторы. http://www.traintech.ru/ru/trainers/index.php

14. Молотов Е.П. Наземные радиотехнические системы управления космическими аппаратами. Москва, Физматлит, 2004.

15. Компьютерное моделирование и виртуальная реальность. Автоматизация проектирования, №2-1998 г.

16. Jerry Isdale. What Is Virtual Reality? http://www.isx.com/~iisdale/WhatlsVr.html

17. Fransis Hammet. Virtual reality. New York, 1993.

18. Марк Гиббс. Обзор языка VRML. Журнал Сети, №6,1996.

19. Майская. Г. Виртуальная реальность в медицине. Электроника-НТБ,№ 6,2000 г.

20. Ф.Куафе. Взаимодействие робота с внешней средой. Москва, Мир, 1985.

21. Г.П.Катыс. Восприятие и анализ оптической информации автоматическими системами. Москва, Машиностроение, 1986.

22. Г.Соколов. Новейшие тенденции и перспективы развития систем машинного зрения. Мир компьютерной автоматизации, №3, 2000 г.

23. Т. W. Calvert, J. Chapman and A. Patla, "Aspects of the kinematic simulation of human movement", IEEE Computer Graphics and Applications, Vol. 2, No. 9, November 1982, pp. 41-50.

24. Carol M. Ginsberg and Delle Maxwell, "Graphical marionette", Proc. ACM SIGGRAPH/SIGART Workshop on Motion, ACM Press, New York, April 1983, pp. 172179.

25. Motion capture overview, http://www.css.tavloru.edu/iristrmat/qraphics/ hypqraph/animation/motion capture/historvl .htm

26. Bottino A. Motion capture system.http://www2.polito.it/ricerca/cqvq/Proiects/MotionCapture/

27. R.O.Duda and P.E.Hart. Pattern classification and scene analysis. John Wiley and Sons, 1973.

28. Ming С. Lin, Stefan Gottschalk. Collision detection between geometric models: a survey, http://citeseer.ist.psu.edu/lin98collision.html

29. S.Gottschalk, M.C.Lin and D.Manocha. OBBTree: A hierarchical structure for rapid interference detection. Proc. of ACM Siggraph'96, 1996, 171-180.

30. S. Gottschalk. Separating axes theorem. Technical report TR96-024, Department of Computer Science, UNC Chapel Hill, 1996.

31. Y. Yang and N. Thalmann. An improved algorithm for collision detection in cloth animation with human body. First Pacific Conference on Computer Graphics and Application, pp. 237-251, 1993.

32. D. J. Cohen, M.C. Lin, D. Manocha, and M. Ponamgi. I-Collide: An interactive andexact collision detection system for large-scale environments. Proceeding of Symposium of1.teractive 3D Graphics, pp. 189-196,1995.

33. J. Klosowski, M. Held, J.S.B. Mitchell, H.Sowizral and K. Zikan. Efficient collision detection using bounding volume hierarchies of k-dops. In Siggraph'96 Visual Proceedings, page 151, 1996.

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