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

Чаговець Ярослав Васильович

УДК 681.323

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

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

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

кандидата технічних наук

Харків – 2002

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

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

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

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

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

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

Офіційні опоненти:

- доктор технічних наук, професор Аліпов Микола Васильович, Харківський національний університет радіоелектроніки,

професор кафедри проектування та експлуатації електронних апаратів;

-

Харківський військовий університет, професор кафедри систем управління

і зв’язку

Провідна установа

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

Захист відбудеться “  ” червня 2002 р. о 15:00 годині на засіданні спеціалізованої вченої ради Д .052.01 у Харківському національному університеті радіоелектроніки за адресою: 61166, м. Харків, пр. Леніна, 14, тел.: (0572) 40-94-51.

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

Автореферат розісланий “ 17 ” травня 2002 р.

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

спеціалізованої ради В. І. Саєнко

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

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

Роботи в галузі розробки наукових основ створення СВ мають для України велике значення: створення нових СВ дозволить модернізувати парк тренажерів, підвищити якість підготовки операторів ТЗ, уникнути ризику при відпрацюванні позаштатних ситуацій, знизити витрати пального. Внесок в галузь створення СВ зробили такі вчені як AkeleyFuchsHodgesFeinerІванов В.П., Ковальов А.М., Бабенко В.С., Белецький А.Я., Іванченко А.Т, Башков Е.А., Коба Ю.А., Зорі С.А., Гусятін В.М. та ін. Вимоги до СВ тренажерів: висока частота генерування зображення, мала затримка від моменту надходження керуючої дії до адекватної зміни зображення, висока реалістичність синтезованого зображення, можливість відображати сцену великого обсягу і детальності. За будь-якого рівня розвитку універсальної техніки наявність апаратного прискорення (на відміну від суто програмної реалізації) дозволяє більш повно задовольнити ці вимоги. Для цього необхідно створення спецпроцесорів (СП), орієнтованих на вирішення конкретної задачі формування зображення.

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

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

Зв’язок роботи з науковими програмами, планами, темами. Дисертаційна робота написана на базі низки НДР, в яких автор був виконавцем. Серед них держбюджетна тема Харківського національного університету радіоелектроніки №410 “Розробка теоретичних основ та нових архітектурних принципів створення тренажерних систем різного призначення” (№ДР 0197U004440). В рамках цієї теми автором розроблена математична модель поверхні рельєфу для застосування в цифрових системах візуалізації. За замовленням Українського державного учбово-сертифікаційного центру цивільної авіації (УД УСЦ ЦА, м. Київ) було проведено НДР “Модернізація цифрової системи візуалізації”, де було відпрацьовано приймання даних від моделюючої машини тренажера, їхня корекція, вилучення імпульсних завад, згладжування. У рамках НДР “Графіка-М” і “Модернізація-Т”, що були проведені в науковому центрі Харківського інституту військово-повітряних сил (ХІ ВПС), були розроблені методи обробки вхідних даних, що надходять у СВ від аналогової моделюючої машини.

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

Для досягнення цієї мети необхідно вирішити задачі:

1.

2.

3.

4.

5.

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

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

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

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

-

-

-

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

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

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

- дістав подальшого розвитку спосіб обробки вхідних даних, які надходять від моделюючої машини, що дозволяє покращити якість зображення шляхом вилучення імпульсних завад та зниження впливу шуму на вхідний сигнал. Основні результати дисертаційної роботи впроваджені при модернізації систем візуалізації авіаційних тренажерів: Тл-39 в ХІ ВПС (акт впровадження від 15.05.2001 р.) та ТУ-154М в УД УСЦ ЦА (акт впровадження від 07.02.2001 р.)

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

Апробація результатів дисертації. Результати досліджень оприлюднені: на 1_му Міжнародному молодіжному форумі “Електроніка та молодь у XXI столітті”, Харків, ХТУРЕ, 1997 р.; на 3-му Міжнародному молодіжному форумі “Радіоелектроніка та молодь у XXI столітті”, Харків, ХТУРЕ, 1999 р.; на 5-й і 7-й Міжнародній конференції “Теорія і техніка передачі, прийому й обробки інформації” (“Телекомунікації. Радіотехніка. Електроніка”), Харків, ХТУРЕ, 1999 і 2001 р.

Публікації. За темою дисертації видано 11 друкованих робіт: 6 статей в збірниках наукових праць, які увійшли до переліку ВАК України, 2 патенти, 2 матеріали конференції, 1 теза доповіді.

