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

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

ДЕРЖАВНИЙ ВИЩИЙ НАВЧАЛЬНИЙ ЗАКЛАД

"ДОНЕЦЬКИЙ НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ"

УДК 004.925.83

Автореферат

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

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

Спеціальність 05.13.05 - Комп'ютерні системи та компоненти

Анас Махмуд Абдель-Хамід Аль-Орайкат

Донецьк-2011

Дисертація є рукописом.

Робота виконана у Державному вищому навчальному закладі «Донецький національний технічний університет» Міністерство освіти і науки, молоді та спорту України.

Науковий керівник:: доктор технічних наук, професор Башков Євген Олександрович, ДВНЗ «Донецький національний технічний університет», Міністерство освіти і науки, молоді та спорту України, завідувач кафедри «Прикладна математика та інформатика».

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

доктор технічних наук, професор Мишко Сергій Васильович, Донецький національний університет, Міністерство освіти і науки, молоді та спорту України, завідувач кафедри «Прикладна математика і технічні системи управління»;

доктор технічних наук, професор Кривуля Геннадій Федорович, Харківський національний університет радіоелектроніки, Міністерство освіти і науки, молоді та спорту України, завідувач кафедри «Автоматизація проектування обчислювальної техніки».

Захист відбудеться «14» 04 2011 р., о 14.00 годині на засіданні спеціалізованої вченої ради Д 11.052.03 Донецького національного технічного університету за адресою 83001, м. Донецьк, вул. Артема,58, ауд. 8.704.

З дисертацією можна познайомитися в бібліотеці Донецького національного технічного університету (адреса: 83001, м. Донецьк, вул. Артема,58, ІІ нав. корп.)

Автореферат розісланий «10» 03 2011 р.

Учений секретар спеціалізованої вченої ради Д.11.052.03 кандидат технічних наук, доцент Г.В. Мокрий.

Загальна характеристика роботи

Актуальність теми. На даний час отримують велике поширення нові способи подання інформації людині за допомогою візуального каналу сприйняття. Підвищення інформативної пропускної здатності передачі візуальної інформації від комп'ютера до людини призводить до нових напрямків вдосконалення пристроїв відображення. І, в першу чергу, до побудови систем, які використовують можливості зорового апарату людини у сприйнятті тривимірних образів. Тут слід зазначити розробки як вітчизняних вчених - В.Ф. Євдокимова, А.І. Стасюка, Ю.Н. Груца, Є.О. Башкова, О.Н. Романюка, так і закордонних - А.Н. Путіліна, В.А. Єжова, Дж. Генга, Г. Фавалора та інших, які досягли істотних результатів у створенні тривимірних пристроїв відображення інформації (3D ПВІ). Такого роду пристрої вже находять своє практичне застосування у системах керування рухом, авіаційних системах, медицині, телебаченні та кінематографії. 3D системи, що отримали в даний час широке розповсюдження, побудовані на базі бінокулярних технологій і мають ряд істотних недоліків: негативний вплив на зоровий апарат людини при тривалому сприйнятті, вимога точного позиціонування спостерігача, відсутність багаторакурсності. Запропоновані різні технології побудови 3D ПВІ, що усувають зазначені недоліки, серед яких виділяється клас об'ємних 3D пристроїв (volumetric displays), що відрізняються рядом привабливих властивостей: відсутність обмежень на положення спостерігача, необмежене поле зору, природна звідність зорового апарату. Побудова систем тривимірної візуалізації, заснованих на об'ємних технологіях, стримується низкою причин, одна з яких пов'язана з відсутністю стандартних підходів подання 3D інформації для них. Для таких пристроїв не вироблені визначення типових 3D графічних примітивів і алгоритмів їх генерування. В зв'язку з цим розробка методів подання загальноприйнятих графічних примітивів, в першу чергу відрізка прямої, для об'ємних 3D ПВІ є актуальним завданням.

