Розкладання відрізка в растр використовуючи цифровий диференціальний аналізатор

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

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

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

cyfrovyj_dyferencialnyj_analizator36

Розкладання відрізка в растр використовуючи цифровий диференціальний аналізатор

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

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

Якщо ж , то здійснювати збільшення на одинцю необхідно значення координати , а обчислення координати  виконується за наступною формулою:

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

Розкладання відрізка в растр використовуючи цифровий диференціальний аналізатор — приклад:

Розглянемо відрізок із точки в точку та використовуючи алгоритм методу цифрового диференціального аналізатора розкладемо його в растр.

cyfrovyj_dyferencialnyj_analizator34

Результат роботи цифрового диференціального аналізатора

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

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

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

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

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

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

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

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