Основи алгоритму трасування променів
При рендеринг методом трасування променів виникає проблема так званих «драбинка» на межах об'єктів і текстур. Джерело проблеми полягає в тому, що ми намагаємося аналітичну функцію дискретизувати із деяким постійним кроком звітів. Це призводить до неминучої втрати даних і, як наслідок, втрати якості зображення. Процес усунення таких драбин називається Anti-Aliasing.
No AA
З AA
Full Screen Anti Aliasing. Метод, що полягає у збільшенні частоти звітів під час дискретизації функції. Найбільш незграбний спосіб - відрендерити картинку N разів з невеликим зміщенням спостерігача щодо вихідної точки, результат усереднити. Структура алгоритму трасування променів дозволяє зробити це трохи інакше. Можна виконувати субпіксельний рендеринг (замість одного променя на піксель посилати N, розподілених по рівномірній сітці всередині пікселя). Результат знову ж таки середнювати. По суті, результат близький до того, що ми генеруємо картинку високої чіткості, а потім масштабуємо її до заданого дозволу з розмиттям. Плюси:
Адаптивний АА
Суть полягає в тому, щоб прораховувати додаткові промені тільки там, де це дійсно потрібно. Адаптивне згладжування виконується за кілька кроків. Спочатку нам треба відрендерити зображення у звичайній якості. Потім слід визначити області, де потрібно зробити уточнений перерахунок. Зазвичай такими областями є межі об'єктів або краї не текстури. Для їх визначення використовується, найчастіше, оператор Собеля Лінійна згортка зображення з таким ядром дає на виході карту вертикальних країв (для горизонтальних операторів треба транспонувати) зображення.
Упікселях, де інтенсивність карти більша за деякий поріг — проводиться уточнення.
Ну і для вірності, результат порога трохи розширити, щоб обрахувати сусідні пікселі.
Таким чином, можна отримувати більш продуктивне згладжування.
Мінусами даного алогоритма і те, що він погано працює на схожих областях.
Ambient Occlusion
Один із методів глобального освітлення, також іноді званий SkyLight. Ідея полягає в тому, що ми використовуємо небо як джерело світла. Чим більше неба видно з точки, в якій ми розраховуємо освітлення, тим більше ця точка освітлена. Формально метод можна описати інтегралом по півсфері навколо точки: ,
де - функція видимості неба з точки z у напрямку r, що дорівнює 1, якщо є пряма видимість і 0 в іншому випадку. Для обчислення цього інтеграла користуються різними техніками, найпоширенішим є метод Монте-Карло (інтегрування з випадкових променів).
Ambient Occlusion дає приємний результат навіть сам по собі, без застосування прямого освітлення, але дуже трудомісткий у обчисленні. Тому для обчислення AO краще використовувати kd-дерева, які суттєво прискорюють пошук перетинів.
Kd(imensional)-tree – це багатовимірне дерево, яке використовується для опису структури сцени. Використання закладеної сцену інформації про становище об'єктів істотно прискорює обробку. Ідея полягає в тому, що ми ділимо простір площиною навпіл, далі лівий напівпростір і правий рекурсивний. Поступово ми таким чином розділимо наш простір надеякі блоки, що не перетинаються. Знаючи напрямок променя ми можемо визначити, які блоки перетне наш промінь, і шукати перетину тільки з тими об'єктами, які потрапили до цих блоків. Таким чином, ми істотно прискорюємо обробку перетинів променів.
Побудова kd-tree
Можна розглянути кілька способів побудови дерев. Вони різняться між собою складністю розрахунків та обчислювальною ефективністю.
Октодерево
В цілому октодерево добре себе показує лише тоді, коли об'єкти рівномірно розподілені по блоку, але це досить рідкісна ситуація. Проте воно показує хороші результати, як прискорююча структура при трасуванні променів.
Використання Surface Area Heuristic метрики дозволяє швидко відкидати порожні області у блоці. Ідея методу у тому, що вводиться вартість обробки блоку, розділеного площиною x. , де - час (вартість) обробки порожнього блоку; - час розрахунку перетинів ( ); - відносна площа лівого підблоку; - те саме для правого; - кількість об'єктів у лівому підблоці; — те саме у правому підблоці.
Тоді мінімум вартості буде найкращим розбиттям блоку з погляду продуктивності. Щоб не виконувати повний перебір площин, можна помітити, що функція змінює своє значення лише в тих місцях, де змінюється кількість об'єктів у підблоках. Тобто на межі об'єктів. Таким чином, достатньо перебрати всього 2*N площин, щоб знайти мінімум, де N — кількість об'єктів у блоці.
Обмеженням на глибину дерева є вартість обробки блоку. Як тільки вартість обробки блоку, як цілого, дорожча за обробку двох підблоків — побудова припиняється.
Аналітично нескінченні об'єкти
Виникає питання, щоробити з аналітично нескінченними об'єктами? Подумавши, я вирішив, що найпростіше просто не враховувати їх у побудові дерева, тим самим спрощуючи процес. Зазвичай, аналітичні об'єкти мають досить просте рівняння перетину, тому витрати на ускладнення дерева можуть виявитися незрівнянно більшими, ніж витрати на обчислення перетину.
Підсумок. Алогоритм постороєнія
- Помістити об'єкти в початковий бокс - корінь дерева
- Якщо не виконано критерій зупинки побудови – продовжити
- Вибрати площину розбиття
- Виконати побудову для лівого підблоку та правого підблоку
Розбір kd-tree
Розбір дерева здійснюється рекурсивно, починаючи з кореня. Обчислюються точки перетину променя з підблоками параметричних координатах. Координата входу в блок - , виходу , перетину площини, що розділяє - .
