Конспект 2-3 (Конспект лекций)

ГЕОМЕТРИЯ И ДИНАМИКА ИЗОБРАЖЕНИЙ

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

В компьютерной графике все, что относится к двумерному изображению, обозначается символами 2D (2-direction). Каждой точке на плоскости ставится в соответствие пара чисел – ее координаты M(x,y). Преобразование координат можно трактовать двояко:

а) либо перемещается точка в неизменной системе координат (см. рис.14),

M(x,y) M^*(x^*,y^*)

б) либо сохраняется точка, а изменяется координатная система (см. рис.15)

(x,y) (x^*,y^*)

В
дальнейшем мы будем рассматривать вариант, представленный на рис.14.

Существуют 4 простейших преобразования координат на плоскости:

1. параллельный перенос (см. рис.14)

новые координаты вычисляются по формулам

x^* = x +a

y^* = y + b

используется также матричная запись:

x^* = x + a

y^* y b

1. вращение (см. рис.16)

поворот на заданный угол  >0 вокруг начальной точки О против часовой стрелки описывается формулами

x^* = x  cos  - y  sin 

y^* = x  sin  + y  cos 

или в матричной записи

x^*  = cos  -sin  x

y^*  sin  cos  y y

1. Зеркальное отражение (см. рис.16)

в озможно относительно оси х (абсцисс) M^b y M

x^*a = x x^*  = 1 0 x

y ^*a = -y y^*  0 -1 y -x x

и ли относительно оси y (ординат) -y

x^*b = x x^*  = -1 0 x

y^*b = -y y^*  0 1 y Рис. 16

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

x^* = x x^*  =  0 x

y^* = y y^*  0  y

При этом, если  и >1, то имеем растяжение вдоль осей (см. рис.17а), а если, например, <1, то – сжатие вдоль соответствующей оси (см. рис.17б).

Заметим, что обратные преобразования описываются матрицами того же вида. Например,

• обратный поворот (на угол - ) описывается матрицей

cos (-) -sin (-) = cos  -sin 

sin (-) cos (-) sin  cos 

• сжатие описывается матрицей

1/ 0 

0 1/

• и т.д.

В общем виде преобразование координат на плоскости можно описать формулами, называемыми аффинным преобразованием на плоскости:

x^* = x + y + a

y^* = x + y + b

т.е. при    ;     - получим формулы параллельного переноса,

при     cos ; - =  = sin ; a = b = 0 – формулы поворота,

при   1,   -1;  =  = a = b = 0 – формулы отражения

относительно оси абсцисс,

а при  =  = a = b = 0 – формулы растяжения (сжатия).

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

Для удобства описания преобразований введено обозначение точки на плоскости упорядоченным набором трех чисел, т.е. координатами в псевдопространстве. Такая тройка чисел называется однородными координатами точки. Таким образом, точке M(x,y) ставится в соответствие вектор-столбец вида

x

y 

1

Тогда основные преобразования (например, поворот) описываются формулами вида

x^* cos  -sin  0 x

y ^*= sin  cos  0  y 

1   0 0 1 1

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

 cos  sin  0

( x^*,y ^*,1) = ( x,y,1) -sin  cos  0 

 0 0 1

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

• матрица поворота Rotation

cos  -sin  0

 R   sin  cos  0 

 0 0 1

• матрица растяжения (сжатия) Dilatation

  0 0

 D    0  0 

 0 0 1

• матрица отражения относительно оси абсцисс (Reflection)

 1 0 0

 M    0 -1 0 

 0 0 1

• матрица параллельного переноса (Translation)

 1 0 a

 T    0 1 b 

 0 0 1

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

Пример 1. Пусть требуется повернуть плоскость изображения против часовой стрелки на заданный угол  вокруг точки A(a,b), не совпадающей с началом координат, это значит – определить матрицу перехода для любой точки M (см. рис. 18).

Алгоритм нахождения матрицы перехода:

1 шаг. Перенос начала координат из точки А y

