Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Оглавление

Введение

1. Векторы

2. Скалярное произведение

3. Детерминанты

4. Векторное произведение

5. Декомпозиция полигонов

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

7. Перенос и повороты в трехмерном пространстве

Введение

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

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

В результате изучения дисциплины студенты должны:

знать математические основы построения графических данных;

иметь навыки работы с современными развитыми графическими пакетами;

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

вектор полигон трехмерный

1. Векторы

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

Вектор -- это направленный отрезок прямой линии, характеризуемый только его длиной и направлением. На рис. 1 показаны два представления одного и того же вектора a=PQ=b=RS. Следовательно, при переносе вектор не изменяется. На рис. 2 начальная точка вектора b совпадает с конечной точкой вектора а. Тогда сумма векторов а и b определяется как вектор с, проведенный из начальной точки вектора а в конечную точку вектора b, поэтому можно записать c=a+b.

Рис. 1. Равные векторы

Рис. 2. Сложение векторов

Длина вектора a обозначается и равна расстоянию между его начальной и конечной точками. Вектор с нулевой длиной называется нулевым вектором и обозначается 0. Обозначение -а применяется для вектора, имеющего длину , направление которого обратно направлению вектора а. Для любого вектора а и вещественного числа с вектор са имеет длину с·. Если а=0 или с = 0, то са = 0, в противном случае вектор са совпадает по направлению с вектором а, если с>0, или имеет противоположное направление, если с<О. Для любых векторов u, v, w и вещественных чисел c,k будем иметь

u+v=v+u

(u + v) + w = u + (v + w)

u + 0 = u

u + (-u) =0

с(u +v) =cu + cv

(c + k)u = cu + ku

c(ku) =(ck)u

1 u = u

0 u = 0.

На рис. 3 показаны три единичных вектора i, j, k. Они взаимно перпендикулярны, имеют длину, равную 1, и определяют направления координатных осей. Можно сказать, что векторы i, j, k образуют тройку ортогональных единичных векторов. Координатная система является правой. Это означает, что если поворот от вектора i к вектору j нa 90° соответствует повороту винта с правой резьбой, то вектор k совпадает с направлением перемещения винта.

Точка О в начале координатной системы, как правило, является начальной точкой всех векторов. Любой вектор v может быть записан как линейная комбинация единичных векторов i, j, k

Рис. 3. Правая координатная система

v = хi + уj + zk.

Вещественные числа х, у, z определяют координаты конечной точки Р вектора v = OP. Этот вектор v может быть обозначен либо в виде строки v=[х у z] , либо в виде столбца v =.

Числа х, у, z иногда называют элементами вектора v.

2. Скалярное произведение

Скалярное произведение двух векторов а и b обозначается через a·b и определяется как

a·b = , если а0 и b0

a·b = 0 , если а = 0 или b = 0, (1)

где г -- угол между а и b.

Применяя это правило к единичным векторам i, j, k, находим

i ·i = j · j = k · k=1 i · j = j · i = j · k = k · j = k · i = i · k = 0. (2)

Приравнивая а = b в уравнении (1), получаем a · a = , так что

.

Важные свойства скалярного произведения:

c(ku · v) =ck(u·v)

(cu +kv) · w=cu · w+ kv · w

u · v = v · u

u · u = 0 только если u = 0.

Скалярное произведение векторов u=[u₁,u₂,u₃] и v=[v₁,v₂,v₃] может быть вычислено как

u·v=u₁v₁+u₂v₂+u₃v₃.

Это легко доказать, переписав правую часть уравнения

u·v=(u₁i+u₂j+u₃k)·( v₁i+v₂j+v₃k)

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

3. Детерминанты

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

, (3)

необходимо умножить первое уравнение на коэффициент b₂, а второе -- на коэффициент -b₁ и сложить, тогда получим

.

После этого можно первое уравнение умножить на -a₂, а второе -- на a₁ и также сложить. В результате получим

.

Если a₁b₂-a₂b₁ не равно нулю, то можно выполнить деление и найти

, . (4)

Выражение в делителе можно записать в форме .

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

Следовательно,

.

С помощью детерминантов уравнение (3) может быть записано в виде

