7.5. Алгоритм Брезенхема
для генерування кола
У растр потрібно розкладати не
лише лінійні, але й інші, більш складні функції. Розкладання конічних
перерізів, тобто кіл, еліпсів, парабол, гіпербол, було присвячено значну
кількість робіт. Один з найбільш ефективних і простих для розуміння алгоритмів
генерації кола належить Брезенхему. Для початку
зауважимо, що необхідно згенерувати лише одну восьму частину кола. Решта її
частин можуть бути отримані послідовними відбитками, як це наведено на рис.
7.9. Якщо згенерований перший октант (від 0 до 45° проти годинникової стрілки),
то другий октант можна отримати дзеркальним відображенням відносно прямої 
, що дає в сукупності
перший квадрант. Перший квадрант відбивається відносно прямої 
для отримання відповідних перетворень.
Рис. 7.9. Генерація повної
окружності з дуги в першому октанті
Для виведення алгоритму
розглянемо першу чверть кола з центром у початку координат. Зауважимо, що якщо
робота алгоритму починається в точці , 
, то при генерації кола за
годинниковою стрілкою в першому квадранті 
є монотонно спадною функцією аргументу 
(рис. 7.10). Аналогічно, якщо вихідною точкою
є 
, то при генерації кола
проти годинникової стрілки буде монотонно спадаючою функцією аргументу .
У нашому випадку вибирається
генерація за годинниковою стрілкою з початком в точці 
. Передбачається, що центр
кола та початкова точка знаходяться точно в точках растру.
Для будь-якої заданої точки на
колі при генерації за годинниковою стрілкою існує лише три можливості вибрати
наступний піксель, що найкращим чином наближає коло: горизонтально вправо, по
діагоналі вниз і вправо, вертикально вниз.
На рис. 7.11 ці напрямки
позначені відповідно 
, 
, 
. Алгоритм вибирає
піксель, для якого мінімальний квадрат відстані між одним із цих пікселів і
колом, тобто мінімум
Рис. 7.10. Коло в першому квадранті Рис. 7.11. Вибір пікселів в
першому
квадранті
Обчислення можна спростити, якщо
зауважити, що в околі точки 
можливі лише п'ять типів перетинів кола та
сітки растру, що наведені на рис. 7.12.
Рис.
7.12. Перетин кола та сітки растру
Різниця між квадратами відстаней
від центра кола до діагонального пікселя 
і від центра до точки на колі 
дорівнює:
.
Як і в алгоритмі Брезенхема для відрізка, для вибору відповідного пікселя
бажано використовувати лише знак помилки, а не її величину.
При 
діагональна точка знаходиться всередині реального кола, тобто,
це випадки 1 або 2 наведені на рис. 7.12. Ясно, що в даній ситуації слід
вибрати чи піксель 
, тобто 
, чи піксель , тобто, . Для цього спочатку
розглянемо випадок 1 і перевіримо різницю квадратів відстаней від кола до
пікселів у горизонтальному і діагональному напрямках:
При 
відстань від кола до діагонального пікселя 
більша, ніж до горизонтального 
. Навпаки, якщо 
, відстань до
горизонтального пікселя більше. Таким чином,
,
.
При 
, коли відстань від кола
до обох пікселів однакова, вибираємо горизонтальний крок.
Кількість обчислень, необхідних
для оцінки величини 
, можна скоротити, якщо
зауважити, що у випадку 1:
,
,
оскільки діагональний піксель 
завжди лежить в колі, а горизонтальний − поза ним. Таким чином, можна обчислити за формулою:
.
Доповнення до повного квадрата
члена 
, з допомогою додавання і
віднімання 
, 
дає
.
У квадратних дужках стоїть за
визначенням 
і його підстановка істотно спрощує вираз.
Розглянемо випадок 2 наведений на
рис. 7.12 і зауважимо, що тут повинен бути вибраний горизонтальний піксель , оскільки є монотонно спадною функцією. Перевірка,
компонента показує, що
,
.
оскільки в випадку 2 горизонтальний
та діагональний 
пікселі лежать у колі. Отже, , і при використанні того
ж самого критерію, що й у випадку 1, вибирається піксель .
Якщо 
, то діагональна точка 
знаходиться за колом, тобто це випадок 3 і 4
наведені на рис. 7.12. У даній ситуації зрозуміло, що потрібно обрати або
піксель , тобто, , або 
, тобто, 
. Аналогічно розгляду
попереднього випадку критерій вибору можна отримати, розглядаючи спочатку
випадок 3 і перевіряючи різницю між квадратами відстаней від кола до
діагонального і вертикального , пікселів, тобто,
.
При 
відстань від кола до вертикального пікселя 
більша і слід вибрати діагональний крок 
до пікселя 
. І навпаки, у випадку 
відстань від кола до діагонального пікселя
більша і слід вибрати вертикальний рух до пікселя 
. Таким чином,
при 
вибираємо в 
,
при вибираємо 
в 
.
Тут у випадку 
, тобто коли відстані
рівні, обраний діагональний крок.
Перевірка
компонента 
показує, що:
,
.
Оскільки для випадку 3
діагональний піксель 
знаходиться за колом, тоді як вертикальний
піксель лежить всередині його. Це дозволяє записати у вигляді:
.
Доповнення до повного квадрата
члена 
за допомогою додавання і віднімання 
дає:
Використання визначення 
приводить вираз до виду:
.
Тепер розглядаємо випадок 4, та
знову зауважимо, що слід вибрати вертикальний піксель , оскільки 
є монотонно спадаючою функцією при зростанні 
.
Перевірка
компонент 
для випадку 4 показує, що:
,
.
Оскільки обидва пікселя
знаходяться за колом то, і при використанні критерію, розробленого для випадку
3, відбувається вірний вибір 
.
Залишилось перевірити лише
випадок 5 наведений на рис. 7.12, який зустрічається, коли діагональний піксель
лежить на колі, тобто 
. Перевірка компонента 
показує, що:
,
.
Отже, 
і обирається діагональний піксель 
. Аналогічним чином
оцінюємо компоненти :
,
.
І , що є умовою вибору
правильного діагонального кроку до 
. Таким чином, випадок 
підпорядковується тому ж критерію, що й
випадок 
або 
.
Підіб'ємо
підсумок отриманих результатів:
Вибираємо піксель 
Вибираємо піксель 
Вибираємо піксель
Вибираємо піксель 
Вибираємо піксель 
.
Легко розробити прості рекурентні
співвідношення для реалізації покрокового алгоритму. Спочатку розглянемо
горизонтальний крок 
до пікселя 
. Позначимо це нове
положення пікселя як 
. Тоді координати нового
пікселя і значення 
рівні
Аналогічно координати нового
пікселя і значення для кроку 
до пікселя 
такі:
Те
ж саме для кроку 
до
Реалізація алгоритму Брезенхема на псевдокоді для кола подана нижче.
Покроковий алгоритм Брезенхема
для створення кола в першому квадранті
всі
змінні – цілі
ініціалізація
змінних
межа = 0
1.
Plot 
if 
Межа then 4
Виділення
випадку 1 або 2, 4 або 5, або 3
if 
then 2
if 
then 3
if 
then 20
визначення
випадку 1 або 2
2.
If then 10
If 
then 20
визначення випадку 4 або 5
3.
if then 20
if then 30
виконання кроків
крок
10. 
go to 1
крок 
20. 
go to 1
крок 
30.
go to 1
4.
finish
Зміна межі встановлюється в нуль
для закінчення роботи алгоритму на горизонтальній осі в результаті генерується
коло в першому квадранті. Якщо необхідний лише один з октантів, то другий
октант можна отримати 
за допомогою установки Межа = Integer 
, а перший 
за допомогою відображення другого октанта
відносно прямої 
. Блок-схема алгоритму
наведена на рис. 7.13.
Рис. 7.13. Блок-схема покрокового алгоритму Брезенхема
створення кола в першому квадранті
Приклад 7.5. Алгоритм
Брезенхема для кола.
Для ілюстрації роботи алгоритму
генерації кола розглянемо коло радіусом 8, з центром у початку координат.
Генерується лише перший квадрант
початкові
дані
Покрокове виконання основного циклу
1.
Plot (0,8)
Межа продовжувати
go to 2
2.
go to 10
10. 
go to 1
1.
Plot (1, 8)
Межа
продовжувати
go to 2
2.
go to 10
10. 
go to 1
1.
Plot (2, 8)
–
–
–
продовжувати
Результати всіх послідовних проходжень алгоритму зведені в
таблицю. Список пікселів, обраних алгоритмом, складається з (0, 8), (1, 8), (2,
8), (3, 7), (4, 7), (5,6), (6, 5), (7, 3), (8, 2), (8, 1), (8, 0)
|
Plot |
|
δ |
|
x |
Y |
|
|
|
|
|
0 |
8 |
|
(0, 8) |
|
|
|
|
|
|
|
−11 |
−13 |
|
1 |
8 |
|
(1, 8) |
|
|
|
|
|
|
|
−6 |
−7 |
|
2 |
8 |
|
(2, 8) |
|
|
|
|
|
|
|
−12 |
3 |
|
3 |
7 |
|
(3, 7) |
|
|
|
|
|
|
|
−3 |
−11 |
|
4 |
7 |
|
(4, 7) |
|
|
|
|
|
|
|
−3 |
−7 |
|
5 |
6 |
|
(5, 6) |
|
|
|
|
|
|
|
1 |
5 |
|
6 |
5 |
|
(6, 5) |
|
|
|
|
|
|
|
9 |
|
−11 |
7 |
4 |
|
(7, 4) |
|
|
|
|
|
|
|
4 |
|
3 |
7 |
3 |
|
(7, 3) |
|
|
|
|
|
|
|
18 |
|
−7 |
8 |
2 |
|
(8, 2) |
|
|
|
|
|
|
|
17 |
|
19 |
8 |
1 |
|
(8, 1) |
|
|
|
|
|
|
|
18 |
|
17 |
8 |
0 |
|
(8, 0) |
|
|
|
|
|
|
Алгоритм закінчено |
|||||
Результати наведені на рис. 7.14
разом із реальною окружністю. Алгоритм легко узагальнюється для інших
квадрантів або дуг кіл.
Рис. 7.14. Результати роботи покрокового алгоритму Брезенхема генерації кола
Приклади
реалізації
Приклад
7.6. Використовуючи
ЦДА та алгоритм Брезенхема, написати програму для
викреслювання відрізків з однієї довільної точки в іншу на псевдорастрі
32×32. Використовуйте псевдобуфер кадру у
вигляді одномірного масиву спочатку для зберігання зображення, а тоді для
виводу його з псевдобуфера на екран. Демонстраційний
текст повинен складатися, принаймні, з 16 відрізків з початком у центрі кола і
кінцями, що рівномірно розташовані по колу. Необхідно забезпечити можливість
встановлювати центр кола в довільну точку растру. Візуально порівняєте
результати. Введіть список активованих пікселів для відрізка з (0,0) в (-8, -3)
для обох алгоритмів. Як впливає на результат ініціалізація? Порівняйте
обчислювальну ефективності двох алгоритмів шляхом хронометражу розкладених в
растр 100 випадково вибраних відрізків.
uses graph;
var
grDriver: Integer;
grMode: Integer;
function sign(v:real): integer;
begin
if v>0 then sign:=1;
if v=0 then sign:=0;
if v<0 then sign:=-1;
end;
procedure p_line(x1,y1,x2,y2:integer);
var
x,y,dx,dy,len:real;
i:integer;
begin
if abs(x2-x1)>=abs(y2-y1) then begin
len:=abs(x2-x1);
end else
len:=abs(y2-y1);
dx:=(x2-x1)/len;
dy:=(y2-y1)/len;
x:=xl+0.5*sign(dx);
y:=yl+0.5*sign(dy);
i:=l;
while (i<=len) do begin
putpixel(trunc(x),trunc(y),10);
x;=x+dx;
y:=y+dy;
inc(i);
end;
end;
procedure b_line(xl,y1,x2,y2:integer);
var
tmp,e,x,y,dx,dy:real;
xchng,i,s1,s2:integer;
begin
x:=x1;
y:=y1;
dx:=abs(x2-x1);
dy:=abs(y2-y1);
s1:=sign(x2-x1);
s2:=sign(y2-y1);
if dy>dx then begin
tmp:=dx;
dx:=dy;
dy:=tmp;
xchng:=1;
end else
xchng:=0;
e:=2*dy-dx;
for i:=l to trunc(dx) do
begin
putpixel(trunc(x),tnmc(y),12);
while e>=0 do begin
if xchng=1 then x:=x+s1
else
y:=y+s2;
e:=e~2*dx;
end;
if xchng=1 then
y:=y+s2
else
x:=x+sl;
e:=e+2*dy;
end;
end;
function readkey:word;
var
ww:word;
begin
asm
mov ah,10h
int$16
mov ww,ax
end;
readkey:=ww;
end;
begin
{init graphiX}
grDriver:=EGA;
grMode:=2;
InitGraph(grDriver,grMode,");
p_line(50,100,2,160);
b_line(200,l
10,2,150);
readkey;
end.
Приклад 7.7. Коло, розкладене в растр, можна отримати за
допомогою алгоритму Брезенхема для генерації кола,
описаного в розділі 7.6. його можна також згенерувати шляхом розкладення в
растр ребер вписаного багатокутника за допомогою
алгоритму Брезенхема для відрізка. Напишіть програму,
яка б реалізувала обидва методи, та розкладіть в растр коло радіусом R=15 на
растрі 32x32. Порівняйте результати для вписаних багатокутників з 4, 8, 16, 32,
64, 128 сторонами для алгоритму генерації кола. Використайте псевдобуфер кадра у вигляді одновимірного масиву спочатку
для збереження інформації, а тоді для виводу його з псевдобуфера
на дисплей. Передбачте вивід списку растрових точок, використовуючи формат
«стрічка-колонка» для кожного алгоритму у припущенні, що початок координат
(0,0) знаходиться в нижньому лівому куті. Результати порівняйте візуально і чисельно.
uses graph;
var
grDriver:
Integer;
grMode: Integer;
ErrCode:
Integer;
procedure
putP(x,y:integer);
begin
putpixel(x+100,y+50,15);
end;
procedure
BrezenchemPlot(x1,y1,x2,y2:integer);{-- npoцедура побудови відрізка алгоритмом Брезенхема}
var
i,x,y,dx,dy,tmp,ch,s1,s2,e:integer;
begin
x:=x1;
y:=y1;
dx:=abs(x2-x1);
dy:=abs(y2-y1);
if dx=0 then s1:=0 else s1:=(x2-x1) div
dx;
if dy=0 then s2:=0 else s2:=(y2-y1) div dy;
if dy>dx then
begin
tmp:=dx;
dx:=dy;
dy:=tmp;
ch:=1;
end
else ch:=0;
e:=2*dy-dx;
for i:=1 to dx do
begin
putpixel(x+150,y+50,10);
while е>=0 do
begin
if ch=1 then x:=x+s1
else
y:=y+s2;
e:=e-2*dx;
end;
if ch=1 then y:=y+s2
else
x:=x+s1;
e:=e+2*dy;
end;
end;
procedure BrezenchemCircle;{--процедура побудови кола за алгоритмом Брезенхема}
var x,y,d,g,r,l:integer;
begin
r:=15;
х:=0;
у:=r;
d:=2*(1-r);
l:=trunc(r/sqrt(2));
repeat
putp(x,y);
putp(-x,y);
putp(x,-y);
putp(-x,-y);
putp(y,x);
putp(-y,x);
putp(y,-x);
putp(-y,-x);
if d=0 then
begin
x:=x+1;
y:=y-1;
d:=d+2*x-2*y+2;
end
else if d<0 then
begin
g;=2*d+2*y-1;
if g<=0 then
begin
x:=x+1;
d:=d+2*x+1;
end;
end
else
begin
g:=2*d+2*x-1;
if g<=0 then
begin
x:=x+1;
y:=y-1;
d:=d+2*x-2*y+2;
end
else
begin
y:=y-1;
d:=d-2*y+1;
end;
end;
until y<=1;
end;
procedure VidrCircle(sg:integer);{--
процедура побудови кола по відрізкам вписаного багатокутника}
var r,x1,y1,x2,y2,i:integer;
phi:real;
begin
r:=15;
phi:=PI*2/sg;
for i:=1 to
sg do
begin
x1:=round(r*sin(phi*(i-1)));
у1:=round(r*cos(phi*(i-1)));
x2:=round(r*sin(phi*i));
y2:=round(r*cos(phi*i));
BrezenchemPlot(x1,y1,x2,y2);
end;
end;
begin
grDriver:=Detect; {--ініціалізація
графічного режиму}
InitGraph(grDriver,grMode,");
{ ..}
ErrCode:=GraphResult; { ..}
if ErrCode <>grOk then Writeln('Graphics
error:',GraphErrorMsg(ErrCode));
VidrCircle(128); {--побудова кола за відрізками
(4,8,16,32,64,128)}
BrezenchemCircle; {-- побудова кола за алгоритмом Брезенхема}
Readln;
CloseGraph;
end.
