Методи та апаратні засоби нанесення текстур для синтезу зображень зворотним трасуванням у системах візуалізації

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

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

УДК 681.323

05.13.05 - комп'ютерні системи та компоненти

Автореферат

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

МЕТОДИ ТА АПАРАТНІ ЗАСОБИ НАНЕСЕННЯ ТЕКСТУР ДЛЯ СИНТЕЗУ ЗОБРАЖЕНЬ ЗВОРОТНИМ ТРАСУВАННЯМ У СИСТЕМАХ ВІЗУАЛІЗАЦІЇ

Кожушко Дмитро Геннадійович

Харків - 2011

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

Робота виконана у Харківському національному університеті радіоелектроніки, Міністерство освіти і науки, молоді та спорту України.

Науковий керівник кандидат технічних наук, доцент Гусятін Володимир Михайлович, Харківський національний університет радіоелектроніки, професор кафедри електронних обчислювальних машин.

Офіційні опоненти: доктор технічних наук, професор Хаханов Володимир Іванович, Харківський національний університет радіоелектроніки, професор кафедри автоматизації проектування обчислювальної техніки.

доктор технічних наук, професор Качанов Петро Олексійович, Національний технічний університет «Харківський політехнічний інститут», завідувач кафедри автоматики і управління в технічних системах;

Захист відбудеться „25” травня 2011 р. о 15 годині на засіданні спеціалізованої вченої ради Д 64.052.01 у Харківському національному університеті радіоелектроніки за адресою: 61166, м. Харків, просп. Леніна, 14.

З дисертацією можна ознайомитися в бібліотеці Харківського національного університету радіоелектроніки за адресою: 61166, м. Харків, просп. Леніна, 14.

Автореферат розіслано „23” квітня 2011 р.

Вчений секретар спеціалізованої вченої ради С.Ф. Чалий



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

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

Роботи у галузі розробки наукових основ створення систем візуалізації мають для України велике значення: нові системи візуалізації дозволять модернізувати парк тренажерів, підвищити якість підготовки операторів транспортних засобів, уникнути ризику при відпрацьовуванні позаштатних ситуацій, знизити витрати пального. Внесок в галузь створення систем візуалізації зробили такі вчені, як Akeley K., Foley V., Fuchs H., Hodges L., Feiner S., Іванов В.П., Ковальов А.М., Башков Е.А., Белецький А.Я., Романюк А.Н., Коба Ю.А., Зорі C.А., Гусятін В.М. та ін.

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

Зв'язок роботи з науковими програмами. Дисертаційна робота була виконана відповідно до плану науково-дослідних робіт Харківського національного університету радіоелектроніки за напрямком державної бюджетної теми № 179-1 “Дослідження й розробка методів, структурних та архітектурних принципів, апаратних і програмних засобів швидких цифрових перетворень зображень” (ДР №0104U004074). У рамках даної теми автором були розроблені формати подання векторних текстур, метод анізотропної фільтрації в площині текстури.

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

Для цього необхідно вирішити такі завдання:

1. Розробити метод анізотропної фільтрації в площині текстури для синтезу зображень 3D об'єктів методом зворотного трасування;

2. Розробити методи упаковки векторних текстур, орієнтованих на зменшення об'єму пам'яті, необхідного для їхнього подання.

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

4. Удосконалити метод усунення крайового аліасинга при синтезі зображень 3D об'єктів методом зворотного трасування.

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

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

Предмет дослідження - методи та апаратні засоби нанесення текстур з усуненням аліасинга при формуванні зображень методом зворотного трасування.

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

Наукова новизна отриманих результатів. При рішенні поставлених завдань автором були отримані наступні наукові результати:

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

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

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

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

Практичне значення одержаних результатів. На основі проведених теоретичних досліджень виконано таке:

- розроблено процедуру анізотропної фільтрації в площині текстури;

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

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

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

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

- розроблено структурні та функціональні схеми спецпроцесорів нанесення текстур.

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