, , (D0) ,

, , .

Определим детерминант третьего порядка в виде уравнения

и детерминант четвертого порядка соответственно:

и т. д.

Детерминанты имеют много интересных свойств. Рассмотрим некоторые из них.

1. Значение детерминанта не изменится, если строки записать в виде столбцов в том же порядке, например:

.

2. Если произвести взаимную замену двух строк (или двух столбцов), то значение детерминанта будет умножено на -1:

.

3. Если любую строку (или столбец) умножить на коэффициент, то значение детерминанта также будет умножено на этот коэффициент. Например:

.

4. Если строка (или столбец) изменяется путем добавления соответствующих элементов другой строки или столбца, умноженного на константу, то значение детерминанта не изменится. Например:

.

5. Если строка (или столбец) является линейной комбинацией некоторых других строк (или столбцов), то значение детерминанта равно нулю. Например:

.

Существует много полезных применений детерминантов. Детерминантные уравнения, выражающие геометрические свойства, просты и легки для запоминания. Например, уравнение для прямой линии в двухмерном пространстве, R₂, проходящей через две точки P₁(x₁,y₁) и P₂(x₂,y₂), может быть записано в виде

.

Аналогично, плоскость в трехмерном пространстве, R₃, проходящая через три точки P₁(x₁,y₁,z₁), P₂(x₂,y₂,z₂), P₃(x₃,y₃,z₃), будет описываться уравнением

4. Векторное произведение

Векторное произведение двух векторов a и b обозначается a Ч b и равно вектору v, который обладает следующими свойствами. Если а = сb для некоторого скаляра с, то v = 0. В противном случае длина вектора v равна

,

где г -- угол между векторами а и b, а направление вектора v перпендикулярно обоим векторам а и b и таково, что a, b, v именно в таком порядке образуют правостороннюю тройку. Последнее означает, что если вектор а поворачивается на угол у < 180° в направлении к вектору b, то вектор v имеет направление перемещения винта с правой резьбой, поворачиваемого в том же направлении. Из этого определения можно вывести следующие свойства векторного произведения:

а) (ka) Ч b =k(a Ч b) для любого вещественного числа k;

б) a Ч (b + c)=a Ч b + a Ч c;

в) a Ч b = - b Ч a.

В общем случае a Ч (b Ч c) (a Ч b) Ч c.

Используя правую ортогональную систему координат с единичными векторами i, j, k, будем иметь

i Ч j = j Ч j = k Ч k = 0

i Ч j = k, j Ч k = i, k Ч i = j

j Ч i = -k, k Ч j = -i, i Ч k = -j .

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

,

получим

,

что также может быть записано в виде

или в более удобной для запоминания форме:

.

Однако это скорее мнемоническая запись, чем реальный детерминант, поскольку элементами первой строки являются векторы, а не числа. Если через векторы a и b обозначены соседние стороны параллелограмма, как на риc. 4, то площадь этого параллелограмма равна длине вектора a b. Это непосредственно следует из записи .

Рис. 4. Параллелограмм с площадью

На рис. 5 векторы a и b лежат в плоскости, проходящей через оси x и y. Предположим, что ось z направлена так, что соответствует правой координатной системе.

Рис. 5. Векторное произведение k = а b

Тогда для трехмерного пространства можно записать:

a=[a₁ a₂ 0], b=[b₁ b₂ 0]

.

Таким образом, вектор а b будет иметь то же направление, что и вектор k, но только в том случае, если детерминант

имеет положительный знак. Это налагает условие, что вектор а, поворачиваемый по направлению к вектору b на угол меньше 180°, вращается в положительном направлении (против часовой стрелки) тогда и только тогда, когда D > 0.

На рис. 6 имеем

u=[u₁ u₂]=AB, v=[v₁ v₂]=AC

.

Рис. 6. Обход точек А, В, С против часовой стрелки

Вершины A, B, C именно в этом порядке обходим в направлении против часовой стрелки, исключительно если вектор u поворачивается в сторону направления вектора v на угол г < 180° против часовой стрелки. Это означает, что направление обхода точек А, В, С может быть установлено на основе анализа детерминанта D

