Реферат
На тему:
«
Алгоритм Брезенхема
»
Львів-2011
1. Алгоритм Брезенхема
Хоча алгоритм Брезенхема був спочатку розроблений для цифрових графопобудовувачів, однак він в тій же мірі підходить для використання растровими пристроями з ЕПТ. Алгоритм вибирає оптимальні растрові координати для представлення відрізка. У процесі роботи одна з координат – або x, або y (в залежності від кутового коефіцієнта) – змінюється на одиницю. Зміна іншої координати (на 0 чи 1) залежно від відстані між дійсним положенням відрізка і найближчих координат сітки. Таку відстань ми назвемо похибкою.
Алгоритм побудований так, що потрібно перевірити лише знак цієї похибки. На рис. 3.1 це ілюструється для відрізка в першому октанті, тобто для відрізка з кутовим коефіцієнтом, що лежить у діапазоні від 0 до 1. З малюнка можна помітити що, якщо кутовий коефіцієнт відрізка з точки (0,0) більший, ніж 1/2, то перетин з прямою x=1 буде розташований ближче до прямої y=1, ніж до прямої y=0. Отже, точка растра (1,1) краще апроксимує хід відрізка, ніж точка (1,0). Якщо кутовий коефіцієнт менше 1/2, то навпаки. для кутового коефіцієнта, рівного 1/2, немає кращого вибору. У даному випадку алгоритм вибирає точку (1,1).
Основна ідея алгоритму Брезенхема
Не усі відрізки проходять через точки растра. Подібна ситуація ілюструється рис. 3.2, де відрізок з тангенсом кута нахилу 3/8 спочатку проходить через точку растра (0,0) і послідовно перетинає три піксели. Також ілюструється обчислення похибки при представленні відрізка дискретними пікселами.
Графік похибки в алгоритмі Брезенхема
Тому що бажано перевіряти тільки знак похибки, то вона спочатку встановлюється рівною -1/2. Таким чином, якщо кутовий коефіцієнт відрізка дорівнює чи більший 1/2, то величина похибки в наступній точці растра з координатами (1,0) може бути обчислена як
e=e+m
де m – кутовий коефіцієнт. У нашому випадку при початковому значенні похибки -1/2
e=-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 – функція перетворення в ціле
x, y, Dx, Dy – цілі
е – дійсне
ініціалізація змінних
x=x1
y=y1
Dx=x2-x1
Dy=y2-y1
Ініціалізація з виправленням на половину піксела
е=Dy/Dx-1/2
початок основного циклу
for i=1 to Dx
plot (x, y)
while (e=>0)
y=y+1
e=e-1
end while
x=x+1
e=e+Dy/Dx
next i
finish
Блок-схема алгоритму на рис. 3.3. Приклад наведений нижче.
Приклад 3.1. Алгоритм Брезенхема.
Розглянемо відрізок, проведений із точки (0,0) у точку (5,5). Розклад відрізка в растр по алгоритму Брезенхема приводить до такого результату:
початкові установки
x=0
y=0
Dx=5
Dy=5
е=1–1/2=1/2
Результати роботи покрокового циклу
| i | Plot | e | x | y |
| 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.4 і збігається з очікуваним. Помітимо, що точка растра з координатами (5,5) не активована. Цю точку можна активувати шляхом зміни циклу for-next на 0 to Dx. Активацію точки (0,0) можна усунути, якщо поставити оператор Plot безпосередньо перед рядком next i.
Результат роботи алгоритму Брезенхема в першому октанті
2. Загальний алгоритм Брезенхема
Щоб реалізація алгоритму Брезенхема була повною необхідно розглянути відрізки у всіх октантах. Модифікацію легко зробити, враховуючи в алгоритмі номер квадранта, в якому лежить відрізок і його кутовий коефіцієнт. Коли абсолютна величина кутового коефіцієнта більше 1, у постійно змінюється на одиницю, а критерій похибки Брезенхема використовується для ухвалення рішення про зміну величини x. Вибір постійно змінюваної координати (на +1 чи -1) залежить від квадранта (рис. 4.1.). Загальний алгоритм може бути оформлений у наступному вигляді:
Узагальнений цілочисельний алгоритм Брезенхема квадрантів передбачається, що кінці відрізка (x1, y1) і (x2, y2) не збігаються усі змінні вважаються цілими Sign – функція, що повертає -1, 0, 1 для від’ємного, нульового і додатнього аргумента відповідно ініціалізація змінних
x=x1
y=y1
Dx=abs (x2-x1)
Dy=abs (y2-y1)
s1=Sign (x2-x1)
s2=Sign (y2-y1)
обмін значень Dx і Dy в залежності від кутового коефіцієнта нахилу відрізка
if Dy<Dx then
Temp=Dx
Dx=Dy
Dy=Temp
Обмін=1
else
Обмін=0
end if
ініціалізація e з виправленням на половину піксела
e=2*Dy-Dx
основний цикл
for i=1 to Dx
Plot (x, y)
while (e=>0)
if Обмін=1 then
x=x+s1
else
y=y+s2
end if
e=e-2*Dx
end while
if Обмін=1 then
y=y+s2
else
x=x+s1
end if
e=e+2*Dy
next i
finish
Розгляд випадків для узагальненого алгоритму Брезенхема
Для ілюстрації розглянемо відрізок із точки (0, 0) у точку (-8, -4).
початкові установки
x=0
y=0
Dx=8
Dy=4
s1=-1
s2=-1
Обмін=0
е=0
Результати роботи покрокового циклу
| i | Plot | е | x | y |
| 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 |
Результат роботи узагальненого алгоритму Брезенхема в третьому квадранті
На рис. 4.2 показаний результат. Порівнюючи з рис. 2.2 бачимо, що результати роботи двох алгоритмів відрізняються.
3. Алгоритм Брезенхема для генерації кола
У растр потрібно розкладати не тільки лінійні, але й інші, більш складні функції. Розкладанню конічних перетинів, тобто кіл, еліпсів, парабол, гіпербол, було присвячено значне число робіт. Найбільша увага, зрозуміло, приділена колу. Один з найбільш ефективних і простих для розуміння алгоритмів генерації кола належить Брезенхему. Для початку відмітимо, що необхідно згенерувати тільки одну восьму частину кола. Інші його частини можуть бути отримані послідовними відображеннями, як це показано на рис. 5.1. Якщо згенерований перший октант (від 0 до 45° проти годинникової стрілки), то другий октант можна отримати дзеркальним відображенням відносно прямої y=х, що дає в сукупності перший квадрант. Перший квадрант відбивається відносно прямої х=0 для отримання відповідної частини кола в другому квадранті. Верхнє півколо відбивається відносно прямої y=0 для завершення побудови. На рис. 5.1 наведені двовимірні матриці відповідних перетворень.
Генерація повного кола з дуги в першому октанті
Для виведення алгоритму розглянемо першу чверть кола з центром у початку координат. Помітимо, що якщо робота алгоритму починається в точці х=0, у=R,
то при генерації кола за годинниковою стрілкою в першому квадранті у
є монотонно спадною функцією аргумента х
(рис. 5.2). Аналогічно, якщо вихідною точкою є у=
0, х
=R,
то при генерації кола проти годинникової стрілки х
буде монотонно спадною функцією аргументу у.
У нашому випадку вибирається генерація за годинниковою стрілкою з початком у точці х
=0, у=R.
Передбачається, що центр кола і початкова точка знаходяться точно в точках растра.
Для будь-якої заданої точки на колі при генерації за годинниковою стрілкою існує тільки три можливості вибрати наступний піксел, що щонайкраще наближає коло: горизонтально вправо, по діагоналі вниз і вправо, вертикально вниз. На рис. 5.3 ці напрямки позначені відповідно mH
, mD
, mV
.
Алгоритм вибирає піксел, для якого мінімальний квадрат відстані між одним з цих положень і колом, тобто мінімум з
mH
=|(xi
+1)2
+(yi
)2
-R2
|
mD
=|(xi
+1)2
+(yi
-1)2
-R2
|
mV
=|(xi
)2
+(yi
-1)2
-R2
|
Різниця між квадратами відстаней від центра кола до діагонального піксела (xi
+1, уi
-
1) і від центра до точки на колі R2
дорівнює
Di
=(xi
+1)2
+(yi
-1)2
-R2
Як і в алгоритмі Брезенхема для відрізка, для вибору відповідного піксела бажано використовувати тільки знак похибки, а не її величину.
При Di
<0 діагональна точка (xi
+1, уi
-
1) знаходиться всередині реального кола, тобто це випадки 1 або 2 на рис. 5.4. Ясно, що в цій ситуації варто вибрати або піксел (xi
+1, у
i
),
тобто mH
, або піксел (xi
+1, у
i
-
1), тобто mD
. Для цього спочатку розглянемо випадок 1 і перевіримо різницю квадратів відстаней від кола до пікселів у горизонтальному і діагональному напрямках:
d=|(xi
+1)2
+(yi
)2
-R2
|-|(xi
+1)2
+(yi
-1)2
-R2
|
При d<0 відстань від кола до діагонального піксела більша, ніж до горизонтального.
Навпаки, якщо d>0, відстань до горизонтального піксела більша. Таким чином,
при d<=0 вибираємо mH
(xi
+1, уi
)
при d>0 вибираємо mD
(xi
+1, уi
-1)
При d=0, коли відстань від кола до обох пікселів однакова, вибираємо горизонтальний крок.
Кількість обчислень, необхідних для оцінки величини d, можна скоротити, якщо помітити, що у випадку 1
(xi
+1)2
+(yi
)2
-R2
>=0
(xi
+1)2
+(yi
-1)2
-R2
<0
тому що діагональний піксел (xi
+1, у
i
-
1) завжди лежить всередині кола, а горизонтальний (xi
+1, у
i
) –поза ним. Таким чином, d можна обчислити за формулою
d=
(xi
+1)2
+(yi
)2
-R2
+(xi
+1)2
+(yi
-1)2
-R2
Доповнення до повного квадрата члена (yi
)2
за допомогою додавання і віднімання – 2yi
+
1 дає
d=2 [(xi
+1)2
+(yi
-1)2
-R2
]+2yi
-
1
У квадратних дужках стоїть по визначенню Di
і його підстановка
d=
2 (Di
+yi
) –
1
значно спрощує вираз.
Розглянемо випадок 2 на рис. 5.4 і помітимо, що тут повинен бути обраним горизонтальний піксел (xi
+1, уi
), тому що у є монотонно спадною функцією. Перевірка компонентів d показує, що
(xi
+1)2
+(yi
)2
-R2
<0
(xi
+1)2
+(yi
-1)2
-R2
<0
оскільки у випадку 2 горизонтальний (xi
+1, уi
) і діагональний (xi
+1, уi
-1) піксели лежать усередині кола. Отже, d<0, і при використанні того ж самого критерію, що й у випадку 1, вибирається піксел (xi
+1, уi
).
Якщо Di
>0, то діагональна точка (xi
+1, уi
-1) знаходиться поза колом, тобто це випадки 3 і 4 на рис. 5.4. У даній ситуації ясно, що потрібно вибрати піксел (xi
+1, уi
-1), або (xi
, уi
-1). Аналогічно розгляду попереднього випадку критерій вибору можна отримати, розглядаючи спочатку випадок 3 і перевіряючи різницю між квадратами відстаней від кола до діагонального mD
і вертикального mV
пікселів, тобто
d'
=|(xi
+1)2
+(yi
-1)2
-R2
|-|(xi
)2
+(yi
-1)2
-R2
|.
При d'
<
0 відстань від кола до вертикального піксела (xi
, уi
-1) більша і варто вибрати діагональний крок до піксела (xi
+1, уi
-1). Навпаки, у випадку d'
>0 відстань від кола до діагонального піксела більша і варто вибрати вертикальний рух до піксела (xi
, уi
-1). Таким чином, при d'
<=
0 вибираємо mD
(xi
+1, уi
-1), при d'>
0 вибираємо mV
(xi
, уi
-1).
Тут для випадку d'
=0, тобто коли відстані рівні, обраний діагональний крок.
Перевірка компонентів d'
показує, що
(xi
)2
+(yi
-1)2
-R2
>=0
(xi
+1)2
+(yi
-1)2
-R2
<0
оскільки для випадку 3 діагональний піксел (xi
+1, уi
-1) знаходиться поза колом, тоді як вертикальний піксел (xi
, уi
-1) лежить всередині кола. Це дозволяє записати d'
у вигляді
d'
=(xi
+1)2
+(yi
-1)2
-R2
+(xi
)2
+(yi
-1)2
-R2
Доповнення до повного квадрата члена (xi
)2
за допомогою додавання і віднімання 2xi
+1 дає
d'
=2 [(xi
+1)2
+(yi
-1)2
-R2
]-2xi
-1
Використання визначення Di
приводить вираз до вигляду
d'
=
2 (Di
-
xi
) –
1
Тепер, розглядаючи випадок 4, знову зауважимо, що варто вибрати вертикальний піксел (xi
, уi
-1), тому що y є монотонно спадною функцією від х.
Перевірка компонентів d'
для випадку 4 показує, що
(xi
+1)2
+(yi
-1)2
-R2
>0
(xi
)2
+(yi
-1)2
-R2
>0
Оскільки обидва піксели знаходяться поза колом. Отже, d'
>0 і при використанні критерію, розробленого для випадку 3, відбувається вірний вибір mV
.
Залишилося перевірити тільки випадок 5 на рис. 5.4, який зустрічається, коли діагональний піксел (xi
+1, уi
-1) лежить на колі, тобто Di
=0. Перевірка компонентів d показує, що
(xi
+1)2
+(yi
)2
-R2
>0
(xi
+1)2
+(yi
-1)2
-R2
=0
Отже, d>0 і вибирається діагональний піксел (xi
+1, уi
-1). Аналогічним чином оцінюємо компоненти d'
:
(xi
+1)2
+(yi
-1)2
-R2
=0
(xi
+1)2
+(yi
-1)2
-R2
<0
і d'
<0, що є умовою вибору правильного діагонального кроку до (xi
+1, уi
-1). Таким чином, випадок Di
=0 підлягає тому ж критерію, що і випадок Di
<0 чи Di
>0. Підіб'ємо підсумок отриманих результатів:
Di
<0
d<=0вибираємо піксел (xi
+1, уi
) – mH
d>
0 вибираємо піксел (xi
+1, уi
-1) –
mD
Di
>0
d'
<=0 вибираємо піксел (xi
+1, уi
-1) – mD
d'>
0 вибираємо піксел (xi
, уi
-1) – mV
Di
=0 вибираємо піксел (xi
+1, уi
-1) – mD
Легко розробити прості рекурентні співвідношення для реалізації покрокового алгоритму. Спочатку розглянемо горизонтальний крок mH
до піксела (xi
+1, уi
).
Позначимо це нове положення піксела як (i+1). Тоді координати нового піксела і значення Di
рівні
xi+1
=xi
+1
yi+1
=yi
Di+1
=(xi+1
+1)2
+(yi+1
-1)2
-R2
=Di
+2xi+1
+1
Аналогічно координати нового піксела і значення Di
для кроку mD
до піксела (xi
+1, уi
-1) такі:
xi+1
=xi
+1
yi+1
=yi
-1
Di+1
=Di
+2xi+1
-2yi+1
+2
Те ж саме для кроку mV
до (xi
, уi
-1)
xi+1
=xi
yi+1
=yi
-1
Di+1
=Di
-2yi+1
+1
Реалізація алгоритму Брезенхема на псевдокоді для кола наводиться нижче.
Покроковий алгоритм Брезенхема для генерації кола в першому квадранті усі змінні – цілі ініціалізація змінних
xi
=0
yi
=R
Di
=2 (1-R)
Межа=0
1 Plot (xi
, yi
)
if
yi
<=Межа then 4
Виділеннявипадку 1 чи 2, 4 чи 5, чи 3
if Di
<0 then 2
if Di
>
0 then 3
if Di
=0 then
20
визначення випадку 1 чи 2
2d=2Di
+2уi
-1
if d<=0 then
10
if d>0 then
20
визначення випадку 4 чи 5
3d=2Di
+2хi
-
1
if
d<=
0 then
20
if
d>
0 then
30
виконання кроків
крок до m
10хi
=хi
+1
Di
=Di
+2хi
+1
gо to 1
крокm
20хi
=хi
+1
yi
=yi
+1
Di
=Di
+2хi
-2уi
+2
gо to 1
4 finish
Змінна межі встановлюється в нуль для закінчення роботи алгоритму на горизонтальній осі, в результаті генерується коло у першому квадранті. Якщо необхідний лише один з октантів, то другий октант можна отримати за допомогою установки Межа=Integer
(R/sqrt(2)), а перший – за допомогою відображення другого октанта відносно прямої у=х (рис. 5.1). Блок-схема алгоритму показана на рис. 5.5.
Блок-схема покрокового алгоритму Брезенхема для генерації кола в першому квадранті
Розглянемо коло радіусом 8 з центром в початку координат. Генерується тільки перший квадрант.
x=0
y=8
=2 (1–8)=-14
Межа=0
Покрокове виконання основного циклу
1 Plot (0,8)
yi>Межа (продовжувати)
Di<0 go to 2
2d=2 (-14)+2 (8) – 1=-13<0 go to 10
10x=0+1=1
Di=-14+2+1=-11
go to 1
1 Plot (1,8)
yi>Межа (продовжувати)
Di<0 go to 2
2d=2 (-11)+2 (8) – 1=-7<0 go to 10
10x=1+1=1
Di=-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 | Di | d | d' | x | y |
| -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) |
Результати показані на рис. 5.6. разом з реальним колом. Алгоритм легко узагальнюється для інших квадрантів чи дуг кіл.
алгоритм генерація коло брезенхем
Результати роботи покрокового алгоритму Брезенхема генерації кола