Зв'язок роботи з науковими програмами, планами, темами. Основні дослідження по темі дисертації виконано протягом 2007-2010 років в рамках наукового напрямку кафедри прикладної математики та інформатики за темами Д-01-09 «Ефективні методи і архітектури обчислювальних систем синтезу, генерування та пошуку тривимірних зображень об'єктів» (№ держреєстрації 0108U010907) і Н-22-2010 «Програмне забезпечення високопродуктивних обчислювальних, інтелектуальних та моделюючих систем» (№ держреєстрації 0110U006207). Автор є одним із виконавців за даними темами.

Мета роботи і завдання дослідження: розробка методів та апаратно-програмних засобів генерування графічних примітивів (відрізків прямих) підвищеної продуктивності для об'ємних 3D пристроїв відображення.

Для досягнення цієї мети в роботі вирішуються наступні завдання:

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

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

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

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

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

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

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

Наукова новизна отриманих результатів полягає в наступному:

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

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

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

- запропонована нова структура і виконана оцінка часових характеристик спеціалізованого процесора для генерування 3D образів відрізків прямих у об'ємних ПВІ.

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

Результати дисертаційного дослідження використані в науково-дослідних роботах Донецького національного технічного університету Д-01-09 «Ефективні методи та архітектури обчислювальних систем синтезу, генерування і пошуку тривимірних зображень об'єктів», Н-22-2010 «Програмне забезпечення високопродуктивних обчислювальних, інтелектуальних та моделюючих систем», при читанні лекцій дисципліни «Комп'ютерний синтез і обробка зображень» і в навчальному процесі при виконанні науково-дослідних, магістерських та дипломних робіт студентами кафедр прикладної математики та кафедри комп'ютерної інженерії.

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

· у роботі [1] дисертант виконав аналіз технологій побудови 3D пристроїв відображення і розробив алгоритм реалізації методу, заснованого на пошуку мінімальної відстані;

· у роботі [2] дисертанту належить модифікований метод воксельного розкладання, що враховує напрямок пріоритетного пошуку наступного вокселя;

· у роботі [3] дисертанту належить метод перпендикулярних площин і порівняльне дослідження часових характеристик запропонованих методів.

Апробація результатів роботи. Результати досліджень і основні положення роботи доповідалися і обговорювалися на:

- IV науково-технічної конференції студентів, аспірантів та молодих вчених «Інформатика та комп'ютерні технології» (м. Донецьк, Донецький національний технічний університет, 25-27 листопада 2008 р..);

- 14-ому Міжнародному молодіжному форумі «Радіоелектроніка та молодь у XXI столітті» (м. Харків, Харківський національний університет радіоелектроніки, 18-20 березня 2010 р);

- V-й науково-практичній конференції «Донбас - 2020: перспективи розвитку очима молодих вчених » (Донецьк, Донецький національний технічний університет, 25-27травня 2010 р.);

- Vth International Scientific and Technical Conference (CSIT 2010) (м. Львів, Національний університет «Львівська політехніка», 14-16 жовтня 2010 р.);

- на наукових семінарах факультету комп'ютерних наук і технологій Донецького національного технічного університету.

Публікації. Основні результати дисертаційної роботи опубліковані у 7 наукових працях, із них 3 статті у виданнях, включених до переліку ВАК України, 4 - у збірниках робіт і тез міжнародних та регіональних науково-технічних конференцій.

Структура та обсяг дисертаційної роботи. Дисертація складається із вступу, чотирьох розділів, висновків, переліку посилань, який містить 96 бібліографічних посилань, і 6 додатків. Повний обсяг дисертації становить 181 сторінок друкованого тексту, з них 115 сторінок основного тексту, містить 35 рисунків і 10 таблиць.

Основний зміст роботи

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

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

Рис. 1. Узагальнена структура об'ємного 3D ПВІ

3D ПВІ будується на базі деякого об'ємного тривимірного монітора, інформація на який подається з двонаправленого запам'ятовуючого пристрою - буфера 3D образу через деякий апаратний перетворювач, який формує дані для монітора з відповідною структурою. Об'ємне зображення генерується за допомогою генератора 3D графічних примітивів, який за результатами рендерінгу тривимірного образу "будує" у відеопам'яті вокселізований 3D образ сцени. Необхідні геометричні перетворення і рендерінг образу можуть виконуватися як на основному комп'ютері, так і на спеціальних пристроях, наприклад, графічних процесорах (ГП, GPU).

