|
Харківський національний університет радіоелектроніки
Філімончук Михайло Анатолійович
УДК 681.323
МОДЕЛІ, АЛГОРИТМИ ТА СТРУКТУРИ СПЕЦПРОЦЕСОРІВ ФОРМУВАННЯ ЗОБРАЖЕНЬ ОБ’ЄКТІВ, ЩО РУХАЮТЬСЯ, В СИСТЕМАХ ВІЗУАЛІЗАЦІЇ РЕАЛЬНОГО ЧАСУ
05.13.13 – обчислювальні машини, системи та мережі
Автореферат
дисертації на здобуття наукового ступеня
кандидата технічних наук
Харків – 2004
Дисертацією є рукопис.
Робота виконана в Харківському національному університеті радіоелектроніки Міністерства освіти і науки України.
Науковий керівник кандидат технічних наук, доцент
Гусятін Володимир Михайлович,
Харківський національний університет радіоелектроніки,
професор кафедри електронних обчислювальних машин.
Офіційні опоненти:
– доктор технічних наук, професор Хаханов Володимир Іванович,
Харківський національний університет радіоелектроніки,
декан факультету комп'ютерної інженерії та управління;
– кандидат технічних наук, доцент Ситнік Борис Тимофійович,
Українська державна академія залізничного транспорту,
доцент кафедри автоматики і комп’ютерних систем управління.
Провідна установа
Національний технічний університет України “КПІ”, кафедра спеціалізованих комп’ютерних систем, Міністерство освіти і науки України, м. Київ.
Захист відбудеться “_12_”_липня_______ 2004 р. о __14___ годині на засіданні спеціалізованої вченої ради Д 64.052.01 у Харківському національному університеті радіоелектроніки за адресою: 61166, м. Харків, пр. Леніна, 14.
З дисертацією можна ознайомитись у бібліотеці Харківського національного університету радіоелектроніки за адресою: 61166, м. Харків, пр. Леніна, 14.
Автореферат розісланий “_9__”___червня____ 2004 р.
Вчений секретар
спеціалізованої вченої ради В.М. Левикін
ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ
Актуальність теми. Одним із самих значних напрямків обчислювальної техніки є комп'ютерна графіка. Висока інформативність комп'ютерної графіки призвела до її широкого використання в таких галузях діяльності людини як освіта, наука, техніка, медицина, комерція, реклама і т.д. Дуже швидко розвивається такий напрямок комп'ютерного синтезу зображень, як тривимірна комп'ютерна графіка реального часу, досягнення якої широко використовуються при побудові систем візуалізації (СВ) тренажерів транспортних засобів, виробництві реклами і кіно, написанні комп'ютерних ігор і ін.
Роботи в області розробки наукових основ створення систем візуалізації мають для України велике значення: нові СВ дозволять модернізувати парк тренажерів, підвищити якість підготовки операторів транспортних засобів, уникнути ризику при відпрацьовуванні позаштатних ситуацій, знизити витрату пального. Внесок в створення СВ внесли такі вчені, як Foley J.D., Akeley K., Fuchs H., Hodges L., Feiner S., Іванов В.П., Ковальов А.М., Бабенко В.С., Бєлецький А.Я., Коба Ю.А., Іванченко А.Т, Башков Е.А., Гусятін В.М. та ін.
Особливості побудови систем візуалізації тренажерів полягають у виконанні комплексу вимог: висока частота генерації зображення, мала затримка часу від моменту надходження керуючого впливу до адекватної зміни зображення, висока реалістичність синтезованого зображення, можливість відображати сцену великого обсягу і детальності. При будь-якому рівні розвитку універсальної техніки наявність апаратного прискорення дозволяє більш повно задовольнити цим вимогам. Для цього необхідно створення спецпроцесорів, орієнтованих на вирішення конкретної задачі формування зображення в реальному часі.
Для систем візуалізації будь-яких тренажерів транспортних засобів, особливо авіаційних, важливою задачею є відображення об'єктів, що рухаються, (відображення нерухомих об'єктів – особистий випадок відображення об'єктів, що рухаються,). Вимоги до спецпроцесорів для формування зображень об'єктів, що рухаються, (ОР) містять у собі високореалістичне відображення складних форм, які займають малий простір. Суміщення цих вимог потребує вирішення ряду наукових задач.
Існує два основних методи формування зображення в системах візуалізації: прямого і зворотного трасування. Метод прямого трасування добре пророблений, однак єдиним типом графічних примітивів, що можуть відображатися з його використанням, є трикутники, що приводить до низької реалістичності зображення і зросту бази даних опису сцени. Метод зворотного трасування дозволяє підвищити ступінь реалістичності, тому що поряд з трикутниками в ролі графічних примітивів можуть бути використані криволінійні поверхні. Однак більшість існуючих реалізацій алгоритмів, що працюють методом зворотного трасування, має низьку продуктивність і не працює в реальному часі. Отже, створення й удосконалювання моделей і алгоритмів, орієнтованих на метод зворотного трасування, для побудови спецпроцесорів формування зображень об'єктів, що рухаються, у СВ реального часу, є актуальною науковою задачею.
Зв’язок роботи з науковими програмами, планами, темами. Дисертаційна робота написана на базі ряду НДР, у яких автор брав безпосередню участь у якості виконавця. Серед них держбюджетна тема Харківського національного університету радіоелектроніки № 410 "Розробка теоретичних основ і нових архітектурних принципів побудови тренажерних систем різного призначення" (№ ГР 0198U004440). У рамках цієї теми автором розроблена математична модель геометричного опису поверхні об'єкта, що рухається, для застосування в цифрових системах візуалізації.
Мета і задачі дослідження. Мета роботи – розробка моделей, алгоритмів і структур спецпроцесорів формування зображень об'єктів, що рухаються, які мають підвищену продуктивність і синтезують зображення з високим ступенем реалістичності. Для досягнення цієї мети необхідно вирішити такі задачі:
1. Розробка моделі геометричного опису об'єктів, що рухаються, орієнтованої на метод зворотного трасування, для використання в системах візуалізації.
2. Розробка алгоритмів роботи спецпроцесорів, орієнтованих на метод зворотного трасування, що працюють у реальному часі.
3. Перевірка отриманих моделей і алгоритмів шляхом їх математичного й імітаційного моделювання.
4. Розробка структурних і функціональних схем спецпроцесорів.
Об'єкт дослідження – існуючі методи і засоби синтезу зображень у системах візуалізації тренажерів транспортних засобів.
Предмет дослідження – моделі, алгоритми і структури спецпроцесорів формування методом зворотного трасування зображень об'єктів, що рухаються, у системах візуалізації реального часу.
Методи дослідження. При проведенні досліджень застосовувалися методи аналітичної геометрії, матричної алгебри, математичний апарат алгебри логіки. При розробці структури спецпроцесора були застосовані методи аналізу і синтезу. Для перевірки працездатності запропонованих алгоритмів, а також для з'ясування їхніх характеристик, були використані методи математичного моделювання. Працездатність окремих блоків спецпроцесора підтверджена за допомогою імітаційного моделювання.
Наукова новизна результатів дисертаційної роботи. При вирішенні основних задач дисертаційної роботи автором були отримані наступні наукові результати:
1. Дістала подальший розвиток математична модель геометричного опису поверхні об'єкта на основі аналітичних моделей для використання в цифрових системах візуалізації, орієнтована на метод зворотного трасування. Розвиток аналітичної моделі полягає в додаванні до опису кожного графічного примітива параметрів його системи координат та додаванні до опису об’єкта матриці зв’язності, яка дозволяє компактно представляти складні поверхні на основі базових графічних примітивів. Використання аналітичної моделі дозволяє, на відміну від тріангуляційних методів, задовольнити ознаці гладкості, збільшити реалістичність зображення; база даних моделі має компактне представлення, що підвищує швидкість обробки сцен, що містять велику кількість об'єктів.
2. Вперше запропоновано метод класифікаційного опису об'єктів, що рухаються. Метод класифікаційного опису базується на обмеженні простору, який займає об’єкт, оболонкою, та розподіленні простору усередині оболонки на домени, для яких сформовано список графічних примітивів об’єкта. Використання методу класифікаційного опису дозволяє шляхом виконання частини обчислень по синтезу зображення на етапі підготовки бази даних об'єктів скоротити загальну кількість обчислень у реальному часі, що дає можливість збільшити продуктивність СВ.
3. Дістав подальший розвиток алгоритм сканування для поверхні рельєфу. Розвиток алгоритму сканування полягає в адаптуванні його для сканування об’єктів, що рухаються, в просторі тривимірної сцени. Адаптований алгоритм сканування дозволяє виділяти з всіх об'єктів сцени, що рухаються, лише ті з них, оболонки яких проектуються на екран; це дозволяє підвищити ефективність синтезу зображення об'єктів за рахунок скорочення кількості складних обчислень і зменшення кількості звертань до пам'яті.
Практичне значення одержаних результатів. Розроблено алгоритм автоматичного складання класифікаційного опису об’єктів, що рухаються, алгоритми сканування простору тривимірної сцени, алгоритм синтезу зображення об'єктів, що рухаються. На базі цих алгоритмів розроблені структурні і функціональні схеми спецпроцесорів формування зображень ОР. На їхній основі можливо побудувати систему візуалізації реального часу, що синтезує реалістичне тривимірне зображення об'єктів, що рухаються. Завдяки високій реалістичності синтезованого зображення, використання такої СВ у тренажерах підвищить рівень підготовки операторів транспортних засобів.
Наукові результати, отримані в ході виконання даної дисертаційної роботи, були використані при модернізації системи візуалізації позакабінного простору в авіаційному тренажері КТС ТУ-154М (довідка про впровадження від 12.06.03), який встановлений в Українському державному навчально-сертифікаційному центрі громадянської авіації (м. Київ). Це дозволило значно підвищити ефективність навчального процесу та якість підготовки пілотів. Також результати виконання дисертаційної роботи впроваджені у навчальний процес на кафедрі електронних обчислювальних машин ХНУРЕ в курсі "Проектування спецпроцесорів" і дипломному проектуванні (акт впровадження від 10.11.02).
Особистий внесок здобувача. Особистий внесок здобувача в роботах, виконаних у співавторстві, полягає в наступному: в роботі [1] запропоновано класифікаційний опис об’єктів, що рухаються, та розроблено алгоритм його автоматичного складання; в роботах [2, 3] запропоновано алгоритми сканування простору сцени; в роботі [4] запропоновано спосіб використання ортогонального класифікаційного опису; в роботах [5, 6] розроблені структурні схеми обчислювальних пристроїв генерації векторів спостерігання; в роботі [7] запропоновано алгоритм синтезу зображення об'єктів, що рухаються, з використанням методу класифікаційного опису; в роботі [8] удосконалено класифікаційний опис об’єктів, що рухаються; в роботі [9] запропоновано модель геометричного опису об’єктів, що рухаються.
Апробація результатів дисертації. Результати досліджень були оприлюднені на 4-й Міжнародній науково-технічній конференції “АВИА-2002” (Київ, 2002 р); 8-й Міжнародній конференції "ИИСТ-2002" (Харків-Туапсе, 2002 р); конференції "Актуальні проблеми сучасної науки в дослідженнях молодих вчених м. Харкова" (Харків, 2002 р); 2-й Міжнародній конференції "Проблемы информатики и моделирования" (Харків, 2002 р); 7-м Міжнароднім молодіжнім форумі “Радиоэлектроника и молодежь в XXI веке” (Харків, 2003 р); ХI Міжнародній науково-практичній конференції “Информационные технологии: наука, техника, технология, образование, здоровье” (Харків, 2003 р).
Публікації. За темою дисертації видано 9 робіт: 3 статті в наукових збірниках, що входять в перелік ВАК України, 1 стаття в науковому збірнику, 2 патенти, 3 матеріали конференцій.
Структура і обсяг дисертації. Дисертація складається зі вступу, чотирьох розділів, висновків, списку використаних джерел зі 100 найменувань на 9 сторінках, 37 рисунків, з них 1 на повній сторінці, 11 таблиць та додатку на 13 сторінках. Загальний обсяг роботи – 143 сторінки.
основний зміст роботи
У вступі стисло розглянуто стан досліджень у галузі систем комп’ютерної графіки, обґрунтовано актуальність теми дисертації, сформульовано мету та задачі дисертаційної роботи, окреслено сукупність наукових результатів, що виносяться на захист, наукову новизну та практичну цінність отриманих результатів.
Перший розділ являє собою критичний огляд існуючих методів формування зображень тривимірної сцени, особисто об’єктів, що рухаються, у реальному часі. Надано загальну характеристику сучасним способам опису поверхонь об’єктів тривимірної сцени щодо можливості їх використання при синтезі зображення методом зворотного трасування, який має значні переваги перед іншими методами при синтезі високореалістичного зображення в реальному часі.
На основі проведеного аналізу сформульовано мету і задачі дослідження, які полягають у розробці моделей опису, алгоритмів синтезу зображень та структурних і функціональних схем спеціалізованих процесорів СВ для формування зображень об’єктів, що рухаються, в реальному часі.
В другому розділі надано розгорнуту характеристику сучасних способів геометричного опису поверхонь об’єктів сцени та виконано подальший розвиток аналітичної моделі геометричного опису, яка має такі переваги: компактність; простота визначення координат точки перетинання прямої (проекційного променя) з поверхнею; відносна простота обчислення вектора-градієнта для розрахунку освітленості; можливість опису даною моделлю досить складних поверхонь штучних об'єктів; коефіцієнти рівнянь поверхонь, використовуваних у даній моделі, мають просте геометричне значення, що полегшує роботу оператора в інтерактивному режимі при складанні опису об'єктів.
Геометричний опис об'єктів виконано за допомогою обмежених відсіків поверхонь 1-го і 2-го порядку – графічних примітивів (ГП). Для опису графічних примітивів використовуються поверхні, задані рівняннями в неявній формі:
 , (1)
