Программирование математических объектов (стр. 4 из 6)

[ 3 ] [ 6 ]

Операция векторного произведения: определена для (n-1) вектора одинакового размера n. Результат - вектор, причем, перпендикулярный всем множителям.

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

Формально определяется как определитель матрицы, первая строка которой есть все базисные вектора, а все последующие - соответствующие координаты всех множителей. Поскольку она необходима только для 3D пространства, мы определим векторное произведение двух 3D векторов явно:

[ Ax ] [ Bx ] | i j k | [ Ay*Bz-Az*By ]

AxB = [ Ay ] x [ By ] = | Ax Ay Az | = [ Az*Bx-Ax*Bz ]

[ Az ] [ Bz ] | Bx By Bz | [ Ax*By-Ay*Bx ]

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

[ 1 x 500 ] [ 8 a 3 ] [ 9 a+x 503 ]

[ 2 y 600 ] + [ 9 b 2 ] = [ 11 b+y 602 ]

[ 3 z 700 ] [ 10 c 1 ] [ 13 c+z 701 ]

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

Операция умножения двух матриц: определена для двух матриц таких размеров a*b и c*d, что b = c. Например, если b = c, но a ¹ d, то при перестановке множителей операция будет вообще не определена. Результатом умножения матрицы A размером a*b на матрицу B размером b*d будет матрица C размером a*d, в которой элемент, стоящий в строке i и столбце j, равен произведению строки i матрицы A на столбец j матрицы B. Произведение строки на столбец определяется как сумма произведений соответствующих элементов строки и столбца. Например, умножение строки на столбец (они должны быть равной длины, поэтому и такие ограничения на размеры матриц):

[ 4 ]

[ 1 2 3 ] * [ 5 ] = 1*4 + 2*5 + 3*6 = 32

[ 6 ]

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

[ 1 2 3 ] [ 0 3 ] [ 1*0+2*1+3*2 1*3+2*4+3*5 ]

[ 4 5 6 ] * [ 1 4 ] = [ 4*0+5*1+6*2 4*3+5*4+6*5 ] = ...

[ 7 8 9 ] [ 2 5 ] [ 7*0+8*1+9*2 7*3+8*4+9*5 ]

Умножение и сложение матриц обладают почти тем же набором свойств, что и обычные числа, хотя некоторые привычные свойства не выполняются (например, A*B ¹ B*A); на самом деле требуется знать, что произведение вида A*B*C*D*... не зависит от того, как расставить скобки. Или, что

A*(B*C) = (A*B)*C.

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

Перенос точки (точки будут также рассматриваться как вектора с началом в начале координат и концом в собственно точке) с координатами (x,y,z) на вектор (dx,dy,dz) делается простым сложением всех координат. То есть результат - это (x+dx,y+dy,z+dz). Подобно сложению вектора-точки с вектором-переносом.

Рассмотрим для примера поворот точки (x,y,z) относительно оси z. В этом случае z не меняется, а (x,y) меняются так же, как и при 2D повороте относительно начала координат.

Покажем координаты точки A' - результата поворота A(x,y) на угол alpha (рис. 4).

Рисунок 4

Пусть r = sqrt(x*x+y*y). Пусть угол AOx равен phi, тогда из рисунка видно, что cos(phi) = x/r, sin(phi) = y/r. Угол A'OA равен по условию alpha. Отсюда

x' = r*cos(alpha+phi) = r*(cos(alpha)*cos(phi)-sin(alpha)*sin(phi)) =

= (r*cos(phi))*cos(alpha)-(r*sin(phi))*sin(alpha) =

= x*cos(alpha)-y*sin(alpha)

y' = r*sin(alpha+phi) = r*(cos(alpha)*sin(phi)+sin(alpha)*cos(phi)) =

= (r*cos(phi))*sin(alpha)+(r*sin(phi))*cos(alpha) =

= x*sin(alpha)+y*cos(alpha)

Для трехмерного случая, таким образом

x' = x*cos(alpha)-y*sin(alpha)

y' = x*sin(alpha)+y*cos(alpha)

z' = z

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

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

