Системы координат на плоскости (стр. 2 )

Например, пусть имеется прямая

Ax + By + C = 0

Замена x и y на x/w и y/w дает A(x/w) + B(y/w) + C = 0. Умножая на w, получаем

Ax + By + Cw = 0

(1)

Другой пример. Пусть задан многочлен 2-го порядка

Ax2 + Bxy + Cy2 + 2Ey + F = 0

После замены x и y на x/w и y/w, соответственно, и умножения на w2, получаем

Ax2 + 2Bxy + Cy2 + 2Dxw + 2Eyw + Fw2 = 0

(2)

Если внимательно посмотреть на многочлены (1) и (2), можно заметить, что степени при всех членах равны. В случае многочлена 1-го порядка, это степень 1, тогда как для многочлена 2-й степени, все члены (т. е. x2, xy, y2, xw, yw и w2) имеют степень 2. Следовательно, для данного многочлена n-го порядка, после введения координаты w все члены будут иметь степень n. Такие многочлены называются однородными, а координаты (x, y,w) называются однородными координатами (homogenous coordinates).

Приведенные рассуждения остаются верными и в случае трехмерного пространства. Координаты (x, y,z) заменяются на (x/w, y/w, z/w) и после умножения на w в соответствующей степени n дают однородный многочлен.

Однородные координаты требуют три компоненты для представления точки на плоскости (и четыре компоненты для точки в пространстве). Какие же однородные координаты соответствуют точке с координатами (x, y)? Легко видеть, что это будет (x, y,1), т. е. w полагается равной 1.

В общем случае, это преобразование не однозначно. Однородные координаты точки (x, y) равны (xw, yw, w) для любого ненулевого w. Аналогично в трехмерном пространстве: точке (x, y,z) соответствуют координаты (xw, yw, zw, w). В то же время, преобразование из однородных координат в евклидовы однозначно: точке (x, y,w) соответствует точка (x/w, y/w).

Приведем более формальное определение.

Определение 1 Однородными координатами точки P=(x1,..,xn),P О Rn называются координаты Phom=(wx1,wx2,..,wxn, w),Phom О Rn+1, причем хотя бы один элемент должен быть отличен от нуля.

На самом деле, множество векторов Phom при определенных дополнительных операциях образуют так называемое проективное пространство, которое имеет важнейшее значение в машинном зрении. Мы на этом останавливаться не будем. Важнее запомнить следующее: преобразование из однородных координат в евклидовы однозначно; преобразование из евклидовых координат в однородные – нет.

Можно дать простую геометрическую интерпретацию однородных координат на плоскости.

Пусть даны однородные координаты (x, y,w) точки на плоскости Oxy, поставим ей в соответствие точку в трехмерном евклидовом пространстве с координатами x, y и w по осям X, Y и W соответственно. Прямая, соединяющая эту точку c началом координат, пересекает плоскость w=1 в точке (x/w, y/w, 1) (см. рис. 1).

Figure 1: Геометрическая интерпретация однородных координат

Таким образом, преобразование из однородных координат в евклидовы эквивалентно проекции точки на плоскость w=1 вдоль линии, соединяющей точку с началом координат.

Из рисунка также видно, что если преобразование из однородных координат в евклидовы однозначно, то обратное преобразование – нет, потому что все точки на линии, соединяющей точку (x, y,w) и начало координат будут проецироваться в точку (x/w, y/w).

Как было сказано выше, с помощью однородных координат можно легко описывать бесконечность. Рассмотрим точку с однородными координатами (x, y,w). Ей соответствует точка с евклидовыми координатами (x/w, y/w). Зафиксируем x и y и устремим w к нулю. Точка (x/w, y/w) будет удаляться все дальше и дальше в бесконечность в направлении (x, y). Когда w станет нулем, (x/w, y/w) уходит в бесконечность. Следовательно, однородные координаты (x, y,0) – идеальная точка (ideal point) или, по-другому, точка в бесконечности (point at infinity) по направлению (x, y). Аналогично для трехмерного пространства: точка (x, y,z,0) – точка в бесконечности по направлению (x, y,z).

Например, в OpenGL для определения положения источника света используются однородные координаты. С их помощью определить как точечный источник света (w=1), так и параллельный источник света (w=0).

