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

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

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

Для пояснення алгоритму розглянемо першу чверть кола з центром у початку координат. Зауважимо, що якщо робота алгоритму починається в точці , то при генерації кола за годинниковою стрілкою в першому квадранті є монотонно спадною функцією аргумента . Аналогічно, якщо вихідною точкою є , то при генерації кола проти годинникової стрілки буде монотонно спадною функцією аргументу . У нашому випадку вибирається генерація за годинниковою стрілкою з початком у точці . Передбачається, що центр кола і початкова точка знаходяться точно в точках растра.

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

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

Отже, нехай різниця між квадратами відстаней від центра кола до діагонального піксела і від центра до точки на колі дорівнює:

Як і у випадку з відрізком, для вибору відповідного пікселя будемо використовувати тільки знак цієї різниці, а не її величину. Якщо , то діагональна точка  знаходиться всередині реального кола. На рисунку, що міститься вище, це випадки 1 або 2. Ясно, що в цій ситуації варто вибрати або піксель  з координатами , або піксель  з координатами . Для цього спочатку розглянемо випадок 1 і перевіримо різницю квадратів відстаней від кола до пікселів у горизонтальному та діагональному напрямках:

При  — відстань від кола до діагонального пікселя більша, ніж до горизонтального. І навпаки, якщо -відстань до горизонтального піксела більша. Таким чином, при  вибираємо , а при  - . У випадку, коли , тобто коли відстань від кола до обох пікселів однакова, вибираємо горизонтальний крок. Кількість обчислень, необхідних для оцінки величини , можна скоротити, якщо зауважити, що у випадку 1 а . Це зумовлено тим, що діагональний піксел  завжди лежить всередині кола, а горизонтальний  — поза ним. Таким чином,  можна обчислити наступним чином:

Доповнення до повного квадрату члена та за допомогою додавання і віднімання дає . У дужках стоїть, за визначенням,  і його підстановка значно спрощує вираз:

Розглянемо випадок 2 на тому ж таки рисунку і зауважимо, що тут повинен бути обраним горизонтальний піксель , тому що  є монотонно спадною функцією. Перевірка компонентів  показує, що і , оскільки у випадку 2 горизонтальний та діагональний пікселі лежать всередині кола. Отже, , і при використанні того ж самого критерію, що і у випадку 1, вибирається піксель .

Якщо , то діагональна точка  знаходиться поза колом, тобто це випадки 3 та 4. У даній ситуації зрозуміло, що потрібно вибрати піксель , або . Аналогічно до попереднього випадку, критерій вибору можна отримати, розглядаючи спочатку випадок 3 і перевіряючи різницю між квадратами відстаней від кола до діагонального та вертикального пікселів:

При відстань від кола до вертикального пікселя  більша і варто вибрати діагональний крок до пікселя . І навпаки, у випадку коли відстань від кола до діагонального пікселя більша і варто вибрати вертикальний рух до пікселя . Таким чином, при  вибираємо піксель  з координатами , а при  -  з координатами .

Тут для випадку , тобто коли відстані рівні, обраємо діагональний крок. Перевірка компонентів показує, що і . А оскільки для випадку 3 діагональний піксель  знаходиться поза колом, в той час як вертикальний  лежить всередині кола, то це дозволяє записати  у наступному вигляді:

Доповнення до повного квадрата члена та за допомогою додавання і віднімання дає . Використання визначення  приводить останній вираз до наступного вигляду:

Тепер, розглядаючи випадок 4, знову-таки зауважимо, що варто вибрати вертикальний піксель , тому що  є монотонно спадною функцією від . Перевірка компонентів  для випадку 4 показує, що і . Тобто обидва пікселя знаходяться поза колом. Отже,  і при використанні критерію, розробленого для випадку 3, приходимо до висновку, що необхідно вибрати піксель  з координатами .

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

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

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

Використовуючи алгоритм Брезенхема растеризувати коло радіусом 4 в першому квадранті за годинниковою стрілкою з центром в початку координат. В якості початкової вибирається точка .

Отже, як було сказано вище, для будь-якої заданої точки на колі, при генерації за годинниковою стрілкою, існують тільки три можливих напрямки для вибору наступного пікселя: горизонтально вправо, по діагоналі і вертикально вниз. В нашому випадку це пікселі , та відповідно.

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

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

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

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

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

Продовжуючи ітераційни процес алгоритму Брезенхема далі, отримаємо координати пікселів для растеризації кола в першому квадранті.

Результати, разом з реальним колом, показано на наступному малюнку.

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