Аффины

· Лекция 2 Аффины.

· Двумерные геометрические (аффинные) преобразования

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

 

· Представление точек и общая схема преобразования с использованием матриц

Так как в компьютерной графике большинство объектов определяются с помощью точек или вершин, то начнем именно с них.  Как известно, точка на плоскости представляется двумя своими координатами (x y). Эту пару можно представить в виде матрицы [x y] размером 1*2 называемой вектор-строка или матрицы  размером 2*1  называемой вектор-столбец. Данные матрицы часто называют координатными векторами. В трехмерном пространстве, точка определяется тройкой координат, и координатный вектор увеличивают свой размер на единицу. Например, вектор-строка будет иметь размер 1*3  - [x y z] .

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

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

Р*М = Р’ ,

Рекомендуемые материалы

где  М – матрица геометрического преобразования; Р – вектор-строка представляющая исходную точку; Р’- вектор-строка полученная в результате преобразования.

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

Р*М =[x y] [(ax+cy) (bx+dy)] = [x’ y’]

т.е. координаты преобразованной точки формируются суммой исходных координат умноженных на соответствующие коэффициенты:

x’= ax+cy;

y’= bx+dy;

Если в матрице преобразования a=d=1 и c=b=0  то

x’= 1x + 0y = x;

y’= 0x+1dy = y;

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

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

Р’* М^-1 = Р ,

где М^-1 - это матрица обратная к матрице трансформации. Методы получения таких матриц рассматриваются в матричной алгебре. Мы рассмотрим одно важное свойство такой матрицы. Если применить к объекту некоторое преобразование, а затем преобразование, обратное данному, то исходный объект останется неизменным.

       Р*М* М^-1= Р

Такой же эффект мы получали при умножении на единичную матрицу. Следовательно, произведение М* М^-1 дает единичную матрицу.

· Преобразование масштабирования

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

Положим  c=b =0, a¹0 и d ¹0, тогда

Р*М =[x y] [(ax+0y) (0x+dy)] =[(ax) (dy)]= [x’ y’]

Таким образом

x’= ax

y’= dy

Следовательно, мы получили преобразование масштабирования. Коэффициенты a и d являются масштабирующими коэффициентами по осям x и y. Обычно их обозначают Sx и Sy, а  соответствующая матрица носит название матрицы масштабирования.

S =

Если 0 < Sx = Sy < 1 имеет место сжатие, в противном случае при  Sx = Sy > 1 расширение. Обратите внимание, что при масштабировании геометрических объектов происходит не только изменение их размеров, но и смещение относительно начала координат. Начало координат остается инвариантным как к преобразованию масштабирования, так и к другим преобразованиям, выполняемым по рассматриваемой схеме. В этом легко убедится:

[0 0] [(a*0+0*0) (0*0+d*0)] =[(0) (0)]= [0 0]

Если Sx ¹ Sy , то координаты масштабируются различным образом и происходит искажение пропорций объектов.

Для обращения преобразования необходимо произвести масштабирование с коэффициентами, обратными заданным. Обратная матрица представляется следующим образом: S^-1 =

Интересный эффект возникает при разрешении отрицательных значений коэффициентов в матрице масштабирования. В этом случае, наряду с масштабированием, происходит отображение объектов относительно различных осей. Положим  Sx = -2, а  Sy = 1.

S=               x’= -2*x           y’= 1*y

Очевидно, что координата y останется неизменной, а координата x увеличится вдовое и поменяет свой знак, т.е. наряду с масштабированием произойдет отображение относительно оси y.

При единичных величинах коэффициентов масштабирования не будет, а знаки будут определять оси отображения. Матрица  определит отображение относительно оси х, а матрица  -  отображение относительно оси y.

Если отклониться от условий масштабирования, положив  = =1 и a=d=0, тогда

преобразование [x y] [(0x+1y) (1x+0y)] =[(y) (x)]= [x’ y’] приведет к перестановке координат  x’= y,  y’= x, что геометрически можно представить как отражение относительно прямой x=y, делящей первый квадрант на октанты. Преобразованиеприводит к отображению относительно прямой y = -x.

· Преобразование поворота

Рассмотрим следующее преобразование.  Его результат можно рассматривать как поворот на 90 градусов против часовой стрелки относительно начала координат. Нетрудно определить другие частные случаи поворота: на 180 -и  270 градусов - .

