Растеризація кола використовуючи алгоритм Брезенхема
У параграфі растеризація відрізка за алгоритмом Брезенхема було розглянуто один з найвідоміших і найбільш викокористовуваних алгоритмів комп'ютерної графіки, призначених для розкладання відрізка в растр. Сьогодні розглянемо найбільш ефективний і простий для розуміння алгоритм генерації більш складної геометричної фігури, а саме кола, який також належить Брезенхему. Для початку зауважимо, що згідно з цим алгоритмом, достатньо згенерувати тільки одну четверту чи навіть одну восьму частину кола. Інші його частини можуть бути отримані послідовними відображеннями, як це показано на насутпному малюнку.

Генерація повного кола з дуги в першому октанті
Тобто, якщо згенерований перший октант (від до
проти годинникової стрілки), то другий октант можна отримати дзеркальним відображенням відносно прямої
, що дає в сукупності перший квадрант. Перший квадрант відбивається відносно прямої
для отримання відповідної частини кола в другому квадранті. Верхнє півколо відбивається відносно прямої
для завершення побудови. Відмітимо, що на рисунку наведені двовимірні матриці відповідних перетворень.
Для пояснення алгоритму розглянемо першу чверть кола з центром у початку координат. Зауважимо, що якщо робота алгоритму починається в точці , то при генерації кола за годинниковою стрілкою в першому квадранті
є монотонно спадною функцією аргумента
. Аналогічно, якщо вихідною точкою є
, то при генерації кола проти годинникової стрілки
буде монотонно спадною функцією аргументу
. У нашому випадку вибирається генерація за годинниковою стрілкою з початком у точці
. Передбачається, що центр кола і початкова точка знаходяться точно в точках растра.
Отже, для будь-якої заданої точки на колі, при генерації за годинниковою стрілкою, існує тільки три варіанти вибрати наступний піксель, що найкращим чином наближає коло. Це здійснити елементариний крок в одному з наступних напрямків по відношенню до біжучого пікселя : горизонтально вправо, по діагоналі (вниз і вправо) та вертикально вниз. На рисунку, що міститься нижче, ці напрямки позначені точками
,
та
відповідно.

Вибір пікселів для растеризації кола у першому квадранті
Згідно з алгоритмом Брезенхема для кола, вибирається піксель, для якого квадрат відстані між одним з цих положень і колом являється мінімальним, тобто , де
,
і
. Відмітимо, що обчислення можна спростити, якщо зауважити, що в околі точки
можливі тільки п'ять типів перетинів кола і сітки растра. Розглянемо їх більш детально.