Запропоновані в роботі спецпроцесори можливо використати при побудові систем візуалізації для підвищення продуктивності синтезу зображень.

Наукові результати, отримані під час виконання дисертаційної роботи, використано при модернізації системи відображення інформації в НЦУВКЗ м. Євпаторія (акт впровадження від 13.12.09), а також були впроваджені в навчальний процес Харківського національного університету радіоелектроніки (акт впровадження від 14.12.10).

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

Апробація результатів дисертації. Результати досліджень були оприлюднені на 8-му Міжнародному молодіжному форумі «Радиоэлектроника и молодежь в XXI веке» (Харків, 2004); V Міжнародній конференції «Проблемы информатики и моделирования» (Харків, 2005); 10-му Міжнародному форумі «Радиоэлектроника и молодежь в XXI веке» (Харків, 2006); 2-й Міжнародній науковій конференції «Сучасні інформаційні системи. Проблеми та тенденції розвитку» (Харків, 2007); VII Міжнародній конференції «Проблемы информатики и моделирования» (Харків, 2007); VIII міжнародній конференції «Проблемы информатики и моделирования» (Харків, 2008); 13-му Міжнародному молодіжному форумі «Радиоэлектроника и молодежь в XXI веке» (Харків, 2009); IX Міжнародній конференції «Проблемы информатики и моделирования» (Харків, 2009).

Публікації. Результати дисертації опубліковані в 17 друкованих працях: 9 статтях у наукових збірниках, які входять до переліку ВАК України, 8 матеріалах конференцій.

Структура й обсяг дисертації. Дисертація складається із вступу, чотирьох розділів, висновків, списку використаних джерел, додатків. Загальний обсяг роботи - 170 сторінок, з яких основний зміст викладено на 130 сторінках. Робота містить 48 рисунка та 1 таблицю. Список джерел складається з 85 найменувань на 9 сторінках. Додатки містять результати експериментальних досліджень і акти впровадження (загалом 31 сторінка).

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

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

У першому розділі проведений аналіз існуючих методів синтезу 3D зображень. Показано, що метод зворотного трасування дозволяє досягти більшого ступеня реалістичності, що є актуальним при проектуванні систем візуалізації (СВ) тренажерів транспортних засобів. Розглянуто існуючі методи нанесення текстур та основні причини виникнення ефекту аліасинга при синтезі зображень методом зворотного трасування. При обчисленні центральної проекції об'єктів сцени на дискретно задану площину екрана (методом зворотного трасування променів) кожному пікселю екрана ставиться у відповідність єдина точка видимої частини об'єкта й відповідний їй тексель на площині текстури, який задає складову кольору даного пікселя. У цьому випадку при дискретизації частина інформації може бути загублена, якщо верхня просторова частота функції, що відображається, перевищує половину частоти дискретизації на площині екрана [3]. У наслідок цього виникає спотворення зображення проекції 3D об'єктів на екрані, яке отримало назву - аліасинг. Розглянуто існуючі методи усунення аліасинга. Поміж них слід виділити такі: засновані на збільшенні частоти дискретизації (кількості вибірок); методи, орієнтовані на зменшення високочастотних складових проекцій 3D зображень (дрібних об'єктів, деталей малюнка текстури) за рахунок введення рівнів деталізації. На підставі проведеного аналізу визначена сукупність перспективних задач дослідження в галузі розробки методів нанесення текстур з усуненням аліасингу, орієнтованих на синтез зображень методом зворотного трасування в реальному часі.

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

На початку розглянуто одновимірний випадок метода анізотропної фільтрації. Докладний аналіз одновимірного випадку фільтрації [3,17] дозволив поширити запропонований метод на двовимірний випадок.

За аналогією з одновимірним випадком введена функція , що є проекцією функції текстури на безперервну площину екрана. Для цієї функції виведені співвідношення:



, , (1)

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

Для виключення зі спектра функції частот, що перевищують половину частоти дискретизації, аналогічно до одновимірного випадку застосована лінійна фільтрація (згортка з ядром фільтра ):

