ОСНОВНЫЕ ТЕОРЕТИЧЕСКИЕ ПОЛОЖЕНИЯ

1.  Системы  координат
 
Системы координат – это совокупность правил, ставящих в соответствие каждому объекту (точке) набор чисел (координат) (x1, y1), (x2, y2), (x3, y3). Число координат, требуемое для определения точки, определяет размерность пространства. Например, если точка A (см. рис. 1) определяется двумя координатами (x1, y1), то мы имеем дело с двумерным пространством.



Рисунок 1 - Двумерное пространство.                            Рисунок 2 - Трехмерное пространство.
 
Если же точка A (см. рис. 2) определяется тремя координатами (x1, y1, z1), пространство будет трехмерным.
В компьютерной графике применяются классические координатные системы: декартова, аффинная, полярная, цилиндрическая, сферическая, однородная.
 
Декартовые двумерные системы координат.
Декартовыми прямоугольными координатами точки P в двумерном пространстве называются взятые с определенным знаком расстояния (выраженные в единицах масштаба) этой точки до двух взаимно перпендикулярных координатных осей или, что то же самое, проекции радиус-вектора r точки P на две взаимно перпендикулярные координатные оси (рис.1).
 
Полярные системы координат.
Полярными координатами точки P называются радиус-вектор ρ - расстояние от точки P до заданной точки O (полюса) и полярный угол φ - угол между прямой OP и заданной прямой, проходящей через полюс (полярной осью). Полярный угол считается положительным при отсчете от полярной оси против часовой стрелки и отрицательным при отсчете в обратную сторону. Координатные линии в полярных системах - окружности с центром в полюсе и лучи (рис.3).
Формулы для перехода от полярных координат к декартовым:
x=ρ*cos(φ)
y=ρ*sin(φ)
и обратно:
ρ=sqrt(x2+y2)
φ=arctg(y/x)=arcsin(y/ρ)
 
 
 

Рисунок 3 - Полярные системы координат
 
Цилиндрические и сферические системы координат применяются только в трехмерной графике.
 
В литературе по компьютерной графике используют также (в зависимости от способа представления графических данных) следующие разновидности координатных систем: локальные, глобальные, мировые, приборные и другие.
Локальная система координат – дву- или трехмерная система собственных координат объекта. В ней производится моделирование объекта. В частных случаях локальная система координат может быть декартовой, аффинной, полярной и т.д.
Глобальная система координат – дву- или трехмерная система координат, в которой описывается взаимосвязь между объектами, например, их взаимное расположение. В частных случаях система может быть декартовой, аффинной, полярной и т. д.
Мировая система координат – дву- или трехмерная система координат, которая является входной системой координат базисных графических систем. Она используется для описания изображений.
Приборная система координат – двумерная прямоугольная система координат, в которой изображение выводится на экран монитора или планшет графопостроителя. Обычно, это декартова система координат.
Однородная система координат - координатная система, которая позволяет представить n-мерный объект в n+1-мерном пространстве. Возникает закономерный вопрос: "Для чего это нужно? ". Чтобы ответить на него, необходимо детальнее рассмотреть одну из операций по преобразованию объекта, например, операцию переноса. Суть операции состоит в том, что преобразуемый объект изменяет свое местоположение, а его форма и размеры должны оставаться неизменными. Иными словами, в ходе операции переноса к координатам вершин исходного двумерного объекта прибавляются параметры переноса, входящие в состав матрицы видового преобразования [1, 2].
Рассмотрим сказанное на примере. Пусть исходный объект представляет собой произвольную точку  A(x, y), заданную в двумерной системе координат. Необходимо перенести ее на  l единиц вдоль оси X и на  m единиц вдоль оси Y, воспользовавшись матрицей переноса второго ранга
Из (1) видно, что перенос выполнен не корректно. В правильно выполненном переносе выходная матрица должна иметь вид:
 
                                        [Mвых]=[x+l    y+m]                                                                                                              (2)
 
