ВІННИЦЬКИЙ НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ

КУРІННИЙ МИХАЙЛО СЕРГІЙОВИЧ

УДК 681.3.06

МЕТОДИ ТА ЗАСОБИ АНТИАЛІАЙЗИНГУ

КОНТУРІВ ОБ’ЄКТІВ У СИСТЕМАХ КОМП’ЮТЕРНОЇ ГРАФІКИ

Спеціальність 05.13.13 – Обчислювальні машини, системи та мережі

Автореферат

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

Вінниця – 2006

Дисертацією є рукопис.

Роботу виконано у Вінницькому національному технічному університеті Міністерства освіти і науки України.

Науковий керівник: кандидат технічних наук, доцент

Романюк Олександр Никифорович,

Вінницький національний технічний університет,

доцент кафедри програмного забезпечення

Офіційні опоненти: доктор технічних наук, професор

Квєтний Роман Наумович,

Вінницький національний технічний університет,

завідувач кафедри автоматики та інформаційно-

вимірювальної техніки

кандидат технічних наук, доцент

Гусятін Володимир Михайлович,

Харківський національний університет радіоелектроніки,

професор кафедри електронних обчислювальних машин

Провідна установа: Національний технічний університет України ”Київський

політехнічний інститут”, кафедра обчислювальної техніки, Міністерство освіти і науки України, м. Київ.

Захист відбудеться ”18 березня 2006 р. о 9 30 год. на засіданні спеціалізованої вченої ради Д 05.052.01 у Вінницькому національному технічному університеті за адресою: 21021, м. Вінниця, Хмельницьке шосе, 95, ГУК.

З дисертацією можна ознайомитись у бібліотеці Вінницького національного технічного університету за адресою: 21021, м. Вінниця, Хмельницьке шосе, 95, ГУК.

Автореферат розіслано 13 лютого 2006 р.

Вчений секретар

спеціалізованої вченої ради Захарченко С.М.

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

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

У більшості сучасних систем комп’ютерної графіки використовується растровий принцип формування зображення. При формуванні растрових зображень виникають спотворення, які обумовлені недостатньою роздільною здатністю растра. На зображеннях з’являються артефакти, одним із проявів яких є яскраво виражені сходинки або зубці на краях об’єктів. Даний ефект отримав назву ступінчастого ефекту чи ефекту аліайзингу. Проведені дослідження показали, що при використанні 17” монітора і розміщенні спостерігача на відстані 65 см від екрана для повного усунення ефекту аліайзингу потрібен монітор із роздільною здатністю як мінімум 4000х4000 пікселів, а для людей із рівнем зору вище середнього - взагалі 8000х8000 пікселів. Сучасний рівень технологій поки що не в змозі забезпечити таку роздільну здатність, тому для забезпечення реалістичності синтезованих зображень у системах комп’ютерної графіки використовують спеціальні методи та засоби усунення ступінчастого ефекту.

На відміну від звичайних методів растеризації, у яких інтенсивність кольору розраховується тільки в центрі піксела, у методах антиаліайзингу колір обчислюється з урахуванням зони, яка оточує піксел. При цьому необхідно враховувати характер траєкторії контуру об’єкта, визначати координати точок крокової траєкторії і розраховувати інтенсивності кольору згідно обраної моделі піксела, а для випадку формування тривимірних зображень - вилучати невидимі поверхні на рівні піксела. У зв’язку із цим процедура антиаліайзингу є достатньо трудомісткою.

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

Зв’язок роботи з науковими програмами, планами, темами. Робота виконувалася відповідно до координаційного плану науково-дослідних робіт Міністерства освіти і науки України (наказ №37 від 13.02.1997 р.) за напрямком – “Перспективні інформаційні технології, прилади комплексної автоматизації, системи зв’язку”. Результати дисертації використано в процесі виконання науково – дослідної роботи № 55-Д-177, “Розробка високоефективних методів формування та перетворення зображень”, номер державної реєстрації 0197U013140.

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

Основними задачами дослідження є:

- аналіз існуючих методів і засобів антиаліайзингу контурів об’єктів із метою визначення основних підходів щодо підвищення їх продуктивності та спрощення програмно-апаратної реалізації;

