автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.12, диссертация на тему:Алгоритмы моделирования поверхностей с применением методов ориентации твердого тела

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

ДЕГТЯРЕВ Михаил Юрьевич

АЛГОРИТМЫ МОДЕЛИРОВАНИЯ ПОВЕРХНОСТЕЙ С ПРИМЕНЕНИЕМ МЕТОДОВ ОРИЕНТАЦИИ ТВЕРДОГО ТЕЛА

Специальность 05.13.12 - Системы автоматизации проектирования (промышленность)

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Санкт-Петербург - 2006

Работа выполнена на кафедре «Прикладная геометрия и дизайн» ГОУ ВПО «Санкт-Петербургский государственный политехнический университет».

Научный руководитель: д.т.н., профессор Якунин Вячеслав Иванович.

Официальные оппоненты: д.т.н., профессор Сироткин Яков Аронович,

к.т.н., доцент Абросимов Сергей Николаевич.

I

Ведущая организация: ОАО «ОКБ Сокол», г. Казань.

Защита состоится «25» апреля 2006 г. в / б часов на заседании диссертационного совета Д 212.229.21 при ГОУ ВПО «Санкт-Петербургский государственный политехнический университет» по адресу: 195251, г. Санкт-Петербург, ул. Политехническая, 29, ГЗ, ауд. i^18■

С диссертацией можно ознакомиться в фундаментальной библиотеке ГОУ ВПО «Санкт-Петербургский государственный политехнический университет».

Автореферат разослан «23» марта 2006 г.

Ученый секретарь диссертационного совета, д.т.н., профессор

Редько С. Г.

/ссбА

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Существует также деление CAD/CAM/CAE-систем на системы верхнего, среднего и нижнего уровня. Наибольшее распространение получили два типа твердотельных геометрических ядер: Parasolid от фирмы Unigraphics Solutions и ACIS от Spatial Technology. CAD-системы нижнего уровня (например, AutoCAD, КОМПАС, БАЗИС) применяются в основном при автоматизации чертежных работ.

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

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

следования, ориентируя его на системное решение проблемы выбора и оптимизации базового уровня СГМ при разработке графического ядра.

Объектом исследования является базовый уровень СГМ (графический «движок»), основанный на геометрических методах и алгоритмах описания и движения твердого тела около неподвижной точки.

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

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

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

Задачи исследования:

1. Исследовать и оптимизировать геометрические методы и алгоритмы движения твердого тела около неподвижной точки при реализации на ЭВМ.

2. Разработать базовый уровень СГМ на основе рассматриваемых методов и алгоритмов.

3. Применить разработанное графическое ядро для моделирования поверхностей.

Научная новизна. Научная новизна теоретических и практических результатов настоящего исследования состоит в следующем:

1. Исследованы методы и алгоритмы описания движения твердого тела около неподвижной точки с использованием ЭВМ.

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

3. Разработана методика исследования и оценки эффективности алгоритмов. Для оценки и сравнения методов и алгоритмов использовалась координатная форма преобразований и абстрактная геометрическая машина.

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

поверхностей, в которой использованы рассматриваемые методы и алгоритмы.

Практическая ценность. В результате выполненного исследования:

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

2. Разработана методика исследования и оценки эффективности алгоритмов на основе использования координатной формы преобразований и абстрактной геометрической машины.

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

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

На защиту выносятся:

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

2. Способы оптимизации алгоритмов описания движения твердого тела при ортогональном проецировании. Способы повышения быстродействия обработки рассматриваемых алгоритмов.

3. Применение и реализация предложенных алгоритмов на языке программирования Си, текст которого может быть легко перенесен на большинство аппаратных платформ и программных сред.

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

Апробация работы. Основные результаты работы докладывались и обсуждались: на каф. «Прикладная геометрия и дизайн» Санкт-Петербургского Государственного Политехнического Университета; на каф. «Прикладная геометрия» Московского авиационного института; на каф. «Автоматика и управление» Казанского государственного технического университета им. А. Н. Туполева.

Публикации. По результатам выполненной работы опубликовано 3 научные работы, две из которых в изданиях, рекомендованных ВАК.

Структура работы. Диссертация состоит из введения, трех глав, заключения, списка литературы из 72 наименований и приложения, подтверждающего реализацию полученных результатов. Работа включает 114 страниц текста, 32 рисунка и 2 таблицы. Общий объем —128 страниц.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

1. АЛГЕБРА КВАТЕРНИОНОВ В ОСНОВЕ МОДЕЛИРОВАНИЯ ПОВЕРХНОСТЕЙ

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

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

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

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

Рассмотрим операцию умножения кватернионов и ее представление на сфере. Пусть даны единичные кватернионы Л и М. Оба эти кватерниона можно представить в виде дуг большого круга соответствующих длин. Дуга кватерниона arc Л располагается на большом круге, перпендикулярном к вектору А,; дуга arc М - на большом круге, определяемом вектором ц. Конец дуги arc Л и начало дуги arc М помещаются в точку А пересечения кругов (рис. 1.1).

