Простий метод усунення східчастого ефекту

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

Рис. 4.7. Усунення східчастості ребра багатокутника: (а) без усунення східчастості, (б) інтенсивність пропорційна площі частини пікселя, яка знаходиться всередині багатокутника, (в) ребро, отримане за допомогою модифікованого алгоритму Брезенхема.

При наявності декількох інтенсивностей, тобто півтонів сірого або відтінків кольору, зовнішній вигляд ребра або відрізка може бути поліпшений розмиванням країв. Простий евристичний метод полягає в тому, щоб встановлювати інтенсивність пікселя на ребрі пропорційною площі частини пікселя, яка знаходиться всередині багатокутника. Ця проста форма усунення східчастості ілюструється рис. 4.7, на якому зображене одне ребро багатокутника з тангенсом кута нахилу ­ . Внутрішня частина багатокутника розташована праворуч. На рис. 4.7, а представлене ребро, розкладене в растр за допомогою стандартного алгоритму Брезенхема з використанням тільки двох рівнів інтенсивності. Зображення має характерний зазубрений або східчастий вигляд. На рис. 4.7, б для вибору одного з восьми (від 0 до 7) рівнів інтенсивності використовується площа частини пікселя, яка знаходиться всередині багатокутника. Зазначимо, що тому що ця площа для деяких пікселів є меншою однієї восьмої, то деякі пікселі, повністю чорні на рис. 4.7, а, зафарбовані в білий колір на рис. 4.7, б. В результаті простої модифікації алгоритму Брезенхема можна одержати апроксимацію площі частини пікселя, яка знаходиться всередині багатокутника. Цю апроксимацію можна використовувати для модуляції інтенсивності. Як показано на рис. 4.8, при перетинанні пікселя і відрізка з тангенсом кута нахилу m може бути задіяний або один, або два пікселі. Якщо перетинається тільки один піксель (рис. 4.8, а), то площа^[2] правіше і нижче відрізка дорівнює . Якщо ж треба розглянути два пікселі (рис. 4.8, б), то площа нижнього пікселя складає , а верхнього — ­. Для відрізка в першому октанті з тангенсом кута нахилу , площа верхнього пікселя може бути досить малою для того, щоб її можна було проігнорувати у вищеописаному евристичному методі, наприклад, для пікселя (1, 1) на рис. 4.7, б. Однак об’єднання цієї площі з площею нижнього пікселя дозволить більш реалістично представити ребро багатокутника. Сумарна площа для двох пікселів дорівнює .

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

Якщо до похибки у початковому алгоритмі Брезенхема додати величину , тобто ввести перетворення ­ , то . Тепер похибка ­ ­ — це міра площі тієї частини пікселя, яка знаходиться всередині багатокутника, тобто . У зв’язку з цими модифікаціями початкове значення похибки дорівнює 1/2, тому для першого пікселя алгоритм, який наводився на рис. 1.6, завжди буде видавати значення інтенсивності, яке буде дорівнювати половині максимальної. Більш реалістичне значення для першого пікселя дає переміщення оператора активування пікселя на інше місце. Більш того, можна одержати безпосереднє значення інтенсивності, а не десятковий дріб від її максимуму за допомогою множення на максимальне число доступних рівнів інтенсивності I наступних величин: тангенса кута нахилу (m), вагового коефіцієнта (w) і похибки . Модифікований алгоритм виглядає наступним чином:

Модифікований алгоритм Брезенхема з усуненням східчастості для першого квадр а нту

Рис. 4.9. Алгоритм Брезенхема з усуненням східчастості

Інтенсивність для першого пікселя передбачає, що відрізок починається з адреси пікселя. На рис. 4.9 наводиться блок-схема алгоритму. Результати для відрізка з тангенсом кута нахилу ­і вісьмома рівнями інтенсивності представлені на рис. 4.7, в. Поширити роботу алгоритму на інші октанти можна тим же способом, що і для основного алгоритму Брезенхема (див. лаб. роб. 3).

[1] Тут мінімізується не квадрат відстані, а абсолютне значення різниці квадратів відстаней від центру кола до піксела і до кола

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