, (2)

де: - функція, отримана в результаті згортки; ядро фільтра; - змінні інтегрування в площині екрана.

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

Для виконання фільтрації в площині текстури виконана заміна змінної інтегрування і записана формула згортки, еквівалентна (2), згідно (1):

. (3)

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



, (4)

де - проекція на площину текстури; - задають зсув ядра фільтра в екрані. Тоді (3) приймає вигляд:

, (5)

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

, (6)

Розглянуті наступні два види функції фільтра : «Box» і «Куранта».

Для кожного з типів фільтрів запропоновані [8] функції, що апроксимують їхні проекції на площину текстури.

- В якості функції, що апроксимує проекцію фільтра «Box» на площину текстури, запропоновано вибрати функцію:

,

де: - мішаний добуток (), - проекції вершин пікселя на площину текстури, узяті в такому порядку, що при обході від до проекція пікселя залишається праворуч; .

В якості функції, що апроксимує проекцію фільтра «Куранта» на площину текстури, запропоновано вибрати функцію:

, (7)

де:,, , ,,,

- координати точки ; - координати точки ,

- проекції центрів сімох сусідніх пікселів на площину текстури.

Для перевірки коректності запропонованого підходу до фільтрації виконане моделювання. В якості тестової функції (текстури) для оцінки якості фільтрації використовувалася функція -“шахівниця”. Результати моделювання показали, що виконання фільтрації запропонованим методом у площині текстури дозволяє усувати ефект аліасинга так само якісно, як у випадку фільтрації в площині екрана або з виконанням суперсемплінгу.

Розроблено метод швидких обчислень зваженого кольору проекції пікселя [4] для випадку анізотропної фільтрації функцією «Box» і «Курант». У комп'ютерній графіці текстура задається на основі матриці кольорів: , де - значення кольору для елементу з номером . - цілі числа; , - ціле число, . Використовуючи елементи матриці, задається функція , для якої координати нормалізовані та знаходяться в інтервалі :

, (8)

де:

Для швидкого обчислення (2) у випадку, коли текстура задана згідно (8), скористаємося способом подання текстури у вигляді кватернарного дерева. В кожній вершині дерева запропоновано зберігати інформацію, необхідну для швидкого обчислення (2). Вершина дерева відповідає області текстури, що має форму квадрата, яка, в свою чергу, може ділитися на чотири квадрати меншого розміру. Швидкі обчислення інтегрального кольору проекції пікселя запропоновано здійснювати наступним шляхом: визначаються квадрати, які відповідають вершинам, що повністю попали в середину проекції пікселя (для цього проекція пікселя розбивається на трикутники, а пошук відбувається для кожного трикутника окремо), в процесі пошуку визначається сума значень, що міститься в цих вершинах, зважених на відповідну вагову функцію. Далі на основі цієї суми вираховується інтегральний колір проекції пікселя. Вид інформації, що зберігається в вершинах дерева, відрізняється в залежності від типу вагової функції . Для випадку функції «Box» у вершинах дерева зберігається зважений колір: , де - номери вершини в рівні дерева, - номер рівня дерева. Значення зважених кольорів вершин верхнього рівня дерева обчислюються за формулою: , де - номер верхнього рівня дерева. Кожен наступний рівень дерева формується на базі попереднього за допомогою співвідношення:

для усіх .

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

, для усіх ,

де під операцією додавання кортежів розуміється їх поелементне додавання.

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

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

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

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

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

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

Запропоновано в якості формату текстур використовувати кватернарне дерево (КД), англ. quadtree. Відомі два різновиди КД: повне й неповне. При розгляді форматів подання текстур уведене поняття класифікаційного квадрата, що є ключовим при розгляді запакування й розпакування текстури. Класифікаційний квадрат (КК) - це область текстури, що має форму квадрата, яка, у свою чергу, може ділитися на чотири КК, менших за розміром. В остаточному підсумку текстура складається з кінцевого набору КК.

