Алгоритм Брезенхема

Размещено на http://www.allbest.ru/

Министерство высшего образования РФ

ФГАОУ ВПО «Северо-Восточный Федеральный университет им. М.К. Амосова»

Горный факультет

Кафедра ОГР

Реферат

Алгоритм Брезенхема

Выполнил:

ст. гр. ОГР-11

Николаев В.В.

Проверил:

Дмитриев А.А.

Якутск 2014 г.



1. Алгоритм Brezenhema

алгоритм брезенхем дискретный пиксел

Хотя алгоритм Брезенхема был первоначально разработан для цифровых графопостроителей, однако он в той же степени подходит для использования растровыми устройствами с ЭЛТ. Алгоритм выбирает оптимальные растровые координаты для представления отрезка. В процессе работы одна из координат - либо x, либо y (в зависимости от углового коэффициента) - изменяется на единицу. Изменение другой координаты (на 0 или 1) в зависимости от расстояния между действительным положением отрезка и ближайших координат сетки. Такое расстояние мы назовем погрешностью.

Алгоритм построен так, что нужно проверить лишь знак этой погрешности. На рис. 1 это иллюстрируется для отрезка в первом октанте, т.е. для отрезка с угловым коэффициентом, лежащим в диапазоне от 0 до 1. Из рисунка можно заметить, если угловой коэффициент отрезка с точки (0,0) больше, чем 1/2, то пересечение с прямой x = 1 будет расположен ближе к прямой y = 1, чем к прямой y = 0. Следовательно, точка растра (1,1) лучше аппроксимирует ход отрезка, чем точка (1,0). Если угловой коэффициент меньше 1/2, то наоборот, для углового коэффициента, равного 1/2, нет лучшего выбора. В данном случае алгоритм выбирает точку (1,1).

Рис. 1. Основная идея алгоритма Брезенхема



Но не все отрезки проходят через точки растра. Подобная ситуация иллюстрируется рис. 2, где отрезок с тангенсом угла наклона 3/8 сначала проходит через точку растра (0,0) и последовательно пересекает три пиксела. Также иллюстрируется вычисления погрешности при представлении отрезка дискретными пикселами.

Рис. 2. График погрешности в алгоритме Брезенхема

Поэтому желательно проверять только знак ошибки, то она сначала устанавливается равной 1/2.Таким образом, если угловой коэффициент отрезка равна или больше 1/2, то величина погрешности в следующей точке растра с координатами (1,0) может быть вычислена как

е = е + м

где m - угловой коэффициент. В нашем случае при начальном значении погрешности Ѕ

е = -1 / 2 +3 / 8 = -1 / 8

Так как е отрицательное, отрезок пройдет ниже середины пиксела. Итак, пиксел на том же горизонтальном уровне лучше аппроксимирует положение отрезка, поэтому в не увеличивается. Аналогично вычисляем погрешность e = 1/8 +3 / 8 = 1/4 в следующей точке растра (2,0). Теперь е положительное, значит, отрезок пройдет выше средней точки. Растровый элемент (2,1) с последующей по величине координатой в лучшее аппроксимирует положение отрезка. Итак, в увеличивается на 1. Прежде чем рассматривать следующий пиксел, необходимо откорректировать ошибку вычитанием из нее 1. Имеем e = 1/4-1 = -3 / 4. Заметим, что пересечение вертикальной прямой x = 2 с заданным отрезком лежит на 1/4 ниже прямой у = 1. Если же перенести отрезок 1/2 вниз, мы получим именно величину 3/4. Продолжение вычислений для следующего пиксела дает e = 3/4 +3 / 8 = -3 / 8.

Так как е отрицательное, то y не увеличивается. Из всего сказанного следует, что погрешность - это интервал, отсекается по оси y рассмотренным отрезком в каждом растровом элементе (относительно -1 / 2).

Приведем алгоритм Брезенхема для первого октанта, т.е. для случая 0 Ј Dy Ј Dx.

Алгоритм Брезенхема разложения в растр отрезка для первого октанта предполагается, что концы отрезка (x1, y1) и (x2, y2) не совпадают.

Integer - функция преобразования в целое

х, у, Dx, Dy - целые

е - настоящее

инициализация переменных

х = x1

у = y 1

Dx = x2-x1

Dy = y2-y1

Инициализация с поправкой на половину пиксела