де ki, si, D – коефіцієнти, що задають вид рівняння ГП, ki ∈{-1;0;1}, D∈{0;1}, si ≠ 0;
ti – координата простору, ti ∈{x;y;z}
pi – значення показника ступеня доданку рівняння ГП, pi ∈{1;2}.
Вибір неявної форми аналітичного опису поверхні пояснюється тим, що при такому описі, використовуючи ітераційний алгоритм, досить просто визначати інцидентність довільної точки простору P(x,y,z) даної поверхні.
Для побудови геометричного опису об’єктів, що рухаються, за допомогою поверхонь виду (1), їх необхідно обмежувати. Для обмеження простору, займаного поверхнею ГП, використовуються поверхні інших графічних примітивів, з яких складається об’єкт. Якщо графічні примітиви використовуються тільки для обмеження простору інших ГП, то поверхня таких примітивів не відображається. При цьому відображувані ГП можуть виконувати взаємне обмеження. Якщо графічний примітив обмежує даний ГП, то між ними існує зв’язність (див. нижче).
Геометричний опис об'єкта, що рухається, містить N графічних примітивів, у тому числі Nv відображуваних. Відповідно, геометричний опис n-го відображуваного графічного примітива,  , можна представити наступною системою рівнянь і нерівностей:
 , (2)
