Геометрические преобразования

ГЕОМЕТРИЧЕСКИЕ ПРЕОБРАЗОВАНИЯ

ВВЕДЕНИЕ В ГЕОМЕТРИЧЕСКИЕ ПРЕОБРАЗОВАНИЯ

Виды преобразований

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

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

1) перемещать рисунки из одного места экрана в другое;

2) создавать рисунок из более мелких элементов (составных частей);

3) добавлять к существующему рисунку новые элементы;

4) увеличивать размер рисунка для улучшения его наглядности или отображения более мелких деталей;

5) уменьшать размер рисунка для внесения, например, поясняющих надписей или отображения на экране новых рисунков;

6) создавать движущиеся изображения.

Все изменения рисунков можно выполнить с помощью трех базовых операций:

1) переноса (перемещения) изображения;

2) масштабирования (увеличения или уменьшения размеров) изображения;

3) поворота изображения (употребляют также термины вращение, изменение ориентации).

Эти операции называются аффинными преобразованиями. Различают двумерные и трехмерные аффинные преобразования.

Основные геометрические свойства двумерных аффинных преобразований:

1) прямые линии после преобразований остаются прямыми;

2) параллельные прямые – параллельными;

3) Отношения деления отрезков остаются неизменными.

Основные геометрические свойства трехмерных аффинных преобразований:

1) плоскости после преобразования остаются плоскостями;

2) параллельные плоскости – параллельными.

Двумерные аффинные преобразования

1) Перенос точки

Тогда Р' с координатами (х',y') полученная после переноса точка.

Рис.1. Перенос точки

x' = x + dx

y' = y + dy

Аффинные преобразования удобно записывать в матричной форме:

P = [x, y];

P' = [x', y'];

T = [dx, dy].

Тогда

2) Перенос отрезка

x1'= x1 + dx

y1'= y1 + dy

x2'= x2 + dx

y2'= y2 + dy

В векторной форме:

T = [dx, dy] - вектоp пеpеноса.

Тогда

Р'= P + T

Масштабирование выполняется умножением координат на некоторые коэффициенты Sx, Sy.

1) Масштабирование точки

Тогда

y'= ySy,

P'= PS

2) Масштабирование отрезка

P'= PS.

а) однородное, когда Sx = Sy;

б) неоднородное, когда Sx  Sy.

При неоднородном масштабировании фигура может изменятся (кpуг-эллипс ).

Масштабирование также делится по значению коэффициента масштабирования S (рис.3, 4).

Пусть необходимо осуществить повоpот точки P (x,y) на угол A:

Рис.5. Дмумерный поворот

x = r cos B,

y = r  sin B. (1)

После поворота точка P' имеет координаты :

x'= r  cos ( A + B ),

y'= r  sin ( A + B ). (2)

Преобразуем выражение (2):

x'= r  cos A  cos B - r  sin A  sin B,

y'= r  cos B  sin A + r sin B cos A. (3)

Подставим (1) в (3):

x'= x  cos A - y  sin A,

y'= x  sin A + y  cos A. (4)

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

P = [ x y ];

P'= [ x' y'];

.

Тогда

Движение считается положительным ( А>0 ), если движемся против часовой стрелки; отрицательным - по часовой.

Пусть задан отрезок, определенный координатами

1) Перенос dx=2, dy=3:

2) Масштабирование Sx=Sy=2:

3) Поворот на А=30 градусов:

Трехмерные аффинные преобразования

Для того, чтобы перенести точку, надо сделать приращение к координатам dx, dy, dz.

Выполняется аналогично двумерному масштабированию. Матрица преобразования:

а) Поворот на угол А по часовой стрелке вокруг оси z:

Не перепутаны ли знаки у sin'усов? Нет не перепутаны, поскольку это поворот по часовой, т.е. здесь левосторонняя система координат.

б) Поворот вокруг оси y по часовой стрелке на угол А:

. (2)

в) Поворот вокруг оси х по часовой стрелке на угол А:

Результирующий поворот точки с координатами (x,y,z):