е = Dy/Dx-1/2

начало основного цикла

для г = 1, чтобы Dx

участок (х, у)

в то время как (е => 0)

у = у +1

е = е-1

конец в то время как

х = х +1

е = е + Dy / Dx

Затем я

отделка

Блок-схема алгоритма на рис. 3. Пример приведен ниже.

Пример 1. Алгоритм Брезенхема.

Рассмотрим отрезок, проведенный из точки (0,0) в точку (5,5). Расписание отрезка в растр по алгоритму Брезенхема приводит к такому результату:

начальные установки

х = 0

у = 0

Dx = 5

Два = 5

= 1-1/2 = 1/2



Результаты работы пошагового цикла

я	Участок	и	х	и
1/2	0	0
1	(0,0)
-1 / 2	0	1
1/2	1	1
2	(1,1)
-1 / 2	1	2
1/2	2	2
3	(2,2)
-1 / 2	2	3
1/2	3	3
4	(3,3)
-1 / 2	3	4
1/2	4	4
5	(4,4)
-1 / 2	5	5
1/2	5	5

Рис. 3. Алгоритмы Блок-схема Brezenhema



Результат показан на рис. 4 совпадает с ожидаемым. Заметим, что точка растра с координатами (5,5) не активизирована. Эту точку можно активировать путем изменения цикла for-next на 0 to Dx. Активация точки (0,0) можно устранить, если поставить оператор Plot непосредственно перед строкой next i.

Рис. 4. Результат работы алгоритма Брезенхема в первом октанте

2. Общий алгоритм Брезенхема

Чтобы реализация алгоритма Брезенхема была полной необходимо рассмотреть отрезки во всех октантах. Модификацию легко сделать, учитывая в алгоритме номер квадранта, в котором лежит отрезок и его угловой коэффициент. Когда абсолютная величина углового коэффициента больше 1, в постоянно меняется на единицу, а критерий погрешности Брезенхема используется для принятия решения об изменении величины x. Выбор постоянно изменяемой координаты (на +1 или -1) зависит от квадранта (рис. 5). Общий алгоритм может быть оформлен в следующем виде:

Обобщенный целочисленный алгоритм Брезенхема квадрантов предполагается, что концы отрезка (x1, y1) и (x2, y2) не совпадают все переменные считаются целыми Sign - функция, возвращающая -1, 0, 1 для отрицательного, нулевого и положительного аргумента соответственно инициализация переменных



х = x1

у = y 1

Dx = абс (x2-x1)

Dy = абс (у2-у1)

s1 = Вход (x2-x1)

s2 = Вход (у2-у1)

обмен значений Dx и Dy в зависимости от углового коэффициента наклона отрезка

если Dy <Dx затем

Temp = Dx

Dx = Dy

Dy = Temp

Обмен = 1

еще

Обмен = 0

конец, если

инициализация e с поправкой на половину пиксела

е = 2 * Dy-DX

основной цикл

для г = 1, чтобы Dx

Земля (х, у)

в то время как (е => 0)

если Обмен = 1, то

х = х + s1

еще

у = у + s2

конец, если

е = е-2 * DX

конец в то время как

если Обмін = 1, то

у = у + s2

еще

х = х + s1

конец, если

е = е +2 * Dy

Затем я

отделка

Рис. 5. Рассмотрение случаев для обобщенного алгоритма Брезенхема

Для иллюстрации рассмотрим отрезок с точки (0, 0) в точку (-8, -4).

начальные установки

х = 0

у = 0

Dx = 8

Два = 4

s1 = -1

s2 = -1

Обмен = 0

е = 0

Результаты работы пошагового цикла

я	Участок	это	х	и
0	0	0
1	(0,0)
-16	0	-1
-8	-1	-1
2	(-1, - 1)
0	-2	-1
3	(-2, - 1)
-16	-2	-2
-8	-3	-2
4	(-3,2)
0	-4	-2
5	(-4,2)
-16	-4	-3
-8	-5	-3
6	(-5, - 3)
0	-6	-3
7	(-6, - 3)
-16	-6	-4
-8	-7	-4
8	(-7, - 4)
0	-8	-4

Рис. 6. Результат работы обобщенного алгоритма Брезенхема в третьем квадранте

На рис. 6 показан результат. Сравнивая рис. 3 видим, что результаты работы двух алгоритмов отличаются.



