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

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

algorytm_brezenhema_dlja_kola85

Генерація повного кола з дуги в першому октанті

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

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

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

Вибір пікселів для растеризації кола у першому квадранті

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

Варіанти перетину кола і сітки растра

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Вибір координатів пікселя P2

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

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

algorytm_brezenhema_dlja_kola71

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

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

Вибір координатів пікселя P3

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

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

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

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

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

Матеріал був корисним, поділись в соціальних мережах:

Якщо тобі сподобалась дана тема, залиш свій коментар