[ x' ] = [ cos(alpha) -sin(alpha) 0 ] [ x ]

[ y' ] = [ sin(alpha) cos(alpha) 0 ] [ y ]

[ z' ] = [ 0 0 1 ] [ z ]

То есть поворот на угол alpha задается одной и той же матрицей, и с помощью этой матрицы (умножая ее на вектор-точку) можно получить координаты повернутой точки. С одной стороны умножение матрицы на вектор требует больше операций, чем расчет x' и y' по формулам.

Нос другой удобство матриц для заключается как раз в свойстве

A*(B*C) = (A*B)*C. Пусть делается несколько поворотов подряд, например, пять (столько, сколько надо для поворота относительно произвольной оси), и пусть они задаются матрицами A, B, C, D, E (A - матрица самого первого поворота, E - последнего). Тогда для вектора p мы получаем

p' = E*(D*(C*(B*(A*p)))) = E*D*C*B*A*p = (E*D*C*B*A)*p = (E*(D*(C*(B*A))))*p = T*p,

где T = (E*(D*(C*(B*A)))) матрица преобразования, являющегося комбинацией пяти поворотов. Посчитав один раз эту матрицу, можно в дальнейшем применить довольно сложное преобразование из пяти поворотов к любому вектору с помощью всего одного умножения матрицы на вектор.

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

На самом деле, эти преобразования тоже легко записываются в виде матриц. Только вместо матриц 3x3 и 3-мерных векторов используются так называемые однородные 4-мерные координаты и матрицы 4x4. При этом вместо векторов вида

[ x ]

[ y ]

[ z ]

используются вектора вида

[ x ]

[ y ]

[ z ]

[ 1 ]

а вместо произвольных матриц 3x3 используются матрицы 4x4 такого вида:

[ a b c d ]

[ e f g h ]

[ i j k l ]

[ 0 0 0 1 ]

Видно, что если d = h = l = 0, то в результате применения всех операций получается то же самое, что и для матриц 3x3.

Матрица параллельного переноса теперь определяется как

[ 1 0 0 dx ]

[ 0 1 0 dy ]

[ 0 0 1 dz ]

[ 0 0 0 1 ]

Матрицу масштабирования можно определить и для матриц 3x3, и для матриц 4x4:

[ kx 0 0 ] [ kx 0 0 0 ]

[ 0 ky 0 ] или [ 0 ky 0 0 ]

[ 0 0 kz ] [ 0 0 kz 0 ]

[ 0 0 0 1 ]

где kx, ky, kz - коэффициенты масштабирования по соответствующим осям.

Таким образом, получаем следующее. Любое нужное нам преобразование пространства можно задать матрицей 4x4 определенной структуры, разной для разных преобразований. Результат последовательного выполнений нескольких преобразований совпадает с результатом одного преобразования T, которое также задается матрицей 4x4, вычисляемой как произведение матриц всех этих преобразований. Важен порядок умножения, так как A*B ¹ B*A. Результат применения преобразования T к вектору [ x y z ] считается как результат умножения матрицы T на вектор [ x y z 1 ].

Докажем на примере, что A*B ¹ B*A. Пусть A - матрица переноса, B - поворота. Если сначала перенести объект, а потом повернем относительно центра координат (это будет B*A), то результат не будет соответствовать результату, при котором сначала объект поворачивают, а затем переносят (A*B).

5.2 Создание одноцветного треугольника

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

Нужно отсортировать вершины так, чтобы вершина A была верхней, C - нижней, тогда min_y = A.y, max_y = C.y, и надо обойти все линии от min_y до max_y. Рассмотрим какую-то линию sy, A.y <= sy <= C.y. Если sy < B.y, то она пересекает стороны AB и AC; если sy >= B.y - то стороны BC и AC. Известны координаты всех вершин, поэтому можно написать уравнения сторон и найти пересечение нужной стороны с прямой y = sy. Получим два конца отрезка. Так как не известно, какой из них левый, а какой правый, нужно сравним их координаты по x и обменяем значения, если нужно. Рисуя этот отрезок, повторяя процедуру для каждой строки - получаем треугольник.

Рассматривая более подробно пересечения прямой

y = sy (текущей строки) и стороны треугольника, например AB, Получим уравнение прямой AB в форме x = k*y+b:

x = A.x+(y-A.y)*(B.x-A.x)/(B.y-A.y)

Теперь надо подставить известное для текущей прямой значение y = sy:

x = A.x+(sy-A.y)*(B.x-A.x)/(B.y-A.y)

Для других сторон пересечение ищется совершенно точно так же. Например:

// ...

// здесь сортируем вершины (A,B,C)

// ...

for sy = A.y to C.y begin

x1 = A.x + (sy - A.y) * (C.x - A.x) / (C.y - A.y);

if (sy < B.y)Then

x2 = A.x + (sy - A.y) * (B.x - A.x) / (B.y - A.y);

else

x2 = B.x + (sy - B.y) * (C.x - B.x) / (C.y - B.y);

if (x1 > x2) Then

begin

tmp = x1; x1 = x2; x2 = tmp;

end;

drawHorizontalLine(sy, x1, x2);

end;

Необходимо защититься от случая, когда B.y = C.y - в этом (и только этом, потому как если C.y = A.y, то треугольник пустой и рисовать его не нужно, или можно рисовать горизонтальную линию; а если B.y = A.y, то sy >= A.y и до деления на B.y - A.y не дойдет) случае произойдет попытка деления на ноль.

// ...

// здесь сортируем вершины (A,B,C)

// ...

for sy = A.y to C.y begin

x1 = A.x + (sy - A.y) * (C.x - A.x) / (C.y - A.y);

if (sy < B.y)

x2 = A.x + (sy - A.y) * (B.x - A.x) / (B.y - A.y);

else begin

if (C.y == B.y)

x2 = B.x;

else

x2 = B.x + (sy - B.y) * (C.x - B.x) / (C.y - B.y);

end;

if (x1 > x2)Then

begin

tmp = x1; x1 = x2; x2 = tmp;

drawHorizontalLine(sy, x1, x2);

end;

// ...

Здесь drawHorizontalLine(sy, x1, x2) - горизонтальная линия. Её создание не представляет сложности и код будетвыглядеть так.

//...

For i:=x1 to x2 do

PutPixel(i,sy,Color);

//...

6. Программа

unit graph3;

interface

uses Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,

DXClass, DXDraws, StdCtrls,graph, Menus,graph3D,figures, Buttons;

const Mode:Word=0;

type TLab = class(TForm)

Vid: TDXDraw;

Timer: TDXTimer;

Enter: TButton;

Menu: TMainMenu;

N1: TMenuItem;

N2: TMenuItem;

N3: TMenuItem;

N4: TMenuItem;

N5: TMenuItem;

N6: TMenuItem;

N7: TMenuItem;

N8: TMenuItem;

N9: TMenuItem;