Конспект лекций с дисциплины «Компьютерная графика» для направления подготовки 0910 “Компьютерная инженерия”




НазваниеКонспект лекций с дисциплины «Компьютерная графика» для направления подготовки 0910 “Компьютерная инженерия”
страница6/19
Дата публикации10.03.2013
Размер0.99 Mb.
ТипКонспект
uchebilka.ru > Информатика > Конспект
1   2   3   4   5   6   7   8   9   ...   19
^

2.32.3 ГЕОМЕТРИЧЕСКИЕ ПРЕОБРАЗОВАНИЯ




2.3.1 2.3.1 Основные математические операции



Геометрические преобразования в МГ как правило связаны с матрицами. Напомним основные понятия матричного исчисления. М а т р и ц а - это таблица коэффициентов размерностью

Элементы называют элементами матрицы.

Операции с матрицами.

1. Две матрицы А = и В = размера ( ) равны друг другу ( А = В) в том и только в том случае, если aik = bik .

2. Сумма двух матриц A = и B = размера () есть матрица размера ():
A + B = + =

A + B = + =
3. Произведение матрицы А = размера ( ) на скаляр u есть матрица размера ( ):

=
4. Произведение матрицы А = размера ( ) на матрицу
B = размера () есть матрица размера () :

C = =

где
* =
Более подробные сведения по матричным операциям можно получить в любой литературе по матричным вычислениям.


^

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



Одна из наиболее распространенных задач МГ заключается в определении местоположения пикселя после его поворота, сдвига, масштабирования.

П е р е н о с .

Точки на плоскости Х, У переносятся в новые позиции путем добавления констант к их координатам. Для каждой точки ^ Р(х,у), которая перемещается в точку Р'(х',у') путем сдвига на Dx единиц по оси Х и на Dy единиц по оси У, записываются уравнения :

X'= X + Dx Y'= Y + Dy (2.12)

На Рис. 2.13 показана точка с координатами (3,3) и перемещенная точка с координатами (8,7). Если определить вектор - строки

Р = [X Y] Р' = [X' Y'] T = [ Dx Dy ],

то уравнение (3.12) перепишется в виде:

[X' Y'] = [X Y] + [Dx Dy] (2.13)

или

Р' = Р + T (2.14)

Рис. 2.13. Перенос точки и объекта
Если речь идет о переносе объекта, то уравнение (2.12) применяется к каждой его точке. Однако, при использовании относительных координат можно перенести только его начальную точку (заданную, например, процедурой MoveTo модуля Graf Турбо-Паскаля), а при использовании абсолютных координат перенести только конечные точки отрез ков (Рис.2. 13 б, в).

М а с ш т а б и р о в а н и е. Точку можно "промасштабировать" с коэффициентом Sx вдоль оси Х и с коэффициентом Sy вдоль оси У:

X' = X * Sx Y' = Y * Sy (2.15)

Определив S как



тогда можно записать в матричной форме :

[ X' Y'] = [ X Y] (2.16)

или

Р' = Р* S (2.17)



Рис.2.14. Масштабирование точки и объекта
На Рис.2.14 а) отдельная точка Р (3,2) масштабируется с коэффициентами Sx=3 и Sy= 2,5 . Следует заметить, что масштабирование осуществляется относительно начала координат, что вызывает не только изменение масштаба изображения объекта, но и изменение его положения относительно начала координат (Рис.2. 14 б, в).

П о в о р о т. Точки могут быть повернуты на угол относительно начала координат, как показано на Рис.2. 17. Математически поворот точки определяется следующим образом:

(2.18)

или, в матричной форме:

[X' Y'] = [X Y] * (2.19)

или

Р' = Р* R (2.20)

где R - матрица поворота.

При повороте объекта уравнение (2.18) или (2.19) необходимо применять к каждой точке объекта. При задании объекта примитивами преобразование производится над конечными точками примитивов (Рис.2. 15 б, в).

При повороте положительными считаются углы, измеряемые против



Рис. 2.15 Поворот точки и объекта
движения часовой стрелки от оси Х к оси У. В случае отрицательных углов

можно воспользоваться тождествами :

cos (- )= cos

sin (- ) = - sin .

Уравнение (3.17) легко получить из Рис.2. 19, на котором точка Р(х,у) переводится в точку Р'(х',у') поворотом на угол . Поскольку поворот производится относительно начала координат, расстояние от него до Р и Р' равны. Обозначим их через r. Тогда

x = r * cos y = r * sin (2.21)