Структура та обсяг роботи. Дисертація складається з вступу, п’яти розділів, висновків, списку літератури, що містить 95 найменувань, шістьох додатків. Робота містить 46 ілюстрацій, 10 таблиць. Загальний обсяг роботи складає 211 сторінки, у тому числі 142 сторінки основного тексту.

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

У вступі обґрунтовується актуальність теми досліджень, наводяться мета, наукова новизна та практичне значення роботи.

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

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

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

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

, ()

де змінні x,y,z декартові координати точки поверхні.

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

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

Функція наближення () повинна інтерполювати множину висот, заданих цифровою картою. Згідно з цим вхідними даними інтерполяції є матриця висот Y={yij}. Елементи цієї матриці – висоти – одержують як значення функції рельєфу при x=i, z=j:

,

де i,j – цілі числа. Це означає, що сітка, у вузлах якої задаються висоти в Y, має одиничний крок. Випадки, коли сітка має крок, відмінний від одиниці, можуть бути отримані масштабуванням координат x та z.

У роботах [4,6] розглянуто гладке подання рельєфу, для чого запропоновано використовувати фінітні функції. Згідно з цим підходом пропонується шукати y(x,z) у вигляді лінійної комбінації функцій, отриманих зсувом деякої базисної фінітної функції f(x,z):

. ()

Той факт, що ваговими коефіцієнтами є висоти yij, дозволяє вести інтерполяцію безпосередньо по вихідним даним, без попередньої підготовки. Внаслідок цього можливо змінювати форму рельєфу в реальному масштабі часу. Функцію f(x,z) будемо представляти у вигляді добутку двох одномірних фінітних функцій однієї змінної: f(x,z)=f(x)f(z). Фінітність функції f(x,z) дозволяє зменшити кількість доданків у (). У y(x,z) вносять свій внесок лише функції , які не дорівнюють нулю в точці (x,z), тобто розташовані поблизу (x,z). Пари (i,j) індексів таких функцій належать множині , де . Залишимо під знаком підсумовування в () тільки ненульові доданки, таким чином зменшивши кількість дій, необхідних для обчислення :

. ()

Далі виконується порівняльний аналіз інтерполяційних властивостей різних базисних функцій. З цією метою вихідна поверхня рельєфу була задана деякою аналітичною функцією, по якій отримані відрахунки, що утворюють матрицю висот Y={yij}. Ця матриця використовувалася в якості початкових даних для інтерполяції. Розглянуто такі базисні фінітні функції: функція “сходинка” (кусково-постійна інтерполяція); функція “кришка” (білінійна інтерполяція); функції Куранта (кусково-площинна інтерполяція, тріангуляція); функції з обмеженнями на похідні; функції на основі B_сплайнів 2-го і 3-го ступенів; а також функція Найквиста-Котельникова. Серед розглянутих видів інтерполяцій кусково-постійна має найнижчу реалістичність через наявність розривів. Злами на стиках комірок при білінійній інтерполяції в ряді випадків негативно впливають на реалістичність. Однак у будь-якому випадку вона вище, ніж при тріангуляції, де злами присутні усередині комірок і наявні плоскі ділянки. Для того, щоб уникнути зламів при інтерполяції, було запропоновано накласти такі обмеження на базисну функцію:

, ()  –

властивість парності, ()  –

властивість фінітності, ()

, ()

. ()

Прикладом функції, що задовольняє (-), є

()

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

Рис.. Приклади інтерполяції фінітними функціями:

а) функція класу (-);

б) функція на основі B-сплайну 2-го ступеня.

Для зменшення перекручувань типу “тераси” пропонується [6] два варіанти “деформації” фінітних функцій класу (-). Перший варіант полягає в розширенні носія вихідної базисної функції:

.

Відповідно до другого варіанта деформована фінітна функція визначається як зважене середнє значення деяких двох фінітних функцій, одна з яких (f1(t)) належить класу (-), а інша (f2(t)) не має перекручувань типу “тераси”:

,

де a – ваговий коефіцієнт.

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

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

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

У випадку білінійної інтерполяції вираз () перетворимо до вигляду

, ()

де , , , , ,  – координати лівого нижнього кута комірки, що містить точку (x,z);  – координати точки (x,z) усередині комірки: , , , .

Розглянуто два способи обчислення (), що становлять найбільший інтерес. Перший спосіб вимагає 6 операцій додавання і 3 операції множення. При другому способі обчислення (яке зводиться до 4 операцій додавання) виконується один раз для всієї комірки. Для кожної точки усередині цієї комірки обчислюється тільки , що вимагає 3 операції додавання і 3 множення.