следующим образом:

D> 0 точки А , В ,С "обходятся" против часовой стрелки;

D< 0 точки А, В, С "обходятся" по часовой стрелке;

D = 0 точки А, В, С лежат на одной прямой.

5. Декомпозиция полигонов на треугольники

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

Рис. 7. Два полигона частично "перекрывают" друг друга

Рис. 8. Типы полигонов: а - выпуклый полигон; б - невыпуклый полигон

Если внутренние углы при всех вершинах полигона меньше 180°, то такой полигон называется выпуклым. На рис. 8,б внутренний угол при вершине Р больше 180°. Такую вершину будем называть невыпуклой. Остальные вершины на рис. 8 -- выпуклые. Если полигон имеет хотя бы одну невыпуклую вершину, то весь такой полигон будем называть невыпуклым.

Если А и В -- две точки на границе выпуклого полигона, то и весь отрезок АВ будет принадлежать полигону. Для невыпуклых полигонов это условие может не соблюдаться.

Невыпуклость полигонов является источником сложностей, это же касается и переменного количества вершин полигонов. По этой причине уделим больше внимания треугольникам. Вполне очевидно, что треугольники всегда имеют фиксированное количество вершин и они обязательно выпуклые. Особый интерес к ним выявляется в связи с рассмотрением произвольных полигонов, поскольку любой полигон может быть разбит на конечное количество треугольников. Операция разбивки выпуклого полигона на треугольники достаточно проста, как это видно из рис. 9. Если вершины полигона пронумеровать последовательно P₀, P₁, …, P_n-1, а затем вычертить диагонали P₀P₂, P₀P₃, …, P₀P_n-2, то этого будет достаточно.

В невыпуклом полигоне, как на рис. 9,б, этот простой способ не применим, поскольку некоторые из диагоналей P₀P₂, P₀P₃, …, P₀P_n-2 могут выходить за пределы полигона.



Рис. 9. Варианты диагоналей: а -- диагонали внутри полигона; б -- диагональ P₀P₃ использовать нельзя

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

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

В качестве контрпримера рассмотрим рис. 10, в котором обход тройки P₁P₂P₃ выполняется по часовой стрелке. Вершина P₂ является невыпуклой, и диагональ P₁P₃ лежит вне полигона. Таким образом, диагональ P_i-1P_i+1 может только предполагаться для использования, если три вершины P_i-1(x_i-1,y_i-1), P_i(x_i,y_i), P_i+1(x_i+1,y_i+1) именно в этом порядке обходятся в направлении против часовой стрелки, т. е. если .

Рис. 10. Диагональ Р₁Р₃ вне полигона

Это условие является необходимым для деления полигона на треугольники. Это условие является необходимым, но, к сожалению, недостаточным, как это показано на рис. 11. Здесь точки P₀, P₁, P₂ обходятся именно в таком порядке в направлении против часовой стрелки, но отрезок P₀P₂ нельзя использовать для деления полигона на треугольники. Такой ситуации можно избежать, если принимать во внимание также длину диагоналей.

Рис. 11. Диагональ P₀P₂ частично находится вне полигона

Таким образом, необходимо выбирать наикратчайшую диагональ P_i-1P_i+2, которую может иметь выпуклая вершина P_i между точками P_i-1 и P_i+1. Эта диагональ используется для отсечения треугольника P_i-1 P_i P_i+1. Затем таким же образом проверяется оставшийся полигон P₀, P₁, …, P_i-1, P_i+1, …, P_n-1 и т. д. Технически это реализуется введением целочисленного массива v₀, …,v_m-1, содержащего номера вершин оставшегося полигона. Вначале задаем m=n и v_i= i (i=0, 1,…, n-1). Каждый раз при отсечении треугольника число m уменьшается на единицу. Исходный массив данных имеет следующую структуру:

n x₀ y₀ x₁ y₁…x_n-1 y_n-1.

Исходные ограничения:

максимальное количество точек n, например, n 500;

минимальное и максимальное значения координат;

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

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

Рис. 12. Штриховая линия

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

/* POLY_TRIA: Разбиение полигона на треугольники */