и

x'= r cos ( +) = r cos cos - r sin sin (2.22)

y'= r sin (+ ) = r cos  sin + r sin cos

Подставив (2.19) в уравнение (2.20) получим уравнение (2.17).


Рис.2. 19. Вывод уравнения поворота


^

2.3.32.3.3 Однородные координаты и матричное представление двухмерных преобразований



Преобразование переноса, масштабирования и поворота в матричной форме записываются в виде:
Р' = Р + Т
Р' = Р * S
Р' = Р * R
Как видим поворот и масштабирование осуществляется с помощью операций умножения, сдвига - с помощью операции сложения. Целесообразно представить их таким образом, чтобы все эти три элементарных преобразования можно было объединять вместе. Рассмотрим как это можно сделать.

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

С помощью однородных координат все три преобразования можно реализовать при помощи умножения.

В однородных координатах точка ^ Р(х,у) записывается как (W*x,W*У,W) для любого масштабного множителя W не равного нулю. При этом, если для точки задано ее представление в однородных координатах Р(х,у,w), то можно найти ее двумерные декартовы координаты как x = x / W и y = y / W. Если принимать значение W=1, операция деления не требуется. Однородные координаты можно представить как вложение промасштабированной с коэффициентом W двумерной плоскости в плоскость z=W ( здесь z=1) в трехмерном пространстве.

Точки теперь описываются трехэлементными вектор строками, поэтому матрицы преобразований, на которые умножается вектор точки, должен иметь размер 3*3. Уравнение переноса (3.12) записывается в виде матрицы преобразования однородных координат:

[х'у'1]= [ху1] (2.23)

или

Р' = Р Т (Dх , Dу) (2.24)

где

Т(Dх,Dу)= (2.25)

Что будет, если точку Р перенести в точку Р' на расстояние (Dх1,Dу1), а затем в Р'' на расстояние (Dх2,Dу2)? Интуитивно ожидаемый результат представляет собой суммарный перенос на расстояние (Dх1+Dх2,Dу1+Dу2):

Р''=РТ(Dх1,Dу1)Т(Dх2,Dу2)] (2.26)

Матричное произведение Т(Dх1,Dу1)Т(Dх2,Dу2) есть

= (2.27).

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

[х'у'1] = [х у 1] (2.28)

Определяя