- отримання більш простих аналітичних залежностей щодо визначення вихідних параметрів для процедур антиаліайзингу векторів та кривих другого порядку з метою спрощення обчислювального процесу;

- розробка методів підвищення продуктивності згладжування контурів тривимірних об’єктів;

- розробка та дослідження нових моделей пікселів, які порівняно з відомими забезпечували б меншу обчислювальну складність процедури антиаліайзингу;

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

- модифікація методу А-буфера з метою зменшення обсягів пам’яті для зберігання фрагментів полігонів;

- розробка алгоритмів та структурних схем пристроїв усунення аліайзингу контурів графічних об’єктів для програмно-апаратної реалізації їх у підсистемах растеризації високопродуктивних графічних систем.

Об’єкт дослідження – процес антиаліайзингу контурів графічних об’єктів у системах комп’ютерної графіки.

Предмет дослідження – методи і засоби антиаліайзингу контурів графічних об’єктів.

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

Наукова новизна одержаних результатів:

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

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

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

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

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

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

- розроблено алгоритми та структурні схеми пристроїв антиаліайзингу векторів, векторних меж багатокутників, кіл та еліпсів з метою їх реалізації у графічних акселераторах;

- створено діючі програмні засоби для згладжування контурів графічних об’єктів у системах комп’ютерної графіки;

- запропоновано табличну реалізацію процедури розрахунку площі покриття піксела траєкторією відрізка прямої та кола, яка дозволила зменшити необхідні обсяги постійної пам’яті;

- розроблено спеціалізовані програмні засоби для тестування методів згладжування контурів графічних об’єктів, які дозволяють отримати порівняльні оцінки за точністю і продуктивністю.

Особистий внесок здобувача в роботах, виконаних у співавторстві: [1] – запропоновано метод антиаліайзингу меж кіл з використанням додаткових оцінювальних функцій; [2] – досліджено похибки, які мають місце при розрахунку площі покриття піксела траєкторією; запропоновано використання принципу дихотомії для розрахунку інтенсивності кольору; [3] – розроблено алгоритм антиаліайзингу відрізка прямої, запропоновано формулу для розрахунку інтенсивності кольору; [4] – запропоновано алгоритм антиаліайзингу меж кіл; [5] – розроблено алгоритм антиаліайзингу меж кіл; [6] – досліджено похибку розрахунку площі покриття піксела траєкторією; [7] – запропоновано використати статично-динамічний принцип розподілу пам’яті для методу А-буфера; [8] – запропоновано формули для визначення площі покриття піксела ребром багатокутника; [11] – отримано співвідношення взаємозв’язку оцінювальної функції та інтенсивності кольору піксела; [12] – розроблено блок керування лінійного інтерполятора з реалізацією антиаліайзингу за методом модифікованої оцінювальної функції; [13] – розроблено блок порівняння оцінювальних функцій; [14] – розроблено алгоритм антиаліайзингу для методу оцінювальної функції з подвійними кроковими приростами; [15] – запропоновано формулу для визначення інтенсивності кольору піксела; [16] – розроблено підпрограму визначення інтенсивності кольору точок; [17] – запропоновано формулу для визначення інтенсивності кольору піксела.

Апробація результатів дисертації. Основні положення дисертаційної роботи доповідалися та обговорювалися на: VIII науково-технічній конференції “Вимірювальна та обчислювальна техніка в технологічних процесах”, Хмельницький, 2001 р.; III міжнародній конференції “ІНТЕРНЕТ – ОСВІТА – НАУКА - 2002” (ІОН - 2002), Вінниця, 2002 р.; VI міжнародній конференції з математичного моделювання “МКММ’2003”, Херсон, 2003 р.; II міжнародній науково-практичній конференції “Динаміка наукових досліджень 2003”, Дніпропетровськ, 2003.; міжнародній науково-технічній конференції “Приборостроение -2003”, Вінниця, 2003 р.; ІІІ міжнародній науково-технічній конференції “Комп’ютерні технології в науці, освіті та промисловості”, Дніпропетровськ, 2004 р.; міжнародному симпозіумі “Наука і підприємництво”, 2000, 2005 р.; ІІ і VI міжнародних науково-технічних конференціях молодих вчених, аспірантів та студентів “Оптоелектронні інформаційно-енергетичні технології”, Вінниця, 2001, 2005 р.; щорічних науково-технічних конференціях професорсько-викладацького складу ВНТУ, Вінниця, 2000-2005 р.

