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

Линейной комбинацией векторов $$\overrightarrow{a}$$ и $$\overrightarrow{b}$$ называется вектор $$\overrightarrow{c}=\alpha\overrightarrow{a}+\beta\overrightarrow{b}$$. При этом числа $$\alpha$$ и $$\beta$$ называются коэффициентами разложения вектора $$\overrightarrow{c}$$ по векторам $$\overrightarrow{a}$$ и $$\overrightarrow{b}$$.

Если два вектора $$\overrightarrow{r}_1$$ и $$\overrightarrow{r}_2$$ заданы своими координатами $$(x_1, y_1, z_1)$$ и $$(x_2, y_2, z_2)$$, то операции над ними легко выразить через эти координаты:

Векторы $$\overrightarrow{a}$$, $$\overrightarrow{b}$$ и $$\overrightarrow{c}$$ называются компланарными, если они лежат в одной плоскости.

Векторы называются линейно независимыми, если равенство нулю их линейной комбинации возможно только в случае равенства нулю коэффициентов $$\alpha$$ и $$\beta$$.

Справедливы следующие свойства:

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

Скалярным произведением векторов $$\overrightarrow{r}_1$$ и $$\overrightarrow{r}_2$$ называется число, равное произведению длин этих векторов на косинус угла между ними. Будем обозначать скалярное произведение векторов символом $$(\overrightarrow{r}_1\cdot\overrightarrow{r}_2)$$. Тогда скалярное произведение можно выразить формулой$$(\overrightarrow{r}_1\cdot\overrightarrow{r}_2=|\overrightarrow{r}_1|\cdot|\overrightarrow{r}_2|\cos\alpha).$$

Несложно доказать следующие свойства данной операции.

Приведем некоторые формулы, связанные с разложением вектора в декартовой системе координат.

Пусть векторы $$\overrightarrow{r}_1$$ и $$\overrightarrow{r}_2$$ заданы своими координатами $$(x_1,y_1,z_1)$$ и $$(x_2,y_2,z_2)$$. Тогда их скалярное произведение может быть вычислено по формуле$$(\overrightarrow{r}_1\cdot\overrightarrow{r}_2)=x_1 x_2+y_1 y_2+z_1 z_2.$$

Отсюда следует условие перпендикулярности векторов:$$x_1 x_2+y_1 y_2+z_1 z_2 = 0.$$

И, наконец, косинус угла между векторами вычисляется по формуле$$\cos\varphi=\frac{x_1 x_2+y_1 y_2+z_1 z_2}_{\sqrt{x_1^2+y_1^2+z_1^2}\cdot\sqrt{x_2^2+y_2^2+z_2^2}}.$$

Теперь расстояние между двумя точками с координатами $$(x_1,y_1,z_1)$$ и $$(x_2,y_2,z_2)$$ можно выразить через скалярное произведение соответствующих векторов:$$d=|{(\overrightarrow{r}_1 - \overrightarrow{r}_2)}|.$$

Введем еще одно понятие, касающееся векторов. Три вектора называются упорядоченной тройкой, если указано, какой из этих векторов является первым, какой - вторым и какой - третьим. При записи тройки векторов будем располагать эти векторы в порядке их следования. Так, запись $$\overrightarrow{b}\overrightarrow{a}\overrightarrow{c}$$ означает, что первым вектором тройки является вектор $$\overrightarrow{b}$$, вторым - $$\overrightarrow{a}$$, третьим - $$\overrightarrow{c}$$.

Тройка векторов называется правой ( левой ), если после приведения к общему началу вектор $$\overrightarrow{c}$$ располагается по ту сторону от плоскости, содержащей векторы $$\overrightarrow{a}$$, $$\overrightarrow{b}$$, откуда кратчайший поворот от $$\overrightarrow{a}$$ к $$\overrightarrow{b}$$ кажется совершающимся против часовой стрелки ( по часовой стрелке ).

Векторным произведением вектора $$\overrightarrow{a}$$ на вектор $$\overrightarrow{b}$$ называется вектор $$\overrightarrow{c}$$, обозначаемый символом $$\overrightarrow{a}\times\overrightarrow{b}$$ и удовлетворяющий следующим требованиям:

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

Ясно, что векторное произведение двух коллинеарных векторов дает нулевой вектор. Выведем теперь формулy для векторного произведения. Пусть базисные векторы декартовой системы координат $$\overrightarrow{i},\overrightarrow{j},\overrightarrow{k}$$ образуют правую тройку. Тогда справедливы следующие соотношения:$$\begin{gathered} [\overrightarrow{i}\times\overrightarrow{j}]=\overrightarrow{k}=-[\overrightarrow{j}\times\overrightarrow{i}], \quad [\overrightarrow{j}\times\overrightarrow{k}]=\overrightarrow{i}=-[\overrightarrow{k}\times\overrightarrow{j}], \\ [\overrightarrow{k}\times\overrightarrow{i}]=\overrightarrow{j}=-[\overrightarrow{i}\times\overrightarrow{k}] \end{gathered}$$