Но как определить преобразование поворота относительно начала координат на произвольный угол? Рассмотрим схему такого поворота, представленную на рисунке 2.9. Введем следующие обозначения: r – радиус поворота. Отрезок ОР, соединяющий начала координат О с поворачиваемой точкой Р; l - угол между осью x и начальным положением отрезка ОР; q - угол, на который выполняется поворот. Определим начальное положение точки Р и ее положение после поворота Р’.

Р = [x y] = [r cos l   r sin l]     (1)

Р’ = [x’ y’] = [r cos(q+l)   r sin(q+l)]

Применив формулы косинуса и синуса суммы, получим:

Р’ = [x’ y’] = [r(cos q cosl - sin q sinl)   r(sin q cos l+ cos q sin l)]

Раскрывая скобки и учитывая формулу (1) получаем:

Р’ = [x’ y’] = [(xcos q  - y sin q) (x sin q + y cos q)] т.е. точка после поворота имеет координаты 

x’ = x cos q  - y sin q

y’ = x sin q + y cos q

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

R =

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

R-1 ==

· Преобразование переноса  и однородные координаты

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

x’ = x + dx

y’ = y + dy,

где dx и dy  - проекции вектора на оси x и y. Рисунок 2.10.

Определить такое преобразование в рамках рассмотренной выше схемы, использующей матрицу размером 2*2, не удается. Преодолеть данное затруднение можно с помощью перехода в однородные координаты. Точка на плоскости в однородных координатах определяется тройкой [X Y W], где W – масштабирующий коэффициент, а X и Y координаты точки, получаемые из декартовых координат посредством следующих соотношений X = x*W, Y = y*W. По однородным координатам с помощью деления на масштабирующий коэффициент всегда можно найти декартовы координаты. x = X/W, y = Y/W. Очевидно, что коэффициент не должен быть равен 0.

Однородные координаты не обладают однозначностью. Точки [2 3 1], [4 6 2], [6 9 3] соответствуют одной и той же точке [2 3] в декартовых координатах.

Рассмотрим однородные координаты при W = 1. В этом случае однородные координаты точки будут совпадать с декартовыми. Что же мы выиграли, увеличив размерность вектора?

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

Р*М =[x y 1] [(a*x+c*y+m) (b*x+d*y+n) (1)] = [x’ y’ 1]

В рамках новой схемы мы легко можем представить как все рассмотренные ранее преобразования (для этого необходимо обнулить коэффициенты m и n), так и преобразование переноса. Коэффициенты m и n собственно и определяют величины перемещения по осям x и y. Матрица переноса представляется следующим образом:

D =

где dx и dy как уже говорилось, проекции вектора переноса.

Р*D =[x y 1]  [(1*x+0*y+dx) (0*x+1*y+dy) (1)] = [x’ y’ 1]

Для обращения преобразования необходимо выполнить перенос на те же величины, но в противоположном направлении.

D =

Обратите внимание. Начало координат не является инвариантным к преобразованию переноса.

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

S =     R =

· Выполнение произвольных преобразований на плоскости. Композиция преобразований

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

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

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

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

Выполнить требуемое преобразование;

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

Рассмотрим данный подход на примере. Повернем отрезок, заданный своими конечными точками P1 и P2 , вокруг точки Р1 на угол 90 градусов.  Как выполнить поворот объекта вокруг произвольной точки, мы не знаем. Однако нам известно как поворачивать объекты вокруг начала координат.

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

Р’ = P*T =  Т 

где Р - матрица объединяющая координатные вектора конечных точек отрезка, а Т – матрица переноса.

На втором этапе выполним поворот отрезка на требуемый угол.

Р’’= P’R

Где R – матрица поворота на угол 90 градусов относительно начала координат.

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

Р’’’ = Р’’T^-1

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

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

Р’’’ = ((P*T)*R)*T^-1 = P*T*R* T^-1= P*M

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

K  =  P *R*T * T^-1= P*R

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

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

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

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

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

· Выводы по плоским геометрическим преобразованиям

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

М =

Элементы a,b,c и d определяют коэффициенты поворота, масштабирования и сдвига. Элементы е и f  служат для формирования переноса. Смысл трех оставшихся элементов необходимо прояснить. Начнем с k и m. Обычно, мы устанавливали им нулевое значение. Теперь положим их отличными от нуля,  элементы главной диагонали приравняем к единице, а остальные элементы обнулим. Применим получившееся преобразование к произвольной точке заданной в однородных координатах с w =1.