Публікації. За результатами виконаних досліджень опубліковано 17 наукових праць: 7 статей у виданнях, що входять до переліку фахових видань, затверджених ВАК України; 3 статті у збірниках матеріалів міжнародних конференцій; 3 публікації у вигляді тез доповідей; 2 патенти на винахід; 1 свідоцтво на реєстрацію авторського права на комп’ютерну програму.

Структура та обсяг роботи. Дисертація складається зі вступу, п’яти розділів, висновків, списку літератури, що містить 120 найменувань, 13 додатків. Робота містить 85 ілюстрацій, 16 таблиць. Загальний обсяг роботи складає 231 сторінку, основний зміст викладено на 144 сторінках друкованого тексту.

ОСНОВНИЙ ЗМІСТ РОБОТИ

У вступі обґрунтовано актуальність теми досліджень, сформульовано мету та задачі дисертаційної роботи, охарактеризовано наукову новизну та практичну цінність отриманих результатів.

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

Другий розділ дисертаційної роботи присвячено розробці теоретичних засад щодо визначення параметрів для антиаліайзингу контурів графічних об’єктів.

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

Для обчислення площі покриття піксела ребром багатокутника найбільшого поширення отримали підходи А.Руа та Піттуея-Уоткінсона. Для випадку, коли ребро перетинає два піксела в ортогональному напрямку (рис. 1), згідно з підходом А.Руа площі покриття та обох пікселів розраховуються з виконанням двох операцій множення. Підхід Піттуея-Уоткінсона полягає у розрахунку площі , яка в подальшому переноситься на нижній піксел. Він не потребує виконання „довгих” операцій в циклі інтерполювання, однак прийнятний тільки для випадку використання 8 рівнів інтенсивності кольору. Було запропоновано нову формулу для розрахунку площі покриття піксела ребром багатокутника:

. (1)

Доведено, що формула (1) прийнятна для випадку використання 64 рівнів інтенсивності кольору.

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

Уперше отримано аналітичні вирази для взаємозв’язку ОФ з площею покриття піксела ребром багатокутника для найбільш поширених алгоритмів оцінювальної функції. ОФ для алгоритму Брезенхема розраховується за формулою:     OFБрез. = 2 хi МП – 2 yi БП – БП.   Доведено,      що ,. При використанні формули (1) для розрахунку площі покриття: .

Згідно з алгоритмом Пєтуха-Обідника ОФ розраховується за формулою:  OF = БП yi – МП хi + БП/2. Доведено, що , . Із використанням формули (1): .

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

Було доведено, що відстань від центра піксела до прямої дорівнює:
d = (БП/2 – OF)/ . Встановлений взаємозв’язок використано для розробки алгоритму антиаліайзингу векторів з використанням конусної моделі піксела.

Встановлено взаємозв’язок між оцінювальною функцією та відстанню від центра піксела до траєкторії кола з радіусом R: di = – OFi /(2R). Показано, що абсолютна похибка обчислення відстані di не перевищує 1/(8R).

Найбільш часто для обчислення площі покриття піксела еліпсом (рис. 2) використовують формулу Філда: Sверх = Ha / 2; Sниз = 1 + Hb / 2, яка забезпечує точність достатню для випадку використання 8 рівнів інтенсивності кольору. Запропоновано нову апроксимаційну формулу для обчислення площі покриття піксела еліпсом (колом), яка характеризується меншою похибкою:

Sверх = Ha 2 / (2 Ha + 2| Hb |); Sниз = 1 + (Ha – Hb )/2 – Sверх .

У таблиці 1 наведено інформацію про необхідні обсяги пам’яті для табличної реалізації запропонованої формули, а також відповідне значення абсолютної похибки обчислення площ покриття Sверх та Sниз.

Таблиця 1

Обсяги пам’яті, необхідної для розрахунку Sверх та Sниз.

Розрядність завдання

Ha , Hb | Кількість
табличних