/* Dividing a polygon into triangles /

#define NMAX 500 /* максимальное количество точек */

#define BIG 1.0e30

^include "math.h"

int n, v[NMAX]; float x[NMAX], y[NMAX];

main()

{ int i, h, j, m, I, imin;

double diag, min_diag; prlntf("%s\n%s\n",

/* "Give n, followed by n coordinate pairs (x, y) of the vertices, ",

"in counter-clockwise order");*/

"Задайте число вершин n и затем п пар координат вершин (х, у)",

"в порядке обхода против часовой стрелки");

scanf("%d", &п);

if (n>-NMAX) { printf /* "n too large" */

("число п слишком велико");

exit(1);

}

for(i-0; Kn; i++) { scanf("%f %f", &x[i], &y[l]}; v[i]-i: } initgr(); draw_polygon(); m-n; while (m>3) { min_diag-=BIG;

for(i=0; Km; I++)

{

h=(i=-O?m-1 ; i-1);j=(i==m-1 ?0: 1+1);

if (counter_clock(h, i, j, &diag) && diag<min_dlag)

{ min_diag=diag; irninH;

} }

Hmin; h= (l= -0 ? m-1 :1-1); j- (I- -m-1 ? 0 : 1+1);

if (min_diag- -BIG) error_gr /* "wrong sense of rotation" */

("неправильное направление обхода");

dash(x[v[h]], y[v[h]], x[vO]], y[v[j]]);

m- -;

for(H; Km; I++) v[l}=v[l+1];

}

endgrt);

}

error_gr(str) char *str;

{ endgr(); prlntf("%s\n", str); exit(1);

}

Int counter_clock(h, i, j, pdist) int h, i, j; double *pdist;

{ double xh=x[v[h]], xi-x[v[i]], xj=x[v[j]],

yh-y[v[h]], yi=-y[v[i]], yj-y[vO]],

x_hi, y_hi, x_hj, y_hj, Determ;

x_hl=xi-xh; y_hl=-yi-yh; x_hj-xj-xh; y_hj-yj-yh;

*pdist = x_hj * x^_hj + y_hj * y_hj;

Determ - x_hi*y_hj - x_hj * y_hi; return

Determ>1e-6;

}

draw_polygon()

{ Int i;

move(x[n-1], y[n-1]);

for(i-0; i<n; П+) draw(x[l], y[l]);

}

dash(x1, y1, x2, y2) float x1. y1, x2, y2;

{ Inti, k;

float xdif=x2-x1, ydif-y2-y1, pitchO=0.3, dx, dy;

k-2 * (int)cell(sqrt(xdif*xdlf+ydif*ydif)/pitchO)+ 1;

dx-xdif/k; dyydif/k;

for (i-0; Kk; i-H-2)

{ move(x1+i*dx, y1+i*dy); draw(xl4{i+1)*dx, y1+{i+1)*dy);

} }

Следующая входная последовательность

n=12

x,y 1 1 6 1 6 4 4 4 4 3 5 3

5 2 2 2 2 3 3 3 3 4 1 4

приведет к выводу изображения, показанного на рис. 13.

Рис. 13. Результат работы программы POLI_TRIA

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

В этой главе рассматривается задача, связанная с построением перспективной проекции. Здесь будут обсуждаться только геометрические свойства этой задачи. Хотя рассуждения сравнительно просты, но они довольно длинные и носят теоретический характер. Цель заключается в более четком понимании обозначений типа [x y 1] и [x y z 1].

Запись [x y 1] уже использовалась для обозначения матрицы, состоящей только из одной строки, иногда называемой вектором - строкой. Такая запись может также рассматриваться как частный случай записи [х у w ], где числа х, у, w называются однородными координатами. Эти три числа однородных координат применяются для обозначения точки в двухмерном пространстве. В проективной геометрии однородные координаты применялись задолго до возникновения и распространения машинной графики. Далее будут рассматриваться перспективные преобразования. Фактически они являются центральным проецированием, исследуемым в различной литературе по проективной геометрии. Вкратце обсудим лишь несколько задач из этого раздела математики, избегая формальных определений и строгих доказательств теории. На рис. 14 имеем ось х и ось w, так что точка задается парой координат (v, w). Любая точка Р(x, у), не лежащая на оси х, имеет свою центральную проекцию Р'(Х, 1), определяемую как точка пересечения прямой линии ОР с прямой линией ?, описываемой уравнением w = 1. Точка начала координат является центром проекции. Для точек Q(0, w) и Q'(0, 1) получим два подобных треугольника OPQ и OP'Q', так что

