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

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)

--> ЧИТАТЬ ПОЛНОСТЬЮ <--