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

 

Хоча алгоритм Брезенхема був спочатку розроблений для цифрових графопобудовувачів, однак, також підходить і для використання растровими пристроями з ЕПТ. Алгоритм вибирає оптимальні растрові координати для подання відрізка. У процесі роботи одна з координат − або , або  (в залежності від кутового коефіцієнта) − змінюється на одиницю. Зміна іншої координати (або на нуль, або на одиницю) залежить від відстані між координатами сітки. Таку відстань ми назвемо помилкою.

Алгоритм побудований так, що потрібно перевіряти лише знак цієї помилки. На рис. 7.3 це ілюструється для відрізка в першому октанті, тобто, для відрізка з кутовим коефіцієнтом, що лежить в діапазоні від нуля до одиниці. З рисунка зрозуміло, що якщо кутовий коефіцієнт відрізка з точки (0, 0) більший 1/2, то його перетинання з прямою = 0. Отже, точка растру (1, 1) краще апроксимує проходження відрізка, ніж точка (1, 0). Якщо кутовий коефіцієнт менше 1/2, то вірно зворотнє. Для кутового коефіцієнта, рівного 1/2, немає будь-якого бажаного вибору. У даному випадку алгоритм обирає точку (1, 1).

 

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

 

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

,

де  - кутовий коефіцієнт. У нашому випадку при початковому значенні помилки − 1/2

,

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

Оскільки  негативне, то відрізок пройде нижче середини пікселя. Отже, піксель на тому ж самому горизонтальному рівні краще апроксимує положення відрізка, тому  не збільшується. Аналогічно обчислюємо помилку

,

в наступній точці растру (2, 0). Тепер  позитивне, а значить, відрізок пройде вище середньої точки. Растровий елемент (2, 1) з наступною за величиною координатою  краще апроксимує положення відрізка. Отже,  збільшується на одиницю. Перш ніж розглядати наступний піксель, необхідно відкоригувати помилку вирахуванням з неї одиниці. Маємо:

.

Зауважимо, що перетин вертикальної прямої  = 2 із заданим відрізком лежить на 1/4 нижче прямої  = 1. Якщо ж перенести відрізок 1/2 вниз, то ми отримаємо саме величину − 3/4. Продовження обчислень для наступного пікселя дасть

,

Оскільки  негативне, то Y не збільшується. З усього сказаного випливає, що помилка − це інтервал, що відсікається по осі  розглянутим відрізком у кожному растровому елементі (відносно − 1/2).

Наведемо алгоритм Брезенхема для першого октанта, тобто для випадку .

 

Алгоритм Брезенхема розкладання в растр відрізка для першого октанту

передбачається, що кінці відрізка () і () не збігаються.

Integer функція перетворення в ціле

  цілі

  дійсне

ініціалізація змінних

ініціалізація  з поправкою на половину пікселя

початок основного циклу

for i = 1 to

         Plot  (x, y)

While ()

end while

next  i

finish

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

Рис. 7.5. Блок-схема алгоритму Брезенхема

 

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

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

початкові дані

Результати покрокового виконання основного циклу

 

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

4

5

 

 

1/2

5

5

 

Результат наведений на рис. 7.6 збігається з очікуваним. Зауважимо, що точка растру з координатами (5, 5) не активована. Цю точку можна активувати шляхом зміни умови циклу for-next на 0 to . Активацію точки (0, 0) можна усунути, якщо поставити оператор Plot безпосередньо перед рядком next i.

 

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