.

Рис. 14. Двухмерная центральная проекция

Все точки (x, w) со свойством х = wX лежат на линии ОР и имеют одну и ту же проекцию Р'. Если будем интересоваться только проекциями на прямую линию ?, а не фактическими значениями x и w, то имеет значение только их отношение. Вполне естественно использовать только одну координату X вместо пары (X, 1), если учитывать только точки на прямой линии ?. Если же все-таки требуется использовать координатную пару, то подойдет любая пара чисел (x,w), удовлетворяющая условию x/w=X, если принять такое соглашение. В геометрическом смысле координатная пара (wX, w) любой точки Р, отличной от О, на прямой линии ОР' может служить обозначением точки Р'. Это и реализуется в случае применения однородных координат.

В общем случае любая точка (Х₁, Х₂,..., X_n) в n-мерном пространстве записывается как точка (wX₁, wX₂, ..., wX_n , w) в (n+1) -мерном пространстве, где w -- любое ненулевое вещественное число. Эта группа из n+1 чисел определяет однородные координаты исходной точки в n-мерном пространстве. Проекция является отображением множества точек в (n+1)-мерном пространстве в одну в n-мерном пространстве. Однородные координаты возникли из-за необходимости обратного преобразования из n-мерного пространства в (n+1)-мерное пространство. Точка (5,7) в двухмерном пространстве, например, может быть записана в однородных координатах как (15, 21, 3) или как (500, 700, 100) и т. д. Хотя все операции относятся к двухмерному пространству, эти тройки можно принимать за точки в трехмерном пространстве. Очевидно, что обозначение (X, Y) представляет собой обычную запись точки в двухмерном пространстве для точки (X,У,1) в трехмерном пространстве. Точка Р' является центральной проекцией для любой точки Р(x, у, w), если x/w=X и y/w=Y. Как и ранее, точка начала координат О будет центром проекций, а все точки проецируются на плоскость w=1.

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

аХ+bУ+с=0 , (6)

описывающим прямую линию в двухмерном пространстве. Заменяя X и У на x/w и y/w, получаем

a(x/w) +b(y/ w) +c = 0 или ax + by + cw = 0 . (7)

Уравнение (7) обычно принято называть однородным, поскольку оно имеет одинаковую структуру в терминах ах, by, cw. Отсюда числа x, у, w закономерно называть однородными координатами точки (X, У). Если опять принять, что двухмерное пространство располагается в плоскости w = 1 в координатной системе x y w, то уравнение (7) описывает плоскость, проходящую через начало координат и заданную прямую линию.

Если считать, что запись (х, у, w) используется как иная форма записи для (x/w, y/w), то необходимо, чтобы значение w не было равно нулю. Однако при этом однородные координаты едва ли имели какие-либо преимущества перед обычными координатами. Например, рассмотрим систему двух линейных уравнений, каждое из которых описывает прямую линию в двухмерном пространстве:

. (8)

Если две прямые линии параллельны, то они не пересекаются, и не существует пары чисел (X,У), удовлетворяющей системе (8). Таким образом, для нахождения общей точки для прямых линий необходимо применять правило с некоторым исключением. При замене координат X и У на однородные координаты х, у, w ситуация несколько улучшится

. (9)

Уравнения из системы (9) можно интерпретировать как плоскости, проходящие через точку начала координат О. Эта система имеет, по крайней мере, одно тривиальное решение х = у = w = 0. Для геометрической интерпретации зададим для коэффициентов конкретные значения.

Пусть, например, заменим систему (8) на следующую систему:

,

описывающую две параллельные прямые линии, изображенные на рис. 15. Тогда систему уравнений (9) можно заменить на

Эта система эквивалентна системе

,