значень | Об’єм пам’яті, байт | Максимальна
абсолютна
похибка, | Максимальна кількість рівнів інтенсивності кольору для згладжування | 4 | 256 | 160 | 0,0305 | 32 | 5 | 1024 | 768 | 0,0151 | 64 | 6 | 4096 | 3584 | 0,00759 | 128 | Отримані вирази було використано для розробки методів антиаліайзингу кривих другого порядку

У третьому розділі дисертаційної роботи розроблено високопродуктивні методи антиаліайзингу векторів та векторних меж багатокутників.

Запропоновано метод антиаліайзингу меж графічних примітивів із використанням модифікованої оцінювальної функції, суть якого полягає у розрахунку спеціальної ОФ, знак якої визначає координати точок траєкторії, а значення – інтенсивність кольору точок. Запропоновано нову ОФ, яка дозволяє виключити „довгі” операції з циклу інтерполювання: , де ID = |IM – IФ|, IM - інтенсивність кольору траєкторії; IФ - інтенсивність кольору фонового зображення. Інтенсивність кольору піксела розраховується за формулою:

Значення модифікованої ОФ може бути розраховане рекурсивно за формулами:

де БП’ = ID, , = БП’ – МП’.

На основі встановленого взаємозв’язку оцінювальної функції з площею покриття піксела ребром багатокутника запропоновано новий метод антиаліайзингу векторів, у якому інтенсивність кольору точок визначається шляхом порівняння потокових значень оцінювальної функції з різними рівнями її максимального значення. Показано, що потоковому значенню оцінювальної функції Di однозначно відповідає певне значення інтенсивності кольору: , . Запропоновано поділити зони значень, які може приймати оцінювальна функція, на інтервали (рис 3.) та апроксимувати всередині цих інтервалів інтенсивність кольору одним дискретним значенням. Метод не потребує використання „довгих” операцій в обчислювальному процесі, що забезпечує простоту його апаратної реалізації.

Подальшого розвитку отримав табличний метод антиаліайзингу векторів. Запропоновано для розрахунку значень функції f(D, БП) = D/БП зберігати її значення з більшим кроком квантування, а проміжні - розраховувати за формулою:

f(A2 p + B, БП) = F(A, БП) + F(B, БП)/2P,

де , D = A2 p + B, p+n=m, - розрядність числа D; якщо m - парне, то n = p = m/2, інакше – n = (m-1)/2+1, p = (m-1)/2. Аналіз показав, що використання запропонованого підходу дозволяє зменшити у 817 разів обсяги пам’яті, необхідні для обчислення площі покриття піксела. Для виконання обчислень у циклі інтерполювання потрібна таблиця значень функції F(i, БП), обсяг якої не перевищує 64 байти, тому рекомендовано при апаратній реалізації використовувати оперативну пам’ять, що дозволить значно зменшити час доступу до пам’яті.

У методах крайового антиаліайзингу найбільше поширення отримала квадратна модель піксела, оскільки вона є найпростішою. Коли до якості згладжування зображеннь висуваються підвищені вимоги, то використовується конусна модель піксела. При цьому інтенсивність кольору піксела встановлюється пропорційно до об’єму, який відтинається від конуса, розташованого в центрі піксела (центр основи конуса збігається з центром піксела, радіус основи конуса дорівнює 1, об’єм конуса дорівнює 1). Інтенсивність кольору піксела обчислюється за формулою: Ip(x,) =(d,) IM + (1 –(d,))Ф, де d – відстань між центром піксела та прямою; t – товщина прямої; F(d,)=V(d +) –(d –); V(d) – об’єм, який відтинається від конуса площиною, перпендикулярною до основи конуса, розташованої на відстані d від центра конуса. Об’єм V(d) може бути розрахований за формулою:

.

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

.

Було запропоновано також більш просту її форму: Vp1(d) = –0,5 2 +. Показано, що при використанні 256 рівнів інтенсивності кольору похибка обчислення інтенсивності не перевищує 4 рівні (рис. 4а). Коефіцієнти у виразі визначаються у вигляді степені двійки, що дозволило замінити операцію множення операціями зсуву та додавання.

