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

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

5.1. Преобразования на плоскости и в пространстве

Для решения таких задач, как движение объектов и их частей, управления камерой применяются аффинные преобразования (АП), рассмотрим их основные свойства:

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

2) пересекающиеся прямые остаются пересекающимися, а параллельные – параллельными;

3) при АП пространства пересекающиеся плоскости остаются пересекающимися, параллельные – параллельными, а скрещивающиеся – скрещивающимися;

4) при АП сохраняются отношения площадей двух квадратов на плоскости и отношение объемов двух кубов в пространстве.

Аффинные преобразования на плоскости

Допустим, на плоскости задана прямолинейная координатная система. Тогда каждой точке М соответствует упорядоченная пара чисел (х ,у ) ее координат (рис. 5.1). Вводя на плоскости еще одну прямолинейную систему координат, мы ставим в соответствие той же точкеМ другую пару чисел – (х *,у *).

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

x* = α x+ β y+ λ ,

y* = γ x+ δ y+ µ ,

где α , β , λ , γ , µ , δ – произвольные числа, связанные неравенством

α β ≠ 0.

γ δ

Формулы (1) можно рассматривать двояко: либо сохраняется точка и изменяется координатная система (рис. 5.2) (в этом случае произвольная точка М остается той же, изменяются лишь ее координаты), либо изменяется точка и сохраняется координатная система (рис. 5.3) (в этом случае формулы (1) задают отображение, переводящее произвольную точкуM (x ,y ) в точкуМ *(х *,у *), координаты которой определены в той же координатной системе).

Рис. 5.1. Исходные

Рис. 5.2. Преобразова-

Рис. 5.3. Преобразова-

ние системы координат

ние точки

В дальнейшем мы будем рассматривать формулы (1) как правило, согласно которому в заданной системе прямолинейных координат преобразуются точки плоскости.

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

1. Поворот вокруг начальной точки на угол ϕ описывается формулами

x * = x cosϕ − y sinϕ ,

y * = x sinϕ + y cosϕ .

2. Растяжение (сжатие) вдоль координатных осей можно задать так:

x * = α x ,y * = δ y ,α > 0,δ > 0.

Растяжение вдоль оси абсцисс обеспечивается при условии, что α > 1, а сжатие – при 0 <α < 1.

3. Отражение (относительно оси абсцисс) задается при помощи

x *= x ,y *= − y .

4. Параллельный перенос обеспечивают соотношения

x* = x+ λ , y* = y+ µ .

Выбор этих четырех частных случаев определяется двумя обстоятельствами.

1. Каждое из приведенных выше преобразований имеет простой и наглядный геометрический смысл (геометрическим смыслом наделены и постоянные числа, входящие в приведенные формулы).

2. Как доказывается в курсе аналитической геометрии, любое преобразование вида (1) всегда можно представить как по-

следовательное исполнение простейших преобразований. Для эффективного использования этих известных формул в за-

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

cosϕ		sinϕ
	− sinϕ
	− sinϕ	cosϕ	−1

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

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

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

x 1/ x 3= x , x 2/ x 3= y .

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

Заметим, что произвольная точка на прямой, соединяющей начало координат, точку O (0, 0, 0) с точкойM *(х ,у , 1), может быть задана тройкой чисел вида (hx ,hy ,h ).

Рис. 5.4. Однородные координаты

Будем считать, что h ≠ 0. Вектор с координатамиhx ,hy ,h является направляющим вектором прямой, соединяющей точки 0(0, 0, 0) иМ *(х ,у , 1). Эта прямая пересекает плоскостьz = 1 в точке (х ,у , 1), которая однозначно определяет точку (х ,у ) координатной плоскостиху.

Тем самым между произвольной точкой с координатами (х ,у ) и множеством троек чисел вида (hx ,hy ,h ) приh ≠ 0 устанавливается (взаимно однозначное) соответствие, позволяющее считать числаhx ,hy ,h новыми координатами этой точки.

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

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

1) точку с однородными координатами (0.5; 0.1; 2.5) h=1 нельзя представить целыми координатами, но, например, при выборе h= 10 получаем (5; 1; 25);

2) чтобы результаты преобразования не приводили к арифметическому переполнению, для точки с координатами

(80000;40000;1000) можно взять, например, h= 0,001. В ре-

зультате получим (80;40;1).

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

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

В самом деле, считая h = 1, сравним две записи: помеченную символом * и следующую, матричную:


{x y 1}= {x y 1}
{x y 1}= {x y 1}

Нетрудно заметить, что после перемножения выражений, стоящих в правой части последнего соотношения, мы получим обе формулы (1) и верное числовое равенство 1 ≡ 1. Тем самым сравниваемые записи можно считать равносильными.

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

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

Выпишем соответствующие матрицы третьего порядка.