Если заданы два вектора $$\overrightarrow{r}_1=x_1\overrightarrow{i}+y_1\overrightarrow{j}+z_1\overrightarrow{k}$$ и $$\overrightarrow{r}_2=x_2\overrightarrow{i}+y_2\overrightarrow{j}+z_2\overrightarrow{k}$$, то, учитывая свойства векторного произведения, отсюда легко вывести, что$$\overrightarrow{r}_3=[\overrightarrow{r}_1\times\overrightarrow{r}_2]=x_3\overrightarrow{i}+y_3\overrightarrow{j}+z_3\overrightarrow{k},$$ где$$x_3=y_1 z_2-z_1 y_2, \quad y_3=z_1 x_2-x_1 z_2, \quad z_3=x_1 y_2-y_1 x_2.$$

Уравнения прямой и плоскости

Уравнение прямой на плоскости в декартовой системе координат можно задать уравнением вида$$y=kx+b$$ для случая, когда прямая не параллельна оси OY, и уравнением$$x=c$$ для вертикальной прямой. Но прямая может быть также задана и другим способом. Достаточно указать вектор направления этой прямой $$\overrightarrow{l}=(l_x,l_y)$$ и какую-нибудь точку $$\overrightarrow{r}_0=(x_0,y_0)$$, лежащую на этой прямой. При этом точки, лежащие на прямой, могут быть заданы с использованием векторных операций в виде так называемого параметрического уравнения прямой$$\overrightarrow{r}=\overrightarrow{r}_0+t\overrightarrow{l},$$ в котором параметр t пробегает все значения числовой прямой. Координаты точки, соответствующей некоторому значению этого параметра, определяются соотношениями$$x=x_0+tl_x, \quad y=y_0+tl_y.$$

Прямую в пространстве тоже можно задавать параметрическим уравнением, которое очень легко получить из предыдущего простым переходом от двумерных векторов к трехмерным. Пусть $$\overrightarrow{l}=(l_x,l_y,l_z), \; \overrightarrow{r}_0=(x_0,y_0,z_0)$$. Тогда это уравнение будет определять прямую в пространстве, а координаты точек этой прямой будут определяться формулами$$x=x_0+tl_x, \quad y=y_0+tl_y, \quad z=z_0+tl_z, \quad -\infty<t<+\infty.$$

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

Плоскость в пространстве можно задать, указав вектор нормали к ней и какую-либо точку, принадлежащую данной плоскости. Пусть $$\overrightarrow{n}=(n_1,n_2,n_3)$$ - вектор единичной нормали, а $$\overrightarrow{r}_0=(x_0,y_0,z_0)$$ - некоторая точка на плоскости. Тогда для любой точки $$\overrightarrow{r}=(x,y,z)$$, лежащей на плоскости, вектор $$\overrightarrow{r}-\overrightarrow{r}_0$$ будет ортогонален вектору нормали, а следовательно, выполняется равенство$$\left( (\overrightarrow{r}-\overrightarrow{r}_0)\cdot \overrightarrow{n} \right)=0.$$ Раскрывая это выражение в координатном виде, получаем$$n_1 x+n_2 y +n_3 z-n_1 x_0 -n_2 y_0 -n_3 z_0 =0.$$ Теперь перепишем это уравнение в виде$$n_1 x+n_2 y+n_3 z+d=0,$$ где $$d=-n_1 x_0-n_2 y_0-n_3 z_0$$. Это уравнение называется каноническим уравнением плоскости. При этом совершенно ясно, что если все это уравнение умножить на какой-либо отличный от нуля множитель, то оно будет описывать ту же самую плоскость, т.е. коэффициенты $$n_1, n_2, n_3$$ для каждой плоскости задаются с точностью до произвольного ненулевого множителя. Но если при этом вектор $$\overrightarrow{n}$$ имеет единичную длину, то $$|d|$$ задает расстояние от начала координат до данной плоскости.

В алгоритмах компьютерной графики довольно часто приходится сталкиваться с задачей построения плоскости, проходящей через три заданные точки. Пусть три точки $$\overrightarrow{r}_1$$, $$\overrightarrow{r}_2$$ и $$\overrightarrow{r}_3$$, не лежащие на одной прямой, имеют координатами $$(x_1,y_1,z_1),(x_2,y_2,z_2)$$ и $$(x_3,y_3,z_3)$$. Для канонического уравнения необходимо построить нормаль к плоскости, что легко можно осуществить, используя операцию векторного произведения. Поскольку векторы $$\overrightarrow{v}_1=\overrightarrow{r}_2-\overrightarrow{r}_1$$ и $$\overrightarrow{v}_2=\overrightarrow{r}_3-\overrightarrow{r}_1$$ лежат в искомой плоскости, то вектор $$\overrightarrow{N}=\overrightarrow{v}_1\times\overrightarrow{v}_2$$ будет ортогонален этой плоскости. Пусть $$\overrightarrow{N}=(N_x,N_y,N_z)$$, тогда уравнение плоскости будет иметь вид$$N_x x+N_y y+N_z z+D=0.$$