де Fn – рівняння (1) поверхні nго ГП;
Fm – ліва частина рівняння (1) mго обмежуючого ГП,  , m≠n;
При складанні геометричного опису поверхні об'єкта довільної форми, графічні примітиви піддаються наступним перетворенням: переміщення – зміна лінійних координат початку системи координат ГП; поворот – зміна кутових параметрів одиничного вектора системи координат ГП; деформація – зміна постійних коефіцієнтів a, b, c, що входять у рівняння ГП (1); відсікання – завдання і розташування обмежуючих ГП.
Опис зв’язності графічних примітивів між собою є присутнім у геометричному описі ГП (2) у вигляді нерівностей. Знак нерівності показує, у якому півпросторі щодо обмежуючого примітива знаходиться даний ГП. За позитивний півпростір прийнятий півпростір, у який направлений вектор нормалі (для площини) або вектор-градієнт (для інших поверхонь).
Для збереження інформації про зв’язність ГП з обмежуючими його примітивами, пропонується використовувати матрицю зв’язності  розмірністю Nv × N. Нульові елементи матриці зв’язності означають, що зв’язність між ГП, що утворюють перетинання рядка і стовпця, відсутня. Для ненульових елементів матриці записуються коди знаків нерівностей з (2) (елемент матриці, записаний у стовпці, обмежує простір елемента, записаного в рядку).
Матриця зв’язності застосовується при визначенні інцидентності точки простору поверхні даного ГП з урахуванням умов обмеження даного ГП іншими графічними примітивами. Однак, при зростанні складності ОР (кількості ГП), матриця зв’язності стає сильно розрідженою, що приводить до великої витрати пам'яті для її збереження і збільшенню часу обробки. Це викликано тим, що звичайно ГП зв'язаний з невеликою кількістю примітивів (до 10), при цьому загальна кількість графічних примітивів в об'єкті може сягати кількох сотень. Усунення зазначених недоліків здійснюється записом матриці зв’язності в упакованому вигляді, тобто для кожного ГП із рядка матриці зберігається інформація тільки з ненульових стовпців.
Для завдання положення об'єктів сцени, що рухаються, застосовується права декартова система координат (с/к). При цьому використовується мінімум три види с/к: базова (Земна або g-с/к), направлення осі ОY якої протилежно направленню сили ваги; система координат ОР, задана щодо базової с/к; система координат ГП, задана відносно с/к об'єкта, що рухається.
Параметри i-ої системи координат  , положення якої задано відносно j-ої системи координат, описано в такий спосіб:
 , (3)