Введя векторы а, Ь, с, кватернионы можно представить в следующем

виде:

А = Ь°а~1, М = а°с~1. Дуга большого круга, соединяющая точки Си В определяет некоторый кватернион N = Ь ° с Очевидно, что

т. е. произведению кватернионов соответствует операция геометрического сложения дуг на сфере: arc М + arc Л = arc (Л0 М).

Поскольку кватернион Л - скользящая дуга на сфере, то Л равняется также а ° / ' (углы FOA и АОВ равны и определяются углом 9); аналогично кватерниону М соответствует ¿»е-1; отсюда следует, что произведению М°Л=</°а_1°а° f~l = d° соответствует дуга FD, представляющая кватернион N' = М ° Л, т. е.

arc Л + arc M = arc (M ° Л).

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

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

Рис 1.2.

2. ТЕОРИЯ КОНЕЧНОГО ПОВОРОТА ТВЕРДОГО ТЕЛА

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

При решении любой динамической или кинематической задачи, где твердое тело не может быть представлено точкой, требуется рациональное описание кинематики вращательного движения. Существенную роль при этом играет выбор кинематических параметров, соответствующих трем вращательным степеням свободы движения твердого тела. Для описания движения твердого тела используются следующие кинематические параметры: направляющие косинусы, углы Эйлера и Крылова, параметры Кейли - Клейна, параметры Родрига - Гамильтона. Параметры Родрига - Гамильтона, представляющие собой компоненты кватерниона, имеют ряд преимуществ. В отличие от углов Эйлера, эти параметры не вырождаются при любом положении твердого тела, т. е. не обращаются в бесконечность ни сами параметры, ни скорости их изменения. Число параметров Родрига - Гамильтона равно четырем, т. е. имеется одно уравнение связи, в отличие от шести уравнений связи в случае направляющих косинусов. С другой стороны, эти параметры характеризуют наиболее естественный способ задания положения твердого тела с помощью плоского вращения.

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

Вектор конечного поворота определяет параметры Родрига - Гамильтона (так же, как и параметры Кейли - Клейна). Применение такого рода кинематических параметров естественным образом приводит к использованию

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

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

Рассмотрим представление ортогонального преобразования в форме умножения кватернионов. Пусть в пространстве Н задана операция вращения, определяемая единичным кватернионом, которая вектору г ставит в соответствие вектор /•':

г'=Л° г °Л.

Очевидно, что векторы г' и г определены своими компонентами в гиперкомплексном базисе Н, при этом операция вращения задает преобразование вектора в вектор, выполняемое относительно фиксированного базиса. Координатная форма преобразования:

г[ = (а.20 + X] -Х22-Х\) г, + 2{Х,Х2 + Х0Х3) Г2 + 2(Х1Х3 -Х0Х2) Г3,

гг = 2(Х,Х2 -Х0Х3) г, +{Х\+Х\-X] -Х23) г2 + 2{ХгХъ +Х0Х1) г3, ■ (2.1)

г3 = 2(А.|А.з -ьЯ-дА^) + 2^X2^-3 —^"(^о ——'з*

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

3. МОДЕЛИРОВАНИЕ ПОВЕРХНОСТЕЙ С ПРИМЕНЕНИЕМ МЕТОДОВ ОРИЕНТАЦИИ ТВЕРДОГО ТЕЛА

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

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

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

Рис. 3.1

Рис 3.2.

I. Моделирование с использованием углов Крылова.

Для аналитического описания движения поверхности удобно использовать координатную форму матрицы преобразования вращения:

хм = (cosфcos+ (cos 4/ sin <р)уо - (sin vy)zo, у„ = (sin9sin\|»cos9-cosSsinф)д:0 + (sin8sin\|/sinф+cosЭсохф)^ + (sinocos\|/)z0, (3.1) zM = (cos Э sin ц; cos ф + sin Ssin9)jc0 + (cos Э sin 4/ sin ф - sin Э cos ф)_у0 + (cos 9cos vy )z„.

При ортогональном проецировании на одну из координатных плоскостей достаточно выбрать любые две строки преобразования (3.1). Для проецирования на плоскость экрана в соответствии с рис. 3.2 это первые две строки:

хм = (аифсоэ у)х„ + (cos ч* sin q>)yo - (sin *|/)z„, ^

ym = (sin Ssin \|/ СОвф - COS 3sin ф)*0 + (sin Эsin »)/ sin ф + COS&С08ф)^о + (sin ScOSXyJZj, .J

Объединим преобразования сдвига, вращения и масштабирования для размещения моделируемого объекта на экране:

х = х, + far

У = Ус+*Ум>)

где хс и ус - координаты, задающие смещение на плоскости экрана; к - коэффициент масштабирования.

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

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

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

=(cos\|/)x„ - (sin vf)z0, ум = (sin 9sin \|/)xo + (cos 9)v„ + (sin Seosцi)z0, ■ (3.4) zM - (eos 9 sin y)x0 - (sin 9)j>0 + (eos 9 eos цi)za. Ортогональная экранная проекция xy в соответствии с рис. 3.2 описывается двумя верхними строками преобразования (3.4):