Для того чтобы получить результат операции переноса таким, как показано в (2), необходимо изменить исходную декартову прямоугольную систему координат. Проблема решается введением новой системы так называемых однородных координат по следующему алгоритму:
1) на координатной плоскости  XOY выбирается произвольная точка  A(x, y);
2) из начала координат восстанавливается перпендикуляр  h  к плоскости  XOY;
3) через точку  h = 1  проводится плоскость, параллельная плоскости  XOY;
4) из точки  A  восстанавливается перпендикуляр до пересечения с плоскостью h = 1;
5) в результате получим точку  A'(x, y, 1), которая однозначно соответствует точке A, поскольку их координаты  x, y одинаковы по условию;
6) соединим точку  O с  A'  вектором  OA';
7) если через любую точку, взятую на этом векторе, провести плоскость, параллельную плоскости XOY, то пересечение перпендикуляра, восстановленного из точки  A  с этой плоскостью, дает образ точки A в однородных координатах - Ah(hx, hy, h). Нормировка этих координат на множитель  h  переводит точку  Ah  в точку A', однозначно соответствующую точке  A.
Рисунок 4 иллюстрирует перечисленные операции по вводу однородных координат.


 
Рисунок 4 - Однородные координаты
 
Таким образом, перевод  n–мерного пространства в  n+1–мерное осуществляется путем добавления еще одной координаты – скалярного числа h. Теперь, пользуясь однородной системой координат, снова выполним операцию переноса, добавив еще одну строку в матрице видового преобразования для согласования операции матричного умножения.


 
Из (3) видно, что перенос выполнен корректно. Однако требуется дополнительная модернизация матрицы видового преобразования. Проблема заключается в том, что преобразующая матрица в соотношении (3) не квадратная. По этой причине для нее нельзя получить обратную матрицу, которая часто используется во многих разделах компьютерной графики. Таких, например, как "Удаление невидимых ребер и граней в трехмерных объектах", "Построение собственных и падающих теней трехмерных объектов" и др. Модернизация матрицы видового преобразования сводится к добавлению третьего столбца, в котором элементы  a13  и  a23  нулевые, aэлемент a33  равен единице. Перепишем (3) с учетом сказанного:

  
Теперь задача переноса двумерных объектов полностью решена.
Кроме переноса однородные координаты широко используются в проективной геометрии в связи с необходимостью описывать бесконечно удаленные точки пространства и рассчитывать точки схода в перспективных проекциях. Однородные координаты позволяют записывать любые видовые преобразования в удобной матричной форме, а также избегать переполнения разрядной сетки ЭВМ за счет нормализации чисел.
Напомним, что если в третьем столбце выходной матрицы  [МВЫХ] появились в результате преобразования числа, отличные от единицы, то в этом случае, для перехода к декартовым координатам, необходима нормировка каждого элемента каждой строки на эти числа, порядок выполнения которой будет рассмотрен далее.
 
2 Форматы  описания  графических объектов
 
Под форматом описания графического объекта понимается способ задания его местоположения в пространстве в математической форме.
В свою очередь, описание самого пространства зависит от принятой системы координат. Для однородной двумерной системы координат, используемой в 2D-графике, принято задавать координаты в виде матрицы, размером n × 3, например:


 
Здесь, параметры матрицы x и y – это координаты вершин объекта по осям X и Y.
Количество строк матрицы (n) соответствует количеству вершин объекта. Каждая вершина занимает свою строку.
Параметр третьего столбца является масштабирующим множителем, применяемым в однородной системе координат и равен единице для приведенного общего случая после нормализации.
 
3 Матричные видовые  преобразования
 
Под базовыми видовыми преобразованиями двумерных объектов подразумеваются преобразования, которые можно выполнить за один шаг с помощью конкретной матрицы видового преобразования.
Математически преобразование исходных координат объекта с помощью матрицы видового преобразования производится по формуле:
 