де  – матриця повороту i-ої системи координат відносно j-й с/к;
 – положення початку координат i-ої с/к у j-й с/к.
Завдання положення системи координат за допомогою координат початку с/к і матриці повороту  розмірністю 3×3, на відміну від однорідних координат (матриця розмірністю 4х4), знижує вимоги до розрядності помножувачів спецпроцесора при збереженні необхідної точності обчислень. Для збереження значень кутових параметрів досить 13 двійкових розрядів, тому що розрізнювальна здатність ока людини лежить у межах  [3]. Для завдання лінійних координат об'єкта  з потрібній точністю необхідно більше двійкових розрядів, ніж для кутових координат. При об'єднанні параметрів різної точності в одній матриці однорідних координат необхідно значення всіх параметрів задавати з урахуванням максимальної необхідної розрядності. Таким чином, завдання положення ОР за допомогою (3) зменшує апаратні витрати при побудові помножувачів.
У загальному вигляді геометричний опис об'єкта, що рухається, пропонується складати в такий спосіб [9]:
 , (4)
де  – графічні примітиви, задані рівняннями виду (1);
 – параметри системи координат об'єкта, що рухається;
 – параметри систем координат ГП;
 – матриця зв’язності.
З метою зменшення часу синтезу зображення об'єктів, що рухаються, пропонується на етапі складання геометричного опису ОР (4) виконувати також і класифікаційний опис об'єктів [4,8], для автоматичного складання якого розроблений відповідний алгоритм [1]. Зменшення часу досягається за рахунок переносу частини обчислень по синтезу зображення з етапу візуалізації в етап складання опису об'єкта, що рухається. Для цього простір, займаний ОР, обмежується оболонкою, наприклад, паралелепіпедом. Простір усередині оболонки розділено на підпростори – домени (також паралелепіпеди), що нумеруються від 1 до D. Після складання геометричного опису ОР (4) формується класифікаційний список Lc, у якому для кожного не порожнього домену  перераховані ГП, поверхня яких принаймні перетинає даний домен:
Lc = {{ГП1, ГП3 …}1, … ,{ГП10, ГП15 …}d … ,{ГП14, ГП25 …}D}. (5)
Для складання класифікаційного списку Lc необхідно мати геометричний опис (4). Кожний відображуваний ГП об'єкта описується системою (2) таким чином, що для всіх точок, що належать об’ємові ОР, виконується умова
Fn(x,y,z) ≤ 0. (6)
З урахуванням (2) і (6) розглянемо умови приналежності n-го ГП d-му домену. Можливі наступні випадки, при яких ці умови можуть виконуватись.
Випадок 1. Поверхня n-го ГП не відсічена іншими примітивами і цілком (або деяка її частина) знаходиться усередині об'єму d-го домена.
Випадок 2. Поверхня i-го ГП відсічена іншими примітивами, і деяка її частина, або вся поверхня, знаходиться усередині об'єму d-го домена.
Введено предикатний опис випадків 1 і 2. Позначимо предикат  , де  відповідно для кожного випадку. Причому Рс =1, якщо умова приналежності для даного випадку виконується і Рс =0 в протилежному випадку. Обчислення предикатів  виконується за допомогою ітераційного алгоритму (ІТА) [7], нижчеперелічені ознаки якого дозволяють використовувати його для цієї мети.
Ознака 1. Якщо існує точка перетинання деякій прямій, у загальному випадку векторної,  (p – точка перетинання) з поверхнею  , то ІТА дозволяє на кожнім кроці ітерацій установити виконання умови (6) для точки, що знаходиться на цій прямій і відповідає цьому кроку ітерацій.
Ознака 2. Якщо відсутня точка перетинання деякій прямій  з поверхнею  , то ІТА по завершенні ітераційного процесу дозволяє знайти на цій прямій точку, найбільше близько розташовану до даної поверхні.
У дисертаційній роботі доведений ряд тверджень, що дозволяють обчислювати предикати  за допомогою ІТА.
Твердження 1. Якщо в процесі класифікації зустрічається ситуація, при якій n-й ГП і d-й домен перебувають в такому взаємному просторовому положенні, що відповідає випадкові 1, то необхідно і досить не більш трьох проходів ITA для встановлення приналежності i-го ГП d-му домену.
Твердження 2. Якщо в процесі класифікації зустрічається випадок 2, то для нього виконання твердження 1 (перебування загальної точки) є необхідною умовою приналежності n-го ГП d-му домену, а достатнім – задоволення системі виражень (2) для знайденої спільної точки.
Твердження 3. Якщо n-й ГП має обмежуючі примітиви  і при цьому для усіх вершин (тобто усіх  ) d-го домена виконується хоча б одна система нерівностей
 , (7)