Варіанти перетину кола і сітки растра
Отже, нехай різниця між квадратами відстаней від центра кола до діагонального піксела і від центра до точки на колі
дорівнює:
Як і у випадку з відрізком, для вибору відповідного пікселя будемо використовувати тільки знак цієї різниці, а не її величину. Якщо , то діагональна точка
знаходиться всередині реального кола. На рисунку, що міститься вище, це випадки 1 або 2. Ясно, що в цій ситуації варто вибрати або піксель
з координатами
, або піксель
з координатами
. Для цього спочатку розглянемо випадок 1 і перевіримо різницю квадратів відстаней від кола до пікселів у горизонтальному та діагональному напрямках:
При — відстань від кола до діагонального пікселя більша, ніж до горизонтального. І навпаки, якщо
-відстань до горизонтального піксела більша. Таким чином, при
вибираємо
, а при
-
. У випадку, коли
, тобто коли відстань від кола до обох пікселів однакова, вибираємо горизонтальний крок. Кількість обчислень, необхідних для оцінки величини
, можна скоротити, якщо зауважити, що у випадку 1
а
. Це зумовлено тим, що діагональний піксел
завжди лежить всередині кола, а горизонтальний
— поза ним. Таким чином,
можна обчислити наступним чином:
Доповнення до повного квадрату члена та за допомогою додавання і віднімання
дає
. У дужках стоїть, за визначенням,
і його підстановка значно спрощує вираз:
Розглянемо випадок 2 на тому ж таки рисунку і зауважимо, що тут повинен бути обраним горизонтальний піксель , тому що
є монотонно спадною функцією. Перевірка компонентів
показує, що
і
, оскільки у випадку 2 горизонтальний та діагональний пікселі лежать всередині кола. Отже,
, і при використанні того ж самого критерію, що і у випадку 1, вибирається піксель
.
Якщо , то діагональна точка
знаходиться поза колом, тобто це випадки 3 та 4. У даній ситуації зрозуміло, що потрібно вибрати піксель
, або
. Аналогічно до попереднього випадку, критерій вибору можна отримати, розглядаючи спочатку випадок 3 і перевіряючи різницю між квадратами відстаней від кола до діагонального та вертикального пікселів:
При відстань від кола до вертикального пікселя
більша і варто вибрати діагональний крок до пікселя
. І навпаки, у випадку коли
відстань від кола до діагонального пікселя більша і варто вибрати вертикальний рух до пікселя
. Таким чином, при
вибираємо піксель
з координатами
, а при
-
з координатами
.
Тут для випадку , тобто коли відстані рівні, обраємо діагональний крок. Перевірка компонентів
показує, що
і
. А оскільки для випадку 3 діагональний піксель
знаходиться поза колом, в той час як вертикальний
лежить всередині кола, то це дозволяє записати
у наступному вигляді:
Доповнення до повного квадрата члена та за допомогою додавання і віднімання
дає
. Використання визначення
приводить останній вираз до наступного вигляду:
Тепер, розглядаючи випадок 4, знову-таки зауважимо, що варто вибрати вертикальний піксель , тому що
є монотонно спадною функцією від
. Перевірка компонентів
для випадку 4 показує, що
і
. Тобто обидва пікселя знаходяться поза колом. Отже,
і при використанні критерію, розробленого для випадку 3, приходимо до висновку, що необхідно вибрати піксель
з координатами
.
Залишилося перевірити тільки випадок 5, який зустрічається, коли діагональний піксел лежить на колі, тобто
. Перевірка компонентів
показує, що
і
. Тобто,
і вибирається діагональний піксель
з координатами
.
Аналогічним чином оцінюємо компоненти :
і
. Якщо
, що є умовою вибору правильного діагонального кроку до пікселя
з координатами
. Таким чином, випадок
підлягає тому ж критерію, що і випадок
чи
.
Растеризація кола використовуючи алгоритм Брезенхема — приклад:
Використовуючи алгоритм Брезенхема растеризувати коло радіусом 4 в першому квадранті за годинниковою стрілкою з центром в початку координат. В якості початкової вибирається точка .
Отже, як було сказано вище, для будь-якої заданої точки на колі, при генерації за годинниковою стрілкою, існують тільки три можливих напрямки для вибору наступного пікселя: горизонтально вправо, по діагоналі і вертикально вниз. В нашому випадку це пікселі ,
та
відповідно.

Вибір координатів пікселя P2
Для того, щоб з'ясувати, який з цих пікселів вибрати, на першому кроці, скористаємось формулою (1), і, таким чином, обчислимо різницю між квадратами відстаней від центра кола до діагонального піксела і від центра до точки на колі
. В результаті отримаємо:
Виходячи з того, що (діагональний піксель знаходиться всередині кола), то в якості наступного слід вибирита або піксель
або піксель
. Для того, щоб визначити, який з цих пікселів найкращим чином наближає коло переходимо до кроку номер два, згідно з яким, за формулою (4), обчислюємо різницю квадратів відстаней від кола до пікселів у горизонтальному та діагональному напрямках:
Отримана різниця являється меншою від нуля. Таким чином, в якості наступного,вибираємо діагональний піксель, тобто, .
На наступній ітерації, для визначення координатів точки , аналогічним чином, в якості кандидатів розглядаємо пікселі, що розташовані горизонтально вправо, по діагоналі та вертикально вниз по відношенню до
.

Вибір координатів пікселя P3
Після цього, знову-таки, за формулою (1) обчислюємо різницю між квадратами відстаней від центра кола до діагонального пікселя та від центра до точки на колі і в залежностів від того, яке значення вона приймає, перевіряємо відповідну різницю квадратів
або
(формула (4) та (7)).
Продовжуючи ітераційни процес алгоритму Брезенхема далі, отримаємо координати пікселів для растеризації кола в першому квадранті.
Результати, разом з реальним колом, показано на наступному малюнку.

Растеризація кола використовуючи алгоритм Брезенхема
Блок-схема алгоритму Брезенхема для растеризації кола