У випадку використання базисної функції на основі В-сплайну 2-го ступеня вираз () зводиться до вигляду, аналогічному () і розглядаються два способи обчислення отриманого виразу, аналогічні розглянутим вище для білінійної інтерполяції. При першому способі кількість елементарних додавань складає 24, множень – 8. При другому способі обчислення, яке зводиться до 24 операцій додавання, виконується один раз для всієї комірки. Для кожної точки усередині цієї комірки обчислюється тільки вираз, який вимагає 8 операцій додавання і 8 множення. Однак при будь-якому способі кількість обчислювальномістких операцій множення більш ніж у 2 рази перевищує кількість відповідних операцій для білінійної інтерполяції.

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

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

Досліджено питання погрішностей інтерполяції. Тому що вихідна функція рельєфу в загальному випадку недоступна, в якості еталонної взята кусково-площинна функція наближення. Показано, що білінійна функція наближення знаходиться в 2 рази ближче до кусково-площинної функції наближення, ніж кусково-площинна функція наближення до свого альтернативного варіанта (в якості міри близькості використовувалися C- і L1- метрики). Це говорить про те, що білінійна інтерполяція добре наближає функцію рельєфу.

У третьому розділі проведена оцінка та оптимізація алгоритмів сканування поверхні рельєфу. Продуктивність спецпроцесора формування зображення рельєфу прямо залежить від ефективності використовуваного алгоритму сканування, тому вибір останнього є важливою задачею при побудові СВ. У даному розділі здійснюється оцінка продуктивності трьох алгоритмів сканування і пропонується четвертий – оптимізований алгоритм, що характеризується підвищеною продуктивністю. Ефективність алгоритмів оцінюється двома параметрами: кількістю операцій обчислення перетинань і кількістю операцій обчислення координат комірок сцени. Під операцією обчислення перетинання розуміємо обчислення точки P перетинання проекційного променя (ПП) R з поверхнею S. Тут  – ознака перетинання: =1, якщо R перетинає S; =0 у противному разі.

Першим розглядається алгоритм, названий силовим (СА). Він припускає перевірку кожного ПП із всіма комірками. Алгоритм, названий модифікованим силовим (МСА), припускає перевірку кожного ПП тільки з тими комірками, через які проходить проекція ПП на площину XZ, у результаті чого зменшується . У так званому -алгоритмі використовується концепція -зрізів. Для кожного ПП із направляючим одиничним вектором можна обчислити кути ,  – координати в сферичній системі (, ). Далі будемо позначати також . Розіб'ємо всю множину ПП на підмножини R(i) (називані -зрізами), утворені проекційними променями, для параметра яких виконується нерівність . Тут

()

де  – кількість -зрізів, .

Проекції всіх ПП однієї підмножини є близькими один до одного. Далі замінимо кожен ПП , що входить до R(i), на близький з ним за напрямом ПП з кутовим параметром (параметри обох променів збігаються). Це дозволить обчислювати координати комірок, що перетинаються, один раз для всієї цієї підмножини ПП, а не для кожного ПП. У результаті кількість операцій NK скорочується. Показано, що корекція напрямків ПП не чинить негативного впливу на синтезоване зображення, що підтверджується також результатами моделювання.

Як результат наведених вище досліджень запропонований -оптимізований алгоритм. Він вимагає меншого числа операцій перетинання в порівнянні з _алгоритмом за рахунок виключення зайвих операцій. Для виявлення операцій, що є зайвими, розглянемо операції обчислення перетинань, виконувані для променів окремого -зрізу. Позначимо через j=1,2,3,…номер комірки в послідовності перетинаємих даним -зрізом комірок (комірка з номером j=1 містить центр проекцій), а через  – поверхню в межах j-ї комірки. Усі промені (i=1,2,3,…) -зрізу упорядкуємо за зростанням параметра , тобто таким чином, щоб виконувалися умови Далі з метою спрощення штрих у позначенні скоректованого променя випускається. Введемо матрицю перетинань , де  ознака перетинання променя Ri з поверхнею Sj. Побудова таких матриць дозволяє наочно представити роботу алгоритму.

Доведено два твердження. Відповідно до першого твердження можна не виконувати операції перетинань для ПП, якщо він уже має перетинання. Відповідно до другого твердження, якщо промінь Ri не перетнувся у даній комірці (а також у жодній з попередніх комірок), то виключаються операції перетинання з даною коміркою всіх променів Rm, де m>i. На базі розглянутих тверджень запропонований -оптимізований алгоритм [5]. На рис.2 проілюстровано його роботу. Перевагою розробленого алгоритму є те, що він застосовний для сканування криволінійних поверхонь, у тому числі всіх типів інтерполяції, розглянутих у другому розділі.

