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

В растр нужно разлагать не только линейные, но и другие, более сложные функции. Наибольшее внимание, разумеется, уделено окружности. Один из наиболее эффективных и простых для понимания алгоритмов генерации окружности принадлежит Брезенхему.

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

 

Для любой заданной точки на окружности при генерации по часовой стрелке существует только три возможности выбрать следующий пиксел, наилучшим образом приближающий окружность: горизонтально вправо, по диагонали вниз и вправо, вертикально вниз. На рис. 2.7 эти направления обозначены соответственно Mh, Md, Mv. Алгоритм выбирает пиксел, для которого минимален квадрат расстояния между одним из этих пикселов и окружностью, т. е.

 

Mh = |(x_i + 1)² + (y_i)² -R²|
Md = |(x_i + 1)² + (y_i - 1)² -R²|
Mv = |(x_i)² + (y_i - 1)² -R²|

 

Вычисления можно упростить, если заметить, что в окрестности точки (x_i,y_i) возможны только пять типов пересечений окружности и сетки растра, приведенных на рис. 2.8.

 

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

 

Δ_i = (x_i + 1)² + (y_i - 1)² - R²

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

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

 

δ = |(x_i + 1)² + (y_i)² - R²| - |(x_i + 1)² + (y_i - 1)² - R²|

 

При δ < 0 расстояние от окружности до диагонального пиксела (Md) больше, чем до горизонтального (Mh). Напротив, если δ > 0, расстояние до горизонтального пиксела (Mh) больше. Таким образом,
при δ <= 0 выбираем Mh в (x_i + 1, y_i)
при δ > 0 выбираем Md в (x_i + 1, y_i - 1)
При δ = 0, когда расстояние от окружности до обоих пикселов одинаковы, выбираем горизонтальный шаг.

Количество вычислений, необходимых для оценки величины δ, можно сократить, если заметить, что в случае 1
(x_i + 1)² + (y_i)² - R² >= 0
(x_i + 1)² + (y_i - 1)² -R² < 0
так как диагональный пиксел (x_i + 1, y_i - 1) всегда лежит внутри окружности, а горизонтальный (x_i + 1, y_i) - вне ее. Таким образом, δ можно вычислить по формуле

δ = (x_i + 1)² + (y_i)² - R² + (x_i + 1)² + (y_i - 1)² - R²

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

δ = 2[(x_i + 1)² + (y_i - 1)² - R²] + 2y_i -1

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

δ = 2(Δ_i + y_i) - 1

существенно упрощает выражение.
Рассмотрим случай 2 на рис. 2.8 и заметим, что здесь должен быть выбран горизонтальный пиксел (x_i + 1, y_i), так как y является монотонно убывающей функцией. Проверка компонент δ показывает, что
(x_i + 1)² + (y_i)² - R² < 0
(x_i + 1)² + (y_i - 1)² - R² < 0
поскольку в случае 2 горизонтальный (x_i + 1, y_i) и диагональный (x_i + 1, y_i - 1) пикселы лежат внутри окружности. Следовательно, δ < 0, и при использовании того же самого критерия, что и в случае 1, выбирается пиксел (x_i + 1, y_i).

Если Δ_i > 0, то диагональная точка (x_i + 1, y_i - 1) находится вне окружности, т. е. это случаи 3 и 4 на рис. 2.8. В данной ситуации ясно, что должен быть выбран либо пиксел (x_i + 1, y_i - 1), т. е. Md, либо (x_i, y_i - 1), т. е. Mv. Аналогично разбору предыдущего случая критерий выбора можно получить, рассматривая сначала случай 3 и проверяя разность между квадратами расстояний от окружности до диагонального Md и вертикального Mv пикселов, т. е.

δ' = |(x_i + 1)² + (y_i - 1)² -R²| - |(x_i)² + (y_i - 1)² -R²|

При δ' < 0 расстояние от окружности до вертикального пиксела (x_i, y_i - 1), больше и следует выбрать диагональный шаг Md, к пикселу (x_i + 1, y_i - 1). Напротив, в случае δ' > 0 расстояние от окружности до диагонального пиксела больше и следует выбрать вертикальное движение к пикселу (x_i, y_i - 1). Таким образом,
при δ' <= 0 выбираем Md в (x_i + 1, y_i - 1)
при δ' > 0 выбираем Mv в (x_i, y_i - 1)
Здесь в случае δ' = 0, т. е. когда расстояния равны, выбран диагональный шаг.

Проверка компонент δ' показывает, что (x_i + 1)² + (y_i - 1)² - R² >= 0
(x_i)² + (y_i - 1)² - R² < 0
поскольку для случая 3 диагональный пиксел (x_i + 1, y_i - 1) находится вне окружности, тогда как вертикальный пиксел (x_i, y_i - 1) лежит внутри ее. Это позволяет записать δ' в виде

δ' = (x_i + 1)² + (y_i - 1)² - R² + (x_i)² + (y_i - 1)² - R²

Пополнение до полного квадрата члена (xi)2 с помощью добавления и вычитания 2xⁱ + 1 дает

δ' = 2[(x_i + 1)² + (y_i - 1)² - R²] - 2x_i - 1

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