Було показано, що повне кватернарне дерево доцільно використовувати для текстур, у яких деталізація рівномірно розподілена по площі (растрові й векторні прості рівномірні зображення). У літературі відомі способи подання растрових текстур у вигляді повного кватернарного дерева (наприклад, MIP-карти) [6]. Неповне кватернарне дерево підходить для випадків, коли текстура має нерівномірний розподіл деталізації (векторні з довільними лініями розділу, векторні прості нерівномірні), що дозволяє істотно скоротити обсяги пам'яті.

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

Основною особливістю запропонованого способу зберігання текстур є те, що у всіх вершинах зберігається інтегральний колір. У роботі запропоновані методи упакування векторного зображення з довільними лініями розділу й векторного простого нерівномірного зображення [6,12]. Для кожного виду зображень наведений метод упакування й формат КК. На рис. 1 а показана векторна текстура з довільними лініями розділу, яка попередньо переведена до растрової форми.

Рис. 1. Ілюстрація процесу упаковки: а - векторної текстури з довільними лініями розділу; б - векторної простої нерівномірної текстури

Наведено ілюстрацію процесу упаковки (побудови неповного кватернарного дерева). Для спрощення ілюстрації процесу упаковки розглянуто зображення одиниці. На рис. 1 б показана векторна проста нерівномірна текстура (фрагмент злітної смуги) та приклад її упаковки згідно з запропонованим методом. Було проведено моделювання, у результаті якого вихідне растрове подання векторної текстури літака (розмір вихідного растрового подання 201 326 646 байт) було упаковано згідно з методом для векторних текстур з довільними лініями розділу, при цьому розмір файлу упакованої текстури склав 1 825 834 байт. Вихідне зображення злітних смуг аеропорту Бориспіль (кількість фігур 500), було упаковано запропонованим методом для векторних простих нерівномірних текстур. Кількість рівнів вибрано 20, при цьому розмір упакованого файлу текстури склав 4 850 580 байт, а еквівалент по роздільній здатності у растровій формі зайняв би що найменше байт.

Далі в розділі викладається метод нанесення текстур з одночасним усуненням аліасинга. Даний метод ґрунтується на методі анізотропної фільтрації в площині текстури [11], що запропонований у другому розділі для випадку фільтрації функцією «Box» й дозволяє працювати із запропонованими форматами текстур без їхнього розпакування в реальному масштабі часу з одночасним усуненням аліасинга [7]. При синтезі зображення тривимірної сцени методом зворотного трасування із центра проекцій h будемо трасувати промені, що проходять через кожну вершину пікселів екрана. Для екрана з роздільною здатністю m на n пікселів необхідно провести променів. Таким чином, для кожного пікселя розглядається четвірка променів, що проходять через його вершини. Розглянемо випадок, коли всі чотири перетинання проекційного променя належать одному примітиву. У загальному випадку справжня проекція пікселя на поверхню примітива являє собою просторову фігуру. Знаходження проекції такої просторової фігури на площину текстури являє собою нетривіальне завдання.

Запропоновано [7,13] знаходити лише проекції чотирьох вершин пікселя на площину текстури. Отриманий у результаті чотирикутник пропонується розглядати як апроксимацію істинної проекції пікселя на площину текстури. У загальному випадку апроксимована проекція пікселя (надалі по тексту просто проекція пікселя (ПП)) являє собою довільний чотирикутник. Знаходження його інтегрального кольору вимагає значних обчислювальних витрат, обумовлених знаходженням перетинання КК [6] підготовлених текстур із проекцією пікселя. З метою спрощення обчислення інтегрального кольору пропонується апроксимувати чотирикутник набором прямокутників - фрагментів, сторони яких паралельні осям системи координат текстури. Глибина дерева текстур в форматі [6] визначається необхідним рівнем збереження деталізації з урахуванням кутової роздільної здатності системи візуалізації. З метою скорочення об'ємів обчислення, необхідних для знаходження інтегрального кольору ПП при збереженні заданої похибки апроксимації проекції пікселя, доцільно обмежитись рівнем деталізації відповідно до заданого рівня похибки. Для цього запропоновано співвідношення для обчислення значення граничного рівня k проходу по дереву підготовлених текстур: , де - максимально допустима відносна похибка апроксимації проекції пікселя фрагментами, - площа проекції пікселя, - периметр проекції пікселя. Розрахунок граничного рівня проходу дозволяє суттєво скоротити об'єми обчислень при роботі з текстурами з високою роздільною здатністю.

