Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
РАСТРОВАЯ ГРАФИКА.
Для работы с устройствами растровой графики нужны специальные методы генерации изображения, вычерчивания прямых и кривых линий, закраски многоугольников, создающих впечатление сплошных объектов. Эти методы и будут рассматриваться.
АЛГОРИТМЫ ВЫЧЕРЧЧИВАНИЯ ОТРЕЗКОВ.
Поскольку экран ЭЛТ можно рассматривать как матрицу дискретных элементов, каждый из которых может быть подсвечен, нельзя непосредственно провести отрезок из одной точки в другую. Процесс определения пикселов, наилучшим образом аппроксимирующих заданный отрезок, называется разложением в растр. В сочетании с процессом построчной визуализации изображения он известен как преобразование растровой развертки. Для горизонтальных, вертикальных и наклоненных под углом 45° отрезков выбор растровых элементов очевиден. Для любой другой ориентации выбрать нужные пикселы труднее, что показано на рисунке.
Прежде, чем приступать к обсуждению конкретных алгоритмов рисования отрезков, полезно рассмотреть общие требования к таким алгоритмам и ответить на вопрос, каковы желаемые характеристики изображения. Очевидно, что отрезки должны выглядеть прямыми, начинаться и заканчиваться в заданных точках. Далее, яркость должна быть постоянной и не зависеть от длины и наклона. Наконец, рисовать нужно быстро. Как это часто бывает, не все из перечисленных критериев могут быть полностью удовлетворены. Сама природа растрового дисплея исключает генерацию абсолютно прямых линий (кроме ряда специальных случаев), равно как и точное совпадение начала и конца отрезков с заданными точками. Тем не менее при достаточно высоком разрешении дисплея можно получить приемлемую аппроксимацию.
Постоянная яркость достигается лишь при проведении горизонтальных, вертикальных и наклоненных под углом 45° прямых. Для всех других ориентаций разложение в растр приведет к неравномерной яркости, как это показано на рисунке. Даже для частных случаев яркость зависит от наклона. Заметим, что расстояние между соседними пикселами для отрезка под углом 45° больше, чем для вертикальных и горизонтальных прямых. Поэтому вертикальные и горизонтальные отрезки будут выглядеть ярче, чем наклонные. Обеспечение одинаковой яркости вдоль отрезков разных длин и ориентаций требует извлечение квадратного корня, а это замедлит вычисления. Обычным компромиссом является нахождение приближенной длины отрезка, сведение вычислений к минимуму, предпочтительное использование целой арифметики, а также реализациа алгоритмов на аппаратном или микропрограммном уровне.
В большинстве алгоритмов вычерчивания отрезков для упрощения вычислений используется пошаговый метод. Приведем пример подобного алгоритма:
позиция = начало
шаг = приращение
Выполнять пока позиция – конец >= точность
Если позиция > конец Тогда позиция := позиция – шаг
Простой алгоритм разложения отрезка в ряд иллюстрирует применение пошаговых методов
ЦИФРОВОЙ ДИФФЕРЕНЦИАЛЬНЫЙ АНАЛИЗАТОР.
Один из методов разложения отрезка в растр состоит в решении дифференциального уравнения, описывающего этот процесс. Для прямой линии имеем
или
Решение представляется в виде
,
где х1, у1 и х2, у2 – концы разлагаемого отрезка и yi – начальное значение для очередного шага вдоль отрезка. Фактически это уравнение представляет собой рекуррентное соотношение для последовательных значений у вдоль нужного отрезка. Этот метод, используемый для разложения в растр отрезков, называется цифровым дифференциальным анализатором (ЦДА). В простом ЦДА либо Δх, либо Δу (наибольшее из приращений) выбирается в качестве единицы растра. Ниже приводится простой алгоритм, работающий во всех квадрантах.
Предполагается, что концы отрезка (х1, у1) и (х2, у2) не совпадают.integer –функция преобразования вещественного числа в целое (взятие целой части); Sign – функция, возвращающая 1, 0, -1 для положительного, нулевого и отрицательного аргументов соответственно.
Аппроксимируем длину отрезка
If abs(x2-x1) abs(y2-y1) then
Длина = abs(x2-x1)
Else
Длина = abs(y2-y1)
Δх =(x2-x1)/Длина
Δу = (y2-y1) /Длина
Округляем величины, а не отбрасываем их дробную часть; использование знаковой функции делает алгоритм пригодным для всех квадрантов
x=x1 + 0.5*Sign(Δх)
y=y1 + 0.5*Sign(Δу)
начало основного цикла
i = 1
while(i Длина)
Plot(integer(x), integer(y))
x= x+ Δх
y= y+ Δу
endwhile
Приведем пример, иллюстрирующий работу алгоритма
(0, 0) – (5,5)
Длина = 5
Δх=1
Δу=1
х = 0.5
у = 0.5
|
i |
Plot |
x |
y |
|
0.5 |
0.5 |
||
|
1 |
(0,0) |
||
|
1.5 |
1.5 |
||
|
2 |
(1,1) |
||
|
2.5 |
2.5 |
||
|
3 |
(2,2) |
||
|
3.5 |
3.5 |
||
|
4 |
(3,3) |
||
|
4.5 |
4.5 |
||
|
5 |
(4,4) |
||
|
5.5 |
5.5 |
Полученное растровое представление отрезка изображено на рисунке. Заметим, что концевые точки определены точно и выбранные пикселы равномерно распределены вдоль отрезка. Внешний вид прямой вполне удовлетворительный. Однако, если начальным знаком переменной i сделать нуль вместо единицы, то окажется активированным пиксел с координатами(5,5), что нежелательно. Если адрес пиксела задан координатами левого нижнего угла, то активация этого пиксела даст явно неверную точку отрезка. Вдобавок при вычерчивании серии последовательных отрезков пиксел (5,5) будет активирован дважды: в конце данного отрезка и в начале следующего. Такой пиксел может выглядеть как более яркий и иметь иной цвет.
Рассмотрим следующий пример.
(0,0) –(-8,-4)
Длина = 8
Δх=-1
Δу=-0.5
х = -0.5
у = -0.5
|
i |
Plot |
x |
y |
|
-0.5 |
-0.5 |
||
|
1 |
(-1,-1) |
||
|
-1.5 |
-1.0 |
||
|
2 |
(-2,-1) |
||
|
-2.5 |
-1.5 |
||
|
3 |
(-3,-2) |
||
|
-3.5 |
-2.0 |
||
|
4 |
(-4,-2) |
||
|
-4.5 |
-2.5 |
||
|
5 |
(-5,-3) |
||
|
-5.5 |
-3 |
||
|
6 |
(-6,-3) |
||
|
-6.5 |
-3.5 |
||
|
7 |
(-7,-4) |
||
|
-7.5 |
-4.0 |
||
|
8 |
(-8,-4) |
||
|
-8.0 |
-4.5 |
Несмотря на то, что результаты выглядят вполне приемлемыми, анализ отрезков, проведенных из точки (0,0) в точки (-8, 4) и (8, -4), показывает, что разложенный в растр отрезок лежит по одну сторону от реального и что на одном из концов отрезка появляется лишняя точка, т.е. результат работы зависит от ориентации. Следовательно, точность в концевых точках ухудшается. Далее, если вместо взятия целой части использовать округление до ближайшего целого, то результаты снова получаются разными. Таким образом, либо нужно использовать более сложный и медленный алгоритм, либо надо отступиться от требования максимально точной аппроксимации. Вдобавок предложенный алгоритм имеет тот недостаток, что он использует вещественную арифметику. Рассмотрим более приемлемый алгоритм
АЛГОРИТМ БРЕЗЕНХЕМА
Алгоритм выбирает оптимальные растровые координаты для представления отрезка. В процессе работы одна из координат либо х, либо у (в зависимости от углового коэффициента) изменяется на единицу. Изменение другой координаты (либо на нуль, либо на единицу) зависит от расстояния между действительным положением отрезка и ближайшими координатами сетки. Такое расстояние назовем ошибкой.
Алгоритм построен так, что требуется проверять лишь знак этой ошибки. Рисунок иллюстрирует ситуацию
для отрезка в первом октанте, т.е. для отрезка с угловым коэффициентом, лежащим в диапазоне от нуля до единицы. Из рисунка можно заметить, что если угловой коэффициент отрезка из точки (0,0) больше чем, то его пересечение с прямой х = 1 будет расположено ближе к прямой у = 1, чем к прямой у = 0. Следовательно, точка растра (1,1) лучше аппроксимирует ход отрезка, чем точка (1,0) . Если угловой коэффициент меньше , то верно обратное. Для углового коэффициента равного , нет какого-либо предпочтительного выбора. В данном случае алгоритм выбирает точку (1,1) .
Не все отрезки проходят через точки растра. Подобная ситуация иллюстрируется на следующем рисунке,
где отрезок с тангенсом угла наклона сначала проходит через точку растра (0,0) и последовательно пересекает три пиксела. Также иллюстрируется вычисление ошибки при представлении отрезка дискретными пикселами. Так как желательно проверять только знак ошибки, то она первоначально устанавливается равной
-. Таким образом, есоли угловой коэффициент больше или равен , то величина ошибки в следующей точке растра с координатами (1,0) может быть вычислена как
e=e+m
где m –угловой коэффициент. В нашем случае при начальном значении ошибки - вычисления для следующего пиксела дает
е= -+= -
так как е отрицательно, отрезок пройдет ниже середины пиксела. Следовательно, пиксел на том же самом горизонтальном уровне лучше аппроксимирует положение отрезка, поэтому у не увеличивается. Аналогичным образом вычисляем ошибку в следующей точке растра (2,0).
е=-+=.
Теперь е положительное, а значит, отрезок пройдет выше средней точки. Растровый элемент (2,1) лучше аппроксимирует положение отрезка. Следовательно, у увеличивается на единицу. Прежде чем рассматривать следующий пиксел, необходимо откорректировать ошибку вычитанием из нее единицы. имеем
е=
Заметим, что пересечение вертикальной прямой х=2 с заданным отрезком лежит на ниже прямой у=1. Если же перенести отрезок вниз, мы получим как раз величину . Продолжение вычислений для следующего пиксела дает
е=
Так как е отрицательно, то у не увеличивается. Из всего сказанного следует, что ошибка \ это интервал, отсекаемый по оси у рассматриваемым отрезком в каждом растровом элементе (относительно -)
Приведем алгоритм Брезенхема для первого октанта, то есть для случая.
Предполагается, что концы отрезка (х1,у1) и (х2,у2) не совпадают.
Integer - функция преобразования в целое
х, у, Δх, Δу – целые
е – вещественное
инициализация переменных
x=x1
y=y1
Δx=x2-x1
Δy = y2 –y1
Инициализация переменных с поправкой на половину пиксела
e=Δx/Δy-1/2
начало основного цикла
for I =1 to Δx
Plot(x,y)
While (e≥0)
y=y+1
e = e-1
end while
x = x + 1
e = e + Δy / Δx
next i
Finish
АЛГОРИТМ БРЕЗЕНХЕМА ДЛЯ ГЕНЕРАЦИИ ОКРУЖНОСТИ
В растр разлагаются не только линейные, но и другие, более сложные функции. Разложению конических сечений, т.е. окружностей, эллипсов, парабол, гипербол посвящено значительное число работ. Наибольшее внимание, разумеется, уделено окружности. Один из наиболее эффективных и простых для понимания алгоритмов генерации окружности принадлежит Брезенхему. Для начала заметим, что необходимо сгенерировать только одну восьмую часть окружности. Остальные ее части могут быть получены последовательными отражениями. Если сгенерировать первый октант (от 0 до 45º против часовой стрелки), то второй октант можно получить зеркальным отражением относительно прямой у=х, что дает в совокупности первый квадрант. Первый квадрант отражается относительно прямой х=0 для получения соответствующей части окружности во втором квадранте. Верхняя полуокружность отражается относительно прямой у=0 для завершения построения. Приведем матрицы соответствующих преобразований.
Для отражения первого октанта относительно оси у=х -
Для отражения первого квадранта относительно оси х=0 -
Для отражения верхней полуокружности относительно оси у=0 .
Для вывода алгоритма рассмотрим первую четверть окружности с центром в начале координат. Заметим. Что если работа алгоритма начинается в точке х=0 у= R, то при генерации окружности по часовой стрелке в первом квадранте у является 0, х= R, то при генерации окружности против часовой стрелки х будет монотонно убывающей функцией аргумента у. В нашем случае выбирается генерация по чаовой стрелке с началом в точке х=0, у=R. Предполагается, что центр окружности и начальная точка находятся точно в точках растра.
Для любой заданной точки на окружности при генерации по часовой стрелке существует только три возможности выбрать следующий пиксел, наилучшим образом приближающий окружность: горизонтально вправо, по диагонали вниз и вправо, вертикально вниз. На следуем рисунке эти направления обозначены соответственно mH, mD, mv. Алгоритм
Выбирает пиксел, для которого минимален квадрат расстояния между одним из этих пикселов и окружностью, т.е.: минимум из
mH =
mD =
mV=
Вычисление можно упростить, если заметить, что в окрестности точки (хi,yi) возможны только пять типов пересечения окружности и сетки растра приведенных на следующем рисунке
Разность между квадратами расстояний от центра окружности до диагонального пиксела (xi-1,yi-1) и от центра до точки окружности R2 равна
Как и в алгоритме Брезенхема для отрезка, для выбора соответствующего пиксела желательно использовать только знак ошибки, а не ее величину.
При< 0 диагональная точка (xi-1,yi-1) находится внутри реальной окружности, т.е это случаи 1 или 2 на нашем рисунке. Ясно, что в этой ситуации следует выбрать либо пиксел (xi+1, yi), т.е. mH, либо пиксел (xi+1,yi-1), т.е. mD. Для этого сначала рассмотрим случай 1 и проверим разность квадратов расстояний от окружности до пиксела в горизонтальном и диагональном направлениях:
Прирассотяние от окружности до диагонального пиксела (mD) больше, чем до горизонтального (mH). Напротив, если, расстояние до горизонтального пиксела (mH) больше. Таким образом,
привыбираем mH в (xi+1, yi)
при выбираем mD в (xi+1, yi-1)
При , когда расстояние от окружности до обоих пикселов одинаково, выбираем горизонтальный шаг.
Количество вычислений, необходимых для оценки величины можно сократить, если заметить, что в случае 1
(xi + 1) 2 + (yi)2 – R2 ≥ 0
(xi + 1) 2 + (yi - 1)2 – R2 < 0
Так как диагональный пиксел (xi+1, yi-1) всегда лежит внутри окружности, а горизонтальный (xi+1, yi) вне ее. Таким образом, можно вычислить по формуле
= (xi + 1) 2 + (yi)2 – R2 + (xi + 1) 2 + (yi - 1)2 – R2
Дополнение до полного квадрата члена (yi)2 c помощью добавления и вычитания -2yi + 1 дает
В квадратных скобках стоит по определению и его подстановка
2
существенно упрощает выражение.
Рассмотрим случай 2 на нашем рисунке и заметим, что здесь должен быть выбран горизонтальный пиксел (xi + 1, yi) так как у является монотонно убывающей функцией. Поверка компонент показывает что,
(xi +1)2 + (yi)2 – R2 < 0
(xi +1)2+ (yi -1)2 – R2 < 0
Поскольку в случае 2 горизонтальный (xi + 1, yi) и диагональный (xi + 1, yi - 1) пикселы лежат внутри окружности. Следовательно, < 0, и при использовании того же самого критерия, что и в случае 1, выбирается пиксел (xi + 1, yi).
Если , то диагональная точка (xi + 1, yi - 1) находится вне окружности, т. Е. это случаи 3 и 4 на нашем рисунке. В данной ситуации ясно, что должен быть выбран либо пиксел (xi + 1, yi - 1), т.е. mD, либо (xi, yi - 1), т.е. mV. Аналогично разбору предыдущего случая критерий выбора можно получить, рассматривая сначала случай 3 и проверяя разность между квадратами расстояний от окружности до диагонального mD и вертикального mV пикселов, т.е.
При< 0 расстояние от окружности до вертикального пиксела (xi, yi - 1) больше и следует выбрать диагональный шаг mD, к пикселу (xi + 1, yi - 1). Напротив, в случае >0 расстояние от окружности до диагонального пиксела больше и следует выбрать вертикальное движение к пикселу (xi, yi - 1), Таким образом,
при выбираем mD в (xi + 1, yi - 1)
при > 0 выбираем mV в (xi, yi - 1).
Здесь в случае = 0, т.е когда расстояния равны выбран диагональный шаг.
Проверка компонент показывает что
(xi +1)2 + (yi - 1)2 – R2 0
(xi )2 + (yi -1)2 – R2 < 0
Поскольку для случая 3 диагональный пиксел (xi + 1, yi - 1) находится вне окружности, тогда как вертикальный пиксел (xi, yi - 1) лежит внутри окружности. Это позволяет записать в виде
= (xi +1)2 + (yi - 1)2 – R2 + (xi )2 + (yi -1)2 – R2
Дополнение до полного квадрата члена (xi )2 с помощью добавления и вычитания 2 xi +1 дает
= 2[(xi +1)2 + (yi - 1)2 – R2] – 2xi – 1
Использование определения приводит выражение к виду
=2 ( - xi) – 1.
Теперь рассматривая случай 4, снова заметим, что следует выбрать вертикальный пиксел (xi, yi - 1), так как у является монотонно убывающей функцией при возрастании х.
Проверка компонент для случая 4 показывает что
(xi +1)2 + (yi - 1)2 – R2 > 0
(xi )2 + (yi -1)2 – R2 > 0
Поскольку оба пиксела находятся вне окружности. Следовательно, > 0 и при использовании критерия, разработанного для случая 3, происходит верный выбор mD.
Осталось проверить только случай 5 на нашем рисунке, который встречается, когда диагональный пиксел(xi + 1, yi - 1) лежит на окружности, т.е. = 0. Проверка компонент показывает, что
(xi +1)2 + (yi)2 – R2 > 0
(xi +1)2 + (yi - 1)2 – R2 = 0
Следовательно, > 0 и выбираем диагональный пиксел (xi + 1, yi - 1). Аналогичным образом оцениваем компоненты
(xi +1)2 + (yi - 1)2 – R2 = 0
(xi )2 + (yi -1)2 – R2 < 0
И < 0, что является условием выбора правильного диагонального шага к (xi + 1, yi - 1). Таким образом, случай = 0 подчиняется тому же критерию, что и < 0 или > 0.
Подведем итог полученных результатов
< 0
выбираем пиксел (xi + 1, yi) mH.
выбираем пиксел (xi + 1, yi - 1) mD
> 0
выбираем пиксел (xi + 1, yi - 1) mD
> 0 выбираем пиксел (xi, yi - 1) mv
= 0 выбираем пиксел (xi + 1, yi - 1) mD
Легко разработать простые рекуррентные соотношения для реализации пошагового алгоритма. Сначала рассмотрим горизонтальный шаг mH к пикселу (xi+1,yi). Обозначим новое положение пиксела как (i+1). Тогда координаты нового пиксела и значение равны
xi+1= xi +1
yi+1 = yi
+1 = (xi+1 +1)2 +(yi+1 -1)2 –R2 =
= (xi+1 +1)2 +2xi+1+1+(yi+1 -1)2 –R2 =
= (xi+1 +1)2 +(yi+1 -1)2 –R2+2xi+1+1 =
=+2xi+1+1
Аналогично координаты нового пиксела и значение для шага mD к пикселу (xi + 1, yi - 1) таковы
xi+1= xi +1
yi+1 = yi -1
+1 = +2xi+1 - 2 yi+1 +2
То же самое для шага mv к (xi, yi - 1)
xi+1= xi +1
yi+1 = yi -1
+1 = - 2 yi+1 +1
Приведем реализацию алгоритма Брезенхема для окружности на псевдокоде.
Пошаговый алгоритм Брезенхема для генерации окружности в первом квадранте
все переменные целые
инициализация переменных
xi = 0
yi = 0
= 2(1-R)
Предел = 0
1 Plot (xi, yi)
If then 4
Выделение случая 1 или 2, 4 или 5, или 3
if < 0 then 2
if > 0 then 3
if = 0 then 20
определение случая 1 или 2
2 + 2yi -1
If 0 Then 10
If > 0 then 20
определение случая 4 или5
3 =2+ 2xi – 1
If 0 then 20
If > 0 then 30
выполнение шагов
шаг mH
10 xi = xi +1
=+2xi+1+1
go to 1
шаг md
20 xi = xi +1
yi = yi -1
= +2xi+1 - 2 yi+1 +2
go to 1
шаг mv
30 yi = yi -1
= - 2 yi+1 +1
go to 1
finish