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

Введение

. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. 3

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

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

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

Заключение

. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .23

Список литературы

. .. .. .. .. .. .. .. .. .. .. .. .. 24

1. Введение

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

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

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

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

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

В компьютерной графике все, что относится к двумерному случаю принято обозначать символом (2D) (2-dimention).

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

Рис. 1

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

x^* = ?x + ?y +???

y^* = ?x + ?y + ???

где ??? — произвольные числа, связанные неравенством:

???

???

??? (2.3)

???

Формулы (2.1) и (2.2) можно рассматривать двояко: либо сохраняется точка и изменяется координатная система (рис. 2) — в этом случае произвольная точка М остается той же, изменяются лишь ее координаты (х, у) | (х^*, y^*), либо изменяется точка и сохраняется координатная система (рис. 3) — в этом случае формулы (2.1) и (2.2) задают отображение, переводящее произвольную точку М (х, у) в точку М* (х*, у*), координаты которой определены в той же координатной системе.

X*

Y*

Рис. 2

Рис. 3

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

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

Поворот вокруг начальной точки на угол ??(рис. 4) описывается формулами:

х* = x cos??? y sin???

y* = x sin??? y cos???

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

x* = ?x, (2.5)

y* = ?y, (2.6)

???

Растяжение (сжатие) вдоль оси абсцисс обеспечивается при условии, что??? На рис. 5 ???

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

x* = x, (2.8)

y* = -y. (2.9)

На рис. 7 вектор переноса ММ* имеет координаты … Перенос обеспечивает соотношения:

x* = x + ???

???y* = y + ???

Рис. 4

Рис. 5

Рис. 6

Рис. 7

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

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

Как известно из курса аналитической геометрии, любое преобразование вида (2.1) всегда можно представить как последовательное исполнение (суперпозицию) простейших преобразований вида 1 — 4 (или части этих преобразований).

Таким образом, справедливо следующее важное свойство аффинных преобразований плоскости: любое отображение вида (2.1) можно описать при помощи отображений, задаваемых формулами (2.3) — (2.11).

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

cos ???sin ???

— sin??? cos ???

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

Пусть М — произвольная точка плоскости с координатами х и у, вычисленными относительно заданной прямолинейной координатной системы. Однородными координатами этой точки называется любая тройка одновременно не равных нулю чисел х₁, х₂, х₃, связанных с заданными числами х и у следующими соотношениями:

x₁ / x₃ = x, x₂ / x₃ = y (3.1)

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

Необходимо заметить, что произвольная точка на прямой, соединяющей начало координат, точку О (0, 0, 0), с точкой М_Э (х, у, 1), может быть задана тройкой чисел вида (hx, hy, h).

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

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

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

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

х: у: 1 (3.2)

или, более общо,

х₁: х₂: х₃ (3.3)

(здесь непременно требуется, чтобы числа х₁, х₂, х₃ одновременно в нуль не обращались).

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

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

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

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

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

Считая, h = 1, сравним две записи:

???

(x * y * 1) = (x y 1) ??? ???

???

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

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

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

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

А. Матрица вращения (rotation)

cos ???sin ???

[ R ] = -sin ???cos ???

???

Б. Матрица растяжения-сжатия (dilatation)

???

???D ] = ???

???

В. Матрица отражения (reflection)

1 0 0

[ M ] = 0 -1 0 (3.7)

0 0 1

Г. Матрица переноса (translation)

1 0 0

[ T ] = 0 1 0 (3.8)

???

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

Пример 1. Построить матрицу поворота вокруг точки, А (a, b) на угол? (рис. 9).

Рис. 8

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

1 0 0

[ T_-A ] = 0 1 0 (3.9)

— ab 1

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

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

cos ???sin ???

[ R_? ] = -sin ???cos ???(3.10)

0 0 1

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

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

1 0 0

[ T_A ] = 0 1 0 (3.11)

a b 1

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

Перемножим матрицы в том же порядке, как они выписаны:

[ T_-A ] [ R_? ] [ T_A ].

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

cos? sin ???0

(x* y* 1) = (x y 1) -sin ???cos ???0 (3.12)???

— a cos ??+ b sin ??? aa sin ??- b cos? + b 1

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

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

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

1 0 0

[ T_-A ] = 0 1 0 (3.13)

— ab 1

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

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

???

???D ] = ???

???

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

1 0 0

[ T_A ] = 0 1 0 (3.15)

a b 1

Премножив матрицы в том же порядке

[ T_-A ] [ D ] [ T_A ],

получим окончательно

???0 0

(x* y* 1) = (x y 1) 0? 0 (3.16)

(1 — ?)a (1 — ?)b 1

Рассуждая подобным образом, то есть разбивая предложенное преобразование на этапы, поддерживаемые матрицами [ R ], [ D ], [ M ], [ T ], можно построить матрицу любого аффинного преобразования по его геометрическому описанию.

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

Рассмотрим трехмерный случай (3D) (3-dimension) и сразу введем однородные координаты.

Поступая аналогично тому, как это было сделано в размерности два, заменим координатную тройку (x, y, z), задающую точку в пространстве, на четверку чисел