= (cosvy)x„ - (sin \|/)z„,

(3.5)

у м = (sin 9 sin у)х0 + (cos 9)j>„ + (sin 9 cos v|/)z0 .J Объединение с преобразованиями сдвига и масштабирования записывается в виде (3.3). Горизонтальная экранная координата х зависит только от одного угла. При этом скорость обработки вершин и вывода поверхности (объектов) при проецировании на координатные плоскости x¿yM и x¿zM выше, чем на координатную плоскость у*рм.

II. Моделирование с использованием кватернионов.

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

= к + "- АК + + ККк + " ККк,'

ум = 2(Х,Х2 -Х0Х3)х. + (Х.20 + Х\-X]-Х\К + 2{ХгХъ + ХЬХ,)zo, (3.6)

2М = 2{ХхХ, + Х0Х2К + 2(Х2Х3 -Я,0А,)уа + (X2<1+X\-X1t-X22)z0.

Для экранной проекции ху в соответствии с рис. 3.2 это первые две строки:

= {К+Ц- - ^ к+2(А.Л2+*-<Лэ к+2(^Лз - КК к .1

/"3 *7\

Ум = 2{Х1Х2-Х0Х})хо + (х,20 +Х22-Х]~Х))уо + 2(Х2Х,+Х0ХХ-1

Объединение сдвига, масштабирования и вращения записывается в виде преобразования (3.3).

Пример ориентации с использованием кватернионов:

Рис 3.3.

На рис. 3.3 использовано сложение дуг на сфере с использованием кватернионов ^ = М ° Л). Таким образом, объединяются два вращения вокруг координатных осей хм и ум.

Связь кинематических параметров и алгоритмов.

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

Рассмотрим последовательность трех поворотов на углы Крылова (рис. 3.4), совершаемых вокруг координатных осей преобразуемого базиса. Первый поворот выполняется вокруг оси /з на угол курса <р, второй поворот происходит по оси /У на угол крена у и третий - вокруг оси е\ на угол тангажа 9. Матрица преобразования А, задающая переход от системы координат / к системе Е, получается путем умножения трех матриц плоских вращений:

Рис. 3.4.

А =

COS (р COS V)/ cosy Sin ф -siny

sin 9 sin v|/cos ф - cos 9 sin ф sin 9 sin \|/ sin ф + cos 9 cos ф sin9cos*|/

cos 9 sin *j/cos ф +sin 9 sin ф cos 9 sin v|/sin ф-sin 9 cos ф cos 9 cos у

Выполняя умножение трех кватернионов, получаем следующие значения

компонент в функции углов Крылова:

. ф ш 9 . ю . у . 9 vn = cos—cos—cos— + sin—sin—sin—, 0 2 2 2 2 2 2

« ф w . & . <p . w 9 v. = cos—cos—sin—sin—sin—cos—, 1 2 2 2 2 2 2 » . w ф 9 . ф vi/ . 9 v, =sin—cos—cos— + sm—cos—sin—, 2 2 2 2 2 2 2 9 . V ф . 9

,q> v.

v, =sin—cos—cos—sm—cos—sin—.

3 2 2 2 2 2 2

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

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

Сравнительный анализ алгоритмов.

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

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

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

Таблица 3.1.

Алгоритм Умножения Сложения

С тремя степенями свободы (3.2) 15 6

С двумя степенями свободы (3.5) 7 3

С использованием кватернионов (3.7) 26 14

Из таблицы 3.1 можно сделать вывод, что самым быстрым является алгоритм с двумя степенями свободы, а самым медленным - алгоритм с использованием кватернионов. Он примерно в 4 раза медленнее алгоритма (3.5) и примерно в 2 раза медленнее алгоритма (3.2). Такой результат не является неожиданным, поскольку алгоритм (3.7) является общей формой преобразования, а алгоритм (3.2) - частный упрощенный случай.

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

Основным недостатком алгоритма 3.2 является вырождение параметров при значении углов ж / 2, что затрудняет его использование для плавного перемещения вокруг объекта. Быстродействие алгоритма среднее. К его преимуществам можно отнести его широкую распространенность и простоту пространственного описания.

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

Алгоритм (3.7) позволяет моделировать и управлять ориентацией объекта в обобщенном виде и может быть использован практически для любых задач управления и ориентации твердого тела. К его недостаткам можно отнести низкое быстродействие. Но и этот его недостаток не является критическим, т. к. в реальных условиях время выполнения алгоритмов занимает лишь малую часть от общего времени преобразований и обработки. Это свя-

зано с тем, что мы производили сравнение с использованием АМ, которая пригодна только для оценки самих алгоритмов.

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

Пример моделирования поверхности (рис. 3.5).

Рис 3.5.

ЗАКЛЮЧЕНИЕ

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

1. Рассмотрена связь геометрии на сфере и на плоскости. Установлена связь алгебры кватернионов с геометрическими преобразованиями в пространстве. Предложено рациональное описание кинематики вращательного движения. Проведен анализ преобразований объектов с использованием матричного аппарата и аппарата кватернионов. Выявлены их возможности и ограничения при реализации на ЭВМ.

2. Рассмотрены ортогональные преобразования, являющиеся в соответствии с теоремой Эйлера конечными поворотами. Установлено изоморфное

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

3. Проведен сравнительный анализ алгоритмов описания и движения твердого тела. Оценка быстродействия алгоритмов на основе АМ в совокупности с рассмотренными преимуществами и недостатками методов и алгоритмов ориентации определила область применения преобразований. Предложена оптимизация алгоритмов преобразований при ортогональном проецировании. Приведенное исследование связи параметров Родрига - Гамильтона с другими кинематическими параметрами раскрывает универсальность преобразований с использованием кватернионов.

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

ОСНОВНЫЕ ПУБЛИКАЦИИ

1. Дегтярев, М. Ю. Моделирование поверхностей с использованием тесселяции [Электронный ресурс] / М. Ю. Дегтярев // Электронный журнал «Прикладная геометрия». - 2005. - № 17.

- Режим доступа: http://www.mai.ru/~apg/volume7/v7_nl7.htm.

2. Дегтярев, М. Ю. Моделирование поверхностей с использованием геометрических методов и алгоритмов описания движения твердого тела с неподвижной точкой [Текст] / М. Ю. Дегтярев // Вестник КГТУ им. А. Н. Туполева. - 2005. - № 4. С. 30-32.

3. Дегтярев, М. Ю. Быстродействие и возможности геометрических методов и алгоритмов описания движения твердого тела с неподвижной точкой при моделировании ортогональных проекций [Текст] / М. Ю. Дегтярев, В. Ф. Снигирев, В. И. Якунин // Вестник КГТУ им. А. Н. Туполева. - 2005. - № 4. С. 33-35.

Лицензия ЛР №020593 от 07.08.97

Подписано в печать 20.03.2006. Формат 60x84/16. Печать цифровая. Усл. печ. л .1,0. Тираж 100. Заказ 393Ь.

Отпечатано с готового оригинал-макета, предоставленного автором, в Цифровом типографском центре Издательства Политехнического университета. 195251, Санкт-Петербург, Политехническая ул., 29. Тел.: 550-40-14 Тел./факс: 297-57-76

- 5983

ВВЕДЕНИЕ

1. АЛГЕБРА КВАТЕРНИОНОВ В ОСНОВЕ МОДЕЛИРОВАНИЯ ПОВЕРХНОСТЕЙ

Введение

1.1. Алгебра кватернионов

1.2. Представление кватерниона на сфере

1.3. Преобразование вращения

1.4. Геометрия на сфере 40 Выводы к главе

2. ТЕОРИЯ КОНЕЧНОГО ПОВОРОТА ТВЕРДОГО ТЕЛА

Введение

2.1. Ортогональные преобразования

2.2. Представление ортогонального преобразования в форме умножения кватернионов

2.3. Преобразование базисов

2.4. Преобразование компонент неизменного вектора. Гиперкомплексное отображение

2.5. Инвариантность операций вращения.

Параметры Родрига - Гамильтона

2.6. Сложение поворотов 77 Выводы к главе

3. МОДЕЛИРОВАНИЕ ПОВЕРХНОСТЕЙ С ПРИМЕНЕНИЕМ МЕТОДОВ ОРИЕНТАЦИИ ТВЕРДОГО ТЕЛА

Введение

3.1. Выбор системы координат и поверхности проецирования

3.2. Тесселяция поверхностей

3.3. Алгоритмы в основе моделирования поверхностей

3.4. Связь кинематических параметров и алгоритмов ориентации твердого тела

3.5. Сравнительный анализ алгоритмов

Выводы к главе

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

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

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

С введением французским философом, математиком, физиком Рене Декартом (1596-1650) метода прямолинейных координат и дальнейшей его систематизацией французским математиком Пьером Ферма (1601-1665) устанавливается связь геометрии и алгебры, которая послужила основой для развития аналитической геометрии. Одной из наиболее успешных геометри-щ ческих интерпретаций алгебры является использование комплексных чисел для описания геометрии на плоскости. Теория функций комплексного переменного французского математика Опостена Коши (1789-1857) позволяет наиболее адекватно отразить связь функций на комплексной плоскости и в реальных физических процессах.

Стремясь найти для изучения геометрии пространства столь же удобный аппарат как комплексные числа при решении задач на плоскости, английский математик и механик Вильям Роуан Гамильтон (1805-1865) вводит в математику теорию кватернионов, которая послужила одним из источников развития векторного анализа. До середины прошлого века кватернионы не нашли какого-либо практического применения и служили примером формальной математической модели четырехмерной линейной алгебры.

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

В. И. Елисеев в своих исследованиях [24] описывает естественную геометрию, построенную на базе алгебры с классическими операциями чисел, определяющей структуру пространства, которая в свою очередь должна соответствовать структуре периодической таблицы элементов Д. И. Менделеева и являться основой теории гравитации.

Основные результаты классической теории углового движения твердого тела были получены в XIX веке. Для описания движения твердого тела около неподвижной точки был предложен ряд кинематических параметров, таких, как параметры Родрига - Гамильтона, параметры Кейли - Клейна, углы Эйлера - Крылова и направляющие косинусы. Усилия исследователей в то время были направлены на поиски удобной формы представления уравнений и к отысканию интегрируемых случаев движения. После этого центр тяжести исследований переместился в область прикладной теории гироскопов. При этом движение твердого тела задавалось исключительно углами Эйлера - Крылова, которые нашли широкое применение во всех работах по механике, в том числе и в работах по исследованию управления движущимися объектами. Кроме того, в теоретических работах применялся также матричный аппарат; при этом положение тела задавалось направляющими косинусами. Другие способы описания углового движения упоминались главным образом для полноты изложения.

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

Среди всех кинематических параметров особое место занимают пара® метры Родрига - Гамильтона и Кейли - Клейна. Эти параметры не вырождаются при любом положении твердого тела, в отличие от углов Эйлера. Число этих параметров равно четырем, поэтому они имеют одно уравнение связи, в отличие от шести для направляющих косинусов. Все это упрощает задачу численного интегрирования кинематических уравнений. Кроме того, параметры Родрига - Гамильтона (и Кейли - Клейна) дают возможность эффективно решать многие вопросы теории конечного поворота твердого тела, устойчивости управляемого движения и т. п. Несмотря на такого рода преиму-Ф щества, использование этих параметров осложняется тем, что оно приводит к ф применению векторной теории конечного поворота или же к стереографическому проецированию и унитарным преобразованиям, не имеющим простого геометрического смысла. Использование параметров Родрига - Гамильтона позволяет эффективно решать задачи ориентации твердого тела.

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

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

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

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

Существует также деление CAD/CAM/CAE-систем на системы верхнего, среднего и нижнего уровня. В настоящее время возможности систем среднего уровня приближаются к возможностям систем верхнего уровня, а системы нижнего уровня становятся трехмерными.

Примерами CAD/CAM-систем верхнего уровня являются Pro Engineer, Unigraphics, CATIA, EUCLID, I-DEAS. Наибольшее распространение получили два типа твердотельных геометрических ядер: Parasolid от фирмы Unigraphics Solutions и ACIS от Spatial Technology. Наиболее известными CAD/CAM-системами среднего уровня на основе ядра ACIS являются: ADEM, Cimatron, Mastercam. CAD/CAM-системы среднего уровня на основе ядра Parasolid: MicroStation Modeler, CADKEY, Pro Desktop, SolidWorks, Unigraphics Modeling. CAD-системы нижнего уровня (например, AutoCAD LT, Medusa, TrueCAD, КОМПАС, БАЗИС) применяются в основном при автоматизации чертежных работ.

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

Таким образом, для создания современных эффективных систем геометрического моделирования необходимо развивать имеющиеся теоретические и практические достижения. Указанные обстоятельства подтверждают актуальность темы исследования, ориентируя его на системное решение проблемы выбора и оптимизации базового уровня СГМ при разработке графиче ского ядра.

Объектом исследования является базовый уровень СГМ (графиче ский «движок»), основанный на геометрических методах и алгоритмах описания движения твердого тела около неподвижной точки.

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

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

Ф стве основы для проектирования и моделирования поверхностей.

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

Задачи исследования:

1. Исследовать и оптимизировать геометрические методы и алгоритмы движения твердого тела около неподвижной точки при реализации на ЭВМ.

2. Разработать базовый уровень СГМ на основе рассматриваемых методов и алгоритмов.

3. Применить разработанное графическое ядро для моделирования поверхностей.

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

Ь Теоретической основой настоящего исследования являются работы из

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

Научная новизна. Научная новизна теоретических и прикладных результатов настоящего исследования состоит в следующем:

1. Исследованы методы и алгоритмы описания движения твердого тела около неподвижной точки с использованием ЭВМ.

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

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

4. Разработана методика исследования и оценки эффективности алгоритмов. Для оценки и сравнения методов и алгоритмов использовалась координатная форма преобразований и абстрактная геометрическая машина.

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

6. Предлагается расширить область применения методов и алгоритмов для моделирования физических процессов с использованием ЭВМ.

Практическая ценность. В результате выполненного исследования:

1. Создана основа для разработки новых геометрических методов и ал* горитмов, которые позволят эффективно решать задачи компьютерной графики и моделирования физических процессов с использованием ЭВМ.

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

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

4. Разработана методика исследования и оценки эффективности алгоритмов на основе координатной формы преобразований и абстрактной геометрической машины. ф 5. Разработана программа моделирования поверхностей, в которой щ применены оптимизированные методы ориентации твердого тела.

На защиту выносятся:

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

2. Способы оптимизации алгоритмов описания движения твердого тела при ортогональном проецировании. Способы повышения быстродействия обработки рассматриваемых алгоритмов.

3. Применение и реализация предложенных алгоритмов на языке программирования Си, текст которого может быть легко перенесен на большинство аппаратных платформ и программных сред.

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

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

• версий. Разработанные программы внедрены и используются в учебном процессе с 1999 учебного года и на одном из промышленных предприятий с 2005 г. Разработка и внедрение велись в годы обучения диссертанта в Казанском государственном техническом университете (им. А. Н. Туполева), Московском авиационном институте и в Санкт-Петербургском государственном политехническом университете.

Апробация работы. Основные результаты работы докладывались и обсуждались: на кафедре «Прикладная геометрия и дизайн» Санкт-Петербургского государственного политехнического университета; на кафедре «Прикладная геометрия» Московского авиационного института; на кафедре «Автоматика и управление» Казанского государственного технического университета им. А. Н. Туполева.

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

Структура работы. Диссертация состоит из введения, трех глав, заключения, списка литературы из 72 наименований и приложений, подтверждающих реализацию полученных результатов. Работа включает 114 страниц текста, 32 рисунка и 2 таблицы. Общий объем - 128 страниц.

Выводы к главе 3

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

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

Разработана программа для наглядного представления рельефа местности, которая позволяет производить сдвиг, масштабирование и вращение квадрата местности с заданными высотами. Реализован экспорт карт с наложением текстур в формат DirectX.

Установлена связь кинематических параметров и алгоритмов, которая позволяет одновременно использовать различные методы ориентации твердого тела.

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

ЗАКЛЮЧЕНИЕ

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

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

2. Рассмотрены ортогональные преобразования, являющиеся в соответствии с теоремой Эйлера конечными поворотами. Установлено изоморфное соответствие операции ортогонального преобразования и операции умножения кватернионов. Все известные результаты теории конечного поворота получены в виде операций умножения кватернионов. Приведенное исследование связи параметров Родрига - Гамильтона с другими кинематическими параметрами раскрывает универсальность преобразований с использованием кватернионов.

3. Проведен сравнительный анализ алгоритмов описания и движения твердого тела. Оценка быстродействия алгоритмов, произведенная с использованием AM, в совокупности с рассмотренными преимуществами и недостатками методов и алгоритмов определила область применения преобразований. Универсальность алгоритмов расширяет область их использования. Рассмотрен наиболее общий случай преобразований с использованием кватернионов, который может быть использован для широкого круга' задач ориентации и управления твердого тела. Предложена оптимизация алгоритмов преобразований при ортогональном проецировании.

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

1. Алгоритмы и программы решения геометрических задач на ЭВМ Текст.: Учеб. пособие: Для слушателей ФПК / [В. И. Якунин, С. И. Бородкина, К. М. Наджаров и др.]; Под ред. В. И. Якунина. М.: МАИ, 1982. - 70 с.

2. Алберг, Дж. Теория сплайнов и ее приложения Текст. / Дж. Алберг, Э. Нильсон, Дж. Уолш. -М.: Мир, 1972. 316 с.

3. Аминов, Ю. А. Дифференциальная геометрия и топология кривых Текст. /Ю. А. Аминов. -М.: Наука, 1987. 159 с.

4. Арбузов, В. А. Компьютерная графика Текст.: Учеб. пособие / В. А. Арбузов; М-во общ. и проф. образования Рос. Федерации, Пенз. гос. ун-т. — Пенза: Изд-во Пенз. гос. ун-та, 1999. 92 с.

5. Баранов, Г. Г. Курс теории механизмов и машин Текст. / Г. Г. Баранов. -М.: Машгиз, 1959. 488 с.

6. Болтянский, В. Г. Математические методы оптимального управления Текст. / В. Г. Болтянский. М.: Наука, 1966. - 320 с.

7. Боресков, А. В. Компьютерная графика: первое знакомство Текст. / А. В. Боресков, Е. В. Шикин, Г. Е. Шикина; Под ред. Е. В. Шикина. М.: Финансы и статистика, 1996. - 173, [2] с.

8. Бранец, В. Н. Применение кватернионов в задачах ориентации твердого тела Текст. / В. Н. Бранец, И. П. Шмыглевский. М: Наука, Гл. ред. физ.-мат. лит., 1973. - 320 с.

9. Ю.Бронштейн, И. Н. Справочник по математике для инженеров и учащихся втузов Текст. / И. Н. Бронштейн, К. А. Семендяев. М.: Наука, Гл. ред. физ.-мат. лит., 1986. - 544 с.

10. Бугровиц, А. Г. Вращение твердого тела относительно неподвижной точки. Сферическое движение твердого тела Текст.: учеб. пос. / А. Г. Бугро-виц, Г. М. Волова. Рига: Изд-во РВКИКУ, 1968.

11. Бутенин, Н. В. Вращение твердого тела вокруг неподвижной оси Текст.: лекции / Н. В. Бутенин. Д.: Изд-во ЛИАП, 1964.

12. Воробьев, Е. И. Пространственные шарнирные механизмы. Замкнутые и открытые кинематические цепи Текст. / Е. И. Воробьев, Ф. М. Димент-берг. М.: Наука. Гл. ред. физ.-мат. лит., 1991. - 264 с.

13. Н.Ганкель, Г. Теория комплексных числовых систем, преимущественно обыкновенных мнимых чисел и кватернионов Гамильтона вместе с их геометрическим толкованием Текст.: пер. с нем. / Г. Ганкель. Казань: Изд-во Казанского университета, 1912.

14. Гардан, И. Машинная графика и автоматизация конструирования Текст. / И. Гардан, М. Люка. М.: Мир, 1987. - 272 с.

15. Гилой, В. Интерактивная машинная графика: структуры данных, алгоритмы, языки Текст. / В. Гилой. М.: Мир, 1981. - 380 с.

16. Голдстейн, Г. Классическая механика Текст.: пер. с англ. / Г. Голдстейн -М.: Наука, Гл. ред. физ.-мат. лит., 1975. 415 с.

17. Грувер, М. САПР и автоматизация производства Текст. / М. Грувер, Э. Зиммерс. М.: Мир, 1987. - 528 с.

18. Давыдов, Ю. В. Геометрия крыла: методы и алгоритмы проектирования несущих поверхностей Текст. / Ю. В. Давыдов, В. А. Злыгарев. М.: Машиностроение, 1987.- 131 с.

19. Диментберг, Ф. М. Винтовое исчисление и его приложения в механике Текст. / Ф. М. Диментберг. М.: Наука, 1965.

20. Дуда, Р. Распознавание образов и анализ сцен Текст. / Р. Дуда, П. Харт. -М.: Мир, 1976.-511 с.

21. Дьяконов, В. П. Вейвлеты. От теории к практике Текст. / В. П. Дьяконов. М.: СОЛОН-Р, 2002. - 440 с.

22. Егоров, Э. В. Моделирование поверхностей агрегатов ЛА Текст.: учеб. пос. под ред. Э. В. Егорова / Э. В. Егоров, А. Д. Тузов. М.: Изд-во. МАИ, 1988.- 53 с.

23. Елисеев, В. И. Введение в методы теории функций пространственного комплексного переменного Текст. : Сб. ст. / Центр науч.-техн. творчества молодежи "Алгоритм". [М.]: НИАТ, 1990. - 189, 1. с.

24. Иванов, В. П. Трехмерная компьютерная графика Текст. / [Г. М. Поли-щук, В. П. Иванов, А. С. Батраков]; Под ред. Г. М. Полищука. М.: Радио и связь, 1995.-223 с.

25. Иванов, Г. С. Конструирование технических поверхностей (математическое моделирование на основе нелинейных поверхностей) Текст. / Г. С. Иванов. -М.: Машиностроение, 1987. 192 с.

26. Иванов, Г. С. Начертательная геометрия Текст.: [Учеб. для втузов]. -М.: Машиностроение, 1995.-223 с.

27. Клейн, Ф. Элементарная математика с точки зрения высшей Текст.: Т. 2: пер. с нем. / Ф. Клейн М.: Наука, Гл. ред. физ.-мат. лит., 1987. - 416 с.

28. Колмогоров, А. Н. Элементы теории функций и функционального анализа Текст. / А. Н. Колмогоров, С. В. Фомин. М.: Наука, 1974. - 120 с.

29. Компьютерная графика и численные методы: Basic. ZX Spectrum Текст. / [А. В. Гайван]. М.: Фирма «ВА принт», 1994. - 114 с.

30. Корн, Г. Справочник по математике для научных работников и инженеров Текст.: пер. с англ. / Г. Корн, Т. Корн. М.: Наука, Гл. ред. физ.-мат. лит., 1984.-832 с.

31. Котов, И. И. Алгоритмы машинной графики Текст. / И. И. Котов, В. С. Полозов, JI. В. Широкова. -М.: Машиностроение, 1977.

32. Лаггали, М. Векторное исчисление Текст.: пер. с нем. / М. Лаггали М.: ОНТИ, 1936.

33. Ламот, А. Программирование трехмерных игр для Windows: советы профессионала по трехмерной графике и растеризации Текст. / А. Ламонт; пер. с англ. Р. Г. Имамутдиновой и др. -М: Вильяме, 2004. 1414 с.

34. Летин, А. С. Компьютерная графика в ландшафтном проектировании Текст.: [Учеб. пособие] / А. С. Летин, О. С. Летина; М-во образования Рос. Федерации, Моск. гос. ун-т леса. М.: Изд-во МГУЛ, 2003. - 212 с.

35. Лурье, А. И. Аналитическая механика Текст. / А. И. Лурье. М.: Физ-матгиз, 1961. - 824 с.

36. Ньюмен, У. Основы интерактивной машинной графики Текст. / У. Ньюмен, Р. Спрулл. М.: Мир, 1976. - 576 с.

37. Персональный компьютер «ZX-Spectrum». Прикладная графика Текст. -М.: ИНФОРКОМ, 1993.

38. Поляков, А. Ю. Методы и алгоритмы компьютерной графики в примерах на Visual С++ Текст. / А. Ю. Поляков. СПб.: БХВ-Петербург, 2002. -400 с.

39. Порев, В. Н. Компьютерная графика Текст. / В. Н. Порев. СПб.: БХВ-Петербург, 2002.-428 с.

40. Пунтус, А. А. Конечномерные линейные пространства Текст.: Учеб. пособие / Моск. гос. авиац. ин-т (техн. ун-т). М.: Изд-во МАИ, 1994. - 71, 1.с.

41. Синг, Дж. Л. Классическая динамика Текст.: пер. с англ. / Дж. Л. Синг -М.: Физматгиз, 1963. 448 с.

42. Соколов, А. П. Сферическое движение твердого тела и элементы теории гироскопа Текст.: учеб. пос. / А. П. Соколов. М.: Изд-во МЭИ, 1961.

43. Стародетко, Е. А. Математическое моделирование лекальных поверхностей Текст. / Е. А. Стародетко. Минск: Наука и техника, 1984. - 126 с.

44. Стародетко, Е. А. Элементы вычислительной геометрии Текст. / Е. А. Стародетко. Минск: Наука и техника, 1986. - 240 с.

45. Стечкин, С. Б. Сплайны в вычислительной математике Текст. / С. Б. Стечкин, Ю. Н. Субботин. М.: Наука, 1976. - 248 с.

46. Столниц, Э. Вейвлеты в компьютерной графике Текст.: пер. с англ. / Э. Столниц, Т. ДеРоуз, Д. Салезин. Ижевск: НИЦ «Регулярная и хаотическая динамика», 2002. - 271 с.

47. Уоррен, Г. С. Алгоритмические трюки для программистов Текст.: пер. с англ. / Генри С. Уоррен М.: Издательский дом «Вильяме», 2003. - 284 с.

48. Фокс, А. Вычислительная геометрия. Применение в проектировании и на производстве Текст. / А. Фокс, М. Пратт. М.: Мир, 1982. - 304 с.

49. Фролов, А. Б. Модели и методы технической диагностики Текст. / А. Б. Фролов. М.: Знание, 1990. - 47 с.

50. Христов, В. К. Координаты Гаусса-Крюгера на эллипсоиде вращения Текст.: пер. с болгарского / В. К. Христов. М.: Изд-во геодезической литературы, 1957. - 264 с.

51. Четверухин, Н. Ф. Проективная геометрия Текст. / Н. Ф. Четверухин. -М.: «Просвещение», 1969. 360 с.

52. Щеглова, Р. А. Краткий курс начертательной геометрии и компьютерной графики Текст.: Учеб. пособие / Р. А. Щеглова, В. А. Семено; Уфим. гос. нефтяной техн. ун-т. Уфа: Изд-во Уфим. гос. нефтяного техн. ун-та, 2000.- 163 с.

53. Шикин, Е. В. Компьютерная графика: Динамика, реалист. Изображения Текст. / Е. В. Шикин, А. В. Боресков -М.: Диалог-МИФИ, 1995. 286 с.

54. Шпур, Г. Автоматизированное проектирование в машиностроении Текст. / Г. Шпур, Ф. Краузе. М.: Машиностроение, 1988. - 648 с.

55. Якунин, В. И. Геометрические основы систем автоматизированного проектирования технических поверхностей Текст. / В. И. Якунин. М.: Изд-воМАИ, 1980.-85 с.

56. Brand L., Vector and Tensor Analysis. New York, J. Wiley, London, Chapman and Hall, 1948.

57. Davies B. L., Yarwood A., Engineer drawing and computer graphics. Van Nostrand Reinhold (UK) Co. Ltd, 1986.63 .DirectX Graphics Documentation for С++. Microsoft Corporation, 2004.

58. Farin G. Some remarks on V -splines. Computer Aided Geometric Design, 1985.

59. Farin G., Piper В., Worsey A. J. The octant of a sphere as a non-degenerate triangular Bezier patch. Computer Aided Geometric Design, 1987.

60. Hamilton W. R., Elements of Quaternions. Chelsea Publishing Company, New York, 1969.

61. Hamilton W. R., Lectures on Quaternions. Dublin, Hodges and Smith, 1853.

62. Microsoft Developer Network Library. Microsoft Corporation, 2003.

63. MacTech Magazine, http://www.mactech.com, 2000.

64. MathWorld, http://mathworld.wolfram.com, 2005.

65. Mitchell E. L., Rogers A. E. Quaternion Parameters in the Simulation of a Spinning Rigid-body. «Simulation», New York, 1968.

66. Pratt M. J. Cyclides in computer aided geometric design. Computer Aided Geometric Design, 1990.