Трассировка лучей. Алгоритмы поиска пересечений

На прошлой лекции
Полигональные модели
Текстура используется как средство передачи освещения и параметров материала
Проективные текстуры
Световые поля как текстуры
Точечные модели
Подходят для сложных моделей
Проще в обработке, быстрее в визуализации
Проблема реконструкции поверхности при приближении
30 ноября 2006
Основы синтеза изображений

На лекции
Трассировка лучей.
Сравнение с алгоритмами растеризации
Методы поиска пересечений
Интерактивная трассировка лучей
30 ноября 2006
Основы синтеза изображений

ТРАССИРОВКА VS. РАСТЕРИЗАЦИЯ
Часть 1/3
30 ноября 2006
Основы синтеза изображений

Экранизация в компьютерной графике
30 ноября 2006
Основы синтеза изображений
Растеризация:
Прямая проекция геометрии
Трассировка лучей:
Обратная проекция пикселей изображения
Два основных подхода

Растеризация
30 ноября 2006
Основы синтеза изображений
Конвейер
Успешная технология
Аппаратная поддержка
Достоинства
Простой и проверенный алгоритм
Все быстрее и быстрее
Полная программируемость
уже скоро

Растеризация: особенности
30 ноября 2006
Основы синтеза изображений
Базовая операция всей компьютерной графики
Построчное сканирование по треугольнику
Последовательная обработка всех треугольников по одному
Невозможно работать более, чем с одним треугольником за раз
Но большинство реалистичных эффектов требуют доступа ко всей сцене: тени, отражения, глобальное освещение!

Генерация луча
Трассирование луча
Пересечение
Тонирование
Буфер кадра
Трассировка лучей
30 ноября 2006
Основы синтеза изображений

Генерация луча
Трассирование луча
Пересечение
Тонирование
Буфер кадра
Трассировка лучей
30 ноября 2006
Основы синтеза изображений

Генерация луча
Трассирование луча
Пересечение
Тонирование
Буфер кадра
Трассировка лучей
30 ноября 2006
Основы синтеза изображений

Трассировка лучей: трассирование луча
Генерация луча
Трассирование луча
Пересечение
Тонирование
Буфер кадра
30 ноября 2006
Основы синтеза изображений

Трассировка лучей : трассирование луча
Генерация луча
Трассирование луча
Пересечение
Тонирование
Буфер кадра
30 ноября 2006
Основы синтеза изображений

Генерация луча
Трассирование луча
Пересечение
Тонирование
Буфер кадра
Трассировка лучей
30 ноября 2006
Основы синтеза изображений

Генерация луча
Трассирование луча
Пересечение
Тонирование
Буфер кадра
Трассировка лучей
30 ноября 2006
Основы синтеза изображений

Генерация луча
Трассирование луча
Пересечение
Тонирование
Буфер кадра
Трассировка лучей
30 ноября 2006
Основы синтеза изображений

Генерация луча
Трассирование луча
Пересечение
Тонирование
Буфер кадра
Трассировка лучей
30 ноября 2006
Основы синтеза изображений

Генерация луча
Трассирование луча
Пересечение
Тонирование
Буфер кадра
Трассировка лучей
30 ноября 2006
Основы синтеза изображений

Генерация луча
Трассирование луча
Пересечение
Тонирование
Буфер кадра
Трассировка лучей
30 ноября 2006
Основы синтеза изображений

Генерация луча
Трассирование луча
Пересечение
Тонирование
Буфер кадра
Трассировка лучей
30 ноября 2006
Основы синтеза изображений

Генерация луча
Трассирование луча
Пересечение
Тонирование
Буфер кадра
Трассировка лучей
30 ноября 2006
Основы синтеза изображений

Трассировка лучей: свойства
Глобальное освещение
Параллелизм
Расширямость
Вычисления только по запросу
Попиксельные операции
30 ноября 2006
Основы синтеза изображений

Растеризация vs. Трассировка лучей
Определение: растеризация
Дан набор лучей и притимивов, вычислить подмножество лучей, пересекающихся с примитивом
2D сетка (экран) как индекс
Определение: трассировка лучей
Дан луч и набор примитивов, вычислить подмножество примитивов, пересекающихся с лучом
3D иерархическая структура как индекс
30 ноября 2006
Основы синтеза изображений

Растеризация vs. Трассировка лучей
3D индекс в мировом пространстве
Ограничивает динамику сцены (перестройка)
Масштабируемость O(log n)
Произвольные наборы лучей
2D сетка в пространстве экрана
Регулярная дискретизация
30 ноября 2006
Основы синтеза изображений

Растеризация vs. Трассировка лучей
Слияние: 2D-сетка + 3D-структура в мировом пространстве
Растеризация становится ближе к трассировке
Те же самые ограничения (динамика сцены)
Но индекс может быть менее детализированным
Вычисления делятся на аппаратные и программные
Увеличение сложности, вопросы обмена данными...
30 ноября 2006
Основы синтеза изображений