Остается определить значение $$D$$. Так как точка $$\overrightarrow{r}_1$$ принадлежит этой плоскости, то ее координаты должны удовлетворять полученному уравнению. Подставим их в уравнение и получим$$N_x x_1+N_y y_1 +N_z z_1 +D=0,$$ следовательно$$D=-N_x x_1-N_y y_1-N_z z_1,$$ и после подстановки окончательно получим:$$N_x(x-x_1)+N_y(y-y_1)+N_z(z-z_1)=0$$

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

Пересечение луча с плоскостью и сферой

Прямая на плоскости и в пространстве является бесконечной в обе стороны. Лучом называется полупрямая, т.е. множество всех точек прямой, лежащих по одну сторону от заданной ее точки, называемой началом луча. Луч будем задавать в параметрическом виде, как это было описано в одном из предыдущих разделов. Пусть $$\overrightarrow{l}=(l_x,l_y,l_z)$$ - направляющий вектор прямой, а $$\overrightarrow{r}_0=(x_0,y_0,z_0)$$ - начальная точка. Тогда координаты точек луча будут определяться формулами$$x=x_0+tl_x, \quad y=y_0+tl_y, \quad z=z_0+tl_z.$$

Будем считать, что направляющий вектор единичный, т.е. $$l_x^2+l_y^2+l_z^2=1$$.

Сначала рассмотрим задачу о нахождении точки пересечения луча с плоскостью, заданной каноническими уравнением$$n_1 x+n_2 y+n_3 z+d =0.$$

Вектор нормали $$\overrightarrow{n}=(n_1,n_2,n_3)$$ тоже будем считать единичным. Сначала надо определить значение параметра t, при котором луч пересекает плоскость. Для этого подставим координаты из формулы (3.8) в уравнение (3.9) и получим$$n_1(x_0+tl_x)+n_2(y_0+tl_y)+n_3(z_0+tl_z)+d=0,$$ откуда легко определить, что луч пересекает плоскость в точке со значением$$t_0=-\frac{(\overrightarrow{r}_0\cdot\overrightarrow{n})+d}{(\overrightarrow{l}\cdot\overrightarrow{n})}.$$

Очевидно, что такая точка существует только при условии $$(\overrightarrow{l}\cdot\overrightarrow{n})\neq0$$. В свою очередь, эта величина обращается в нуль только в случае, когда векторы $$\overrightarrow{l}$$ и $$\overrightarrow{n}$$ ортогональны друг другу.

Пусть теперь нам задана сфера с центром в точке $$\overrightarrow{r}_c=(x_c,y_c,z_c)$$ и радиусом $$d$$. Тогда уравнение сферы будет иметь вид$$(x-x_c)^2+(y-y_c)^2+(z-z_c)^2=d^2.$$

Подставив сюда координаты луча из уравнения (3.8), получим, что параметр, при котором луч пересекает сферу, должен удовлетворять квадратному уравнению$$at_0^2+bt_0+c=0,$$ где $$a=|\overrightarrow{r}_c|^2, \; b=2((\overrightarrow{r}_0-\overrightarrow{r}_c)\cdot\overrightarrow{l}), \; c=|\overrightarrow{r}_0-\overrightarrow{r}_c|^2-d^2$$. Определим корни этого уравнения. Если дискриминант $$D=\frac{b^2}{4}-c\ge 0$$, то корни существуют. Их может быть либо два $$(D>0)$$, либо один $$(D=0)$$. В первом случае имеем две точки пересечения, во втором - одну (луч касается сферы). Соответствующие значения параметра определяются соотношением$$t_{1,2}=-\frac{b}{2}\mp\sqrt{D}$$

Аналитическое представление кривых и поверхностей

Пусть на плоскости задана декартова система координат.

Кривая на плоскости - это геометрическое место точек $$(x,y)$$, удовлетворяющих уравнению$$F(x,y)=0$$ где $$F$$ - функция двух переменных. Ясно, что далеко не каждая функция будет задавать линию. Так, например, уравнению$$x^2+y^2+1=0$$ не удовлетворяет ни одна точка плоскости, а уравнению$$x^2+y^2=0$$ удовлетворяет только одна точка $$(0,0)$$.