[x',y',z'] = [x,y,z]  R(A)  R(B)  R(C).

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

ГЕОМЕТРИЧЕСКИЕ ПРЕОБРАЗОВАНИЯ С ИСПОЛЬЗОВАНИЕМ ОДНОРОДНЫХ КООРДИНАТ

Однородные координаты

Геометрический смысл однородных координат заключается в следующем (рис.6 из [1]). Произвольная точка на прямой, соединяющей начало координат, точку О(0,0,0), с точкой Р'(x,y,1), может быть задана тройкой чисел вида (Wx,Wy,W). Вектор с координатами Wx,Wy,W является направляющим вектором прямой, соединяющей точки О(0,0,0) и Р'(x,y,1). Эта прямая пересекает плоскость z=1 в точке (x,y,1), которая однозначно определяет точку (x,y) координатной плоскости x,y.

Рис.6.

Тем самым между произвольной точкой с координатами (x,y) и множеством троек чисел вида (Wx,Wy,W), W0 устанавливается взаимно однозначное соответствие, позволяющее считать числа Wx,Wy,W новыми координатами этой точки. Однородные координаты можно представить как вложение промасштабированной с коэффициентом W двумерной плоскости в плоскость z=W (здесь z=1) в трехмерном пространстве.

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

Если устройство отображения работает только с целыми числами (или если необходимо работать только с целыми числами), то для произвольного значения W (например, W=1) точку с однородными координатами (0.5 0.1 2.5) представить нельзя. Однако при разумном выборе W можно добиться того, чтобы координаты этой точки были целыми числами. В частности, при W=10 для рассматриваемого примера имеем (5 1 25).

Другой случай. Чтобы результаты преобразования не приводили к арифметическому переполнению, для точки с координатами (80000 40000 1000) можно взять, например, W=0.001. В результате получим (80 40 1).

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

Как известно, преобразования переноса, масштабирования и поворота в матричной форме записываются в виде:

Р'= P + T

P'= PS

P'= PR.

Уравнения переноса записываются в виде матрицы преобразования однородных координат следующим образом:

или

где

Иногда подобные выражения записывают таким образом (см. например, [16]):

Рассмотрим, например, двойной перенос точки. Пусть необходимо перенести точку Р в точку Р' на расстояние (dx1, dy1), а затем в P'' на расстояние (dx2,dy2). Суммарный перенос должен быть равен расстоянию (dx1+dx2, dy1+dy2). Докажем это. Запишем данные в виде

P'=PT(dx1,dy1),

P''= P'T(dx2,dy2).

Подставляя первую формулу во вторую, получим:

P''= P(T(dx1,dy1)T(dx2,dy2)).

Матричное произведение T(dx1,dy1)T(dx2,dy2) есть

.

Таким образом, действительно, результирующий перенос есть (dx1+dx2, dy1+dy2), т.е. последовательные переносы являются аддитивными.

Уравнения масштабирования в матричной форме с использованием однородных координат записываются в виде

,

S(Sx, Sy)=,

P'=P'S(Sx, Sy).

Матричное произведение S(Sx1, Sy1)S(Sx2, Sy2) есть

Таким образом последовательные масштабирования мультипликативны.

И наконец, уравнения поворота (в правосторонней системе) можно представить в виде

[x' y' 1] = [x y 1],

P'=PR(A).

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

Композиция двумерных преобразований с помощью однородных координат

Рассмотрим, например, поворот объекта относительно некоторой произвольной точки P1. Поскольку нам известно, лишь как поворачивать вокруг начала координат, разобьем исходную задачу на три подзадачи:

1) перенос, при котором точка Р1 перемещается в начало координат;

2) поворот;

3) перенос, при котором точка из начала координат возвращается в первоначальное положение Р1.

Последовательность этих преобразований показана на рис.7.

Рис. 7.

Результирующее преобразование имеет вид:

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

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

Рис. 8.

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

T(-x₁,-y₁)S(S_x,S_y)R(A)T(x₂,y₂).

В общем случае перемножение матриц некоммутативно. Если М1 и М2 представляют собой элементарные перенос, масштабирование или поворот, в следующих частных случаях коммутативность имеет место:

М1	М2
Перенос Масштабирование Поворот Масштабирование (при Sx=Sy)	Перенос Масштабирование Поворот Поворот

Ее верхняя часть размером 2х2 является объединенной матрицей поворота и масштабирования, в то время как t_x и t_y описывают суммарный перенос. Для вычисления РМ как произведения вектора на матрицу размером 3х3 требуются 9 операций умножения и 6 операций сложения. Структура последнего столбца обобщенной матрицы позволяет упростить фактически выполняемые действия:

x' = xr₁₁+yr₂₁+tx,

y' = xr₁₂+yr₂₂+ty,

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

Матричное представление трехмерных преобразований с помощью однородных координат

Трехмерная система координат, которой мы будем пользоваться в данном разделе, является правосторонней (рис. 9.).

Рис.9. Правосторонняя система координат

Примем соглашение, в соответствии с которым положительными будем считать такие повороты, при которых (если смотреть с конца положительной полуоси в направлении начала координат) поворот на 90^о против часовой стрелки будет переводить одну положительную полуось в другую.

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

