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

О. Н. Романюк

Размещено на http://www.allbest.ru/

32

Размещено на http://www.allbest.ru/

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

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

Серед методів зафарбовування тривимірних об'єктів найбільшого поширення отримали методи Гуро та Фонга [1, 2].

У методі Гуро [1, 2] розраховуються інтенсивності кольору для полігональних вершин, які потім у процесі растеризації лінійно інтерполюються вздовж ребер і рядків сканування. Більш перспективним уважається метод Фонга, в якому замість значень інтенсивності кольору інтерполюються вектори нормалей, які потім використовуються у функції тонування для обчислення інтенсивності кольору кожного елемента зображення. Цей метод порівняно з методом Гуро характери-зується значно більшими обчислювальними витратами, однак при цьому дося-гається краща локальна апроксимація кривизни поверхні та, як наслідок, отри-муються більш реалістичні зображення.

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

Основною перешкодою до широкого впровадження методу Фонга в графічні акселератори є великий обсягом обчислень, оскільки для кожної точки поверхні необхідно обчислити вектор нормалі до поверхні, вектор напрямку джерела світла , вектор спостерігача , серединний вектор , нормалізувати їх, знайти скалярні добутки й обчислити інтенсивність кольору згідно функції тонування [1, 2]:

, (1)

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

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

По векторах нормалей (рис. 1) легко розрахувати нормовані значення векторів нормалей у крайніх точках рядка растеризації відповідно лівого та правого ребер трикутника. Аналогічні дії виконують і для векторів і . Згідно функції тонування (1) розраховують інтенсивності кольору в лівій і правій точках рядка растеризації.

Обчислюють значення інтенсивності кольору в середній точці рядка растеризації, яка може й не співпадати з точкою координатної решітки. Вектор нормалі в середній точці і-го рядка растеризації можна обчислити за формулою [3]:

зафарбовування растерізація колір інтерполяція

Формули для розрахунку , аналогічні. За отриманими значеннями векторів нормалей згідно формули (1) знаходять .

Рис. 1. Вектори нормалей до ребер трикутника

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

Проміжні значення інтенсивностей кольору в рядку растеризації знайдемо за формулою:

, (2)

де змінюється від нуля до одиниці. Знайдемо невідомі .

При . У правій точці рядка растеризації , тому .

У середній точці рядка растеризації , тому .

Розв'язавши систему рівнянь

знаходимо невідомі :

.

Підставивши значення коефіцієнтів у рівняння (2), отримуємо:

.

Якщо - позиція піксела в рядку растеризації, то потокове значення змінної буде дорівнювати , де - довжина рядка растеризації. Приріст на один піксел дорівнює .

Підставивши в рівняння (2) значення отримуємо:

Нехай

. (3)

Знайдемо значення останнього виразу для :

.

З урахуванням виразу (3) отримуємо:

.

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

Кількість і склад операцій для зафарбовування середнього трикутника, який містить 100 точок (), за методом Фонга і запропонованим методом наведено в таблиці.

Кількість і склад операцій для зафарбовування середнього трикутника

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

З таблиці видно, що при використанні для зафарбовування квадратичної інтерполяції досягається суттєве підвищення продуктивності за рахунок змен-шення кількості довготривалих операцій ділення та знаходження квадратного кореня. Так, наприклад, час зафарбовування середнього трикутника (див. табли-цю) зменшився в 3,5 рази (для отримання оцінки було використано дані [4] про кількість тактів роботи мікропроцесора для наведених у таблиці мікрооперацій).

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

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

Проміжні значення векторів нормалей у рядку растеризації знайдемо за формулою:

.

Аналогічно до розв'язку рівняння (2), знаходимо:

.

Позначимо через , тоді:

,

.

Неважко побачити, що .

Аналіз розкладу у ряди Тейлора, Лежандра, Лагера, Чебішева показав, що найменшу похибку апроксимації забезпечує ряд Чебішева.

Позначимо через r, де - кут між векторами і . Тоді функцію можна апроксимувати поліномом Чебішева другого ступеня: .

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

Рис. 3. Відносна похибкаапроксимації виразу рядом Чебішева

Аналіз показав, що для зафарбовування середнього трикутника, параметри якого наведено вище, при визначені векторів нормалей згідно запропонованого методу необхідно виконати таку кількість мікрооперацій: додавань - 2944, множень - 2362, ділень - 201, квадратний корінь - 24. Час зафарбовування середнього трикутника порівняно із класичною реалізацією методу Фонга зменшився у два рази, що є вагомим підтвердженням суттєвого підвищення продуктивності.

Запропоновані методи дозволили суттєво підвищити продуктивність зафарбовування. Візуальна відмінність між тестовими зображеннями оцінювалася за нормованою середньоквадратичною похибкою (NMSE), значення якої не перевищувало 0,00025, що є прийнятним при формуванні реалістичних зображень.

Література

1. Херн Д., Павлин Бейкер М. Компьютерная графика и стандарт OpenGL. - М.: Издательский дом «Вильямс», 2005. - 1168 с.

2. Роджерс Д. Алгоритмические основы машинной графики: Пер. с англ. - М.: Мир, 1989. - 512 с.

3. Романюк О.Н. Комбіноване використання бінарної та кодової лінійної інтерполяції для нормалізації векторів нормалей при зафарбовуванні тривимірних об'єктів // Вестник Херсонского национального технического университета. - Херсон: ХНТУ, 2006. - Вып. 2 (25). - С. 408-411.

4. Pentium™ Processor Family User's Manual. Volume 3: Architecture and Programming Manual. 1994.

Размещено на Allbest.ru