А. Матрица вращения (rotation)		Б. Матрица растяжения
cosϕ	sinϕ	(сжатия) (dilatation)
	cosϕ
= − sinϕ	cosϕ





Г. Матрица переноса (translation)		В. Матрица отражения (re-


			− 1 0 .
			− 1 0 .

Рассмотрим примеры аффинных преобразований плоскости.

Пример 1. Построить матрицу поворота

вокруг точки А(a, b) на угол ϕ (рис. 5.5).

А (-а ,

совмещения центра

поворота

координат.

2-й шаг. Поворот на уголϕ .

A(a,

Рис. 5.5. Поворот

возвращения центра поворота в прежнее положение; матрица соответствующего преобразования.

cosϕ

sinϕ

= − sinϕ

cosϕ

−A

−a

−b

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

		sinϕ	sinϕ
{x y 1}= {x y 1}×		− sinϕ	cosϕ
{x y 1}= {x y 1}×		− sinϕ	cosϕ
	− a cosϕ + b sinϕ + a		− a sinϕ − b cosϕ + b

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

Пример 2. Построить матрицу растяжения с коэффициентами растяженияα вдоль оси абсцисс иβ вдоль оси ординат и с центром в точке А(а, b).

1-й шаг. Перенос на вектор А (-а , -b ) для совмещения центра растяжения с началом координат.

2-й шаг. Растяжение вдоль координатных осей с коэффициентамиα иβ соответственно.

3-й шаг. Перенос на векторА (а ,b ) для возвращения центра растяжения в прежнее положение; матрица соответствующего преобразования.

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

На рис.1: L"= б(L), A"=б(A), B"=б(B), C"=б(C), |

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

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

Пусть даны плоскости: w и w1 прямая l (направление проектирования), не параллельная ни одной из этих плоскостей (рис.2). Точка Аєw называется проекцией точки А1єw1, если АА1||l , то прямая АА1 называется проектирующей прямой. Параллельное проектирование представляет собой отображение плоскости w1 на w.

Отметим следующие свойства параллельного проектирования.

1) Образом всякой прямой а1 является прямая.

В самом деле, прямые, проектирующие точки прямой а1, образуют плоскость (она проходит через а1 параллельно l), которая при пересечении с w дает образ прямой а1 - прямую а(рис.2).

2) Отношение, в котором точка делит отрезок, сохраняется, т.е.

Сразу следует из теоремы о пересечении сторон угла параллельными прямыми.

Перейдем непосредственно к построению примера аффинного преобразования.

Возьмем два экземпляра плоскости w и один из них переместим в другое положение w1(рис.3). Новое положение какой-либо точки Аєw обозначим А1єw1. Теперь плоскость w1 спроектируем в каком-нибудь положении на w, проекцию точки А1 обозначим А".

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

3)Основная теорема. Каковы бы ни были 2 аффинных репера и, существует единственное аффинное преобразование, которое первый переводит во второй.

Существование. Рассмотрим преобразование а, которое произвольную точку А, имеющую в репере R координаты (х,у), переводит в точку А", имеющую в репере R" те же координаты (рис.4). Очевидно, что а(R)=R". Покажем, что а - аффинное преобразование.

Образом прямой l, имеющей в репере R уравнение ах+ву+с=0, будет линия l", которая в R" имеет то же самое уравнение. Значит, l"- прямая(рис.5). Следовательно, образом произвольной прямой является прямая.

Пусть теперь точка С(х,у) делит отрезок, соединяющий точки А(х1,у1), В(х2,у2) в отношении

А так как образы этих точек- А",В",С" имеют те же координаты(в другой системе), то и, следовательно,

Итак для преобразования б выполнены оба требования определения, значит б- аффинное преобразование.

Единственность доказательства от противного. Пусть существует два аффинных преобразования б1 и б2, при которых. Тогда найдется такая точка А, что, где (рис.6). Обозначим через К точку пересечения прямых ОА и Е1Е2(если эти прямые параллельны, то надо взять Е1А, ОЕ2, если и эти прямые параллельны, надо взять Е2А и ОЕ1). Так как, то образом точки К будет точка К"1-точка пересечения прямых. В силу определения аффинного преобразования:

Аналогично для преобразования б2.

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

Первое из этих равенств показывает, что точки К"1 и К"2 совпадают, а тогда из второго следует А"1=А"2, что противоречит А. Полученное противоречие доказывает теорему.

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

Доказанная основная теорема делает понятие аффинного преобразования конструктивным. Аффинное преобразование задается парой произвольных аффинных реперов.

4)Уравнения аффинного преобразования получаются из основной теоремы и формул преобразования аффинных координат точно так же, как и уравнения движения и подобия. Пусть даны два репера и (рис. 7).

получаются уравнения:

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

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