так что решение состоит из всех троек (3k, -2k, 0), где k -- любое вещественное число. В трехмерном пространстве эти точки образуют прямую линию, проходящую через точки О и (3, -2, 0), причем эта прямая линия представляет собой линию пересечения двух плоскостей, заданных уравнениями (10). Возвращаясь к двухмерному пространству плоскости w= 1, напомним, что каждая точка (X, Y) ассоциируется с прямой линией (wX, wY, w) в трехмерном пространстве. Для ненулевых значений w эта ассоциация почти тривиальна. Теперь станет понятной очень важная причина применения однородных координат. Для каждой прямой линии в двухмерном пространстве добавим один объект, называемый бесконечно удаленной точкой. Эта бесконечно удаленная точка не может быть обозначена в обычной системе координат, а в системе однородных координат -- может. Например, бесконечно удаленная точка на прямой линии, описываемой уравнением (10, а), записывается как (3, -2, 0) или в виде любой тройки (3k, -2k, 0) для ненулевого k.

Поскольку эти тройки являются решением системы уравнений (10), то бесконечно удаленную точку можно считать точкой пересечения двух параллельных линий, изображенных на рис. 15. Считается, что бесконечно удаленная точка находится в двухмерном пространстве. Как было показано, каждая точка в двухмерном пространстве ассоциируется с прямой линией в трехмерном пространстве, поэтому желательно выяснить, с какой прямой линией ассоциируется бесконечно удаленная точка (3, -2, 0). Поскольку эта линия должна проходить через точку начала координат 0(0, 0, 0), то искомая линия должна быть линией, проходящей через точку О и точку (3, -2, 0), то есть лежащей в плоскости w=0.

Рис. 15. Параллельные прямые линии

Вполне резонно назвать точку (3, -2, 0) бесконечно удаленной точкой, поскольку ее можно рассматривать как предельную (3, -2, w) при w, стремящемся к нулю, а эта тройка в однородных координатах эквивалентна точке (3/w, -2/w, 1), которая при малых значениях w удалена очень далеко. Введение бесконечно удаленной точки позволяет утверждать, что две любые прямые пересекаются в одной точке. Аналогично в проективной геометрии можно утверждать, что две любые различные плоскости имеют линию пересечения. Если плоскости параллельны, то все точки этой линии пересечения в однородных координатах записываются в виде (х, у, z, 0). Этот вопрос не будем рассматривать детально, а вернемся к двухмерному пространству и покажем другие новые проявления возможностей, предоставляемых однородными координатами.

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

[X' Y']=[X Y] A

.

Поскольку [1 0] А = [a₁ а₂] и [0 1] А = [b₁ b₂], то строки матрицы A отображают соответственно точки [10] и [01].

Вне зависимости от способа определения матрицы А начало координат О не изменяется, так что [0 0] A = [0 0], поэтому этим способом нельзя выразить операцию переноса. Однако в однородных координатах точка в двухмерном пространстве задается тройкой (х, у, z) и преобразование записывается в виде