Із використанням поліномів Чебишева отримано нову модифікацію конусної моделі піксела, згідно з якою об’єм V(d) розраховується за формулою:

Із графіка (рис. 4б) видно, що значення абсолютної похибки обчислення об’єму V(d) не перевищує 0,0055. При використання 256 рівнів інтенсивності кольору похибка складе не більше 2 рівнів, що не позначиться на якості кінцевого зображення.

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

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

При використанні фіксованої кількості фрагментів на один піксел зображення спрощується апаратна реалізація методу А-буфера, однак пам’ять використовується неефективно, оскільки кількість фрагментів для розрахунку інтенсивності кольору піксела може суттєво відрізнятися для різних пікселів. Було запропоновано використати комбінований статично-динамічний принцип організації пам’яті, який полягає у введенні загального буфера фрагментів. В основному буфері фрагментів на кожен піксел виділяється блок пам’яті фіксованого розміру для зберігання Nосн. фрагментів полігонів та Nдод. адрес, які визначають номер фрагмента у загальному буфері фрагментів. Для загального буфера фрагментів виділяється фіксований блок пам’яті для зберігання Nзаг. фрагментів. Якщо кількість фрагментів, які згенеровано для даного піксела, перевищує Nосн., то надлишкові фрагменти зберігаються в загальному буфері фрагментів. Запропонований підхід має простішу апаратну реалізацію ніж динамічний розподіл пам’яті та потребує у 1,32,6 разів менших обсягів пам’яті для зберігання фрагментів полігонів порівняно з фіксованим розподілом.

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

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

Розроблено метод згладжування контурів, в якому для обчислення площі покриття піксела контуром графічного об’єкта використовуються оцінювальні функції, розраховані у допоміжних точках Тi ,j. всередині піксела (рис. 6). Інтенсивність кольору піксела встановлюється пропорційно до кількості допоміжних точок, які покриваються об’єктом. Площа покриття піксела знаходиться за формулою: . Для точок, які покриваються графічним примітивом, Pi ,j= 1.В усіх інших випадках Pi ,j= 0. Для визначення покриття точки об’єктом використано оцінювальну функцію, яка від’ємна для всіх точок, що лежать всередині графічного примітива. Таким чином, знак оцінювальної функції, яка розрахована у допоміжній точці Тi ,j, визначає розташування даної точки відносно межі графічного примітива. Показано, що максимальне значення абсолютної похибки обчислення площі покриття піксела графічним примітивом дорівнює: . Для випадку, коли H=V=C; max(S)=1/2C.

Для, прикладу, при використанні чотирьох допоміжних точок, на кожному кроці шукана площа апроксимується за допомогою п’яти дискретних значень: 0;1/4 ;1/2 ;3/4; 1. Для вибору дискретного значення використовуються чотири допоміжні точки: A, B, C, D (рис.7). Значення оцінювальної функції в допоміжних точках обчислюється за формулами:

;

;

;

.

Розрахунок значень оцінювальної функції у додаткових точках можна виконати незалежно. Згідно із запропонованим методом для визначення інтенсивності кольору точки на кожному кроці інтерполяції обчислюються значення оцінювальної функції у додаткових точках і перевіряється, яка кількість точок потрапила всередину кола. Якщо всередину кола попали всі 4 точки, то I=IM; якщо лише 3 точки, то I=3IM /4; якщо дві, то I=IM /2; якщо одна – то I=IM /4.

Було запропоновано використовувати різне розміщення допоміжних точок всередині піксела в залежності від характеру перетину дискретної решітки та траєкторії. Наприклад, для кола та еліпса в першому октанті можна виділити два характерні варіанти перетину. Доведено, що використання різного розміщення точок для кожного варіанта перетину (рис. 8) дозволяє підвищити точність обчислення площі покриття піксела траєкторією без збільшення кількості допоміжних точок на один піксел.

На рис. 9 показано коло, згладжене з використанням адаптивного вибору розташування допоміжних точок.

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

