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

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

Алексей Игнатенко
Лекция 8
30 ноября 2006

2. На прошлой лекции

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

3. На лекции

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

4. Трассировка vs. растеризация

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

5. Экранизация в компьютерной графике

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

6. Растеризация

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

7. Растеризация: особенности

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

8. Трассировка лучей

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

9. Трассировка лучей

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

10. Трассировка лучей

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

11. Трассировка лучей: трассирование луча

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

12. Трассировка лучей : трассирование луча

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

13. Трассировка лучей

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

14. Трассировка лучей

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

15. Трассировка лучей

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

16. Трассировка лучей

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

17. Трассировка лучей

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

18. Трассировка лучей

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

19. Трассировка лучей

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

20. Трассировка лучей

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

21. Трассировка лучей: свойства

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

22. Растеризация vs. Трассировка лучей

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

23. Растеризация vs. Трассировка лучей

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

24. Растеризация vs. Трассировка лучей

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

25. Растеризация vs. Трассировка лучей

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

26. Растеризация vs. Трассировка лучей

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

27. Растеризация vs. Трассировка лучей

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

28. Основы трассировки и алгоритмы поиска пересечений

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

29. Трассировка поверхностей

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

30. Основные шаги

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

31. Генерация лучей

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

32. 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);
}
x
y
d
u
f
o
30 ноября 2006
Основы синтеза изображений
32

33. Представления луча и объектов

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

34. Пересечение луча со сферой

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

35. Пересечение луча с плоскостью

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

36. Пересечение луча с треугольником

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

37. Пересечение луча с треугольником

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

38. Проблема точности

30 ноября 2006
Основы синтеза изображений
38

39. Ускорение трассировки

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

40. Сетки

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

41. Сетка: проблемы

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

42. Сетка: проблемы

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

43. Иерархические сетки

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

44. Октодерево

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

45. Описывающие объемы

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

46. Иерархия описывающих сфер

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

47. BSP- и Kd-деревья

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

48. Построение kD-дерева

30 ноября 2006
Основы синтеза изображений
48

49. Построение kD-дерева

30 ноября 2006
Основы синтеза изображений
49

50. Построение kD-дерева

30 ноября 2006
Основы синтеза изображений
50

51. Построение kD-дерева

30 ноября 2006
Основы синтеза изображений
51

52. Трассировка: интерактивная трассировка

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

53. Интерактивная трассировка лучей

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

54. Что можно оптимизировать?

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

55. Оптимизации: построение пространственного индекса

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

56. Оптимизации: Алгоритм трассирования луча

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

57. Оптимизации: Алгоритм трассирования луча

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

58. Алгоритм трассирования луча: корректирующие текстуры

30 ноября 2006
Основы синтеза изображений
58

59. Оптимизации: Вычисление освещения

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

60. Почему сейчас?

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

61. Причины использования интерактивной трассировки

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

62. Реалистичные изображения по умолчанию

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

63. Физическая корректность

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

64. Физическая корректность

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

65. Физическая корректность

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

66. Физическая корректность

ноября 2006
66
Основы синтеза изображений
VR30scene
illuminated from realtime
video feed, AR with realtime environment lighting

67. Поддержка массивных сцен

30 ноября 2006
Основы синтеза изображений
67

68. Интеграция различных типов примитивов

30 ноября 2006
Основы синтеза изображений
Triangles, Bezier splines,
and subdivision surfaces fully integrated
68

69. Интеграция различных типов примитивов

Volume
visualization
using multiple
iso-surfaces
in combination with surface rendering
30 ноября
2006
69
Основы
синтеза изображений

70. Интеграция различных типов примитивов

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

71. Декларативное описание сцен

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

72. Глобальное освещение

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

73. Глобальное освещение

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
73
Основы синтеза изображений

74. Глобальное освещение

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
74
Основы синтеза изображений

75. Проблемы интерактивной трассировки лучей

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

76. Проблемы интерактивной трассировки лучей

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

77. Проблемы интерактивной трассировки лучей

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

78. Итоги

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

79. Материалы

В презентации использованы слайды из
курса “Interactive Ray Tracing”,
представленнего на конференции
SIGGRAPH’2005
30 ноября 2006
Основы синтеза изображений
79