Далі в розділі запропоновані методи швидких обчислень зваженого кольору фрагментів для випадків подання текстур у вигляді повного [2] і неповного [1] КД. Сума зважених кольорів таких фрагментів дозволяє розрахувати інтегральний колір проекції пікселя.

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

У четвертому розділі були наведені результати математичного моделювання. Відповідно до поставленого завдання обчислення у СВ запропоновано розподілити між універсальною ЕОМ і спеціалізованим обчислювачем. Інформація про сцену змінюється згідно з даними, що поступають ззовні. Синтез зображення СВ здійснюється для кожного кадру окремо. Це значить, що в певні моменти часу фіксується положення системи відображення, що повністю визначає (на даному кадрі) положення всіх векторів спостереження (ВС) щодо базової системи координат. Спецпроцесор (СП) векторів спостереження виробляє всі ВС, що відповідають поточному положенню системи спостереження. ВС подаються на входи всіх СП, кожен з яких провадить трасування променів для об'єктів сцени певного типу. Кожний з типів об'єктів має свої особливості, що дозволяють оптимізувати кожний із СП для максимально швидкого виконання візуалізації об'єктів цього типу з найменшими апаратними витратами. Кожний з СП виробляє дані, що характеризують перетин (перетини) ВС із об'єктами сцени. Такими даними можуть бути координати, нормаль до поверхні в даній точці перетину, індекс текстури, нанесеної на об'єкт, відбивна здатність, прозорість та ін. Ці дані надходять у СП нанесення текстур, де проводиться обчислення інтегрального кольору для всіх пікселів зображення. Для цього інформація для кожного пікселя від усіх СП поєднується. У СП нанесення текстур провадиться анізотропна фільтрація текстур запропонованими у роботі методами. На основі отриманої інформації про інтегральний колір кожного пікселя, а також даних освітленості, визначається колір пікселя. Далі розглянута структурна схема СП нанесення текстур та блоку текстурної пам'яті (рис. 2).

Рис. 2. Структурна схема СП нанесення текстур та блоку пам'яті

На вхід СП надходять координати точок перетину проекційних променів із об'єктами сцени та індекси текстур, що відповідають даним точкам перетину. СП нанесення текстур складається з таких блоків: 1) блок аналізу розташування КК відносно трикутника проекції пікселя - ANALIZE; 2) блока SPLITTER, який містить стек КК та виконує ділення КК на чотири дочірніх; 3) блока MEMORY, який реалізує функції зберігання кольорів КК у пам'яті та накопичення зваженого кольору трикутника проекції пікселя.

Обчислювач працює в такий спосіб: на першому (підготовчому) етапі відбувається ініціалізація пам'яті текстур, на другому етапі виконується пошук інтегрального кольору трикутників, на які розбивається проекція пікселя на площині текстури. При надходженні на вхід обчислювача даних про новий трикутник відбувається: обнуління акумулятора зваженого кольору в блоці MEMORY (рис. 2); ініціалізація блоку SPLITTER; завантаження в блок ANALIZE даних про трикутник. Кожна ітерація обчислювача містить такі дії: 1) блок SPLITTER витягає із стеку черговий поточний класифікаційний квадрат (ПКК), для якого необхідно обчислити ознаки розташування щодо трикутника; 2) блок ANALIZE аналізує ПКК і формує сигнали: divide і consider; 3) у випадку, якщо сигнал consider (ПКК знаходиться в середині трикутника); 4) у випадку, якщо сформовано divide (ПКК перетинає сторони трикутника), ПКК буде поміщений до стеку блоку SPLITTER для подальшої розбивки. У розділі приводиться докладний опис структурних схем кожного із блоків СП. Текстуру запропоновано зберігати в RAM-блоках текстур обчислювача. Якщо на виході блоку ANALIZE сигнал consider установлений в одиницю, це є ознакою того, що ПКК потрапив усередину трикутної області і його зважений колір буде врахований при розрахунку інтегрального кольору проекції пікселя. У розділі запропонований метод адресації КК текстури в пам'яті. Якщо є текстур, у кожній з яких рівнів, то для кодування адресу КК текстури буде потрібно біт. З них: старших біт - номер текстури, біт - адрес КК у текстурі. Адрес КК у текстурі має наступний формат:

, , ... , .

Тоді адрес КК для кожної текстури позначимо:,

де: - двійкове подання номера текстури, - номер рівня в текстурі.

У блоках RAM для зниження вартості СП нанесення текстур використовуються блоки DDR пам'яті. Такий тип пам'яті має латентність доступу приблизно 50 нс. У випадку, якщо блок Memory містить усього один блок RAM, інтерфейс до цього блоку буде обмежувати пропускну здатність усього блоку Memory. Тому запропоновано ввести декілька паралельно працюючих блоків RAM. У цьому випадку виникає завдання балансування навантаження між цими блоками. Таку задачу запропоновано вирішувати, використовуючи механізм хешування. Для цього запропоновано обчислювати два числа, адреса блоку RAM: ; адрес КК усередині блоку: , де:- кількість модулів RAM; - операція пошуку залишку від ділення; - операція ділення з відкиданням залишку. Такий метод адресації КК дозволяє підвищити продуктивність роботи СП за рахунок рівномірного розподілу вибірок з пам'яті між усіма блоками RAM.



ВИСНОВКИ

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

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

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

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

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

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

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

7. Практичне значення результатів дисертаційної роботи підтверджено актами впровадження у НЦУВКЗ м. Євпаторія (акт впровадження від 13.12.09) та каф. ЕОМ ХНУРЕ (акт впровадження від 05.12.10).



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

1. Гусятин В.М. Метод расчета цвета проекции пикселя в задачах нанесения текстур, представленных неполным кватернарным деревом / В.М. Гусятин, Я.В. Чаговец, Д.Г. Кожушко // Радіоелектронні і комп'ютерні системи. - Х.: “ХАІ”. -2008.- С. 59-62.

2. Гусятин В.М. Расчет взвешенного цвета проекции пикселя с проходом по полному кватернарному дереву текстур /В.М. Гусятин, Я.В. Чаговец, Д.Г. Кожушко // Информационные технологии и компьютерная инженерия. - Вінниця: ВНТУ. - 2008. - C. 57-60.

3. Гусятин В.М. Метод фильтрации текстур для синтеза изображений обратным трассированием лучей. Одномерный случай/ В.М. Гусятин, Я.В. Чаговец, Д.Г. Кожушко // Радиоэлектроника. Информатика. Управлениею. - Запорожье: ЗНТУ. - 2009. - C. 10-15.

4. Гусятин В.М. Метод быстрых вычислений для задачи анизотропной фильтрации при синтезе изображений обратным трассированием/ В.М. Гусятин, Я.В. Чаговец, Д.Г. Кожушко // Вимірювальна та обчислювальна техніка в технологічних процесах. - Хм.:ХНУ. - 2010. - №1. - С. 128-137.

5. Волк М.А. Оценка эффективности распараллеливания вычислительных задач в локальных компьютерных сетях / М.А. Волк, Д.Г. Кожушко // АСУ и приборы автоматики. - 2004. - № 127. - С. 149-154.

6. Гусятин В.М. Упаковка векторных текстур в задачах синтеза изображений для систем визуализации/ В.М. Гусятин, Я.В. Чаговец, Д.Г. Кожушко // Вісник НТУ "ХПІ" "Інформатика і моделювання". - 2005. - № 56. - С. 9-16.