δ' = 2(Δ_i - x_i) - 1

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

Проверка компонент δ' для случая 4 показывает, что
(x_i + 1)² + (y_i - 1)² - R² > 0
(x_i)² + (y_i - 1)² - R² > 0
поскольку оба пиксела находятся вне окружности. Следовательно, δ' > 0 и при использовании критерия, разработанного для случая 3, происходит верный выбор Mv.

Осталось проверить только случай 5 на рис. 2.8, который встречается, когда диагональный пиксел (x_i + 1, y_i - 1) лежит на окружности, т. е. Δ_i = 0. Проверка компонент δ показывает, что
(x_i + 1)² + (y_i)² - R² > 0
(x_i + 1)² + (y_i - 1)² - R² = 0
Следовательно, δ > 0 и выбирается диагональный пиксел (x_i + 1, y_i - 1). Аналогичным образом оцениваем компоненты δ':
(x_i + 1)² + (y_i - 1)² - R² = 0
(x_i)² + (y_i - 1)² - R² < 0
и δ' < 0, что является условием выбора правильного диагонального шага к (x_i + 1, y_i - 1). Таким образом, случай Δ_i = 0 подчиняется тому же критерию, что и случай  Δ_i < 0 или Δ_i > 0.

Подведем итог полученных результатов:
Δ_i < 0
δ <= 0 выбираем пиксел (x_i + 1, y_i) ==> Mh
δ > 0 выбираем пиксел (x_i + 1, y_i - 1) ==> Md
Δ_i > 0
δ' <= 0 выбираем пиксел (x_i + 1, y_i - 1) ==> Md
δ' > 0 выбираем пиксел (x_i, y_i - 1) ==> Mv
Δ_i = 0 выбираем пиксел (x_i + 1, y_i - 1) ==> Md

Легко разработать простые рекуррентные соотношения для реализации пошагового алгоритма. Сначала рассмотрим горизонтальный шаг Mh к пикселу (x_i + 1, y_i). Обозначим это новое положение пиксела как (i + 1). Тогда координаты нового пиксела и значение Δ_i равны
x_i+1 = x_i + 1
y_i+1 = y_i
Δ_i+1 = (x_i+1 + 1)² + (y_i+1 - 1)² - R² = (x_i+1)² + 2x_i+1 + 1 + (y_i - 1)² - R² = (x_i + 1)² + (y_i - 1)² - R² + 2x_i+1 + 1 = Δ_i + 2x_i+1 + 1
Аналогично координаты нового пиксела и значение Δ_i для шага Md к пикселу (x_i + 1, y_i - 1) таковы:
x_i+1 = x_i + 1
y_i+1 = y_i - 1
Δ_i+1 = Δ_i + 2y_i+1 + 1

То же самое для шага Mv к (x_i, y_i - 1)
x_i+1 = x_i
y_i+1 = y_i - 1
Δ_i+1 = Δ_i - 2y_i+1 + 1
Реализация алгоритма Брезенхема на псевдокоде для окружности приводится ниже.

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

 

	хi = 0; yi = R; Δi = 2(1 - R);	/ инициализация переменных
1	Предел = 0; Plot(xi, уi)= R; If уi <= Предел then 4;
	if Δi < 0 then 2 if Δi > 0 then 3 if Δi = 0 then 20	/ выделение случая 1 или 2, 4 или 5, или 3
2	δ = 2Δi + 2уi - 1 if δ <= 0 then 10 if δ > 0 then 20	/ определение случая 1 или 2
3	δ = 2Δi - 2xi - 1 if δ <= 0 then 20 if δ > 0 then 30	/ определение случая 4 или 5
10	xi = xi + 1 Δi = Δi + 2xi + 1 go to 1	/ шаг Mh
20	xi = xi + 1 yi = yi - 1 Δi = Δi + 2xi - 2yi + 2 go to 1	/ шаг Md
30	yi = yi - 1 Δi = Δi - 2yi + 1 go to 1	/ шаг Mv
4	finish

Пример 2.2. Алгоритм Брезенхема для окружности.
Для иллюстрации работы алгоритма генерации окружности рассмотрим окружность радиуса 8 с центром в начале координат. Генерируется только первый квадрант.
x = 0
y = 8
Δ_i = 2(1 - 8) = -14
Предел = 0

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

 

1	Plot (0,8) yi > Предел Δi < 0 go to 2	продолжать
2	δ = 2(-14) +2(8) - 1 = -13 < 0 go to10
10	x = 0 + 1 =1; Δi = -14 + 2 + 1 = -11; go to 1
1	Plot (1,8) yi > Предел Δi < 0 go to 2	продолжать
2	δ = 2(-11) +2 · 8 -1 = -7 < 0 go to 10
10	x = 1 + 1 =2; Δi = -11 + 2(2) + 1 = -6; go to 1
1	Plot (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).

 

Plot	Δi	δ	δ'	x	y
(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 -11 -6 -12 -3 -3 1 9 4 18 17 18	-13 -7 3 -11 7 5	-11 3 -7 19 17	0 1 2 3 4 5 6 7 7 8 8 8	8 8 8 7 7 6 5 4 3 2 1 0
алгоритм завершен

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