3. Алгоритм Брезенхема для генерации круга

В растр нужно разлагать не только линейные, но и другие, более сложные функции. Разложению конических сечений, т.е. окружностей, эллипсов, парабол, гипербол, было посвящено значительное число работ. Наибольшее внимание, разумеется, уделено кругу. Один из наиболее эффективных и простых для понимания алгоритмов генерации окружности принадлежит Брезенхему. Для начала заметим, что необходимо сгенерировать только одну восьмую часть окружности. Другие его части могут быть получены последовательными отражениями, как это показано на рис. 5.1. Если сгенерированный первый октант (от 0 до 45 ° против часовой стрелки), то второй октант можно получить зеркальным отражением относительно прямой y = х, что дает в совокупности первый квадрант. Первый квадрант отражается относительно прямой х = 0 для получения соответствующей части окружности во втором квадранте. Верхнее полуокружность отражается относительно прямой y = 0 для завершения построения. На рис. 7 приведены двумерные матрицы соответствующих преобразований.

Рис. 7. Генерация полного круга с дуги в первом октанте



Для вывода алгоритма рассмотрим первую четверть окружности с центром в начале координат. Заметим, что если работа алгоритма начинается в точке х = 0, у = R, то при генерации окружности по часовой стрелке в первом квадранте в является монотонно убывающей функцией аргумента х. Аналогично, если исходной точкой является у = 0, х = R, то при генерации окружности против часовой стрелки х будет монотонно убывающей функцией аргумента у. В нашем случае выбирается генерация по часовой стрелке с началом в точке х = 0, у = R. Предполагается, что центр круга и начальная точка находятся точно в точках растра.

Для любой заданной точки на окружности при генерации по часовой стрелке существует только три возможности выбрать следующий пиксел, наилучшим приближает круг горизонтально вправо, по диагонали вниз и вправо, вертикально вниз. Эти направления обозначены соответственно M_H, M_D, M_V. Алгоритм выбирает пиксел, для которого минимальный квадрат расстояния между одним из этих положений и кругом, то есть минимум с

м_H = | (х_я +1) ² + (у_я ) ² -R² |

м_D = | (х_я +1) ² + (у_я -1) ² -R² |

м_V = | (х_я ) ² + (у_я -1) ² -R² |

Разница между квадратами расстояний от центра окружности до диагонального пиксела (X_и +1, в_i -1) и от центра до точки на окружности R² равна

D_я = (х_я +1) ² + (у_я -1)² -R²

Как и в алгоритме Брезенхема для отрезка, для выбора соответствующего пиксела желательно использовать только знак погрешности, а не ее величину.

При D_и <0 диагональная точка (X_и +1, в_i - 1) находится внутри реального круга. Ясно, что в этой ситуации следует выбрать либо пиксел (X_и +1, в_i) , т.е. M_H, или пиксел (X_и +1, в_i - 1), т.е. M_D. Для этого сначала рассмотрим случай 1 и проверим разность квадратов расстояний от окружности до пикселов в горизонтальном и диагональном направлениях:

г = | (х_я +1) ² + (у_я )² -R² | - | (х_я +1)² + (у_я -1)² -R² |

При d <0 расстояние от окружности до диагонального пиксела больше, чем до горизонтального. Напротив, если d> 0, расстояние до горизонтального пиксела больше. Таким образом,

при d <= 0 выбираем M_H (X_и +1, в_i)

при d> 0 выбираем M_D (X_и +1, в_i -1)

При d = 0, когда расстояние от круга до обоих пикселов одинакова, выбираем горизонтальный шаг.

Количество вычислений, необходимых для оценки величины d, можно сократить, если заметить, что в случае 1

(Х_I +1)² + (у_I )² -R² > = 0

(Х_я +1) ² + (у_я -1)² -R² <0

потому что диагональный пиксел (X_и +1, в_i - 1) всегда лежит внутри круга, а горизонтальный (X_и +1, в_i ) - вне его. Таким образом, d можно вычислить по формуле

D = (х_I +1) ² + (у_I ) ² -R² + (х_I +1)² + (у_I -1)² -R²



Дополнение до полного квадрата члена (Y_и)² с помощью сложения и вычитания - 2Y_и + 1 дает

г = 2 [(х_я +1)² + (у_я -1)² -R²] +2у_я - 1

