З адание на лабораторную работу № 2 "Фильтрация. Модифицированный алгоритм Брезенхема "
Сгенерировать многоугольник с использованием алгоритма Брезенхема при двухуровневом изображении (пиксел или закрашен или не закрашен).
Сгенерировать многоугольник с вычислением интенсивности пикселов, через которые проходит ребро многоугольника, с использованием модифицированного алгоритма Брезенхема.
Сгенерировать изображение, используя масочную фильтрацию.
Каким образом осуществляется устранение ступенчатости ребер многоугольника?
В чем суть методов, основанных на "размывании" границы изображения?
Назовите причины возникновения искажения изображения и методы их устранения.
3 . Алгоритмы генерации окружности
Ц ель: Изучить алгоритмы построения окружности по целочисленному методу Брезенхема и по алгоритму Мичнера
Для того чтобы построить окружность, можно сгенерировать только ее 1/8 часть (рис. 3.1 а). Далее, отражение относительно прямой Y = X (рис. 3.1 б), отражение относительно прямой X = 0 (рис. 3.1 в), и отражение относительно прямой Y = 0 (рис. 3.1 г).
Рис. 3.1. Метод последовательной генерации окружности
3.1. Целочисленный алгоритм Брезенхема
Для генерации окружности по методу Брезенхема рассматривается первый квадрант с начальной точкой X = 0, Y = R и построение ведется по часовой стрелке. Т.е., в данном случае, Y является монотонно убывающей функцией аргумента X, и для любой точки окружности существует только 3 варианта выбора дальнейшей точки (рис 3.2):
;
;
.
Алгоритм выбирает пиксел, для которого квадрат расстояния от реального центра окружности до предполагаемого будет минимальным.
Т.е. выбираем минимум из:
;
;
.
Рис. 3.2. Алгоритм Брезенхема
Можно было бы закончить алгоритм, но необходимо сделать его целочисленным.
Для этого упрощаем вычисления: в окрестности точки xi, yi возможны только 5 типов пересечения окружности и сетки растра (рис 3.3).
Рис. 3.3. Приведение алгоритма Брезенхема к целочисленному
Разность квадратов расстояний от центра окружности до диагонального пиксела:
.
При i < 0 точка d находится внутри реальной окружности (т.е. случай 1 или 2) и следует выбрать точки h или d.
Рассмотрим случай 1. Разность квадратов расстояния от реальной окружности до пикселов h и d равна:
.
При e < 0 m d > m h, при e > 0 – наоборот. Поэтому при e 0 выбираем пиксел h, при e > 0 – пиксел d.
Сокращаем количество вычислений.
В случае 1
,
а
и, следовательно,
,
дополняем
до
,
прибавляя и вычитая
:
.
В случае 2 должен быть выбран пиксел h.
При этом
,
и
и, следовательно, e < 0. Т.е. при
использовании того же критерия, что и
в случае 1, автоматически выбирается
пиксел h.
В случае
– точка лежит вне окружности (случай
3 или 4), и, проведя аналогичные вычисления,
получаем
.
И если e' 0,
выбираем пиксел d, иначе пиксел v.
Для случая 5
(
)
автоматически выбираем пиксел d
(хотя здесь можно использовать и любые
другие вышеперечисленные критерии).
Итог:
i < 0:
e 0 – выбираем m h;
e > 0 – выбираем m d;
i > 0:
e' 0 – выбираем m d;
e' > 0 – выбираем m v;
i = 0: – выбираем m d.
Легко разработать рекурентные соотношения:
для m h:
x i+1 = x i + 1
y i+1 = y i
и т.д.
Приведем общий алгоритм:
x = 0; y = R; = 2*(1 – R) ;
т.к. = (x + 1) 2+(y – 1) 2 – R 2 = (0 + 1) 2 + (R – 1) 2 – R 2 = 2*(1 – R).
предел = 0;
1: Plot (x,y);
if y предел then 4;
; выделение случая 1 или 2, 3 или 4, или 5
if < 0 then 2 ;случай 1 или 2
if > 0 then 3 ;случай 3 или 4
if = 0 then 20 ;случай 5
;определение случая 1 или 2
2: e = 2*+2*y-1;
if e 0 then 10 ;случай h
if e > 0 then 20 ;случай d
;определение случая 3 или 4
3: e' = 2* – 2*x – 1;
if e' 0 then 20 ;случай d
if e' > 0 then 30 ;случай v
;изменение координат для случаев 1, 2, 3, 4 и 5
10: x = x + 1;
= + 2*x + 1;
go to 1;
x = x + 1;
y = y – 1;
= + 2*x – 2*y + 2
go to 1;
y = y – 1;
= – 2*y + 1;
go to 1;
4: finish
П
риведем
пример работы алгоритма для окружности
радиусом R
= 8
(рис.
3.4).
Рис. 3.3. Пример построения окружности по целочисленному алгоритму Брезенхема