тобто хоча б для одного m-го обмежуючого примітива, то поверхня n-го ГП не належить d-му домену. Введено предикат Р3, який дорівнює 1, якщо виконується (7), і Р3=0 в протилежному випадку.
Твердження 1-3 є основою алгоритму складання класифікаційного опису ОР, в якому при аналізі доменів оболонки обчислюється функція f приналежності n-го примітива d-му домену:
f =  ,
де а=1, якщо n-й ГП відсічений іншими примітивами і а=0 в протилежному випадку;
Р1, Р2 – предикати, що описують випадки 1 і 2 відповідно.
Якщо f = 1, поверхня n-го примітива принаймні перетинає d-й домен, і f = 0 в протилежному випадку.
Крім класифікаційного списку ГП (5), класифікаційний опис включає також розміри оболонки і доменів. У загальному виді класифікаційний опис має вигляд:
 , (8)
де Sx, Sy, Sz – розміри оболонки по осях X, Y і Z відповідно;
dx, dy, dz – розміри домена оболонки по осях X, Y і Z відповідно.
Класифікаційний опис (8) є складовою частиною методу класифікаційного опису, який включає до себе також алгоритм [1] автоматичного складання класифікаційного списку (5), та спосіб [4] використання класифікаційного опису при синтезі зображення ОР для зменшення загальної кількості обчислень в реальному часі.
З урахуванням (4) і (8) повний опис об'єкта, що рухається, має вигляд:
FD = {GD, CD}. (9)
В третьому розділі розглядаються етапи синтезу зображення об'єктів, що рухаються. З метою зменшення обсягу обчислень для синтезу зображення в реальному часі використовується поділ обчислень на “повільні” і “швидкі”. До “повільних” обчислень відносять такі обчислення, результат яких не змінюється протягом кадру (наприклад, визначення положення ОР відносно екрана). Задача “повільних” обчислень – попередня обробка інформації для синтезу кадру. До “швидких” обчислень відносять обчислення, результат яких змінюється протягом кадру при обробці чергового пиксела зображення, наприклад, обчислення точок перетинання проекційних променів (ПП) із ОР. Поділ обчислень на “повільні” і “швидкі” призводить до появи кадрового конвеєра, у якому перша ступінь виконує “повільні” обчислення, а наступні – “швидкі”. Затримка (латентність) такого конвеєра не повинна перевищувати 100-120 мс, а час такту – 33 мс, що обумовлюється особливостями нервової системи людини. Синтез одного кадру зображення ОР складається з двох етапів.
Етап 1. Сканування сцени [2,3]. Результатом сканування є список L1, кожен запис якого складається з номера ОР і діапазону проекційних променів, що можливо перетинаються з оболонкою цього ОР. Кількість записів Q у списку обумовлюється кількістю ОР, що потрапили в поле зору спостерігача. Оскільки сканування сцени виконується один раз на кадр, те перший етап синтезу зображення відноситься до “повільного” обчисленням і реалізується першою ступінню кадрового конвеєра, наприклад, універсальною ЕОМ.
Зроблено подальший розвиток алгоритму сканування поверхні рельєфу, який полягає в адаптуванні його для сканування ОР в просторі тривимірної сцени. Розроблено два алгоритми сканування простору сцени – кутовий і проекційний. Показано, що кутовий алгоритм сканування призначений для виконання операції сканування ОР в підсистемі синтезу зображення об'єктів, що рухаються, для СВ, у якій синхронізація підсистем здійснюється на піксельном рівні, тобто в кожнім каналі виконуються обчислення для одного поточного оброблюваного вектора спостереження. Для кутового алгоритму сканування q-й ( ) запис списку L1 має вигляд
{k, Dα, Dβ}q,
де k – номер ОР,  (К – загальна кількість ОР в сцені);
Dα, Dβ – кутове положення оболонки ОР в просторі сцени.
Проекційний алгоритм сканування призначений для виконання операції сканування ОР в підсистемі синтезу зображення об'єктів, що рухаються, для СВ, у якій синхронізація підсистем здійснюється на кадровому рівні, тобто в кожнім каналі виконуються обчислення для одного поточного оброблюваного кадру зображення сцени. Для проекційного алгоритму сканування q-й запис списку L1 має вигляд
{k,  , }q,
де [μmin, μmax], [νmin,νmax] – діапазони екранних координат пікселів, що відповідають проекції оболонки ОР на екрані по вертикалі і горизонталі відповідно.
Етап 2. Пошук перетинань ПП з об'єктами сцени, що рухаються, і визначення найближчих видимих ОР, поверхня яких буде відображатися на екрані. При цьому використовуються результати першого етапу синтезу зображення. Операції другого етапу виконуються для кожного піксела синтезованого зображення і відносяться до “швидких” обчислень. Другий етап синтезу кадру зображення виконується наступними ступінями кадрового конвеєра, реалізованими на спецпроцесорі. У свою чергу, друга і наступна ступіні кадрового конвеєра являють собою конвеєр обробки векторів спостереження (векторний конвеєр).
Вхідними даними для візуалізації об'єктів, що рухаються, являються: параметри системи відображення; положення спостерігача (центра проекцій); опис ОР (9); результати сканування – список L1.
На рис.1 представлена геометрична модель синтезу зображення об'єктів, що рухаються, заснована на математичній моделі геометричних перетворень [7] для методу зворотного трасування. Показані: базова система координат (g-с/к) XYZ; рухома система координат UVW (v-с/к), зв'язана зі спостерігачем і центром проекцій h; екранна система координат YSОSZS, що задає положення пікселів екрана S; система координат об'єкта, що рухається, XОРYОРZОР, початок якої розміщено в центрі ваги ОР; оболонка (паралелепіпед), що обмежує простір, займаний ОР.
На рис.1 прийняті наступні позначення:  – радіус-вектор початку v-с/к у базовій системі координат,  задає положення v-с/к відносно базової с/к;  – радіус-вектор центра проекцій h у v-с/к, задає положення центра проекцій відносно v-с/к;  – вектор спостереження (ВС), проведений з центра проекцій до поточного i-го піксела екрана,  , Nz – кількість пікселів по горизонталі, Ny – кількість пікселів по вертикалі;  – проекційний промінь, проведений з центра проекцій у напрямку вектора спостереження  до перетинання з відображуваною поверхнею;  – радіус-вектор точки Рі поверхні ОР в базовій с/к, точка Рі утвориться перетинанням проекційного променя  з поверхнею ОР.
Для збереження в процесі синтезу зображення постійної кутової погрішності для усіх ОР, що знаходяться на різних відстанях від центра проекції, уведене поняття сфери охоплення (на рис.1 показана пунктиром). Така сфера з центром у точці h будується для кожного ОР, і її радіус визначає довжину ітераційного відрізка hЕ, на якому виконується пошук точок перетинання проекційного променя з об'єктом. Радіус сфери охоплення RСО визначається в такий спосіб: RСО = hООР+ΔRСО, де hООР – відстань від центра проекцій до центра ваги ОР; ΔRСО = ООРB – деяка мінімальна величина (визначається на етапі конструювання й опису об'єкта, що рухається), що задає радіус сфери охоплення таким чином, щоб усі вершини оболонки ОР виявилися усередині сфери.
Синтез зображення об'єктів сцени методом зворотного трасування здійснюється в такий спосіб. Кожному i-му пікселу екрана відповідає свій вектор спостереження  . Кожному векторові спостереження  відповідає свій проекційний промінь  . Якщо ПП перетинається з поверхнею об'єкта, що рухається, у деякій точці Pi, то на екрані в і-му пікселі відображається колір поверхні об'єкта, що відповідає точці Pi. Якщо перетинання проекційного променя з об'єктом відсутнє, відображається колір фону. Положення точки перетинання ПП з об'єктом визначається векторним рівнянням
 ,