S( =

имеем:

Р' = Р S(Sх,Sу) (2.29)

Так же как последовательные переносы являются аддитивными, можно ожидать, что последовательные масштабирования будут мультипликативными

Если заданы:

Р'=РS(Sх1,Sу1)

Р''=Р' S(Sх2,Sу2)

то получаем:

Р'=Р*[S(Sх1,Sу1)*S(Sх2,Sу2)] (2.30)

Матричное произведение S(Sх1,Sу1) S(Sх2,Sу2) есть

=

т.е. масштабирования мультипликативные.

Уравнение поворота можно представить в виде
[х'у'1]=[ху1] (2.31)

Полагая

R()=

имеем
Р' = Р R() (2.30)
Два последовательных поворота являются аддитивными по углам:
R(1) R(2)= (2.31)


^

2.3.4 2.3.4 Композиция двумерных преобразований.



Композицией будем называть произведение матриц. Рассмотрим, как можно использовать композицию преобразований для объединения фундаментальных матриц R,S,T с целью получения желаемых общих результатов. Основное преимущество объединенных преобразований состоит в том, что к точке более удобно применить одно результирующее преобразование, чем ряд преобразований друг за другом.

Рассмотрим, например, поворот объекта относительно некоторой произвольной точки ^ Р1. Ранее нами рассмотрен поворот относительно начала координат. Поэтому разобьем задачу на три шага:

- перенос точки Р1 в начало координат и соответствующий сдвиг объекта;

- поворот объекта относительно начала координат;

- перенос точки Р1 из начала координат в первоначальное положение и соответствующий сдвиг объекта.

Указанная последовательность приведена на Рис.2. 20.

Рис.2. 20. Поворот объекта вокруг произвольной точки.
Результирующее преобразование имеет вид:
=
= (2.32)
Последовательность преобразований масштабирования, поворота и переноса показаны на Рис.2. 21.



Рис.2. 21. Преобразование с масштабированием, поворотом,

переносом.
Преобразование, показанное на Рис.2. 21., может быть записано следующей матрицей преобразование:
=

Следует отметить, что в общем случае умножение матриц не коммутативно.


^

2.3.5 2.3.5 Вопросы эффективности



Композиция наиболее общего вида, составленная из операций R, S и T, имеет матрицу:
M=
Ее верхняя часть размером 2 x2 является объединенной матрицей поворота и масштабирования, в то время как и описывают суммарный перенос. Для вычисления координат точки как произведения вектора на матрицу размером 3 x 3 требуется 9 операций умножения и 6 операций сложения. Структура последнего столбца матрицы в выражении (2.33) позволяет упростить фактически выполняемые действия:

(2.35)

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

Одной из областей применения, в которой важно быстродействие, является генерация последовательных кадров - изображений объектов, когда каждый последующий кадр отличается от предыдущего поворотом объекта на несколько градусов. Если каждый следующий кадр строится и выводится на экран дисплея достаточно быстро - в течении 30-60 мс - то поворот объекта будет казаться непрерывным и плавным. Для достижения такого эффекта каждую точку объекта следует преобразовать как можно быстрее. В уравнение поворота входит 4 операции умножения и 2 операции сложения. Если учесть, что угол поворота очень мал - несколько градусов - можно принять, что cos = 1. При такой аппроксимации уравнение поворота принимае вид:
x'= x - y*sin

(2.35)

y'= x*cos  + y

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

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


^

2.3.62. 3. 6 Отсечение примитивов вывода


Видовая операция «окно» производит операцию отсечения точек, линий, цепочек литер для типичного вертикального прямоугольного окна ( Рис. 2. 22 ). Точка А находится внутри окна и поэтому она отображается внутри поля вывода на видовой поверхности. Точка В находится вне окна и поэтому она не изображается. Отрезок прямой EF изображается полностью, отрезки GH и IJ изображаются частично (отсекаются), а CD и KL не изображаются совсем. Отметим, что точки и отрезки, находящиеся на границе окна, считаются внутренними и поэтому отображаются.



Рис. 2. 22 Двумерное отсечение

^ Отсечение точек. Отсечение точек осуществляется достаточно просто. Если xmax и xmin , ymax и ymin - координаты границ окна, то для того чтобы точка была видимой, должны выполняться неравенства:

xmin x xmax , ymin y ymax

Если хотя бы одно из этих неравенств неверно, точка не отображается.

Отсечение отрезков

Отсечение отрезков прямых требует большего числа вычислений, чем отсечение точек. Конечно как и в предыдущих преобразованиях достаточно рассмотреть конечные точки отрезка, не принимая во внимание бесконечное количество внутренних точек. Прежде всего можно быстро разобраться с классом отрезков, обе конечные точки которых лежат внутри окна (отрезок EF на Рис. 2. 22). Такие отрезки целиком находятся внутри окна и, следовательно, могут быть приняты целиком. Отрезки, одна конечная точка которых находится внутри окна, а другая вне его, требует операции отсечения (отрезок GH на Рис. 2.22). Отрезки, обе конечные точки которых находятся вне окна, необходимо проверить по границам окна, чтобы выявит возможное пересечение с окном: при обнаружении пересечения необходимо отсечение (см. отрезки CD, IJ, KL).

При таком подходе для каждой пары (сторона - отрезок) необходимо решать систему двух уравнений, используя операции умножения и деления. При этом удобно параметрическое задание прямых:
x = x1 + t( x2 - x1),

y = y1 + t( y2 - y1).

Для t из диапазона (0, 1) эти уравнения определяют точки (x, y), находящиеся на ориентированном отрезке прямой, начинающемся в точке (x1, y1) и заканчивающемся в точке (x2, , y2). В данном случае для нахождения точки пересечения необходимо решить систему уравнений относительно tсторона и tотрезок. Если найденные значения

tсторона и tотрезок лежат в диапазоне (0, 1), точка пересечения находится внутри проверяемого отрезка и внутри стороны окна и, следовательно, отрезок пересекается с окном. До решения системы уравнений специальной проверкой необходимо исключит случай, когда прямые параллельны сторонам окна.

Эффективность системы отсечения приобретает особое значение в анимационных системах графики, когда сотни и тысячи отрезков должны отсекаться с высокой скоростью для плавного перехода от одного кадра к другому. Одним из наиболее эффективных алгоритмов отсечения является алгоритм Коэна-Сазерленда.
2.3.6.1.1.1.1.1Алгоритм Коэна-Сазерленда

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

Работа алгоритма начинается с присвоения конечным точкам отрезков 4-битного кода «вне - внутри» по правилу Рис. 2. 23.



Рис. 2.23 Формирование кодов для конечных точек
Каждому биту присваивается значение 1, если выполняется соответствующее данному биту условие, характеризующее взаимное расположение точки и окна (биты нумеруются слева направо):

- бит 1 - точка выше окна;

- бит 2 - точка ниже окна;

- бит 3 - точка справа от окна;

- бит 4 - точка слева от окна.

В противном случае биту присваивается значение 0.

Существует эффективный способ вычисления этого кода, вытекающий из того факта, что бит 1 является знаковым битом разности (ymax -y), бит 2 знаковым битом для (y - ymin), бит 3 для (xmax - x), бит 4 для (x - xmin) . Точка находится внутри окна, если эти разности неотрицательны (код 0000). Отрезок можно принять целиком, если оба его конца лежат внутри окна (оба кода 0000). Отрезок отбрасывается без вычислений, если оба его конца лежат выше, ниже, правее или левее окна. В этих случаях соответствующие биты в обоих кодах равны 1 и это легко выявить применив к кодам логическую операцию И и проверив результат на отличие от 0000.

Если результат логической операции И равен 0000, отрезок нельзя ни принять ни отвергнуть целиком, так как он может пересекаться с окном (см. отрезки CD, IJ, KL на рис.2. 22). Для определения пересечения в алгоритме используется итеративная стратегия «разделяй и властвуй», требующая небольшого объема вычислений. Используется горизонтальность либо вертикальность сторон окна, что позволяет определить координаты x или y точки пересечений без вычислений. Кроме того используется тот факт, что часть отрезка, расположенная с внешней стороны окна, может быть отброшена. Оставшийся отрезок проверяется на возможность его принятия или отбрасывания целиком. Если это невозможно процесс повторяется для другой стороны окна. На каждой итерации конечная точка отрезка с ненулевым кодом заменяется на точку , лежащую на стороне окна или на прямой, содержащей сторону. Порядок перебора окон совершенно произволен: независимо от порядка отсечение некоторых отрезков потребует четырех итераций, определяющих пересечения со всеми четырьмя сторонами окна. В данном случае будем руководствоваться расположением битов в коде:

1. верхняя часть - отбросить часть отрезка, расположенную над окном;

2. нижняя часть - отбросить часть отрезка, расположенную ниже окна;

3. правая сторона - отбросит часть отрезка, расположенную справа;

4. левая сторона - отбросить часть отрезка, расположенную слева.

При расчете точек пересечения используется тот факт, что одна из координат точки пересечения известна (xmin , xmax, ymax , ymin). Например, при вычислении точки пересечения I (см. Рис. 2.22) воспользуемся уравнением:

y = yI + M (x - xI ) = ymin

x = 1/M (ymin - yI) - xI

где x, y - координаты точки I.

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

^ Алгоритм деления отрезка пополам

Алгоритм деления отрезка пополам сначала отображает все примитивы в координаты устройства и затем отсекает их по границам поля вывода. В этом алгоритме коды «вне/внутри» используются так же как и в алгоритме Коэна-Сазерленда. Если отрезок нельзя ни принять, ни отбросить целиком, он делится на две равные части. Общая стратегия состоит в повторении этой процедуры до тех пор, пока один сегмент исходного отрезка не будет принят целиком (если существует пересечение), а другой - целиком отброшен. На каждом шаге обычно можно принять и/или отбросить половину отрезка. Например, на Рис. 2.24 половина отрезка GI принимается, а половина отрезка KL отбрасывается.



Рис. 2.24 Отсечение методом деления отрезка пополам

Имеется только одна небольшая сложность. При отсечении отрезков, подобных AC и DF (см. Рис. 2.24), необходимо найти либо два пересечения, либо ни одного. Какой конкретно имеет место случай, легко определить в процессе деления. На некотором шаге либо обе половины отбрасываются (как AB и BC), либо нет (как DE и EF). В последнем случае рассмотрение одного временно откладывается, а другой делится до нахождения пересечения. После этого найденные координаты запоминаются и процесс повторяется для отложенного отрезка.


^

2.3.7 2.3.7 Отображение окна на поле вывода



После отсечения примитива по границам поля вывода процессор видовой операции отображает его на поле вывода в НК. Аналогичная операция выполняется после геометрических преобразований: производится отображения поля вывода в нормированных координатах в поле вывода в физических координатах.



Рис. 2.25 Сохранение пропорций при отображении «окно - поле вывода».

На Рис.2. 25 точка xw , yw отображается в точку xv , yv с сохранением пропорций, т.е. с сохранением ее относительного положения внутри замкнутого прямоугольника окна. Более точно это условие формулируется следующим образом: отношение расстояния от точки до y- границы к длине х- границы и отношение расстояния от точки до х- границы к длине y- границы должны быть одинаковыми для окна и поля вывода. Используя обозначения Рис. 2.25 , это условие можно записать в следующем виде:

xw.dist / xw.leng = (xw - xw.min ) / (xw.max. - xw.min) = (xv - xv.min) / (xv.max - xv.min) = xv.dist /xv.leng

и

yw.dist / yw.leng = (yw - yw.min ) / (yw.max. - yw.min) = (yv - yv.min) / (yv.max - yv.min) = yv.dist /yv.leng

Отсюда можно вывести уравнение отображения:

xv = xv.min + [(xv.max - xv.min) / (xw.max - xw.min)] (xw - xw.min)

yv = yv.min + [(yv.max - yv.min) / (yw.max - yw.min)] (yw - yw.min)

или

xv = sx (xw - xw.min) + xv.min

yv = sy (yw - yw.min) + yv.min

где sx , sy - параметры масштабирования, согласующие размеры окна и поля, а xv.min , yv.min - переноса, привязывающие координаты окна к левому нижнему углу поля вывода.


1   2   3   4   5   6   7   8   9   ...   19

Похожие:

Конспект лекций с дисциплины «Компьютерная графика» для направления подготовки 0910 “Компьютерная инженерия” iconКонспект лекций по дисциплине “ основы защиты информации” для направления...
Министерство образования и науки украины восточноукраинский государственный университеТ

Конспект лекций с дисциплины «Компьютерная графика» для направления подготовки 0910 “Компьютерная инженерия” iconМетодические указания к выполнению лабораторных работ по дисциплине...
Компьютерная инженерия” (для студентов дневной и заочной формы обучения специальности 091501 “Компьютерные системы и сети”, 091502...

Конспект лекций с дисциплины «Компьютерная графика» для направления подготовки 0910 “Компьютерная инженерия” iconЛитература. Студенты выполняют свои варианты следующих работ: ргр...
«Инженерная и компьютерная графика» модуль «Компьютерная графика» выполняют расчётно-графические работы (ргр) по методическим пособиям...

Конспект лекций с дисциплины «Компьютерная графика» для направления подготовки 0910 “Компьютерная инженерия” iconЛитература. Студенты выполняют свои варианты следующих работ: ргр...
«Начертательная геометрия и компьютерная графика» модуль «Компьютерная графика» выполняют расчётно-графические работы (ргр) по методическим...

Конспект лекций с дисциплины «Компьютерная графика» для направления подготовки 0910 “Компьютерная инженерия” iconКонспект лекций по дисциплине “
«Компьютерная инженерия», специальности 091501 «Компьютерные сети и системы», 091502 «Системное программирование»

Конспект лекций с дисциплины «Компьютерная графика» для направления подготовки 0910 “Компьютерная инженерия” iconМетодические указания для самостоятельного изучения и подготовки...
Комп'ютерна електроніка”. “Математичне моделювання електронних пристроїв в сапр micro-Cap 0” для студентів напрямку 0915 “Комп'ютерна...

Конспект лекций с дисциплины «Компьютерная графика» для направления подготовки 0910 “Компьютерная инженерия” iconОпорный конспект лекций по дисциплине Компьютерная графика для специальности...
Тема. Основные понятия компьютерной графики. Аппаратное и программное обеспечение

Конспект лекций с дисциплины «Компьютерная графика» для направления подготовки 0910 “Компьютерная инженерия” iconРабочая программа, методические указания и контрольные задания по...
Рабочая программа, методические указания и контрольные задания по дисциплине «Компьютерная графика» для студентов заочного факультета...

Конспект лекций с дисциплины «Компьютерная графика» для направления подготовки 0910 “Компьютерная инженерия” iconМетодические указания для самостоятельного изучения и подготовки...
Сбис мп I пл”. “Система автоматизованого проектування Quartus ii” для студентів напрямку підготовки 0915 “Комп'ютерна інженерія”./...

Конспект лекций с дисциплины «Компьютерная графика» для направления подготовки 0910 “Компьютерная инженерия” iconМетодические указания для выполнения лабораторных, самостоятельных...
«Информатика и компьютерная техника» (для студентов 1-го и 2-го курсов заочной формы обучения образовательно-квалификационного уровня...

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
uchebilka.ru
Главная страница


<