Метод трасування променів

Головна ідея цього алгоритму була запропонована в 1968 р. А.Аппелем, а перша реалізація була виконана в 1971 р.

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

Рис. 8.7. Трасування паралельними променями

Рис. 8.8. Трасування із центральною крапкою

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

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

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

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

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

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

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

Створити список об'єктів, що містить:

- повний опис об'єкта: тип, поверхня, характеристики, тип оболонки й т.п.;

- опис оболонки: центр і радіус для сфери або шість значень для паралелепіпеда .

Для кожного трассируемого лучачи:

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

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

- Знайти перетинання з усіма активними об'єктами.

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

- У противному випадку в списку припинень знайти найближче до спостерігача (з максимальним значенням ) і визначити атрибути крапки.

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

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

Питання й вправи

- У чому полягає суть видалення невидимих ліній і поверхонь?

- У якому просторі працює алгоритм Робертса?

- Для яких об'єктів приміриться алгоритм Робертса?

- Що являє собою вектор-стовпець узагальненої матриці опису багатогранника?

- Як інтерпретується вираження ( - узагальнена матриця) в алгоритмі Робертса?

- У якому просторі працює алгоритм Варнока?

- Які типи розташування багатокутника щодо вікна розглядаються в алгоритмі Варнока?

- Який із шести кроків алгоритму вирішує завдання про видалення невидимих поверхонь?

- У якому просторі працює алгоритм Вейлера-Азертона?

- У чому принципова відмінність алгоритму Вейлера-Азертона від алгоритму Варнока?

- Яке узагальнення алгоритму Вейлера-Азертона запропонував Кэтмул?

- Ким запропонований алгоритм Z-Буфера?

- У чому недоліки алгоритму Z-Буфера?

- На чому засновані методи пріоритетів?

- Для якого виду зображення розроблений метод художника?

- Для якого виду зображення розроблений метод плаваючого обрію?

- Що загального між алгоритмом порядкового сканування й методом Z-Буфера?

- У чому складається ідея методу трасування?

- Які бувають види трасування?

- Які прийоми використовуються для підвищення ефективності алгоритму трасування?