| Глава 1. Введение | 5 |
| 1.1. Модель вычислений | 6 |
| 1.2. О - символика | 7 |
| 1.3. Асимптотическая эффективность | 7 |
| 1.4. Какие алгоритмы использовать? | 10 |
| 1.5. Структуры данных и запись алгоритмов | 11 |
| 1.5.1. Контейнеры | 12 |
| 1.5.2. Итераторы | 12 |
| 1.5.3. Вектор | 14 |
| 1.5.4. Список | 15 |
| 1.5.5. Ассоциированный массив | 16 |
| Глава 2. Геометрический поиск | 19 |
| 2.1. Региональный поиск подсчет | 20 |
| 2.2. Региональный поиск перечисление | 22 |
| 2.2.1. Метод сетки | 22 |
| 2.2.2. Квадратичное дерево | 24 |
| 2.2.3. 2-d Дерево | 28 |
| 2.3. Локализация точки многоугольник | 29 |
| 2.4. Локализация точки планарное разбиение | 32 |
| 2.4.1. Метод полос | 32 |
| 2.4.2. Алгоритм заметающей прямой | 33 |
| 2.4.3. Метод детализации хриангуляции | 35 |
| Глава 3. Выпуклые отсечения | 40 |
| 3.1. Двумерные отсечения | 41 |
| 3.1.1. Определение видимости отрезка | 41 |
| 3.1.2. Алгоритм Сазерченда - Коуэна для регулярного окна | 42 |
| 3.1.3. Алгоритм Лайэнга - Барски для регулярного окна | 43 |
| 3.1.4. Алгоритм Кируса Бека для выпуклого окна | 46 |
| 3.2. Трехмерные 01 сечения | 47 |
| 3.2.1. Отсечения относительно параллелепипеда | 47 |
| 3.2.2. Отсечения относительно усеченной пирамиды | 48 |
| 3.3. Отсечение многоугольников | 49 |
| Глава 4. Пересечения | 52 |
| 4.1. Пересечение выпуклых многоугольников | 52 |
| 4.2. Пересечение прямолинейных отрезков | 54 |
| 4.2.1. Нижние оценки | 54 |
| 4.2.2. Пересечение ортогональных отрезков | 55 |
| 4.2.3. Пересечение произвольных отрезков | 57 |
| Глава 5. Геометрические преобразования | 61 |
| 5.1. Линейные преобразования на плоскости | 61 |
| 5.2. Однородные координаты | 62 |
| 5.3. Композиция двумерных преобразований | 63 |
| 5.4. Эффективность вычислений | 64 |
| 5.5. Трехмерные геометрические преобразования | 65 |
| Глава 6. Построение плоских проекций | 68 |
| 6.1. Математическое описание проекций | 69 |
| 6.2. Виды и свойства параллельных проекций | 73 |
| 6.3. Виды и свойства центральных проекций | 76 |
| 6.4. Вычисление проекций | 76 |
| 6.4.1. Свойства матрицы поворота | 78 |
| 6.4.2. Вычисление параллельной проекции | 81 |
| 6.4.3. Вычисление центральных проекций | 84 |
| 6.4.4. Отсечение по границе канонического объема | 87 |
| 6.4.5. Переход к координатам физического устройства | 88 |
| Глава 7. Удаление невидимых поверхностей | 91 |
| 7.1. Алгоритм сортировки по глубине | 92 |
| 7.2. Алгоритм, использующий z -буфер | 97 |
| 7.3. Алгоритм построчного сканирования | 99 |
| 7.4. Алгоритм Варнока | 102 |
| Глава 8. Моделирование кривых и поверхностей | 104 |
| 8.1. Представление кривых в пространстве | 106 |
| 8.1.1. Общее представление кубических кривых | 107 |
| 8.1.2. Форма Эрмита | 107 |
| 8.1.3. Форма Безье | 108 |
| 8.1.4. Форма В-сплайнов | 111 |
| 8.2. Построение поверхностей | 112 |
| 8.2.1. Билинейные поверхности | 112 |
| 8.2.2. Линейчатые поверхности | 113 |
| 8.2.3. Линейные поверхности Кунса | 114 |
| 8.2.4. Кубические поверхности Кунса | 115 |
| 8.2.5. Общее представление бикубических поверхностей | 117 |
| 8.2.6. Форма Эрмита для бикубической поверхности | 117 |
| 8.2.7. Форма Безье для бикубической поверхности | 120 |
| Глава 9. Введение в реалистическую графику | 122 |
| 9.1. Простая модель освещения | 122 |
| 9.2. Зеркальная составляющая | 125 |
| 9.3. Направленный свет | 127 |
| Литература | 129 |
| Предметный указатель | 130 |