Математические основы компьютерной графики
Для того чтобы отображать графические объекты на дисплее нужно иметь некий инструмент, позволяющий легко и просто описывать эти объекты на языке математики. Положение точек на плоскости очень удобно описывать с помощью декартовой системы координат. Чтобы создать декартову систему координат нужно провести две прямые неколлинеарные линии, которые называют осями. Пусть они пересекаются в точке O, которую называют началом координат. Выберем на построенных осях единицу измерения. Тогда положение любой точки плоскости можно описать через координаты этой точки, которые представляют собой расстояния от начала координат до проекций точки на соответствующие оси координат. Проекцией точки на координатную ось называется точка пересечения прямой, проходящей через заданную точку и параллельной другой оси координат. Вообще введенные оси координат могут располагаться под произвольным углом (рис. 1.1).
Рис. 1.1.
Однако, на практике удобно пользоваться системой координат со взаимно перпендикулярными осями. Такая система координат называется ортогональной. Оси координат имеют названия; горизонтальная ось называется осью абсцисс (Ox), вертикальная – осью ординат (Oy). Таким образом, точка на плоскости представляется двумя своими координатами, что записывается в виде двумерного вектора P=(x,y).
Математический аппарат описания точек на плоскости с помощью декартовой системы координат идеально подходит для выполнения различных аффинных преобразований над точками (сдвиг, масштабирование, вращение).
Точку P(x,y), заданную на плоскости можно перенести (сдвинуть) в новую позицию путем добавления к координатам этой точки констант переноса. Для произвольной точки P=(x,y), которая перемещается в новую точку P'=(x',y'), сдвигаясь на Tx единиц параллельно оси абсцисс и на Ty единиц параллельно оси ординат, можно записать следующие выражения: x'=x+Tx, y'=y+Ty. Так, например, точка с координатами P(1,2) смещаясь на расстояние (5,7) преобразуется в точку P'(6,9). Определяя точку и перенос как вектор-строки P=(x,y), P'=(x',y') и T=(Tx,Ty) можно записать преобразование переноса (сдвига) в векторной форме: (x',y')=(x,y)+(Tx,Ty) или P'=P+T. Преобразованию можно подвергнуть не только одни точки. Геометрический объект можно переместить, применив к каждой его точке преобразование переноса. Так, если в описании объекта имеются отрезки прямой, то достаточно применить преобразование к концам отрезка и затем провести прямую линию между двумя преобразованными точками. Это правило справедливо и для операций масштабирования и поворота. На рис. 1.2 представлен результат действия на треугольник операции переноса на расстояние (2,-1).
Рис. 1.2.
Точки можно подвергнуть операции масштабирования (растяжения или сжатия) в Sx раз вдоль оси абсцисс и в Sy раз вдоль оси ординат. Полученные в результате новые точки будут выражаться как: x'=x*Sx;y'=y*Sy. Определив S как
Рис. 1.3.
Следует отметить, что операция масштабирования производится относительно начала координат. В результате преобразования объект может стать меньше/больше в размерах и ближе/дальше от начала координат. Пропорции объекта также могут измениться при масштабировании с различными коэффициентами:Sx
Точка плоскости P=(x,y) может быть повернута на произвольный угол
Рис. 1.4.
Выведем формулы для пересчета точки (x,y) в точку (x',y'). Обозначим расстояние от начала координат до точки P(x,y) через ?. Очевидно, что расстояние от начала координат до точки P'(x',y') также будет ?. Пусть Q и Q' - проекции точек P и P' соответственно на ось абсцисс. Тогда из прямоугольного треугольника OP'Q' и тригонометрических определений синуса и косинуса имеем:
Домножим правую и левую части уравнений на ?.
Используя простейшие тригонометрические свойства прямоугольного треугольника OPQ, следует заметить, что ?cos?=x, а ?sin?=y. Таким образом, формула "перевода" точки P(x,y) в точку P'(x',y') поворотом на угол
В матричном виде преобразование вращения будет выглядеть так:
Так треугольник с координатами вершин (20,0),(60,0),(40,100) после поворота на угол 45 градусов по часовой стрелке относительно начала координат (
Точка плоскости P(x,y) может быть легко отражена относительно прямых y=0, x=0, y=x следующим образом. Отражение относительно прямой y=0 (ось абсцисс) может быть получено с использованием матрицы
Подобным образом матрица отражения относительно прямой x=0 (ось ординат) будет иметь вид
Отражение относительно прямой y=x осуществляется с помощью матрицы
Рис. 1.5.
Рассмотренные выше аффинные преобразования переноса, масштабирования, вращения и отражения можно записать в матричной форме следующим образом: P'=P+T, P'=P*S, P'=P*R, P'=P*M, где P' - координаты преобразованной точки, P - координаты исходной точки, T - вектор сдвига (translate), S - матрица масштабирования (scale), R - матрица вращения (rotate), M - матрица отражения (mirror). К сожалению, операция переноса (сдвига) реализуется отдельно (с помощью сложения) от масштабирования, поворота и отражения (с помощью умножения). Тем не менее, существует возможность, чтобы все эти элементарные преобразования (перенос, масштабирование, вращение, отражение) можно было реализовать с помощью только операций умножения матриц. Данная возможность реализуется с помощью так называемых однородных координат точки.
Однородное представление двумерной точки (x,y) в общем случае имеет вид (wx wy w), где w - любой ненулевой скаляр, иногда называемый множителем. При этом если для точки задано ее представление в однородных координатах P(x y w), то найти ее двумерные координаты можно поделив первые две на скалярный множитель (x/w y/w). Вообще двумерное представление точки (x y w) есть ее проекция на плоскость w=1 (рис. 1.6).
Рис. 1.6.
Теперь точки плоскости можно описывать трехэлементным вектором, а матрицы преобразования должны иметь размер 3х3. В общем случае преобразование точки (x,y) в новую точку (x',y') можно представить следующим образом
Уравнения переноса (сдвига), масштабирования и вращения записываются в виде матриц преобразования однородных координат следующим образом:
где Tx,Ty - величины сдвига, Sx,Sy - масштабные множители,
Преимущество такого подхода (матричных формул) заключается в том, что совмещение последовательных элементарных преобразований при этом значительно упрощается. Рассмотрим следующую последовательность преобразований: масштабирование исходной точки P(x,y) при масштабных коэффициентах Sx и Sy, а затем смещение ее (после масштабирования) на Tx и Ty. Запишем преобразования масштабирования и переноса (сдвига) через однородные координаты точки:
Подставим первое уравнение во второе:
В результате получим
До сих пор мы рассматривали преобразования как перевод множества точек, принадлежащих объекту, в некоторое другое множество точек, причем оба эти множества описаны в одной и той же системе координат. Другими словами система координат у нас оставалась неизменной, а сам объект преобразовывался относительно начала координат. Эквивалентным способом описания преобразования является смена системы координат. Такой подход оказывается полезным и удобным, когда необходимо собрать вместе много объектов, каждый из которых описан в своей собственной локальной системе координат, и выразить (пересчитать) их координаты в одной глобальной (мировой) системе координат. Например, точка на рис. 1.7 описана в четырех системах координат, и имеет соответствующие координаты: (11,10), (8,8), (12,10), (3,3)
Рис. 1.7.
Преобразование из системы координат 1 в систему координат 2 есть
Для введения трехмерной декартовой системы координат проведем три направленные взаимно перпендикулярные прямые линии, называемые осями, так чтобы они пересекались в одной точке – начале координат. Выберем на осях единицу измерения. Тогда положение любой точки пространства можно описать через координаты этой точки, которые представляют собой расстояния от начала координат до проекций точки на соответствующие оси. Такая система координат называется ортогональной. Таким образом, положение точки P в пространстве описывается ее координатами: P=(x,y,z). Взаимное расположение координатных осей в ортогональной системе трехмерного пространства может быть двух видов. При добавлении третьей оси к двумерной системе координат ось Oz можно направить как от наблюдателя в плоскость листа, так и от плоскости листа к наблюдателю.
Рис. 1.8.
В первом случае систему координат принято называть левосторонней, во втором – правосторонней. Известен способ определения типа системы по ладоням. Так для левой ладони большой (ось Y), указательный (ось Z) и средний (ось X) пальцы образуют левую тройку ортогональных векторов.
В трехмерном пространстве значительно возрастает разнообразие геометрических объектов. При работе на двумерной плоскости мы рассматривали отрезки, плоские кривые и многоугольники. При переходе в трехмерное пространство это многообразие примитивов можно рассматривать в разных плоскостях, а также здесь появляются пространственные кривые: ?(t)=[x(t),t(t),z(t)], t?[a,b]. Помимо всего прочего в трехмерном пространстве присутствуют пространственные объекты – участки криволинейных поверхностей и объемные тела – параллелепипеды, эллипсы, тетраэдры и др.
При работе в трехмерном пространстве возникает проблема описания формы объектов. На практике получили широкое распространение три основных типа моделей трехмерных объектов: описание объекта поверхностями, сплошными телами и с помощью проволочной сетки. При первом подходе объект представляется в виде тонких поверхностей, под которым находится пустое незаполненное пространство. Примером такого объекта может выступать неразбитая скорлупа совершенно пустого внутри яйца. Поверхность объекта может быть описана различными математическими моделями. Поверхности, заданные в виде x=x(u,v),y=y(u,v),z=z(u,v), где u,v - параметры, изменяющиеся в заданных пределах, относятся к классу параметрических. Для одной фиксированной пары значений u,v можно вычислить положение только одной точки поверхности. Для полного представления всей поверхности необходимо с определенным шагом перебрать множество пар u,v из диапазона их изменений, вычисляя для каждой пары значение XYZ в трехмерном пространстве. Очень широкое распространение получили параметрические бикубические поверхности, с помощью которых достигается непрерывность составной функции и ее первых производных (функция, составленная из нескольких смежных бикубических участков, будет обладать непрерывностью и гладкостью в местах стыковки). Основным преимуществом параметрического описания является возможность построения объекта с очень сложной и замысловатой формой. Недостатком такого способа описания являются большие вычислительные затраты при построении поверхностей. Частным случаем параметрических поверхностей являются поверхности первого порядка. Из таких поверхностей можно составить описание формы объекта типа полигонального поля. Такими полями называют серию смежных многоугольников, не имеющих разрывов между собой. Каждое ребро такого поля является общим для смежных многоугольников. В результате чего составная функция, описывающая поверхность, обладает непрерывностью, а производная имеет разрывы в местах стыка
участков поверхностей. В настоящее время полигональный способ описания трехмерных объектов является одним из самых распространенных и востребованных. Так, например, производительность современных графических процессоров (видеокарт) определяется количеством выводимых полигонов в единицу времени, как правило, в секунду.
Еще один способ описания поверхностей, который следует упомянуть, заключается в представлении формы объекта множеством отдельных точек, принадлежащих этой поверхности. Теоретически при бесконечном увеличении числа точек такая модель обеспечивает непрерывную форму описания. Точки, используемые для описания, должны располагаться достаточно близко друг к другу, чтобы можно было воспринять поверхность без грубых потерь и искажений. Поточечное описание поверхностей применяют в тех случаях, когда поверхность очень сложна, не обладает нужной гладкостью, а детальное представление многочисленных геометрических особенностей важно для практики.
Описание объекта сплошными геометрическими конструктивами (твердотельное моделирование) заключается в представлении сложного объекта в виде объединения простых объемных примитивов. Обычно такие примитивы включают кубы, цилиндры, конусы, эллипсоиды и другие подобные формы. Булевы операции над примитивами позволяют достигать объединения, вычитания и выделения общих частей примитивов. Структуры данных модели этого вида идентичны бинарному дереву, причем узлы (нетерминальные вершины) дерева являются операторами над примитивами, а листья – примитивами.
Следует также отметить метод описания объекта с помощью проволочной сетки (wire-frame), суть которого заключается в представлении поверхности серией пересекающихся линий, принадлежащих поверхности объекта. Как правило, в качестве таких линий принято использовать отрезки прямых. Достоинством проволочного представления является простой и эффективный способ построения объектов.
Для наилучшего восприятия формы объекта необходимо иметь его представление в трехмерном пространстве. Как правило, наглядное представление об объекте можно получить с помощью выполнения операций вращения и переноса, а также путем построения его проекций. Как и двумерном случае, существует три основных преобразования в трехмерном пространстве: перенос (изменение положения), изменение масштаба и вращение.
Преобразование перемещения точки трехмерного пространства P=(x,y,z) в новую точку P'=(x',y',z') можно записать следующим образом: x'=x+Tx, y'=y+Ty, z'=z+Tz, где Tx,Ty,Tz - величины перемещения в направлениях x,y,z соответственно. Определяя точку и операцию переноса как вектор-строку P=(x,y,z), P'=(x',y',z'),T=(Tx,Ty,Tz), преобразование сдвига можно записать в векторной форме: (x',y',z')=(x,y,z)+(Tx,Ty,Tz) или P'=P+T.
Точку трехмерного пространства P=(x,y,z) можно подвергнуть операции масштабирования (растяжения или сжатия) в Sx раз по оси абсцисс, в Sy раз по оси ординат и в Sz раз по оси аппликат. Полученная в результате преобразованная точка P'=(x',y',z') будет выражаться как: x'=x*Sx,y'=y*Sy,z'=z*Sz. Определив S как матрицу
азуемая точка отдаляется от начала координат, если же Sx,Sy,Sz<1 то точка приблизится к началу координат.
Трехмерные преобразования вращения являются более сложными, чем их двумерные аналоги. В данном случае необходимо дополнительно задать ось вращения. Рассмотрим сначала простейшие случаи, когда ось вращения совпадает с одной из координатных осей.
Найдем матрицу поворота вокруг оси OZ на угол ?. Будем записывать матрицу преобразования для левосторонней системы координат. Следует отметить, что в левосторонней системе координат положительными будут повороты, выполняемые по часовой стрелке, если смотреть с конца положительной полуоси в направлении начала координат (рис. 1.9).
Рис. 1.9.
В данном случае ось поворота перпендикулярна к плоскости рисунка, и поскольку мы используем левостороннюю систему координат, то вращение вокруг оси OZ сводится к повороту точки на плоскости XOY на угол ?. При этом координата z точки вращения не изменяется. Таким образом, формулу поворота точки (x,y,z) вокруг оси OZ на угол ? можно записать следующим образом:
Изменим теперь положение координатных осей левосторонней системы координат таким образом, чтобы ось OY была направлена в плоскость рисунка. Тогда положительная полуось OZ будет направлена горизонтально вправо, а положительная полуось OX - вертикально вверх (рис. 1.10).
Рис. 1.10.
Получить формулу вращения точки вокруг оси OY на угол ? можно заменив x на z, y на x в формуле двумерного поворота. При этом координата точки y при таком вращении не изменяется. В результате чего формула вращения точки (x,y,z) вокруг оси OY на угол ? будет иметь следующий вид:
Аналогично поступаем с осью вращения OX. Изменим положение координатных осей так, чтобы ось OX была направлена в плоскость рисунка, ось OY - горизонтально вправо, ось OZ - вертикально вверх (рис. 1.11).
Рис. 1.11.
Заменив в формуле двумерного поворота y на z, x на y, получим формулу вращения точки (x,y,z) вокруг оси OX на угол
Способ двумерного плоского вращения вокруг произвольной точки может быть обобщен на случай вращения вокруг произвольной оси трехмерного пространства. Пусть произвольная ось вращения задается вектором
Рис. 1.12.
Вращение вокруг задаваемой оси (вектора
- Перенос вектора так, чтобы начало вектора (точка) совпала с началом системы координат. Это осуществляется с помощью операции сдвига T(-a,-b,-c);
- Поворот вокруг оси OY на угол ? так, чтобы вектор (m,l,n) оказался в плоскости OYZ: ;
- Поворот вокруг оси OX на угол так, чтобы вектор (m',l',n') совпал с осью OZ:;
- Поворот вокруг оси OZ на заданный угол ?: Rx(?);
- Выполнение преобразования, обратного, произведенному на шаге 3. Т.е. поворот вокруг оси OX на угол -;
- Выполнение преобразования, обратного, произведенному на шаге 2. Т.е. поворот вокруг оси OY на угол -?;
- Выполнение преобразования, обратного, произведенному на шаге 1. Т.е. сдвиг на вектор (a,b,c):T(a,b,c)
Данный алгоритм вращения вокруг произвольной оси можно записать с помощью произведения серии элементарных матриц:
Остается определить чему равны углы поворотов
Рис. 1.13.
Из простых тригонометрических соотношений можно получить следующие формулы:
Как видно, операции трехмерного масштабирования и вращения могут быть реализованы с помощью умножения вектор-строки (точки) на матрицу преобразования. Операция же сдвига реализуется через сложение двух вектор-строк. Аналогично тому, как все двумерные преобразования (сдвиг, масштабирование и вращение) описываются матрицами размером 3х3 (через однородные координаты), трехмерные преобразования могут быть представлены в виде матриц размером 4х4. И тогда точка трехмерного пространства (x,y,z) записывается в однородных координатах как Wx,Wy,Wz,W, где W
Уравнения трехмерного поворота, масштабирования и вращения записываются в виде матриц преобразования однородных координат следующим образом:
где Tx,Ty,Tz - величины сдвига по осям OX, OY, OZ соответственно, Sx,Sy,Sz - масштабные множители по OX,OY,OZ соответственно,
Как и в двумерном случае, матричный подход позволяет совместить два или более элементарных преобразования в одно. Таким образом, последовательное применение двух преобразований
Процесс вывода трехмерной графической информации по существу является более сложным, чем соответствующий двумерный процесс. Сложность, характерная для трехмерного случая, обуславливается тем, что поверхность вывода не имеет графического третьего измерения. Такое несоответствие между пространственными объектами и плоскими изображениями устраняется путем введения проекций, которые отображают трехмерные объекты на двумерной проекционной картинной плоскости. В процессе вывода трехмерной графической информации мы задаем видимый объем в мировом пространстве, проекцию на картинную плоскость и поле вывода на видовой поверхности. В общем случае объекты, определенные в трехмерном мировом пространстве, отсекаются по границам трехмерного видимого объема и после этого проецируются. То, что попадает в пределы окна, которое само является проекцией видимого объема на картинную плоскость, затем преобразуется в поле вывода и отображается на графическом устройстве. В общем случае операция проекции преобразует точки, зада нные в системе координат размерности n, в точки системы координат размерности меньшей, чем n. В нашем случае точка трехмерного пространства отображается в двумерное пространство. Проекция трехмерного объекта строится при помощи прямых проецирующих лучей, которые называются проекторами и которые выходят из центра проекции, проходят через каждую точку объекта и, пересекая картинную плоскость, образуют проекцию. На рис. 1.14 представлены две различные проекции одного и того же отрезка и проекторы, проходящие через его конечные точки.
Рис. 1.14.
Определенный таким образом класс проекций известен под названием плоских геометрических проекций, т.к. проецирование осуществляется на плоскость, а не на искривленную поверхность и в качестве проекторов используют прямые линии. Плоские геометрические проекции можно подразделить на два основных класса: центральные (перспективные) и параллельные (ортогональные). Различие между ними определяется соотношением между центром проекции и проекционной плоскостью. Так, если расстояние между ними, конечно, то проекция будет центральной, если же оно бесконечно, то – параллельной. При описании центральной проекции мы явно задаем ее центр проекции, в то время как для параллельной проекции мы указываем лишь направление проецирования. Центр проекции порождает визуальный эффект, аналогичный тому, к которому приводят фотографические системы и используется в случаях, когда желательно достичь некоторой степени реализма. Следует заметить, что размер центральной проекции объекта изменяется обратно пропорционально расстоянию от центра проекции до объекта. Параллельная проекция порождает менее реалистичное изображение, т.к. отсутствует перспективное "укорачивание" объекта. Проекция фиксирует истинные размеры объекта, и параллельные линии остаются параллельными.
В общем случае задача получения центральной проекции заключается в том, чтобы определить проекцию точки объекта, расположенную в произвольном месте трехмерного пространства, на некоторую плоскость в этом же пространстве, называемую картинной. Нахождение центральной проекции является частным случаем задачи определения пересечения луча L с плоскостью
Рис. 1.15.
В машинной графике задача вычисления центральной проекции, как правило, сильно упрощена. В данном случае центр проекции, который также называют точкой зрения, находится на одной из осей системы координат, картинная (проекционная) плоскость перпендикулярна оптической оси. Как правило, точку зрения (центр проекции) располагают на оси OZ, тогда картинная плоскость будет параллельна плоскости OXY системы координат (рис. 1.16).
Рис. 1.16.
В нашем случае точка C=(0,0,c) - центр проекции (положение наблюдателя), плоскость z=0 - картинная плоскость. Пусть точка P=(x,y,z) имеет проекцию P'=(x',y',0). Рассмотрим два подобных треугольника CPQ и CP'Q', и запишем отношение катетов:
Если теперь c
Следующим шагом необходимо спроецированное изображение перевести в координаты экрана. Это можно проделать следующим образом:
Существует связь однородных координат с операцией центральной и параллельной проекциями, которая может быть выражена так:
Для перехода от однородных координат к обычным, необходимо разделить все компоненты точки на четвертую координату:
Для параллельной проекции матрица преобразования будет иметь вид:
Таким образом, шаг проецирования можно описать в терминах матричной операции умножения. В результате этого мы можем объединить вместе операции преобразования объекта (сдвиг, масштабирование, вращение) и операцию проецирования в одну общую матрицу преобразования. Аналогично можно поступить с приведением спроецированных точек к экранным координатам:
Таким образом, все операции преобразования объекта трехмерного пространства на картинную плоскость (экран) можно описать в терминах матричных умножений.