В квадратных скобках стоит по определению D_и и его подстановка

г = 2 (D_я + у_я) - 1

значительно упрощает выражение.

Рассмотрим случай 2, заметим, что здесь должен быть избранным горизонтальный пиксел (X_и +1, в_i), так как в является монотонно убывающей функцией. Проверка компонентов d показывает, что

(Х_I +1)² + (у_I) ² -R² <0

(Х_я +1)² + (у_я -1)² -R² <0

поскольку в случае 2 горизонтальный (X_и +1, в_i ) и диагональный (X_и +1, в_i -1) пикселы лежат внутри круга. Итак, d <0, и при использовании того же самого критерия, что и в случае 1, выбирается пиксел (X_и+1, в_i).

Если D_и > 0, то диагональная точка (X_и +1, в_i -1) находится вне круга, то есть это случаи 3 и 4. В данной ситуации ясно, что нужно выбрать пиксел (X_и +1, в_i -1), или (X_и, в_i -1). Аналогично рассмотрения предыдущего случая критерий выбора можно получить, рассматривая сначала случай 3 и проверяя разность между квадратами расстояний от окружности до диагонального M _D и вертикального M _V пикселей, то есть

д ' = | (х_я +1)² + (у_я -1)² -R² | - | (х_я)² + (у_я -1)² -R² |.



При d' < 0 расстояние от окружности до вертикального пиксела (X_и, в_i -1) больше и следует выбрать диагональный шаг к пиксела (X_и +1, в_i -1). Напротив, в случае d' > 0 расстояние от окружности до диагонального пиксела больше и следует выбрать вертикальное движение к пиксела (X_и, в_i -1). Таким образом, при d' <= 0 выбираем M_D (X_и +1, в_i -1), при d' > 0 выбираем M_V (X_и, в_i -1).

Здесь для случая d ' = 0, т.е. когда расстояния равны, выбран диагональный шаг.

Проверка компонентов d ' показывает, что

(Х_я)² + (у_я -1)² -R² > = 0

(Х_я +1)² + (у_я -1)² -R² <0

поскольку для случая 3 диагональный пиксел (X_и +1, в_i -1) находится вне круга, тогда как вертикальный пиксел (X_и, в_i -1) лежит внутри круга. Это позволяет записать d ' в виде

д ' = (х_я +1)² + (у_я -1)² -R² + (х_я)² + (у_я -1)² -R²

Дополнение до полного квадрата члена (X_и)² с помощью добавления и вычитания 2x_и +1 дает

д ' = 2 [(х_я +1)² + (у_я -1)² -R² ]-2x_я -1

Использование определения D _и приводит выражение к виду

д' = 2 (D_я - х_я ) - 1



Теперь, рассматривая случай 4, снова заметим, что следует выбрать вертикальный пиксел (X_и, в_i-1), так как y является монотонно убывающей функцией от х.

Проверка компонентов d' для случая 4 показывает, что

(Х_я +1)² + (у_я -1)² -R² > 0

(Х_я)² + (у_я -1)² -R² > 0

Поскольку оба пиксела находятся вне круга. Итак, d' > 0 и при использовании критерия, разработанного для случая 3, происходит верный выбор M_V.

Осталось проверить только случай 5, который встречается, когда диагональный пиксел (X_и +1, в_i -1) лежит на окружности, то есть D_и = 0. Проверка компонентов d показывает, что

(Х_я +1) ² + (у_я)² -R² > 0

(Х_я 1)² + (у_я -1)² -R² = 0

Итак, d> 0 и выбирается диагональный пиксел (X_и +1, в_i -1). Аналогичным образом оцениваем компоненты d':

(Х_я 1)² + (у_я -1)² -R² = 0

(Х_я +1)² + (у_я -1)² -R² <0

и d' <0, что является условием выбора правильного диагонального шага к (X_и +1, в_i -1). Таким образом, случай D_и = 0 подлежит тому же критерию, что и случай D_и <0 или D_и > 0. Подведем итог полученных результатов:

D_я <0

d <= 0 вибираем пиксел (X_и +1, в_i ) - M_H

d > 0 выбираем пиксел (X_и +1, в_i -1) - M_D

D_я > 0

d' <= 0 выбираем пиксел (X_и +1, в_i -1) - M_D