Завдання генерування базового 3D-графічного примітиву - відрізка прямої для об'ємних 3D ПВІ - формулюється наступним чином. Нехай деяка область тривимірного евклідового простору, яка відображається 3D дисплеєм, має вид тривимірного куба . Припустимо, що заповнена вокселями - атомарними елементами, які відображаються 3D дисплеєм. Воксель - куб із одиничним ребром, а множина вокселів, що заповнюють , являє собою тривимірний масив вокселів . Причому, з одного боку, i, j, l - це індекси вокселя в масиві, які приймають значення 0,1,...,[H], а з іншого, визначають координати вокселя в . Сусідами деякого вокселя з координатами i_k, j_k, l_k будемо вважати вокселі , для яких виконується умова max {| i_g,-i_k| , | j_g -j_k| , | l_g -l_k |}=1. В якості метрики на множині векселів прийнята функція m_g,k = | i_g,-i_k,|+| j_g -j_k,|+| l_g -l_k |. Визначимо координати центру вокселя в як = i + 0.5, = j + 0.5, = l + 0.5. У задано відрізок прямої своєї початкової S = [x_S, y_S, z_S]' і кінцевої E = [x_E, y_E, z_E]' точками, при цьому E ? S. Необхідно знайти таку послідовність вокселів, , k=1, 2, ... N, що , а для будь-якого проміжного вокселя , k=2,3, ... N-1 виконується умова - існує така точка відрізку для якої для деяких t, 0<t<1. Остання умова вимагає, щоб будь-який проміжний воксель містив у собі деяку частину відрізка. Знайдена послідовність називається «3D цифровою апроксимацією» або «3D воксельним розкладанням» , а процедуру отримання послідовності - «3D генерування» . Потрібно також, щоб у всіх проміжних вокселів, крім першого і останнього, було тільки два зв'язаних з ним сусіди, та щоб відстань m_k,k+1 будь-якої пари вокселів в послідовності була максимальною. Відзначимо, що мінімальна кількість вокселів N в 3D розкладанні з урахуванням виконання попередньої вимоги може бути знайдена як .

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

У другому розділі «Розробка методів генерування воксельного подання відрізка прямій» представлені розроблені методи розв'язання задачі воксельного розкладання відрізка на базі мінімізації відхилення від заданого відрізка. Ідея підходу полягає у виборі чергового вокселя послідовності із сукупності можливих вокселів-претендентів, як вокселя з мінімальною відстанню до заданої прямої. Відстань від центру вокселя - претендента знаходиться як довжина перпендикуляру, який опущено із центру вокселя на пряму. У роботі запропоновано скорочувати кількість вокселів - претендентів на кожному кроці до 4-х, з огляду на пріоритетність напрямку руху по певній координаті. Показано, що помилка методу, що визначається як максимальне відхилення центру вокселя з усіх вокселів розкладання, не перевищує половини головної діагоналі одиничного куба - 0,866.

Запропоновано метод воксельного розкладання відрізка, заснований на представленні відрізка як множини точок перетину двох площин. Відхилення довільної точки від деякої площини можна оцінити як , де - коефіцієнти площини. Запропоновано першу площину вибирати як площину, яка містить початок координат і точки S і E, за умови, що S? 0 і (або) E ? 0, а другу - таку, яка перпендикулярна першій. Черговий воксель послідовності вибирається з вокселів - претендентів як воксель з мінімальним сумарним відхиленням від площин. Алгоритм, який реалізує запропонований метод пересічних площин, можна представити наступним чином:

Begin

Введення початкової S і кінцевої E точок;

Обчислення направляючого вектора відрізка;

Обчислення коефіцієнтів площин;

Визначення кількості кроків N, початкового і кінцевого вокселів;