Для аналитического представления кривой во многих случаях удобнее задавать кривую параметрическими уравнениями, используя вспомогательную переменную (параметр) $$t$$:$$x=\varphi(t), \quad y=\psi(t), t \in [a,b],$$ где $$\varphi$$ и $$\psi$$ - непрерывные функции на заданном интервале изменения параметра. Если функция $$\varphi(t)$$ такова, что можно выразить $$t$$ через $$x(t=\varphi^{-1}(x))$$, то от параметрического представления кривой легко перейти к уравнению (3.10):$$y=\psi(\varphi^{-1}(x))=0.$$ Систему уравнений (3.11) можно записать в векторном виде:$$\overrightarrow{r}=\overrightarrow{f}(t), \quad \overrightarrow{r}=(x,y), \quad \overrightarrow{f}(t)=(\varphi(t),\psi(t)).$$

Отрезок прямой представляет собой частный случай кривой, причем параметрическое представление его может иметь вид$$x=t, \quad y=at+b, \quad t \in[t_1,t_2]$$ или$$x=at+b, y=t, t\in[t_1,t_2]$$

Окружность радиуса $$r$$ с центром в точке $$(x_0,y_0)$$ может быть представлена параметрическими уравнениями$$x=x_0+r\cdot\cos t, \quad y=y_0+r\cdot\sin t, t\in[0,2\pi].$$

Перейдем к трехмерному пространству с заданной декартовой системой координат.

Поверхность в пространстве - это геометрическое место точек $$(x,y,z)$$, удовлетворяющих уравнению вида$$F(x,y,z)=0.$$

Так же как и в случае кривой на плоскости, не всякая функция $$F$$ описывает какую-либо поверхность. Например, уравнению$$x^2+y^2+z^2+1=0$$ не удовлетворяет ни одна точка пространства. Поверхность также может быть задана в параметрическом виде, но в отличие от кривой для этого требуются две вспомогательные переменные (параметры):$$x=\varphi(u,v), \quad y=\psi(u,v), \quad z=\zeta(u,v), \quad u\in[a,b], \quad v\in[c,d].$$

Например, сфера радиуса $$r$$ с центром в точке $$(x_0, y_0, z_0)$$ может быть задана уравнением$$(x-x_0)^2+(y-y_0)^2+(z-z_0)^2-r^2=0$$ либо же параметрическими уравнениями$$x=x_0+r\cdot\cos u\cdot\cos v, \quad y=y_0+r\cdot\sin u, \quad z=z_0+r\cdot\cos u \cdot\sin v.$$

Кривую в пространстве можно описать как пересечение двух поверхностей, т.е. с помощью системы уравнений$$F_1(x,y,z)=0, \quad F_2(x,y,z)=0$$ или параметрическими уравнениями вида$$x=\varphi(t), \quad y=\psi(t), z=\zeta(t), \quad t\in[a,b].$$

Интерполяция функций одной и двух переменных

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

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

Пусть на плоскости задана система координат $$XOY$$ и отрезок $$[x_1,x_2]$$ на оси $$OX$$, на концах которого заданы значения $$y_1,y_2$$ некоторой линейной функции (рис. 3.3). Тогда для любой точки $$x$$ внутри заданного отрезка соответствующее значение $$y$$ вычисляется по формулам$$y=ty_1+(1-t)y_2, \qquad t=(x_2-x)/(x_2-x_1).$$

Обратимся теперь к задаче интерполяции функций двух переменных. В этом случае наиболее простой также является интерполяция по трем заданным точкам опять же с помощью кусочно-линейной функции. Пусть на плоскости задан треугольник с вершинами $$(x_1,y_1),(x_2,y_2),(x_3,y_3)$$ и заданы значения функции в этих точках $$z_1,z_2,z_3$$. Тогда три точки $$(x_i,y_i,z_i)$$ определяют в пространстве треугольник, который является плоской фигурой. Предполагается, что площадь треугольника больше нуля, или, как говорят, треугольник невырожденный. Для определения значения функции в произвольной точке $$(x,y)$$, лежащей внутри треугольника, воспользуемся так называемыми барицентрическими координатами $$(\alpha,\beta,\gamma)$$ этой точки. Геометрический смысл этих координат заключается в том, что они равны отношению площадей треугольников, изображенных на рис. 3.4:

$$\alpha=\frac{S_1}{S}, \; \beta=\frac{S_2}{S}, \; \gamma=\frac{S_3}{S}, \; S=S_1+S_2+S_3.$$ Эти числа неотрицательны и удовлетворяют следующим соотношениям:$$\left. \begin{aligned} \alpha+\beta+\gamma=1 \\ \alpha x_1+\beta x_2+\gamma x_3=x \\ \alpha y_1+\beta y_2+\gamma y_3=y \end{aligned} \right\}.$$ Эти соотношения будем рассматривать как уравнения для нахождения чисел $$(\alpha,\beta,\gamma)$$.

