Д.С. Котов, В.Н. Ланцов

У системах візуалізації, які використовуються в САПР, таких як AutoCAD, 3ds max, ArchiCAD і інших, застосовуються алгоритми побудови зображення, засновані на методі трасування променів або фотонів. Найбільш часто зустрічаються такі види трасування: пряма трасування променів, зворотна трасування, трасування фотонів, трасування шляхів, двунаправленная трасування шляхів, Metropolis Light Transport. У всіх випадках прорахунок зображення здійснюється за рівнянням візуалізації, представленому у вигляді суми інтегралів. Рівняння візуалізації має наступний вигляд:

Зокрема, інтеграл в рівнянні візуалізації зручно представити у вигляді суми прямого і непрямого освітлення:

,

де fr - функція двобічної розподілу відбивної здатності поверхні, Le - випущене освітлення, Li - освітлення, що приходить на поверхню.

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

В рамках даної статті ми будемо розглядати загальне освітлення в сцені як суму первинного освітлення і всього іншого освітлення - вторинного. В ході проведених дослідів стало відомо, що основну обчислювальну навантаження несе прорахунок вторинного освітлення. Для кожного первинного променя при трасуванні в ідеалі проводиться depth * samples перевірок на перетин з геометрією, де depth - глибина трасування, samples - кількість променів, знову генеруються при кожному зіткненні з геометрією сцени. З ростом глибини трасування частка вторинних відскоків зростає з геометричною прогресією. Таким чином, на прорахунок вторинного освітлення йде основна частина часу візуалізації.

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

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

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

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

Серед уже існуючих методів оптимізації роботи з геометрією варто виділити два найбільш ефективних: сортування геометрії в kd-дерево до стадії трасування і пакетна трасування променів. Використання хорошого kd -дерева дозволяє досягти кількості тестів на перетин з трикутником в середньому до 1,1-1,4 (Chaosgroup Vray Demo v1.5) для кожного променя. Показник кількості тестів променя на перетин з трикутником менше одиниці буде означати, що тест на перетин з трикутником проводиться не для кожного променя. З досвіду можна сказати, що в існуючих системах візуалізації така ситуація є недосяжною.

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

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

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

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

Розглянемо два випадки (рис. 1): типовий приклад трасування променя в сцену (а) і з використанням запропонованого методу (б).

a

b

Мал. 1. Трасування: а - класична; б - кластерна

Мал. 2. Групування променів в кластери

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

На відміну від підходів, що застосовуються в сучасних системах візуалізації, де промені трасуються рекурсивно один за іншим, пропонується лише генерувати координати нових променів, а трасування виконувати пізніше. Принцип відкладеної трасування дозволяє сказати, що ми маємо справу з деяким набором векторів, що мають свої координати, де кожен вектор - це промінь, який було збережено у вигляді набору даних, який поки не піддався операції трасування. Все це підмножина таких векторів пропонується розділяти на підкласи за ознакою напрямку, де в один клас можуть входити всі вектори, напрямок яких не перевищує даного тілесного кута в загальній для всієї множини векторів системі координат. Іншими словами, група векторів - це набір векторів, що вказують приблизно в одному і тому ж напрямку з похибкою ε. Для кожного порівняно невеликої ділянки поверхні в сцені знайдеться деякий набір променів, що вказують приблизно в одному і тому ж напрямку (якщо відбивна функція ДФОС однакова для всієї площі цієї ділянки поверхні). Отже, ці промені або деяка їх частина ймовірно потраплять на одну і ту ж поверхню при їх трасування.

Таким чином, промені пропонується класифікувати за двома ознаками:

• напрямок променя;
• початок променя.

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

Мал. 2 ілюструє групування променів в кластери.

Алгоритм роботи пропонованого підходу виглядає наступним чином:

1. На кожному проміжному етапі трасування сортувати всі промені у напрямку.

2. Розділити отримані групи променів за ознакою точки відліку.

3. Проектувати для кожної отриманої групи променів піраміду проектування в напрямку поширення даної групи променів.

4. Виділяти в тимчасовий масив все полігони, які опинилися всередині піраміди проектування даної групи променів.

5. Сортувати полігони по їх нормалям і положенню в просторі.

6. Пошук суміжних полігонів, що лежать в одній площині.

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

8. Здійснити групову трасування всієї групи променів разом.

Таким чином, даний підхід дозволяє розбити задачу візуалізації на потрібну кількість підзадач: з'являється гнучкий механізм розподілу завантаження обчислювальних ядер процесора. Кожну з отриманих підзадач можна віддати на виконання окремого обчислювальному модулю, здатному виробляти арифметичні і геометричні операції. Прикладами таких модулів можуть стати процесори x86 персональних комп'ютерів, відеочіпи від ATI і NVIDIA, що підтримують обчислення загального призначення, а також високопродуктивні комп'ютери (сервери і кластерні системи). Розбиття завдання візуалізації на деякий безліч кластерів дозволяє гнучко управляти завантаженням наявних обчислювальних потужностей.

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

Область застосування пропонованого методу: САПР, професійні пакети 3D-моделювання та візуалізації.

САПР і графіка 3`2010