Посвящение...............................................................................................................9
Благодарности ........................................................................................................10
Введение ..................................................................................................................11
Глава 1. Координаты и преобразования на плоскости ................................14
Преобразования на плоскости..................................................................................20
Масштабирование .................................................................................................21
Отражение..............................................................................................................22
Поворот ..................................................................................................................23
Сдвиг.......................................................................................................................24
Составные преобразования ..................................................................................25
Использование библиотеки GLM для работы с двухмерными векторами
и матрицами ..........................................................................................................26
Комплексные числа как координаты на плоскости ................................................28
Глава 2. Основные геометрические алгоритмы на плоскости ...................30
Прямая и ее уравнение .............................................................................................31
Построение прямой, луча и отрезка по двум точкам..............................................33
Определение положения точки относительно прямой или отрезка .....................33
Определение положения круга по отношению к прямой ......................................35
Прямоугольники со сторонами, параллельными осям координат,
и их классификация по отношению к прямой ........................................................36
Нахождение расстояния от точки до ААВВ..............................................................38
Определение угла между двумя прямыми ..............................................................38
Вычисление площади треугольника и многоугольника .........................................38
Определение направления обхода многоугольника...............................................40
Проверка многоугольника на выпуклость...............................................................40
Нахождение пересечения двух прямых ...................................................................42
Нахождение пересечения двух отрезков .................................................................43
Нахождение расстояния и ближайшей точки
от заданной точки к прямой, лучу и отрезку...........................................................44
Проверка на попадание точки внутрь многоугольника .........................................45
Отсечение отрезка по выпуклому многоугольнику. Алгоритм Цируса–Бека.......47
Алгоритм отсечения Лянга–Барского......................................................................50
Отсечение многоугольника. Алгоритм Сазерленда–Ходжмана.............................52
Отсечение многоугольника по выпуклому многоугольнику .................................54
4 Содержание
Барицентрические координаты ...............................................................................54
Построение выпуклой оболочки, алгоритм Грэхема ..............................................56
Триангуляция Делоне. Диаграмма Вороного ..........................................................59
Реализация булевых операций над многоугольниками. Метод построчного
сканирования. Разложение на трапеции .................................................................65
Глава 3. Координаты и преобразования в пространстве.
Кватернионы...........................................................................................................69
Векторы и матрицы в пространстве.........................................................................69
Преобразования в пространстве. Базовые преобразования ..................................72
Пример: отражение относительно плоскости.........................................................75
Однородные координаты..........................................................................................76
Жесткие преобразования..........................................................................................78
Преобразования нормали.........................................................................................79
Проектирование. Параллельное проектирование ..................................................79
Перспективное проектирование ..............................................................................81
Углы Эйлера. Задание ориентации в пространстве ................................................83
Понятие линейного пространства и его размерности. Многомерные
векторы и преобразования .......................................................................................85
Системы координат в пространстве. Переходы между различными
системами координат................................................................................................87
Ортогонализация Грамма–Шмидта .........................................................................88
Кватернионы. Задание поворотов и ориентации в пространстве
при помощи кватернионов.......................................................................................89
Использование библиотеки GLM для работы с 3- и 4-мерными векторами
и матрицами, а также кватернионами.....................................................................92
Преобразование между кватернионом и базисом касательного
пространства..............................................................................................................93
Собственные векторы и собственные числа матрицы............................................94
Глава 4. Основные геометрические алгоритмы в пространстве ...............96
Задание прямых и плоскостей в пространстве .......................................................96
Проекция точки на прямую ......................................................................................97
Проекция точки на плоскость...................................................................................97
Задание прямой двумя точками. Задание плоскости тремя точками ...................97
Проведение плоскости через прямую и точку ........................................................98
Проверка прямых и отрезков на параллельность и перпендикулярность.
Нахождение углов между прямыми и отрезками ...................................................98
Проверка, лежит ли отрезок или прямая на заданной плоскости .........................98
Проверка, пересекает ли отрезок/луч/прямая заданную плоскость......................99
Проверка, пересекает ли луч заданный треугольник............................................100
Нахождение пересечения луча и ОBB ....................................................................101
Нахождение пересечения луча и сферы.................................................................103
Проверка, пересекает ли плоскость заданную сферу............................................105
Содержание 5
Проверка, пересекает ли плоскость заданный ААВВ............................................105
Телесный угол. Проверка на попадание в него .....................................................106
Определение, лежат ли две заданные прямые в одной плоскости......................106
Классификация двух прямых в пространстве .......................................................107
Нахождение расстояния между двумя прямыми в пространстве........................107
Проверка на пересечение двух треугольников в пространстве ...........................108
Глава 5. Структуры для работы с большими наборами
геометрических данных.....................................................................................110
Ограничивающие тела ............................................................................................110
Прямоугольный параллелепипед (ААВВ) ..........................................................111
Сфера ....................................................................................................................115
k-DOP....................................................................................................................116
Ориентированные ограничивающие прямоугольные параллелепипеды
(ОВВ).....................................................................................................................120
Иерархические структуры.......................................................................................124
Иерархия ограничивающих тел..........................................................................124
Тетрарные и восьмеричные деревья..................................................................125
kD-деревья ...........................................................................................................126
BSP-деревья..........................................................................................................131
R-деревья..............................................................................................................133
Равномерное разбиение пространства..............................................................136
Глава 6. Цвет и его представление. Работа с цветом .................................139
Цветовая модель CIE XYZ........................................................................................142
Цветовая модель RGB ..............................................................................................144
Цветовые модели CMY CMYK .................................................................................145
Цветовая модель HSV..............................................................................................147
Цветовое пространство HSL....................................................................................150
Гамма-коррекция ....................................................................................................153
Цветовые пространства Y¢uv и YCbCr.....................................................................154
Цветовые пространства L*u*v* и L*a*b*.................................................................155
Цветовое пространство sRGB..................................................................................156
Соглашения по дальнейшему использованию цветов..........................................156
Глава 7. Растеризация и растровые алгоритмы ..........................................157
Класс TgaImage и его использование .....................................................................159
Понятие связности растровой сетки. 4- и 8-связность .........................................160
Построение растрового представления отрезка. Алгоритм Брезенхейма ..........161
Алгоритм Брезенхейма для окружности................................................................166
Заполнение треугольника .......................................................................................169
Заполнение области, заданной цветом границы ..................................................174
6 Содержание
Глава 8. Удаление невидимых линий и поверхностей...............................178
Лицевые и нелицевые грани...................................................................................180
Сложность по глубине .............................................................................................182
Загораживание.........................................................................................................182
Когерентность..........................................................................................................183
Удаление невидимых линий. Алгоритм Робертса.................................................185
Понятие количественной невидимости. Алгоритм Аппеля .................................185
Удаление невидимых граней. Метод трассировки лучей .....................................188
Метод буфера глубины (z-буфера)..........................................................................189
Метод иерархического z-буфера ............................................................................191
Алгоритмы, основанные на упорядочивании. Алгоритм художника..................194
Использование BSP-деревьев для определения видимости ................................196
Метод порталов .......................................................................................................198
Множества потенциально видимых граней (PVS). Расчет PVS
при помощи порталов.............................................................................................200
Глава 9. Отражение и преломление света. Модели освещения ..............203
Немного физики ......................................................................................................203
Модель Ламберта (идеальное диффузное освещение) .........................................206
Модель Фонга...........................................................................................................207
Модель Блинна–Фонга ............................................................................................208
Изотропная модель Уорда.......................................................................................209
Модель Миннаэрта ..................................................................................................209
Модель Ломмеля–Зилиджера .................................................................................210
Модель Страусса ......................................................................................................210
Простейшая анизотропная модель ........................................................................211
Анизотропная модель Уорда...................................................................................214
Двулучевая функция отражательной способности (BRDF)...................................214
Физически корректные модели освещения ..........................................................216
Модель Орена–Найара ............................................................................................218
Модель Кука–Торранса............................................................................................221
Диффузная модель Диснея .....................................................................................223
Модель Ашихмина–Ширли.....................................................................................223
Image-based lighting.................................................................................................224
Сферические гармоники и их использование.......................................................226
Precomputed Radiance Transfer................................................................................230
Использование PRT в играх Far Cry 3 и FarCry 4....................................................231
Глава 10. Трассировка лучей ............................................................................233
Constructive Solid Geometry.....................................................................................243
Распределенная трассировка лучей .......................................................................248
Реализация спецэффектов при помощи распределенной трассировки
лучей.........................................................................................................................250
Фотонные карты ......................................................................................................254
Monte-Carlo path tracing..........................................................................................257
Содержание 7
Глава 11. Взаимодействие с оконной системой. Библиотеки
freeglut и GLFW.....................................................................................................259
Основы работы оконной системы..........................................................................259
Работа с библиотекой freeglut.................................................................................260
Инициализация ...................................................................................................260
Создание окна......................................................................................................261
Обработка сообщений.........................................................................................262
Заворачиваем freeglut в класс С++......................................................................265
Работа с библиотекой GLFW ...................................................................................266
Инициализация и обработка ошибок ................................................................266
Создание окна......................................................................................................267
Обработка сообщений.........................................................................................268
Пример работы с OpenGL при помощи библиотеки Qt 5 .....................................271
Глава 12. Основы современного OpenGL.......................................................273
Основные концепции OpenGL. Графический конвейер .......................................274
Расширения OpenGL................................................................................................277
Отсечение примитивов...........................................................................................280
Вершинный шейдер ................................................................................................280
Растеризация и система координат экрана...........................................................281
Фрагментный шейдер .............................................................................................283
Операции с фрагментами.......................................................................................284
Работа с буферами...................................................................................................284
Атрибуты вершин. Вершинные массивы, VBO, VAO .............................................285
Вершинные массивы, задание атрибутов при помощи вершинных
массивов...................................................................................................................285
Вывод примитивов..................................................................................................291
Провоцирующая вершина.......................................................................................293
Буфер трафарета и работа с ним ............................................................................294
Тест глубины ............................................................................................................295
Полупрозрачность. Смешивание цветов ...............................................................295
Текстуры и работа с ними .......................................................................................296
Работа с текстурами ................................................................................................308
Работа с шейдерами ................................................................................................308
Готовое приложение................................................................................................312
Вспомогательные классы и работа с ними ............................................................314
Глава 13. Простейшие эффекты ......................................................................318
Отражение относительно плоскости......................................................................318
Имитация отражения окружающей среды и преломления..................................320
Точечные спрайты. Системы частиц......................................................................325
Проективное текстурирование...............................................................................329
Реализация основных моделей освещения ...........................................................332
Построение теней при помощи теневых карт.......................................................334
8 Содержание
Освещение с учетом микрорельефа (bump mapping) ...........................................339
Имитация отражения окружающей среды с учетом карт нормалей ...................344
Вывод текста при помощи поля расстояний .........................................................345
Рендеринг меха........................................................................................................347
Physically Based Rendering (PBR).............................................................................352
Приложение. Язык GLSL ....................................................................................355
Основы языка...........................................................................................................355