Определитель этой системы уравнений есть$$\Delta= \begin{vmatrix} 1 1 1 \\ x_1 x_2 x_3 \\ y_1 y_2 y_3 \end{vmatrix} =(x_2-x_1)(y_3-y_1)-(x_3-x_1)(y_2-y_1),$$ и он по модулю равен удвоенной площади треугольника, поэтому $$\Delta\ne 0$$, следовательно, система имеет единственное решение при любой правой части. Воспользуемся формулами Крамера и выпишем вид этого решения:$$\alpha=\frac{\Delta_1}{\Delta}, \quad \beta=\frac{\Delta_2}{\Delta}, \quad \gamma=1-\alpha-\beta,$$ где$$\begin{aligned} \Delta_1= \begin{vmatrix} 1 1 1 \\ x x_2 x_3 \\ y y_2 y_3 \end{vmatrix} =(x_2 y_3-x_3 y_2)+x(y_2-y_3)+y(x_3-x_2), \\ \Delta_2= \begin{vmatrix} 1 1 1 \\ x_1 x x_3 \\ y_1 y y_3 \end{vmatrix} =(x_3 y_1-x_1 y_3)+x(y_3-y_1)+y(x_1-x_3). \end{aligned}$$ После того как получены барицентрические координаты точки $$(x,y)$$, значение функции в ней рассчитывается по формуле$$z=\alpha z_1+\beta z_2 +\gamma z_3.$$

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

Матрицы

Для выполнения преобразований векторов в пространстве мы будем использовать матричный метод. Матрицей размерности $$n\times n$$ называется таблица чисел вида$$A= \begin{pmatrix} a_{11} a_{12} \ldots a_{1n} \\ a_{21} a_{22} \ldots a_{2n} \\ \vdots \vdots \ddots \vdots \\ a_{n1} a_{n2} \ldots a_{nn} \end{pmatrix}.$$

В дальнейшем будем использовать сокращенную запись для матрицы: $$A=(a_{ij})$$. Строки матрицы $$A_i=(a_{i1},a_{i2},\ldots,a_in)$$ будем называть вектор-строками (поскольку каждая из них определяет вектор), а столбцы $$A^j$$ - вектор-столбцами. Матрицы являются эффективным инструментом для выполнения преобразований на плоскости и в пространстве. В этих случаях применяются матрицы размерности $$2\times 2$$ и $$3\times 3$$.

Сначала введем ряд операций над матрицами и векторами.

Пусть заданы матрицы $$A=(a_{ij})$$ и $$B=(b_{ij})$$. Суммой матриц называется матрица $$C=(c_{ij})$$, элементами которой являются $$c_{ij}=a_{ij}+b_{ij}$$.

Определим также операцию умножения матрицы на число. Результатом умножения матрицы $$A=(a_{ij})$$ на число $$\alpha$$ является матрица $$B=(b_{ij})$$, элементы которой $$b_{ij}=\alpha a_{ij}$$.

Произведением двух матриц $$A=(a_{ij})$$ и $$B=(b_{ij})$$ называется матрица $$C=(c_{ij})$$, элементы которой определяются следующим образом:$$c_{ij}=\sum_{k=1}^n a_{ik}b_{kj}.$$

Произведение матриц некоммутативно, т.е. в общем случае $$A\cdot B\ne B\cdot A$$.

Предыдущие определения мы вводили для матриц произвольной размерности. Следующие операции будут связаны с векторами, и мы будем подразумевать, что $$n=2$$ или $$n=3$$. Пусть задана матрица $$A=(a_{ij})$$ и вектор $$\overrightarrow{r}=(x_1,\ldots,x_n)$$. Результатом умножения матрицы на вектор является вектор $$\overrightarrow{r}_0=(x_1^0,\ldots,x_n^0)$$, координаты которого вычисляются как скалярное произведение строки матрицы на вектор:$$x_i^0=\sum_{k=1}^n a_{ik} x_k \equiv(A_i\cdot\overrightarrow{r}).$$

Если матрица $$B=(b_{ij})$$ получена из матрицы $$A=(a_{ij})$$ путем замены всех вектор-строк на вектор-столбцы, т.е. $$b_{ij}=a_{ji}, \; i, \; j=1,\ldots,n$$, то ее называют транспонированной матрицей $$A$$ и обозначают $$A^T$$.

Аналогичным образом определяется умножение вектора на матрицу, только в этом случае вектор скалярно умножается на вектор-строки матрицы. Матрица вида$$E= \begin{pmatrix} 1 0 \ldots 0 \\ 0 1 \ldots 0 \\ \vdots \vdots \ddots \vdots \\ 0 0 \ldots 1 \end{pmatrix}$$ называется единичной и обладает следующими свойствами:

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

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

