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

[ виправити ] текст може містити помилки, будь ласка перевіряйте перш ніж використовувати.

скачати

Факультет інформатики і систем управління

Кафедра "Програмне забезпечення ЕОМ та інформаційні технології"

Курсовий проект

по машинній графіці

Розрахунково-пояснювальна записка

Тема:

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

Москва 2004

Зміст

1. Введення

2. Конструкторська частина

2.1 Обгрунтування використаних алгоритмів

2.2 Структура даних

2.2.1 Джерела світла

2.2.2 Об'єкти для візуалізації

2.2.3 Текстури

2.3 Алгоритм зворотного трасування променів

2.3.1 Опис алгоритму

2.3.2 Математична основа зворотного трасування променів

2.3.3 Складання матриці

2.3.4 Програмна реалізація

2.3.5 Визначення перетину променя з трикутником

2.3.4 Формування відбитого променя

2.3.5 Формування переломленого променя

2.4 Оболонки

2.4.1 Алгоритм побудови ієрархічних оболонок

2.4.2 Алгоритм обходу оболонок в трасуванні променів

2.5 Текстурування

2.5.1. Процедури для роботи з текстурами

2.5.2. Власне текстурування

2.6 Зафарбування Фонга

2.7 Освітлення

2.7.1. Модель освітлення Уіттеда

2.7.2 Дифузійне відбиття

2.7.3 Дзеркальне відображення

2.7.4 Фонова освітленість

2.7.5 Прозорість

2.7.6 Процедури розрахунку освітленості

3. Технологічна частина

3.1 Вибір мови програмування та обгрунтування вибору

3.2 Модульна структура програми

3.3 Інтерфейс програми

4. Експериментально-дослідна частина

Тест № 1

Тест № 2

Тест № 3

Висновок

Список літератури

1. Введення

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

У моїй курсовій роботі для рендеринга застосовується алгоритм зворотного трасування. На сьогоднішній день він вважається одним із кращих для формування реалістичних зображень. Його використовують більшість тривимірних графічних редакторів. Застосовується так само алгоритм z-буфера. Але ефекти віддзеркалення і заломлення, там досягаються штучними методами і вважаються не зовсім точно. Подібним методом користуються в програмах, де вкрай важлива швидкість. Прикладом таких програм служать комп'ютерні ігри. Майже всі вони побудовані на використанні алгоритму z-буфера.

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

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

управління камерою

управління джерелами світла

завдання об'єктів на сцені.

повороту об'єктів

рендеринга сцени

виведення зображення в задається вікно

Щодо використання модуль Engine дуже схожий на модуль OpenGL.

2. Конструкторська частина

2.1 Обгрунтування використаних алгоритмів

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

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

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

Для згладжування зображення застосований алгоритм зафарбовування Фонга. Він є найбільш витратним за часом. Метод Гуро, наприклад, швидше Фонга приблизно в 5 разів. Але час його виконання від загального часу рендеринга не перевищує 3 відсотків. Зате він дає чудові результати. Зокрема, відблиски виглядають куди реалістичніше, ніж якщо використовувати метод Гуро.

2.2 Структура даних

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

2.2.1 Джерела світла

Джерела світла не мають ніяких геометричних розмірів, вони є точковими і не малюються при рендерінгу. Інформація про джерела світла зберігається в масиві Svet. У i-му елементі масиву зберігається інформація про i-му джерелі світла. Елемент масиву представляє собою запис:

TLight = record

tip: integer;

lim: real;

Center: TPoint;

R, G, B: real;

DirX, DirY, DirZ: real;

end;

Поле tip містить інформацію про тип джерела. Якщо воно дорівнює 1, то джерело світить у всі сторони. Якщо воно дорівнює 2, то джерело світить всередині конуса, напрямна якого DirX, DirY, DirZ, а кут при вершині дорівнює 2 * Lim. Кут вимірюється в радіанах. Якщо тип джерела - 3, то джерело також світить в конусі, але в міру відхилення від утворює його інтенсивність зменшується і на вугіллі Lim дорівнює нулю.

Поле Center містить координати джерела в глобальній системі координат.

Поля R, G, B містять інтенсивність джерела по червоній, зеленій і синій компоненті. Вони можуть приймати значення від 0 до 1.