Основний недолік класичних методів антиаліайзингу меж кіл, які використовують конусну модель піксела, полягає у необхідності виконання „довгих” операцій у циклі інтерполювання та використанні арифметики із плаваючою комою. Було запропоновано для обчислення відстані від центра піксела до дуги кола використати модифіковану оцінювальну функцію, знак якої визначає координати точок траєкторії, а значення – відстань від точки до траєкторії. У більшості алгоритмів колової інтерполяції використовується така оцінювальна функція: OFi =i2 +i2 –2. Запропоновано використати модифіковану оцінювальну функцію, яку визначають за формулою: . Знак OF’ збігається зі знаком оцінювальної функції OF, отже вона може бути використана для визначення координат точок траєкторії кола. Відстань від центра піксела до дуги кола знаходиться за формулою: . Використання модифікованої оцінювальної функції дозволяє при визначенні відстані di виключити з обчислювального процесу „довгі” операції в циклі інтерполювання і, таким чином, підвищити швидкодію процедури антиаліайзингу та спростити апаратну реалізацію.

У дисертаційній роботі подальшого розвитку дістав табличний метод антиаліайзингу меж кіл. Отримано нові аналітичні вирази для розрахунку значень виразу :

де , T = R2 – x2, , B = T – A2 p, p<m, m – розрядність T, p - обирається залежно від необхідної точності обчислень.

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

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

,

де , , ,, IM -
інтенсивність кольору еліпса; IФ - інтенсивність кольору фонового зображення.

Якщо значення t / M представити у вигляді: , то інтенсивність кольору піксела можна розрахувати за формулою:

.

Знаходження коефіцієнтів a1 a8 виконується за таким правилом: ai=0, якщо ; інакше ai=0; k0=t; . Кількість ітерацій визначає швидкодію формування траєкторії та якість згладжування. В обчислювальному процесі відсутні „довгі” операції, що обумовлює простоту його апаратної реалізації.

П’ятий розділ дисертаційної роботи присвячено розробці програмних та апаратних засобів для реалізації запропонованих методів антиаліайзингу графічних об’єктів у системах комп’ютерної графіки. Розроблено програмний модуль, який дозволяє порівнювати результати антиаліайзингу меж графічних об’єктів із використанням різних підходів. Комп’ютерна програма виконує такі функції: формування тестового зображення відрізків прямих, кривих другого порядку; формування тривимірних графічних об’єктів у статичному та динамічному режимах із згладжуванням (з використанням обраної модифікації методу А-буфера), без згладжування (з використанням методу -буфера); визначення за нормованою середньоквадратичною похибкою (NMSE) візуальних відмінностей між двома зображеннями, сформованими за різними методами; визначення часу, який витрачається на формування тестового зображення; визначення обсягу пам’яті основного та загального буфера фрагментів; генерація синтетичних сцен різного ступеня складності для оцінювання якості згладжування складних та простих сцен. Програмне моделювання розроблених методів антиаліайзингу графічних об’єктів виконувалося з метою перевірки їх достовірності. Моделювання та тестова перевірка розроблених методів здійснювалося на комп’ютері з такою конфігурацією: процесор – AMD Athlon XP2500+; графічний відеоадаптер – GeForce4 Ti4200, 64 Mb; оперативна пам’ять – DDR 400, 512 Mb.

За базовий метод для антиаліайзингу відрізків прямих було обрано метод Гупти-Спроула, у якому використовується арифметика з плаваючою комою та конусна модель піксела. Він найчастіше використовується для тестування методів антиаліайзингу, оскільки забезпечує порівняно з іншими найбільшу точність розрахунків інтенсивності кольору точок. Результати тестування методів антиаліайзингу відрізків прямих, розроблених у розділі 3, зведено в таблицю 2. Із таблиці 2 видно, що запропоновані модифікації конусної моделі піксела забезпечують формування зображень візуально ідентичних тим, які було сформовано з використанням еталонної реалізації базової моделі, оскільки значення NMSE не перевищує 0,0001. Результати моделювання показали, що розроблені методи забезпечують підвищення швидкодії згладжування відрізків прямих порівняно з базовим методом у 2,24,4 рази.

Таблиця 2

Результати тестування методів згладжування відрізків прямих

Метод згладжування | Метод розрахунку

конусного

фільтра | Час формування всіх можливих відрізків прямих у дискретному просторі 512х512, мсек | Коефіцієнт підвищення швидкодії порівняно з базовим методом | Нормована середньо-квадратична похибка (NMSE) | Гупти-Спроула