де  – обчислюється за допомогою ІТА [7].
Візуалізація сцени. Синтез зображення виконується для кожного піксела екрана однаковим образом і незалежно друг від друга, що дозволяє розпаралелювати обчислення для зниження загального часу синтезу кадру зображення. В основі візуалізації ОР лежить пошук точок перетинання ПП спочатку з оболонкою, а потім і з графічними примітивами об'єкта. Пошук точок перетинання виконується за допомогою ітераційного алгоритму, що дозволяє визначати координати точки перетинання прямій з поверхнями першого і другого порядку, заданими аналітично рівняннями в неявній формі. Вираження для рівняння поверхні в неявному виді, визначене в системі координат графічного примітива, має найбільш простий запис, що зменшує апаратні витрати при реалізації обчислювача ІТА. При цьому необхідно координати початкової і кінцевої точок ітераційного відрізка задавати в системі координат поверхні, з яким визначається перетинання.
Далі всі операції по синтезу зображення k-го ОР сцени описано для і-го піксела зображення. Алгоритм візуалізації k-го ОР складається з наступних кроків:
1. Аналіз результатів сканування. У випадку застосування кутового алгоритму сканування перевіряється виконання умови
 , (10)
де αі, βі – кутові параметри і-го вектора спостереження.
Якщо застосовано проекційний алгоритм сканування, необхідно перевіряти виконання умови
 , (11)