Рис.. Ілюстрація роботи -оптимізованого алгоритму. Матриця для кроків 2-5. Прочерком позначені елементи ij, які відповідають операціям F(Ri,Sj), що виключаються. Знаком “x” позначені елементи, значення яких не відоме

Кількість операцій NF і NK для розглянутих алгоритмів наведена в табл.. Прийнято такі позначення:  – кількість пікселів в екрані;  – кількість комірок, через які проходить проекція ПП на базову площину. З таблиці видно, що

Таблиця

Порівняння алгоритмів за кількістю операцій

Алгоритм | Кількість операцій

Загальний вигляд | Для даних з прикладу

СА | 0 | 0

МСА | 491 520 000 | 491 520 000

-алгор. | 491 520 000 | 8 388 608

-ОА | 8 860 416 | 8 388 608

Примітка. Приклад наведений для випадку: , , .

зі зростанням NП виграш -оптимізованого алгоритму за кількістю NF операцій перетинання збільшується.

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

Четвертий розділ присвячений вирішенню таких задач: обчислення векторів спостереження (ВС), упорядкування ВС за параметрами і , оптимізація параметрів сканування.

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

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

Впорядкування ВС виконується в три етапи: перетворення системи координат векторів, розбивка множини ВС на -зрізи, упорядкування кожного -зрізу за параметром ?. На етапі перетворення системи координат по декартових координатах ВС обчислюються його кутові координати ?, в. Для рішення задачі розбивки множини ВС на -зрізи розглянуті такі варіанти структур даних і алгоритмів роботи з ними. Варіант : одна таблиця виду , де  – координати піксела, що відповідає ВС, D – додаткові дані. Тут і далі в позначенні BC мається на увазі, що дана структура даних адресується словом у форматі B, а C – формат її вихідного слова. Недоліком цього варіанта є занадто великий об'єм пам'яті, необхідність її ініціалізації перед наступним етапом і, як наслідок, великий термін роботи алгоритму. Варіант 2: Для кожного -зрізу промені організовані в список. При цьому обсяг пам'яті істотно менше варіанта . Фізична реалізація даної структури може бути виконана на основі двох таблиць: (містяться адреси початку списків), (містяться елементи списків). Поле A=(yэ,zэ) (адреса) у кожній з комірок таблиці потрібне для зазначення наступного елемента в списку. Останній елемент списку містить у цьому полі спеціальне значення NULL. Розбивка на -зрізи виконується в такому порядку: визначається номер -зрізу для ВС із даним параметром :

, ()

потім ВС розміщується в i-му -зрізі (тобто дописується в початок i-го списку).

Для упорядкування кожного -зрізу за параметром ? використовується алгоритм, що є варіантом сортування підрахунком. Алгоритм використовує дві таблиці: , . Адреса N у T4 є порядковим номером променя в упорядкованій множині променів даного -зрізу. Алгоритм функціонує в такий спосіб. З таблиці вибираються дані чергового ВС даного -зрізу. Потім координати ВС записуються в за адресою

, ()

де N – кількість індексів у таблиці T3.

Після цього дані про ВС переписуються в без пропусків. Цінністю алгоритму є лінійна залежність терміну роботи від N і кількості променів у -зрізі.

Розроблено метод оптимізації параметрів сканування [3], що полягає в узгодженні параметрів N, N сканування з параметрами системи відображення. Завдяки оптимізації відбувається збільшення продуктивності СВ і зменшення необхідних об'ємів пам'яті при одночасній відсутності “випадань” пікселів. Показано, що ефект втрати пікселів відсутній при виконанні умови

, ()

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

1)

2)

Розроблено методику розрахунку параметрів сканування, яка дозволяє для заданої системи відображення обчислити набір “оптимальних” параметрів . Наприклад, для (де і  – кількість пікселів по горизонталі і вертикалі;  – відношення вертикального розміру піксела до його горизонтального розміру,  – горизонтальний кут огляду), використовуючи методику оптимізації параметрів сканування, ми одержимо три альтернативних варіанти вибору параметрів сканування: (); (); (). Вибір конкретного варіанта визначається вимогами проекту.

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

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

Описується структура СВ у цілому. Обчислення у СВ пропонується розподілити між ЕОМ загального призначення і спеціалізованою ЕОМ (спецобчислювачем), як показано на рис..

Рис.. Структура системи візуалізації

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

Рис..Спецобчислювач СВ