7. Гусятин В.М. Устранение алиасинга при нанесении текстуры на 3D объекты в методе обратного трассирования/ В.М. Гусятин, Я.В. Чаговец, Д.Г. Кожушко // Вісник НТУ "ХПІ" "Інформатика і моделювання".-2007.-C.36-43.

8. Гусятин В.М. Метод анизотропной фильтрации текстур при синтезе изображений обратным трассированием / В.М. Гусятин, Я.В. Чаговец, Д.Г. Кожушко // Информатика, кибернетика и вычислительная техника (ИКВТ-2009). Выпуск 10 (153). - Донецк: ДонНТУ. - 2009. - C. 64-69.

9. Гусятин В.М. Метод устранения краевого алиасинга при синтезе изображений обратным трассированием / В.М. Гусятин, Я.В. Чаговец, Д.Г. Кожушко // Системи обробки інформації.- Х.: ХУПС. - 2010. - № 2(83). - С. 71-74.

10. Волк М.А. Оценка эффективности распараллеливания вычислительных задач в локальных компьютерных сетях / М.А. Волк, Д.Г. Кожушко // 8-й международный молодежный форум «Радиоэлектроника и молодежь в XXI веке». - Харьков, 2004. - С. 280.

11. Гусятин В.М. Метод нанесения текстур с одновременным устранением алиайзинга / В.М. Гусятин, Я.В. Чаговец, Д.Г. Кожушко // Проблеми інформатики і моделювання: Матеріали П'ятої міжнародної науково-технічної конференції. - Х.: НТУ “ХПІ”. - 2005. - С. 27.

12. Кожушко Д.Г. Форматы хранения векторных текстур для систем визуализации реального времени / Д.Г. Кожушко, Н.Е. Семикин // 8-й Международный молодежный форум «Радиоэлектроника и молодежь в XXI веке». - Харьков, 2006. - С. 262.

13. Гусятин В.М. Метод нанесения векторных и растровых текстур при синтезе изображения обратным трассированием лучей / В.М. Гусятин, Я.В. Чаговец, Д.Г. Кожушко // Проблеми інформатики і моделювання. Матеріали п'ятої міжнародної науково-технічної конференції. - Х.: НТУ “ХПІ”, 2007. - C. 24.

14. Гусятин В.М. Устранение эффекта краевого алиасинга при синтезе изображения методом обратного трассирования / В.М. Гусятин, Д.Г. Кожушко // 2-а Міжнародна наукова конференція «Сучасні інформаційні системи. Проблеми та тенденції розвитку»: Зб. матеріалів конференції - Х.: ХНУРЕ, 2007. - С. 497-498.

15. Гусятин В.М. Подход к фильтрации текстур в задачах синтеза изображений методом обратного трассирования лучей / В.М. Гусятин, Я.В. Чаговец, Д.Г. Кожушко // Материалы Восьмой международной научно-технической конференции "Проблемы информатики и моделирования". -Х: НТУ "ХПИ". - 2008. - C.33.

16. Гусятин В.М. Подход к выполнению быстрых вычислений для задач анизотропной фильтрации текстур при синтезе изображений методом обратного трассирования/ В.М. Гусятин, Я.В. Чаговец, Д.Г. Кожушко // Проблеми інформатики і моделювання. Матеріали Дев'ятої міжнародної науково-технічної конференції. Х.: НТУ “ХПІ”, 2009. - С.33.

17. Кожушко Д.Г. О фильтрации текстур для синтеза изображений обратным трассированием (одномерный случай) / Д.Г. Кожушко // 13-й Международный молодежный форум «Радиоэлектроника и молодежь в XXI веке»: Сб. материалов форума ч.2. - Харьков: ХНУРЭ, 2009. - С. 125.



АНОТАЦІЯ

Кожушко Дмитро Геннадійович. Методи та апаратні засоби нанесення текстур для синтезу зображень зворотним трасуванням у системах візуалізації. - Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.05 - комп'ютерні системи та компоненти. - Харківський національний університет радіоелектроніки, Харків, 2011.

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

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

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

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

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

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