d' > 0 выбираем пиксел (X_и, в_i -1) - M_V

D_и = 0 выбираем пиксел (X_и +1, в_i -1) - M_D

Легко разработать простые рекуррентные соотношения для реализации пошагового алгоритма. Сначала рассмотрим горизонтальный шаг M _H к пиксела (X _и +1, в _i). Обозначим это новое положение пиксела как (i +1). Тогда координаты нового пиксела и значение D _и уровне

х_{я +1} = х_я +1

у_{я +1} = у_я

D_{я +1} = (х_{я +1} +1)² + (у_{I +1} -1)² -R² = D_I 2х_{я +1} +1

Аналогично координаты нового пиксела и значение D_и для шага M_D к пиксела (X_и +1, в_i -1) таковы:

х_{я +1} = х_я +1

у_{я +1} = у_я -1

D_{я +1} = D_я +2 х_{я +1} -2y_{я +1} +2

То же самое для шага M_V до (X_и, в_i -1)

х_{я +1} = х_я

у_{я +1} = у_я -1

D_{я 1} = D_я -2y_{я +1} +1

Реализация алгоритма Брезенхема на псевдокоде для круга приводится ниже.

Пошаговый алгоритм Брезенхема для генерации окружности в первом квадранте все переменные - целые инициализация переменных

х_я = 0

у_я = R

D_я = 2 (1-R)

Предел = 0

1 земля (х_я, у_я)

если у_я <= Межа затем 4

Выделение случая 1 или 2, 4 или 5, или 3

если D_я < 0 затем 2

если D_я > 0, то 3

если D_я = 0, то 20

определение случая 1 или 2

2d = 2D_я 2 у_I -1

если г <= 0, то 10

если D> 0, то 20

определение случая 4 или 5

3d = 2D_я 2 х_I - 1

если г <= 0, то 20

если г > 0, то 30

выполнения шагов

шаг до m

10х_я = х_я +1

D_я = D_я 2 х_I 1

gо 1

шаг m

20х _я = х_я +1

у_я = у_я +1

D_я = D_я 2 х_я -2у_я +2

gо 1

4 отделка



Переменная границы устанавливается в ноль для окончания работы алгоритма на горизонтальной оси, в результате генерируется круг в первом квадранте. Если необходим только один из октантов, то второй октант можно получить с помощью установки Предел = Integer (R / sqrt (2)), а первый - за счет отражения второго октанта относительно прямой у = х (рис. 6). Блок-схема алгоритма показана на рис. 8.

Рис. 8. Блок-схема пошагового алгоритма Брезенхема для генерации окружности в первом квадранте



Рассмотрим окружность радиусом 8 с центром в начале координат. Генерируется только первый квадрант.

х = 0

у = 8

2 (1-8) = -14

Предел = 0

Пошаговое выполнение основного цикла

1 земля (0,8)

yi> Предел (продолжать)

Ди <0 перейти к этапу 2

2D = 2 (-14) +2 (8) - 1 = -13 <0 К 10

10x = 0 +1 = 1

Ди = -14 +2 +1 = -11

перейдите к 1

1 земля (1,8)

yi> Предел (продолжать)

Ди <0 перейти к этапу 2

2D = 2 (-11) +2 (8) - 1 = -7 <0 К 10

10x = 1 +1 = 1

= -11 До +2 (2) +1 = -6

перейдите к 1

1 земля (2,8)

Результаты всех последовательных проходов алгоритма сведены в таблицу. Список точек выбранных алгоритмов состоит из (0,8), (1,8), (2,8), (3,7), (4,7), (5,6), (6,5), (7 , 4), (7,3), (8,2), (8,1), (8,0).



Участок	Из	г	д '	х	и
-14	0	8
(0,8)
-11	-13	0	8
(1,8)
-6	-7	2	8
(2,8)
-12	3	3	7
(3,7)
-3	11	4	7
(4,7)
1	5	6	5
(6,5)
9	-11	7	4
(7,4)
18	-7	8	2
(8,2)
17	19	8	1
(8,1)
18	17	8	0
(8,0)

Результаты показаны на рис. 9 вместе с реальным кругом. Алгоритм легко обобщается для других квадрантов или дуг окружностей.

Рис. 9. Результаты работы пошагового алгоритма Брезенхема генерации круга

Размещено на Allbest.ru

...