Геометрические преобразования (перенос, масштабирование, вращение)

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

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

Сначала рассмотрим преобразования на плоскости, или двумерные преобразования.

Параллельный перенос объекта сводится к перемещению всех его точек на одно и то же расстояние $$d$$ в одном и том же направлении, заданном определенным вектором $$\overrightarrow{v}$$. Если этот вектор имеет длину $$d$$, то операция переноса может быть реализована путем сложения всех точек объекта с вектором $$\overrightarrow{v}$$. Довольно просто доказать, что при такой операции сохраняются расстояния между точками и, как следствие, углы между отрезками. Понятно также, что отрезки прямых перейдут в отрезки прямых. Поэтому при переносе многоугольника нет необходимости подвергать этой операции бесконечное множество точек, достаточно просто перенести вершины, а затем соединить их отрезками.

Масштабирование объекта можно реализовать путем умножения координат всех его точек на некоторое число. Пусть имеются точки с координатами $$(x_1,y_1)$$ и $$(x_2,y_2)$$, над которыми выполняется такое преобразование. Результатом будут новые точки с координатами $$(S_x x_1,S_y y_1)$$ и $$(S_x x_2,S_y y_2)$$. Если $$S_x=S_y=S_0$$, то несложно доказать, что обе точки переместятся вдоль прямых, проходящих через саму точку и начало координат, т.е. в направлении своего же радиус-вектора (рис. 3.5). При этом расстояние между новыми точками будет в $$S_0$$ раз отличаться от прежнего, но углы между отрезками сохранятся (это можно показать, если выразить косинус угла через скалярное произведение векторов). Ясно, что если коэффициент масштабирования $$S_0$$ больше единицы, соответствующий отрезок растягивается, а если меньше, то сжимается. Кроме того, при таком преобразовании объект смещается.

В случае, когда $$S_x\ne S_y$$, расстояния между точками изменятся неравномерно, поскольку растяжения в горизонтальном и вертикальном направлениях будут различными. Углы между отрезками также не сохранятся (рис. 3.6).

Вращения в плоскости перемещают точки по дуге окружности, центр которой находится в начале координат. Рассмотрим сначала движение одной точки при повороте на угол $$\alpha$$ (положительным является направление против часовой стрелки), т. е. поворот радиус-вектора на угол (рис. 3.7). Пусть точка располагалась на расстоянии $$r$$ от начала координат, а ее радиус-вектор составлял угол $$\beta$$ с осью абсцисс. Тогда координаты точки определяются формулами$$x=r\cos\beta, \quad y=r\sin\beta.$$

После поворота вектор будет составлять угол $$\beta+\alpha$$, а новые координаты точки будут определяться соотношениями$$\begin{aligned} x'=r\cos(\beta+\alpha)=r\cos\beta\cos\alpha-r\sin\beta\sin\alpha=x\cos\alpha-y\sin\alpha \\ y'=r\sin(\beta+\alpha)=r\sin\beta\cos\alpha+r\cos\beta\sin\alpha=x\sin\alpha+y\cos\alpha \end{aligned}.$$

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

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

При повороте относительно оси $$OX$$ на угол $$\alpha$$ у всех точек координата $$x$$ остается неизменной. Если смотреть на плоскость $$YOZ$$ со стороны конца оси $$OX$$, то оси будут расположены так, как показано на рис. 3.8. Положительным считается поворот от оси $$OY$$ к оси $$OZ$$. Если воспользоваться формулами для плоских поворотов, то координаты $$y'$$ и $$z'$$ новой точки определяются выражениями$$\begin{aliganed} y'=y\cos\alpha-z\sin\alpha \\ z'=y\sin\alpha+z\cos\alpha \end{eligned}.$$

Формулы поворота относительно оси $$OZ$$ полностью совпадают с теми, которые были выведены для плоского случая, а поворот относительно оси $$OY$$ выглядит так:$$\begin{aliganed} x'=x\cos\alpha+z\sin\alpha \\ z'=-x\sin\alpha+z\cos\alpha \end{eligned}.$$

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

Преобразования масштабирования и поворота на плоскости и в пространстве можно выразить с помощью матриц. Если заданы коэффициенты масштабирования $$S_x,S_y,S_z$$, то преобразование точки осуществляется посредством умножения матрицы на ее радиус-вектор,$$\overrightarrow{r}'=S\cdot\overrightarrow{r}= \begin{pmatrix} S_x 0 0 \\ 0 S_y 0 \\ 0 0 s_z \end{pmatrix} \begin{pmatrix} x \\ y \\ z \end{pmatrix} = \begin{pmatrix} S_x x \\ S_y y \\ S_z z \end{pmatrix}.$$ Двумерный случай выглядит подобным же образом.