Растеризация vs. Трассировка лучей
Попиксельная эффективность
Функции тонирования имеют одинаковую сложность
Растеризация
Инкрементное вычисление между пикселями
Строчная развертка
Лишние операции из-за z-буфера (overdraw)
Трассировка
Нет инкрементных вычислений
Нет лишних операций
30 ноября 2006
Основы синтеза изображений

Растеризация vs. Трассировка лучей
Достоинства вычислений «по запросу»
Только требуемые вычисления
? эффективность
Пример: не нужно вычислять всю карту освещения
Не требуется передискретизация данных
? точность
Подгрузка данных только по требованию ? ресурсы
30 ноября 2006
Основы синтеза изображений

Растеризация vs. Трассировка лучей
Аппаратная поддержка
Растеризация имеет полную аппаратную поддержку
Быстрое развитие
Высокая производительность, параллелизм, поточная обработка
Трассировка в основном реализуется программно
Требуются гибкие потоки управления, рекурсия, гибкий ввод/вывод
Требуется виртуальная память, инкреметная подгрузка
Требуется полная поддержка циклов
Сильно зависит от кэширования
? Нет аппаратной поддержки
30 ноября 2006
Основы синтеза изображений

ОСНОВЫ ТРАССИРОВКИ И АЛГОРИТМЫ ПОИСКА ПЕРЕСЕЧЕНИЙ
Часть 2/3
30 ноября 2006
Основы синтеза изображений

Трассировка поверхностей
Предположение: пустое пространство полностью прозрачно
Поверхности
Трехмерные геометрические модели объектов
Материалы поверхностей
Отражение, поглощение, пропускание и т.п.
Освещение
Положение и характеристики источников света
30 ноября 2006
Основы синтеза изображений

Основные шаги
Генерация первичных лучей
Rays from viewpoint into 3D scene
Трассировка лучей
Первое пересечение с геометрией сцены
Тонирование
Излучение (radiance) переносится с лучом
В точке пересечения входящее излучение вычисляется с помощью дополнительных лучей
30 ноября 2006
Основы синтеза изображений

Генерация лучей
Камера-обскура
o: Центр проекции (наблюдатель)
f: Вектор зрения (фокусное расстояние)
x, y: Оконные координаты
xres, yres: Размер изображения
u
f
y
x
d
o
30 ноября 2006
Основы синтеза изображений

Ray Generation
Камера-обскура
for (x= 0; x < xres; x++)
for (y= 0; y < yres; y++)
{
d= f + 2(x/xres - 0.5)⋅x
+ 2(y/yres - 0.5)⋅y;
d= d/|d|; // Normalize
col= trace(o, d);
write_pixel(x,y,col);
}
u
f
y
x
d
o
30 ноября 2006
Основы синтеза изображений

Представления луча и объектов
Луч: r(t)=o+t d
o=(ox, oy, oz), d=(dx, dy, dz)
Геометрия сцены
Plane: (p-a)·n=0
Implicit definition (n : surface normal, a : point one surface )
Sphere: (p-c)·(p-c)-r2=0
c : sphere center, r : sphere radius
Triangles: Plane plus 2D coordinates
30 ноября 2006
Основы синтеза изображений

Пересечение луча со сферой
Сфера
Сфера в начале координат (x2 + y2 + z2 - 1= 0)
Подставляем уравнение для луча
t2(dx2 + dy2 + dz2) + 2t (dxox + dyoy + dzoz) + (ox2 + oy2 + oz2) –1 = 0
Вариант: геометрическая задача
30 ноября 2006
Основы синтеза изображений

Пересечение луча с плоскостью
Плоскость
Уравнение плоскости: p·n - D = 0, |n| = 1
Неявное представление
Нормаль: n
Перпендикуляр до (0, 0, 0): D
Заменяем o + td на p
(o + td)·n – D = 0
Решаем для t:
30 ноября 2006
Основы синтеза изображений

Пересечение луча с треугольником
Барицентрические координаты
Невырожденный трк. ABC
P= λ1A + λ2B + λ3C
λ1 + λ2 + λ3 = 1
λ3 = ∠(APB) / ∠(ACB) etc
Relative area
Пересечение, если все λi >= 0
30 ноября 2006
Основы синтеза изображений

Пересечение луча с треугольником
Пересечение с плоскостью треугольника
Дана 3D-точка пересечения
Спроецировать точку на плоскость xy, xz, yz
Можно использовать любую
плоскостью
Плоскость и 2D-положения
вершин можно вычислить
заранее
Провести барицентрический
тест
30 ноября 2006
Основы синтеза изображений

Проблема точности
30 ноября 2006
Основы синтеза изображений