7.  Однородные координаты пространства. Аффинные преобразования в пространстве.

Обратимся теперь к трехмерному случаю (3D) (3-dimension) и начнем наши рассмотрения сразу с введения однородных координат.

Поступая аналогично тому, как это было сделано в 2D, заменим координатную тройку (х, у, z), задающую точку в пространстве, на четверку чисел (х y z 1) или, более обще, на четверку (hx hy hz ), h ¹ 0.

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

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

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

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

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

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

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

Замечание

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

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

где

a > О - коэффициент растяжения (сжатия) вдоль оси абсцисс;

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

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

В. Матрицы отражения

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

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

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

Матрица переноса (здесь (l, m, n) - вектор переноса):

Замечание

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

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

Пример 1

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

l2 +m2+n2=1

Рис. 10

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

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

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

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

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

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

Рис. 11

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

(0, m, n).

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

cos y = n/d, sin y = m/d

где

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

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

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

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

cos q = l, sinq = - d.

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

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

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

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

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

Замечание

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

6-й шаг. Перенос на вектор А(а, b, с). Перемножив найденные матрицы в порядке их построения, получим следующую матрицу:

[T-A] [RX] [RY] [RZ] [RY]-1 [RX]-1 [T-A]-1

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

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

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

Пример 2

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

Рис. 12.

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

Vi(xi, yi, zi,), i = 1,…., n,

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

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

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

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

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

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

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

Ранее рассмотренная для двумерного случая матрица поворота является в то же время трехмерным поворотом вокруг оси Z. Так как при трехмерном повороте вокруг оси Z (поворот в плоскости XY) размеры вдоль оси Z неизменны, то все элементы третьей строки и третьего столбца равны 0, кроме диагонального, равного 1:

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

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

Столбцы и строки подматриц 3×3 матриц поворота Rx,  Ry,  Rz, аналогично двумерному случаю, представляют собой взаимно ортогональные единичные векторы. Легко убедиться, что суммарная матрица преобразования для произвольной последовательности поворотов вокруг осей X,  Y и Z имеет вид:

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

Зеркальное отображение:

Аффинные преобразования: вращение, дилатация (растяжение, сжатие), отражение и перенос — часто используются в качестве механизма порождения новых фигур из исходных. Способом описания, позволяющим единым образом представить все указанные преобразования и, широко используемым в компьютерной графике, являются однородные координаты. Они вводятся следующим образом в пространстве. Пусть точка имеет декартовы координаты (x, y,z), тогда её однородными координатами называется четвёрка чисел (hx, hy, hz) при . Фиксированной точке пространства при этом ставится в соответствие множество четвёрок однородных координат с различными . Если  — однородные координаты точки, то её декартовы координаты вычисляются согласно определению

, ,

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

Для описания аффинных преобразований достаточно рассмотреть случай, когда и каждая точка описывается четвёркой однородных координат вида (x, y,z,1). При преобразованиях точка с однородными координатами (x, y,z,1) переходит, в общем случае, в новую точку с однородными координатами , которые находятся с помощью матричного умножения:

=[A].

Рассмотрим теперь, какие матрицы отвечают аффинным преобразованиям в пространстве и могут использоваться в качестве матрицы [A].

Матрицы вращения (Rotation):

где а=sina, b=соsa. Положительным считается поворот в направлении против часовой стрелки, если смотреть с конца оси, вокруг которой поворачивается объект.

Матрица дилатации (Dilatation):

[D()]=

зависит от трёх параметров , , >0 — коэффициентов сжатия-растяжения вдоль соответствующих осей. При <1 — сжатие вдоль оси x, при >1 — растяжение. Аналогично для , .

Матрицы отражения (Reflection, Mirror):

— относительно плоскости xy:

[]=;

— относительно плоскости yz:

[]=;

— относительно плоскости zx:

[]=;

Матрицы переноса (Translation):

[]=

соответствует параллельному переносу на вектор .

Приведённые матрицы представляют элементарные аффинные преобразования. Для общих аффинных преобразований в пространстве матрица [A] формируется последовательным перемножением соответствующих матриц. В порядке, в котором производятся преобразования, слева направо.

Основные преобразования координат