Поворот на плоскости можно осуществить с помощью матрицы$$R= \begin{pmatrix} \cos\alpha -\sin\alpha \\ \sin\alpha \cos\alpha \end{pmatrix}.$$

И наконец, повороты в пространстве относительно осей координат можно выполнить с помощью трех матриц вращения$$\begin{gathered} R_x(\alpha)= \begin{pmatrix} 1 0 0 \\ 0 \cos\alpha -\sin\alpha \\ 0 \sin\alpha \cos\alpha \end{pmatrix}, \quad R_y(\alpha)= \begin{pmatrix} \cos\alpha 0 \sin\alpha \\ 0 1 0 \\ -\sin\alpha 0 \cos\alpha \end{pmatrix}, \\ R_z(\alpha)= \begin{pmatrix} \cos\alpha -\sin\alpha 0 \\ \sin\alpha \cos\alpha 0 \\ 0 0 1 \end{pmatrix} \end{gathered}$$

Нетрудно проверить, что для матриц вращения справедливо соотношение$$R(-\alpha)=R^{(-1)}(\alpha)$$

Для выполнения последовательных поворотов вокруг осей на углы $$\alpha,\beta,\gamma$$ можно создать матрицу преобразования путем перемножения трех матриц:$$R=R_z(\gamma)\cdot R_y(\beta)\cdot R_x(\alpha).$$

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

Переход в другую систему координат

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

Пусть единичные орты первой системы координат обозначаются $$\overrightarrow{i},\overrightarrow{j},\overrightarrow{k}$$, а оси координат - $$OX, OY, OZ$$. Введем еще одну систему координат, единичные орты которой обозначим $$\overrightarrow{e}_1,\overrightarrow{e}_2,\overrightarrow{e}_3$$, а оси координат - $$O'X', O'Y', O'Z'$$. Эта система имеет свое начало координат и свои направления осей. Считаем, что в обеих системах координат орты образуют левую тройку (рис. 3.9).

Сначала рассмотрим ситуацию, когда точка $$O'$$ совпадает с точкой $$O$$. Векторы $$\overrightarrow{e}_1,\overrightarrow{e}_2,\overrightarrow{e}_3$$ можно задать в первой системе координат, разложив их по векторам $$\overrightarrow{i},\overrightarrow{j},\overrightarrow{k}$$:$$\left. \begin{aligned} \overrightarrow{e}_1=e_x^1\overrightarrow{i}+e_y^1\overrightarrow{j}+e_z^1\overrightarrow{k} \\ \overrightarrow{e}_2=e_x^2\overrightarrow{i}+e_y^2\overrightarrow{j}+e_z^2\overrightarrow{k} \\ \overrightarrow{e}_3=e_x^3\overrightarrow{i}+e_y^3\overrightarrow{j}+e_z^3\overrightarrow{k} \end{aligned} \right\}.$$

Если в первой системе точка $$\overrightarrow{M}$$ имеет координаты $$(x,y,z)$$, а во второй системе - $$(x',y',z')$$, то, очевидно,$$x'\overrightarrow{e}_1+y'\overrightarrow{e}_2+z'\overrightarrow{e}_2=x\overrightarrow{i}+y\overrightarrow{j}+z\overrightarrow{k}.$$

Умножая скалярно это соотношение на векторы $$\overrightarrow{e}_1,\overrightarrow{e}_2,\overrightarrow{e}_3$$, получим связь между значениями координат в разных системах:$$\left. \begin{aligned} x'=e_x^1 x+ e_y^1 y +e_z^1 z \\ y'=e_x^2 x+ e_y^2 y +e_z^2 z \\ z'=e_x^3 x+ e_y^3 y +e_z^3 z \end{aligned} \right\}.$$

Эти соотношения можно записать в матричном виде$$\begin{pmatrix} x' // y' //z' \end{pmatrix} = \begin{pmatrix} e_x^1 e_y^1 e_z^1 // e_x^2 e_y^2 e_z^2 // e_x^3 e_y^3 e_z^3 \end{pmatrix} \cdot \begin{pmatrix} x // y //z \end{pmatrix},$$ или в векторной записи$$\overrightarrow{M}'=A\cdot\overrightarrow{M}.$$

Предположим, что вторая система координат получена из первой путем поворота на угол $$\varphi$$ относительно оси $$OY$$. Тогда$$\overrightarrow{e}_1=R_y(\varphi)\cdot \begin{pmatrix} 1 \\ 0 \\ 0 \end{pmatrix}= \begin{pmatrix} \cos\varphi \\ 0 \\ -\sin\varphi \end{pmatrix}, \quad \overrightarrow{e}_2=R_y(\varphi)\cdot \begin{pmatrix} 0 \\ 1 \\ 0 \end{pmatrix}= \begin{pmatrix} 0 \\ 1 \\ 0 \end{pmatrix}, \quad\\ \overrightarrow{e}_3=R_y(\varphi)\cdot \begin{pmatrix} 0 \\ 0 \\ 1 \end{pmatrix}= \begin{pmatrix} \sin\varphi \\ 0 \\ \cos\varphi \end{pmatrix},$$ следовательно$$A= \begin{pmatrix} \cos\varphi 0 -\sin\varphi \\ 0 1 0 \\ \sin\varphi 0 \cos\varphi \end{pmatrix} =R_y(-\varphi)=R_y^{-1}(\varphi).$$

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

Если новая система координат получена из старой путем сдвига на вектор $$\overrightarrow{l}=(l_x,l_y,l_z)$$, то очевидно, что новые координаты точки задаются формулами$$x'=x-l_x, \quad y'=y-l_y, \quad z'=z-l_z.$$

Теперь можно рассмотреть композицию двух преобразований системы координат - переноса и вращения. Тогда координаты точек преобразуются по формуле$$\overrightarrow{M}'=A\cdot(\overrightarrow{M}'-\overrightarrow{l}).$$