в точку О, т.е. на вектор A(-a,-b). M

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

 1 0 -a

 T_-A    0 1 -b  b A

 0 0 1

2 шаг. Поворот на угол  O a x

cos  -sin  0 Рис. 18

 R_   sin  cos  0 

 0 0 1

3 шаг. Перенос обратно в точку А

 1 0 a

 T_A    0 1 b 

 0 0 1

Перемножая матрицы, получим результирующую матрицу нужного преобразования

cos  -sin  -a cos  + b sin  + a

T_-A  R_  T_A = sin  cos  -a sin  - b cos  + b 

 0 0 1 

Само преобразование координат для точки M имеет вид

x^* cos  -sin  -a cos  + b sin  + a  x

y ^*= sin  cos  -a sin  - b cos  + b  y 

1   0 0 1  1

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

Алгоритм нахождения матрицы перехода:

1 шаг. Перенос начала координат из точки A в точку О, т.е. на вектор

A(-a,-b). Матрица преобразования имеет вид

 1 0 -a

 T_-A    0 1 -b 

 0 0 1

2 шаг. Растяжение

  0 0

 D    0  0 

 0 0 1

3 шаг. Перенос обратно на вектор A(a,b)

 1 0 a

 T_A    0 1 b 

 0 0 1

Перемножив матрицы, получим

  0 (1-) a

T_-A  D  T_A =  0  (1-) b 

 0 0 1 

В общем случае однородными координатами точки M(x,y) называется любая тройка одновременно не равных нулю чисел x₁,x₂,x₃, связанных с исходными x и y следующими соотношениями

x₁ / x₃ = x x₂ / x₃ = y

При h=1 произвольной точке М на плоскости ставят в соответствие точку М^*, в пространстве координат на высоте 1, получим (x,y,1), а в общем случае (hx, hy,h), и можно трактовать однородные координаты как проекцию точки М на направляющий вектор ОМ^* .

Это - определенный род масштабирования в пространстве координат.

Способы описания прямой на плоскости

Любая прямая на плоскости может быть описана уравнением вида:

т.е. числа А и В одновременно не равны 0.

Известна запись при В0 (см. рис.20)

Если же В=0, то А0 и уравнение х = а, где а = - С/А. (см. рис.21).

Известно описание прямой координатами двух точек, принадлежащих ей.

Пусть есть точки (Рис.22).

Будем искать уравнение прямой L в виде:

Ax + By + C = 0

Тогда для любой точки на прямой должно быть справедливо

и уравнения прямой L можно записать в виде:

откуда получаем:

.

Таким образом, можно получить уравнение прямой L в виде:

.

Это называется каноническое уравнение прямой.

Описываемая каноническим уравнением пропорцио-нальность координат вектора

М₁ М = (x-x₁ ,y-y₁ ), где М – любая точка M L

и вектора М₁ М₂ = (x₂ -x₁ ,y₂ -y₁ )

означает, что эти векторы параллельны (коллинеарные), т.е. существует число t такое, что откуда получим систему уравнений:

,

где t принимает любые значения.

Эти уравнения называются параметрическими уравнениями прямой.

Если ограничить то уравнения имеют вид

и описывают отрезок, соединяющий заданные точки.

Существует описание прямой на плоскости путем задания точки и ненулевым вектором, перпендикулярным прямой L, n=(A,B).

Возьмем на прямой L произвольную точку M(x,y)L, тогда векторы n и M₀M перпендикулярны, т.е. скалярное произведение этих векторов равно 0.

(M₀M, n)=0.

Координатами вектора M₀M является пара чисел (x-x₀, y-y₀), перемножая соответствующие координаты и складывая, получим

,

обозначив имеем

Ax+By+C=0.

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

Вектор n = (A,B) называется нормальным вектором прямой или вектором нормали.

Всякая прямая L разбивает плоскость на две полуплоскости так, что для произвольной точки M’(x’,y’) справедливо одно из трех описаний:

а) Ax’+By’+C=0 - точка лежит на прямой;

б) Ax’+By’+C0 – считается, что точка M’ лежит в положительной полуплоскости;

в) Ax’+By’+C0 - считается, что точка M’ лежит в отрицательной полуплоскости.

Нормальный вектор обладает еще одним важным свойством: если отложить нормальный вектор n=(A,B) от некоторой точки, рассматриваемой прямой L, то его конец всегда окажется лежащим в положительной полуплоскости.

При умножении обеих частей уравнения на (-1) можно записать: -Ax-By-C=0, тогда n = (-A,-B) – конец вектора будет указывать на положительную полуплоскость, но относительно другого уравнения – прямой L.

Описание выпуклого многоугольника на плоскости

Выпуклый многоугольник обладает следующим свойством: отрезок, соединяющий любые две точки, принадлежащие многоугольнику, также принадлежат этому многоугольнику (см. рис.24). Треугольник является самым простым из выпуклых многоугольников. Он может быть задан либо координатами вершин M₁(x₁,y₁), M₂(x₂,y₂), M₃(x₃,y₃), либо уравнениями прямых, на которых лежат его стороны:

L₁: A₁ x + B₁ y + C₁ = 0

L₂: A₂ x + B₂ y + C₂ = 0

L₃: A₃ x + B₃ y + C₃ = 0

Переход от одного описания к другому очевиден.

Треугольник ограничивает часть плоскости, являющуюся его внутренностью.

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

L_i: A_i x + B_i y + C_i = 0, i = 1,2,3

запишем нормальные векторы n_i = (A_i ,B_i ) (см.рис. 25).

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

Тогда алгоритм проверки положения произвольной точки внутри треугольника или вне его имеет вид.

1 шаг. Добиться того, чтобы внутренность треугольника была отрицательной, т.е. преобразовать уравнения

A_i x + B_i y + C_i = 0, i = 1,2,3

так, чтобы вершина, не лежащая на прямой L_i, находилась в отрицательной полуплоскости. Для чего должны быть вычислены и координаты нормального вектора n_i = (A_i ,B_i ) и координаты вершины M_i(x_i,y_i).

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

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

ОСВЕЩЕНИЕ И ПОСТРОЕНИЕ ТЕНИ НА ПЛОСКОСТИ

Обратимся к проблеме освещенности на плоскости, т.к. это проще описать математически, а затем можно экстраполировать результаты на трехмерное изображение.

Существуют два варианта освещенности:

• параллельным пучком лучей или

• расходящимися лучами, имеющими точку исхода или центр пучка.

Рассмотрим сначала более простой вариант – параллельный пучок лучей, освещающих прямую (см. рис.26)

L: A x + B y + C = 0,

описанную таким образом, что источник расположен в положительной полуплоскости; тогда вектор l может указывать на источник (бесконечно удаленный). Угол падения луча  измеряет от нормали n. Ясно, что интенсивность освещенности прямой L зависит от величины этого угла

I = K(n,l) , где K –некоторый положительный коэффициент.

(n,l) = n l cos  скалярное произведение векторов n и l.

Так как источник находится в бесконечности, то прямая L будет освещена равномерно.

Рассмотрим освещение угла, образованного двумя прямыми L₁ и L_2. (см.рис.27).

Считаем, что векторы нормалей n₁ и n₂ имеют равную длину, причем

n₁ = n₂ = 1.

Для чего определяем n = (A,B) как

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

Алгоритм построения тени:

а) находим неосвещенные стороны по следующему признаку: углы  неосвещенных сторон тупые, а следовательно соответствующие скалярные произведения – отрицательные;

б) проецируем вершины, примыкающие к освещенным сторонам, на прямую;

в) проецируем вершины, примыкающие к неосвещенным сторонам, на заданную прямую;

г) находим две крайние проекции; соединяющий их отрезок прямой L и есть тень;

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

д) определяем освещенность точек прямой, лежащих вне отрезка L.

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

38