[х' у' w' ] = [х у w ] A

.

Мы имеем

[1 0 0] A= [a₁ а₂ а₃] .

Так как точка [1 0 0] -- бесконечно удаленная точка на оси х, то первая строка [а₁, а₂ а₃] матрицы А представляет собой отображение этой бесконечно удаленной точки на оси х. Аналогично вторая строка матрицы [b₁ b₂ b₃] будет отображением бесконечно удаленной точки на оси у. Поскольку

[0 0 1]А =[ c₁, с₂, с₃] ,

то можно считать, что третья строка матрицы [c₁ c₂ c₃] является отображением точки начала координат [0 0 1]. Это означает, что однородные координаты позволяют выразить любые преобразования путем матричного умножения. Фактически в этом нет ничего нового и это свойство уже использовалось в двухмерных алгоритмах. Однако операция переноса -- не единственное новое свойство, предоставляемое таким матричным умножением. С его помощью можно преобразовать параллельные прямые линии в пересекающиеся. Покажем это на примере преобразования полного прямоугольного квадранта в треугольник.

На рис. 16 изображен произвольный треугольник, вершины которого заданы в прямоугольной системе координат точками А(а₁, а₂), B(b₁, b₂) и С(c₁, c₂). Добавим третью координату, равную 1, как формальное средство образования однородных координат. Исключением являются бесконечно удаленные точки (1, 0, 0) и (0, 1, 0) на координатных осях, у которых третья однородная координата равна нулю. Образуем матрицу M, такую, что матричное умножение



Рис. 16. Квадрант, преобразованный в треугольник

[х' у' z']=[x у z] M

отобразит точку О на точку С, точку (1, 0, 0) -- на точку А и точку (0, 1, 0) -- на точку В. Для любых ненулевых значений б, в, г точки А, В и С будут точками требуемого изображения треугольника, если

. (11)

Это легко проверить, поскольку имеем очевидное соотношение

[1 0 0] М= [ба₁ ба₂ б] ,

правая часть которого является просто другим обозначением точки А на рис. 16. На первый взгляд кажется, что константы б, в, г в уравнении (11) не нужны и могут быть установлены равными 1. Однако они нужны для того, чтобы можно было задать заранее установленное отображение U' для так называемой единичной точки U. Точка U' может быть выбрана в любом месте внутри треугольника. Поскольку точка U(1, 1, 1) отображается на точку U' (u₁, u₂, u₃), то имеем

[1 1 1] M = [ u₁ u₂ 1]

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

a₁б + b₁в + c₁г = u₁

а₂б + b₂в + с₂г = u₂

б + в + г = 1 .

Система имеет единственное решение, которое следует из того факта, что тройки (a₁, а₂, а₃), (b₁, b₂, b₃) и (c₁, c₂, с₃) обозначают вершины треугольника. Решение этой системы для б, в, г и подстановка результата в уравнение (11) дают искомое значение матрицы М.

Прямые линии преобразуются в прямые линии, но их параллелизм не сохраняется. Например, вертикальная линия, проходящая через точку U на рис. 16, превращается в прямую линию, проходящую через точки В и U'. Это дает геометрическое средство для нахождения проекции Р' для точки Р. Имея вычисленное значение матрицы М, точку проекции Р' можно найти аналитически как произведение [1 0 1] М.

Заметим, что все бесконечно удаленные точки отображаются на отрезок АВ, а все бесконечно удаленные точки параллельных линий -- на единственную точку на отрезке АВ. Это даст основание рассматривать весь квадрант как плоскую перспективу, в которой треугольник ABC является картиной, а отрезок АВ представляет собой линию горизонта.

На этом закончим анализ однородных координат. Другие интересные свойства однородных координат можно найти в учебниках по проективной геометрии, например Hopkins and Hails (1953).

7. Перенос и повороты в трехмерном пространстве

Если каждая точка Р(х, у, z) отображается на точку Р'(х', y', z') в соответствии с уравнениями

,

где a₁, a₂, a₃ -- константы, то этот процесс называется переносом в трехмерном пространстве. Такой перенос может быть записан в матричной форме

[ x' y' z' 1 ]=[ x y z 1 ] T ,

. (12)

Здесь первая, вторая и третья строки матрицы Т соответствуют отображениям бесконечно удаленных точек на координатных осях, а четвертая строка -- отображению точки [0 0 0 1 ]. Последнее означает, что в однородных координатах точка [a₁, a₂, a₃ 1] является отображением точки начала координат О. Поворот вокруг координатных осей может быть описан матрицей и без использования однородных координат. Будем использовать правую координатную систему, считая вращение вокруг оси положительным, если оно соответствует положительному направлению этой оси по правилу винта с правой резьбой. Это показано на рис.17.

Рис. 17. Вращение в положительном направлении вокруг координатных осей

Рассмотрим поворот вокруг оси z на угол б и для сокращения обозначим cosб = с и sinб = s. Тогда можно записать

[ x' y' z' 1 ]=[ x y z ] R_Z

.

Матрицу R_Z можно использовать для получения матриц и R_X, определяющих поворот вокруг соответствующих осей, чисто формальным образом, т. е. без применения картинки. Это делается путем циклических перестановок, получаемых заменой каждой из букв x, y, z на последующую, считая, что за буквой z следует буква x.

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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Аналогично матрица R_X преобразуется в "последующую" матрицу R_Y:

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

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

(13)

(14)

. (15)

Для поворота точки вокруг оси x на угол б матрица R_X используется следующим образом:

[ x' y' z' 1 ]=[ x y z ] R_X.

Матрицы R_y и R_z применяются аналогично.

Уравнения для преобразований могут интерпретироваться как изменения координат. Перенос точки на определенное расстояние вправо описывается теми же уравнениями, что и перенос системы координат на такое же расстояние влево. Удобнее перемещать координатную систему вместо точки, но для этого требуется инвертирование матрицы. Инверсия матриц T, R_X, R_Y, R_Z, уравнения (12) …(15), может быть записана немедленно:

(16)

(17)

(18)

. (19)

Теперь можно найти матрицу R для поворота вокруг любой прямой линии, проходящей через точку начала координат O. Для определенности будем полагать, что поворот осуществляется вокруг вектора v, начало которого расположено в точке O. Тогда положительное направление вращения соответствует направлению вектора по правилу винта с правой резьбой. Как и ранее, поворот будем производить на угол б.

Если концевая точка вектора v задана в ортогональных координатах, то сначала вычислим его сферические координаты с, и, ц ( рис. 18)

.

Если с=0, то будем считать, что и=ц=0. В противном случае

ц=arccos (v₃/с).

Существует также обратное вычисление

v₁=с sinц cosи, v₂=с sinц sinи, v₃= с cosц.

Дальнейшая стратегия заключается в таком изменении системы координат, чтобы вектор v (ось вращения) совпадал с новым направлением положительной полуоси z. Начнем с поворота осей x и y вокруг оси z на угол и. В соответствии с уравнением (19)

[ x' y' z' 1 ]=[ x y z ]

R_z^-1.

Ось x' имеет положительное направление вектора (v₁, v₂, 0). Повернем оси x' и z' вокруг оси y' на угол ц до совпадения оси z" с вектором v (рис. 18). Пользуясь уравнением (18), запишем это условие следующим образом:

Рис. 18. Сферические координаты

\[ x" y" z" ] = [ x' y' z' ] R_y^-1

.

Фактический поворот вокруг вектора v на угол б теперь можно выполнить как поворот вокруг оси z". Из уравнения (15) получим

[ x''' y''' z''' ]=[ x" y" z" ] R_V

.

К этому моменту достигнуто выполнение соотношения

[ x''' y''' z''' ]=[ x y z ] R_z^-1 R_y^-1 R_V^-1.

Координаты x''', y''', z''' относятся к самой последней системе координат, тогда как их необходимо выразить в исходной системе. Обозначим эти координаты в исходной системе через x*, y*, z*. Переход к исходной системе инвертированных матриц R_Z^-1 и R_Y^-1 (которые будут совпадать с матрицами R_Z и R_Y) в обратном порядке для преобразования точки x''', y''', z''' будет осуществляться следующим образом:

[ x* y* z* ] = [ x''' y''' z''' ] R_Y R_Z.

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

[ x* y* z* ] = [ x''' y''' z''' ] R_Z^-1 R_Y^-1 R_V R_Y R_Z,

.

Для последующего применения запишем

. (20)

До сих пор обсуждалось решение задачи о повороте относительно вектора, исходящего из точки начала системы координат 0. Теперь нужно устранить это последнее ограничение и поставить задачу определения поворота относительно вектора, начало которого расположено в любой произвольной точке А(а1,а2,а3).

Для этого используем вектор v для вычисления матрицы R в уравнении (20) таким же образом, как и ранее. Затем нужно выполнить три следующих шага:

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

;

теперь можем осуществить поворот относительно оси, проходящей через 0, как и ранее, но матрицу R из уравнения (20) необходимо расширить тривиальным образом, чтобы можно было использовать однородные координаты

;

применить преобразование, обратное шагу 1, используя матрицу Т

.

После этого матрица обобщенного поворота вычисляется как

R_GEN = T^-1 R*T

и ее можно использовать следующим образом:

[ x* y* z* 1 ] = [ x y z 1 ]R_GEN.

Размещено на Allbest.ru