Содержание к диссертации
Введение
ГЛАВА 1. Современные способы организации геометрических преобразований для компьютерных представлений пространства геометрической модели 8
1.1. Существующие способы геометрических преобразований полигональных моделей 9
1.2. Существующие способы геометрических преобразований растровых моделей
1.2.1. Смещение растрового изображения 11
1.2.2. Поворот растрового изображения 12
1.2.3. Масштабирование растрового изображения
1.3. Геометрическое преобразование воксельных-кубических моделей 22
1.4. Выводы по первой главе 24
ГЛАВА 2. Основы построения функционально-воксельного пространства 26
2.1. Повышенное пространство как способ воксельной организации представления функции 26
2.1.1. Графическое представление рельефа поверхности функции 26
2.1.2. Образное представление локальных геометрических характеристик поверхности функции двух переменных 28
2.1.3. Организация воксельной геометрической модели 31
2.2. Тройственность вычислительного подхода в процедурах функционально воксельного моделирования 35
2.2.1. Согласованность функциональных и функционально-воксельных моделей. Операторы перехода 35
2.2.2. Тройственность вычислительного подхода к выполнению арифметических операций с применением ВГМ 36
2.2.3. Тройственность вычислительного подхода к процедуре преобразования пространства ВГМ 43
2.3. Выводы по второй главе 44
ГЛАВА 3. Принципы геометрических преобразований пространства в функционально-воксельном моделировании 46
3.1. Геометрические принципы организации пространственного смещения воксельных геометрических моделей 49
3.2. Геометрические принципы организации пространственного поворота воксельных геометрических моделей 61
3.3. Геометрические принципы организации масштабирования пространства воксельных геометрических моделей 72
3.4. Выводы по третьей главе 81
ГЛАВА 4. Теоретико-множественные операции в функционально-воксельном моделировании 82
4.1. Геометрические принципы R-функционального моделирования 82
4.2. Тройственность вычислительного подхода к множественным операциям над пространствами ВГМ 86
4.3. Принципы пространственной компоновки сложных аналитических объектов на основе предложенных геометрических преобразований 90
4.4. Анализ времени работы алгоритмов преобразований пространства в ФВМ 95
4.5. Экспериментальное применение разработанных алгоритмов 98
4.6. Выводы по четвертой главе 99
Заключение 101
Список литературы 102
- Поворот растрового изображения
- Образное представление локальных геометрических характеристик поверхности функции двух переменных
- Геометрические принципы организации пространственного поворота воксельных геометрических моделей
- Тройственность вычислительного подхода к множественным операциям над пространствами ВГМ
Поворот растрового изображения
В работе пойдет речь о преобразовании растровых представлений, поэтому способам пространственных преобразований последних [15] будет уделено особое внимание. Растровая модель - цифровое представление пространственных объектов в виде совокупности ячеек растра с присвоенными им значениями класса объекта. Растровая модель предполагает позиционирование объектов путём указания их положения в соответствующей растру матрице единообразно для всех типов пространственных объектов [16].
Растровая модель разбивает всю заполняемую область на элементы регулярной сетки или ячейки, при этом каждая ячейка может содержать только одно значение. Поскольку каждое местоположение в пространстве растровой модели соответствует ячейке растра [17], растровая модель является пространственно заполненной.
Основным отличием существующих алгоритмов для растровых геометрических преобразований является тот факт, что в процессе их выполнения участвует абстрактный графический объект (изображение). Геометрическим инвариантом преобразования здесь может выступать расстояние между парой точек растра, который невозможно увязать с локальными геометрическими характеристиками геометрической модели.
При смещении растровой модели необходимо использовать формулы преобразования координат как при параллельном переносе (1.1.1) [18]. Так Ах и Ау, отражающие приращение вдоль осей OX и OY, равное величине смещения в двухмерном пространстве, при смещении в пространстве растровой модели будут соответствовать величине целочисленного смещения в индексном массиве, содержащем растровую модель.
Поворот растрового изображения можно выполнить несколькими известными способами [6,8,28,30]. Рассмотрим отдельно каждый из них. Поворот растровых изображений с помощью матричных преобразований [6, 8]. Поворот выполняется с помощью матрицы поворота: (cosd + sin 0 М(0) = +sin0 COS в J При таком способе проявляется искажение изображения - муар [19], характеризуемое неравномерным смещением точек растра (рис. 3). При выполнении ряда последовательных поворотов погрешность будет накапливаться, что неизбежно приведет к нарушению структуры представления графической информации [20], [21].
Возникновение муара при матричном повороте растрового изображения Для улучшения качества выводимого изображения и уменьшения подобного рода геометрических искажений используют аппроксимирующие значения яркости точек, определяемые с учетом разницы линейного шага в ортогонально расположенном к координатной оси линейном объекте и объекте, расположенном под непрямым углом [22]. Подобные алгоритмы округления используются в основном при печати изображений и не подходят для работы с геометрическими моделями.
Способ поворота растровых изображений с помощью композиций последовательных сдвигов строк и столбцов индексного массива значений.
Вариант исключения муара из изображения возможен при использовании алгоритма рассмотренного в работе [23]. Общий поворот Т цифровых изображений представлен в виде композиций последовательных сдвигов строк и столбцов (Рис. 4). Пусть Т = Я-С, где С - F/S преобразование, сохраняющее столбцы, R - преобразование, сохраняющее строки. Необходимо найти Рис. 4. Разложение поворота массива значении в композицию линейных смещений значения координат после поворота Т:(х,у) (х",/ ). При этом в процессе выполнения поворота получается промежуточный результат (х\У)(С: ( , ) - ( ,/), Д: ( ,/) - ( ",/ )) . Выражая преобразования для каждого этапа и исходя из заданных условий: (Ф,у)\ iv ,у \с X \с2{х,у) Т ГЛ(х\У)) JV \?2 У получаем, что т (h(x,yy\Jrx(x,c2(x,y)f\ с2(х,У) Таким образом, с2(х,у) = ф,у) и ф,і2(х,у)) = ф,у). Для того, чтобы найти гх, в выражении tx необходимо выделить все подвыражения, содержащие у, и привести их к виду t2 (х, у). После этого, произведя замену этих подвыражений на у, получить выражение для гх. Рассмотрим данную процедуру на примере поворота на произвольный угол : fcos -sinQYj sin COSXJ T(x,y) ф,у) = со5&-х-5т&-у,с2(х,у) = (х,у) = 5т&-х + со5&-у, v= (0 +90), cos v ti(x,y) = cos-x-sm-\t2(X,y Sm@ X ) = sQC-xm2(x,y). { cos J Отсюда следует, что rl(x,y) = sec-xm-y. Таким образом получается следующее выражение: т R С (cos0 -sin 0 (sec0 an 0 sin0 COS0 0 1 0 sin0 COS0 В случае @ = ±90 разложение по вышеописанному алгоритму не представляется возможным. В этом случае всё преобразование Т сведётся к замене х на у и возможному отражению (когда 0 = -90). Также стоит отметить, что при вращении на углы 0, близкие к ±90, произойдут слишком большие искажения по вертикали. В этом случае необходимо сначала произвести поворот на угол ± 90, а затем уже на угол -(±90) (знак соответствует близкому к 0 углу).
Образное представление локальных геометрических характеристик поверхности функции двух переменных
Графическое представление рельефа поверхности функции выражается в алгоритмах построения максимально наглядного отображения данных поверхности [46]. При этом получаемая геометрическая модель может содержать определенный функционал, обеспечивающий ее использование при различного рода преобразованиях [47], направленных на улучшение качества восприятия [48]. Метод функционально-воксельного моделирования основан на построении цветовой градации в соответствии со значениями коэффициентов нормального уравнения, полученного линейной аппроксимацией функции на определённой области. Получаемая в результате воксельная геометрическая модель (ВГМ) содержит графическую информацию о локальных геометрических характеристиках (ЛГХ) для каждой точки на области определения функции в виде набора образов-моделей (М-образы).
Построение воксельной геометрической модели (ВГМ) приводит к представлению локальной геометрии для компьютерных расчётов, что позволяет получать интегральные и дифференциальные характеристики аналитического объекта для решения прикладных задач в аналитических САПР [49]. В итоге ВГМ позволяет выполнять над собой различные математические операции по аналогии с аналитическими функциями, применяя локальные геометрические характеристики, организованные воксельным скалярным полем. М-образ - специальный графический образ поверхности функции, отображающий дифференциальную характеристику Специфика графического представления функции локальными характеристиками изложена в работе [50]. Рассмотрим её на примере определения выпуклости графика f(x) = e xll0-sm(5x).
При нахождении выпуклых промежутков функции, нет необходимости определения их фактического значения. Интересует только область определения, где график является отрицательно или положительно выпуклым.
Участок функции Дx), где вторая производная fн(x) 0 является положительно выпуклым, а при f"(x) 0 - отрицательно выпуклым участком функции f(x). Геометрический смысл - определение изменения направления вектора нормали осn в окрестности точки Mi. Интерес в данном случае представляет не значение угла, а направление изменения: максимум при f (a) = 0 и f"(a) о; минимум при f (a) = 0 и f"(a) 0. Функция f(x) = ex/l0-sin(5x) с указанием зон выпуклостей, выраженных в виде графической информации, представлена на рисунке 18.
Отображение локальных геометрических характеристик, для нахождения выпуклых участков функции характеристикой, необходимой для определения зон выпуклости. Подобного рода характеристики можно отнести к локальным геометрическим. В трудах Л.Д. Кудрявцева отражены основные критерии функционального анализа [51]. Предлагаемый способ разложения функции одной переменной на одномерные визуальные М-образы можно применить для исследования поверхности функции двух переменных f(x,y) по принципу разбиения пространственного образа на плоские визуальные М-образы, отображающие визуальную информацию о геометрических свойствах поверхности функции.
В основе способа исследования функций двух переменных f(x,y) = z, так же как и исследования функции одной переменой, лежит разработка и использование специальных графических образов поверхности функции [52]. Рассмотрим образное представление ЛГХ поверхности функции двух переменных. Информация, представленная базовыми М-образами (рис. 21), имеет целочисленные значения и содержится в индексном массиве значений, при этом выражается в соответствии линейной градации интенсивности тона монохромной палитры р = [0;Р] (рис. 19). Значение ЛГХ в каждой точке пространства образа при этом соответствует косинусу угла Рис 19 Принцип градации тона компонент нормали отклонения нормали от заданной оси. Размер получаемого образа зависит от установленного разрешения создаваемого компьютерного изображения. Точность представленной в образе информации на прямую зависит от диапазона применяемой «палитры». В работе при визуализации используется 256-ти тоновая монохромная палитра, которой достаточно для иллюстрации полученных результатов [53]. На примере поверхности функции типа f(x,y) = z в монографии проф. Толока А.В [54] рассмотрен принцип организации воксельной геометрической модели (ВГМ), представляющей набор базовых растровых М-образов, отражающих дифференциальные свойства рассматриваемой поверхности.
В каждой точке поверхности некоторой функции f(x,y) (рис. 20) определяется вектор нормали к касательной плоскости. Уравнение касательной плоскости выражается из уравнения плоскости проходящей через три заданные точки х (jcl, у\ z\\ (х2, у2, z2), (хЗ, уЗ, z3), Рис. 20. Линейная аппроксимация поверхности функции принадлежащие поверхности функции и не лежащие на одной прямой, при условии стремления расстояние между точками к нулю. Уравнение плоскости, построенной по данным трем точкам, имеет вид [55]:
Геометрические принципы организации пространственного поворота воксельных геометрических моделей
Для создания ВГМ, содержащей смещенную функцию в воксельном пространстве, необходимо выполнить аналогичный расчёт смещения (1.1.1) на целочисленный промежуток Д [21] исходной функции. Вместо привычных координат трехмерного пространства Oxyz, используются индексы массива, представляющего воксельное пространство ijk : Г / =/ + Дг \f=J + Aj . (3.1.1) [k = k + Ak
Для получения набора базовых графических образов смещенной функции необходимо провести аппроксимацию по полученным значениям координат с помощью функционала оператора {GJ, определяющего плоскость по трём точкам не лежащих на одной прямой (х , ), / = 1.3, и определяющего общее уравнение касательной плоскости из определителя по формуле: У1 z1 1 x1 z1 1 x1 У1 1 x1 У1 z1 У2 z2 1 х- x2 z2 1 У + x2 у2 1 z- x2 У2 z2 У3 z3 1 x3 z3 1 x3 У3 1 x3 У3 z3 Коэффициенты уравнения касательной плоскости необходимо нормировать до косинусных компонентов нормали для выбранной окрестности точки нормального поля N(nx , ny , nz , nt ). С последующим применением оператора {C} для перехода от компонентов нормального поля к их графическому представлению. Данный алгоритм известен и описывает прямое преобразование, при котором исходными данными выступает аналитическое выражение, в котором присутствует смещение, выполненное с применением численных методов. Только после завершения всех необходимых сдвигов, по вновь полученной аналитической модели, строится ВГМ, представленная набором базовых графических образов.
Принцип функционально-воксельного подхода к моделированию пространства заключается в нахождении нового положения касательной площадки поверхности функции (рис. 37), организующей вектор нормали. Напомним, ВГМ содержится в массиве значений и несет информацию о направляющих косинусах, определяющих ориентацию единичной нормали в пространстве увеличенной [21]. Обычная адресная замена ячеек массива значений (смещение в контексте индексного массива) не даст нам ожидаемого результата. В итоге будет получено новое положение модели в индексном массиве (рис. 36) но направления Рис. 36. Смещение вектора нормали в плоскости OXY векторов нормалей останутся неизменны, что в свою очередь приведёт к нарушению согласованности получаемой ВГМ и исходного функционального описания.
Чтобы сохранить целостность и согласованность ВГМ, необходимо выполнять смещение вектора нормали, определяющего положение окрестности точки в контексте индексного массива значений с одновременным изменением направления самого вектора. При анализе динамики смещения следует, что параметры формы (углы наклона окрестности точки к осям координат) останутся неизменными, в то время как параметр положения (удаленность от начала координат) изменит свое значение в зависимости от величины смещения.
Однородность структуры представления графической информации в ВГМ предполагает использование единого алгоритма вычислений при повышении размерности задачи смещения. Рассмотрим более подробно данный алгоритм. Ax
При выполнении функционально-воксельного смещения пространства ВГМ необходимо использовать графическую информацию, содержащуюся в ВГМ, представляющую собой ЛГХ. Необходимо с помощью операторов {X} и {Щ выразить в явном виде значение функции на поверхности. После того, как будут получены значения на поверхности функции в каждом элементе массива, содержащего ВГМ, выполняется смещение данных значений на целочисленный промежуток А с помощью матричных преобразований (3.1.1), (3.3.2).
В результате получается новое местоположение значений поверхности функции в пространстве (рис. 37). На следующем этапе создаётся новая ВГМ с помощью алгоритма заложенного в последовательном применении операторов {G} и {С}.
Таким образом, функционально-воксельное смещение ВГМ выглядит по аналогии с евклидовым пространством как композиция последовательных преобразований координат, только представленных нормальным полем, в плоскостях проекции. Конечным итогом таких преобразований для пространства Е3 является вычисление окончательного положения касательной плоскости. Рассмотрим в качестве примера смещение ВГМ для функции окружности.
Ниже на рисунке 38 проиллюстрировано изменение в базовом графическом образе, определяющем параметр формы (ЛГХ D„), при смещении функции окружности, заданной в виде выражения: w = R2 -(х - а)2 - у2, где а - величина смещения вдоль оси ОХ. Рис. 38. Изменение в образе коэффициента D при смещении функции окружности
Воксельный подход к смещению Рассмотрим подробнее взаимосвязь компонентов нормали в ВГМ, на примере двумерного случая, где вектор нормали пространства увеличенной размерности определяет положение прямой на плоскости (рис. 39). Ах + Ву + С = on»
Взаимосвязь локальных геометрических характеристик воксельной геометрической модели Представим прямую Ах+Ву+С = 0 (т. 2,3 є Ах + By + С = 0) в виде пересечения двух плоскостей: 1. Ax + By + Cz = 0 (т. (0,2,3)є Ах + By+ Cz = 0), проходящую через начало координат; 2. z = 1 (т. (і,2,з) є z = 1), отстоящую от плоскости OXY на единицу. Восстановим единичную нормаль N3 из начала координат к плоскости Ax + By + Cz = o. Углы ссп,(Зп,уп - углы отклонения единичной трехкомпонентной нормали N3 от осей ox, OY,OZ соответственно. 4, = cosa„, В„ = cos J3„, C„ = cos r„ - ЛГХ, проекции единичной нормали N3 на оси координат. При изменении положения прямой Ах + Ву + С = о в пространстве будет меняться направление единичного вектора 3. Соответствующим образом будут изменяться компоненты Ап,вп,Сп, определяющие направление данного вектора. При пересечении прямой оси 01 нормаль N3 переходит в двухкомпонентную нормаль N2, где А = cos а и 5 = cos/? (проекции N2 на ОХ и OY) являются параметрами формы. При этом проекция нормали, определяющая параметр положения (удаленность от начала прямой Ах + Ву + С = о), станет равна нулю Сп=0. Уравнение прямой примет вид Ах + Ву = о, что соответствует общему уравнению прямой, проходящей через начало координат.
Тройственность вычислительного подхода к множественным операциям над пространствами ВГМ
В функциональном моделировании есть понятие теоретико-множественных операций. К теоретико-множественным операциям относят: объединение, пересечение, вычитание, декартово произведение, выборка, проекция, соединение, деление. Часть операций, таких как объединение и пересечение возможно реализовать с помощью -функционального моделирования, как еще одного способа конструирования пространства. Особенностью построения Д-функций является наличие пространства увеличенного на единицу размерности, представленного в виде предиката функции [62]. Данная особенность коррелируется с функционально-воксельным представлением функции.
Таким образом, -функциональное моделирование позволяет работать с пространством функции, используя специальные законы при объединении и пересечении. К примеру: закон сохранения знака. Применяя данный закон, можно описывать аналитически сложные геометрические формы, имеющие положительное значение внутри всей конструкции. Данные операции имеют аналогию с операциями алгебры логики и их геометрическим приложением -булевыми операциями [63].
Геометрические принципы -функционального моделирования Д-функции - это функции, обладающие тем свойством, что задание знаков аргументов однозначно определяет знак і?-функции. Разберем на конкретных примерах принцип -функционального моделирования [2] [62] [64]. Предположим, что есть функция, определяющая положение прямой в пространстве: у = кх+Ь. Все значения х четко соотносятся со значениями у . Что бы определить знак функции в каждой из областей трехмерного пространства, разбитого гиперповерхностью Я, добавим значение предиката. Иными словами увеличим размерность пространства на 1 и запишем уравнение прямой в следующем виде: W = y-(kx+b).
На графиках на рисунке 58 помимо самих функции у = 7-х и у = 0,5х-1, так же присутствует информация о знаке в каждой точке пространства вокруг самой функции. Соответственно предиката функции будет
Области положительных и отрицательных значений функции определяться следующим образом: W1=7-x-y и W2 = 0,5х-1-у. Чтобы создать контур с общими областями положительных и отрицательных значений, необходимо воспользоваться логическими операциями для объединения или пересечения: wобщ =W1 W2, wобщ =w1 w2. В теории Рвачёва полная а-система і?-функций, применяемая в аналитическом моделировании, представлена системой уравнений: где ае(-1;1] - коэффициент, влияющий на форму функции внутри объекта, необходимый при решении краевых задач и обеспечивающий ноль на границе. Последовательная комбинация таких преобразований позволяет получать общее функциональное описание области пространства [65] [52], составленной из множества аналитических зависимостей.
Из аналитической записи для W1 и W2 следует, что при значении предикаты равном нулю, уравнения проецируются в линию на плоскости. Расположение положительной и Рис. 59. Общие области положительных и отрицательных значений функций отрицательной области можно поменять местами, изменив знак в выражении. Таким образом, R функциональное моделирование позволяет создавать функциональное описание сложных геометрических объектов в пространстве. На рисунке 60 разобран пример создания геометрического объекта сложной формы с помощью R-функционального моделирования.
Пример создания геометрического объекта сложной формы с помощью -функционального моделирования При объединении и пересечении областей функции используется упрощенный вид выражения (3.1.1). При а = 0 результатом является квадратичный закон заполнения функционального пространства при сохранении нулевых значений на границе. Тогда а-система і?-функций, применяемая в аналитическом моделировании будет представлена следующей системой уравнений:
На каждом их этапов формируется отдельная часть общей формы объекта, добавляя или вычитая области пространства, постепенно формируется общее уравнение геометрии сложной формы. Поэтапный вывод такого уравнения представлен ниже на рисунке 61: W1 = -х + 3; W2 = х + 3; j = 2x + 18 j = -2x+18 W12 =W1 + W2- (W2 + W2);[W12 =W1C\W2;] W3=y +14; W 123 = w12 +W3- (W12 + W3); W4 = - + 2x + 18; W5 = - -2x + 18; 2 = (j-8)2+x2 W45 =W4+W5- (W2 +W2); 2 = (М)Ч x2 wteh = 123 +W 45 -VW 23 + 45 ); W6 = -y - 2x - 8; W7 = у +12; W67 =W6+W7+ (W62 + W72);[W67 =W6KJW7;] W8=-y + 2x- 8; W78 = W7+W8 + -](W2 +W2); x = -3 wk = wteh + w67 J(W2 +W 67 ); Wt=Wk+ W78 (QV2 +W728); Wo1 = -(2-( -8)2-x2); Wo2 = -(2-( -4)2-x2); У2 -x2); Wo3 = "(2 Wto1 =Wt+ Wo1 - (W2 +W21); y = -12 j = -2x-8 j = 2x-8 W to1o2 = W to1 + W o2 4(W to1 +W2 2 ); Wmkety = W to1o2 + W o3 -4(W2 1o2+W2 3 ); y = -14 Wrakety=W1 оЖ2 n(f3 глЖ4 глЖ5 гл(Ж6 Ж7)гл(Ж7 Ж8)глЖо1 глЖо2 глЖо3 Рис.61. Формирование общего аналитического выражения функции сложной формы с помощью -функционального моделирования 4.2. Тройственность вычислительного подхода операциям над пространствами ВГМ к множественным ВГМ позволяет применять операции R-функций для конструирования сложной ВГМ как результата синтеза из нескольких ВГМ. Принцип тройственного вычислительного подхода к множественным операциям над пространствами ВГМ, так же, как при арифметических и операциях компоновки пространства ВГМ сохраняется.
В качестве примера сравним результат R-функционального объединения и пересечения двух окружностей при F и FV моделировании [21] [61].
Функциональный подход к теоретико-множественным операций для метода ФВМ известен и характерен использованием значения аналитического выражения функции как одного из предикатов в выражении (3.1.1), для создания ВГМ как результата синтеза нескольких функции, представленных единой областью определения.
В результате формируются общие области положительных и отрицательных значений. На рисунке 62 представлены отдельные образы окружностей функции W=x 2+y 2-1 и W2=(x-1)2 + (y2)-0.52. Результат их функционального объединения и пересечения представлен на рисунке 63. Формирование образов происходит по алгоритму, приведенному в предыдущих главах. В качестве исходных данных выступает аналитическая запись выражения. Далее с помощь последовательного применения операторов {G} и {С} формируется ВГМ, содержащая результат синтеза пространств ВГМ.