Формування матриці збільшень ;

For k:=1 to N-1 do

е_min= + ?;

For q:=1 to 4 do

;

обчислення сумарної ;

if (е _q < е_min) then е_min = е; r ₌ q; end if

end for

=;

end for

End

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

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

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

Таблиця 1

			Час генерування (мсек)	Продуктивність (Mvps)	Прискорення відносно базового
Базовий метод (мод. 4 напр.)	0,352	0,681	330	1,71
Перпендикулярні площині	0,35	0,86	266	2,12	1,2
Параметричний метод	0,43	0,86	62	9,09	5,3

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

У третьому розділі «Підвищення продуктивності засобів воксельного розкладання 3D відрізків на базі технології CUDA» досліджуються можливості сучасних паралельних графічних процесорів для реалізації методів воксельного розкладання відрізків. В якості базового пристрою застосовувався GPU з архітектурою CUDA фірми NVIDIA (відеокарта GeForce GTX 285, графічний процесор GT 200, 240 обчислювальних блоків). Часова ефективність реалізації певного алгоритму на GPU залежить від багатьох факторів і, в першу чергу, від обраної конфігурації мережі блоків та потоків і від обраного способу і місця зберігання даних. Для всіх запропонованих методів та їх модифікацій розроблена узагальнена схема реалізації, на рис. 2 наведена схема для методу перпендикулярних площин.

Рис. 2. Схема модифікованого алгоритму перпендикулярних площин

При проведенні експериментів варіювалися наступні параметри:

* для методу перпендикулярних площин досліджувалися алгоритми як з 7 вокселями - претендентами (базовий метод), так і 4 вокселями - претендентами (модифікований метод);

* виконувалося воксельне розкладання одного відрізка заданої довжини - 10, 20,50, 100, 1 000, 2 000, 5 000, 10 000, 20 000, 50 000, 100 000 вокселів;

* виконувалося воксельне розкладання множини (1024-х) відрізків заданої довжини - 10, 20, 50, 100, 1 000, 2 000, 5 000, 10 000, 20 000, 50 000, 100 000 вокселів;

* виконувалося воксельне розкладання множини (1024-х) довільних відрізків прямих сумарною довжиною більше 500 000 вокселів;

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

* дані представлялися у форматі з плаваючою комою одинарної (float) і подвійної точності (double).

Аналіз результатів комп'ютерних експериментів дозволяє зробити такі основні висновки:

- найбільшу продуктивність при реалізації на архітектурі CUDA має параметричний метод (до 40 Mvps), як і при реалізації на ресурсах ПК (більше 10Mvps) (рис.3);

- найбільша продуктивність і завантаження GPU досягаються при «одночасному» виконанні операцій воксельного розкладання множини відрізків (при використанні параметричного методу завантаження до 100%);

- модифіковані методи (4 вокселя - претендента) при їх реалізації на архітектурі CUDA не мають переваг у порівнянні з базовими (7 вокселів - претендентів), як це спостерігалося при реалізації засобами ЦПУ.

Рис. 3. Продуктивність методів воксельного розкладання на ЦП і ГП

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

Виконана оцінка продуктивності запропонованого спецпроцесору на базі його реалізації на ПЛМ фірми Xilinx типу Vertix-6. З урахуванням максимально можливої швидкодії типових схем фірми, продуктивність спеціалізованого процесору складає 4,6 мегавокселя за секунду. У порівнянні з результатами реалізації методу засобами ПК (CPU) продуктивність у 2 рази більше.

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

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

Рис. 4. Структура спецпроцесору вексельного розкладання відрізка прямої

Висновки

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

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

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

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

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

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

5. Проаналізовано результати експериментів, що дозволяє зробити наступні висновки:

- найбільшу продуктивність при реалізації на ГП з архітектурою CUDA має параметричний метод (до 40 Mvps), як і при реалізації на ресурсах ПК (більше 10Mvps),

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

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

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