де μі, νі – екранні координати і-го піксела екрана.
У разі виконання (10) або (11) переходять до наступного кроку алгоритму.
2. Пошук точок перетинання ПП з оболонкою об'єкта, що рухається, (xЕ1, yЕ1, z Е1) і (x Е2, y Е2, z Е2). У разі існування хоча б однієї точки перетинання переходять до наступного кроку алгоритму.
3. Складання списку графічних примітивів LПП, що лежать на шляху проекційного променя, за допомогою метода класифікаційного опису. Якщо список LПП містить хоча б один ГП, переходять до наступного кроку алгоритму.
4. Пошук точок перетинання ПП із ГП об'єкта, що рухається. У разі існування хоча б однієї точки перетинання переходять до наступного кроку алгоритму.
5. Аналіз точок перетинання ПП із ГП за допомогою матриці зв’язності. Якщо хоча б одна з точок перетинання задовольняє умовам з матриці зв’язності, переходять до наступного кроку алгоритму.
6. Визначення кольору відображуваної поверхні ОР.
Слід зазначити, що синтез і-го піксела зображення k-го ОР може бути припинений при виконанні кожного з кроків 1-5 алгоритму, якщо встановлено, що даний ОР в поточному пікселу не відображається.
Повний алгоритм синтезу окремого піксела зображення сцени, що містить M об'єктів, що рухаються.
1. Вибір наступного запису зі списку L1, отриманого після сканування.
2. Синтез зображення k-го ОР поточного запису. Виконується відповідно до п.1-6 алгоритму синтезу окремого ОР. При цьому формується список LОР, у який у випадку існування точки перетинання k-го ОР з i-м ПП додається запис виду
{k; tk}і ,
де tk – відстань від центру проекцій до точки перетинання i-го ПП із ОР.
Кроки 1 і 2 алгоритму виконуються для всіх записів списку L1. Якщо в результаті список LОР не містить ні одного запису, то в даному пікселі не відображається жоден з об'єктів сцени, що рухаються, і робота алгоритму завершується.
3. Вибір об'єкта, що рухається, поверхня якого буде відображатися в даному пікселі екрана. Здійснюється порівнянням значень tk кожного запису списку LОР і вибором мінімального з них. Мінімальному tk відповідає номер ОР k, по якому здійснюється вибірка з області пам'яті, що зберігає параметри ОР, значення кольору пиксела екрана, розрахованого з урахуванням освітленості, прозорості і властивостей матеріалу поверхні.
Четвертий розділ присвячено моделюванню запропонованих методів опису та алгоритмів синтезу зображень об’єктів, що рухаються.
Виконано математичне моделювання моделей і алгоритмів, розроблених у дисертаційній роботі. Моделювання показало значне зменшення (більше ніж в 10 разів [4], рис.2) часу візуалізації при використанні методу класифікаційного опису й алгоритму сканування сцени. У четвертому розділі на основі алгоритмів, розроблених у розділах 2-3, розроблена структура підсистеми формування зображення об'єктів, що рухаються, (рис.3). Підсистема складається з операційного пристрою ОП і запомінаючих пристроїв ЗП. У свою чергу, запомінаючі пристрої поділяються на ЗП даних для операційного пристрою і буферні ЗП для збереження проміжних результатів роботи ОП. Операційний пристрій включає наступні блоки: два блоки обчислення точок перетинання БОТП1 і БОТП2, призначених для пошуку точок перетинання проекційного променя з оболонкою ОР і графічних примітивів відповідно; формувач адресу і списку примітивів ФАСП, призначений для складання списку графічних примітивів об'єкта, що рухається, LПП, що лежать на шляху проекційного променя; блок аналізу зв’язності БАЗ, який виконує перевірку отриманих БОТП2 точок перетинання на відповідність умовам зв’язності; блок обробки текстури БОТ, призначений для обчислення кольору поверхні для знайденої точки перетинання з урахуванням освітленості. Буферні ЗП служать для збереження списків ГП, складених у результаті роботи ФАСП і БОТП2. ЗП даних використовується для збереження класифікаційного опису ОР (8), геометричного опису ОР (4), текстурного опису об'єктів, що рухаються.
Окремі блоки підсистеми формування зображення об'єктів, що рухаються, деталізовані до рівня функціональних схем і виконане імітаційне моделювання їхньої роботи. Розроблені блоки мають паралельно-конвеєрну архітектуру [5,6], завдяки якій можливе суміщення операцій, а, отже, і досягнення високої продуктивності. Імітаційне моделювання було виконано за допомогою САПР фірми Altera, відомого виробника програмувальних логічних інтегральних схем (ПЛІС) і показало, що розроблену підсистему СВ можливо реалізувати за допомогою технології ПЛІС, що дозволяє виконати фізичне моделювання системи візуалізації.
В додатках наведені результати математичного та імітаційного моделювання, документи впровадження.
| 
