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

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

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

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

Графічне представлення роботи алгоритму Брезенхема при растеризації відрізка прямої

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

Звідси, відстань від прямої до вузла  і відстань від прямої до вузла  визначаються по формулах:

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

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

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

Якщо ж , то в якості наступного слід вибирати вузол , і тоді:

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

algorytm_brezenhema_dlja_vidrizka_prjamoi582

Випадки для узагальненого алгоритму Брезенхема

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

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

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

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

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

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

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

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

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