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

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

Подшивалов Алексей Юрьевич

ИСПОЛЬЗОВАНИЕ ИНДУЦИРОВАННОЙ ВИРТУАЛЬНОЙ СРЕДЫ ДЛЯ АНАЛИЗА ВЗАИМОРАСПОЛОЖЕНИЯ ОБЪЕКТОВ

05 13.11 - математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ

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

Москва 2005

Работа выполнена в М.В.Ломоносова.

Московском государственном университете им.

Научный руководитель: Официальные оппоненты:

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

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

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

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

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

Защита состоится " 10 " Февраля 2006 г. в 11 ч. 00 мин на заседании диссертационного совета Д 501.001.44 в Московском государственном университете им. М.В.Ломоносова по адресу: 119992, ГСП-2, г. Москва, Воробьевы Горы, МГУ им. М.В Ломоносова, 2-ой учебный корпус, факультет Вычислительной математики и кибернетики, аудитория 685.

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

Автореферат разослан * 10 " января 2006 г.

Ученый секретарь Диссертационного совета

кандидат физико-математических наук, профессор —. Трифонов Н.П.

¿00& А

т

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

Актуальность работы

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

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

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

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

Цель работы

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

Рве НАЦИОН А Л БИБЛМОТЬКА

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

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

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

Научная новизна работы

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

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

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

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

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

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

Практическая значимость

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

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

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

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

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

Апробация работы и публикации

Результаты работы докладывались и обсуждались на

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

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

• семинаре «Научно-техническая визуализация» (ИМВС РАН)

• научно - исследовательском семинаре по автоматизации программирования под руководством проф М Р Шура-Бура (ф-т ВМиК МГУ),

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

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

Содержание работы

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

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

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

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

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

Исходными данными для определения пространственного

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

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

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

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

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

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

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

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

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

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

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

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

р', с/, г* - векторы из трех элементов, описывающие вершины 1-го треугольника Тогда:

Зп