Описується структура і принцип роботи підсистеми формування зображення рельєфу (рис.), що включає в себе СП генерування ВС і СП поверхні рельєфу. Для компактного збереження текстурних даних великих просторів рельєфу в блоці накладення текстур може застосовуватися технологія розпакування графічної інформації [8]. Для забезпечення безупинного відображення крапкових світних об'єктів блок накладення текстур може реалізувати алгоритм, заснований на використанні так званої зони охоплення [2,7].

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

Рис.. Структура підсистеми формування зображення рельєфу

Далі описані функціональні схеми блоків, що входять у підсистему формування зображення рельєфу. Схеми, що розроблені, є апаратною реалізацією алгоритмів, запропонованих у попередніх розділах. З метою досягнення високої продуктивності спецобчислювача для його синтезу використаний паралельно-конвеєрний принцип. Для більшої наочності робота деяких блоків проілюстрована часовими діаграмами. В обчислювачі ВС в якості базового блока використовується накопичувальний підсумовувач. Цінністю схеми є безперервність генерування ВС і мала кількість керуючих входів. Блок перетворення координат використовує таблично-алгоритмічний метод обчислення. Задачами блока сортування променів (БСП) є: поділ множини ПП на -зрізи і сортування ПП усередині кожного -зрізу в порядку зростання параметра . Відповідно до цього БСП складається з двох блоків: формувача -списків і блока упорядкування ВС за параметром . До складу формувача -списків входять таблиці T1 (реалізується як двохпортова статична пам'ять) і T2 (однопортова статична пам'ять). Розглядаються два варіанти формату подання координат піксела: з окремими полями й упакований. Наводяться аналітичні і чисельні залежності об'ємів пам'яті таблиць T1 і T2 від параметрів сканування і відображення. Наприклад, для параметрів , , , , N=214, N=213 об'єм таблиць при використанні упакованого формату буде становити 38K і 2048K для T1 і T2 відповідно. Схема блока упорядкування ВС за параметром складається зі схем ініціалізації T3, заповнення T3, заповнення T4. Описано принцип роботи схем і наводяться відповідні часові діаграми.

Призначення обчислювача перетинань – пошук точок перетинання променів -зрізу з поверхнею рельєфу. Обчислювач будується на основі -оптимізованого алгоритму сканування. Операція F обчислення перетинання виконується ітераційним алгоритмом (ІТА), що описаний у літературі, який з метою врахування особливостей моделі рельєфу модифікований, а саме: в якості кінцевих точок відрізка, на якому здійснюється пошук точки перетинання, пропонується брати точки, проекції яких лежать на границях комірки. Обчислення координат XKj і ZKj чергової точки здійснюється обчислювачем за допомогою алгоритму обчислення координат комірок сцени. З метою апаратної реалізації ітераційного алгоритму співвідношення приводяться до відповідного вигляду. Обґрунтовується збіжність ітераційного процесу для умов, прийнятих у якості початкових.

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

Розглядається питання суміщення ітерацій при апаратній реалізації алгоритму сканування. Суміщення досягається за рахунок конвеєризації. Принцип роботи конвеєрного обчислювача перетинань розглянуто на конкретному прикладі. Наведено вираз кількості тактів, необхідних для обчислення як окремого -зрізу, так і всього кадру. У прикладі, що наводиться, суміщення операцій привело до зменшення в 6,6 разів часу обчислення кадру. Крім того, суміщення операцій можливе шляхом збільшення кількості одночасно працюючих обчислювачів _зрізів. Для розглянутого приклада час обчислення кадру, який дорівнює 1/30 с, досягається вже при використанні чотирьох обчислювачів -зрізів.

Для роботи ІТА потрібно на кожнім кроці обчислювати висоту поверхні згідно з (). Розроблено обчислювачі висоти поверхні рельєфу для інтерполяції такими фінітними функціями: функцією “кришка”, функцією на основі B-сплайну 2 ступеня та функціями виду (,). Для зазначених випадків інтерполяції розроблені обчислювачі нормалі до поверхні рельєфу. Обчислювач координат комірок сцени будується на основі алгоритму, розглянутого в третьому розділі.

Для перевірки правильності розроблених структурних і функціональних схем блоків спецпроцесорів проведене моделювання окремих блоків СП з використанням мови VHDL у середовищі Active HDL 4.1. Моделювання підтвердило працездатність розроблених схем.

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

ВИСНОВКИ

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

1.

2.

3.

4.

5.

6.

7.

8.

9.

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

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

11.

АНОТАЦІЯ

Чаговець Ярослав Васильович. “Моделі, алгоритми та структури спецпроцесорів для формування зображень рельєфу в системах візуалізації реального часу”. – Рукопис.

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

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

Ключові слова: рельєф, реальний час, зворотне