(Базовий метод, із пл. комою) | Табличний | 23 093 | 1 | 0 | Модифікованої оцінювальної функції. (цілочисельний) | Кусково-лінійна апр | 10 390 | 2,2 | 27110-7 | Модифікованої ОФ.

(цілочисельний) | Поліном

2-го ст. | 8 484 | 2,7 | 12410-6 | Модифікований ГуптиСпроула з використанням властивості симетрії крокових приростів | Табличний | 12 060 | 1,9 | 11010-7 | Модифікованої. ОФ із використанням властивості симетрії крокових приростів | Кусково-лінійна апр. | 6 782 | 3,4 | 32210-7 | Модифікованої ОФ із використанням властивості симетрії крокових приростів | Поліном

2-го ст. | 5  | 4,4 | 12910-6 |

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

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

На рис. 10 наведено підсистему растеризації тривимірних графічних об’єктів, у якій використано розроблений модифікований метод А-буфера. Підсистема включає блоки: сортування вершин - БСВ; визначення приростів координат – ВПК; визначення координат - ВК; визначення маски покриття – ВМП; зафарбовування та текстурування – ЗТ; формування нового фрагмента – ФНФ; розрахунку масок глибини – РМГ; розрахунку інтенсивності кольору – РІК; визначення адреси – ВА; блок керування – БК; кешування фрагментів – КФ; основного буфера фрагментів – ОБФ; загального буфера фрагментів – ЗБФ; об’єднання фрагментів – ОФ.

Фрагменти, згенеровані для піксела (х, у), з основного та загального буфера фрагментів завантажуються в кеш фрагментів. У БФМГ із використанням даних про глибину та маски покриття визначається розташування фрагмента в списку вже згенерованих фрагментів. Nосн. фрагментів зберігаються у БОБФ. Якщо фрагментів більше, ніж Nосн., то в БОБФ зберігається Nдод. адрес, які визначають розташування додаткових фрагментів у загальному буфері. У випадку, якщо згенеровано більше, ніж Nосн.+ Nдод. фрагментів, у БОФ два найбільш віддалені від спостерігача фрагменти комбінуються у один.

У додатках наведено лістинг основних програмних модулів, документи про впровадження результатів наукових досліджень, свідоцтво про державну реєстрацію авторського права на комп’ютерну програму та інші матеріали.

ВИСНОВКИ

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

Основні результати досліджень є такими:

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

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

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

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

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

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

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

4. Подальшого розвитку дістав табличний метод антиаліайзингу меж кіл. Розроблено новий підхід до розрахунку площі покриття піксела колом, який дозволив зменшити у 28 разів обсяги пам’яті, необхідні для обчислення інтенсивності кольору із використанням табличного методу.

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

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

5. Розроблено нові модифікації методу А-буфера, у яких використано:

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

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

6. На основі запропонованих методів антиаліайзингу графічних об’єктів розроблено структурні схеми пристроїв для апаратної реалізації антиаліайзингу в графічних акселераторах. Створено діючі програмні засоби для згладжування графічних об’єктів у системах комп’ютерної графіки. Розроблено спеціалізовані програмні засоби для тестування методів згладжування контурів графічних об’єктів, які дозволяють отримати порівняльні оцінки за точністю і продуктивністю.

7. Результати проведених досліджень впроваджено в ВАТ “Науково-виробничий комплекс завод „Термінал”, ВАТ “Інфракон”, ТОВ „ІТ-Груп” при проектуванні високопродуктивних засобів комп’ютерної графіки, а також у навчальний процес у Вінницькому національному технічному університеті на кафедрі програмного забезпечення.

СПИСОК ПРАЦЬ, ЩО ОПУБЛІКОВАНІ АВТОРОМ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

1. Романюк О. Н., Курінний М.С. Усунення ефекту аліайзингу границі кола // Вимірювальна та обчислювальна техніка в технологічних процесах. – 2001. – №2. – С. 75-77.

2. Романюк О. Н., Курінний М.С. Усунення ефекту аліайзингу границь еліпсів // Оптико – електронні інформаційно – енергетичні технології. – 2004. – №2(8) – С. 40-47.

