Содержание к диссертации
Введение
Глава 1. Проблемы анализа взаиморасположения объектов в системах моделирования 12
1.1 Определение пространственного положения объектов, 12
1.2 Анализ взаиморасположения для 3D объектов. 14
1.2.1 Трехмерные модели объекгоз. 14
12.2 Обзор методов анализа взаиморасположения объектов. 16
1.2.3 Метод ориентированных ограничивающих объемов (ОВВ). 20
1.3 Виртуальная среда (ВиС) в системах моделирования. Автономная ВиС, индуцированная ВиС. 26
Глава 2 Методы идентификации пространственного положения объектов на основе регистрации координат опорных узлов 29
2.1 Развитие концепции управления с обратной связью с использованием 29
индуцированной виртуальной среды (ИВиС).
2.1.1 ИВиС - носитель обратной связи. 29
2.1.2 Роль априорной информации при реконструкции ИВиС. 31
2.1.3 Применение ИВиС в системах управления. 33
2.2 Определение пространственного положения объектов в ИВиС с 36
использованием высокоточных маркеров.
2.2.1 Определение положения объектов методом минимизации функции невязки координат маркеров . 36
2.2.2 Исследование условий применимости метода. 39
2.3 Алгоритмы анализа взаиморасположения для 3D объектов высокой 41
сложности.
2.3.1 Применение метода ОВВ для анализа взаиморасположения ЗD -объектов в условиях бортовых систем. 41
2.3.2 Адаптация алгоритмов анализа взаиморасположения для деформируемых объектов. 42
2.3.3 Оценки качества предложенных методов. 46
Глава 3 Инструментальные средства анализа взаиморасположения объектов 43
3.1 Подсистема хранения трехмерных моделей объектов. 49
3.2 Библиотеки для решения задач определения положения объектов и анализа их взаиморасположения . 52
3.3 Подсистема визуализации. 61
Глава 4 Применение методов идентификации пространственного положения объектов с использованием инструментальных средств 63
4.1 Проведение испытаний по анализу взаиморасположения элементов 63
космических станций,
4.2 Интерпретация результатов испытаний. 69
Основные результаты работы 74
Литература
- Анализ взаиморасположения для 3D объектов.
- Метод ориентированных ограничивающих объемов (ОВВ).
- Определение положения объектов методом минимизации функции невязки координат маркеров
- Библиотеки для решения задач определения положения объектов и анализа их взаиморасположения
Введение к работе
В настоящее время интенсивно развивается направление, связанное с созданием систем моделирования и их применением в различных областях науки и техники [8]. Это связано, в первую очередь, с быстрым развитием информационных технологий и экспоненциальным ростом производительности вычислительных комплексов. Моделирование производится в тех случаях, когда реальное проведение эксперимента невозможно или нежелательно по тем или иным причинам, в частности из-за высокой стоимости эксперимента и высокой цены риска. В ряде случаев моделирование является единственной альтернативой получения информации о поведении объектов и их характеристиках.
В последнее время моделирование широко применяется для технических систем, в первую очередь, космических [12]. Космические технические системы отличаются как сложностью устройства самих систем, так и сложностью стоящих перед ними задач.
Моделирование технических систем в процессе управления ими представляет собой сложную и объемную задачу, В этом случае требуется принимать решения в течение заданного короткого промежутка времени (режим реального времени). Основной особенностью здесь является быстрая смена состояния объектов системы и наличие обратной связи по параметрам, описывающим их состояние. При этом построение модели ситуации осуществляется на основе оперативных данных, поступающих от подсистем слежения за реальными объектами. Физическая система и система моделирования функционируют параллельно, а состояние и поведение моделей объектов воспроизводится на основе информации, поступившей на текущий момент времени. Характерным примером является моделирование процессов стыковки и сборки сложных элементов орбитальных станций.
Использование существующих подходов далеко не всегда позволяет решать подобные задачи за приемлемое время. Актуальным на сегодняшний день является проблема создания и применения новых подходов к построению таких систем моделирования.
Применение подобных систем наиболее актуально в областях, где они в ближайшее время могут оказаться незаменимыми при проведении сложных операций, сопряженных с высоким риском, например, при создании и эксплуатации больших космических орбитальных станций, проведении планетных экспедиции и т.п.
Новые подходы к построению систем могут быть получены с использованием методов технологии "виртуальная реальность" [17, 18]. Рассмотрим подробнее основное понятие, присущее системам моделирования, а именно, понятие «виртуальная среда» (ВиС). В виртуальную среду помещены модель наблюдаемой среды и модели находящихся в ней объектов.
Виртуальная среда может существовать независимо от существования реальной среды - в этом случае будем называть ее автономной,
К этому классу относятся разнообразные тренажерные системы, предназначенные, как правило, для обучения навыкам вождения, управления летательными аппаратами и т.п. [14], Существует большое количество систем имитационного моделирования для изучения поведения так называемых «больших систем» из областей экономики, экологии, а также военных областей [8, 13]. Кроме того, к системам с автономной ВиС можно отнести и средства для создания виртуальных миров [16].
В рамках данной работы больший интерес представляют системы, в которых виртуальная и реальная среды функционируют параллельно. В случае, если виртуальная среда воссоздается на основе информации, поступающей из реальной системы, будем называть ее индуцированной.
К классу систем с индуцированной ВиС относятся медицинские системы, позволяющие с помощью специальных инструментов наблюдать за состоянием внутренних органов без оперативного вмешательства [20]. К этому классу относятся большинство систем телеприсутствия. Они делятся на системы удаленного присутствия, в которых виртуальная среда отражает состояние удаленных объектов, например, роботов, работающих в опасных для человеческой жизни условиях [7, 17], и системы телеобщения, в которых человек тем или иным образом представлен в виртуальном пространстве и может взаимодействовать с искусственными агентами или личностями [18].
Наблюдается следующая картина использования существующих систем моделирования. В подавляющем большинстве случаев цели, поставленные перед системами, состоят в реалистичном воспроизведении состояния объектов моделирования и достигаются за счет высокопроизводительной подсистемы отображения, позволяющей тем или иным способом осуществить погружение наблюдателя в виртуальный мир [7] и (или) визуализировать информацию, поступающую от подсистемы наблюдения за удаленными объектами. То есть основой большинства систем является система отображения, предназначенная для создания визуальных, звуковых, тактильных, гравитационных эффектов.
Однако индуцированные виртуальные среды могут быть использованы не только как средство отображения состояния объектов, но и как основа при создании систем управления отими объектами.
Рассмотрим подробнее процесс воссоздания состояния моделей объектов в виртуальной среде, В классической постановке в системах управления сигнал обратной связи целиком извлекается из физической системы [9]. Это означает, что в систему управления необходимо передавать всю информацию, необходимую для формирования управляющего воздействия, что может быть неэффективно при высокой сложности управляемых объектов.
В технических системах большой процент информации о свойствах моделей объектов часто известен заранее (например, конструкторская документация). При совместном использовании априорной и апостериорной информации методы слежения за объектами и воссоздания их состояния могут быть упрощены, а объемы информации, передаваемой из физической среды в систему управления, радикально понижены. Таким образом, индуцированная виртуальная среда может быть использована для создания принципиально новых подходов при моделировании и управлении объектами. Отметим, что в данной работе не рассматриваются традиционные аспекты систем моделирования, связанные с отображением.
В разделе 2.1 показано, при каких условиях индуцированная виртуальная среда может быть использована как основа для создания и применения качественно новых подходов к построению систем моделирования реального времени.
Одной из актуальных проблем при реконструкции индуцированной виртуальной среды (то есть восстановлении состояния объектов и окружающей среды) является задача определения положения объектов в пространстве. При решении этой задачи традиционно используются системы технического зрения [21], основанные, как правило, на методах распознавания образов в получаемых изображениях физической системы [22, 23]. Такие методы сложны и требуют большого объема вычислений. Кроме того, при движении объектов на расстояниях, соизмеримых с их размерами, необходимо следить за большим количеством узлов моделей объектов, что приводит к еще большему усложнению задачи.
В современных системах моделирования такой подход зачастую является избыточным, поскольку имеется подробная априорная информация о поверхностях моделей объектов. Технология "виртуальная реальность" предоставляет качественно новые методы для решения задачи определения пространственного положения объектов. В основу нового подхода может быть положен метод motion capture ("перехват движений1 ) [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 описаны разработанные инструментальные программные средства для решения задач определения положения объектов и анализа их взаимного расположения. Программные компоненты реализованы на языке C++, что позволило достигнуть гибкости при их использовании, сохранив при этом высокую эффективность выполнения вычислений.
В рамках работ по внедрению разработанных программных средств в системе GL View [36] были проведены описанные в главе 4 испытания по анализу взаиморасположения элементов космических станций. Результаты испытаний показали, что предложенные методы удовлетворяют предъявленным к ним требованиям, а их быстродействие позволяет успешно использовать их в системах моделирования реального времени и в условиях бортовых вычислительных комплексов.
Анализ взаиморасположения для 3D объектов.
Информацию об объектах можно классифицировать по нескольким признакам, например: данные, описывающие форму объектов, и данные, описывающие их поведение (и/или особенности движения); априорные данные и данные, поступающие в процессе работы системы и описывающие изменения пространственного положения объектов, их формы (деформации объектов) и т.п. Выбор подхода для описания объектов определяется их сложностью и задачами, поставленными перед системой. Существует много способов для описания как формы объектов, так и их поведения. На рис.1 представлена одна из классификаций поверхностей объектов [28].
Полигональные модели объектов являются самым распространенным типом преставления 3D объектов в компьютерной графике и моделировании. Широкое использование полигональных моделей определяется, в первую очередь, возможностью представления практически любых поверхностей с помощью многоугольников (полигонов). Обычно используются треугольники как самая простая основа для представления участка плоскости. Кроме того, для таких моделей разработаны аппаратные средства ускорения визуализации.
Наиболее общим классом являются так называемые "полигональные супы", то есть неупорядоченный набор полигонов в пространстве. Для таких полигонов нельзя использовать какую-либо топологическую информацию о свойствах поверхностей. Многие из реально существующих объектов, по большей части жесткие конструкции, удается представить с помощью выпуклых полигонов. Для их обработки разработано большое количество алгоритмов, включая алгоритмы по анализу столкновений. Полигональные поверхности с выпуклыми многоугольниками также называют сеточными поверхностями. Узлами сетки называют вершины, а примитивами - набор треугольников, связывающих вершины. Иногда объекты содержат невыпуклые полигоны. Однако на практике такой случай рассматривается крайне редко, а для устранения невыпуклостей обычно применяют методы триангуляции.
Поверхности неполигональных моделей делятся на три класса: поверхности конструктивной геометрии, неявные поверхности и параметрические поверхности.
Объекты с поверхностями, относящимися к классу конструктивной геометрии (Constructive solid geometry - CSG), задаются с помощью простых геометрических фигур - примитивов. К числу таковых относятся параллелепипед, сфера, конус, тор и т.д. Построение объекта осуществляется заданием логических операций над примитивами: объединение, пересечение, разность и т.п. Преимуществом данного типа является возможность построения сложных объектов, используя всего несколько простых поверхностей. Очевидно, что количество примитивов будет значительно меньше, чем число узлов сеточной модели объекта. Использование логических операций также упрощает алгоритмы по анализу столкновений. Недостатком CSG моделей является трудность проведения некоторых операций, например сглаживания. Кроме того, трудно осуществить построение объемов, ограничивающих CSG-объекты, и их иерархий, что часто используется для рендеринга и анализа столкновений.
Неявные поверхности (Implicit surfaces) определяются с помощью неявных функций f: Rj- R Условие равенства функции нулю определяет множество точек пространства, принадлежащих поверхности. Такие поверхности часто используются в качестве примитивов CSG. Алгоритмы работы с неявными поверхностями предназначены, как правило, для специальных подмножеств функций: алгебраических функций, функций, описывающих поверхности второго или четвертого (quadrics) порядка сложности и т.д.
Параметрические поверхности определяются функциями вида f : R2 - /. Данный класс позволяет описывать не только замкнутые поверхности (в отличие от CSG и неявных поверхностей). Специальный подкласс параметрических поверхностей, называемый NURBS (Non-Uniform Rational B-Spline), широко применяется в CAD системах.
Необходимо также упомянуть о языке VRML (Virtual Reality Markup Language) и семействе ему подобных языков, таких как Cyberspace Description Format и Manchester Scene Description Language [19]. VRML предоставляет все основные возможности для описания реалистичных ЗО-сцен и ориентирован, в первую очередь, на использование в сети internet. VRML-файл представляет собой обычный ASCII текст с описанием всех участников сцены; объектов, состоящих из примитивов, источников света, текстур и т.п.
Метод ориентированных ограничивающих объемов (ОВВ).
Построение ОВВ-дерева для объекта. При построении ОВВ-дерева выполняется два типа операций: построение объема, облегающего объект или часть объекта, и построение иерархии ограничивающих объемов. Рассмотрим часть сеточной модели объекта, состоящую из л треугольников. Для того, чтобы построить ограничивающий их объем, требуется определить ориентацию объема и его длину вдоль каждой из пространственных осей.
Для нахождения ориентации объема согласно [30] необходимо вычислить общий центр масс треугольников т и ковариационную матрицу С,, Пусть р , q7, г -векторы из трех элементов, описывающие вершины / -го треугольника. Тогда: где Cjk- элементы ковариационной матрицы С, а векторы р -ps-m q ql -т, г =rf -т
Таким образом, получена симметрическая ковариационная матрица С размером 3x3. В качестве ортонормированного базиса, задающего оси объема в пространстве, будем использовать нормированые собственные векторы полученной матрицы.
Для определения размеров объема используется понятие экстремальных вершин. Вершина является экстремальной по данной координате, если среди рассматриваемого множества вершин данная ее координата имеет минимальное или максимальное значение. Размером объема считается размер параллелепипеда, грани которого параллельны соответствующим векторам базиса и проходят через экстремальные вершины.
Процесс последовательного дробления охватывающего объект объема можно представить иерархической структурой, в которой корнем дерева является объем, охватывающий весь рассматриваемый объект. Для последующих дроблений объема применяется следующее правило. Упорядочим оси объема по убыванию длины. Деление объема происходит вдоль самой длинной из осей с помощью плоскости, ортогональной самой оси. Треугольники, принадлежащие объему, делятся между объемами-потомками в зависимости от того, по какую сторону от разделяющей плоскости лежит центр масс треугольника. Двухмерный аналог такого деления показан на рис,2.
Координата деления вдоль оси определяется положением центра масс треугольников т. Такой выбор основывается на предположении построения сбалансированного дерева. Если не удается разделить объем вдоль самой длинной оси, выбирается следующая по длине ось и повторяются те же действия. Случай, когда деление не может быть выполнено ни в одном направлении, определяет окончание процесса. Таким образом, каждому объему-листу дерева может принадлежать один или несколько треугольников.
Сложность построения ОВВ-дерева оценивается как 0(п 1дп). Дествительно, для построения каждого слоя дерева требуется 0(п) операций, а глубина дерева определяется как 0(1д п)ш Необходимо отметить, что построение ОВВ-деревьев для объектов выполняется на предварительном этапе вычислений.
Проверка пары объектов на пересечение. Для того, чтобы определить, пересекаются ли объекты, производится проверка на перекрывание пар объемов, входящих в ОВВ-деревья объектов, начиная с корневых объемов и далее, вплоть до листьев дерева. Отсутствие пересечения двух объемов заведомо гарантирует отсутствие пересечения самих объектов в узлах сетки, ограниченными этими объемами. В этом случае спуск по дереву прекращается. В случае пересечения двух объемов на данном уровне проводится проверка для всех пар объемов следующего уровня иерархии. Если один из объемов является листом дерева, то процедура проверки вызывается для него и двух объемов-потомков второго дерева. Если же оба объема являются листьями, то процедура проверки вызывается для всех пар треугольников, принадлежащих соответствующим объемам.
Следует отметить, что наличие пересечения двух объемов лишь сужает область поиска. Наличие же пересечения треугольников указывает на контакт между объектами и точно определяет узлы, в которых сеточные модели объектов пересекаются.
В процессе работы алгоритма анализа взаиморасположения объектов основное время занимает тестирование пар ОВВ на перекрывание. Стандартный способ проверки (проверить все пары граней) занимает слишком много времени и является малопригодным при обработке больших деревьев. Поэтому рассмотрим алгоритм, предложенный в [30], как наиболее эффективный из известных автору.
Проверка двух ОВВ на перекрывание. Выберем некоторую прямую в пространстве и спроектируем на нее рассматриваемые ОВВ. Каждая проекция представляет собой отрезок этой прямой. Если отрезки не пересекаются, то не пересекаются и сами объемы. В этом случае выбранная прямая называется "разделяющей прямой", а плоскость, перпендикулярная этой прямой, "разделяющей плоскостью". В противном случае необходим дальнейший анализ-Определим множество прямых, которые необходимо проверить.
Определение положения объектов методом минимизации функции невязки координат маркеров
Задача, рассматриваемая в данной работе, состоит в определении пространственного положения объектов на основе информации о трехмерных координатах маркеров, закрепленных за объектами, и априорной информации о моделях объектов. Априорная информация содержит, в том числе, координаты маркеров и узлов сеточной модели объектов в их локальных системах координат (СК). Для того, чтобы уметь определять координаты произвольной точки модели объекта в мировой СК, достаточно построить матрицу преобразования локальной СК объекта в мировую.
Вообще говоря, для построения матрицы преобразования достаточно знать координаты любых трех маркеров, не лежащих на одной прямой. Однако на практике количество маркеров может быть существенно большим (кроме того, количество доступных для системы слежения маркеров может меняться по времени), а координаты маркеров определяются с некоторой погрешностью.
Введем функцию невязки между вычисленными и реальными координатами маркеров. Тогда решение задачи сводится к отысканию матрицы преобразования, которая минимизирует функцию невязки.
Рассмотрим произвольный объект моделируемой сцены. Пусть подсистема слежения определила ЗО-координаты л маркеров, прикрепленных к данному объекту. Будем искать коэффициенты матрицы преобразования, заданной в виде;
Здесь необходимо сделать некоторые пояснения. Искомое преобразование является ортогональным (сохраняются расстояния и углы). Для описания трехмерных преобразований в компьютерной графике часто используют следующий подход, К трем координатам векторов добавляют четвертую, которая всегда равна единице. Тогда с помощью матрицы размерностью 4x4 очень удобно описывать ортогональные преобразования: коэффициенты ац-азз описывают преобразование поворота, а коэффициенты аи&мам - сдвига.
За основу метода минимизации невязки возьмем метод наименьших квадратов [14].
Пусть мы определили коэффициенты матрицы преобразования. Тогда координаты /-го маркера xfGU t уґш z,peuit построенные с помощью найденного преобразования, определяются следующим образом: где ж?5, у 6, Zf6 - координаты маркера в СК объекта (известны априорно). Невязка определения координат /-го маркера записывается в виде:
Таким образом, функция невязки для объекта в зависимости от коэффициентов матрицы преобразования записывается в виде:
Для определения точки минимума функции /запишем ее частные производные по всем аргументам {ниже приведены производные по аргументам ац-а14, производные по остальным аргументам вычисляются аналогично):
В итоге получаем систему из 12 линейных уравнений с 12-ю неизвестными. Заметим, что вся система распадается на 3 независимых системы для коэффициентов ац-а14 &zr&24t ЗзгЗм. Например, для коэффициентов ац а и система уравнений записывается в следующем виде: i i i=] j=i /=i
Если случай невырожденный, и определители матриц систем линейных уравнений не равны нулю, получим единственное решение. Это решение и будет точкой минимума функции невязки. Действительно, при стремлении аргументов к плюс-минус бесконечности функция невязки стремится к плюс бесконечности, а значит (поскольку функция невязки является непрерывной и дифференцируемой во всех точках) в случае равенства нулю производной в единственной точке, эта точка должна являться точкой минимума.
Итак, получив решение системы уравнений, определяются коэффициенты матрицы преобразования из СК объекта в мировую СК. Таким образом, для того чтобы получить вектор координат любого узла сеточной модели объекта в мировой СК (хмирі умир 7 upf 1), необходимо умножить найденную матрицу преобразования А на вектор координат этого узла в СК объекта (хб,уб, z6, 1).
Условия существования и единственности решения. Определение коэффициентов матрицы преобразования построено на решении системы линейных уравнений. Для того, чтобы система линейных уравнений имела единственное решение, необходимо и достаточно, чтобы определитель матрицы этой системы был отличен от нуля.
Исследуем выражение для определителя матрицы системы (4)-(7). Для упрощения выкладок рассмотрим двумерный случай. Тогда определитель матрицы будет равен:
В случае n=2 определитель тождественно равен нулю (что очевидно, исходя из постановки задачи), Рассмотрим случай п 2 : пусть, например, л-3, а координаты маркеров в системе координат объекта равны (а,, Ь;), І = 7.,3. Подставив координаты маркеров в формулу (8) и проведя преобразования (в целях сокращения записи они опущены), получим следующее выражение для определителя:
Формула (9) представляет собой полный квадрат, а значит, определитель равен нулю только в случае, когда равно нулю выражение в скобках. Если bf = bjt i?$ , равенство нулю очевидно. Если это не так, выражение в скобках можно представить з виде
Библиотеки для решения задач определения положения объектов и анализа их взаиморасположения
Сеточные поверхности объектов описываются с помощью одного из классов иерархии, базовым среди которых является CSceneObject (рис. 9). Этот класс содержит следующие данные: указатели на объект-родитель и объекты-потомки в иерархии объектов; список вершин и примитивов, из которых состоит сеточная поверхность; указатель на ОВВ-дерево объекта; указатель на класс CDeformation для описания деформаций; список координат маркеров, привязанных к объекту; вспомогательные структуры данных.
Для описания поведения деформируемых объектов используется семейство классов, производных от CDeformation. В случае если объект является деформируемым, он содержит ненулевой указатель на один из производных от CDeformation классов, в зависимости от типа деформации. Заметим, что в отличие от наследования (с единой иерархией деформируемых и недеформируемых объектов), использование указателя является более гибким методом, поскольку позволяет присваивать объекту класс деформации динамически, во время исполнения программы.
Классы для описания ОВВ-деревьев Ограничивающий объем представлен с помощью класса CBoundBox. Класс содержит следующие данные: координаты центра объема; линейные размеры объема вдоль каждой из осей; матрицу поворота.
Каждый узел ОВВ-дерева представлен классом COBBNode. Класс содержит следующие данные: объект CBoundBox, описывающий непосредственно объем; указатели на узел-родитель и два узла-потомка; список указателей на примитивы. Список указателей на примитивы является непустым только в объемах-листьях. Классы для описания деформаций моделей объектов
Класс CDeformation является базовым в иерархии классов описания деформаций объектов. Класс CDeformActiveStates описывает деформации объектов с активными состояниями. Класс CDeformMovableNodes описывает деформации объектов с подвижными узлами сетки. Диаграмма основных классов, используемых для представления моделей объектов, приведена на рис. 9.
Приведенная иерархия позволяет инкапсулировать в соответствующих классах особенности применения алгоритмов анализа взаиморасположения для деформируемых объектов различных типов.
Библиотеки для решения задач определения положения объектов и анализа их взаиморасположения.
В библиотеке, предназначенной для решения задачи определения положения объектов, реализованы алгоритмы, предложенные в разделе 2.2, Библиотека экспортирует следующие основные методы: bool SetMarkerPosition ( [in, out] CSceneObject pObject [in] CMarker pMarker) Метод задает текущие координаты маркера (в мировой системе координат), закрепленного за указанным объектом. Данный метод вызывается подсистемой слежения за маркерами на каждой итерации работы системы, bool FindObjectPosition ([in, out] CSceneObject pObject)
Метод определяет текущее пространственное положение объекта по алгоритму, предложенному в разделе 2.2.1. Данный метод должен вызываться на каждой итерации перед проведением анализа взаимного расположения объектов.
Рассмотрим подробнее реализацию и использование функций библиотеки. Для описания маркеров используется класс CMarker Класс содержит следующие данные: идентификатор маркера (уникальный в пределах сцены); координаты маркера в системе координат объекта (известны априорно» постоянны на протяжении работы системы); текущие координаты маркера в мировой системе координат, полученные от подсистемы слежения за маркерами.
Каждый объект сцены CSceneObject содержит список маркеров, закрепленных за этим объектов. Этот список инициализируется в начале работы системы в момент загрузки модели объекта в оперативную память. Задача определения пространственного положения объектов решается следующим образом (рис. 10).
На каждой итерации подсистема слежения за маркерами обновляет их координаты при помощи вызова функции SetMarkerPositionQ для каждого маркера, координаты которого удалось определить.
Далее, для определения положения объектов сцены в пространстве, вызывается функция FindObjectPositionQ, алгоритм работы которой подробно представлен на рис. 10. Задача данной функции состоит в определении коэффициентов матрицы преобразования координат из локальной системы координат объекта в мировую систему координат. Для этого, согласно алгоритму, предложенному в разделе 2.2.1, последовательно решаются три системы линейных уравнений.
