Компьютерная геометрия

1. Компьютерная геометрия

1. Двумерные преобразования

 

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

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

Для начала заметим, что точки на плоскости задаются с помощью двух ее координат. Таким образом, геометрически каждая точка задается значениями координат вектора относительно выбранной системы координат. Координаты точек можно рассматривать как элементы матрицы [x,y], т. е. в виде вектор-строки или вектор-столбца. Положением этих точек управляют путем преобразования матрицы.

Точки на плоскости xy можно перенести в новые позиции путем добавления к координатам этих точек констант переноса:

.

Таким образом, для перемещения точки на плоскости надо к матрице ее координат прибавить матрицу коэффициентов преобразования.

Рассмотрим результаты матричного умножения матрицы [x,y], определяющей точку Р, и матрицы преобразований 2´2 общего вида:

.

Проведем анализ полученных результатов, рассматривая x* и y* как преобразованные координаты. Для этого исследуем несколько частных случаев.

Рассмотрим случай, когда a = d = 1 и c = b = 0. Матрица преобразований приводит к матрице, идентичной исходной:

.

При этом изменений координат точки Р не происходит.

Если теперь d = 1, b = c = 0, a = const, то:

.

Как видно, это приводит к изменению масштаба в направлении х, так как х*=ах. Следовательно, данное матричное преобразование эквивалентно перемещению исходной точки в направлении х.

Теперь положим b = c = 0, т. е.

.

В результате получаем изменение масштабов в направлениях x и y. Если a ≠ d, то перемещения вдоль осей неодинаковы. Если a = d >1, то имеет место увеличение масштаба координат точки Р. Если 0 < a=d <1, то будет иметь место уменьшение масштаба координат точки Р.

Если a или (и) d отрицательны, то происходит отображение координат точек. Рассмотрим это, положив b = c = 0; d = 1 и а = -1, тогда

.

Произошло отображение точки относительно оси у. В случае b = c = 0, a  = 1, d = -1, отображение происходит относительно оси х. Если b = c = 0, a = d  < 0, то отображение будет происходить относительно начала координат.

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

Теперь рассмотрим случай, когда a = d = 1, а  с = 0, т. е.

.

Координата х точки Р не изменяется, в то время как у* линейно зависит от начальных координат. Этот эффект называется сдвигом. Аналогично, когда a = d = 1, b = 0, преобразование осуществляет сдвиг пропорционально координате у.

Заметим, что преобразование общего вида, примененное к началу координат, не приведет к изменению координат точки (0,0). Следовательно, начало координат инвариантно при общем преобразовании. Это ограничение преодолевается за счет использования однородных координат.

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

Преобразование единичного квадрата

Четыре вектора положения точек единичного квадрата с одним углом в начале координат записываются в виде

Применение общего матричного преобразования к единичному квадрату приводит к следующему:

.

 

Рис. 3.1. Преобразования единичного квадрата

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

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

 

Рис. 3.2. Вращение единичного квадрата

Как следует из рис. 3.2, точка В с координатами (1,0) преобразуется в точку В*, для которой х*=(1)cos q и y=(1)sin q, а точка D, имеющая координаты (0,1) переходит в точку D* с координатами x*=(-1)sin q и y*=(1)cos q.

Матрица преобразования общего вида записывается так:

.

Для частных случаев. Поворот на 90° можно осуществить с помощью матрицы преобразования

.

Если использовать матрицу координат вершин, то получим, например:

.

Поворот на 180° получается с помощью матрицы .

Отображение

В то время как чистое двумерное вращение в плоскости xy осуществляется вокруг оси, перпендикулярной к этой плоскости, отображение определяется поворотом на 180° вокруг оси, лежащей в плоскости ху.

Такое вращение вокруг линии у = х происходит при использовании матрицы .

Преобразованные новые выражения определяются соотношением

.

Вращение вокруг у = 0 получается при использовании матрицы

.

 

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

 

Преобразования переноса, масштабирования и поворота записываются в матричной форме в виде

,

,

.

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

.

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

  ,

откуда следует, что константы т, п вызывают смещение х* и y* относительно х и у. Поскольку матрица 3´2 не является квадратной, она не имеет обратной матрицы. Эту трудность можно обойти, дополнив матрицу преобразования до квадратной размером 3´3. Например,

.