3. Романюк О. Н., Курінний М.С. Використання конусної моделі пікселя для
антиаліайзингу відрізків прямих // Вiсник Вiнницького полiтехнiчного iнституту. – 2004. – № 4. – С. 76-81.

4. Романюк О. Н., Курінний М.С. Антиаліайзинг границі кола з використанням модифікованої оцінювальної функції // Вісник Херсонського державного технічного університету. – 2003. – Вип. 3(19). – С. 206-208.

5. Романюк О. Н., Курінний М.С. Математичні моделі пікселів для задач антиаліайзингу // Вісник Житомирського інженерно-технологічного інституту. – 2002. – №3. – С. 35-47.

6. Романюк О. Н., Курінний М.С. Новий підхід до антиаліайзингу границь кіл з використанням табличного методу // Вимірювальна та обчислювальна техніка в технологічних процесах. – 2005. – №1. – С. 35-37.

7. Романюк О. Н., Курінний М.С. Модифікація методу А-буфера для антиаліайзингу тривимірних зображень // „Наука и предпринимательство” Сборник трудов международной научно-технической конференции. – Винница. – 2005. – С. 249-253.

8. Романюк О.Н, Курінний М.С. Використання методу оцінювальної функції для задач антиаліайзингу // Сборник научных трудов НГУ. – №19. – Том 2. – Дніпропетровськ: НГУ. – 2004. – С. 200-208.

9. Курінний М.С. Аналіз математичних моделей пікселів для задач крайового антиаліайзингу // Матеріали ІІ Міжнародної науково – практичної конференції “Динаміка наукових досліджень ‘2003”. – Том 29. – Сучасні інформаційні технології. – Дніпропетровськ: Наука і освіта. – 2003. – С. 25-27.

10. Курінний М.С. Аналіз методів антиаліайзингу // Збірник матеріалів конференції “ІНТЕРНЕТ – ОСВІТА – НАУКА 2002”. – 2002. – С. 390-392.

11. Романюк А.Н., Куринный М.С. Разработка алгоритмов антиалиайзинга векторных границ // Труды филиала МГТУ им. Н.Э. Баумана. Специальный выпуск: Материалы международн. симп. “Наука и предпринимательство”. – 2000. –С. 407- 411.

12. Патент № 40931 А України, МПК 7 G06F15/353. Лінійний інтерполятор/ О. Н. Романюк, М.С. Курінний. - №2000116433; Заяв. 14.11.2000; Опубл. 15.08.2001, Бюл. №7. - 30 с.

13. Патент № 60427 А України, МПК 7 G06F17/00. Лінійний інтерполятор/ О. Н. Романюк, М.С. Курінний. - №2002054287; Заяв. 24.05.2002; Опубл. 15.10.2003, Бюл. №10. - 32 с.

14. Романюк О. Н., Курінний М.С. Ефективний алгоритм антиаліайзингу векторних границь багатокутника // Вимірювальна та обчислювальна техніка в технологічних процесах: Збірник наукових праць. Хмельницький: ТУП, 2002. – С. 105-109.

15. Романюк О. Н., Курінний М.С. Ефективний алгоритм антиаліайзингу відрізків прямих // Збірник матеріалів ІІІ - ї міжнародної науково – технічної конференції “Приборостроение - 2003”. – 2003. – С. 42 - 46.

16. Романюк О. Н., Курінний М.С. Комп’ютерна програма “Програма формування еліпсів з усуненням ефекту аліайзингу” / Свідоцтво про реєстрацію авторського права на твір № 12165 ПА. України - Заявлено 17.12.2004; Видано 03.02.2005.

17. Романюк О.Н, Курінний М.С. Розробка принципів апаратної реалізації антиаліайзингу векторних границь полігонів //Збірник тез доповідей міжнародної науково-технічної конференції молодих вчених, аспірантів та студентів „Оптоелектронні інформаційно – енергетичні технології”. - Вінниця. - 2001. – С.154.

АНОТАЦІЯ

Курінний М.С. Методи та засоби антиаліайзингу контурів об’єктів у системах комп’ютерної графіки. – Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю
05.13.13 – Обчислювальні машини,