(x y z 1)

или, более общо, на четверку

(hx hy hz), h = 0.

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

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

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

А. Матрицы вращения в пространстве.

Матрица вращения вокруг оси абсцисс на угол ?:

1 0 0 0

cos ???sin ???0

0 -sin ???cos? 0

0 0 0 1

Матрица вращения вокруг оси ординат на угол ??

cos? 0 -sin? 0

0 1???

sin? 0??? cos? 0

0 0 0 1

Матрица вращения вокруг оси аппикат на угол ?:

cos? sin? 0 0

— sin??? cos ???0 0

0 0??? 0

0 0 0 1

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

Б. Матрица растяжения-сжатия:

???

???

???

???

где

? > 0 — коэффицент растяжения (сжатия) вдоль оси абсцисс;

??> 0 — коэффицент растяжения (сжатия) вдоль оси ординат;

??> 0 — коэффицент растяжения (сжатия) вдоль оси аппликат.

В. Матрицы отражения Матрица отражения относительно плоскости ху:

???

???

???

???

Матрица отражения относительно плоскости yz:

???

???

???

???

Матрица отражения относительно плоскости zx:

???

???

???

???

Г. Матрица переноса (здесь (???вектор переноса):

???

???

???

???

Как и в двумерном случае, все выписанные матрицы невырождены.

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

Пример 3. Построить матрицу вращения на угол? вокруг прямой L, проходящей через точку, А (a, b, c) и имеющую направляющий вектор (l, m, n). Можно считать, что направляющий вектор прямой является единичным:

l² + m² + n² = 1

На рис. 10 схематично показано, матрицу какого преобразования требуется найти.

L

X

Рис. 10

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

1-й шаг. Перенос на векторА (-a, -b, -c) при помощи матрицы

???

???

???

— ab -c 1

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

2-й шаг. Совмещение оси аппликат-с прямой L двумя поворотами вокруг оси абсцисс и оси ординат.

1-й поворот — вокруг оси абсцисс на угол ??(подлежащий определению). Чтобы найти этот угол, рассмотрим ортогональную проекцию L' исходной прямой L на плоскость X = 0 (рис. 11).

L' L ?

Y

Рис. 11

Направляющий вектор прямой L' определяется просто — он равен

(0, m, n).

Отсюда сразу же вытекает, что

cos ???n / d, sin ??= m / d, (4.10)

где

d = m² + n² (4.11)

Соответствующая матрица вращения имеет следующий вид:

1 0 0 0

0 n/d m/d 0

0 -m/d n/d 0

0 0 0 1

Под действием преобразования, описываемого этой матрицей, координаты вектора (l, m, n) изменятся. Подсчитав их, в результате получим

(l, m, n, 1)[ R_x ] = (l, 0, d, 1). (4.13)

2-й поворот вокруг оси оси ординат на угол ?, определяемый соотношениями

сos? = l, sin? = -d (4.14)

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

l???d???

???

— d??? l???

???

3-й шаг. Вращение вокруг прямой L на заданный угол ??

Так ка теперь прямая L совпадает с осью аппликат, то соответствующая матрица имеет следующий вид:

cos? sin? 0 0

— sin??? cos ???0 0

0 0??? 0

0 0 0 1

4-й шаг. Поворот вокруг оси ординат на угол -??

5-й шаг. Поворот вокруг оси абсцисс на угол -??

Однако вращение в пространстве некоммутативно. Поэтому порядок, в котором проводятся вращения, является весьма существенным.

6-й шаг. Перенос на вектор, А (a, b, c).

Перемножив найденные матрицы в порядке их построения, получим следующую матрицу:

[ T ][ R_x ][ R_y ][ R_z ][ R_y ]^-1[ R_x ]^-1 [ T ]^-1.

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

l² + cos ?(1 — l²) l (1 — cos?? m + n sin??? l (1 — cos ?)n — m sin ?? 0

l (1 — cos?? m — n sin??? m² + cos ??1 — m²) m (1 — cos?? n + lsin ???0

l (1 — cos?? n + m sin??? m (1 — cos?? n — lsin??? n² + cos ???- n²) 0

0 0 0 1

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

?_????_????_????

?_????_????_????

?_????_????_????

???

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

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

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

V_i (x_i, y_i, z_i), i = 1,…, n,

Строим матрицу

x₁ y₁ z₁ 1

V =. .. .. .. ... (4.18)

x_n y_n z_n 1

Подвергая этот набор преобразованию, описываемому найденной невырожденной матрицей четвертого порядка, [ V ][ A ], мы получаем набор вершин нового выпуклого многогранника — образа исходного (рис. 12).

Z

Y

X

Рис. 11

5. Заключение

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

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

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

6. Список используемой литературы.

Шишкин Е. В., Боресков А. В. Компьютерная графика. М.: Диалог-МИФИ, 1995. — 288 с., ил.

2. Вайсберг А. В., Гриценко М. Е. Формирование структуры станка на ранних стадиях проектирования. — Точность автоматизированных производств (ТАП — 97). Сборник статей международной научно-технической конференции. Пенза, 1997., с. 52 — 53.