Если ось вращения	Положительным будет направление поворота
x y z	от y к z от z к x от x к y

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

Трехмерный перенос является простым расширением двумерного:

T(dx,dy,dz) = ,

т.е. [xyz1]T(dx,dy,dz) = [x+dx y+dy z+dz 1].

Масштабирование расширяется аналогичным образом:

S(Sx,Sy,Sz) = ,

[xyz1]S(Sx,Sy,Sz) = [Sxx Syy Szz 1].

В трехмерном пространстве поворот вокруг оси z описывается выражением (напомним, это выражение для правосторонней системы, для левостронней знаки синусов поменялись бы местами)

Rz(A) = .

Матрица поворота вокруг оси x имеет вид

Rx(A) = .

Матрица поворота вокруг оси у записывается в виде

Ry(A) = .

Столбцы (и строки) верхней левой подматрицы размером 3х3 матриц Rz(A), Rx(A), Ry(A) представляют собой взаимно ортогональные единичные векторы.

Все эти матрицы преобразований имеют обратные матрицы. Матрица, обратная Т, получается подстановкой знака минус перед dx, dy и dz; обратная S – заменой Sx,Sy и Sz на обратные им значения, а для каждой из трех матриц поворота – выбором отрицательного угла поворота.

Результатом произвольной последовательности поворотов вокруг осей x,y, и z является матрица М, имеющая вид

М = .

Подматрицу поворота размером 3х3 называют ортогональной, поскольку ее столбцы являются взаимно ортогональными единичными векторами. При повороте, задаваемом матрицей, эти единичные векторы совмещаются с осями x,y и z. Матрицы поворота сохраняют длину и углы, а матрицы масштабирования и переноса не сохраняют.

Для любой ортогональной матрицы В обратная матрица совпадает с транспонированной: В^-1 = В^Т. Этот результат является полезным, поскольку вычислять матрицу, обратную матрице поворота, приходится часто. Для получения транспонированной матрицы не требуются даже взаимные пересылки между элементами массива, описывающего матрицу. Необходимо только при выборе элементов массива поменять местами индексы строк и столбцов. Этот метод определения обратной матрицы дает тот же результат, что и способ обращения Rx,Ry,Rz, основанный на подстановке знака минус углом перед углом А.

Можно перемножить произвольное число матриц поворота, масштабирования и переноса. Результат всегда будет иметь вид

.

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