[x’ y’ w’] =  [x y 1] = [x y kx+my+1]

x’ = x,    y’=y 

Для того, чтобы понять результат, обратимся к геометрической интерпретации однородных координат. Точка в однородных координатах определяется тройкой, следовательно, мы имеем дело с трехмерной координатной системой, определенной в пространстве. Две оси системы нам привычны это X и Y, а третья – W, ось масштабных коэффициентов. Зафиксировав значение W, установив его равным единице, мы перешли от пространства к плоскости параллельной плоскости XOY. Установив элементы k и m отличными от нуля, мы сняли данное ограничение и полученная в результате преобразования точка расположена в пространстве. При этом ее третья координата определяется по формуле kx+my+1 т.е. зависит от значений x и у. Следовательно, точки, подвергшиеся данному преобразованию, будут лежать в некоторой плоскости не параллельной плоскости XOY. Вернем точку на плоскость W=1 путем проецирования лучами, проходящими через начало координат. Из подобия треугольников x’’= x’/w’= x/( kx+my+1) и аналогично y’’= y’/w’= y/( kx+my+1). Таким образом, математически подобное проецирование выразится в простой нормализации.

[x’’ y’’ 1] =

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

[x y 1] = [x y s]

Все точки, подвергшиеся такому преобразованию будут лежать в плоскости W=s которая параллельна плоскости W=1. Нормализация будет приводить к простому масштабированию с одинаковыми коэффициентами по осям.

[x’ y’ 1] =

Основное отличие такого масштабирования от рассмотренного ранее состоит в том, что при s<1 будет происходить растяжение, а при s>1 – сжатие.

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

При переходе в пространство добавляется координата Z и, следовательно, размерность матриц увеличивается на единицу. Точки в пространстве представляются четверками [x y z 1],  размерность матриц преобразований становится 4*4.

В главную диагональ матрицы масштабирования добавляется масштабирующий коэффициент по оси Z, а в матрицу переноса добавляется проекция вектора переноса на ось Z.

Отображение в пространстве производится относительно плоскостей. Так при отображении относительно плоскости XOY поменяют знаки только координаты Z. Матрица такого преобразования будет выглядеть следующим образом. М = . Аналогично для других плоскостей.

С поворотами ситуация более сложная.

· Преобразования поворота в пространстве

 Повороты в пространстве производятся вокруг осей. Рассмотрим повороты вокруг главных координатных осей. Положительными считаются повороты против часовой стрелки, если смотреть с конца положительной полуоси. Изученный нами ранее поворот относительно начала координат на плоскости XOY можно рассматривать как поворот в пространстве относительно оси Z. Для получения матриц поворота относительно других координатных осей можно использовать ту же схему рассуждений, что приводилась нами для определения поворота на плоскости XOY.

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

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

Для выполнения заданного преобразования необходимо:

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

Выполнить поворот вокруг оси X на угол a, переводящий направляющий вектор в плоскость XOZ .

Выполнить поворот вокруг оси Y на угол b, совмещающий направляющий вектор с положительной полуосью Z.

Выполнить поворот вокруг оси Z  на требуемый угол q.

Выполнить обратные преобразования, приводящие сцену в исходное состояние.

· Коммутативность преобразований

Преобразования как изменение координатных систем

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

Рассмотрим любое преобразование объекта, например перенос точки. Перенесем точку в соответствии с заданным вектором. Точка Р с координатами (2 3) преобразуется в точку Р’ с координатами (4 5).

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

Бесплатная лекция: "1 - Структура вычислительной машины" также доступна.

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

Рассмотрим еще один пример. В исходной координатной системе С1 с помощью преобразования масштабирования ( Sx=0.5 Sy=0.5 ) определим координатную систему  C2=C1*S₂₁. На ее основе с помощью преобразований переноса (Dx=4 Dy=2) и  поворота (q=45є) определим координатную систему 

C3=C2*T₂₃*R₂₃. С учетом композиции запишем С3=С2*M₂₃ Очевидно, что отношения между координатными системами С3 и С1 описываются формулой  C3= C1*S₂₁*T₂₃*R_{23 =}С1*М₃₁.

Таким образом, мы определили три координатные системы и установили отношения между ними. Нарисуем в координатных системах С2 и С3 два одинаковых домика и перейдем в координатную систему С1. Изображения подверглись масштабированию, повороту и смещению согласно установленных нами отношений.

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

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