Використання квадратичної інтерполяції для зафарбовування тривимірних графічних об’єктів
Розглянуто питання використання квадратичної інтерполяції для зафарбовування тривимірних графічних об’єктів. Запропоновано два нових підходи до зафарбовування. Згідно з першим підходом розраховуються інтенсивності кольору в кінцевих і середній точках рядка растеризації, а всі потокові визначають із...
Збережено в:
| Дата: | 2006 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Ukrainian |
| Опубліковано: |
Інститут проблем реєстрації інформації НАН України
2006
|
| Назва видання: | Реєстрація, зберігання і обробка даних |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/50860 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Використання квадратичної інтерполяції для зафарбовування тривимірних графічних об’єктів / О.Н. Романюк // Реєстрація, зберігання і оброб. даних. — 2006. — Т. 8, № 4. — С. 31-37. — Бібліогр.: 4 назв. — укр. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-50860 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-508602013-11-06T03:07:27Z Використання квадратичної інтерполяції для зафарбовування тривимірних графічних об’єктів Романюк, О.Н. Математичні методи обробки даних Розглянуто питання використання квадратичної інтерполяції для зафарбовування тривимірних графічних об’єктів. Запропоновано два нових підходи до зафарбовування. Згідно з першим підходом розраховуються інтенсивності кольору в кінцевих і середній точках рядка растеризації, а всі потокові визначають із використанням квадратичної інтерполяції. Суттєва відмінність другого підходу полягає в тому, що замість інтенсивностей кольору визначаються вектори нормалей, які в подальшому використовуються для розрахунку дифузної та дзеркальної складової кольору. Рассмотрены вопросы использования квадратичной интерполяции для закраски трехмерных графических объектов. Предложены два новых подхода к закраске. В соответствии с первым подходом рассчитываются интенсивности цвета в конечных и средней точках строки растеризации, а все промежуточные определяются с использованием квадратичной интерполяции. Существенное отличие второго подхода состоит в том, что вместо интенсивностей цвета определяются векторы нормалей, которые впоследствии используются для расчета диффузной и спекулярной составляющей цвета. Problems of using quadratic interpolation for shading of three-dimensional graphic objects are considered. Two new approaches of shading are offered. According to the first one the intensities of color in final and middle dots of rasterization line are calculated and the all intermediate are defined by using quadratic interpolation. The essential difference of the second approach is that instead of intensities of color the normal vectors are defined, which later on are used for calculating diffuse and specular color component. 2006 Article Використання квадратичної інтерполяції для зафарбовування тривимірних графічних об’єктів / О.Н. Романюк // Реєстрація, зберігання і оброб. даних. — 2006. — Т. 8, № 4. — С. 31-37. — Бібліогр.: 4 назв. — укр. 1560-9189 http://dspace.nbuv.gov.ua/handle/123456789/50860 004.92 uk Реєстрація, зберігання і обробка даних Інститут проблем реєстрації інформації НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Ukrainian |
| topic |
Математичні методи обробки даних Математичні методи обробки даних |
| spellingShingle |
Математичні методи обробки даних Математичні методи обробки даних Романюк, О.Н. Використання квадратичної інтерполяції для зафарбовування тривимірних графічних об’єктів Реєстрація, зберігання і обробка даних |
| description |
Розглянуто питання використання квадратичної інтерполяції для зафарбовування тривимірних графічних об’єктів. Запропоновано два нових підходи до зафарбовування. Згідно з першим підходом розраховуються інтенсивності кольору в кінцевих і середній точках рядка растеризації, а всі потокові визначають із використанням квадратичної інтерполяції. Суттєва відмінність другого підходу полягає в тому, що замість інтенсивностей кольору визначаються вектори нормалей, які в подальшому використовуються для розрахунку дифузної та дзеркальної складової кольору. |
| format |
Article |
| author |
Романюк, О.Н. |
| author_facet |
Романюк, О.Н. |
| author_sort |
Романюк, О.Н. |
| title |
Використання квадратичної інтерполяції для зафарбовування тривимірних графічних об’єктів |
| title_short |
Використання квадратичної інтерполяції для зафарбовування тривимірних графічних об’єктів |
| title_full |
Використання квадратичної інтерполяції для зафарбовування тривимірних графічних об’єктів |
| title_fullStr |
Використання квадратичної інтерполяції для зафарбовування тривимірних графічних об’єктів |
| title_full_unstemmed |
Використання квадратичної інтерполяції для зафарбовування тривимірних графічних об’єктів |
| title_sort |
використання квадратичної інтерполяції для зафарбовування тривимірних графічних об’єктів |
| publisher |
Інститут проблем реєстрації інформації НАН України |
| publishDate |
2006 |
| topic_facet |
Математичні методи обробки даних |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/50860 |
| citation_txt |
Використання квадратичної інтерполяції для зафарбовування тривимірних графічних об’єктів / О.Н. Романюк // Реєстрація, зберігання і оброб. даних. — 2006. — Т. 8, № 4. — С. 31-37. — Бібліогр.: 4 назв. — укр. |
| series |
Реєстрація, зберігання і обробка даних |
| work_keys_str_mv |
AT romanûkon vikoristannâkvadratičnoíínterpolâcíídlâzafarbovuvannâtrivimírnihgrafíčnihobêktív |
| first_indexed |
2025-07-04T12:43:29Z |
| last_indexed |
2025-07-04T12:43:29Z |
| _version_ |
1836720336138141696 |
| fulltext |
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2006, Т. 8, № 4 31
УДК 004.92
О. Н. Романюк
Вінницький національний технічний університет
Використання квадратичної інтерполяції
для зафарбовування тривимірних графічних об’єктів
Розглянуто питання використання квадратичної інтерполяції для за-
фарбовування тривимірних графічних об’єктів. Запропоновано два но-
вих підходи до зафарбовування. Згідно з першим підходом розрахову-
ються інтенсивності кольору в кінцевих і середній точках рядка рас-
теризації, а всі потокові визначають із використанням квадратичної
інтерполяції. Суттєва відмінність другого підходу полягає в тому, що
замість інтенсивностей кольору визначаються вектори нормалей, які
в подальшому використовуються для розрахунку дифузної та дзерка-
льної складової кольору.
Ключові слова: зафарбовування, рендеринг, нормалізація векторів
нормалей.
Вступ
Одним із пріоритетних напрямків розвитку комп’ютерної графіки є форму-
вання в реальному часі тривимірних зображень, які характеризуються високою
реалістичністю та інформативністю. Одним з основних та найбільш трудомістких
етапів формування реалістичних зображень є етап зафарбовування, на якому роз-
раховуються екранні координати пікселів поверхні та їхні інтенсивності кольору.
Традиційні засоби, які використовуються для цього, не завжди в змозі забезпечи-
ти продуктивність, необхідну для відтворення сцени в реальному часі. Указане
обумовлює необхідність розробки більш продуктивних методів і засобів зафарбо-
вування тривимірних графічних об’єктів.
Аналіз методів і постановка задачі
Серед методів зафарбовування тривимірних об’єктів найбільшого поширення
отримали методи Гуро та Фонга [1, 2].
У методі Гуро [1, 2] розраховуються інтенсивності кольору для полігональ-
них вершин, які потім у процесі растеризації лінійно інтерполюються вздовж ре-
бер і рядків сканування. Більш перспективним уважається метод Фонга, в якому
замість значень інтенсивності кольору інтерполюються вектори нормалей, які по-
© О. Н. Романюк
О. Н. Романюк
32
тім використовуються у функції тонування для обчислення інтенсивності кольору
кожного елемента зображення. Цей метод порівняно з методом Гуро характери-
зується значно більшими обчислювальними витратами, однак при цьому дося-
гається краща локальна апроксимація кривизни поверхні та, як наслідок, отри-
муються більш реалістичні зображення.
Метод Гуро, який реалізовано практично в усіх сучасних графічних акселера-
торах, найбільш придатний тільки для формування матових поверхонь та таких,
які погано відбивають світло, тому що лінійна кодова інтерполяція інтенсивнос-
тей кольору не враховує кривизни поверхні, у той час, як дифузна та дзеркальна
складові інтенсивності кольору мають нелінійну залежність від координат піксе-
лів.
Основною перешкодою до широкого впровадження методу Фонга в графічні
акселератори є великий обсягом обчислень, оскільки для кожної точки поверхні
необхідно обчислити вектор нормалі N
r
до поверхні, вектор напрямку джерела
світла L
r
, вектор спостерігача V
rr
, серединний вектор H
r
, нормалізувати їх, знайти
скалярні добутки LNHN
rrrr
×× , й обчислити інтенсивність кольору згідно функції
тонування [1, 2]:
))(( n
sdaa HNkLNkIkII
rrrr
××+××+×= , (1)
де aI — інтенсивність розсіяного світла; I — інтенсивність джерела свтла;
sda kkk ,, — відповідно коефіцієнти розсіяного, спекулярного та дифузного від-
биття; п — коефіцієнт спекулярності поверхні. Слід зазначити, що всі вектори, які
використовуються у функції (1) тонування, повинні бути нормалізовані.
Мета статті — спрощення методу Фонга за рахунок виконання розрахунків
інтенсивностей кольору згідно функції тонування тільки для точок, які належать
ребрам трикутника, з подальшим використанням квадратичного інтерполювання
інтенсивностей кольору або векторів нормалей уздовж рядків растеризації.
Розробка методів зафарбовування
По векторах нормалей ),(),,( , CABA NNNN
rrr
(рис. 1) легко розрахувати нормо-
вані значення векторів нормалей ,,liN
r
piN ,
r
у крайніх точках рядка растеризації
відповідно лівого та правого ребер трикутника. Аналогічні дії виконують і для
векторів H
r
і L
r
. Згідно функції тонування (1) розраховують інтенсивності кольо-
ру в лівій і правій точках рядка растеризації.
Обчислюють значення інтенсивності кольору в середній точці рядка растери-
зації, яка може й не співпадати з точкою координатної решітки. Вектор нормалі в
середній точці і-го рядка растеризації можна обчислити за формулою [3]:
.
)1(2 ,,
,,
,
pili
pili
ci
NN
NN
N rr
rr
r
×+
+
=
Використання квадратичної інтерполяції для зафарбовування тривимірних графічних об’єктів
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2006, Т. 8, № 4 33
Формули для розрахунку ciH ,
r
, ciL ,
r
аналогічні. За отриманими значеннями
векторів нормалей згідно формули (1) знаходять ciI , .
Таким чином, для кожного рядка растеризації розраховують інтенсивності
кольору picili III ,,, ,, відповідно в лівій, середній та правій точках.
Проміжні значення інтенсивностей кольору в рядку растеризації знайдемо за
формулою:
iiiti CtBtAI +×+×= 2
, , (2)
де t змінюється від нуля до одиниці. Знайдемо невідомі iii CBA ,, .
При 0=t ili CI =, . У правій точці рядка растеризації 1=t , тому
iiipi CBAI ++=, .
У середній точці рядка растеризації 2/1=t , тому i
ii
ci CBAI ++=
24, .
Розв’язавши систему рівнянь
ï
ï
ï
î
ïï
ï
í
ì
++=
++=
=
,
24
,
,
,
,
,
i
ii
ci
iiipi
ili
CBAI
CBAI
CI
знаходимо невідомі iii CBA ,, :
liilipiciilicipii ICIIIBIIIA ,,,,,,, ,34,242 =×--×=×+×-×= .
Рис. 1. Вектори нормалей
до ребер трикутника
О. Н. Романюк
34
Підставивши значення коефіцієнтів у рівняння (2), отримуємо:
lilipicilicipiti ItIIItIIII ,,,,
2
,,,, )34()242( +××--×+××+×-×= .
Якщо j — позиція піксела в рядку растеризації, то потокове значення змін-
ної t буде дорівнювати d
j , де d — довжина рядка растеризації. Приріст tD на
один піксел дорівнює d
1 .
Підставивши в рівняння (2) значення ,ttt D+= отримуємо:
).)2(()()( ,
2
, iitiiiitti BttAtICttBttAI +D+××D+=+D+×+D+=D+
Нехай
))2((, iiti BttAtW +D+××D= . (3)
Знайдемо значення останнього виразу для ttt D+= :
2
, 2))2(()))(2(( tABtAtBtttAtW iiiiitti D×++D+××D=+D+D+××D=D+ .
З урахуванням виразу (3) отримуємо:
2
,, 2 tAWW ititti D×+=D+ .
Останній член є константою для рядка растеризації та може бути розрахова-
ним на етапі підготування до зафарбовування. Граф-схему алгоритму розрахунку
інтенсивностей кольору в рядку растеризації наведено на рис. 2, де j — позиція
піксела в рядку растеризації.
Кількість і склад операцій для зафарбовування середнього трикутника, який
містить 100 точок ( 12,9,4,16,8,8 =D=D=D=D=D=D ACACBCBCABAB xxYxyx ), за
методом Фонга і запропонованим методом наведено в таблиці.
Кількість і склад операцій для зафарбовування середнього трикутника
Метод зафарбовування
Кількість операцій
Додавання Множення Ділення Квадратний корінь
Метод Фонга 1903 2490 987 324
Запропонований метод 2944 2364 201 24
Використання квадратичної інтерполяції для зафарбовування тривимірних графічних об’єктів
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2006, Т. 8, № 4 35
Рис. 2. Граф-схема алгоритму визначення інтенсивностей кольору точок рядка растеризації
З таблиці видно, що при використанні для зафарбовування квадратичної
інтерполяції досягається суттєве підвищення продуктивності за рахунок змен-
шення кількості довготривалих операцій ділення та знаходження квадратного
кореня. Так, наприклад, час зафарбовування середнього трикутника (див. табли-
О. Н. Романюк
36
цю) зменшився в 3,5 рази (для отримання оцінки було використано дані [4] про
кількість тактів роботи мікропроцесора для наведених у таблиці мікрооперацій).
Запропонований підхід найбільш доцільно використати для об’єктів із висо-
кою щільністю тріангуляційної мережі, де ймовірність різкого переходу інтенсив-
ностей кольору в межах трикутника достатньо мала.
Для об’єктів із малим та середнім ступенем деталізації доцільно інтерполю-
вати вектори нормалей N
r
і H
r
, які враховують локальну кривизну поверхні, а та-
кож положення джерела світла та спостерігача. Якщо для і-го рядка растеризації
задано вектор нормалей liN ,
r
і piN ,
r
, то згідно наведеної раніше формули для роз-
рахунку ciN ,
r
легко знайти вектор у середній точці рядка.
Проміжні значення векторів нормалей у рядку растеризації знайдемо за фор-
мулою:
iiiti QtPtGN
rrrr
+×+×= 2
, .
Аналогічно до розв’язку рівняння (2), знаходимо:
liilipiciilicipii NQNNNPNNNG ,,,,,,, ,34,242
rrrrrrrrrr
=×--×=×+×-×= .
Позначимо
)1(2
1
,, pili NN
rr
×+
через ih , тоді:
)( ,,, piliici NNhN
rrr
+= ,
liipipiliipilii NQNNNhPNNhG ,,,,,, ,2)()34(),()21(2
rrrrrrrrr
=×++×-=+××-= .
Неважко побачити, що ipilii GNNP
rrrr
-+= )( ,, .
Аналіз розкладу ih у ряди Тейлора, Лежандра, Лагера, Чебішева показав, що
найменшу похибку апроксимації забезпечує ряд Чебішева.
Позначимо ipili NN шcos,, =×
rr
через r, де iш — кут між векторами liN ,
r
і piN ,
r
.
Тоді функцію
)1(2
1
r+
можна апроксимувати поліномом Чебішева другого сту-
пеня: 705,0306,0103,0
)1(2
1 2 +-»
+
rr
r
.
На рис. 3 зображено графік відносної похибки апроксимації, яка не переви-
щує 0,36 %. Використання запропонованої формули дозволяє зменшити час роз-
рахунку вектора нормалі в середній точці рядка растеризації майже в чотири рази
порівняно із класичною реалізацією.
Використання квадратичної інтерполяції для зафарбовування тривимірних графічних об’єктів
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2006, Т. 8, № 4 37
Аналіз показав, що для зафарбовування середнього трикутника, параметри
якого наведено вище, при визначені векторів нормалей згідно запропонованого
методу необхідно виконати таку кількість мікрооперацій: додавань — 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.
Надійшла до редакції 16.11.2006
Рис. 3. Відносна похибка
апроксимації виразу
)1(2
1
r+
рядом Чебішева
УДК 004.92
УДК 004.92
Вступ
Аналіз методів і постановка задачі
|