АННОТАЦИЯ

Кожушко Дмитрий Геннадиевич. Методы и аппаратные средства нанесения текстур для синтеза изображений обратным трассированием в системах визуализации. - Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.05 - компьютерные системы и компоненты. - Харьковский национальный университет радиоэлектроники, Харьков, 2011.

Диссертация посвящена вопросам разработки методов и аппаратных средств нанесения текстур для синтеза изображений обратным трассированием в системах визуализации реального времени.

В работе впервые предложен метод анизотропной фильтрации в плоскости текстуры для задач синтеза изображений обратным трассированием. Метод предполагает выполнение анизотропной фильтрации в плоскости текстуры при нанесении ее на поверхность трехмерного объекта. Такой метод позволяет увеличить производительность синтеза изображений методом обратного трассирования. Показано, что предложенный метод анизотропной фильтрации в плоскости текстур применим для различных форм фильтров. Результаты моделирования в одномерном и двумерном случае показали эффективность предложенного метода для устранения алиасинга.

Проведена классификация исходных изображений текстур. Впервые предложены методы упаковки векторных текстур простых неравномерных и текстур с произвольными линиями раздела. Текстуры, упакованные согласно предложенным методам: обеспечивают компактность представления в памяти; сохраняют такое достоинство векторного представления, как высокое разрешение; позволяют быстро отображать текстуры без перевода их в растровую форму с одновременным устранением алиасинга; применение композиционных текстур позволяет гибко комбинировать векторные и растровые текстуры.

Предложен метод быстрых вычислений взвешенного цвета проекции пикселя для задач анизотропной фильтрации текстур. Данный метод предполагает выполнение в препроцессорном времени значительного количества сложных вычислений взвешенного на соответствующую функцию цвета. Вычисление взвешенного цвета проекции пикселя согласно предложенному методу выполняется с проходом по дереву упакованных текстур без распаковки в растровую форму. Метод позволяет уменьшить вычислительные затраты при нанесении текстур с одновременным устранением алиасинга.

Получил дальнейшее развитие метод адаптивного трассирования лучей для задач устранения краевого алиасинга для синтеза изображений методом обратного трассирования. Такой метод, в отличие от известных, использует предложенный критерий выбора количества уровней разбиения, который учитывает параметры системы отображения и угловое разрешение глаза человека.

Разработанные модели были математически промоделированы. Моделирование подтвердило, что разработанные методы отвечают поставленным требованиям и являются корректными.

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

Ключевые слова: текстура, алиасинг, метод обратного трассирования, система визуализации, угловая погрешность, реальное время, классификационный квадрат.

ABSTRACT

Kozhushko Dmitro Gennadievich. Methods and application-specific processors of texture mapping for image synthesis using ray-tracing in visualization systems. - Manuscript.

Thesis for a candidate degree of technical sciences on a speciality 05.13.05 - computer systems and components. Kharkiv national university of radio electronics, Kharkiv, 2011.

The thesis is devoted to developing methods and application-specific processors for texture mapping in image synthesis tasks using ray-tracing in real-time visualization systems.

In the thesis method of anisotropic texture filtering is proposed for image synthesis tasks using ray-tracing. The method involves performing anisotropic filtering in the texture plane.

In the thesis compression methods for simple uneven vector textures and vector textures with arbitrary boundary lines are proposed. The main feature of the methods is that the vector input data are converted to a form of tree structure and focused on the proposed method of anisotropic texture filtering.

Thesis suggests a method of rapid calculation of weighted color of pixel projection for anisotropic texture filtering tasks. According to the method the large number of complex calculations of the color weighted to the corresponding function is performed in preprocessor time.

Adaptive ray-tracing method is received further development for the edge anti-aliasing tasks. Introduced the choice criterion for number of partitioning levels.

Keywords: texture, aliasing, ray-tracing, visualization system, angular resolution, real time, classification square.

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

...