Ускорение трассировки
Пересечение луча со всеми объектами и сортировка для поиска ближайшего пересечения
Очень дорого!
Ускорение алгоритма пересечения
Небольшой эффект
Уменьшение количества пересечений
Разбиение пространства (часто иерархическое)
Сетки, октодеревья, BSD и kd-деревья, деревья ограничивающих объемов
5D разбиение (позиция и направление)
30 ноября 2006
Основы синтеза изображений

Сетки
Построение сетки
Начинаем с описывающего
параллелепипеда
Треугольники разбиваются
по вокселям
Трассировка
Алгоритм Брезенхема в 3D
Останавливаемся, если
пересечение найдено в
текущем вокселе
30 ноября 2006
Основы синтеза изображений

Сетка: проблемы
Обход сетки
Перечисление вокселей вдоль луча
Очень простой алгоритм, возможна аппаратная реализация
Разрешение сетки
Очень сильно зависит от сцены
Невозможна адаптация к локальной плотности примитивов
Проблема «Чайника на стадионе»
Возможное решение: иерархические сетки
30 ноября 2006
Основы синтеза изображений

Сетка: проблемы
Объекты в нескольких вокселях
Хранить только ссылки на объекты
Хранить информацию о найденных пересечениях в кэше
Предел: хранить индекс луча в каждом треугольнике
30 ноября 2006
Основы синтеза изображений

Иерархические сетки
Простой алгоритм построения
Рекурсивное создание сеток
в вокселях
с высокой плотностью
Проблема: какое должно быть
разрешение на каждом уровне?
Улучшения алгоритма
Разделить сетки для объектов
Проблема: что считать
объектами?
30 ноября 2006
Основы синтеза изображений

Октодерево
Иерархическое разбиение пространства
Адаптивное рекурсивное разбиние
пространства на 8 равных частей
Проблемы
Достаточно сложный алгоритм
обхода
Сложные регионы сходятся
медленно
30 ноября 2006
Основы синтеза изображений

Описывающие объемы
Идея
Вычислять пересечение с объектом только
если луч пересекает простой описывающий
объем
Возможные описывающие объемы:
Сфера
Выровненный по осям описывающий
параллелепипед
Описывающий параллелепипед
30 ноября 2006
Основы синтеза изображений

Иерархия описывающих сфер
Идея:
Разбиваем
рекурсивно
Преимущества:
Очень хорошая адаптивность
Эффективный обход O(log N)
Проблемы
Как располагать описывающие объемы?
30 ноября 2006
Основы синтеза изображений

BSP- и Kd-деревья
Рекурсивное разбиение пространства
на полупространства
Двоичное разбиение пространства
(BSP):
Разбиение плоскостями в произвольных
положениях
Kd-деревья
Разбиение выровненными
относительно осей плоскостями
1
1.1
1.1.1
1.2
1.1.2
1.1.2.1
1.1.1.1
30 ноября 2006
Основы синтеза изображений

Построение kD-дерева
30 ноября 2006
Основы синтеза изображений

Построение kD-дерева
30 ноября 2006
Основы синтеза изображений

Построение kD-дерева
30 ноября 2006
Основы синтеза изображений

Построение kD-дерева
30 ноября 2006
Основы синтеза изображений

ТРАССИРОВКА: ИНТЕРАКТИВНАЯ ТРАССИРОВКА
30 ноября 2006
Основы синтеза изображений

Интерактивная трассировка лучей
В: Что такое интерактивная трассировка лучей?
О: Это обычная трассировка + оптимизации, оптимизации, оптимизации...
Оптимизации могут быть и алгоритмическими!
30 ноября 2006
Основы синтеза изображений

Что можно оптимизировать?
1. Построение пространственного индекса
2. Алгоритм трассирования луча
3. Вычисление освещения
30 ноября 2006
Основы синтеза изображений

Оптимизации: построение пространственного индекса
kD-деревья
Адаптивны
Компактны
Быстрый обход
За счет хорошо построенного дерева можно получить увеличение скорости
в несколько раз!
Проблема: где провести разбивающую плоскость?
Учет вероятностей попадания луча в разные полуплоскости
Проблема: где остановить разбиение?
30 ноября 2006
Основы синтеза изображений

Оптимизации: Алгоритм трассирования луча
Оптимизация структуры данных для узла дерева
Учет процессорного кэша
Оптимизация цикла трассировки
Никаких рекурсий
Минимизация операцией со стеком
Параллелизация: SIMD, многоядерность
Когерентность
30 ноября 2006
Основы синтеза изображений

Оптимизации: Алгоритм трассирования луча
Трассировка луча все равно очень дорога
Два варианта:
Трассировать больше лучей в секунду
рассмотрели
Трассировать меньше лучей на кадр
Использование растеризационной аппаратуры
Технологии на основе изображений
Интерполяция результатов трассирования
30 ноября 2006
Основы синтеза изображений