Рассмотрим некоторую декартову систему координат. Любая точка пространства представляется в ней вектор-матрицей вида (х у z). Мы будем пользоваться однородными координатами точки в пространстве (х у z 1).

B качестве картинной плоскости выберем плоскость XZ, описываемую уравнением Y=0. Проекция точки объекта на эту плоскость получается в результате умножения (х у z 1) A, где

задает преобразование проецирования на плоскость XZ.

Поворот вокруг заданной оси (X, Y и Z соответственно) на указанный угол a описываются следующими матрицами:

где а=sina, b=соsa. Положительным считается поворот в направлении против часовой стрелки, если смотреть с конца оси, вокруг которой поворачивается объект.

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

Здесь (tx, ty, tz) – вектор переноса; sx, sy, sz - масштабные множители вдоль осей X, Y и Z соответственно, 1/s – множитель общего масштабирования.

8.  Аффинные преобразования, их свойства и инварианты.

Линейное преобразование на плоскости

(1)

называется ортогональным, если выполняются соотношения

(2)

Из соотношений (2) следует, что

(3)

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

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

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

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

1о. Последовательное выполнение двух ортогональных преобразований есть ортогональное преобразование.

2°. Тождественное преобразование х' = х, у' = у является ортогональным преобразованием (для этого преобразования соотношения (2), очевидно, выполняются).

3°. Преобразование, обратное ортогональному, также является ортогональным.

Линейное преобразование в пространстве

(4)

называется ортогональным, если выполняются соотношения

(5)

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

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

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

2°. Тождественное преобразование x' = x, y' = y, z' = z — ортогональное преобразование.

3°. Преобразование, обратное ортогональному, также ортогональное.

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

Уравнение цилиндра:

. (1)

Параметрическое уравнение прямой:

(2)

(l ,m ,n) – координаты вектора, коллинеарного данной прямой.

Точка принадлежит прямой.

Подставим уравнение прямой (2) в уравнение цилиндра (1). Получим квадратное уравнение относительно t.

;

; (3)

. (4)

Если выполняются соотношения:

;

; (5)

;

; (6)

; (7)

то прямая лежит на боковой поверхности цилиндра.

Если выполняются условия (5), (6), но не выполняется (7), то прямая || оси OZ и лежит внутри цилиндра (нет точек пересечения). Если выполняется (5) и не выполняются остальные условия, то прямая || оси OZ и лежит вне цилиндра (нет точек пересечения). Если дискриминант (4) D <0, то если не выполняются условия п.1 , то точек пересечения нет. Если дискриминант (4) D =0, то прямая касается цилиндра в одной точке. Если дискриминант (4) D >0, то существует 2 точки пересечения.

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

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

Прямая:

Пересечение луча с многоугольником.

В данном случае задача разбивается на две

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

2)  Проверка принадлежности точки пересечения многоугольнику.

1)Пусть плоскость задана общим уравнением

Ax+By+Cz+D=0

Где N=(A, B ,C)-нормальный вектор плоскости.

Заменяя в уравнении плоскости величины x, y и z их выражениями (*),

Получаем линейное уравнение относительно t :

Разрешая которое, находим, что

Если a=Al+Bm+Cn обращается в нуль, a=Al+Bm+Cn=0, то луч параллелен плоскости, и, следовательно, не пересекает ее.

В случае t*<0 луч не пересекает плоскости.

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

2) Решение основано на нахождении пересечения с треугольником. Если у многоугольника n вершин (n>3), то он будет представляться как набор из n-2 треугольников. N — вектор нормали к плоскости, в которой лежит рассматриваемый многоугольник. Точка Р задается как

(4)

Точка Р будет внутри треугольника

если а>=0, b>=0, и a + b<= 1

В равенство (4) состоит из 3 равенств:

(5)

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

В качестве направления проектирования рекомендуется брать ту ось, которой соответствует наибольшая координата у нормали.

Пусть

Пусть (u, v) координаты вектора в плоскости, на которую был спроектирован многоугольник. Тогда векторы будут иметь следующие координаты:

Система (5) упроститься до системы:

Решением являются :

2*) Выпуклый n-угольник однозначно задается набором своих вершин