Заметим, что третья компонента векторов положения точек не изменяется при добавлении третьего столбца к матрице преобразования. Используя эту матрицу в соотношении, получаем преобразованный вектор [х* у* 1]. Добавление третьего элемента к вектору положения и третьего столбца к матрице преобразования позволяет выполнить смещение вектора положения. Третий элемент здесь можно рассматривать как дополнительную координату вектора положения. Итак, вектор положения [х  у 1] при воздействии на него матрицы 3´3 становится вектором положения в общем случае вида [X Y Н]. Представленное преобразование было выполнено так, что [X Y Н]  = [х* у* 1].

Преобразование, имеющее место в трехмерном пространстве, в нашем случае ограничено плоскостью, поскольку H = 1. Если, однако, третий столбец   матрицы преобразования Т размера 3 х 3 отличен от 0, то в результате матричного преобразования получим [х у 1] =[Х Y Н], где Н ¹ 1.

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

Итак, найденные х* и у* получены с помощью пучка лучей, проходящих через начало координат. Результат преобразований показан на рис. 3.3.

 

Рис. 3.3. Геометрическое представление однородных координат

 

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

.

Представление двумерного вектора трехмерным или в общем случае n-мерного вектора (п + 1)-мерным называют однородным координатным воспроизведением. При однородном координатном воспроизведении n-мерного вектора оно выполняется в (п + 1)-мерном пространстве, и конечные результаты в n-мерном пространстве получают с помощью обратного преобразования. Таким образом, двумерный вектор [х у] представляется трехкомпонентным вектором . Разделив компоненты вектора на однородную координату h, получим

 и  .

Не существует единственного однородного координатного представления точки в двумерном пространстве. Например, однородные координаты (12, 8, 4), (6, 4, 2) и (3, 2, 1) представляют исходную точку [3 2]. Для простоты вычислений выбираем [х у 1], чтобы представить непреобразованную точку в двумерных однородных координатах. Преобразование

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

.

Выполнение указанных выше преобразований показывает, что Х = х*, Y = у*, а Н = 1. Равенство единице дополнительной координаты означает, что преобразованные однородные координаты равны исходным координатам.

В общем случае Н ¹ 1, и преобразованные обычные координаты получаются за счет нормализации однородных координат, т. е.

 и  .

Геометрически все преобразования х и у происходят в плоскости Н = 1 после нормализации преобразованных однородных координат.

Преимущество введения однородных координат проявляется при использовании матрицы преобразований общего вида порядка 3´3

,

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

Чтобы показать воздействие третьего столбца матрицы преобразований 3´3, рассмотрим следующую операцию:

;

здесь Х = х, Y = у, а Н = рх + qy + 1. Переменная Н, которая определяет плоскость, содержащую преобразованные точки, представленные в однородных координатах, теперь образует уравнение плоскости в трехмерном пространстве.

Это преобразование показано на рис. 3.4, где линия АВ, лежащая в плоскости ху, спроектирована на линию CD плоскости рХ + qY —Н + 1 = 0.

Рис. 3.4. Преобразование линии в однородных координатах

На рисунке величина р = q = 1.Выполним нормализацию для того, чтобы получить обычные координаты:

,

Полагая р = q = 1, для изображенных на рисунке точек А и В с координатами соответственно (1, 3) и (4, 1) получим

 и  .

После преобразования А в С* и В в D* имеем

 и  .

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

Результатом нормализации является перевод трехмерной линии CD в ее проекцию C*D* на плоскость Н = 1. Как показано на рисунке, центром проекции является начало координат.

Основная матрица преобразования размером 3´3 для двумерных однородных координат может быть подразделена на четыре части:

.

Как мы видим, а, b, с и d осуществляют изменение масштаба, сдвиг и вращение; т и п выполняют смещение, а р и q — получение проекций. Оставшаяся часть матрицы, элемент s, производит полное изменение масштаба. Чтобы показать это, рассмотрим преобразование

Здесь Х = х, Y = у, а Н = s. Это дает х* = x/s и y* == y/s. В результате преобразования [х у 1 ] —> [x/s y/s 1] имеет место однородное изменение масштаба вектора положения. При s < 1 происходит увеличение, а при s > 1 — уменьшение масштаба.

 

2. Двумерное вращение вокруг произвольной оси

 

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

.

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

 

Предположим, что центр изображения имеет координаты (4, 3) и желательно повернуть изображение на 90° против часовой стрелки вокруг центральной его оси. Действие, выполненное с помощью матрицы

,

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

.

Затем следует применить матрицу вращения и, наконец, привести результаты к началу координат посредством обратной матрицы. Вся операция

   

может быть объединена в одну матричную операцию путем выполнения матричных преобразований вида

.

В результате будет получено х* =Х/Н и у* = Y/H. Двумерные вращения около каждой оси ортогональной системы представлены на рис. 3.5.