где С/* - элементы ковариационной матрицы С, а векторы

—1 I I /

р = р -т, д =д -т, г = г -т

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

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

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

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

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

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

Рис. 2 Проверка прямой на разделение двух объемов

Пусть даны два объема, А и В. Пусть относительно координат объема А объем В задается матрицей поворота 11 и вектором сдвига Т. Пусть полудлины ребер А и В равны соответственно а», яг, аз, и Ь*, Ь2, Ь3, а направления ребер объемов задаются как векторы А1 и В*, где / =1,2,3 Поскольку векторы направлений объемов взаимно ортогональны, то длина проекции объема на прямую равна сумме длин проекций каждого из трех ребер, то есть

г. = Хя,|(Л',£)|

Расстояние между проекциями центров объемов равно \(Т,Ц\ Отсюда получаем искомое неравенство'

.=1 1-1

Если оно выполняется, то интервалы, а значит и объемы, не пересекаются.

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

Рис. 3. Управление с обратной связью

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

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

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

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

Принципиальным отличием системы управления с ИВиС является наличие звена реконструкции состояния ИВиС. Поэтому по каналу обратной связи

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

Роль априорной информации - многократно увеличивать «полезность» передаваемой информации. Можно сравнить объемы данных, которые необходимы для передачи набора двумерных изображений объектов и данных о местоположении маркеров. В первом случае каждое изображение будет содержать порядка 104 пикселей, во втором случае достаточно координат 4-х маркеров.

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

Требуется определить координаты заданного узла объекта в мировой СК. Для этого достаточно отыскать матрицу преобразования А локальной СК объекта в мировую:

Для описания трехмерных преобразований в компьютерной графике часто используют так называемые «однородные координаты». К трем координатам векторов добавляют четвертую, которая всегда равна единице Тогда с помощью матрицы размерностью 4x4 очень удобно описывать ортогональные преобразования

Тогда координаты /-го маркера х,р""1 уГш, г/™", построенные с помощью найденного преобразования, определяются следующим образом.

"П °\2 й13 °14

ООО

где х,06, у¡°б, г/*- координаты маркера в СК объекта

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

Введем функцию невязки между вычисленными и реальными координатами маркеров как функцию от коэффициентов искомой матрицы:

/К

1 = 1

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

аргументам вычисляются аналогично):

Л',, =2аи£(х?У+2а12£хГуГ + 2au±xfz?+2аи±х?-2±х?х,

1=1 |«| /=1 1=1 /=1

fin = 2au±xfyf + 2ап±(у?У + 2an±yfzf + 2au±yf -2±yfx,

1=1 i*i i=i i=I i»i

Г,з = 2au±x^ + 2aa±y?z? + 2a„£(z;")2 +2au±zf -2±z<?x,

i-i /-1 i=i i-i I-1

/;,4 =2an±xf + 2an±yf + 2al}±zf +2aIAn-2±xl i-i /=i /-i >»i

Получаем систему из 12 линейных уравнений с 12-ю неизвестными, которая распадается на 3 независимых системы для коэффициентов а«-3м, аггЯы, ац-аз4-Например, для коэффициентов ац-аи система уравнений записывается в следующем виде:

ап£(х?У +ап£х?у? +a„£x?zf +а„£х? =±xfxt (1)

i-i ;=i I-I /=1 <-1

°и±х?У*+°п±{У?)2 + + aH±yf =±у?х, (2)

i-i i=i i-i i=i i-i

an±x*z*+an£y*zf +an±{z*Y+au±z* = £zfx, (3)

/=| 1=1 i* I im\ /=]

+an±yf +an£zf +а,,п = ±х, (4)

i=i м 1=1 1=1

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

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

преобразования А на вектор координат этого узла в СК объекта fx06, у0®, Z06,1)

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

Исследуем выражение для определителя матрицы системы (1)-(4). Для упрощения выкладок рассмотрим двумерный случай. Тогда определитель матрицы будет равен:

deM = n±(xff±(yff -n(±xfyff + 2±х?±у?±х?у? -

1=1 /=1 1=1 (=1 1.1 /= I ^

-t(xf)\±yff-(ixff±{,xff 1=1 /=1 1=1 (=1

В случае, когда количество маркеров п=2 определитель тождественно равен нулю (что очевидно исходя из постановки задачи). Рассмотрим случай, когда п=3. Пусть координаты маркеров в системе координат объекта равны (ah bj, i = 1..3.

Подставив координаты маркеров в формулу (5) и проведя преобразования, получим следующее выражение для определителя:

(И А = 3 (а,2 + а\ + а] )(62 + Ь\ + ¿3) - 3(а, + агЬг + а, Ь} )2 + + 2(а, + я2 + а3 )(6, +Ьг+Ьъ 6, +а2Ь2 +а3Ь3)~ (а2 + а2 + а, )(6, + 62 + ¿>3 )2 - (6) -(в, + а2 + а3 )2(б2 + 62 + 63) = (а, (А2 -Ьг) + аг{Ь% -6, ) + я3(6, -¿2)Г

Формула (6) представляет собой полный квадрат, а значит, определитель равен нулю только в случае, когда равно нулю выражение в скобках Если Ь/ = Ьу, , равенство нулю очевидно. Если это не так, выражение в скобках можно представить в виде:

Ьг~Ь\ Ьг-Ьг

Равенство (7) выполняется тогда, когда все три маркера лежат на одной прямой В случае п>3 получим формулы, аналогичные (6), содержащие сумму квадратов. Каждый элемент суммы описывает тройки маркеров, и равен нулю, если эти три маркера лежат на одной прямой. Таким образом, определитель будет равен нулю, если все п маркеров лежат на одной прямой.

В трехмерном случае, проведя аналогичные рассуждения, получим формулы для вычисления определителя, также состоящие из суммы квадратов. При п^З в силу постановки задачи определитель тождественно равен нулю. При п£4 каждый член суммы описывает четверки маркеров, а его равенство нулю означает, что все четыре маркера лежат в одной плоскости. Формулы для трехмерного случая опущены из-за их громоздкости.

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

плоскости.

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

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

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

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

Предлагаемое решение проблемы состоит в выборе компромисса между стремлением достичь высокой производительности при выполнении алгоритмов и уменьшить затраты оперативной памяти. Возможности здесь достаточно велики: при уменьшении глубины дерева на к, число его узлов, а значит и расход памяти, уменьшается в 2* раз. Например, для к=3, дерево будет занимать в 8 раз меньше памяти С другой стороны, объемы-листья дерева будут содержать по 2* треугольников, и в случае плотного контакта участков поверхностей с недостроенными деревьями потребуется гораздо больше проверок для пар треугольников. Однако, испытания показали, что увеличение времени вычисления незначительно, а уменьшение затрат оперативной памяти существенно. В

рассматриваемых сценах, при уменьшении объема памяти в 8 раз, время работы метода увеличивалось в 1,4 раза.

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

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

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

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

3 Если объем является корнем дерева, то выполнение алгоритма заверщается. Иначе, происходит переход к объему-родителю и повторение пункта 2.

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

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

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

Т = NobbTobb + NprTpr + Tdef, где

T - общее время работы алгоритма,

Ыоьь - количество проверок для пар ограничивающих объемов,

Тоьь - время выполнения одной проверки для пары объемов,

Npr - количество проверок пар треугольник - треугольник,

Тр - время выполнения одной проверки для пары треугольник- треугольник,

Tdet - время коррекции ОВВ-деревьев после проведения деформаций

Чем меньше расстояние между объектами, тем больше требуется тестов на перекрывание. С использованием ОВВ-деревьев, обеспечивается получение относительно небольших значений Ы0ьь и Npr из-за плотного облегания объекта. Эффективность алгоритма проверки двух объемов на перекрывание также позволяет получить крайне малые величины Т0ьь, Тр,. Время Tdef коррекции ОВВ-деревьев после деформаций зависит от количества деформируемых узлов: при деформации m узлов требуется 0(m 1дп) операций.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Название показателя Результат

Количество итераций работы системы 1557

Среднее время анализа сцены на каждой итерации 0 022 сек

Количество зафиксированных точек пересечения объектов 12782

Общее количество проверок пар объемов 221050

Общее количество проверок пар треугольников 36512

Среднее время коррекции ОВВ-деревьев 0 005 сек

Таблица 1 Быстродействие методов анализа взаиморасположения объектов без ограничений по затратам оперативной памяти.

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

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

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

Ограничения по оперативной памяти Среднее время работы (сек)

Без ограничения 0 022

10 МЬ 0 023

ЗМЬ 0 027

1 МЬ 0 032

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

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

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

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

В заключении сформулированы основные результаты работы

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

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

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

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

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

Благодарности

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

Публикации по теме диссертации

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

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

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

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

Для заметок

Для заметок

Заказ № 02/01/05 Подписано в печать 28.12.2005 Тираж 100 экз. Усл. п.л. 0,92

\ ООО "Цифровичок", тел. (095) 797-75-76; (095) 778-22-20 Л \vw\v. с/г. ги; е-таН: т/о@с/г. ги

¿ooM

99<f

O 6 - 9 p f

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. По результатам испытаний даны оценки быстродействия и точности применяемых методов.

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.