Будем считать, что вершины многоугольника занумерованы так, что соседние по номеру вершины примыкают к одной стороне. Обозначим через (x*,y*,z*) точку пересечения заданного луча с плоскостью Ax+By+Cz+D=0, в которой лежит рассматриваемый многоугольник.

Вследствие того, что нормальный вектор N=(A, B ,C) плоскости, несущей заданный многоугольник, отличен от нуля, этот n-угольник можно взаимно однозначно спроектировать на n-угольник, лежащий в одной из координатных плоскостей. В качестве направления проектирования рекомендуется брать ту ось, которой соответствует наибольшая координата у нормали.

Предположим для определенности, что C =Max(A, B,C).

Тогда в качестве такой плоскости можно взять координатную плоскость xy, а в качестве направления проектирования – ось аппликат (ось Z).

Легко видеть, что координаты вершин n-угольника, получающегося в результате такого проектирования, будут иметь вид

Координаты точки, получающейся в результате проектирования на плоскость xy точки (x* ,y* ,z*) будут соответственно (x*, y*).

Ясно, что если точка (x*, y*) лежит вне (внутри) n-угольника, получившегося на плоскости xy ,то исходная точка (x* ,y* ,z*) будет внешней (внутренней ) по отношению к исходному n-угольнику.

Для определения положения точки (x*, y*) относительно выпуклого n-угольника, лежащего на плоскости xy, можно поступить, например, следующим образом.

Передвинем n-угольник

в плоскости xy так, чтобы точка (x*, y*) попала в начало координат.

В новой координатной системе абсциссы и ординаты вершин n-угольника будут соответственно

Теперь остается выяснить, будет (или не будет) точка (0,0), в которую преобразуется точка (x*, y*), внутренней точкой n-угольника с вершинами

Возможны два случая.

I Абсциссы всех вершин n-угольника – одного знака.

Это означает, что рассматриваемая точка лежит вне n-угольника.

II Есть два ребра n-угольника с вершинами

соответственно ( i < j), такие, что

Если

то интересующая нас точка лежит внутри n-угольника.

Это означает, что точка (x* , y* ,z*) лежит внутри исходного n-угольника.

Если же последнее произведение положительно, то точка (x* , y* ,z*) лежит вне исходного n-угольника.

11.  Алгоритм для определения точек пересечения луча со сферой.

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

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

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

Например, вершинами (x_, y_, z_), (x+, y+, z+).

Рассмотрим луч, исходящий из точки (x0, y0, z0) в направлении вектора

(l, m, n), где l2 + m2 + n2 =1, и опишем алгоритм, посредством которого можно определить, пересекает ли этот луч заданный прямоугольный параллелепипед или нет.

Возьмем пару плоскостей, параллельных плоскости yz: x = x_ и x = x+

При l=0 заданный луч параллелен этим плоскостям и, если x0 < x+ или x0 > x+, то он не пересекает рассматриваемый прямоугольный параллелепипед. Если же l не равно 0, то вычисляем отношения

t1x = (x_ - x0)/l, t2x = (x+ - x0)/l.

Можно считать, что найденные величины связаны неравенством t1x < t2x.

Пусть tn = t1x, tf = t2x

Считая, что m¹0, и рассматривая вторую пару плоскостей, несущих грани заданного параллелепипеда, y = y_ и y = y+, находим величины

t1y = (y_ - y0)/m, t2y = (y+ - y0)/m.

Если t1y > tn, тогда пусть tn = t1y.

Если t2y < tf, тогда пусть tf = t2y.

При tn > tf или при tf < 0 заданный луч проходит мимо прямоугольного параллелепипеда.

Считая n¹0, рассматриваем последнюю пару плоскостей z = z_ и z = z+ , находим величины t1z = (z_ - z0)/n, t2z = (z+ - z0)/n и повторяем предыдущие сравнения.

Если в итоге всех проведенных операций мы получим, что 0 < tn < tf или

0 < tf, то заданный луч непременно пересечет исходный параллелепипед со сторонами, параллельными координатным осям.

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

13.  Проективные преобразования.

Параллельное проектирование, при котором картинная плоскость совпадает с координатной плоскостью z==const описывается матрицей

[P]=

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

Основные свойства параллельных проекций

Свойство 1: Изображение прямой линии есть прямая или точка.