[x' y' z'] = [x y z]R + T,

где R и T - подматрицы общей матрицы.

Пример композиции трехмерных преобразований [7]

Начальная позиция Конечная позиция

Рис. 11. Преобразование точек Р₁, Р₂ и Р₃ из начальной позиции
в конечную

Рассмотрим пример. Задача состоит в том, чтобы преобразовать отрезки и из начальной позиции в конечную. Точка Р1 переносится в начало координат, располагается вдоль отрицательной полуоси z, а помещается в плоскости yz в той ее половине, где ось у положительна. На длины отрезков преобразование не воздействует.

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

1. Перенос точки Р₁ в начало координат.

2. Поворот вокруг оси у до совмещения с плоскостью yz.

3. Поворот вокруг оси х до совмещения с отрицательной плоскостью z.

4. Поворот вокруг оси z до совмещения с плоскостью yz.

Шаг 1. Перенос Р₁ в начало координат:

Применение Т к Р₁, Р₂ и Р₃ дает

Р₁' = P₁T(-x₁, -y₁, -z₁) = [0 0 0 1],

Р₂' = P₂T(-x₁, -y₁, -z₁) = [x₂-x₁ y₂-y₁ z₂-z₁ 1],

Р₃' = P₃T(-x₁, -y₁, -z₁) = [x₃-x₁ y₃-y₁ z₃-z₁ 1].

Шаг 2. Поворот вокруг оси у.

Поворот производится на положительный угол А, для которого

где

В результате подстановки этих значений в матрицу Ry(A) получаем:

Шаг 3. Поворот вокруг оси х.

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

cos(-B) = cosB = ,

sin(-B) = -sinB = ,

где

. (длина отрезка ).

Результатом поворота на шаге 3 является:

P₂''' = P₂''Rx(B) = P₂'Ry(A)Rx(B) = P₂TRy(A)Rx(B) =

= ,

т.е. теперь совпадает с отрицательной полуосью z.

Шаг 4. Поворот вокруг оси z.

P₃''' = [x₃''' y₃''' z₃''' 1] = P₃T(-x₁, -y₁, -z₁)Ry(A)Rx(B).

Рис. 14. Поворот вокруг оси z; проекция поворачивается до совмещения с осью у

Поворот производится на положительный угол С, для которого cosC = y₃'''/D₂, sinC = x₃'''/D₂, D₂ = .

После шага 4 получается конечный результат.

Результирующая матрица

T(-x1,-y1,-z1)Ry(A)Rx(B)Rz(C) = TR

описывает искомое преобразование.

ГЕОМЕТРИЧЕСКИЕ ПРЕОБРАЗОВАНИЯ В ГРАФИЧЕСКОМ СТАНДАРТЕ OPENGL

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

Масштабирование

glScalef (0.5, 0.5, 1.0);

то будет нарисована уменьшенная в два раза фигура.

Например (пример Chapter\Ex50 из М.Краснова):

glScalef (0.5, 0.5, 1.0);

glBegin (GL_POLYGON);

glVertex2f (-0.23678, 0.35118);

glVertex2f (-0.23678, 0.7764);

glVertex2f (-0.37966, 0.7764);

glVertex2f (-0.55, 0.60606);

glVertex2f (-0.55, -0.4);

glVertex2f (-0.23576, -0.4);

glVertex2f (-0.23678, 0.35118);

glVertex2f (-0.23576, -0.4);

glVertex2f (0.1375, -0.4);

glVertex2f (0.13678, 0.35118);

glEnd;

glBegin (GL_POLYGON);

glVertex2f (0.45, -0.4);

glVertex2f (0.45, 0.60606);

glVertex2f (0.27966, 0.7764);

glVertex2f (0.13678, 0.7764);

glVertex2f (0.13678, 0.35118);

glEnd;

glScalef (2.0, 2.0, 1.0);

Библиография

2. Аммерал Л. Машинная графика на языке Си. М.:СолСистем, 1992.

Т.1:Принципы программирования в машинной графике. 224 с.

Т.2:Машинная графика на персональных компьютерах. 232 с.

Т.3:Интерактивная трехмерная машинная графика. 317 с.

Т.4:Программирование графики на Турбо Си. 221 с.

3. Роджерс Д. Алгоритмические основы машинной графики. - М.:Мир, 1989. - 512 с.

4. Абраш М. Таинства программирования графики. Киев.:ЕвроСИБ, 1996. 384 с. ил.

5. Довгаль В.М., Керекеша В.В., Веретенников А.А. Растровые продукционные системы // Известия КГТУ, № 2, Курск. гос. техн. ун-т, 1998. С.110-119.

6. Хирн Д., Бейкер М. Микрокомпьютерная графика. М.:Мир, 1987. - 352 с.

7. Фоли Дж., вэн Дэм А. Основы интерактивной машинной графики. М.:Мир, 1985. - Т.1: 375 с., Т.2: 368 с.

8. Фролов А.В., Фролов Г.В. Программирование видеоадаптеров. М.: ДИАЛОГ-МИФИ, 1995. 272 с. - (Библиотека системного программиста; Т.21)

9. Корриган Дж. Компьютерная графика: Секреты и решения: Пер. с англ. - М.:Энтроп, 1995. 352 с.

10. Прокофьев Б.П., Сухарев Н.Н., Храмов Ю.Е. Графические средства Turbo C и Turbo C++/ ред. Г.В.Генса, Ю.Е.Храмова. М.: Финансы и стастистика, СП “Ланит”, 1992. 160 с.

11. Марков А.А., Нагорный Р.М. Теория алгорифмов. М.: Наука, 1984. 432 с.

12. Тоффоли Т., Марголус Н. Машины клеточных автоматов: Пер. с англ. М.: Мир, 1991. 280 с.

13. Методы модификации формальных систем обработки символьной информации /В.М.Довгаль; Курск. гос. техн. ун-т. Курск, 1996. 115 с.

14. Керекеша В.В. Конструктивные объекты компьютерной графики // Сборник материалов 3 Международной конференции Распознавание-97. Курск. гос. техн. ун-т. Курск, 1997. С.207-208.

15. Титов В.С., Довгаль В.М., Керекеша В.В., Веретенников А.А. Разложение в растр окружности с помощью системы продукционных правил // Межвузовский сборник научных трудов "Информационные технологии моделирования и управления". Воронежский гос. техн. ун-т. Воронеж, 1998. С.133-136.

16. Тихомиров Ю. Программирование трехмерной графики. СПб.: BHV – Санкт-Петербург, 1998. 256 с.

17. Segal M., Akeley K. The OpenGL Graphics System: A Specification (Version 1.1 – 25 June 1996). Editor: Chris Frazier.

18. OpenGL for Windows from Silicon Graphics. Release Notes for Manufacturing Release 1. (www.sgi.com, 1997.)