Оцінка ефективності всіх алгоритмів видалення невидимих поверхонь, що обговорювалися в попередніх розділах, залежить від певних характеристик когерентності тієї сцени, на яку ведеться пошук її видимих ділянок.
На відміну від нього трасування променів є методом грубої сили (методом грубої сили прийнято називати, метод, що не враховує специфіку оброблюваного об'єкта). Головна ідея, що лежить в основі цього методу, полягає в тому, що спостерігач бачить будь-який об'єкт у вигляді испускаемого якимось джерелом світла, який падає на цей об'єкт і потім якимось шляхом доходить до спостерігача. Світло може досягти спостерігача, відбившись від поверхні, поламав або пройшовши через неї. Якщо простежити за променями світла, випущені джерелом, то можна переконатися, що вельми мало хто дійдуть до спостерігача. Отже, цей процес був би обчислювально неефективний. Аппель [15] першим запропонував відслідковувати (трассіровать) промені в зворотному напрямку, тобто від спостерігача до об'єкта, як показано на малюнку 10.20. Це метод був з успіхом реалізований у рамках дисплейної системи візуалізації твердих тіл MAGI [16]. У самій системі MAGI трасування припинялася, як тільки промінь перетинав поверхню видимого непрозорого об'єкта; тобто промінь використовувався для обробки прихованих чи видимих поверхонь. Надалі Кей [17,18] і Уиттед [16] реалізували алгоритми трасування променів з використанням загальних моделей висвітлення. Ці алгоритми враховують ефекти відображення одного об'єкта від поверхні іншого, заломлення, прозорості та затемнення. Проводитися також усунення ступінчастості. Справжнє ж обговорення обмежена прімененіемметода трасування променів для визначення видимих або прихованих поверхонь.
Рис 10.20 служить ілюстрацією алгоритму трасування променів. У цьому алгоритмі передбачається, що сцена вже перетворена в простір зображення. Перспективне перетворення не використовується. Вважається, що точка зору або спостерігач перебуває в нескінченності на позитивній півосі z. Тому всі світлові промені паралельні осі z. Кожен промінь, що виходить від спостерігача, походить через центр пікселя на растрі до сцени. Траєкторія кожного променя відстежується, щоб визначити, які саме об'єкти сцени, якщо такі існують, перетинаються з цим променем. Необхідно перевірити те що кожного об'єкта сцени з кожним променем. Якщо промінь перетинає об'єкт, то визначаються всі можливі точки перетину променя і об'єкта. Можна отримати велику кількість перетинів, якщо розглядати багато об'єктів. Ці перетину упорядковуються по глибині. Перетин з максимальним значенням z представляє видиму поверхню для даного пікселя. Атрибути цього об'єкта використовуються для визначення характеристик пікселя.
Якщо думка перебуває в нескінченності, алгоритм трасування промені лише незначно ускладнюється. Тут передбачається, що спостерігач як і раніше знаходиться на позитивно піввісь z. Картинна площину, тобто растр, перпендикулярна осі z, як показано на рис. 10.21. Завдання полягає в тому, щоб побудувати одноточечную центральну проекцію на картинну площину [1-1].
Найбільш важливим елементом алгоритму визначення видимих поверхонь шляхом трасування промені, є процедура визначення перетинань. До складу сцени можна включати будь-який об'єкт, для якого можна створити процедуру побудови перетинів. Об'єкти сцени можуть складатися з набору плоских багатокутників, багатогранників або тіл, обмежених чи визначених квадратичними або биполиномиальная параметрическими поверхнями. Оскільки 75-96% часу, затрачеваемого алгоритмом трасування променів, йде на визначення перетинів, то ефективність процедури пошуку перетинань значно впливає на продуктивність всього алгоритму. Обчислювальна вартість визначення перетинань довільній просторової прямий (променя) з одним виділеним об'єктом може надаватися високою (див. Наприклад [21]). Щоб позбутися від непотрібного пошуку перетинань, виробляється перевірка перетину променя з об'ємної оболонкою аналізованого об'єкта. І якщо промінь не перетинає оболонки, то не потрібно більше шукати перетинань цього об'єкта з променем. В якості оболонки можна використовувати прямокутний паралелепіпед або сферу.
Хоча, як показано, на рис. 10.22, використання сфери в ролі оболонки може бути неефективним, факт перетину тривимірного променя зі сферою визначається дуже просто. Зокрема, якщо відстань від центру сферичної оболонки до променя перевершує радіус цієї сфери, то промінь не перетинає оболонки. Отже, він не може перетнутися і з об'єктом.
Тому тест зі сферичної оболонкою зводиться до визначення відстані від точки до тривимірної прямий, тобто променя. Будемо використовувати параметричне представлення прямої, що проходить через точки P1 (x1, y1, z1) і P2 (x2, y2, z2), тобто .:
P (t) = P1 + (P2-P1) t з компонентами
Х = х1 + (x2-x1) t = x1 + at
y = y1 + (y2-y1) t = y1 + bt
z = z1 + (z2-z1) t = z1 + ct
Тоді мінімальна відстань d від цієї прямої до точки P0 (x0, y0, z0 одно:
Де параметр t, що визначає найближчу точку P (t) дорівнює:
T = (a (x1-x0) + b (y1-y0) + c (z1-z0)) / (a2 + b2 + c2)Якщо d2> R2, де R- радіус сферичної оболонки, то промінь не може перетнутися з об'єктом.
Виконання габаритного тесту з прямокутної оболонкою в тривимірному просторі вимагає більшого обсягу обчислень. При цьому слід перевірити те променя щонайменше трьома нескінченними площинами, обмежують прямокутну оболонку. Оскільки точки перетину можуть виявитися поза граней цього паралелепіпеда, то для кожної з них слід, крім того, зробити перевірку на охоплення чи потрапляння всередину. Отже, для трьох вимірів дослідження з прямокутної оболонкою виявляється повільнішим, ніж тест зі сферичної оболонкою.
Однією простий процедурою можна звести дослідження з прямокутної оболонкою до порівняння знаків, спрощуючи тим самим обчислення перетинів з об'єктом, а також порівняння за глибиною серед точок перетину. У цій процедурі використовуються перенесення поворотів навколо координатних осей [1-1] для того, щоб домогтися збігу променя з віссю z. Аналогічним перетворенням піддається і прямокутна оболонка об'єкта. Луч перетинає оболонку, тоді як нової перенесеної і поверненою системі координат знаки xmin і xmax, а також ymin і ymax протилежний, як показано на рис. 10.23.
Продемонструємо спрощення обчислень точок перетину на прикладі поверхні другого порядку загального виду. У довільній системі координат поверхонь другого порядку є геометричне місце точок, координати яких задовольняють рівняння: Q (x, y, z) = a1x2 + a2y2 + a3z2 + b1yz + b2xz + b3xy + c1x + c2y + c3z + d = 0
Після застосування перетворення, яке є комбінацією перенесення і повороту і використовується для суміщення променя з віссю z, те що цього променя з поверхнею, якщо воно має місце, виникає при x = 0, y = 0. Тому в загальному випадку точки перетину є рішенням рівняння: a'3z2 + c'3z2 + d = 0 тобто
Z = (- c'3sqrt (c'32-4a'3d ')) / (2a'3), де штрих зверху позначає коефіцієнти загального рівняння поверхні другого порядку після перетворення. Якщо c'3- 4a'3d '<0, то рішення виражаються комплексними числами промінь не перетинає поверхні. Якщо нескінченна поверхню другого порядку (наприклад конус або циліндр) обмежена площинами, то ці площини теж слід перетворити і перевірити на перетину. Якщо знайдено те з нескінченної обмежує площиною, то необхідно, крім того, провести перевірку потрапити всередину. Однак в реформованій системі координат цю перевірку можна провести на двовимірної проекції фігури, утвореної перетином яка обмежує площини і квадратної поверхні. Для отримання точки перетину в вихідної системі координат необхідно застосувати зворотне перетворення.
Обчислення перетину для елементів биполиномиальная параметричних поверхонь складніші. Уиттед [19] запропонував простий метод розбивки для елемента бикубической поверхні. Обчислення виконуються з елементом поверхні в його початковому положенні. Якщо промінь перетинає сферичну оболонку елемента поверхні, то цей шматок розбивається з допомогою алгоритму розбивки Кетмул. Потім промінь перевіряється на перетин зі сферичними оболонками піделементи. Якщо пересічний не виявлено, то промінь не перетинається і з самим елементом. Якщо ж промінь перетинається зі сферичною оболонкою якогось піделементи, то останній розбивається далі. Процес завершується, якщо жодна з сферичних оболонок НЕ пересічена або якщо досягнуто заздалегідь визначений їх мінімальний розмір. Ці сферичні оболонки мінімального розміру і є шуканими перетинами променя і елемента поверхні.
При реалізації перетворення, сполучає промінь з віссю z, метод розбивки можна використовувати швидше стосовно прямокутним оболонок, ніж до сферичним. Це скорочує число розбиття і збільшує ефективність алгоритму. Для параметричних поверхонь, що володіють властивістю опуклої оболонки, наприклад для поверхонь Безьє і B-сплайнів [1-1], число розбиття можна скоротити додатково зарахунок ускладнення алгоритму, якщо для поделіментов скористатися їх опуклими оболонками замість прямокутних.
Кадзи [21] розробив метод для биполиномиальная параметричних поверхонь, який не вимагає їх підрозділи. Цей метод заснований на поняттях, запозичених з алгебраїчної геометрії. Рішення які утворюються при цьому алгебраїчних рівнянь вищих ступенів знаходяться чисельно. Метод, подібний цьому, можна реалізувати в реформованій системі координат. Нагадаємо, що биполиномиальная параметричну поверхню визначається рівнянням
Q (u, w) = 0 з компонентами x = f (u, w) y = g (u, w) z = g (u, w)
У реформованій системі координат виконано умова x = y = 0. Значить, f (u, w) = 0 g (u, w) = 0
Спільне рішення цієї пари рівнянь дає значення u і w для точок перетину. Підстановка цих значень у рівняння z = h (u, w) дає компоненту z для точок перетину. Невдача спроби знайти дійсне рішення означає, що промінь не перетинає поверхню. Ступінь системи рівнянь для u і w дорівнює добутку ступенів биполиномиальная поверхонь. Бикубическая поверхню, наприклад, має шосту ступінь. Отже, в загальному випадку знадобляться чисельні методи рішення. Там, де це допустимо, для початкового наближення u і w можна використовувати перетину променя з опуклою оболонкою. Для отримання перетинів у вихідній системі координат, як і раніше, слід застосувати зворотне перетворення.
Якщо трассируемого промінь перетинає об'єкти сцени в декількох точках, то необхідно визначити видиме те. Для алгоритмів визначення видимості простих непрозорих поверхонь, які обговорюються в даному розділі, перетином з видимої поверхнею буде точка з максимальним значенням координати z. Для більш складних алгоритмів, які враховують відблиски і заломлення, ці перетину слід упорядкувати уздовж променя за відстанню від його початку. У реформованій системі координат цієї мети можна досягти простий сортуванням по z.
Алгоритм трасування променів для простих непрозорих поверхонь можна представити таким чином:
Створити список об'єктів, що містить щонайменше наступну інформацію:
Повний опис об'єкта: тип, поверхня, характеристики і т.д.
Опис сферичної оболонки: центр і радіус.
Прапор прямокутної оболонки. Якщо цей прапор піднято,
то буде виконано габаритний дослідження з прямокутної оболонкою,
якщо ж опущений, то тест виконуватися не буде. Зауважимо, що габаритний тест необхідний не для всіх об'єктів, наприклад для сфери він не потрібен.
Опис прямокутної оболонки: xmin, xmax, ymin, ymax, zmin, zmax
Для кожного трассируемого променя:
Виконати для кожного об'єкта тривимірний тест зі сферичної оболонкою в вихідної системі координат. Якщо промінь перетинає цю сферу, то занести об'єкт до списку активних об'єктів.
Якщо список активних об'єктів порожній, то зобразити даний піксел з фоновим значенням інтенсивності і продовжити роботу. В іншому випадку, перенести повернути промінь те, щоб він совместился з віссю z. Запам'ятати це комбіноване перетворення.
Для кожного об'єкта зі списку активних об'єктів:
Якщо прапор прямокутної оболонки піднято, перетворити, використовуючи комбіноване перетворення, цю оболонку в систему координат, в якій перебуває промінь, і відповідний тест. Якщо перетину з променем немає, то перейти до наступної пісні. В іншому випадку перетворити, використовуючи комбіноване перетворення, об'єкт в систему координат, в якій перебуває промінь, і визначити його перетину з променем, якщо вони існують. Занести всі перетину в список перетинань.
Якщо список перетинань порожній, то зобразити даний піксел з фоновим значенням інтенсивності.
В іншому випадку визначити zmax для списку перетинів.
Обчислити перетворення, зворотне комбінованому перетворенню.
Використовуючи це зворотне перетворення, визначити точку перетину в вихідної системі координат.
Зобразити даний піксел, використовуючи атрибути пересеченного об'єкта і відповідну модель освітленості.
Зауважимо, що алгоритм визначення видимості простих непрозорих поверхонь, не вимагає обраховувати перетворення, зворотне комбінованому, або визначати точку перетину в вихідної системі координат, тоді як моделі висвітлення немає необхідність включення в алгоритм властивостей поверхні об'єкта або її орієнтації в точці перетину. Ці кроки включені в даний алгоритм для повноти і зручності при реалізації алгоритму трасування променів з урахуванням загальної моделі освітленості. Більш повно наведені міркування проілюструємо на прикладі .
Дві модифікації цього простого алгоритму помітно підвищують його ефективність. Перша модифікація полягає в зрозуміти кластерних груп просторово пов'язаних об'єктів. Наприклад, припустимо, що сцена складається з столу, на якому стоять ваза з фруктами і страву з цукерками. У вазі лежать апельсин, яблуко, банан і груша. Блюдо містить кілька цукерок різних форм і кольорів. Вводяться сферичні оболонки для груп або кластерів пов'язаних об'єктів, наприклад для вази і всіх плодів в ній, для страви і всіх цукерок в ньому, а також для столу і всіх предметів на ньому. Сферичні оболонки, що охоплюють більш ніж один об'єкт, називаються сферичними кластерами. Якщо це необхідно, то можна ввести і прямокутні кластери. Вводиться, крім того, найбільший сферичний кластер, що його сферою сцени, яка охоплює всі об'єкти в цій сцені. Потім сферичні оболонки обробляються в ієрархічному порядку. Якщо промінь не перетинає сферу сцени, то він не може перетнути і жодного з її об'єктів. Отже, піксель, що відповідає цьому променю, буде зображений з фоновим значенням інтенсивності. Якщо ж промінь перетинає сферу сцени, то на те що з променем перевіряються сферичні кластери і сферичні оболонки об'єктів, які не містяться в жодному з сферичних кластерів, але належать кластеру сцени. Якщо промінь не перетинає сферичний кластер, то саме цей кластер і всі об'єкти або кластери, що містяться в ньому, виключаються з подальшого розгляду. Якщо ж промінь перетинає кластер, то ця процедура рекурсивно повторюється до тих пір, поки не будуть розглянуті всі об'єкти. Якщо промінь перетинає сферичну оболонку якогось об'єкта в який-небудь точці, то цей об'єкт заноситься в список активних об'єктів. Ця процедура значно скорочує кількість обчислень точок перетину променя зі сферичними оболонками і тим самим підвищує ефективність всього алгоритму.
Друга модіфікація вікорістовує впорядкування по пріорітету, щоб скоротіті число об'єктів, для якіх обчислюють перетин з Променя. Замість того, щоб Негайно віробляті обчислення перетин об'єкта до Променя, як це робиться у викладеня вищє простому алгорітмі, об'єкт містіться в список перетнув об'єктів. После РОЗГЛЯДУ всех об'єктів сцени Перетворення список Які перетнув об'єктів впорядковується по пріорітету Глибина ( см. алгоритм, Який вікорістовує список пріорітетів ). Для визначення пріорітетного порядку можна використовуват центри сферичних оболонок або найбільші (найменші) значення z прямокутна оболонок. Перетин променя з об'єктами зі списку Які перетнув об'єктів визначаються в порядку їх пріорітетів. На жаль, як Ранее Вказував в опісі алгоритму, что вікорістовує список пріорітетів, точка перетин променя З першого з об'єктів в упорядкованому за пріорітетамі списку Які перетнув об'єктів необов'язково буде відімої. Необходимо візначіті точки Перетин променя з усіма потенційно видимими об'єктами з багатьох {Q} (Подробиці см.в алгорітмі, что вікорістовує список пріорітетів ) І занести їх до списку перетінів. Потім модіфікованій алгоритм впорядковує цею список перетінань так, як це робілося и в простому алгорітмі. На щастя, безліч {Q} потенційно видимих об'єктів зазвичай значно менше числа об'єктів в списку перетнув променем. Отже, ефективність алгоритму зросте. Обидві ці модифікації застосовні також і до загального алгоритму трасування променів, що враховує відбиток, переломлення і.
Викладений вище простий алгоритм не використовує тієї обставини, що деякі грані багатогранника є нелицьову і їх можна відразу видалити, до уваги береться тут і можлива когерентність сцени. Наприклад, несуттєвий порядок обробки пікселів. Разом з тим розгляд цих пікселів в порядку сканування рядки розгорнення дозволило б скористатися в алгоритмі когерентністю скануючих рядків. Інший підхід може полягати в підрозділі сцени в дусі алгоритму Варнока, причому облік когерентності областей привела б до зменшення числа об'єктів, що розглядаються для кожного променя і, отже, до підвищення ефективності алгоритму. Хоча використання подібних прийомів підвищує ефективність алгоритму визначення видимості непрозорих поверхонь, їх неможливо застосувати в загальному алгоритмі трасування променів, що враховує відбиток, переломлення і. Наприклад, якщо в алгоритмі враховано відбиток, то об'єкт, який повністю закритий іншим об'єктом, може бути видимим, відбитка від третього об'єкта. Оскільки метод трасування променів є методом грубої сили, алгоритми визначення видимості непрозорих поверхонь, обговорювані в попередніх розділах, є більш ефективними, і саме ними потрібно користуватися [Експериментальні оцінки алгоритмів, описаних в попередніх розділах отримані на програмах, написаних однією мовою і запушених на одній обчислювальної системі, для однієї сцени, пов'язані між собою наступним відношенням: Трасування променів: Варнок: Уоткінс: Сканування з z-буфером: z-буфер - 9.2: 6.2: 2.1: 1.9: 1.].
Рот [20] зазначив, що алгоритм трасування променів можна використовувати також і для створення каркасних креслень суцільних тіл. При цьому передбачається, що промені народжуються у порядку, в якому відбувається сканування екрана, тобто зверху вниз і зліва направо. Що виходять процедура така:
Якщо видима поверхня для Пиксел (x, у) відповідає фону чи відрізняється від видимої поверхні для Пиксел (x-1, у) або для Пиксел (х, у-1), то зобразити цей піксел. В іншому випадку піксель не зображати.
Алгоритм трасування променів можна використовувати, крім того, для визначення фізичних властивостей суцільного тіла. Повний розгляд цього питання не входить у завдання цієї книги. Однак для ілюстрації цього підходу наведемо один приклад. Зокрема, обсяг будь-якого суцільного тіла можна визначити, аппроксимируя його сумою маленьких прямокутних паралелепіпедів. Це можна зробити, породивши безліч паралельних променів, розташованих на певних відстанях один від одного. Точки перетину кожного променя з заданим об'ємом обчислюються і упорядковуються вздовж напрямку цього променя. Якщо піддати промінь переносу, що сполучає його з віссю z, як це було описано вище, то обсяг кожного прямокутного паралелепіпеда дорівнюватиме:
V = lxly [(z1-z2) + (z3-z4) + ... + (zn-1-zn)]
де lx і ly. - відстань між променями по горизонталі і вертикалі відповідно. Кожне складова (zi-1-zi) є ділянку променя, внутрішній заданого тіла. Обсяг тіла, отже, дорівнює сумі обсягів усіх таких прямокутних паралелепіпедів. Точність результатів залежить від кількості використаних променів. Точність можна підвищити, помірковано збільшивши обсяг обчислень і рекурсивно зменшивши розмір "пікселя", в тому випадку, якщо обсяги суміжних прямокутних паралелепіпедів різняться понад заздалегідь задану величину. При такому підході точніше визначаються обсяги тих елементів тіла, де мають місце швидкі зміни, наприклад в околицях ребер тіл, обмежених криволінійними поверхнями.
З огляду на внутрішньо властивою алгоритму трасування променів паралельності обчислень (тут все промені обробляються однаково і незалежно один від одного) його можна реалізувати апаратно на основі надвеликих інтегральних схем (НВІС) з використанням методів паралельної обробки.