Мисх * Тпр = Мрез                                                                                (6)
Мисх - это матрица исходных координат графической фигуры. В развернутой форме после преобразования она приобретает следующий вид:

  
Матрица видового преобразования Тпр в общем виде имеет следующее представление:
 
 
Здесь каждый параметр матрицы отвечает за свой, и только свой вид преобразования.
Различают следующие виды преобразования графических объектов:
- перенос (параметры l, m);
- масштабирование (параметры a, e, s);
- зеркальное отображение относительно осей или начала координат (параметры a, e, s);
- сдвиг (параметры b, d);
- проецирование (параметры p, q);
- вращение вокруг осей координат (параметры a, b, d, e).
Далее, в лабораторной работе №2 будет подробно рассмотрена работа каждого из параметров видового преобразования.

4  Преобразование графических  объектов  с  использованием
  результирующих матриц
 
Как уже говорилось в предыдущем параграфе преобразование координат графических объектов с помощью матриц преобразования заключается в перемножении матрицы исходных координат на матрицу видового преобразования. Если преобразования комбинированные, т.е. являются совокупностью нескольких преобразований, то для таких случаев составляется результирующая матрица Трез. Тогда процесс преобразования будет иметь вид:
 
Мисх * Трез = Мрез                                                                               (9)
 
Результирующие матрицы преобразования двумерных объектов (Трез) представляют собой комбинации из нескольких базовых матриц видовых преобразований, например переноса, масштабирования, отображения, сдвига или вращения. Количество и состав входящих матриц определяется конкретным видом преобразования и может быть абсолютно любым.
Приведем примеры получения результирующих матриц:
Для переноса и масштабирования:                                    Трез = Тпер ×  Тмашт                                                                                                                                       (10)
 
Для вращения относительно произвольного центра:             Трез = Тпер.пр. ×  Твращ ×  Тпер.обр.                                                                                         (11)
 
     Для отображения относительно произвольного отрезка:       Трез = Тпер.пр. ×  Твращ.пр. ×  Тотобр ×  Твращ.обр. ×  Тпер.обр.             (12)
 
Перемножение матриц проиводится по правилам матричного анализа (см. параграф 5) и например, для (12) результат перемножения в развернутом виде будет иметь вид:
 
 
Развернутые матрицы для (10) и (11) приведены в теоретических разделах лабораторных работ 2 и 3 при рассмотрении принципов их практического применения.
 
5.  Матричные  операции
 
Все видовые преобразования графических объектов, задаваемых в виде матриц, выполняются по правилам матричного анализа.
К ним относятся такие операции как:
- сложение и вычитание;
- умножение матриц;
- вычисление определителей матриц;
- обращение матриц.
 
5.1. Определение матриц.
Матрица – это прямоугольный массив чисел. Числа, которые составляют матрицу, называются ее элементами. Элементы образуют строки и столбцы внутри матрицы. Если число строк и столбцов одинаково, то матрица называется квадратной. Рассмотрим квадратную матрицу размерностью 4×4, заданную в общем виде:
 
 
Первый индекс элемента относится к строке матрицы, а второй – к столбцу. Например,  a34  представляет собой элемент, расположенный на пересечении третьей строки и четвертого столбца.
Матрица, состоящая из m  строк и  n  столбцов, является матрицей порядка  m×n. В приведенной выше квадратной матрице m=n=4. Элементы a11, a22, a33, a44 называются диагональными элементами. Сумма диагональных элементов в квадратной матрице называется следом. У нулевой матрицы все элементы равны нулю [5].
Единичной матрицей называется квадратная матрица, каждый элемент которой равен нулю, за исключением диагональных элементов, равных единице. Например, единичная матрица порядка 3×3 имеет вид:

  
Две матрицы считаются равными только в том случае, когда каждый элемент одной матрицы равен соответствующему элементу другой.
 