Определение. Преобразование плоскости называется аффинным (от англ. affinity – родство) , если

оно взаимно однозначно;
образом любой прямой является прямая.

Преобразование называется взаимно однозначным , если

разные точки переходят в разные;
в каждую точку переходит какая-то точка.

Свойства аффинного преобразования в трехмерном пространстве:

отображает n -мерный объект в n -мерный: точку в точку, линию в линию, поверхность в поверхность;
сохраняет параллельность линий и плоскостей;
сохраняет пропорции параллельных объектов – длин отрезков на параллельных прямых и площадей на параллельных плоскостях.

Любое аффинное преобразование задается матрицей 3x 3 с ненулевым определителем и вектором переноса:

Посмотрим на это с точки зрения математики. R представляет собой матрицу линейного оператора над пространством трехмерных векторов. Вектор T требуется для осуществления параллельного переноса: если помножить (000) на любую матрицу 3x 3, опять получим (000) – начало системы координат, относительно преобразования R , является неподвижно точкой. Требование, чтобы определитель был ненулевой, диктуется определением. По сути, если определитель матрицы R равен нулю, то всё пространство переходит в плоскость, прямую или точку. Тем самым не соблюдается взаимная однозначность .

На практике удобно задавать аффинное преобразование одной матрицей. При этом используются однородные координаты, введенные в предыдущей статье . Аффинное преобразование будет задаваться следующей матрицей 4x 4:

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

Рассмотрим частные случаи аффинных преобразований.

Прим. Здесь и в дальнейшем будет использоваться система координат, введенная следующим образом:

система координат правая;
ось z направлена на наблюдателя, перпендикулярно плоскости экрана;
ось y находится в плоскости экрана и направлена вверх;
ось x находится в плоскости экрана и направлена вправо.

Подробнее мы остановимся на этом при рассмотрении геометрического конвейера.

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

В данном случае матрица R = E , единичной матрице.

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

Поворот (вращение)

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

Прим. Поворот вокруг произвольного вектора не равно поворот вокруг произвольной направленной прямой.

Заметим, что при повороте вокруг оси y ординаты точек (у -координаты) не меняются. Также стоит отметить, что координаты x и z точки преобразуются независимо от y -координаты. Это означает, что любая точка p (x , y , z ) перейдет в точку p ’(x ’(x , z ), y , z ’(x , y )) . Теперь осталось понять, как преобразуются координаты x и z : в плоскости Oxz это будет поворот вокруг начала координат по часовой стрелке (т.к. x z y - левая тройка), т.е. в отрицательном направлении. Матрица такого преобразования известна (см. Поворот плоскости):

Матрица преобразования R y (φ y ) :

Поворот вокруг осей x и z

Аналогичными рассуждениями можно получить матрицы поворотов R x (φ x ) и R z (φ z ) вокруг осей x и z , соответственно.

Приведём окончательные результаты:

Несложно заметить, что определители матриц R x , R y , R z равны 1 . Также матрицы вращений R rot обладают свойством ортогональности: R T R = RR T = E . Из этого, в свою очередь, следует полезное свойство, что обращение матрицы поворота можно заменить транспонированием: R -1 (φ ) = R T (φ ) .

Масштабирование (сжатие/растяжение, отражение)

Коэффициенты сжатия/растяжения, по аналогии с двухмерным пространством, определяются диагональными членами матрицы R :

Результат:

Комбинация коэффициентов s x = -1, s y = 1, s z = 1 будет задавать отражение от плоскости Oyz (x = 0) . При s x = s y = s z = -1 получим центральную симметрию относительно начала координат.

Интерпретация матрицы R

Рассмотрим, что представляет собой матрица R с точки зрения линейной алгебры. Оказывается, что матрица R содержит базис новой системы координат.

Действительно, матрица

(R 11 R 12 R 13 )

(R 21 R 22 R 33 )

(R 31 R 32 R 33 )

переводит вектора декартова базиса:

(100) → (R 11 R 21 R 31 )

(010) → (R 12 R 22 R 32 )

(001) → (R 13 R 23 R 33 )

Теперь несложно получить преобразование скоса. Например:

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

Сложные аффинные преобразования

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

Как можно догадаться - с пространством всё тоже самое, что и с плоскостью. Все правила, которые касались АП в однородных координатах на плоскости, сохраняются и в пространстве, все проблемы, что были на плоскости, остаются и в пространстве. Можно предположить, что все эти правила действительны и для любого n-мерного пространства. Что надо хорошо помнить: есть разные понятия: радиус-вектор по сути – это точка в КГ, а свободный вектор – это просто направление, и третье понятие – нормаль. Преобразования для них определяют по-разному. В пространстве всё также, причём в пространстве это более актуально, т.к. в трёхмерной графике много задач, которые не часто или вообще не встречаются на плоскости.