Аналіз часових параметрів запропонованого пристрою дозволяє зробити висновок, що продуктивність пристрою може досягати значень 4,6 Mvps, що на порядок перевищує реалізацію засобами CPU з технологією CUDA.

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

1. Аль-Орайкат Анас Махмуд. К построению генератора графических примитивов для трехмерных дисплеев / Анас Махмуд Аль-Орайкат, Е.А. Башков, О.А. Авксентьева // Наукові праці Донецького державного технічного університету, Серія “Проблеми моделювання та автоматизації проектування динамічних систем”. - Вип. 7 (150). - Донецьк : ДонНТУ, 2008. - С. 203 - 214.

2. Аль-Орайкат Анас Махмуд. Генератор отрезков прямых повышенной производительности для трехмерного дисплея / Анас Махмуд Аль-Орайкат, Е.А. Башков, О.А. Авксентьева, Д.И. Хлопов // Наукові праці Донецького національного технічного університету, Серія “Інформатика, кібернетика і обчислювальна техніка”. - Вип. 11 (164). - Донецьк : ДонНТУ, 2010. - С. 100-105.

3. Аль-Орайкат Анас Махмуд. Алгоритмический базис построения генераторов отрезков прямых для 3D дисплеев / Анас Махмуд Аль-Орайкат, Е.А. Башков, О.В. Дубровина, О.А. Авксентьева // Наукові праці Донецького державного технічного університету, Серія «Обчислювальна техніка та автоматизація». - Вип. 18 (169). - Донецьк : ДонНТУ, 2010. - С. 62 - 70.

4. Al-Oraiqat A.M. Hlopov D.I. Modified algorithm of straight line segments generation for 3D displays / Bashkov E.A., Avksentieva O.A., Al-Oraiqat A.M. // Proceedings of the Vth International Scientific and Technical Conference (CSIT 2010), Видавницьтво ПП «Вежа і Ко», 2010. - P. 193-195.

5. Аль-Орайкат Анас Махмуд. Модифицированный алгоритм генерации отрезков прямых для 3D дисплеев / Авксентьева О.А., Аль-Орайкат Анас Махмуд, Башков Е.А., Хлопов Д.И. // Труды V научно-практической конференции «Донбас - 2020: персепктивы развития глазами молодых ученых», 25-27 мая 2010 г., - Донецк, ДонНТУ, 2010. - С. 614-618.

6. Аль-Орайкат Анас Махмуд. Улучшенный алгоритм генерации прямой для 3D дисплеев / Аль-Орайкат Анас Махмуд, Хлопов Д.И. // 14-го Международный молодежный форум «Радиоэлектроника и молодежь в XXI веке, 18-20 марта 2010 г». Сб. материалов форума. Ч.1. - Харьков, ХНУРЭ, 2010. - С. 460.

7. Аль-Орайкат Анас Махмуд. Подходы к построению трехмерных графических дисплеев / Авксентьева О.А, Аль-Орайкат Анас Махмуд // Інформатика та комп'ютерні технології - 2008 Матеріали IV науково-технічної конференції студентів, аспірантів та молодих учених - 25-27 листопада 2008, ДонНТУ, Донецьк - 2008 - С. 277-278.

Анотація

Анас Махмуд Абдель-Хамід Аль-Орайкат. Методи та апаратно-програмні засоби генерування тривимірних (воксельних) графічних примітивів для 3D пристроїв відображення. - Рукопис.

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

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

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

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

Показано, що найбільш швидким є параметричний метод, який більш ніж в 5 разів зменшує часові витрати в порівнянні з базовим методом.

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

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

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

Аннотация

Анас Махмуд Абдель-Хамид Аль-Орайкат. Методы и аппаратно-программные средства генерации трехмерных (воксельных) графических примитивов для 3D устройств отображения. - Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.05 - компьютерные системы и компоненты. - Государственное высшее учебное заведение «Донецкий национальный технический университет», Донецк, 2011.

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

