геометрические преобразования. Геометрические преобразования в компьютерной графике
 Скачать 1.14 Mb.
|
|
b a a* b* Проекторы, сходящиеся в центре V V x z Пирамида видимости z x V a* b* a b Параллелепипед видимости Проекторы, параллельные оси z Картинная плоскость Рисунок 1 – Иллюстрация перспективного преобразования пространства 17 Для затенения примитива, то есть моделирования его освещения некоторым источником света анализируется угол между лучом света и нормалью к примитиву. В результате описанного перспективного преобразования луч света становится вектором, параллельным оси глубины СКН, а нормаль к примитиву вычисляется или устанавливается принудительно. Вычисление нормалей к примитивам различной формы достаточно подробно описано в учебном пособии [1]. Вычисление освещенности для каждой точки примитива выполняется на этапе растрирования. Полученные нормали к примитивам используются для определения видимости этих примитивов наблюдателем, или, как часто называют эту операцию, – для отбраковки нелицевых примитивов. Нелицевыми называются примитивы, повернутые к наблюдателю своей тыльной частью. Они принадлежат стороне объекта, противоположной наблюдателю и потому ему не видны. Следовательно, в процессе обработки примитивов они должны быть выявлены и отброшены. Анализ видимости примитива идет по углу между лучом зрения, направленным на некоторую точку (вершину) примитива, и нормалью, проведенной через эту точку. Прямой или тупой угол говорит о принадлежности примитива к нелицевым. Лицевые примитивы могут входить в пирамиду (параллелепипед) видимости полностью или частично. Во втором случае они подвергаются отсечению. В процессе отсечения части примитивов, выходящие за пределы окна видимости, отбрасываются. В результате образуются новые примитивы с другими границами. Для выполнения такого отсечения разработан целый ряд эффективных алгоритмов, например, алгоритмы Коэна-Сазерленда, Сазерленда-Ходжмена, Лианга-Барски. Список 18 лицевых примитивов, полностью попадающих в окно видимости, вместе с атрибутами их освещенности передается на этап растеризации. Обзор операций, образующих конвейер рендеринга, показывает, что значительное место среди них составляют геометрические преобразования. Они применяются при определении положения объектов в отдельности и сцены в целом, а также в процессе отсечения объектов и нахождения их образов на картинной плоскости. 2 ГЕОМЕТРИЧЕСКИЕ ПРЕОБРАЗОВАНИЯ НА ПЛОСКОСТИ 2.1 Аффинные преобразования Под компьютерной графикой на плоскости, или двумерной компьютерной графикой понимают отображение на экране плоских, то есть двумерных объектов. В двумерной графике нет необходимости в операциях проецирования и наложения теней, так как объект плоский и расположен в одной плоскости – плоскости экрана. К геометрическим преобразованиям плоских объектов относятся сдвиг, поворот, масштабирование и отражение в плоскости экрана. Эти преобразования относятся к так называемым аффинным преобразованиям. Напомним, что аффинной (общей декартовой) системой координат называется декартова система координат, в которой единицы масштаба (единицы отсчета) на координатных осях в общем случае различны. Если в плоскости введены две аффинные системы координат, то преобразование, ставящее в соответствие точке P в одной системе координат точку P во второй системе координат и притом такую, которая 19 во второй системе координат имеет такие же координаты, как и точка P в первой системе координат, называется аффинным. Аффинные преобразования сохраняют прямолинейность и параллельность линий, углы между ними, а также функциональные зависимости между параметрами геометрических фигур. В компьютерной графике обычно применяются декартовы прямоугольные системы координат. В них точка на плоскости описывается парой координат x, y. При наличии в плоскости нескольких координатных систем перевод точки из одной системы в другую, в общем случае, описывается системой уравнений: , , 0 22 21 0 12 11 y y t x t y x y t x t x (2.1) где x, y – координаты точки в «старой», а x , y – в «новой» системе координат; t ij , x 0 , y 0 – числа, связанные неравенством 0 22 21 12 11 t t t t Приведенные выражения имеют и другой геометрический смысл. Они описывают новые координаты точки после выполнения над ней ряда геометрических преобразований в одной системе координат. Числа t ij , x 0 , y 0 описывают параметры конкретных преобразований, но определить их значения для желаемого вида преобразований весьма затруднительно. В аффинных преобразованиях плоскости особую роль играют несколько важных частных случаев, для которых числовые коэффициенты уравнений перевода имеют ясный геометрический смысл. Это уже названные сдвиг, поворот, масштабирование и отражение. 20 Преобразование сдвига устанавливает соответствие между координатами точки в двух координатных системах, одна из которых сдвинута относительно другой на расстояние x 0 по горизонтали и y 0 по вертикали. Применительно к компьютерной графике преобразование сдвига переводит координаты точки объекта из СКО (xOy) в СКН (в систему координат экрана x O y ) при перемещении объекта: , , 0 0 y y y x x x где x 0 , y 0 – координаты начала системы xOy в системе x O y Преобразование поворота (или – вращения) устанавливает соответствие между координатами точки объекта и экраном (СКН) при вращении объекта (без сдвига) относительно начала координат: , cos sin , sin cos y x y y x x где – угол поворота СКО в СКН. Другими словами, если центры СКО и СКН совпадают, то точка объекта, имеющая в СКО координаты x, y, при повороте объекта на угол примет в СКН координаты x , y в соответствии с приведенными выражениями. Преобразование масштабирования увеличивает или уменьшает размер изображения объекта в СКН по сравнению с исходным размером в СКО. При масштабировании назначается точка, относительно которой производится преобразование (неподвижная точка преобразования). Масштабирование относительно начала координат описывается уравнениями , , y k y x k x y x 21 где k x , k y 0 – коэффициенты преобразования по координатным осям. При k x, y 1 происходит увеличение изображения, при k x, y 1 – уменьшение, а при k x k y форма изображения искажается. Преобразование отражения (симметрии) формирует в СКН изображение объекта, симметричное исходному. Отражение относительно оси, проходящей через начало координат СКН под углом к оси абсцисс, описывается уравнениями: 2 cos 2 sin , 2 sin 2 cos y x y y x x Геометрическая иллюстрация частных аффинных преобразований представлена на рисунке 2. Как видно, все они «привязаны» к началу СКН и потому являются частными вариантами общего случая, представленного выражениями (2.1). P* x* p x* x p y p y* p P 0* y* x* x p y p P 0* y* y* p P* x* p x* p x* x p y p y* p P 0* y* x f y x x p P 0* y Y* 0 x* 0 P y p y* p x* p x* y* a б в г Рисунок 2 – Иллюстрация частных аффинных преобразований сдвига (а), поворота (б), масштабирования (в) и отражения (г) 22 Удобно записывать аффинные преобразования в матричной форме. Во-первых, можно компактно описывать сложные преобразования как сочетание (суперпозицию) простых. Во-вторых, в технических средствах компьютерной графики заложены возможности быстрого выполнения матричных операций (программно или аппаратно). Матричная запись в общем виде должна выглядеть так: , T y x y x (2.2) где T – матрица геометрического преобразования. Для получения результирующих координат x , y нужно умножить матрицу-строку y x на матрицу T. Матрицу T можно получить из системы уравнений (2.1), она может выглядеть только как транспонированная матрица коэффициентов этих выражений: 0 0 22 12 21 11 y x t t t t T Однако приведенный вид матрицы невозможен для матричного умножения (2.2). Поскольку не совпадают размерности перемножаемых матриц, получить исходные выражения перевода их перемножением нельзя. Для установления соответствия размерностей в выражении (2.2) матрицы- строки y x y x , должны иметь три элемента, то есть точка на плоскости должна описываться тремя координатами. Это возможно при использовании так называемых однородных координат. 2.2 Однородные координаты. Матричное представление аффинных преобразований Однородным представлением n-мерного объекта в математике, в общем случае, называют его представление в (n+1)-мерном пространстве, 23 полученное добавлением еще одной координаты – скалярного множителя. Однородные координаты на плоскости определяются следующим образом. Пусть на плоскости в аффинной системе координат задана точка P с координатами (x, y). Однородными координатами этой точки называется любая тройка одновременно не равных нулю чисел [w 1 w 2 w 3 ], связанных с координатами точки P соотношениями: , 3 2 3 1 y w w x w w (2.3) Безразмерное число w 3 называется скалярным множителем. Геометрически можно пояснить однородные координаты точки на плоскости, представив точку в некоторой условной пространственной системе координат (x,y,w), как это показано на рисунке 3. P (xh,yh,h) ’’ P (x,y, ) ’ 1 P(x,y) y x x w 1 0 y w=1 Экр ан Рисунок 3 – Иллюстрация однородных координат точки на плоскости 24 Точку P(x,y) может представлять тройкой своих координат w 1 , w 2 , w 3 произвольная точка на прямой, соединяющей начало координат О (0, 0, 0) с точкой P (x, y, 1). В частности, и точка P однозначно определяет точку P, а также и любая точка P c координатами (xh, yh, h), где h – скалярный множитель. В этом можно убедиться, воспользовавшись выражениями (2.3). Такое описание точки на плоскости называется в компьютерной графике описанием в однородных координатах. Представляют точку обычно так: (x : y : 1), то есть принимают h=1 , но применяют и общую форму: (w 1 : w 2 : w 3 ). Чтобы отличить однородное описание точки на плоскости (три координаты – w 1 , w 2 , w 3 ) от привычного описания точки в декартовом пространстве (тоже три координаты – x, y, z), однородные координаты в описании точки разделяют не запятой, а двоеточием, например, A(x A :y A :1). Это правило не относится к матричному описанию точки, так как в математике знаки препинания между элементами матриц не ставятся, например, K A =| x A y A 1|. Теперь аффинное преобразование в общем виде будет выглядеть следующим образом: 1 0 0 1 1 0 0 22 12 21 11 y x t t t t y x y x или K = K T, (2.4) где обозначения очевидны. Перемножение матриц K и T даст два основных уравнения (2.1) перевода точки из СКО в СКН и верное числовое равенство 1=1. Следовательно, при помощи троек однородных координат и матриц третьего порядка можно описать любое частное аффинное преобразование. 25 Так, матрица преобразований для сдвига (translation – перенос) принимает вид: , 1 0 1 0 0 0 1 0 0 y x TR для вращения (rotation) – , 1 0 0 0 cos sin 0 sin cos RT для масштабирования (scaling) – , 1 0 0 0 0 0 0 y x m m SC и для отражения (reflection) – 1 0 0 0 2 cos 2 sin 0 2 sin 2 cos RF Отметим, что последняя матрица принимает более простой вид, если описывает отражение относительно оси x (α=0) или оси y (α=90°). Справедливость представленных матриц можно проверить, подставив их в (2.4) и выполнив умножение. В результате получатся выражения аффинных преобразований в алгебраической форме. Пользуясь матрицами частных аффинных преобразований, можно описать более сложные преобразования, представив их в виде последовательности частных аффинных преобразований [2]. 26 Пример 1. Пусть требуется описать поворот точек объекта на угол вокруг произвольного центра С с координатами x c , y c Применить матрицу поворота RT нельзя, так как она описывает поворот относительно начала координат, а в задании требуется повернуть точку вокруг некоторого центра С. Значит, чтобы использовать RT, нужно сначала разместить начало координат СКН в точке С или, что то же самое, переместить точку С в начало СКН. При этом точка объекта (x : y : 1) также изменит свои координаты. Чтобы найти ее координаты после сдвига, используется матрица TR. Теперь можно описывать поворот точки объекта с помощью матрицы RT. Однако предварительный сдвиг исказит результат преобразования поворота. Чтобы этого не произошло, нужно после поворота выполнить обратный сдвиг (возврат) системы координат, чтобы точка С вновь заняла свое место. Вместе с ней изменит свои координаты и повернутая точка объекта. Для нахождения ее новых координат применяется матрица сдвига с обратными значениями смещений по координатным осям. Таким образом, поворот объекта (каждой его точки) вокруг произвольного центра представляется в виде последовательности следующих действий: сдвиг центра вращения в начало СКН, поворот объекта на угол вокруг начала координат и сдвиг центра вращения в исходное положение. В итоге возникает описание , 1 0 1 0 0 0 1 1 0 0 0 cos sin 0 sin cos 1 0 1 0 0 0 1 1 1 C C C C y x y x y x y x или в «свернутом» виде: 2 1 TR RT TR K K Произведение (суперпозиция) трех матриц частных аффинных преобразований представляет собой текущую матрицу геометрического Сдвиг Поворот Возврат 27 преобразования. Она может быть вычислена, подставлена в выражение (2.4) и использована для нахождения координат всех точек графического объекта при его повороте. Пример 2. Пусть требуется найти точку P , симметричную точке P относительно некоторого центра С(x c , y c ). В задании требуется выполнить преобразование центральной симметрии (относительно точки), а частное преобразование отражения описывает осевую симметрию (относительно прямой). Однако центральную симметрию можно представить как результат двух последовательных преобразований осевой симметрии: сначала относительно горизонтальной оси, затем – относительно вертикальной. При этом обе оси должны проходить через центр симметрии. Так как матрица RF «работает» только относительно осей, проходящих через начало координат, перед симметрией нужно предусмотреть сдвиг центра С в начало СКН. Очевидно, после преобразований симметрии нужно предусмотреть возврат точки С на свое старое место (еще один сдвиг). В результате для выполнения задания нужно выполнить следующий ряд преобразований: 1 0 1 0 0 0 1 1 0 0 0 1 0 0 0 1 1 0 0 0 1 0 0 0 1 1 0 1 0 0 0 1 1 1 C C C C P P P P y x y x y x y x Две средние матрицы суперпозиции (матрицы симметрии) можно поменять местами, но в остальном последовательность записи матриц имеет принципиальное значение. |