5.2. Матричные операции.
Сложение и вычитание матриц. Если две матрицы имеют одинаковый порядок, то допустимо их сложение и вычитание. Для того чтобы сложить или вычесть две матрицы, необходимо сложить или вычесть каждые два соответствующих элемента этих матриц. Например,
 
 
Умножение матриц. Умножение матриц – это наиболее часто используемая операция при выполнении видовых преобразований в компьютерной графике. Рассмотрим матрицу порядка m1 × n1 и матрицу порядка m2 × n2. Для умножения этих матриц необходимо, чтобы величина n1 была равна m2. Это означает, что число столбцов первой матрицы должно быть равно числу строк второй матрицы.
Покажем на примере правила умножения матриц. Если A – матрица порядка  4×3  и  B – матрица порядка 3×3, то матричное произведение определяется следующей операцией:
 
 
Заметим, что матрица порядка 4×3, умноженная на матрицу порядка 3×3, дает матрицу порядка 4×3. В общем случае, матрица порядка  m1 × n1, умноженная на матрицу порядка  m2 × n2,  где  m1 = n2, дает матрицу порядка  m1 × n2.
Операция матричного умножения не коммутативна. Это означает, что в общем случае  ABBA,  т.е. важен порядок выполнения матричного умножения.
Матричные операции подчиняются первому и второму дистрибутивным законам:


A(B + C) = AB + AC            и           (A + B)C = AC + BC                                                                                  (19)
 
и ассоциативному закону:
 
A(BC) = (AB)C                                                                                                                                                         (20)
 
Приведем числовой пример матричного умножения:
 
 
5.3. Определитель квадратной матрицы. Определитель квадратной матрицы A обозначается через |A|. Покажем на примере квадратной матрицы размера 3×3 один из методов вычисления определителя - по правилу треугольников. Пусть задана квадратная матрица третьего ранга в общем виде. Необходимо найти ее определитель.
 
 
Правило треугольников гласит: определитель матрицы третьего ранга равен сумме произведений элементов главной диагонали и произведений элементов, образующих треугольники со сторонами параллельными главной диагонали минус произведение элементов вспомогательной диагонали и минус произведения элементов, образующих треугольники со сторонами параллельными вспомогательной диагонали.
В развернутом виде операция нахождения определителя представляется посредством соотношений (23) и (24). В верхней левой части (10) показана схема, по которой в правиле треугольников вычисляются произведения элементов определителя со знаком "+", а в (24) приведена схема, по которой в правиле треугольников вычисляются произведения элементов определителя со знаком "-" [6].
 
 
Пример 1. Вычислим определитель матрицы:
 
1) разложением по элементам первой строки
 

 
2) по правилу треугольников:
 
detT = 9 + 144 + 120 – 8 – 162 –120 = 153 – 170 = –17                                                                      (26)
 
Убеждаемся в идентичности полученных результатов.
 
5.4. Обращение матриц. Выше упоминалось, что в компьютерной графике часто используются обратные матрицы. Например, дано матричное уравнение:
 
[A][X] = [B]                                                                                        (27)
 
в котором неизвестна матрица [X]. Поскольку операция деления в матричной алгебре не определена, то матрицу [X] находят следующим образом:
1. Выполняют умножение левой и правой частей уравнения (27) на матрицу [A]–1, обратную матрице [A]
 
[A]–1[A][X] = [A]–1 [B]                                                                      (28)
 
2. Известно, что произведение прямой и обратной матриц дает единичную матрицу [E], которая, будучи умноженной на любую величину, не изменяет ее значения.
3. Поэтому в соотношении (28) произведение прямой и обратной матриц не учитывается и неизвестная матрица [X] оказывается найденной
 
[X] = [A]–1[B]                                                                                     (29)
 
Существует много способов нахождения обратных матриц. Приведем одну из формул для определения элементов обратной матрицы  [B]–1, если дана прямая матрица [B] [3]:
              
 
В знаменателе (30) стоит определитель исходной матрицы, а в числителе - определители дополнений транспонированной матрицы [B]T.
Элементы матрицы [B]–1 не определенны, если det[B]=0. В этом случае матрица [B] называется вырожденной.

 
Пример 2.
Дана матрица третьего ранга:
                                                             
 
Найти обратную ей матрицу [B]–1.
 
Решение.
1. Находим по правилу треугольников определитель матрицы [B

                                    
2. Транспонируем матрицу [B]:
                                                 
             
3. Рассчитываем по соотношению (30) элементы обратной матрицы


 
Обратная матрица запишется:

                                               

4. Проверяем ее корректность:

                                             

Убеждаемся, что обратная матрица найдена правильно.