Содержание

1. Аннотация
2. Постановка проблемы
3. Анализ литературы
4. Постановка задачи исследования
5. Решение задач и результаты исследований
6. Результаты
7. Выводы
8. Список литературы

1. Аннотация

Разработан алгоритм трассировки лучей для реалистичной визуализации трехмерных сцен. Использован метод сеточного разделения для уменьшения сложности алгоритма. Проанализированы результаты работы для различных конфигураций и найдены оптимальные значения.

2. Постановка проблемы

Задачи реалистичной визуализации и генерации статических и динамических изображений объектов и сцен в реальном времени сегодня по-прежнему не теряют своей актуальности. Из всех существующих схем рендеринга трехмерных сцен трассировка лучей дает наиболее высокоточный визуальный эффект.

3. Анализ литературы

Изучен и реализован алгоритм трассировки лучей Вайтеда [1], для уменьшения вычислительной сложности был реализован метод сеточного разделения [2], для решения задачи определения, через какие подпространства проходит луч, использовался алгоритм 3DDA — модификация алгоритма Fujimoto [3].

Цель статьи — модификация алгоритма трассировки лучей для уменьшения его вычислительной сложности и его программная реализация.

4. Постановка задачи исследования

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

5. Решение задач и результаты исследований

Для трассировки лучей был применён алгоритм Вайтеда [1]. Этот алгоритм можно описать следующими действиями:

• Для каждого пикселя трассируем первичный луч в направлении V к первой видимой поверхности.
• Для каждого пересечения трассируем вторичные лучи:
  • Лучи Li в направлении источников света;
  • Отраженные лучи в направлении R;
  • Лучи преломления или проходящие лучи T

Общий вид алгоритма приведен на рисунке 1.

Поиск пересечения лучей и объектов — это наиболее трудоемкая задача и она занимает более 90% времени работы алгоритма. При стандартном использовании алгоритма трассировки лучей ищутся пересечения между лучом и каждым объектом. При этом количество вычислений можно выразить формулой:

Где 〖res〗_x*〖res〗_y — умножение разрешения экрана, что, в принципе, является количеством первичных лучей,

n_objects — количество объектов на сцене.

При этом зависимость сложности от количества объектов равна O(n). Это — довольно трудоемкая задача и ее можно упростить.

Для упрощения разделим пространство на подпространства. То есть разделим все пространство на небольшие кубы. Для трассировки луча будем рассматривать только те подпространства, через которые проходит луч. Вид сверху данного алгоритма схематически изображен на рисунке 2.

Для того, чтобы определить, через какие подпространства проходит луч, использовался алгоритм 3DDA — модификация алгоритма Fujimoto [2].

Для реализации алгоритма будем хранить, какие объекты входят подпространство. При просчете также будем идти по всем подпространствам до первого пересечения с объектом, остальные нас не будут интересовать.

Данный алгоритм достаточно прост в реализации и достаточно эффективен, однако имеет недостаток. Если объекты собираются в одной области, то использование сеточного разделения не эффективно (см. рисунок 3).

6. Результаты

Можно заметить, что данный метод становится более эффективным при большом количестве сфер. Также определено, что оптимальное количество кубов равняется 8.

7. Выводы

Разработан алгоритм трассировки лучей для реалистичной визуализации трехмерных сцен. Использован метод сеточного разделения для уменьшения сложности алгоритма. Проанализированы результаты работы для различных конфигураций. Данный метод становится более эффективным при большом количестве сфер. Определено, что оптимальное количество кубов равняется 8.

8. Список литературы

1. Don Fussel. Ray tracing. [Электронный ресурс]. — Электрон. дан.: 2013 — Режим доступа: http://www.cs.utexas.edu/~fussel/courses/cs384g/lectures/lecture09-Ray_tracing.pdf
2. Regular grid. [Электронный ресурс]. — Электрон. дан.: 2013 — Режим доступа: http://www.ray-tracing.ru/articles182.html
3. An Efficient and Robust Ray-Box Intersection Algorithm. [Электронный ресурс]. — Электрон. дан.: 2013 — Режим доступа: http://www.cs.utah.edu/~awilliam/box/box.pdf