Координаты и преобразования

Лекция №2.

Координаты и преобразования

· двумерные (2D) преобразования, · 2D преобразования в однородных координатах, · композиция 2D преобразований, · 3D координаты, · проекции, · стереоизображения, · преобразования растровых картин.

Всюду далее: X,Y,Z - декартовые координаты, x,y,z - однородные координаты,

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

1. Сдвиг:

Скалярная форма

Xn = X + Tx,

Yn = Y + Ty.

Векторная форма

[Pn\vec] = [P\vec] + [T\vec].

где [Pn\vec] = [Xn, Yn],    [P\vec] = [X, Y],     [T\vec] = [Tx, Ty].

2. Масштабирование относительно начала координат:

Скалярная форма

Xn = X · Sx,

Yn = Y · Sy.

Матричная форма
[Pn\vec] = [P\vec] ·S,
[Xn, Yn] = [X, Y] ·[	Sx  0 0  Sy	]

где S = [

Sx	0
0	Sy

] - матрица масштабирования.

3. Поворот относительно начала координат:

Скалярная форма

Xn = X ·cosf- Y ·sinf,

Yn = X ·sinf+ Y ·cosf,

Матричная форма

[Pn\vec] = [P\vec] ·R.

где f - угол поворота,

R = [

cosf	sinf
-sinf	cosf

] = [

R11	R12
R21	R22

] -

матрица

поворота,

Столбцы и строки матрицы поворота - взаимно перпендикулярные единичные векторы,
Т.е. квадраты длин векторов строк и столбцов = 1:

R112+R122 = 1 =	cosf·cosf	+	sinf·sinf,
R212+R222 = 1 =	(-sinf)·(-sinf)	+	cosf·cosf,
R112+R212 = 1 =	cosf·cosf	+	(-sinf)·(-sinf),
R122+R322 = 1 =	sinf·sinf	+	cosf·cosf,

а их скалярное произведение = 0:

R11·R21+R12·R22 = 0 = cosf·(-sinf) + sinf·cosf,

R11·R12+R21·R22 = 0 = cosf·sinf+ (-sinf) ·cosf.

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

[ cosf -sinf ]	·	[  cosf sinf -sinf cosf ]	=	1 0 ,    вдоль    X
sinf cosf	·	cosf sinf -sinf cosf	=	0 1 ,    вдоль    Y.

Это позволяет сформировать матрицу преобразования, если известны его результаты.

2D преобразования в однородных координатах

Формирование суммарного 2D преобразования затруднено, т.к. различные преобразования имеют различные виды. Для устранения затруднений вводятся 2D однородные координаты:

[ x y w ];    w 0  и  произвольно  X = x/w;  Y = y/w.

Однородные координаты можно представить как декартовые, промасштабированные коэффициентом w, расположенные в плоскости с Z = w.

Все 2D преобразования в однородных координатах имеют одинаковую форму.

[ xn yn wn	] = [	x y w	]·			1 0 0 0 1 0 Tx Ty 1
сдвиг

[ xn yn wn	] = [	x y w	]·			Sx 0 0 0 Sy 0 0 0 1
масштаби-
рование.

[ xn yn wn	] = [	x y w	]·			cosf sinf 0 -sinf cosf 0 0 0 1
поворот

Видно, что wn = w, а матрица преобразования для двумерных однородных координат имеет вид:

A	B	P
D	E	Q
L	M	S

,

A	B
D	E

определяет мас-

штабирование, по-

ворот, смещение

[L  M] определяет сдвиг, S определяет общий масштаб,
[

P

Q

] определяет проецирование,

Для уяснения смысла элемента S рассмотрим

x y 1 · 1 0 0 0 1 0 0 0 S = x y S

Таким образом двумерные декартовые координаты преобразованной точки

X = x / S, Y = y / S,

т.е. это преобразование задает изменение масштаба.

Для уяснения смысла вектора [P  Q] выполним преобразование

x y 1 · 1 0 P 0 1 Q 0 0 1 = x y (Px+Qy+1) = xn yn h ,

h - переменная, определяющая положение плоскости с преобразованной точкой, из 1 преобразовалась в уравнение 3D плоскости:

h = Px + Qy + 1.

Двумерные декартовые координаты Xn, Yn для преобразованной точки

Xn = x Px+Qy+1 , Yn = y Px+Qy+1 .

Это соответствует вычислению их в плоскости Z = 1, т.е. проецированию из плоскости Px + Qy + 1 в плоскость Z = 1.

Покажем, что центр проецирования находится в начале координат.

Рассмотрим для этого параметрические уравнения прямой, проходящей через точки (Xn, Yn, 1) и(x, y, (Px+Qy+1) ):

X(t) = Xn + (x-Xn) ·t = x/h + (x-x/h)·t, Y(t) = Yn + (y-Yn) ·t = y/h + (y-y/h)·t, Z(t) = 1 + (Px+Qy)·t = 1 + (h-1).

Полагая X(t) = 0, получим t = 1/(1-h). Подставляя это значение в выражения для Y(t) и Z(t), получим:

Y(t) = y/h + (y - y/h)/(1-h) = y/h - y/h = 0.

Z(t) = 1 + (h-1)/(1-h) = 0.

Т.е. показано, что вектор [P  Q] определяют проецирование с центром проекции в начале координат.

Декартовые точки с бесконечными координатами

Пусть имеем линию, проходящую через декартовую точку (X,Y).

Ее однородные координаты - (x,y,h) = (Xh,Yh,h).

При h ® 0    lim(x/y) = X/Y,    но    x ® ,    y ® , т.е. (x,y,0) задает в декартовой системе координат точку на для рассмотренной прямой.

Параллельные прямые

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

Пусть две пересекающиеся прямые в декартовой системе координат заданы системой уравнений:

A1 ·X + B1 ·Y + C1 = 0 A2 ·X + B2 ·Y + C2 = 0

Решая эту систему относительно X и Y, найдем координаты точки пересечения

X0	=	(C1·B2	-	C2·B1) / D,
Y0	=	(A1·C2	-	A2·C1) / D,
D	=	A1·B2	-	A2·B1.

Запишем результат в однородных координатах

C1 ·B2-C2 ·B1 D ,  A1 ·C2-A2 ·C1 D ,  1 .

В силу произвольности масштабного множителя, умножим значения координат на D

(C1 ·B2-C2 ·B1,    A1 ·C2-A2 ·C1,    D).

Если прямые параллельны, то определитель системы - D равен нулю. Учитывая это и обозначая x0 = (C1 ·B2-C2 ·B1), y0 = (A1 ·C2-A2 ·C1), получим координату пересечения параллельных прямых в однородной системе координат

( x0, y0, 0 ).

При этом точка пересечения лежит на на прямой:

-y0 ·x + x0 ·y = 0

Композиция двумерных преобразований

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

Последовательное выполнение сдвигов

Сдвинем точку P1 на расстояние (Tx1, Ty1) в точку P2:

P2 = P1 ·T1.

Затем сдвинем точку P2 на расстояние (Tx2, Ty2) в точку P3:

P3 = P2 ·T2 = (P1·T1)·T2) = P1·(T1·T2) = P1·T.

Сдвиг аддитивен, т.е. последовательное выполнение T1 и T2 д.б. эквивалентно одному сдвигу на расстояние (Tx1+Tx2, Ty1+Ty2).

Для доказательства этого рассмотрим произведение матриц сдвига T1 и T2, равное

T = 1 0 0 0 1 0 Tx1 Ty1 1 · 1 0 0 0 1 0 Tx2 Ty2 1 =

1 0 0 0 1 0 Tx1+Tx2 Ty1+Ty2 1 .

Итак, получили, что результирующий сдвиг есть (Tx1+Tx2, Ty1+Ty2), т.е. суммарный сдвиг, вычисленный как произведение матриц, как и ожидалось, аддитивен.

Последовательное выполнение масштабирований

Первое масштабирование с коэффициентами (Sx1, Sy1), второе с коэффициентами (Sx2, Sy2).

Следует ожидать, что суммарное масштабирование будет мультипликативным. Обозначая через S1 и S2 матрицы масштабирования, получим:

P1 = P0 ·S1,   P2 = P1 ·S2   =  (P0 ·S1) ·S2   =   P0 ·(S1 ·S2) = P0 ·S.

Найдем значения элементов матрицы S

S = Sx1 0 0 0 Sy1 0 0 0 1 · Sx2 0 0 0 Sy2 0 0 0 1 = Sx1 ·Sx2 0 0 0 Sy1 ·Sy2 0 0 0 1 .

Итак, получили, что результирующее масштабирование мультипликативно.

Последовательное выполнение поворотов

Можно показать, что два последовательных поворота аддитивны.

Поворот на угол f относительно заданной точки P(X,Y)

1. Перенос начала координат в точку P(X,Y).
2. Поворот на угол f вокруг начала координат.
3. Обратный перенос начала координат:

Pn = P ·T(-X,-Y) ·R(f) ·T(X,Y).

В матричной записи:

1 0 0 0 1 0 -X -Y 1 · cosf sinf 0 -sinf cosf 0 0 0 1 · 1 0 0 0 1 0 X Y 1 .

Эффективность преобразований

Двумерное преобразование в однородных координатах имеет вид:

Pn (xn, yn, wn) = P·T = [x, y, w ]· A B 0 D E 0 L M 1 .

где [

A	B
D	E

] -

объединенная матрица

масштабирования и поворота,

а [ L    M ] - вектор сдвига.

Непосредственное использованием выражения P ·T требует 9 операций умножения и 6 операций сложения.

Но так как значение w может быть выбрано равным 1, а третий столбец T содержит единственный ненулевой элемент, равный 1, то экономное преобразование может быть представлено в виде:

Xn = X ·A + Y ·D + L, Yn = X ·B + Y ·E + M,

что требует уже только 4 операции умножения и 4 операции сложения.

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

Матрицы же 33 удобны при вычислении суммарного преобразования.

Трехмерные координаты

Правая и левая системы координат

Система координат называется правой, если для совмещения с положительной полуосью Y положительную полуось X требуется повернуть на +90° при этом направление движения расположенного вдоль оси Z и поворачивающегося против часовой стрелки правого винта и положительной полуоси Z совпадают.

В однородных координатах точка представляется четырехмерным вектором [ x y z w ], где w 0, а матрицы преобразований имеют размер 44.

Переход от однородных к декартовым координатам:

X  Y  Z  1  ] = [   x w    y w    z w   1   .

Преобразование в однородных координатах:

[ xn yn zn wn  ] = [ x y z w ] ·T.

Матрица преобразования T имеет вид:

[ A B C P D E F Q I J K R L M N S ],

Подматрица 33 определяет суммарные смещение, масштабирование и поворот. Вектор [ L M N ] задает сдвиг. Вектор [ P Q R ] отвечает за преобразование в перспективе. Скалярный элемент S определяет общее изменение масштаба.

Матрица сдвига имеет вид:

T(Tx, Ty, Tz) = 1 0 0 0 0 1 0 0 0 0 1 0 Tx Ty Tz 1 .

Матрица обратного преобразования для сдвига получается путем смены знака у Tx, Ty и Tz.

Матрица масштабирования относительно центра координат имеет вид:

S(Sx, Sy, Sz) = Sx 0 0 0 0 Sy 0 0 0 0 Sz 0 0 0 0 1 .

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

Поворот вокруг оси Z (в плоскости XY)

Размеры вдоль оси Z неизменны, поэтому все элементы 3-й строки и 3-го столбца равны 0, кроме диагонального, равного 1:

Rz(fz) = cosfz sinfz 0 0 -sinfz cosfz 0 0 0 0 1 0 0 0 0 1 .

Поворот вокруг оси X (в плоскости YZ)

Размеры вдоль оси X не меняются, поэтому все элементы 1-й строки и 1-го столбца равны 0, за исключением диагонального, равного 1:

Rx(fx) = 1 0 0 0 0 cosfx sinfx 0 0 -sinfx cosfx 0 0 0 0 1 .

Поворот вокруг оси Y (в плоскости XZ)

Размеры вдоль оси Y не меняются, поэтому все элементы 2-й строки и 2-го столбца равны 0, за исключением диагонального, равного 1:

Ry(fy) = cosfy 0 -sinfy 0 0 1 0 0 sinfy 0 cosfy 0 0 0 0 1 .

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

Суммарная матрица преобразования для произвольной последовательности поворотов вокруг осей X, Y и Z имеет вид:

R = r1x r1y r1z 0 r2x r2y r2z 0 r3x r3y r3z 0 0 0 0 1

Векторы-столбцы при повороте, задаваемом матрицей, совмещаются с соответствующими осями координат.

Матрица, столбцы (или строки) которой представляют собой взаимно ортогональные векторы, называется ортогональной.

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

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

Формирование матрицы преобразования

Пусть заданы три точки P1, P2, P3. Найти матрицу преобразования такого, что после преобразования вектор [(P1)\vec][(P2)\vec] будет направлен вдоль оси Z, а вектор [(P1)\vec][(P3)\vec] будет лежать в плоскости YZ.

1. Вначале надо сместить начало координат в точку [(P1)\vec] с помощью преобразования

T(-x1, -y1, -z1).

1. Единичный вектор, который должен лечь вдоль оси Z

® Rz   = [r1z  r2z  r3z] = ® P1   ® P2   / | ® P1   ® P2   |.

1. Здесь |[(P1)\vec][(P2)\vec]| - длина вектора [(P1)\vec][(P2)\vec].
2. Вектор, перпендикулярный плоскости, построенной на векторах [(P1)\vec][(P2)\vec] и [(P1)\vec][(P3)\vec], должен быть направлен вдоль оси X, так как вектор [(P1)\vec][(P2)\vec] лежит вдоль оси Z, а вектор [(P1)\vec][(P3)\vec] лежит в плоскости YZ. Этот вектор задается векторным произведением

® Rx   = [r1x  r2x  r3x] = ® P1   ® P2   ® P1   ® P3   | ® P1   ® P2   | ·| ® P1   ® P3   | .

1. Наконец, вдоль оси Y должен быть направлен вектор, перпендикулярный к векторам [(Rx)\vec]  и   [(Rz)\vec]:

® Ry   = [ r1y r2y r3y  ] = ® Rz   ® Rx   .

1. Искомая матрица есть

M = T(-x1,-y1,-z1) · r1x r1y r1z 0 r2x r2y r2z 0 r3x r3y r3z 0 0 0 0 1 .

Проецирование

· представление объекта на плоскости отображения
(в терминах графики - визуализация объекта)

Визуализация двумерных изображений

Визуализация трехмерных изображений

Классификация плоских проекций

• проецирование - отображение точек, заданных в системе координат с размерностью N, в точки в системе меньшей размерности;
• проекторы (проецирующие лучи) - отрезки прямых, идущие из центра проекции через каждую точку объекта до пересечения с плоскостью проекции (картинной плоскостью);
• параллельная проекция - центр проекции на бесконечности от плоскости проекции:
  • ортогональные,
  • прямоугольные аксонометрические - проекторы ^ к плоскости проекции, расположенной под углом к главной оси,
  • косоугольные аксонометрические - плоскость проекции ^ к главной оси, проекторы расположены под углом к плоскости проекции;
• центральная проекция - центр проекции на конечном расстоянии от плоскости проекции. Имеют место т.н. перспективные искажения.

Ортогональные проекции (основные виды)

1. Вид спереди, главный вид, фронтальная проекция, (на заднюю грань V),
2. Вид сверху, план, горизонтальная проекция, (на нижнюю грань H),
3. Вид слева, профильная проекция, (на правую грань W),
4. Вид справа (на левую грань),
5. Вид снизу (на верхнюю грань),
6. Вид сзади (на переднюю грань).

Аксонометрическая прямоугольная изометрическая проекция

Аксонометрическая прямоугольная диметрическая проекция

Аксонометрическая косоугольная фронтальная диметрическая проекция (проекция кабине)

Аксонометрическая косоугольная горизонтальная изометрическая проекция (военная перспектива)

Матрицы преобразования для параллельных проекций

Ортогональное проецирование - на плоскость, перпендикулярную какой-либо оси, т.е. проецирование вдоль этой оси. В частности, проецирование в XY-плоскость, заданную соотношением Z = Z0, обеспечивается матрицей:

xn yn zn wn = x y z 1 · 1 0 0 0 0 1 0 0 0 0 0 0 0 0 Z0 1 .

Косоугольное проецирование - на плоскость, перпендикулярную главной оси, проекторы составляют с плоскостью проецирования угол не равный 90°.

Косоугольная параллельная проекция P1(L·cosa, L·sina, 0) точки P0(0,0,1)

Проектором, параллельным P0P1 спроецируем некоторую точку (X,Y,Z) в точку (Xp,Yp,Zp).

Из подобия треугольников получаем:
(Xp-X)/Z = L·cosa    
Xp = X + Z·L·cosa

(Yp-Y)/Z = L·sina    
Yp = Y + Z·L·sina

Этому соответствует матричное выражение:

xp yp zp 1 = x y z 1 · 1 1 0 0 0 0 0 0 L·cosa L·sina 1 0 0 0 0 1 .

Центральная проекция

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

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

Центральная проекция точки P0 в плоскость Z = d

Соотношения для координат точки P1, полученной проецированием точки P0(X,Y,Z) в плоскость Z = d:

X1 d = X Z , X1 d = X Z , X1 = X Z/d , Y1 = Y Z/d .

Или, в матричном виде:

x1 y1 z1 w1 = x y z 1 · 1 1 0 0 0 0 0 0 0 0 1 1/d 0 0 0 0 =

x y z 1 ·Mц = x y z z/d .

Переходя к декартовым координатам, получаем:

X (Z/d)      Y (Z/d)     d     1      .

Если же точка просмотра расположена в плоскости проекции, тогда центр проекции расположен в точке (0, 0, -d).

Аналогично рассмотренному выше, получаем:

X1 = X Z/d + 1 ; Y1 = Y Z/d + 1 .

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

M0 = 1 0 0 0 0 1 0 0 0 0 0 1/d 0 0 0 1 .

Матрица M0 может быть представлена в виде:

M0      =     T(0, 0, d) ·Mц ·T (0, 0, -d),

т.е. перенос начала координат в центр проецирования, собственно проецирование и обратный сдвиг начала координат.

Стереоизображения

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

Для разделения динамических видов на экране дисплея могут использоваться:

· цветовое разделение;

· пространственное-временное разделение на дисплеях с чересстрочной разверткой;

· временное разделение на дисплеях с двойным кадровым буфером.

Матрицы преобразований для получения стереопроекций - матрицы перспективных проекций.

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

· преобразования сдвига,
· преобразования масштабирования,
· преобразования поворота.

Преобразование сдвига - переписывание части изображения (bitblt-операции - Bit Block Transfer). Сдвиг может сопровождаться исполнением операция над кодами пикселов. Наиболее употребимыми являются:

· замена - новый пиксел просто заменяет старый,

· исключающее ИЛИ - в видеопамять заносится результат операции XOR над старым и новым кодами пикселов.

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

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

· целочисленное - zoom,

· произвольное, когда коэффициент масштабирования не обязательно целое число, - transfocation.

Нецелочисленное уменьшение

#define Max 13 // размер исходного массива

#define Min 7 // размер результирующего массива

int ist; // целая часть приращения индекса большего

// массива при смещении на 1 по меньшему

float rst; // дроб. часть приращения индекса большего

// массива при смещении на 1 по меньшему

int iwr; // индекс записи

int ird; // целая часть индекса чтения

float rrd; // дробная часть индекса чтения

char isx[Max]; // исходный массив пикселов

char rez[Min]; // результирующий массив пикселов

void main (void) {

ist= (int)(Max / Min);

rst= (float)(Max - ist*Min)/(float)Min;

ird= 0; rrd= 0.0;

for (iwr=0; iwr < Min; iwr++) {

ird= ird + ist; // накопление целой части индекса

rrd= rrd + rst; // накопление дроб. части индекса

if (rrd >= 1.0) {rrd= rrd - 1.0; ird= ird + 1; }

rez[iwr]= rez[ird-1];

}

}

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

Проблемы возникают при повороте растровой картины на угол не кратный 90°. Здесь возможны два подхода:

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

Координаты и преобразования