Якщо джерело першого типу, то немає необхідності вводити поля DirX, DirY, DirZ і Lim, так як вони не потрібні для розрахунку інтенсивності.

2.2.2 Об'єкти для візуалізації

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

Objects (масив об'єктів), Vse (масив трикутників), Toch (масив точок).

Масив Objects

Елемент масиву представляє собою запис:

TObj = record

StartT, EndT: integer;

StartG, EndG: integer;

XC, YC, ZC, R: real;

nnn, NPr: real;

end;

StartT, EndT відповідають індексам в масиві точок. Вони вказують, що точки з номером, більшим чи рівним StartT і меншим або рівним EndT, належать даному об'єкту.

StartG, EndG відповідають індексам в масиві трикутників. Вони вказують, що трикутники з номером, більшим чи рівним StartG і меншим або рівним EndG, належать даному об'єкту.

У NPr міститься показник заломлення даного об'єкта.

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

Масив Toch

Елемент масиву представляє собою запис:

TApex = record

X, Y, Z: real;

nx, ny, nz: real;

end;

Поля X, Y, Z містять координати точки.

Поля nx, ny, nz містять значення нормалі в даній точці. Ці поля використовуються при закраске за методом Фонга.

Масив Vse

Масив містить повну інформацію про всі трикутниках сцени.

Елемент масиву представляє собою запис:

TGran = record

Nom: array [1. .3] Of integer;

ColorR, ColorG, ColorB: Byte;

KOt, KPr, KRas, KDif, KBlik: real;

Tek: array [1. .3] Of array [1. .2] Of integer;

TNom: integer;

PaintType: boolean;

XC, YC, ZC, R: real;

O: integer;

p: real;

end;

Масив Nom містить номери точок, які є вершинами трикутника.

ColorR, ColorG, ColorB містять колір трикутника.

Поля KOt, KPr, KRas, KDif, KBlik, містять оптичні коефіцієнти поверхні трикутника.

O - номер об'єкта, якому належить даний трикутник.

XC, YC, ZC, R - координати центра та радіус сферичної оболонки трикутника.

PaintType - спосіб зафарбовування трикутника.

TNom - номер текстури, що була накладена на трикутник.

Масив Tek містить текстурні координати, кожної вершини трикутника.

Запис трикутника не містить координат вершин, вона містить посилання на вершини. Таким чином, відразу кілька трикутників, можуть посилатися на одну й ту ж вершину.

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

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

Дуже зручно повертати, об'єкти. Якщо необхідно повернути заданий об'єкт, досить пробігти по всіх його точках і змінити їх координати.

Налаштування кольору, коефіцієнтів і згладжування у кожного трикутника свої, а не однакові в усіх трикутників об'єкта. Це дає велику свободу у формуванні сцени.

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

Дана організація не має надмірністю, всі трикутники і вершини описуються рівно один раз.

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

Ієрархічні оболонки

Для зберігання ієрархічних оболонок використовується масив Shapes. Він складається із записів:

TShape = record

tip: integer;

S: integer;

G: TSpisok;

S1: integer;

G1: TSpisok;

Low: array [1. .8] Of integer;

NLow: integer;

XC, YC, ZC, R: real;

end;

Перший елемент у масиві Shapes відповідає оболонці, що включає всі трикутники сцени.

Поле tip приймає два значення: 1 і 2. Якщо в оболонки немає подоболочек, то tip дорівнює 2, в іншому випадку дорівнює 1.

G - це покажчик на список трикутників, що належать цій оболонці, S - їх число.

G 1 - це покажчик на список трикутників, які належать оболонці і дуже великі, S 1 - їх число.

Low - масив містить номери подоболочек в масиві Shapes, Nlow - число цих подоболочек.

XC, YC, ZC - координати центру цієї оболонки.

R - радіус оболонки.

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

2.2.3 Текстури

Інформація про текстурах зберігається в масиві Tex. Для кожної текстури зберігаються її розміри (lx, ly) і покажчик на область пам'яті, куди завантажена текстура (PT).

TTex = record

lx, ly: integer;

PT: PRGBI;

end

2.3 Алгоритм зворотного трасування променів

2.3.1 Опис алгоритму

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

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

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

Метод зворотного трасування променів дозволяє значно скоротити перебір світлових променів. Цей метод розробили в 80-х роках Уіттед і Кей. У цьому методі відстежуються промені не від джерел, а з камери. Таким чином, трасує певне число променів, рівне вирішенню картинки.

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

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

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

Таким чином, первинний промінь, знайшовши перетин з об'єктом, ділиться у загальному випадку на два промені (відбитий і заломлений). Далі ці два промені діляться ще на два і так далі.

Рис 1.

Головною процедурою зворотного трасування променів в моїй програмі є процедура Ray. Вона має таку структуру:

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

Визначаємо найближчий трикутник, з яким перетинається промінь.

Якщо такого трикутника немає, повертаємо колір фону, якщо є, йдемо далі.

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

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

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

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

Висвітлювати сцену можуть тільки спеціальні об'єкти - джерела світла. Вони точкові і не можуть поглинати, заломлювати і відбивати світло.

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

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

Дзеркальність теж ділиться на дві складові.

reflection - враховує відбиття від інших об'єктів (не джерел світла)

specular - враховує відблиски від джерел світла

У трасуванні не враховуються залежно від довжини хвилі світла:

коефіцієнта заломлення

коефіцієнта поглинання

коефіцієнта відбиття

Так як я не моделюю дифузне відбиття й заломлення, то не зможу отримати фонову підсвічування. Тому вводимо мінімальну фонову освітленість. Часто вона дозволяє просто значно поліпшити якість зображення.

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

У моїй програмі є можливість включити згладжування зображення. Згладжування полягає в тому, що для визначення кольору пікселя. пускається не один промінь, а чотири і визначається середнє значення кольору у цих променів. Якщо необхідно знайти колір пікселя (i, j), то пускаються 4 променя в точки екранної площини з координатами (i -0.25, j -0.25), (i -0.25, j +0.25), (i +0.25, j -0.25) , (i +0.25, j +0.25).

2.3.2 Математична основа зворотного трасування променів

Координати всіх об'єктів сцени визначені в якійсь глобальній системі координат (у тому числі і камери). Після формування первинного променя створимо підсистему, у якій центр збігається з точкою виходу променя і вісь OZ спрямована по променю. Обчислимо матрицю переходу з першої системи координат в другу. Це дозволить просто шукати перетину з трикутником, зі сферою, вектори заломлення і відбиття. При необхідності переводимо координати потрібних об'єктів в нову систему координат і працюємо вже в ній. Якщо необхідно побудувати вторинний промінь, створюємо ще одну систему координат, пов'язану з вторинним променем, і вважаємо матрицю для переходу з 2 системи в 3. Щоб отримати матрицю переходу з 1 в 3 необхідно помножити матрицю переходу з 2 в 3 помножити на матрицю переходу з 1 в 2. Таким чином, ми працюємо весь час в якійсь підсистемі. Нам не треба переводити ніякі координати назад в глобальну систему. Тому не треба і складати зворотну матрицю.

2.3.3 Складання матриці

Складання матриці перетворення з поточної системи координат до системи координат, центр якої знаходиться в точці (x, y, z) і вісь OZ якої спрямована по (dx, dy, dz). Для такого перетворення необхідно:

зробити зрушення в точку (x, y, z)

зробити поворот навколо OZ

зробити поворот навколо OX

1. Матриця зсуву: .

2. Необхідно зробити поворот навколо осі OZ за годинниковою стрілкою на кут α.

.

Матриця повороту, таким чином, буде дорівнює:

3. Необхідно зробити поворот навколо осі OX за годинниковою стрілкою на кут β.

.

Матриця повороту, таким чином, буде дорівнює:

Помноживши M 3 на M 2, а результат на M 1 отримаємо шукану матрицю переходу:

2.3.4 Програмна реалізація

У багатьох функціях і процедурах в програмі в якості вхідних і вихідних параметрів виступають матриці. Тому в програмі введений спеціальний тип:

TMatrix = Array [0. .11] Of real

Це масив з 12 елементів типу real. Він являє собою послідовно записані три верхні рядки матриці. Я не включив останню строчку, так як вона однакова у всіх матриць перетворення і дорівнює (0, 0, 0,1).

Для операцій над матрицями в програмі передбачені такі процедури:

1. Procedure MatrixAB (var Res: TMatrix; const M1, M2: TMatrix)

Процедура примножує матрицю M 1 на матрицю M 2 і поміщає результат в Res.

2. Procedure ShiftMatrix (var M: TMatrix; Z: real)

Створює матрицю переходу з поточної системи координат до системи координат, зрушену по осі OZ на z.

Процедура переміщує систему координат, що задається матрицею M, по осі OZ на z.

3. Procedure SetMatrix (var M: TMatrix; dx, dy, dz, x, y, z: real) overload

Створює матрицю переходу з поточної системи координат до системи координат, що знаходиться в точці (x, y, z), вісь OZ якої спрямована за вектором (dx, dy, dz).

4. Procedure SetMatrix (var M: TMatrix; dx, dy, dz: real) overload

Створює матрицю переходу з поточної системи координат до системи координат, вісь OZ якої спрямована за вектором (dx, dy, dz).

Перетворення координат

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

Для перетворення точки з однієї системи координат в іншу в програмі існує процедура Trans (const M: TMatrix; var F: TPoint; const V: TPoint).

У V містяться координати точки, координати якої треба перетворити.

У F містяться результат.

M - матриця перетворення.

У процедуру Ray передається тільки матриця переходу з глобальної системи координат до системи, пов'язану з променем (M i).

Процедура знаходить координати вторинного променя в новій системі координат.

Складає матрицю переходу з поточної системи в систему, пов'язану з променем (L i +1).

Примножує матриці M i +1 = L i +1 M i

Викликає рекурсивно Ray з параметром M i +1

2.3.5 Визначення перетину променя з трикутником

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

Перетворимо координату x вершин трикутника в локальну систему координат.

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

Перетворимо координату у вершин трикутника в локальну систему координат.

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

Необхідно, щоб при обході трикутника за годинниковою стрілкою точка (0,0) лежала праворуч від кожної сторони (або навпаки). Це можна встановити, перевіривши одного чи знака три векторних твори:

, , .

Якщо не одного знака, то перетинання немає, Якщо одного, то:

Перетворимо координату z вершин трикутника в локальну систему координат.

Визначаємо нормаль до трикутника, для цього помножимо векторно два вектори

і

У разі якщо, NZ дорівнює нулю, промінь паралельний осі OZ і відповідно променю. Значить, перетинання немає. В іншому випадку перетин є.

Знаходимо координати перетину.

Складемо рівняння площини, в якій знаходиться трикутник:

,

підставимо x = 0 і y = 0,

2.3.4 Формування відбитого променя



Позначимо відбитий промінь через R, вектор, спрямований проти падаючого променя - S, вектор нормалі - N. Розглянемо одиничні вектори цих векторів R 1, S 1, N 1. Так як всі три вектора знаходяться в одній площині, то можна записати R 1 + S 1 = N '. Довжина вектора N 'дорівнює 2 cos θ. Так як вектори N N 1 сонаправленние, то можна записати:

N '= N 1 лютому cosθ.

Таким чином

.

Поставимо умова, що падаючий і відбитий промені мають однакову довжину.

Так як падаючий промінь в локальній системі координат має координати (0, 0,1). Те вектор S буде мати координати (0, 0, - 1). Підставимо його координати в вираз для відбитого променя. Отримаємо

2.3.5 Формування переломленого променя



Позначимо переломлений промінь, що має одиничну довжину, через T 1. Одиничний вектор нормалі - через N 1. А вектор, спрямований протилежно падаючому променю - через S 1. Розкладемо вектор S 1 на A і N s, а вектор T 1 на B і N T. Вектор дорівнює

.

Знайдемо вектор N T. Цей вектор протилежний за напрямом вектора нормалі, а довжина його дорівнює

.

Таким чином

.

Для того, щоб визначити cosα 2, запишемо закон заломлення

.

Скористаємося тотожністю

Отримаємо

Значення для cos α 1 можна виразити через скалярний твір одиничних векторів S 1 та N 1 . З урахуванням цього можна записати вираз для вектора

N T:

Знайдемо вектор B. Він розташовується на одній прямій з вектором A, причому

.

Знайдемо відношення довжин векторів A і B:

. Звідси

.

Якщо подкоренное вираз негативно, то це відповідає повному внутрішньому віддзеркаленню. У цьому випадку переломлений промінь створюватися не буде. Зважимо на те, що вектор S дорівнює (0, 0,1).

2.4 Оболонки

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

При побудові оболонок необхідно, щоб головна оболонка цілком включала всі її подоболочкі, інакше не буде працювати правило: "Якщо промінь не перетинає головну оболонку, то він не перетинає і всі її подоболочкі". Так само при побудові оболонок бажано, щоб оболонки, що мають один порядок вкладеності, перетиналися по як можна меншого об'єму. Це поліпшить ефективність алгоритму. Метод оболонок допомагає зробити час рендеринга пропорційним Clog (n).

2.4.1 Алгоритм побудови ієрархічних оболонок

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

Знаходить мінімальний паралелепіпед, в якому знаходиться весь трикутник.

Визначає середину паралелепіпеда.

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

Далі викликається процедура Obol 2. Вона і займається власне побудовою ієрархії. Процедура створює одну оболонку, в яку записує номери всіх трикутників, сцени і викликає рекурсивну процедуру step з параметром 1. Це означає, що step обробить перші оболонку.

Процедура step:

Визначає центр і радіус сфери, яка включає в себе всі трикутники даної оболонки.

Переміщаємо подумки систему координат у центр цієї сфери. Створюємо 8 оболонок, кожна оболонка відповідає за свій октант в перенесеної системі координат.

Розподіляємо трикутники даної сфери, за цим 8 оболонок (Октант) за принципом: якщо центр сфери навколо трикутника лежить в Октант, то трикутник поміщається у відповідну оболонку.

Якщо якась оболонка виявилася порожньою (тобто якщо в неї не потрапив не один трикутник), то вона знищується.

Встановлюється зв'язок: у запис оболонки додаються номери її подоболочек.

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

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

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

2.4.2 Алгоритм обходу оболонок в трасуванні променів

Встановлюємо поточної перший оболонку.

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

Перетинаємо промінь з великими трикутниками даної оболонки.

Якщо в оболонки немає подоболочек, то шукаємо перетину з трикутниками цієї оболонки. Якщо ж у неї є подоболочкі, то викликаємо п.2 для них усіх.

При перетині оболонок з променем необхідно перетворити, центри оболонок в систему координат, пов'язану з променем.

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

2.5 Текстурування

2.5.1. Процедури для роботи з текстурами

Для роботи з текстурою передбачено 3 функції:

1. AddTeksture

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

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

була у форматі BMP

мала глибину кольору рівну 24.

Функція поверне true при успішній завантаженні текстури і false при невдачі.

2. CloseTex

Видаляє всі раніше завантажені текстури з пам'яті.

3. GetTexPoint

Ця функція дозволяє отримати 3 компоненти кольору точки текстури. Вхідними параметрами для неї є:

X і Y - координати точки текстури

Nom - номер текстури

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

Третя функція використовується безпосередньо на етапі текстурування.

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

2.5.2. Власне текстурування

Поставимо у відповідність кожному трикутнику формули перетворення координат точок трикутника в текстурні координати:

Визначимо коефіцієнти a, b, c, d, e, f.

Поставимо у відповідність кожній вершині трикутника потрібну текстурну координату.

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

Ця умова відповідає тому, що три точки трикутника лежать на одній прямій. Якщо це так, то трикутник не текстуріруем.

В іншому випадку визначаємо коефіцієнти. Точка перетину трикутника і променя має в допоміжній системі координат нульові координати X і Y.

Тому X T = C і Y T = F. Має сенс шукати тільки коефіцієнти С і F.

Далі викликається, описана вище процедура GetTexPoint, з текстурними координатами round (C) і round (F). Отримуємо колір потрібної нам точки трикутника.

2.6 Зафарбування Фонга

У програмі є можливість згладити вибірково потрібні трикутники. Для цього в атрибутах трикутника є прапор PaintType. Якщо він дорівнює True, відбувається згладжування Фонга. Якщо дорівнює False, то трикутник не згладжується. Для зручності в програмі введено дві константи Const_Paint_Fong і Const_Paint_F lat, рівні відповідно True і False. Наявність такого прапорця, робить можливим будувати практично будь-які за формою тіла.

Зафарбування Фонга полягає в наступному:

Визначаються нормалі в вершинах межі

Визначаються зовнішні нормалі у всіх граней, що містять дану вершину

Нормаль у вершині дорівнює середньому значенню нормалей прилеглих граней

Білінійної інтерполяцією обчислюється нормаль у кожному пікселі.

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

Опускаючи обчислення, визначимо с, f, e.

Обчислені значення є значеннями нормалі в точці перетину променя і трикутника.

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

2.7 Освітлення

2.7.1. Модель освітлення Уіттеда

У даній програмі я застосував модель освітлення Уіттеда. Вона задається наступною формулою:

K a - коефіцієнт розсіяного відображення.

K d - коефіцієнт дифузного відбиття.

K s - коефіцієнт дзеркальності.

K r - коефіцієнт відбиття.

K t - коефіцієнт заломлення.

I a - інтенсивність фонового освітлення.

I d - інтенсивність, що враховується для дифузного розсіювання.

I s - інтенсивність, що враховується для дзеркальності.

I r - інтенсивність випромінювання, що приходить по відбитому променю.

I t - інтенсивність випромінювання, що приходить з заломлення променю.

С - колір поверхні.

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

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

2.7.2 Дифузійне відбиття

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

, Де θ - кут між нормаллю і напрямом на джерело.

Косинус кута між двома векторами можна порахувати за формулою:

.

Відповідно cos (θ) можна порахувати за формулою

.

Так як нормаль - це одиничний вектор, то

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

2.7.3 Дзеркальне відображення

Падаючий промінь, потрапляючи на злегка шорстку поверхню реального дзеркала породжує, не один відбитий промінь, а кілька променів, що розсіюються по різних напрямах. Зона розсіювання залежить від якості полірування і може бути описана деяким законом розподілу. Як правило, форма зони розсіювання симетрична щодо лінії ідеального дзеркально відбитого променя. До числа найпростіших, але досить часто використовуваних, відноситься емпірична модель розподілу Фонга, згідно з якою інтенсивність дзеркально відбитого випромінювання пропорційна cos p α. Α - кут відхилення від лінії ідеально відображеного променя. Показник p знаходиться в діапазоні від 1 до 200 і залежить від якості полірування.

.

α - кут між вектором спостереження і вектором відображення променя з даного джерела (R і S).

Але можна поступити навпаки. Можна знайти кут між відображенням S і L, він буде дорівнює першому. Але в даній процедурі вигідно шукати кут між S і L. Це дає економію в розрахунках. Так як в допоміжній системі координат падаючий промінь (S) і вісь OZ збігаються. Тому відбитий промінь (W) шукається дуже просто:

W x =- N x * N y

W y =- N y * N z

W z = 0,5 - N z 2

Тому

Для розрахунку дзеркальності у формулі Уіттеда необхідно підсумувати всі Icos p α для кожного, видимого з даної точки, джерела.

2.7.4 Фонова освітленість

Постійна розсіяного світла вводиться для того, щоб врахувати фонову освітленість, що утворюється при вторинних і третинних відображеннях.

Повністю формула Уіттеда буде виглядати:

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

2.7.5 Прозорість

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

Проста модель.

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

Модель заломлення.

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

1 - K d - K s - K a (Part).

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

Якщо коефіцієнт заломлення об'єкта менше 10000, то визначаємо, чи відповідає кут падіння променя кутку повного внутрішнього відображення.

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

Якщо це не кут повного внутрішнього відображення, то формуються і переломлений, і відбитий промінь. Залежність між енергією переломленого і відбитого променя висловлює формула Френеля:

Вона визначає частку відбитої енергії. Частка пропущеної енергії дорівнює 1 - F. Відповідно, коефіцієнт відображення встановлюється рівним Part * F, а заломлення Part * (1 - F).

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

2.7.6 Процедури розрахунку освітленості

Розрахунок дифузної і дзеркальної складових здійснює процедура Elluminaty.

Elluminaty (const M: TMatrix; MaxN: integer; NX, NY, NZ, RX, RY, RZ: real; BodyR, BodyG, BodyB: byte; var DifR, DifG, DifB, BlikR, BlikG, BlikB: real)

Параметри функції:

BodyR, BodyG, BodyB - компоненти кольору поверхні

Dif R, Dif G, Dif B - повертаються функцією компоненти дифузного світла

Blik R, Blik G, Blik B - повертаються функцією компоненти дзеркального світла

NX, NY, NZ - нормаль до поверхні, порахована в системі координат, де Z спрямований по ходу променя, що падає на поверхню.

RX, RY, RZ - відображення падаючого на поверхню променя (вектора спостерігача).

MaxN - номер трикутника, на якому знаходиться розглянутий піксел.

M - матриця перетворення вихідної системи координат до системи координат, де Z спрямований по ходу променя, падаючого на Поверхность.

Процедура Elluminaty перебирає всі джерела світла і визначає внесок кожного джерела в підсумкову освітленість точки.

Для кожного джерела вона визначає його координати в допоміжній системі координат (T. X, T. Y, T. Z). C залишає матрицю перетворення до системи координат, в якій вісь OZ співпадає з напрямком на джерело.

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

Функція Per 2 повертає коефіцієнт, який дорівнює частці світла, який дійшов від джерела до точки. Вона перебирає трикутники, що лежать між джерелом і аналізованої точкою. Якщо зустрічається непрозорий трикутник, то функція завершується зі значенням 0. При зустрічі з прозорим об'єктом результуючий коефіцієнт множиться на прозорість трикутника.

3. Технологічна частина

3.1 Вибір мови програмування та обгрунтування вибору

Для розробки програми використовувалася мова Object Pascal. В якості середовища розробки використовувалася середу Borland Delphi 6. Вибір саме Delphi 6 був обумовлений тим, що дана середу володіє багатими можливостями для налагодження програм, а так само тим, що вона володіє великим зібранням візуальних компонент, що дозволяє зробити якісний інтерфейс.

3.2 Модульна структура програми

Програма написана за допомогою структурного підходу.

У ній міститься 6 модулей.4 модуля відносяться до модулів форм. Це модулі

Main, Model, Options, Figure. Головною формою в програмі є Main. У поле цієї форми виводиться зображення, так само за допомогою неї здійснюється виклик, інших форм. Форма Model служить для перетворень над сценою, камерою, джерелами світла. За допомогою форми Options здійснюється настроювання опцій рендерингу. Форма Figure, служить для параметричного завдання першої моделі. Так як головна форма управляє всіма іншими формами, то модулі цих форм повинні бути підключені до Main. Але крім цього всі подформи повинні мати доступ до головній формі. Тому я встановив двосторонній зв'язок між Main і модулями подформ.

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

Модуль DataControl підключається до тих модулів, в яких здійснюється введення даних з клавіатури. Модуль містить функції для перевірки правильності введення даних. Це функції IsReal і IsInt. Вони перевіряють, чи є передана ним рядок числом з плаваючою крапкою або цілим. Оскільки введення даних здійснюється у всіх формах крім Main, то модуль підключений до всіх них.

Повна структура зв'язків виглядає так:

3.3 Інтерфейс програми

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

Меню головної форми складається з пунктів: "Перетворення", "Фігура", "Опції", "Візуалізація".

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

При виборі пункту "Фігура", можна вибрати з розгорнувся списку сцену, яку необхідно зобразити.

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

При виборі пункту "Опції" на екрані, так само з'явиться форма, в якій можна змінювати параметри візуалізації.


Форма перетворень:



Форма ділиться на три частини:

верхня частина відповідає за перетворення над сценою.

середня відповідає за перетворення над камерою.

нижня дозволяє управляти джерелами освітлення.

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

Сцена.

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

Повороти можливі навколо осей OX, OY, OZ. Для кожної осі виділена своя рядок з полем для введення кута і двома кнопками. Для повороту необхідно ввести в поле, відповідне потрібної осі, кут повороту і натиснути на одну з двох кнопок. При натисканні на "+" поворот здійсниться на позитивний кут, при натисненні на "-" - на негативний кут.

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

Камера.

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

Для повороту камери вгору або вниз необхідно ввести в перше поле кут повороту і натиснути "+" для повороту вгору або "-" для повороту вниз.

Для повороту камери вліво або вправо необхідно ввести кут повороту в друге поле і натиснути "+" для повороту ліворуч або "-" для повороту ліворуч.

Для повороту камери за годинниковою стрілкою або проти годинникової діємо аналогічно, для повороту за годинниковою треба натиснути "+", проти годинникової "-".

Переміщенню камери відповідає опущений прапорець.

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

Джерела світла.

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

Знайти за допомогою стрілок потрібне джерело.

У поля характеристик джерела ввести потрібні значення.

Натиснути кнопку змінити.

Обов'язковими параметрами для всіх джерел є координати та інтенсивність по 3 складових. Якщо джерело є звичайним (тобто що світить у всі сторони), то цих параметрів досить. Якщо ж джерело світить в конусі, то необхідно ввести напрямок і кут, в якому світить джерело. Якщо джерело другого типу, то можна поставити галочку в пункті загасання. У цьому випадку інтенсивність джерела буде максимальна на твірною конуса і поступово знижується ближче до країв. На краях інтенсивність дорівнює нулю.

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


Форма опцій

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

Включено, згладжування чи ні.

Включені тіні чи ні.

Включено Чи якісне моделювання ефекту заломлення

Глибина трасування

Дозвіл одержуваного зображення

Відстань від камери до екранної площини.

Всі ці налаштування можна змінювати. Для цього потрібно ввести в поля нові значення та натиснути "OK".

4. Експериментально-дослідна частина

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

Тест № 1

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

1,43

3,45

4,53

5,24

5,76

6,06

0

10000

20000

30000

40000

50000

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

Тест № 2

Розглянемо тепер сцену, в якій отримане зображення займає не весь екран. Для цього я буду видаляти камеру від сцени. При дуже сильному видаленні сцена буде займати всього 1 піксель. Сцена буде використовуватися одна і та ж і буде складатися з 40000 трикутників. Проведемо залежність часу рендеринга від площі, займаної зображенням на екрані. Зображення буде мати розміри 800х600.

1,57

2,37

3,33

4,06

4,76

5,76

0

96000

192000

288000

384000

480000

Графік являє собою лінійну залежність. Якщо промінь не перетинає сцену, то після порівняння з найбільшою оболонкою для багатьох променів відразу ж буде встановлено, що вони нічого не перетинають. Тому час рендеринга буде визначатися часом на обробку променів, що перетинають сцену. А оскільки час (t) обробки кожного з променів в середньому однакове. Той час буде носити залежність n * t, де n - число пікселів. А це лінійна функція від n.

Тест № 3

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

1,63

110

190

230

270

300

0

10000

20000

30000

40000

50000

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

Висновок

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

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

Для прискорення використовується метод ієрархічних оболонок, що робить алгоритм трасування дуже швидким.

Крім цього в програмі:

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

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

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

Існує безліч варіантів модернізації програми.

Модернізація алгоритму трасування:

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

Додавання нових оптичних ефектів. Можна, наприклад, зробити всі оптичні властивості поверхні, що залежать від довжини хвилі падаючого світла.

Написання тривимірного редактора, який буде дозволяти:

редагувати геометрію об'єктів на сцені

редагувати властивості матеріалів

додавати і видаляти об'єкти сцени.

управляти джерелами світла.

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

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

Список літератури

  1. Роджерс Д. Алгоритмічні основи машинної графіки: пров. з англ. - М.: Світ, 1989.

  2. Порєв В.М. Комп'ютерна графіка 2004.

  3. Тихомиров Ю. Програмування тривимірної графіки. - СПб.: ІРМ - Санкт-Петербург, 1998.

  4. Гантмахер Ф.Р. Теорія матриць. - М.: Наука, 1967.

Додати в блог або на сайт

Цей текст може містити помилки.

Програмування, комп'ютери, інформатика і кібернетика | Курсова
138.1кб. | скачати


Схожі роботи:
Розробка алгоритму роботи і реалізація інтелектуальної інформаційної системи
Програмна реалізація криптографічного алгоритму шифрування з використанням відкритого тексту
Програмна реалізація алгоритму Дейкстри побудова ланцюгів мінімальної довжини
Реалізація математичних моделей використовують методи інтегрування в середовищі MATLAB
Знаходження мінімального остовом дерева Порівняння алгоритму Прима і алгоритму Крускала
Розробка алгоритму і програми для обчислення коефіцієнта оперативної готовності системи
Створення алгоритму для розстановки переносів у словах за правилами російської орфографії
Розробка алгоритму та інструментарію для виявлення професійної компетентності психолога організації
Система моделей для CADCAE верстатів
© Усі права захищені
написати до нас