Итак, в пространстве имеем три координаты x,y,z и дополнительно вводится координата W для получения свойства однородности. Также для АП принимаем, что W=1 и тогда (x, y, z) = ( , ).

Преобразования в общем случае можно представить в виде скалярного произведения вектора – строки на матрицу преобразования – слайд 29:

В матрице 12 коэффициентов. Блок (3х3) (как в 2D блок (2х2)) отвечает за преобразования - поворот, масштабирование… Нижняя строка отвечает за параллельный перенос, правый столбик должен отвечать за перспективные преобразования, но пока эти вопросы рассматривать не будем. Матрицы преобразования имеют аналогичный вид и смысл - (слайд 30)

и повороты - (слайд 31)

Если вспомнить пример поворота точки, то в пространстве выполнить это так же просто нельзя. Поворот, рассмотренный на плоскости, по существу был выполнен вокруг оси Z, и если надо выполнить поворот какой-то точки в пространстве, то его нельзя задать однозначно простым действием. Он будет описываться посредством трёх матриц – вокруг оси Z, оси Х, оси У, т.е. его надо будет разбить на ряд отдельных действий – на три составных.

Ещё одно замечание – определитель матрицы равен 1. Это означает, что в процессе поворота объект не поменяет своих размеров и не претерпеет какой-либо деформации, т.е. ведёт себя как твёрдое тело. Этому телу можно задавать необходимую ориентацию в пространстве. Тоже можно сказать и о параллельном переносе.

Имеется более универсальный способ осуществления поворота относительно произвольной оси, проходящей через начало координат. Матрица такого преобразования построена на КВАТЕРНИОНАХ и приведена ниже:

С кватернионами следует познакомиться самостоятельно!

Замечание о кватернионах.

При выводе последнего соотношения использовалось понятие о кватернионах. Это система гиперкомплексных чисел (предложена в 1843 г. Гамильтоном, в то время - гл. астрономом Англии).

Кватернион – это пара (а, ū ). а - скаляр, вещественное число. ū - вектор трёхмерного пространства. Кватернионы образуют систему (ряд) гиперкомплексных чисел, подобную другим числовым рядам. Если коротко – то это 4-х компонентная математическая абстракция со своими свойствами и правилами выполнения операций сложения и умножения. Кватернион в общем виде можно представить как сумму a+bi+cj+dk, где a,b,c,d – вещественные числа, а i,j,k – несократимые мнимые единицы, причём для них определено, что

i 2 =j 2 =k 2 =ijk= -1;

Примеры числовых рядов:

Натуральные: 1,2,3,4,5….

Целые: 0,1,-1,2,-2,…

Рациональные: 1;-1;1/2; 0,12,..

Вещественные: рациональные + ирац.: π, е, ,….

Комплексные: -1; ½; π; 3i+z; -еiπ/3;… (включают в себя все предшедствующие)

Кватернионы: 1; -1; 1/2; I; j; k; πj-1/2k; …

9. Пример трёхмерного преобразования – построение матрицы камеры - (слайд 34)

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

Считаем, что виртуальный наблюдатель (камера) находится в некоторой точке “C” в ортогональной системе координат U,V,N

и есть другая система координат – X,Y,Z (мировая). Мировые координаты описывают истинное положение объектов в пространстве. Экранная система координат предназначена для синтеза (создания) изображения на к.-л. плоскость. Эта система может быть двумерной и трёхмерной. Различают так же другие системы координат как системы устройств изображения, осуществляющие вывод изображения в заданной форме.

Проекция - способ отображения объекта на графическом устройстве: экране, бумажном, тканном или другом материальном носителе на плоскости или поверхности.

Будем считать, что обе системы координат правосторонние, и та, что в камере и мировая. Это означает, что ось Z смотрит на нас. Все векторы направлений нормированы и, что естественно, ортогональны. Это требуется для сокращения набора вычислений. Камеру С должно рассматривать как некоторую одноразовую, однократно задаваемую в программе абстракцию. Её можно заранее настроить, а затем применить ко всем объектам.

Что значит настроить? Настроить – это значит ортонормировать все векторы и согласовать их с векторами – направлениями в другой СК. А дальше применять так долго, как это потребует обстановка.

Что будем искать? Будем искать такое преобразование, которое переводит объект из мировой системы координат в систему координат наблюдателя.

Как будем делать?

Сначала перенесём камеру в начало координат Мировой СК на (- C z), (- C y), (- C x); затем повернём, причем таким образом, что бы оси -U совпала с осью X, V совпала с осью Y и ось N c осью Z; т.е. будем искать матрицу преобразования в виде: перенос-поворот.

Поскольку камера находится в позиции точка “C” с координатами (x,y,z), то необходимо выполнить обратный её перенос: матрица переноса показана на слайде 33.