РОЗДІЛ 2
ТЕОРЕТИЧНІ ЗАСАДИ ЩОДО ВИЗНАЧЕННЯ ПАРАМЕТРІВ ДЛЯ АНТИАЛІАЙЗИНГУ КОНТУРІВ
ГРАФІЧНИХ ОБ’ЄКТІВ
Згідно з методами крайового антиаліайзингу для згладжування контурів графічних
примітивів інтенсивність кольору піксела встановлюють пропорційно до площі
покриття піксела об’єктом [41, 46, 55]. Обчислювальна складність процедури
визначення площі покриття суттєво впливає на швидкодію формування зображення,
що обумовлює актуальність розробки підходів до її зменшення.
Серед методів формування відрізків прямих та кривих другого порядку найбільшого
поширення отримали методи, які основані на обчисленні оцінювальної функції [21,
22, 41], знак якої використовується для визначення координат точок траєкторії.
Оцінювальна функція розраховується на кожному кроці інтерполяції, тому
знаходження залежності між значенням оцінювальної функції та площею покриття
піксела графічним примітивом дозволить скоротити обчислювальні витрати методів
крайового антиаліайзингу.
До найбільш поширених примітивів комп’ютерної графіки відносять полігони,
відрізки прямих, дуги кіл та еліпсів [1, 24, 41].
У даному розділі дисертаційної роботи проведені дослідження з метою отримання
більш простих аналітичних залежностей для реалізації крайового антиаліайзингу.
2.1. Взаємозв’язок оцінювальної функції з площею покриття
піксела ребром полігона
Проаналізуємо аналітичні вирази, що пов’язують площу покриття піксела та
параметри ребра полігона. В подальшому будемо розглядати формування ребер
полігонів, які належать першому октанту, оскільки вирази для інших октантів
отримують аналогічно з врахування симетрії та правила
подвійності [26]. При перетині піксела та відрізка з тангенсом кута нахилу може
бути задіяний один або два піксела [41, 97]. Розглянемо різні випадки перетину
піксела відрізком прямої. В подальшому площа покриття – це площа, частини
піксела, яка відтинається траєкторією примітива і належить графічному об’єкту.
Коли ребро багатокутника перетинає лише один піксел (рис. 2.1), то площа
покриття піксела багатокутником визначається за формулою:
. (2.1)
Рис. 2.1. Визначення площі покриття для випадку, коли пряма
перетинає один піксел
Якщо ребро багатокутника перетинає в ортогональному напрямку два піксела, то
можливо два різних випадки покриття. У першому випадку верхній піксел
розташовано ближче до ідеальної прямої (рис. 2.2). При цьому площа покриття
піксела багатокутником для верхнього піксела визначається згідно з виразом:
(2.2)
Площа покриття для нижнього піксела визначається за формулою:
. (2.3)
Для спрощення обчислення площі покриття піксела можна використати підхід
запропонований М. Піттуеєм та Д. Уоткінсоном [104], який полягає у тому, що
площа покриття нижнього піксела приймається рівною одиниці. Сумарна площа двох
пікселів залишається незмінною. При цьому площа покриття верхнього піксела
наближено обчислюється за формулою:
Коли нижній піксел розташовано ближче до ідеальної
прямої (рис. 2.3), то площа покриття для верхнього піксела знаходиться за
формулою:
(2.4)
Площа покриття нижнього піксела в даному випадку розраховується згідно з
виразом:
. (2.5)
Для спрощення розрахунку площі покриття в даному випадку також можна
застосувати підхід, який використано раніше. При цьому площа покриття верхнього
піксела приймається рівною нулю, а площа покриття нижнього піксела обчислюється
за формулою:
Слід зазначити, що коли до швидкодії формування зображення висуваються жорстокі
вимоги, то доцільно використати наближені формули для обчислення площі
покриття. При цьому вирази для всіх трьох випадків перетину піксела ребром
багатокутника збігаються:
. (2.6)
Рис. 2.2. Визначення площі покриття для випадку, коли верхній піксел
розташовано ближче до відрізка прямої
Рис. 2.3. Визначення площі покриття для випадку, коли нижній піксел розташовано
ближче до відрізка прямої
Дослідимо максимальне значення абсолютної похибки обчислення площі покриття
піксела за виразом (2.6).
Для оцінювання похибки апроксимації було розроблено програму, згідно з якою
формувалися усі можливі відрізки прямих в дискретному координатному просторі з
розмірами 1024х1024. У циклі інтерполювання розраховувалась площа покриття
пікселів згідно з виразом (2.6) та порівнювалась із точним значенням. В додатку
А на рис. А.1 зображено залежність максимальної абсолютної похибки обчислення
площі покриття від коефіцієнта нахилу прямої. Як видно з рис. А.1, абсолютна
похибка обчислення площі покриття прямо пропорційна коефіцієнту нахилу прямої.
Максимальне значення похибки менше за . Таким чином, розрахунок площі покриття
піксела за виразом (2.6) доцільно проводити у випадку використання чотирьох
рівнів інтенсивності кольору для згладжування контурів. При використанні
більшої кількості рівнів інтенсивності кольору необхідно більш точно
розраховувати площу покриття.
Пропонується новий метод обчислення площі покриття піксела ребром
багатокутника, який забезпечує меншу абсолютну похибку і порівняно з виразами
(2.2) та (2.4) має меншу обчислювальну складність.
Коли нижній піксел розташовано ближче до прямої (рис. 2.4), площа покриття
верхнього піксела може бути визначена як різниця між площею трикутника та
площею трапеції :
. (2.7)
Площа трикутника дорівнює: . Площа
трапеції може бути знайдена за формулою:
Підставивши останні вирази в формулу (2.7), отримуємо:
, (2.8)
де , .
Розглянемо апроксимацію функції більш простим виразом, який потребує меншого
обсягу обчислень. Знайдемо мінімальне значення, яке може приймати функція .
Похідна даної функції дорівнює: . Прирівнявши похідну до нуля та розв’язавши
отримане рівняння, знаходим
- Київ+380960830922