Задача вращения относительно произвольной оси

Вращение относительно произвольной оси также можно реализовать посредством умножения матрицы на вектор, но предварительно эту матрицу надо построить. Предположим, что прямая проходит через начало координат и задана единичным вектором $$\overrightarrow{l}=(l_x,l_y,l_z)$$, и требуется выполнить поворот точки на угол $$\alpha$$ относительно нее. Для этого воспользуемся следующим алгоритмом:

Итоговая матрица преобразования, таким образом, является произведением нескольких матриц, а именно$$R=R_x(\varphi)\cdot R_y(\psi)\cdot R_z(\alpha)\cdot R_y(-\psi)\cdot R_x(-\varphi).$$

Матрицы $$R_y(-\psi), R_x(-\varphi)$$ являются матрицами преобразования координат при поворотах системы координат, как было показано в предыдущем разделе. Определим сначала угол $$\varphi$$, который является углом между осью $$OZ$$ и его проекцией вектора $$\overrightarrow{l}$$ на плоскость $$YOZ \quad \overrightarrow{l}_1=(0,l_y,l_z)$$. Пусть $$d=\sqrt{l_y^2+l_z^2}$$ - длина этой проекции. Тогда $$\cos\varphi=\frac{l_z}{d}, \; \sin\varphi=-\frac{l_y}{d}$$, (синус отрицателен, поскольку поворот идет от оси $$OZ$$ к оси $$OY$$, т.е. в отрицательном направлении). После поворота системы координат новыми координатами вектора $$\overrightarrow{l}$$ будут $$l_x,0,d$$. Угол $$\psi$$ - это угол между векторами $$\overrightarrow{l}_1$$ и $$\overrightarrow{l}$$, поэтому $$\cos\psi=d, \sin\psi=l_x$$. Теперь мы можем выписать вид матриц преобразования координат для каждого шага алгоритма, учитывая то, что матрицы преобразования координат при повороте системы координат обратны по отношению к соответствующим матрицам вращения:$$R_x(\varphi)= \begin{pmatrix} 1 0 0 \\ 0 \frac{l_z}{d} -\frac{l_y}{d} \\ 0 \frac{l_y}{d} \frac{l_z}{d} \end{pmatrix}, \quad R_y(\psi=) \begin{pmatrix} d 0 -l_x \\ 0 1 0 \\ l_x 0 d \end{pmatrix}, \quad \\ R_z(\alpha)= \begin{pmatrix} \cos\alpha -\sin\alpha 0 \\ \sin\alpha \cos\alpha 0 \\ 0 0 1 \end{pmatrix}.$$

Нетрудно убедиться, что последовательное умножение матриц $$R_x(-\varphi)$$ и $$R_y(-psi)$$ на вектор $$\overrightarrow{l}$$ дадут в результате вектор $$(0,0,1)$$, т.е. этот вектор действительно станет осью аппликат.

Остается только выписать окончательный вид матрицы $$R$$ (для сокращения записи введем следующие обозначения: $$c=\cos\alpha, \; s=\sin\alpha, \; c_1=1-\cos\alpha$$ ):$$R= \begin{pmatrix} l_x^2+c l_x l_y c_1 - l_z s l_x l_z c_1 +l_y s \\ l_x l_y c_1 + l_z s l_y^2 c_1 + c l_y l_z c_1 - l_x s \\ l_x l_z c_1 - l_y s l_x l_z c_1 + l_x s l_z^2 c_1 + c \end{pmatrix}.$$

Напомним, что $$l_x, l_y, l_z$$ являются направляющими косинусами прямой, относительно которой выполняется поворот. Нетрудно убедиться, что если в качестве осей вращения взять оси координат, то мы в точности получим формулы (3.10).

Вопросы и упражнения