Алгоритм трассирования луча: корректирующие текстуры
30 ноября 2006
Основы синтеза изображений

Оптимизации: Вычисление освещения
Проблема: вычисление интеграла
Подходы:
Квази-статические (квази Монте-Карло)
Гибридные
Использование растеризационной аппаратуры
Технологии на основе изображений
30 ноября 2006
Основы синтеза изображений

Почему сейчас?
Успех растеризации и отсутствие прогресса остановили развитие алгоритмов трассировки лучей в 90е
Мало низкоуровневой оптимизации, не использовалась когерентность и т.п.
В начале 2000х развитие алгоритмов позволило догнать аппаратные методы
За счет софтверной оптимизации
В основном на сложных сценах
Сейчас программируемые аппаратные ускорители позволили еще более ускорить трассировку
Все равно неудобно – ориентация на растеризацию
Надежды на следующее поколение
30 ноября 2006
Основы синтеза изображений

Причины использования интерактивной трассировки
Реалистичные изображения по умолчанию
Физическая корректность
Поддержка массивных сцен
Интеграция различных типов примитивов
Декларативное описание сцен
Интерактивное глобальное освещение
30 ноября 2006
Основы синтеза изображений

Реалистичные изображения по умолчанию
Volkswagen Beetle with correct shadows and (multi-)reflections on curved surfaces
30 ноября 2006
Основы синтеза изображений

Физическая корректность
Fully ray traced car head lamp, faithful visualization requires up to 50 rays per pixel
30 ноября 2006
Основы синтеза изображений

Физическая корректность
Rendered directly from trimmed NURBS surfaces, with smooth environment lighting
30 ноября 2006
Основы синтеза изображений

Физическая корректность
BTF Data Courtesy R. Klein, Uni Bonn
Rendered with accurately measured BTF data
that accounts for micro lighting effects
Textured Phong for
comparison
30 ноября 2006
Основы синтеза изображений

Физическая корректность
VR scene illuminated from realtime video feed, AR with realtime environment lighting
30 ноября 2006
Основы синтеза изображений

Поддержка массивных сцен
30 ноября 2006
Основы синтеза изображений

Интеграция различных типов примитивов
Triangles, Bezier splines, and subdivision surfaces fully integrated
30 ноября 2006
Основы синтеза изображений

Интеграция различных типов примитивов
Volume visualization using multiple iso-surfaces in combination with surface rendering
30 ноября 2006
Основы синтеза изображений

Интеграция различных типов примитивов
Realtime ray tracing of point clouds (1 Mpoints each)
On one dual-Opteron 2.4 GHz: 4-9 fps
24 MPoints, 2.1 fps with shadow @ 640x480
30 ноября 2006
Основы синтеза изображений

Декларативное описание сцен
Декларативный интерфейс задания сцены
Приложение задает всю сцену за раз
Экранизация полностью выполняется на уровне трассировщика (например, в железе)
Достоинства
Сильно упрощает программирование
Возможно полное аппаратное ускорение
30 ноября 2006
Основы синтеза изображений

Глобальное освещение
Conference room (380 000 tris, 104 lights) with full global illumination in realtime
30 ноября 2006
Основы синтеза изображений

Глобальное освещение
250k / 3 fps
25M / 11 fps
Light pattern from a car head lamp computed in realtime using photon mapping:
Left: realtime update, middle: accumulated in 30s, right: photograph of real pattern
30 ноября 2006
Основы синтеза изображений

Глобальное освещение
250k / 3 fps
25M / 11 fps
Photograph
Light pattern from a car head lamp computed in realtime using photon mapping:
Left: realtime update, middle: accumulated in 30s, right: photograph of real pattern
30 ноября 2006
Основы синтеза изображений

Проблемы интерактивной трассировки лучей
Динамические сцены
Изменения геометрии ? обновление пространственного индекса
Подходы
Деление сцен исходя из темпоральных характеристик
«Ленивый» индекс
30 ноября 2006
Основы синтеза изображений

Проблемы интерактивной трассировки лучей
Эффективное устранение ступенчатости и блестящие (glossy) отражения
Нужно много лучей для корректного результата
30 ноября 2006
Основы синтеза изображений

Проблемы интерактивной трассировки лучей
Аппаратная поддержка
Сейчас вся mainstream-поддержка разрабатывается под растеризацию
Возможные решения
Многоядерные CPU – перспективно!
Cell: Нет кэша
GPU: ограничения на поток управления
Специальная аппаратура
30 ноября 2006
Основы синтеза изображений

Итоги
Трассировка лучей = быстрый поиск пересечения
Трассировка vs. Растеризация
Интерактивная трассировка лучей = оптимизация
30 ноября 2006
Основы синтеза изображений