Выполнен обзор и сравнительный анализ основных тенденций развития устройств отображения визуальной информации и, в первую очередь, устройств визуализации 3D контента. Обобщена классификация технологий построения 3D УОИ и выделены объемные технологии, как имеющие ряд существенных преимуществ. Рассмотрены типовые аппаратно-программные решения, используемые для построения объемных 3D УОИ и определена обобщенная структура такого устройства.

Рассмотрена задача генерации отрезка прямой для 3D УОИ, как задача определения множества вокселей, аппроксимирующих заданный отрезок. Выполнен анализ существующих методов решения поставленной задачи. На базе анализа типичных структур объемных устройств отображения определены место и основные функции генераторов трехмерных графических примитивов в объемных 3D УОИ.

Получил дальнейшее развитие метод воксельного разложения отрезка прямой в 3D пространстве, основанный на последовательном продвижении вдоль отрезка с учетом минимальности расстояния следующего вокселя до отрезка (базовый метод). Предложены модифицированные методы воксельного разложения отрезка прямой, основанные на представлении прямой как пересечения двух плоскостей и на параметрическом задании прямой. Показано, что все предложенные методы дают максимальную ошибку, не превосходящую 0,5 диагонали вокселя, при этом средняя ошибка составляет менее четверти диагонали.

Показано, что наиболее быстрым является параметрический метод, более чем в 5 раз уменьшающий временные затраты по сравнению с базовым.

Предложены подходы к организации параллельных вычислений на графических процессорах и выбору рациональных параметров распараллеливания (количество и конфигурация блоков, количество потоков) методов воксельного разложения. Проанализированы результаты экспериментов, что позволяет сделать вывод, что набольшей производительностью при реализации на ГП с архитектурой CUDA имеет параметрический метод (до 40 Mvps), как и при реализации на ресурсах ПК (более 10 Mvps).

Предложено и аналитически обосновано архитектурное решение специализированного процессора, реализующего модифицированный метод воксельного разложения отрезка прямой. Выполнена оценка производительности предложенного процессора при его реализации на ПЛМ фирмы Xilinx типа Vertix-6. С учетом максимально возможного быстродействия типовых схем фирмы, производительность спецпроцессора составит 4,6 Mvps.

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

Abstract

Anas Mahmud Abdel-Hamid Al-Oraiqat. The methods and hardware-software means of generation three-dimensional (voxels) graphic primitives for 3D display devices. - Manuscript.

Doctoral candidate's thesis in a specialty 05.13.05 - «Computer systems and components». - State higher educational establishment «Donetsk national technical university», Donetsk, 2011.

The dissertation is devoted to the problem of the burning scientific issue for the increase in order to improve the visualized content for the computer system's user. It could be achieved through the creating of hardware-software basis volume three-dimensional devices of display.

The problem of generation of a straight-line segment for 3D display devices has been considered as the problem of the defining multitude voxels, which approximate the given segment. The analysis of existing methods of the problem of a task in view has been realized. Having based on the analyses of typical structures of volume devices of display, the place and basic functions of generators of three-dimensional graphic primitives in volume 3D display devices are defined.

The method of voxel expansions of a segment of a straight line in 3D space, that is based on serial advancement along a segment, taking into account the minimality of the following voxel's distance to a segment (a basic method) - has found his further development. We have presented these methods of voxel expansions of the straight line segment, which is based on straight line representation as intersections of two planes and the parametric definition of a straight line. You can't but come across the situation that all offered methods give the maximum error, which is not exceeding 0,5 voxel's diagonals, at the same time the average error component is less than a diagonal quarter.

From this dissertation we know that the parametric method is the fastest one, which in comparison with basic more than in 5 times has reduced the temporal expenses.

Researches on effective implementation of the offered methods on graphic processors with parallel architecture CUDA are fulfilled. It is experimentally installed that the parametric method possesses the greatest productivity.

The architectural decision of the specialized processor, which realized the modified method of voxel's expansion of a straight line segment with productivity to 4.6 Mvps is offered and is analytically justified.

Key words: a display device, 3D content, a graphic primitive, a straight line segment, voxel, voxel's expansion, the generator, CUDA, the specialized processor.

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

...