Обложка
Введение
Необходимая подготовка по программированию
Философия книги
Использование OpenGL
Использование C++ в качестве языка программирования
Акцент на трехмерной компьютерной графике
Описание 3D-сцен с помощью языка проектирования сцен
Дополнительное использование PostScript
Структура книги и планы курса
Рекомендуемые последовательности изучения глав книги
Возможные планы курса
Дополнения
Благодарности
Примечание для читателя: как смотреть стереоскопические изображения
Об авторе
От издательства
Глава 1. Введение в компьютерную графику
1.2. Где используются изображения, создаваемые компьютером
1.2.2. Компьютерная графика и обработка изображений
1.2.3. Управление процессом
1.2.4. Отображение имитаций
1.2.5. Автоматизированное проектирование
1.2.6. Научный анализ и наглядность
1.3. Элементы изображений, создаваемых в компьютерной графике
1.3.2. Текст
1.3.3. Закрашенные области
1.3.4. Растровое изображение
1.3.5. Представление оттенков серого и других цветов в растровых 
									изображениях
1.4. Графические устройства отображения
1.4.2. Растровые отображающие устройства
1.4.3. Индексированный цвет и кодовая таблица
1.4.4. Другие устройства растрового отображения
1.4.5. Растровые устройства для изготовления твердых копий
1.5. Входные графические примитивы и устройства
1.5.2. Типы физических входных устройств
1.6. Заключение
1.7. Дополнительная литература
Глава 2. Начальная стадия: рисование фигур
2.1.2. Оконное программирование
2.1.3. Открытие окна для рисования
2.2. Рисование основных графических примитивов
2.3. Создание рисунков из линий
2.3.3. Рисование выровненных прямоугольников
2.3.4. Форматное соотношение выровненного прямоугольника
2.3.5. Закрашивание полигонов
2.3.6. Другие графические примитивы в OpenGL
2.4. Простое взаимодействие с помощью мыши и клавиатуры
2.4.2. Взаимодействие с помощью клавиатуры
2.5. Резюме
2.6. Тематические задания
Тематическое задание 2.2. Введение в систему итерируемых функций
Тематическое задание 2.3. Золотое отношение и другие жемчужины
Тематическое задание 2.4. Создание и применение файлов для ломаных 
									линий
Тематическое задание 2.5. Рисование линий и многоугольников 
									пунктиром
Тематическое задание 2.6. Редактор ломаных линий
Тематическое задание 2.7. Построение и запуск лабиринтов
2.7. Дополнительная литература
Глава 3. Дополнительные инструменты для рисования
3.2. Мировые окна и порты просмотра
3.2.2. Автоматическая установка окна и порта просмотра
3.3. Отсечение линий
3.3.2. Алгоритм отсечения Кохена-Сазерленда
3.4. Разработка класса Canvas
3.4.2. Реализация класса Canvas
3.5. Относительное рисование
3.5.2. Черепашья графика
3.6. Фигуры на основе правильных многоугольников
3.6.2. Вариации п-угольников
3.7. Рисование окружностей и дуг
3.8. Применение параметрического задания кривой
3.8.2. Вычерчивание кривых, заданных параметрически
3.8.3. Суперэллипсы
3.8.4. Формы в полярных координатах
3.8.5. Трехмерные кривые
3.9. Резюме
3.10. Тематические задания
Тематическое задание 3.2. Реализация отсекателя Кохена-Сазерленда на 
									С или C++
Тематическое задание 3.3. Реализация Canvas на Turbo C++
Тематическое задание 3.4. Рисование арок
Тематическое задание 3.5. Некоторые рисунки, используемые в физике и 
									технике
Тематическое задание 3.6. Мозаики
Тематическое задание 3.7. Веселые вариации на тему
Тематическое задание 3.8. Окружности, вращающиеся вокруг окружностей
Тематическое задание 3.9. Суперэллипсы
3.11. Дополнительная литература
Глава 4. Векторные инструменты для графики
4.2. Обзор векторов
4.2.2. Линейные комбинации векторов
4.2.3. Модуль вектора; единичные векторы
4.3. Скалярное произведение
4.3.2. Угол между двумя векторами
4.3.3. Знак b•с и перпендикулярность
4.3.4. Двумерный «перп» вектор
4.3.5. Ортогональные проекции и расстояние от точки до прямой
4.3.6. Приложения проекции: отражения
4.4. Векторное произведение двух векторов
4.4.2. Нахождение нормали к плоскости
4.5. Отображение ключевых геометрических объектов
4.5.2. Аффинные комбинации точек
4.5.3. Линейная интерполяция двух точек
4.5.4. Твининг в искусстве и анимации
4.5.5. Обзор: квадратичный и кубический твининг и кривые Безье
4.5.6. Представление прямых и плоскостей
4.6. Определение точки пересечения двух отрезков прямой
4.7. Пересечения прямых с плоскостями; отсечение
4.8. Задачи о пересечениях многоугольников
4.8.2. Пересечение с лучами и отсечение для выпуклых полигонов
4.8.3. Алгоритм Сайруса-Бека
4.8.4. Отсечение границами произвольных полигонов
4.8.5. Более сложное отсечение
4.9. Резюме
4.10. Тематические задания
Тематическое задание 4.2. Разные окружности
Тематическое задание 4.3. Находится ли точка Q внутри выпуклого 
									полигона Р?
Тематическое задание 4.5. Отсечение Сайруса-Бека
Тематическое задание 4.6. Отсечение полигона границами выпуклого 
									полигона: отсечение Сазерленда-Ходгмана
Тематическое задание 4.7. Отсечение одного полигона границами 
									другого: отсечение Вейлера-Азертона
Тематическое задание 4.8. Булевы операции с полигонами
4.11. Дополнительная литература
Глава 5. Преобразования объектов
5.2. Введение в преобразования
5.2.2. Аффинные преобразования
5.2.3. Геометрические эффекты элементарных двумерных аффинных 
									преобразований
5.2.4. Инвертирование аффинного преобразования
5.2.5. Композиция аффинных преобразований
5.2.6. Примеры композиции двумерных преобразований
5.2.7. Некоторые полезные свойства аффинных преобразований
5.3. Трехмерные аффинные преобразования
5.3.2. Компонование трехмерных аффинных преобразований
5.3.3. Комбинирование поворотов
5.3.4. Краткое изложение свойств трехмерных аффинных преобразований
5.4. Изменения систем координат
5.5. Использование аффинных преобразований в программах
5.6. Рисование трехмерных сцен с применением OpenGL
5.6.2. Некоторые инструменты OpenGL для моделирования и вида
5.6.3. Рисование элементарных форм, поддерживаемых OpenGL
5.7. Резюме
5.8. Тематические задания
Тематическое задание 5.2. Рисование звезды с рисунка 5.39 с помощью 
									многократных поворотов
Тематическое задание 5.3. Разложение двумерного аффинного 
									преобразования
Тематическое задание 5.4. Обобщенные трехмерные сдвиги
Тематическое задание 5.5. Вращение вокруг оси: конструктивный подход
Тематическое задание 5.6. Разложение трехмерных аффинных 
									преобразований
Тематическое задание 5.7. Рисование трехмерных сцен, описанных на 
									языке SDL
5.9. Дополнительная литература
Глава 6. Моделирование поверхностей полигональными сетками
6.2. Введение в трехмерное моделирование полигональными сетками
6.2.2. Нахождение нормальных векторов
6.2.3. Свойства сеток
6.2.4. Каркасные модели для немонолитных объектов
6.2.5. Работа с сетками в программе
6.3. Многогранники
6.3.2. Платоновы тела
6.3.3. Другие любопытные многогранники
6.4. Экструзивные формы
6.4.2. Совокупности экструзивных призм: «кирпичная кладка»
6.4.3. Экструзии с «поворотом»
6.4.4. Создание сегментированных экструзий: трубки и змейки
6.4.5. «Дискретно» заметаемые поверхности вращения
6.5. Каркасные аппроксимации гладких объектов
6.5.2. Нормальный вектор к поверхности
6.5.3. Влияние аффинного преобразования
6.5.4. Три «базовые» формы: сфера, цилиндр и конус
6.5.5. Формирование полигональной сетки для криволинейной 
									поверхности
6.5.6. Линейчатые поверхности
6.5.7. Поверхности вращения
6.5.8. Поверхности второго порядка
6.5.9. Суперквадрики
6.5.10. Трубки на базе трехмерных кривых
6.5.11. Поверхности на базе явных функций двух переменных
6.6. Заключение
6.7. Тематические задания
Тематическое задание 6.2. Вывод метода Ньюэлла
Тематическое задание 6.3. Призма
Тематическое задание 6.4. Совокупность призм и экструдированные 
									полосы из четырехугольников
Тематическое задание 6.5. Трубки и змейки на базе параметрической 
									кривой
Тематическое задание 6.6. Построение поверхностей вращения с 
									дискретными шагами
Тематическое задание 6.7. Списки ребер и каркасные модели
Тематическое задание 6.8. Сводчатые потолки
Тематическое задание 6.9. О Платоновых телах
Тематическое задание 6.10. Об Архимедовых телах
Тематическое задание 6.11. Алгебраическая форма поверхностей второго 
									порядка
Тематическое задание 6.12. Сцены с супеквадриками
Тематическое задание 6.13. Рисование гладких параметрических 
									поверхностей
Тематическое задание 6.14. Сузить, закрутить, изогнуть и расплющить
6.8. Дополнительная литература
Глава 7. Трехмерный просмотр
7.2. Снова о камере
7.2.2. Позиционирование и ориентирование камеры
7.3. Встраивание камеры в программу
7.4. Перспективные проекции трехмерных объектов
7.4.2. Перспективная проекция прямой линии
7.4.3. Включение перспективы в графический конвейер
7.4.4. Отсечение граней границами отображаемого объема
7.5. Создание стереоизображений
7.6. Классификация проекций
7.6.2. Параллельные проекции
7.7. Резюме
7.8. Тематические задания
Тематическое задание 7.2. Стереоизображения
Тематическое задание 7.3. Создание параллельных проекций
Тематическое задание 7.5. Удаление невидимых граней для большей 
									эффективности
7.9. Дополнительная литература
Глава 8. Визуализация граней для усиления реалистичности
8.2. Введение в модели закрашивания
8.2.2. Вычисление диффузной составляющей
8.2.3. Зеркальное отражение
8.2.4. Роль фонового света
8.2.5. Комбинирование компонентов освещения
8.2.6. Добавление цвета
8.2.7. Закраска и графический конвейер
8.2.8. Использование источников света в OpenGL
8.2.9. Работа со свойствами материалов в OpenGL
8.2.10. Закраска сцен, заданных с помощью SDL
8.3. Плоское и плавное закрашивание
8.3.2. Плавное закрашивание
8.4. Удаление невидимых поверхностей
8.5. Добавление текстуры к граням
8.5.2. Визуализация текстуры
8.5.3. Что регулирует текстура?
8.5.4. Пример текстурирования с использованием OpenGL
8.5.5. Обертывание текстуры вокруг криволинейных поверхностей
8.5.6. Отображение отражений
8.6. Добавление теней объектов
8.6.2. Создание теней с помощью буфера теней
8.7. Заключение
8.8. Тематические задания
Тематическое задание 8.2. Самодельный графический конвейер
Тематическое задание 8.3. Добавление закраски полигонов и удаления 
									невидимых поверхностей при помощи буфера глубины
Тематическое задание 8.4. Визуализация текстуры
Тематическое задание 8.5. Применение процедурных ЗD-текстур
Тематическое задание 8.6. Рисование теней
Тематическое задание 8.7. Расширение SDL с целью включения 
									текстурирования
8.9. Дополнительная литература
Глава 9. Приближение к бесконечности
9.2. Фракталы и самоподобие
9.2.2. Рисование кривых и снежинок Коха
9.2.3. Дробная размерность
9.3. Создание строк и кривые Пеано
9.3.2. Разрешение ветвления
9.3.3. Добавление случайности и сужения
9.4. Замощение плоскости
9.4.2. Диэдральные мозаичные размещения
9.4.3. Рисование мозаик
9.4.4. Рептилии
9.5. Создание изображений с использованием системы итерируемых 
							функций
9.5.2. Теоретические основы процесса копирования
9.5.3. Рисование k-й итерации
9.5.4. «Игра в Хаос»
9.5.5. Нахождение системы IFS; фрактальное сжатие изображений
9.6. Множество Мандельброта
9.6.2. Определение множества Мандельброта
9.6.3. Определение того, находится ли точка с в пределах множества 
									Мандельброта
9.6.4. Рисование множества Мандельброта
9.6.5. Некоторые замечания по поводу множества Мандельброта
9.7. Множества Жюлиа
9.7.2. Рисование плотных множеств Жюлиа
9.7.3. Некоторые замечания относительно неподвижных точек и 
									бассейнов притяжения
9.7.4. Множество Жюлиа Jc
9.8. Случайные фракталы
9.8.2. Контроль за спектральной плотностью фрактальной кривой
9.9. Резюме
9.10. Тематические задания
Тематическое задание 9.2. Рисование снежинок и рептилий
Тематическое задание 9.3. «Игра в Хаос»
Тематическое задание 9.4. Рисование орбит внутри множества 
									Мандельброта
Тематическое задание 9.5. Создание изображений множества 
									Мандельброта
Тематическое задание 9.6. Создание изображений множеств Жюлиа
Тематическое задание 9.7. Непериодические мозаики; мозаики Пенроуза
Тематическое задание 9.8. Фрактализация кривых
Тематическое задание 9.9. Моделирование фрактализованных гор
9.11. Дополнительная литература
Глава 10. Средства для растровой графики
10.2. Управление пиксельными картами
10.2.2. Типы данных, используемые для пиксельных карт
10.2.3. Масштабирование и поворот изображений
10.3. Объединение пиксельных карт
10.3.2. Альфа-канал и смешивание изображений
10.3.3. Логические комбинации пиксельных карт
10.3.4. Операция BitBLT
10.4. Рисование прямых своими силами: алгоритм Брезенхема
10.5. Определение и заполнение областей из пикселов
10.5.2. Пиксельно-определенные области
10.5.3. Рекурсивный алгоритм заливки
10.5.4. Заполнение областей узорами
10.5.5. Использование связности: заполнение области на основе серий 
									пикселов
10.6. Манипулирование символически-определенными областями
10.6.2. Области, заданные контуром
10.7. Заполнение полигонально-определенных областей
10.7.2. Повышение эффективности алгоритма
10.8. Ступенчатость; технологии сглаживания
10.8.2. Сглаживание текстуры
10.8.3. Сглаживание с применением OpenGL
10.9. Увеличение количества цветов и оттенков
10.9.2. Рассеивание ошибок
10.10. Резюме
10.11. Тематические задания
Тематическое задание 10.2. Растворение одной пиксельной карты в 
									другой с помощью OpenGL
Тематическое задание 10.3. Заполнение области на основе серий
Тематическое задание 10.4. Работа со структурой данных «формы»
Тематическое задание 10.5. Цепное кодирование форм
Тематическое задание 10.6. Заполнение «горизонтально-выпуклых» 
									полигонов
Тематическое задание 10.7. Заполнение полигона общего вида
Тематическое задание 10.8. Рассеивание ошибок
10.12. Дополнительная литература
Глава 11. Создание кривых и поверхностей
11.1.2. Плавность движения
11.2. Описание кривых полиномами
11.3. Интерактивное конструирование кривых
11.4. Применение кривых Безье для построения кривых
11.5. Свойства кривых Безье
11.6. Нахождение лучших стыковочных функций
11.6.2. Список пожеланий для множества стыковочных функций
11.6.3. Кусочно-полиномиальные кривые и сплайны
11.6.5. Сплайны и базисные функции
11.7. Базисные функции В-сплайнов
11.7.2. Использование кратных узлов в узловом векторе
11.7.3. Незамкнутые В-сплайн кривые: стандартный узловой вектор
11.8. Полезные для дизайна свойства В-сплайн кривых
11.9. Рациональные сплайны и NURBS-кривые
11.10. Краткое знакомство с интерполяцией
11.10.2. Эрмитова интерполяция
11.10.3. Естественные кубические сплайны
11.10.4. Вычисление наклонов при кубической интерполяции
11.10.5. Интерактивное задание касательных векторов
11.11. Моделирование криволинейных поверхностей
11.11.2. Поверхности вращения на базе В-сплайнов
11.11.3. Лоскуты Безье
11.11.4. Сшивание лоскутов Безье
11.11.5. В-сплайн лоскуты
11.11.6. NURBS-поверхности
11.12. Резюме
11.13. Тематические задания
Тематическое задание 11.2. «Эллиптипул»
Тематическое задание 11.3. Кривые Безье
Тематическое задание 11.4. Генератор квадратичной сплайн-кривой
Тематическое задание 11.5. Создание редактора сплайн-кривых
Тематическое задание 11.6. Интерполяция контрольных точек 
							В-сплайнами
Тематическое задание 11.7. Интерполяция кубическими полиномами
Тематическое задание 11.8. Многоуважаемый чайник
Тематическое задание 11.9. Инвариантность относительно проективных 
							преобразований
Тематическое задание 11.10. Рисование NURBS-лоскутов
11.14. Дополнительная литература
Глава 12. Теория цвета
12.2. Описания цветов
12.2.2. Подбор цветов
12.3. Международная комиссия по стандартам освещенности
12.3.2. Использование хроматической CIE-диаграммы
12.3.3. Цветовые охваты
12.4. Цветовые пространства
12.4.2. Аддитивные и субтрактивные цветовые системы
12.4.3. Цветовая модель HLS
12.5. Квантование цвета
12.5.2. Алгоритм популярности
12.5.3. Алгоритм медианного сечения
12.5.4. Octree-квантование
12.6. Резюме
12.7. Тематические задания
Тематическое задание 12.2. Рисование RGB-прсстранства
Тематическое задание 12.3. Из HSV в RGB
Тематическое задание 12.4. Однородное квантование цвета
Тематическое задание 12.5. Квантование цвета по популярности
Тематическое задание 12.6. Квантование цвета методом медианного 
									сечения
Тематическое задание 12.7. Квантование цвета методом октодерева
12.8. Дополнительная литература
Глава 13. Удаление невидимых поверхностей
13.1.2. Описание данных для полигональных сеток
13.2. Снова об алгоритме буфера глубины
13.3. HSR-методы со списками приоритетов
13.3.2. HSR с использованием деревьев двоичного разбиения 
									пространства
13.3.3. Алгоритм сортировки по глубине
13.4. HSR-метод построчного сканирования
13.5. Методы разбиения области
13.5.2. Другие определения простой области
13.6. О методах удаления невидимых линий
13.7. HSR-методы для криволинейных поверхностей
13.8. Резюме
13.9. Тематические задания
Тематическое задание 13.2. Тест и разбиение
Тематическое задание 13.3. Удаление невидимых поверхностей с 
									использованием BSP-деревьев
Тематическое задание 13.4. HSR с использованием сортировки по 
									глубине
Тематическое задание 13.5. Использование HSR-метода построчного 
									сканирования
Тематическое задание 13.6. Рисование при помощи алгоритма Варнока
Тематическое задание 13.7. HLR с помощью алгоритма стека ребер
13.10. Дополнительная литература
Глава 14. Введение в трассировку лучей
14.2. Построение геометрии трассировки лучей
14.3. Обзор процесса трассировки луча
14.4. Пересечение луча с объектом
14.4.2. Пересечение с базовой сферой
14.4.3. Пересечение луча с преобразованными объектами
14.5. Организация трассировщика луча в приложении
14.5.2. Полный трассировщик лучей для сцен с излучающей сферой
14.6. Пересечение лучей с другими примитивами
14.6.2. Пересечение с коническим цилиндром
14.6.4. Добавление новых примитивов
14.7. Рисование закрашенных изображений сцен
14.7.2. Раскраска объектов в соответствии с материалами поверхностей
14.7.3. Физически обоснованные модели закраски: закрашивание 
									Кука-Торренса
14.8. Наложение текстуры на поверхности
14.8.2. Наложение изображений на поверхности
14.8.3. Сглаживающая трассировка лучей
14.9. Использование экстентов
14.9.2. Использование проекционных экстентов
14.10. Добавление теней для большей реалистичности
14.11. Отражения и прозрачность
14.12. Составные объекты: логические операции с объектами
14.12.2. Структура данных для Булевых объектов
14.12.3. Пересечения лучей с Булевыми объектами
14.12.4. Построение и использование экстентов для CGG-объектов
14.13. Резюме
14.14. Тематические задания
Тематическое задание 14.2. Усовершенствованный трассировщик лучей
Тематическое задание 14.3. Реализация теней при трассировке лучей
Тематическое задание 14.4. Использование экстентов для ускорения 
									трассировки лучей
Тематическое задание 14.5. Трассировка лучей с 3D-текстурами
Тематическое задание 14.6. Сглаживание
Тематическое задание 14.7, Трассировка лучей для других примитивов
Тематическое задание 14.8. Двумерный трассировщик лучей для работы с 
									преломлением
Тематическое задание 14.9. Отраженный и преломленный свет
Тематическое задание 14.10. Трассировка Булевых комбинаций объектов
14.15. Дополнительная литература
Приложение А. Графический инструментарий: получение OpenGL
Приложение Б. Немного математики для компьютерной графики
Б1.2. Умножение двух матриц
Б1.3. Разбиение матрицы на блоки
Б1.4. Определитель матрицы
Б1.5. Обращение матрицы
Б2. Некоторые свойства векторов и операции над ними
Б2.2. Смешанное произведение
Б2.3. Двойное векторное произведение
БЗ. Арифметика комплексных чисел
Б4. Сферические координаты и направляющие косинусы
Приложение В. Некоторые полезные классы и служебные подпрограммы
B2. RGBPixmap CLASS
B3. Класс SCENE и сопутствующие классы
B4. Класс NOISE
B5. Некоторые классы, полезные при трассировке лучей
Приложение Г. Введение в PostScript®
Г1.2. PostScript основан на стеке
Г1.3. Некоторые операции со стеком: pop, dup, exch, clear
Г1.4. Более сложные операторы работы со стеком
Г1.5. Некоторые арифметические операторы
Г2. Графические операторы в PostScript
Г2.2. Команды создания контура
Г2.3. Дуги окружностей
Г2.4. Использование операторов закрашивания
Г2.5. Преобразования координат
Г2.6. Операторы графического состояния
ГЗ. Рисование текста в PostScript
Г4. Определение новых переменных и процедур
Г4.2. Определение процедур
Г4.3. Простейшая форма итерации с использованием оператора repeat
Г5. Команды решений и итераций
Г5.2. Принятие решений
Г5.3. Итерация
Г6. Печать численных значений
Г7. Рисование полутоновых изображений
Приложение Д. Введение в SDL
Д2. Макросы в SDL
ДЗ. Расширение SDL
Литература
Список терминов
D-E-F
G-H-I-J-K
L-M-N-O-P
R-S
T-U
V-W-Y-Z
Алфавитный указатель
H-I-K-L-M-N-O
P-R-S-T-U-V-W-X-Z-А
Б-В
Г
Д-Е-Ж-З
И-К
Л
М
Н-О
П
Р
С
Т-У-Ф
Х-Ц-Ч-Ш-Щ-Э-Я
Обложка
Текст
                    I» *
О
made by Dickobraz, May-2004
ВТОРОЕ ИЗДАНИЕ


Francis S. Hill Computer Graphics Using OpenGL Second Edition ppj Prentice HaH PTR ртр lipper Seddie River, New Jersey 07458 . _www.phptr.com
Френсис Хилл "П НО' ПВОАС^МОШ-ВЛП да •* да - л . * » , < OPENGL Программирование компьютерной ГРАФИКИ Второе издание {^ППТЕР Москва Санкт-Петербург Нижний Новгород Воронеж Ростов-на-Дону • Екатеринбург • Самара Киев - Харьков Минск 2002
Френсис Хилл OpenGL. Программирование компьютерной графики Для профессионалов Второе издание Перевела с английского А. Шкадова Главный редактор Заведующий редакцией Руководитель проекта Научный редактор Литературный редактор Художник Иллюстрации Корректор Верстка Е. Строганова И. Корнеев А. Васильев А. Шкадова Е. Ваулина Н. Биржаков В. Шендерова В. Листова Р. Гришанов ББК 32.973-018.3 УДК 681.327.1 Хилл Ф. Х45 OpenGL. Программирование компьютерной графики. Для профессионалов. — СПб.: Питер, 2002. — 1088 с.: ил. ISBN 5-318-00219-6 Эта книга — введение в мир программирования компьютерной графики. Графические системы становятся лучше, быстрее и дешевле. Каждый год изобретается множество новых технических приемов, однако основные принципы и подходы к програм- мированию по-прежнему остаются неизменными. Автор написал в высшей степени практичный и доступный для восприятия текст, отличающийся основательным и интегрированным подходом. Понятия тщательно определены; их математические основы разъ- яснены, доказана важность каждого рассмотренного понятия. Книга показывает читателю, как переводить математические пред- ставления в программный код, и демонстрирует результат. Предлагаемое новое издание предоставляет самую современную инфор- мацию в области компьютерной графики. © Prentice Hall, 2001 © Перевод на русский язык, ЗАО Издательский дом «Питер», 2002 © Издание на русском языке, оформление, ЗАО Издательский дом «Питер», 2002 Права на издание получены по соглашению с Prentice Hall, Inc. Все права защищены. Никакая часть данной книги не может быть воспроизведена в какой бы то ни было форме без письменного разрешения владельцев авторских прав. Информация, содержащаяся в данной книге, получена из источников, рассматриваемых издательством как надежные. Тем не менее, имея в виду возможные человеческие или технические ошибки, издательство не может гарантировать абсолютную точность и полноту приводимых сведений и не несет ответственность за возможные ошибки, связанные с использованием книги. ISBN 5-318-00219-6 ISBN 0-02-354856-8 (англ.) ООО «Питер Принт». 196105, Санкт-Петербург, ул. Благодатная, д. 67. Лицензия ИД № 05784 от 07.09.01. Налоговая льгота — общероссийский классификатор продукции ОК 005-93, том 2; 953005 — литература учебная. Подписано в печать 06.07.02. Формат 84х108'/|6. Усл. п. л. 114,24. Тираж 4000 экз. Заказ № 815. Отпечатано с диапозитивов в ФГУП «Печатный двор» им. А. М. Горького Министерства РФ по делам печати, телерадиовещания и средств массовых коммуникаций. 197110, Санкт-Петербург, Чкаловский пр., 15.
Краткое содержание Введение................................................................... 18 Глава 1. Введение в компьютерную графику................................... 28 Глава 2. Начальная стадия: рисование фигур................................. 67 Глава 3. Дополнительные инструменты для рисования......................... 118 Глава 4. Векторные инструменты для графики................................ 192 Глава 5. Преобразования объектов.......................................... 263 Глава 6. Моделирование поверхностей полигональными сетками................ 350 Глава 7. Трехмерный просмотр.............................................. 426 Глава 8. Визуализация граней для усиления реалистичности.................. 481 Глава 9. Приближение к бесконечности...................................... 551 Глава 10. Средства для растровой графики.................................. 617 Глава 11. Создание кривых и поверхностей.................................. 689 Глава 12. Теория цвета.................................................... 770 Глава 13. Удаление невидимых поверхностей................................. 799 Глава 14. Введение в трассировку лучей.................................... 838 Приложение А. Графический инструментарий: получение OpenGL............. 939 Приложение Б. Немного математики для компьютерной графики ................ 941 Приложение В. Некоторые полезные классы и служебные подпрограммы ......... 956 Приложение Г. Введение в PostScript®......................................1001 Приложение Д. Введение в SDL...............................................1038 Литература.................................................................1046 Список терминов............................................................1058 Алфавитный указатель.......................................................1065
Содержание Введение.........................................................................................18 Предполагаемая аудитория..................................................................... 18 Необходимая математическая подготовка ................................................... 18 Необходимая подготовка по программированию............................................... 19 Философия книги.............................................................................. 19 Упражнения и задачи...................................................................... 19 Использование OpenGL..................................................................... 20 Использование C++ в качестве языка программирования...................................... 20 Акцент на трехмерной компьютерной графике................................................ 21 Описание ЗО-сцен с помощью языка проектирования сцен..................................... 21 Дополнительное использование PostScript.................................................. 21 Структура книги и планы курса................................................................ 21 Краткий обзор глав....................................................................... 22 Рекомендуемые последовательности изучения глав книги..................................... 25 Возможные планы курса.................................................................... 25 Дополнения................................................................................... 25 Благодарности................................................................................ 25 Примечание для читателя: как смотреть стереоскопические изображения.......................... 27 Об авторе.................................................................................... 27 От издательства.............................................................................. 27 Глава 1. Введение в компьютерную графику.........................................................28 1.1. Что такое компьютерная графика?......................................................... 28 1.2. Где используются изображения, создаваемые компьютером................................... 30 1.2.1. Искусство, развлечения и издательское дело........................................ 30 1.2.2. Компьютерная графика и обработка изображений...................................... 31 1.2.3. Управление процессом.............................................................. 32 1.2.4. Отображение имитаций.............................................................. 33 1.2.5. Автоматизированное проектирование................................................. 34 1.2.6. Научный анализ и наглядность...................................................... 36 1.3. Элементы изображений, создаваемых в компьютерной графике................................ 37 1.3.1. Ломаные линии..................................................................... 38 1.3.2. Текст............................................................................. 40 1.3.3. Закрашенные области .............................................................. 42 1.3.4. Растровое изображение............................................................. 43 1.3.5. Представление оттенков серого и других цветов в растровых изображениях............ 47 1.4. Графические устройства отображения...................................................... 50 1.4.1. Графические дисплеи............................................................... 51
Содержание 7 1.4.2. Растровые отображающие устройства................................................. 52 1.4.3. Индексированный цвет и кодовая таблица............................................ 56 1.4.4. Другие устройства растрового отображения.......................................... 58 1.4.5. Растровые устройства для изготовления твердых копий............................... 59 1.5. Входные графические примитивы и устройства.............................................. 61 1.5.1. Типы входных графических примитивов............................................... 61 1.5.2. Типы физических входных устройств................................................. 62 1.6. Заключение.............................................................................. 65 1.7. Дополнительная литература............................................................... 66 Глава 2. Начальная стадия: рисование фигур.......................................................67 2.1. Начальная стадия создания изображения................................................... 68 2.1.1. Аппаратно-независимое программирование и OpenGL................................... 69 2.1.2. Оконное программирование.......................................................... 70 2.1.3. Открытие окна для рисования....................................................... 72 2.2. Рисование основных графических примитивов............................................... 73 2.2.1. Рисование созвездия точек......................................................... 78 2.3. Создание рисунков из линий.............................................................. 83 2.3.1. Рисование ломаных линий и полигонов............................................... 86 2.3.2. Рисование линий с использованием movetoQ и linetof)............................... 91 2.3.3. Рисование выровненных прямоугольников............................................. 92 2.3.4. Форматное соотношение выровненного прямоугольника................................. 94 2.3.5. Закрашивание полигонов............................................................ 96 2.3.6. Другие графические примитивы в OpenGL............................................. 97 2.4. Простое взаимодействие с помощью мыши и клавиатуры...................................... 98 2.4.1. Взаимодействие с помощью мыши..................................................... 98 2.4.2. Взаимодействие с помощью клавиатуры.............................................. 102 2.5. Резюме................................................................................. 103 2.6. Тематические задания................................................................... 103 Тематическое задание 2.1. Псевдослучайные облака из точек .............................. 104 Тематическое задание 2.2. Введение в систему итерируемых функций........................ 106 Тематическое задание 2.3. Золотое отношение и другие жемчужины.......................... 109 Тематическое задание 2.4. Создание и применение файлов для ломаных линий................ 112 Тематическое задание 2.5. Рисование линий и многоугольников пунктиром.................... ИЗ Тематическое задание 2.6. Редактор ломаных линий........................................ 114 Тематическое задание 2.7. Построение и запуск лабиринтов................................ 115 2.7. Дополнительная литература.............................................................. 117 Глава 3. Дополнительные инструменты для рисования...............................................118 3.1. Введение............................................................................... 119 3.2. Мировые окна и порты просмотра......................................................... 120 3.2.1. Преобразование из мирового окна в порт просмотра................................. 121 3.2.2. Автоматическая установка окна и порта просмотра.................................. 132 3.3. Отсечение линий........................................................................ 135 3.3.1. Отсечение прямой................................................................. 135 3.3.2. Алгоритм отсечения Кохена-Сазерленда............................................. 136 3.4. Разработка класса Canvas .............................................................. 140 3.4.1. Несколько полезных вспомогательных классов....................................... 141 3.4.2. Реализация класса Canvas......................................................... 144 3.5. Относительное рисование................................................................ 146 3.5.1. Разработка moveRel() и lineRelQ.................................................. 146 3.5.2. Черепашья графика................................................................ 148 3.6. Фигуры на основе правильных многоугольников ........................................... 153 3.6.1. Правильные многоугольники........................................................ 153 3.6.2. Вариации п-угольников............................................................ 155 3.7. Рисование окружностей и дуг............................................................ 159 3.7.1. Рисование дуг.................................................................... 159
8 Содержание 3.8. Применение параметрического задания кривой............................................... 164 3.8.1. Параметрические формы для кривых................................................... 165 3.8.2. Вычерчивание кривых, заданных параметрически....................................... 167 3.8.3. Суперэллипсы....................................................................... 169 3.8.4. Формы в полярных координатах....................................................... 170 3.8.5. Трехмерные кривые.................................................................. 172 3.9. Резюме................................................................................... 174 3.10. Тематические задания.................................................................... 175 Тематическое задание 3.1. Изучение логистического преобразования и имитация хаоса......... 175 Тематическое задание 3.2. Реализация отсекателя Кохена—Сазерленда на С или C++............ 177 Тематическое задание 3.3. Реализация Canvas на Turbo C++.................................. 179 Тематическоезадание 3.4. Рисование арок................................................... 182 Тематическое задание 3.5. Некоторые рисунки, используемые в физике и технике.............. 183 Тематическое задание 3.6. Мозаики......................................................... 186 Тематическое задание 3.7. Веселые вариации на тему........................................ 187 Тематическое задание 3.8. Окружности, вращающиеся вокруг окружностей...................... 189 Тематическое задание 3.9. Суперэллипсы.................................................... 190 3.11. Дополнительная литература................................................................ 191 Глава 4. Векторные инструменты для графики........................................................192 4.1. Введение................................................................................. 193 4.2. Обзор векторов........................................................................... 195 4.2.1. Операции с векторами............................................................... 197 4.2.2. Линейные комбинации векторов....................................................... 198 4.2.3. Модуль вектора; единичные векторы.................................................. 200 4.3. Скалярное произведение................................................................... 201 4.3.1. Свойства скалярного произведения................................................... 201 4.3.2. Угол между двумя векторами......................................................... 202 4.3.3. Знак b • с и перпендикулярность.................................................... 203 4.3.4. Двумерный «перп» вектор............................................................ 204 4.3.5. Ортогональные проекции и расстояние от точки до прямой............................. 206 4.3.6. Приложения проекции: отражения..................................................... 208 4.4. Векторное произведение двух векторов..................................................... 209 4.4.1. Геометрическая интерпретация векторного произведения............................... 210 4.4.2. Нахождение нормали к плоскости..................................................... 211 4.5. Отображение ключевых геометрических объектов............................................. 212 4.5.1. Системы координат и координатные фреймы............................................ 213 4.5.2. Аффинные комбинации точек.......................................................... 216 4.5.3. Линейная интерполяция двух точек................................................... 219 4.5.4. Твининг в искусстве и анимации..................................................... 219 4.5.5. Обзор: квадратичный и кубический твининг и кривые Безье............................ 222 4.5.6. Представление прямых и плоскостей.................................................. 222 4.6. Определение точки пересечения двух отрезков прямой....................................... 231 4.6.1. Приложение пересечения прямых: окружность, проходящая через три заданные точки..... 234 4.7. Пересечения прямых с плоскостями; отсечение.............................................. 236 4.8. Задачи о пересечениях многоугольников.................................................... 238 4.8.1. Работа с выпуклыми полигонами и полиэдрами......................................... 239 4.8.2. Пересечение с лучами и отсечение для выпуклых полигонов............................ 240 4.8.3. Алгоритм Сайруса—Бека.............................................................. 243 4.8.4. Отсечение границами произвольных полигонов......................................... 246 4.8.5. Более сложное отсечение............................................................ 248 4.9. Резюме................................................................................... 249 4.10. Тематические задания..................................................................... 250 Тематическое задание 4.1. Анимация с твинингом............................................ 250 Тематическое задание 4.2. Разные окружности .............................................. 250 Тематическое задание 4.3. Находится ли точка Q внутри выпуклого полигона Р?............... 252 Тематическое задание 4.4. Отражения в комнате (двумерная трассировка луча)................ 253 Тематическое задание 4.5. Отсечение Сайруса—Бека.......................................... 254
Содержание 9 Тематическое задание 4.6. Отсечение полигона границами выпуклого полигона: отсечение Сазерленда—Ходгмана................................................................. 254 Тематическое задание 4.7. Отсечение одного полигона границами другого: отсечение Бейлера—Азертона.................................................................... 257 Тематическое задание 4.8. Булевы операции с полигонами ............................... 260 4.11. Дополнительная литература............................................................. 262 Глава 5. Преобразования объектов...............................................................263 5.1. Введение.............................................................................. 264 5.2. Введение в преобразования............................................................. 265 5.2.1. Преобразование точек и объектов................................................ 268 5.2.2. Аффинные преобразования........................................................ 270 5.2.3. Геометрические эффекты элементарных двумерных аффинных преобразований.......... 271 5.2.4. Инвертирование аффинного преобразования........................................ 276 5.2.5. Композиция аффинных преобразований............................................. 278 5.2.6. Примеры композиции двумерных преобразований ................................... 279 5.2.7. Некоторые полезные свойства аффинных преобразований............................ 284 5.3. Трехмерные аффинные преобразования.................................................... 289 5.3.1. Элементарные трехмерные преобразования......................................... 289 5.3.2. Компонование трехмерных аффинных преобразований................................ 293 5.3.3. Комбинирование поворотов....................................................... 294 5.3.4. Краткое изложение свойств трехмерных аффинных преобразований................... 299 5.4. Изменения систем координат............................................................ 300 5.5. Использование аффинных преобразований в программах.................................... 303 5.5.1. Сохранение СТ для дальнейшего использования.................................... 311 5.6. Рисование трехмерных сцен с применением OpenGL........................................ 316 5.6.1. Знакомство с процессом визуального отображения и графическим конвейером........ 316 5.6.2. Некоторые инструменты OpenGL для моделирования и вида.......................... 320 5.6.3. Рисование элементарных форм, поддерживаемых OpenGL............................. 323 5.7. Резюме................................................................................ 338 5.8. Тематические задания.................................................................. 339 Тематическое задание 5.1. Выполнение вашего собственного преобразования с помощью СТ в классе Canvas.................................................................. 339 Тематическое задание 5.2. Рисование звезды с рисунка 5.39 с помощью многократных поворотов. 340 Тематическое задание 5.3. Разложение двумерного аффинного преобразования.............. 340 Тематическое задание 5.4. Обобщенные трехмерные сдвиги ............................... 344 Тематическое задание 5.5. Вращение вокруг оси: конструктивный подход.................. 346 Тематическое задание 5.6. Разложение трехмерных аффинных преобразований............... 347 Тематическое задание 5.7. Рисование трехмерных сцен, описанных на языке SDL........... 349 5.9. Дополнительная литература............................................................. 349 Глава 6. Моделирование поверхностей полигональными сетками ....................................350 6.1. Введение.............................................................................. 351 6.2. Введение в трехмерное моделирование полигональными сетками............................ 351 6.2.1. Определение полигональной сетки................................................ 353 6.2.2. Нахождение нормальных векторов................................................. 355 6.2.3. Свойства сеток................................................................. 357 6.2.4. Каркасные модели для немонолитных объектов..................................... 358 6.2.5. Работа с сетками в программе................................................... 359 6.3. Многогранники......................................................................... 363 6.3.1. Призмы и антипризмы............................................................ 365 6.3.2. Платоновы тела................................................................. 366 6.3.3. Другие любопытные многогранники................................................ 371 6.4. Экструзивные формы.................................................................... 375 6.4.1. Создание призм................................................................. 375 6.4.2. Совокупности экструзивных призм: «кирпичная кладка»............................ 376 6.4.3. Экструзии с «поворотом»........................................................ 378 6.4.4. Создание сегментированных экструзий: трубки и змейки........................... 379 6.4.5. «Дискретно» заметаемые поверхности вращения.................................... 385
10 Содержание 6.5. Каркасные аппроксимации гладких объектов................................................... 386 6.5.1. Представления поверхностей.......................................................... 386 6.5.2. Нормальный вектор к поверхности..................................................... 388 6.5.3. Влияние аффинного преобразования.................................................... 389 6.5.4. Три «базовые» формы: сфера, цилиндр и конус.................................... 391 6.5.5. Формирование полигональной сетки для криволинейной поверхности...................... 394 6.5.6. Линейчатые поверхности.............................................................. 396 6.5.7. Поверхности вращения................................................................ 402 6.5.8. Поверхности второго порядка......................................................... 404 6.5.9. Суперквадрики....................................................................... 408 6.5.10. Трубки на базе трехмерных кривых................................................... 409 6.5.11. Поверхности на базе явных функций двух переменных.................................. 410 6.6. Заключение................................................................................. 411 6.7. Тематические задания . Тематическое задание Тематическое задание Тематическое задание Тематическое задание Тематическое задание Тематическое задание Тематическое задание Тематическое задание Тематическое задание 6.1. Сетки, записанные в файл ........................................ 6.2. Вывод метода Ньюэлла............................................. 6.3. Призма........................................................... 6.4. Совокупность призм и экструдированные полосы из четырехугольников ... 6.5. Трубки и змейки на базе параметрической кривой................... б.б. Построение поверхностей вращения с дискретными шагами............ 6.7. Списки ребер и каркасные модели ................................. 6.8. Сводчатые потолки................................................ 6.9. О Платоновых телах............................................... 412 412 414 416 417 418 419 419 420 420 Тематическое задание 6.10. Об Архимедовых телах............................................ 420 Тематическое задание 6.11. Алгебраическая форма поверхностей второго порядка............... 420 Тематическое задание 6.12. Сцены с супеквадриками........................................ 422 Тематическое задание 6.13. Рисование гладких параметрических поверхностей.................. 422 Тематическое задание 6.14. Сузить, закрутить, изогнуть и расплющить........................ 423 6.8. Дополнительная литература ................................................................. 425 Глава 7. Трехмерный просмотр..................................................................425 7.1. Введение............................................................................. 427 7.2. Снова о камере....................................................................... 427 7.2.1. Установка отображаемого объема................................................ 428 7.2.2. Позиционирование и ориентирование камеры...................................... 429 7.3. Встраивание камеры в программу....................................................... 434 7.3.1. «Пилотирование» камеры........................................................ 436 7.4. Перспективные проекции трехмерных объектов........................................... 440 7.4.1. Перспективная проекция точки.................................................. 441 7.4.2. Перспективная проекция прямой линии........................................... 444 7.4.3. Включение перспективы в графический конвейер.................................. 449 7.4.4. Отсечение граней границами отображаемого объема............................... 456 7.5. Создание стереоизображений .......................................................... 463 7.6. Классификация проекций............................................................... 465 7.6.1. Одно-, двух-и трехточечные перспективы........................................ 465 7.6.2. Параллельные проекции......................................................... 470 7.7. Резюме............................................................................... 477 7.8. Тематические задания................................................................. 477 Тематическое задание 7.1. «Пилотирование» камеры по сцене............................ 477 Тематическое задание 7.2. Стереоизображения.......................................... 478 Тематическое задание 7.3. Создание параллельных проекций ............................ 478 Тематическое задание 7.4. Самодельное проецирование (если бы OpenGL был недоступен).. 479 Тематическое задание 7.5. Удаление невидимых граней для большей эффективности........ 479 7.9. Дополнительная литература............................................................ 480 Глава 8. Визуализация граней для усиления реалистичности......................................481 8.1. Введение............................................................................. 482 8.2. Введение в модели закрашивания....................................................... 486 8.2.1. Геометрические составляющие для нахождения отраженного света.................. 487
Содержание 11 8.2.2. Вычисление диффузной составляющей ............................................... 488 8.2.3. Зеркальное отражение............................................................. 489 8.2.4. Роль фонового света.............................................................. 492 8.2.5. Комбинирование компонентов освещения............................................. 493 8.2.6. Добавление цвета................................................................. 494 8.2.7. Закраска и графический конвейер ................................................. 496 8.2.8. Использование источников света в OpenGL.......................................... 497 8.2.9. Работа со свойствами материалов в OpenGL......................................... 503 8.2.10. Закраска сцен, заданных с помощью SDL............................................ 503 8.3. Плоское и плавное закрашивание.......................................................... 504 8.3.1. Плоское закрашивание............................................................. 506 8.3.2. Плавное закрашивание ............................................................ 507 8.4. Удаление невидимых поверхностей......................................................... 511 8.4.1. Использование буфера глубины..................................................... 511 8.5. Добавление текстуры к граням............................................................ 514 8.5.1. Наложение текстуры на плоскую поверхность........................................ 517 8.5.2. Визуализация текстуры ........................................................... 519 8.5.3. Что регулирует текстура?......................................................... 526 8.5.4. Пример текстурирования с использованием OpenGL................................... 528 8.5.5. Обертывание текстуры вокруг криволинейных поверхностей........................... 534 8.5.6. Отображение отражений............................................................ 539 8.6. Добавление теней объектов............................................................... 542 8.6.1. Тени как текстура ............................................................... 543 8.6.2. Создание теней с помощью буфера теней............................................ 544 8.7. Заключение.............................................................................. 546 8.8. Тематические задания.................................................................... 547 Тематическое задание 8.1. Создание закрашенных объектов с использованием OpenGL......... 547 Тематическое задание 8.2. Самодельный графический конвейер.............................. 548 Тематическое задание 8.3. Добавление закраски полигонов и удаления невидимых поверхностей при помощи буфера глубины............................................................. 548 Тематическое задание 8.4. Визуализация текстуры......................................... 548 Тематическое задание 8.5. Применение процедурных 30-текстур............................. 548 Тематическое задание 8.6. Рисование теней............................................... 549 Тематическое задание 8.7. Расширение SDL с целью включения текстурирования.............. 549 8.9. Дополнительная литература .............................................................. 550 Глава 9. Приближение к бесконечности........................................................... 551 9.1. Введение................................................................................ 552 9.2. Фракталы и самоподобие.................................................................. 552 9.2.1. Последовательное усложнение кривых............................................... 553 9.2.2. Рисование кривых и снежинок Коха................................................. 554 9.2.3. Дробная размерность.............................................................. 556 9.3. Создание строк и кривые Пеано........................................................... 557 9.3.1. Рекурсивная генерация строк и рисование в программе.............................. 559 9.3.2. Разрешение ветвления............................................................. 562 9.3.3. Добавление случайности и сужения................................................. 565 9.4. Замощение плоскости..................................................................... 565 9.4.1. Моноэдрические мозаики........................................................... 566 9.4.2. Диэдральные мозаичные размещения................................................. 568 9.4.3. Рисование мозаик ................................................................ 571 9.4.4. Рептилии......................................................................... 571 9.5. Создание изображений с использованием системы итерируемых функций ...................... 574 9.5.1. Экспериментальный копир.......................................................... 574 9.5.2. Теоретические основы процесса копирования........................................ 576 9.5.3. Рисование k-й итерации........................................................... 577 9.5.4. «Игра в Хаос».................................................................... 579 9.5.5. Нахождение системы IFS; фрактальное сжатие изображений........................... 582 9.6. Множество Мандельброта.................................................................. 586 9.6.1. Множества Мандельброта и системы итерируемых функций............................. 586
12 Содержание 9.6.2. Определение множества Мандельброта............................................... 590 9.6.3. Определение того, находится ли точка с в пределах множества Мандельброта......... 592 9.6.4. Рисование множества Мандельброта ................................................ 593 9.6.5. Некоторые замечания по поводу множества Мандельброта............................. 595 9.7. Множества Жюлиа......................................................................... 595 9.7.1. Плотное множество Жюлиа Кс....................................................... 596 9.7.2. Рисование плотных множеств Жюлиа................................................. 596 9.7.3. Некоторые замечания относительно неподвижных точек и бассейнов притяжения........ 596 9.7.4. Множество Жюлиа Jc............................................................... 599 9.8. Случайные фракталы...................................................................... 602 9.8.1. Фрактализация отрезка............................................................ 602 9.8.2. Контроль за спектральной плотностью фрактальной кривой........................... 604 9.9. Резюме.................................................................................. 606 9.10. Тематические задания.................................................................... 607 Тематическое задание 9.1. Рисование по генерации строк.................................. 607 Тематическое задание 9.2. Рисование снежинок и рептилий................................. 608 Тематическое задание 9.3. «Игра в Хаос» ................................................ 610 Тематическое задание 9.4. Рисование орбит внутри множества Мандельброта................. 611 Тематическое задание 9.5. Создание изображений множества Мандельброта................... 612 Тематическое задание 9.6. Создание изображений множеств Жюлиа........................... 612 Тематическое задание 9.7. Непериодические мозаики; мозаики Пенроуза..................... 612 Тематическое задание 9.8. Фрактализация кривых.......................................... 614 Тематическое задание 9.9. Моделирование фрактализованных гор............................ 615 9.11. Дополнительная литература............................................................... 616 Глава 10. Средства для растровой графики.................................................... 617 10.1. Введение............................................................................... 618 10.2. Управление пиксельными картами......................................................... 619 10.2.1. Важные операции с пиксельными картами........................................... 619 10.2.2. Типы данных, используемые для пиксельных карт................................... 620 10.2.3. Масштабирование и поворот изображений........................................... 627 10.3. Объединение пиксельных карт............................................................ 630 10.3.1. Цикл «чтение — модификация-запись».............................................. 631 10.3.2. Альфа-канал и смешивание изображений............................................ 632 10.3.3. Логические комбинации пиксельных карт........................................... 636 10.3.4. Операция BitBLT................................................................. 640 10.4. Рисование прямых своими силами: алгоритм Брезенхема.................................... 641 10.4.1. Алгоритм Брезенхема для рисования прямых линий.................................. 642 10.5. Определение и заполнение областей из пикселов.......................................... 648 10.5.1. Задание областей................................................................ 648 10.5.2. Пиксельно-определенные области.................................................. 649 10.5.3. Рекурсивный алгоритм заливки.................................................... 650 10.5.4. Заполнение областей узорами .................................................... 652 10.5.5. Использование связности: заполнение области на основе серий пикселов............ 653 10.6. Манипулирование символически-определенными областями................................... 655 10.6.1. Области, описываемые прямоугольниками........................................... 655 10.6.2. Области, заданные контуром...................................................... 657 10.7. Заполнение полигонально-определенных областей.......................................... 658 10.7.1. Какие пикселы ребра принадлежат полигону?....................................... 659 10.7.2. Повышение эффективности алгоритма............................................... 662 10.8. Ступенчатость; технологии сглаживания.................................................. 666 10.8.1. Технологии сглаживания.......................................................... 667 10.8.2. Сглаживание текстуры............................................................ 672 10.8.3. Сглаживание с применением OpenGL................................................ 675 10.9. Увеличение количества цветов и оттенков................................................ 676 10.9.1. Упорядоченное размытие.......................................................... 678 10.9.2. Рассеивание ошибок.............................................................. 682 10.10. Резюме................................................................................. 684
Содержание 13 10.11. Тематические задания.................................................................... 685 Тематическое задание 10.1. Чтение и просмотр BMP-файлов изображений...................... 685 Тематическое задание 10.2. Растворение одной пиксельной карты в другой с помощью OpenGL.. 686 Тематическое задание 10.3. Заполнение области на основе серий............................ 686 Тематическое задание 10.4. Работа со структурой данных «формы»........................... 686 Тематическое задание 10.5. Цепное кодирование форм....................................... 687 Тематическое задание 10.6. Заполнение «горизонтально-выпуклых» полигонов................. 687 Тематическое задание 10.7. Заполнение полигона общего вида............................... 688 Тематическое задание 10.8. Рассеивание ошибок............................................ 688 10.12. Дополнительная литература .............................................................. 688 Глава 11. Создание кривых и поверхностей..........................................................689 11.1. Введение................................................................................ 690 11.1.1. Параметрические кривые как траектории............................................ 690 11.1.2. Плавность движения............................................................... 691 11.2. Описание кривых полиномами.............................................................. 695 11.3. Интерактивное конструирование кривых ................................................... 700 11.4. Применение кривых Безье для построения кривых........................................... 702 11.4.1. Алгоритм де Кастельо............................................................. 702 11.5. Свойства кривых Безье .................................................................. 707 11.6. Нахождение лучших стыковочных функций................................................... 712 11.6.1. Проблема локального контроля .................................................... 712 11.6.2. Список пожеланий для множества стыковочных функций............................... 713 11.6.3. Кусочно-полиномиальные кривые и сплайны ......................................... 715 11.6.4. Построение из g(t) множества стыковочных функций................................. 717 11.6.5. Сплайны и базисные функции ...................................................... 720 11.7. Базисные функции В-сплайнов............................................................. 721 11.7.1. Определение В-сплайн функций..................................................... 721 11.7.2. Использование кратных узлов в узловом векторе.................................... 726 11.7.3. Незамкнутые В-сплайн кривые: стандартный узловой вектор.......................... 727 11.8. Полезные для дизайна свойства В-сплайн кривых........................................... 730 11.8.1. Использование кратных контрольных точек.......................................... 732 11.9. Рациональные сплайны и NURBS-кривые..................................................... 733 11.10. Краткое знакомство с интерполяцией...................................................... 737 11.10.1. Интерполяция посредством кусочных кубических полиномов.......................... 737 11.10.2. Эрмитова интерполяция........................................................... 739 11.10.3. Естественные кубические сплайны................................................. 742 11.10.4. Вычисление наклонов при кубической интерполяции ................................ 743 11.10.5. Интерактивное задание касательных векторов ..................................... 748 11.11. Моделирование криволинейных поверхностей................................................ 748 11.11.1. Линейчатые поверхности на базе В-сплайнов....................................... 748 11.11.2. Поверхности вращения на базе В-сплайнов......................................... 749 11.11.3. Лоскуты Безье................................................................... 751 11.11.4. Сшивание лоскутов Безье......................................................... 752 11.11.5. В-сплайн лоскуты................................................................ 754 11.11.6. NURBS-поверхности............................................................... 755 11.12. Резюме.................................................................................. 757 11.13. Тематические задания.................................................................... 759 Тематическое задание 11.1. Попурри из интересных параметрических кривых................... 759 Тематическое задание 11.2. «Эллиптипул»................................................... 760 Тематическое задание 11.3. Кривые Безье................................................... 762 Тематическое задание 11.4. Генератор квадратичной сплайн-кривой .......................... 762 Тематическое задание 11.5. Создание редактора сплайн-кривых............................... 762 Тематическое задание 11.6. Интерполяция контрольных точек В-сплайнами..................... 763 Тематическое задание 11.7. Интерполяция кубическими полиномами............................ 765 Тематическое задание 11.8. Многоуважаемый чайник.......................................... 765 Тематическое задание 11.9. Инвариантность относительно проективных преобразований......... 766 Тематическое задание 11.10. Рисование NURBS-лоскутов..................................... 767 11.14. Дополнительная литература .............................................................. 769
14 Содержание Глава 12. Теория цвета...........................................................................770 12.1. Введение............................................................................... 770 12.2. Описания цветов........................................................................ 772 12.2.1. Доминантная длина волны.......................................................... 773 12.2.2. Подбор цветов.................................................................... 774 12.3. Международная комиссия по стандартам освещенности...................................... 777 12.3.1. Построение С1Е-диаграммы ........................................................ 778 12.3.2. Использование хроматической С1Е-диаграммы........................................ 780 12.3.3. Цветовые охваты.................................................................. 781 12.4. Цветовые пространства.................................................................. 782 12.4.1. Цветовые пространства RGB и CMY.................................................. 782 12.4.2. Аддитивные и субтрактивные цветовые системы...................................... 783 12.4.3. Цветовая модель HLS.............................................................. 785 12.5. Квантование цвета...................................................................... 787 12.5.1. Квантование с постоянным шагом................................................... 789 12.5.2. Алгоритм популярности............................................................ 791 12.5.3. Алгоритм медианного сечения...................................................... 791 12.5.4. Octree-квантование............................................................... 792 12.6. Резюме................................................................................. 795 12.7. Тематические задания................................................................... 795 Тематическое задание 12.1. Рисование С1Е-диаграммы....................................... 795 Тематическое задание 12.2. Рисование RGB-пространства.................................... 795 Тематическое задание 12.3. Из HSV в RGB.................................................. 796 Тематическое задание 12.4. Однородное квантование цвета.................................. 796 Тематическое задание 12.5. Квантование цвета по популярности............................. 796 Тематическое задание 12.6. Квантование цвета методом медианного сечения.................. 796 Тематическое задание 12.7. Квантование цвета методом октодерева ......................... 796 12.8. Дополнительная литература.............................................................. 798 Глава 13. Удаление невидимых поверхностей .......................................................799 13.1. Введение............................................................................... 800 13.1.1. Два подхода: «точность по объекту» и «точность по изображению»................... 802 13.1.2. Описание данных для полигональных сеток.......................................... 802 13.2. Снова об алгоритме буфера глубины...................................................... 805 13.3. HSR-методы со списками приоритетов..................................................... 806 13.3.1. Алгоритм беспечного художника ................................................... 807 13.3.2. HSR с использованием деревьев двоичного разбиения пространства................... 808 13.3.3. Алгоритм сортировки по глубине................................................... 812 13.4. HSR-метод построчного сканирования..................................................... 816 13.5. Методы разбиения области .............................................................. 818 13.5.1. Квадрантное разбиение............................................................ 819 13.5.2. Другие определения простой области............................................... 822 13.6. О методах удаления невидимых линий..................................................... 825 13.6.1. Геометрическое тестирование в подпрограмме edgeTest()............................ 828 13.7. HSR-методы для криволинейных поверхностей.............................................. 829 13.8. Резюме................................................................................. 832 13.9. Тематические задания................................................................... 834 Тематическое задание 13.1. Проверка алгоритма художника.................................. 834 Тематическое задание 13.2. Тест и разбиение.............................................. 834 Тематическое задание 13.3. Удаление невидимых поверхностей с использованием BSP-деревьев.. 835 Тематическое задание 13.4. HSR с использованием сортировки по глубине.................... 836 Тематическое задание 13.5. Использование HSR-метода построчного сканирования............. 836 Тематическое задание 13.6. Рисование при помощи алгоритма Варнока........................ 837 Тематическое задание 13.7. HLR с помощью алгоритма стека ребер........................... 837 13.10. Дополнительная литература............................................................. 837
Содержание 15 Глава 14. Введение в трассировку лучей...........................................................838 14.1. Введение............................................................................... 839 14.2. Построение геометрии трассировки лучей................................................. 840 14.3. Обзор процесса трассировки луча ....................................................... 842 14.4. Пересечение луча с объектом............................................................ 844 14.4.1. Пересечение луча с базовой плоскостью........................................... 845 14.4.2. Пересечение с базовой сферой.................................................... 845 14.4.3. Пересечение луча с преобразованными объектами................................... 846 14.5. Организация трассировщика луча в приложении............................................ 848 14.5.1. Подпрограмма для вычисления пересечений луча со сферой.......................... 855 14.5.2. Полный трассировщик лучей для сцен с излучающей сферой.......................... 857 14.6. Пересечение лучей с другими примитивами................................................ 858 14.6.1. Пересечение с квадратом......................................................... 858 14.6.2. Пересечение с коническим цилиндром.............................................. 860 14.6.3. Пересечение с кубом (или с любым другим выпуклым полиэдром)..................... 864 14.6.4. Добавление новых примитивов..................................................... 871 14.7. Рисование закрашенных изображений сцен ................................................ 872 14.7.1. Нахождение нормали в точке соударения........................................... 873 14.7.2. Раскраска объектов в соответствии с материалами поверхностей.................... 874 14.7.3. Физически обоснованные модели закраски: закрашивание Кука—Торренса.............. 877 14.8. Наложение текстуры на поверхности...................................................... 883 14.8.1. Текстура твердого тела.......................................................... 884 14.8.2. Наложение изображений на поверхности............................................ 894 14.8.3. Сглаживающая трассировка лучей.................................................. 896 14.9. Использование экстентов................................................................ 897 14.9.1. Боксы и сферические экстенты.................................................... 899 14.9.2. Использование проекционных экстентов............................................ 904 14.10. Добавление теней для большей реалистичности............................................ 907 14.11. Отражения и прозрачность............................................................... 910 14.11.1. Преломление света.............................................................. 913 14.11.2. Обработка преломления методом shade().......................................... 918 14.12. Составные объекты: логические операции с объектами..................................... 921 14.12.1. Трассировка лучей для CSG-объектов............................................. 922 14.12.2. Структура данных для Булевых объектов.......................................... 924 14.12.3. Пересечения лучей с Булевыми объектами......................................... 927 14.12.4. Построение и использование экстентов для CGG-объектов.......................... 933 14.13. Резюме................................................................................. 935 14.14. Тематические задания................................................................... 936 Тематическое задание 14.1. Эмиссионный трассировщик..................................... 936 Тематическое задание 14.2. Усовершенствованный трассировщик лучей....................... 936 Тематическое задание 14.3. Реализация теней при трассировке лучей ...................... 937 Тематическое задание 14.4. Использование экстентов для ускорения трассировки лучей......... 937 Тематическое задание 14.5. Трассировка лучей с ЗО-текстурами............................... 937 Тематическое задание 14.6. Сглаживание..................................................... 937 Тематическое задание 14.7. Трассировкалучей для других примитивов.......................... 937 Тематическое задание 14.8. Двумерный трассировщик лучей для работы с преломлением. 938 Тематическое задание 14.9. Отраженный и преломленный свет......................... 938 Тематическое задание 14.10. Трассировка Булевых комбинаций объектов............... 938 14.15. Дополнительная литература ...................................................... 938 Приложение А. Графический инструментарий: получение OpenGL................................939 Al. Получение и инсталляция OpenGL ................................................... 939 Приложение Б. Немного математики для компьютерной графики.................................941 Б1. Некоторые основные определения, относящиеся к матрицам и операциям над ними....... 941 Б1.1. Действия с матрицами ....................................................... 942 Б1.2. Умножение двух матриц....................................................... 943
16 Содержание Б1.3. Разбиение матрицы на блоки .................................................... 944 Б1.4. Определитель матрицы........................................................... 945 Б1.5. Обращение матрицы.............................................................. 946 Б2. Некоторые свойства векторов и операции над ними...................................... 948 Б2.1. Перп вектора; перп-скалярное произведение...................................... 948 Б2.2. Смешанное произведение..........................>.............................. 949 Б2.3. Двойное векторное произведение................................................. 950 БЗ. Арифметика комплексных чисел......................................................... 950 Б4. Сферические координаты и направляющие косинусы....................................... 953 Приложение В. Некоторые полезные классы и служебные подпрограммы ... 956 В1. Классы для двумерной графики......................................................... 957 В2. RGBPixmap CLASS...................................................................... 961 ВЗ. Класс SCENE и сопутствующие классы................................................... 966 В4. Класс NOISE.......................................................................... 995 В5. Некоторые классы, полезные при трассировке лучей..................................... 998 Приложение Г. Введение в PostScript®...................................................... 1001 Г1.0 языке PostScript................................................................... 1002 Г1.1. Некоторые предварительные замечания........................................... 1002 Г1.2. PostScript основан на стеке................................................... 1003 Г1.3. Некоторые операции со стеком: pop, dup, exch, clear........................... 1004 Г1.4. Более сложные операторы работы со стеком...................................... 1005 Г1.5. Некоторые арифметические операторы............................................ 1005 Г2. Графические операторы в PostScript.................................................. 1008 Г2.1. Системы координат и преобразования............................................ 1008 Г2.2. Команды создания контура...................................................... 1009 Г2.3. Дуги окружностей.............................................................. 1010 Г2.4. Использование операторов закрашивания......................................... 1011 Г2.5. Преобразования координат...................................................... 1012 Г2.6. Операторы графического состояния.............................................. 1016 ГЗ. Рисование текста в PostScript....................................................... 1019 Г4. Определение новых переменных и процедур............................................. 1019 Г4.1. Определение переменных........................................................ 1020 Г4.2. Определение процедур.......................................................... 1020 Г4.3. Простейшая форма итерации с использованием оператора repeat................... 1024 Г5. Команды решений и итераций.......................................................... 1026 Г5.1. Команды, принимающие логические величины в качестве аргументов................ 1027 Г5.2. Принятие решений.............................................................. 1027 Г5.3. Итерация...................................................................... 1029 Гб. Печать численных значений........................................................... 1034 Г7. Рисование полутоновых изображений................................................... 1035 Приложение Д. Введение в SDL.............................................................. 1038 Д1. Синтаксис SDL....................................................................... 1039 Д2. Макросы в SDL....................................................................... 1043 ДЗ. Расширение SDL...................................................................... 1044 Литература................................................................................ 1046 Список терминов.............................................................................1058 Алфавитный указатель.................................................................... 1065
Посвящается Мерили, а также Грете, Джесси и Рози
Введение В этой книге содержится введение в компьютерную графику для тех студентов, которые желают изу- чить основные принципы и технические приемы в этой области и, кроме того, намерены сами писать солидные графические приложения. Сфера компьютерной графики по-прежнему обладает невероят- ной живучестью и продолжает стремительно развиваться. Использование возможностей графики во все возрастающем числе полнометражных анимационных фильмов производит головокружительное впечатление, а широкий доступ к ней через компьютерные игры и Интернет побуждает людей учиться применять эти возможности самим. Графические системы становятся лучше, быстрее и дешевле с невероятной скоростью. Каждый год исследователи и практики всего мира изобретают множество новых технических приемов, однако основные принципы и подходы по-прежнему составляют неизменный и логически последовательный стержень знания компьютерной графики. Большинство этих сведений может быть получено в резуль- тате изучения одного курса графики, и в этой книге делается попытка систематизировать идеи и мето- ды так, чтобы даже начинающий читатель со скромным опытом программирования смог придумывать и писать серьезные графические программы. Предполагаемая аудитория Эта книга предназначается в качестве одно- или двухсеместрового курса для студентов-старшекурсни- ков или аспирантов первого года обучения. Она может быть также использована для самообучения. Книга преимущественно нацелена на студентов, специализирующихся в компьютерной теории или практике, но подойдет и студентам других областей знания, таких как физика или математика. Необходимая математическая подготовка Читателю желательно обладать знанием математики в объеме одного года колледжа; предполагается также знание элементарной алгебры, геометрии, тригонометрии и основных вычислительных методов. Полезным было бы некоторое представление о векторах и матрицах, но не обязательно глубокое, по- скольку векторные и матричные технологии вводятся в контекст графиков по мере необходимости; кро- ме того, ключевые идеи резюмируются в приложении. В компьютерной графике используется много математики для выражения геометрических соотно- шений между линиями, поверхностями и взглядом на них наблюдателя. Хотя ни одно математическое понятие не является сложным по своей сути, общее количество необходимых инструментальных средств может показаться устрашающим. В книге делается особый акцент на обосновании причин, по
Философия книги 19 которым следует использовать тот или иной технический прием, и на том, как правильно описывать в программе нужные графические объекты с помощью объектов математических. Необходимая подготовка по программированию Вообще говоря, читателю следовало бы иметь по меньшей мере опыт одного семестра написания ком- пьютерных программ на языках С, C++ или Java. Значительная часть программирования графики сво- дится к непосредственному переводу геометрических соотношений в код и, следовательно, непосред- ственно использует переменные, функции, массивы, циклы и тестирование, что является общим для всех языков. На протяжении всей книги используется C++, однако большая часть материала будет близ- ка и тем, кто знаком только с С. Читателю очень поможет опыт работы со структурами (structs) на С или с классами на C++. Они используются для охвата достаточно сложной структуры некоторых графических объектов, участвую- щих в сцене, когда объект (скажем, замок или самолет) состоит из множества частей, которые, в свою очередь, сами состоят из сложных элементов. Желателен (но не обязателен) также некоторый опыт ра- боты с элементарными связными структурами данных, такими как связные списки (linked lists) или деревья. Читателю, знающему С, но не C++, придется познакомиться с основами объектно-ориентированного программирования. Мы определим несколько полезных классов, таких как Window (окно), Mesh (сетка), Scene (сцена), Camera (видеокамера) и Texture (текстура), и покажем, почему они являются столь удоб- ными и полезными. Некоторые признаки объектно-ориентированного программирования, как, напри- мер, наследование и полиморфизм, используются лишь для того, чтобы облегчить работу программис- та, однако мы не уделяем чисто объектно-ориентированному подходу слишком большого внимания. Философия книги После выхода первого издания книга была полностью реорганизована и переписана заново, однако при этом была сохранена ее основная философия: изучать компьютерную графику — значит создавать ее: чтобы полностью постичь то, что происходит, необходимо писать и прогонять реальные программы. Главная задача книги состоит в том, чтобы показать читателям, как преобразовать отдельную проект- ную «задачу» сначала в основные геометрические компоненты, затем найти для выбранных объектов соответствующее математическое представление и, наконец, перевести это представление в надлежа- щий алгоритм и программный код. Читатели начинают с изучения того, как разрабатывать простые подпрограммы для создания изображений; затем шаг за шагом показываются методы визуализации (rendering) рисунков или более сложных объектов. Упражнения и задачи На протяжении всей книги предлагается более 440 практических упражнений. Большинство из них относятся к типу «остановись и подумай», не требующему программирования и позволяющему читате- лям самим проверить понимание материала. Некоторые упражнения побуждают студента воплотить новые идеи в программном коде. Кроме того, в конце каждой главы приводятся тематические задания («case studies») по пройденно- му материалу, общим числом около ста. Эти задания представляют собой обычные программистские задачи для домашнего задания, в диапазоне от простых до сверхсложных. Они основаны на материале соответствующих глав и зачастую развивают высказанные идеи в новых направлениях. Но независимо от того, выполняются ли эти контрольные задания студентами до конца, они должны изучаться как неотъемлемая часть главы. Для каждого тематического задания приведен предполагаемый «уровень сложности», чтобы обозна- чить, сколько примерно времени может понадобиться студенту для выполнения данного задания. Про-
20 Введение граммирование — это непредсказуемое занятие, к тому же возможности студентов различны, однако в первом приближении нужно руководствовать^предложенным ниже разбиением. Уровни сложности. 1. Простой проект, который может быть реализован за один вечер, его можно сделать к очередно- му занятию в классе. 2. Более сложный проект, на который нужно отвести около недели, так что студент должен иметь время на разработку программы и достаточно времени для многократного (и иногда тщетного) тестирования и процесса отладки, в котором проекты, похоже, нуждаются всегда. 3. Крупный проект, который может потребовать до трех недель для разработки и реализации. Та- кой проект требует солидной работы по проектированию и тщательной компоновке програм- мы, а его выполнение будет заслуженно рассматриваться студентом как значительный успех. Использование OpenGL Когда человек впервые начинает совершенствоваться в области компьютерной графики, зачастую кам- нем преткновения является начальное создание изображений. Не так уж трудно написать программу, однако должен быть базовый инструмент, который, в конечном счете, рисует на экране линии и кривые. К счастью, такой инструмент имеется и легко доступен. OpenGL был разработан в 1992 году фирмой Silicon Graphics, Inc и превратился в широко используемый интерфейс прикладных графических про- грамм (graphics application programming interface — API). В нем представлены инструменты рисования, действующие с помощью целого набора функций, которые вызываются внутри приложения. Как опи- сано в приложении А, этот интерфейс доступен (обычно его скачивают из Интернета) для всех типов компьютерных систем, встречающихся в колледжах, университетах и в промышленности. OpenGL прост в установке и изучении, и его долговечность в качестве стандартного API поддерживается экс- пертной комиссией по архитектуре OpenGL (OpenGL Architecture Review Board — ARB) — промыш- ленным консорциумом, ответственным за направление развития программного обеспечения. Еще одним аспектом OpenGL, который делает его столь удобным для использования в курсе компь- ютерной графики, является его «независимость от устройства», или мобильность. Компьютерные ла- боратории многих университетов имеют множество различных компьютеров. Студент может разраба- тывать и запускать свою программу на любом доступном ему компьютере. Затем эта программа может быть запущена на другом компьютере, например, для тестирования или оценки, и графика на этих двух машинах будет одинаковой. OpenGL предлагает обширный и чрезвычайно удобный набор API-функций для 2В-графики и об- работки изображений, но его истинная мощь проявляется в SD-графике. Используя OpenGL, студенты могут быстро развивать свое умение и изготавливать великолепные анимации уже после курса, прочи- танного за один семестр. Использование C++ в качестве языка программирования В настоящее время язык C++ достаточно хорошо знаком большинству студентов, как в технической области, так и в вычислительной технике, из начального курса программирования, поэтому естестве- нен выбор этого языка для дальнейшего использования. Он имеет ряд преимуществ по сравнению с С, таких как передача параметров функции посредством ссылки, что уменьшает необходимость в явных указателях и упрощает чтение кода. Файловый ввод-вывод также стал значительно проще с примене- нием потоков, и вообще синтаксис всех видов ввода-вывода в C++ прозрачнее, чем в С. Проще говоря, в C++ не делается ударения на исполняющих операторах. Более того, в C++ легко разрабатываются полезные прикладные классы: точка на плоскости и в про- странстве, линия, окно или цвет, что делает код более простым и ясным. Студенты видят преимущества инкапсуляции деталей геометрического объекта внутри самого объекта и наделения этого объекта спо- собностью делать такие вещи, как рисование самого себя или проверку на пересечение с другим объек- том. Класс Canvas (полотно), введенный в главе 3, является хорошим примером этого, так как он под-
Структура книги и планы курса 21 держивает свое собственное понятие окна, порта просмотра (viewport) и текущих координат; кроме того, он может рисовать основные фигуры при минимуме усилий со стороны программиста. Акцент на трехмерной компьютерной графике Поскольку игры на персональном компьютере стали очень популярными, а в фильмах появилось ог- ромное количество великолепной анимации, студенты особенно интересуются разработкой приложе- ний с ЗО-графикой. По этой причине несколько глав из первого издания было переписано заново, а их расположение было изменено таким образом, чтобы как можно быстрее перейти к темам по ЗО-графи- ке. В ряде случаев новые понятия вводятся для случаев 2D- и ЗО-графики одновременно, что помогает уяснить различия между ними. Описание ЗО-сцен с помощью языка проектирования сцен Было бы весьма затруднительным и неэкономным с точки зрения времени проектировать сцены, содер- жащие много ЗО-объектов, с помощью «сырых» команд OpenGL. Поэтому в главе 5 вводится (а в при- ложении полностью определяется) простой язык проектирования сцен (Scene Design Language — SDL)1. Используя этот язык, студенты могут описывать сцены в привычных терминах, таких как «куб», «сфе- ра», «повернуть», и создавать файлы, состоящие из инструкций, которые будут считываться в их про- грамму во время выполнения. В приложении (и на сайте книги) имеется код интерпретатора, способ- ного читать SDL-файл и создавать список объектов, описанных в этом файле. По этому списку объектов нарисовать сцену с помощью OpenGL уже несложно. Те же самые язык и интерпретатор успешно применяются в главе 14, где разрабатывается код для трассировки луча (ray trace) по сцене, описанной с помощью SDL. Студенты могут разрабатывать и создавать с помощью трассировки луча значительно более сложные и интересные сцены, чем это было возможно без SDL. Дополнительное использование PostScript В последние годы язык описания страниц PostScript фактически стал стандартным языком для размет- ки страниц (page-layout), поскольку он предлагает богатый набор операторов для аппаратно-независи- мого рисования текста и графики. Обычно PostScript работает незаметно внутри лазерного принтера, получая команды от текстового процессора или программы разметки и преобразуя их в линии, точки и символы. Однако можно подготовить «сценарий» (script) из команд PostScript и направить их принтеру, после чего встроенный в принтер интерпретатор PostScript создаст желаемую графику. Таким спосо- бом может быть создана прекрасная графика. Поэтому PostScript является блестящим примером крат- кого и мощного языка для 2О-графики, с теми же возможностями выполнения преобразований и визуа- лизации, что и OpenGL. Язык PostScript помещен в приложении, где студентам, заинтересованным в таком подходе к графи- ке, демонстрируется, как создавать интересные сценарии, которые создадут симпатичные картинки. Кроме того, в приложении показано, как загружать язык GhostScript и как работать с этим языком, в котором содержится экранный интерпретатор PostScript, позволяющий легко просматривать и отла- живать картинки во время их разработки. Структура книги и планы курса В книге намного больше материала, чем может вместить курс в один и даже в два семестра. Книга орга- низована так, что преподаватель может выбрать различную последовательность глав для подробного изучения — в зависимости от длительности курса, а также от интересов и подготовленности студентов ' В приложении 5 этот язык называется языком описания сцен (Scene Description Language — SDL). — Примеч. nep.
22 Введение группы. Ниже, после перечисления основных тем каждой главы, приведено несколько возможных по- следовательностей глав, выбранных из всей книги. Краткий обзор глав О Глава 1. В этой главе дается обзор всех областей применения компьютерной графики с примера- ми того, как используется графика в разных областях. Описаны различные виды имеющихся си- стем графического отображения, а также типы «примитивов» — полигоны (многоугольники), текст, изображения, — которые отображает данная графическая система. Кроме того, в данной главе описываются некоторые из многих широко применяющихся входных устройств: мышь, планшет (tablet), информационная перчатка (data glove) и т. д. О Глава 2. В этой главе студенты начинают писать графические приложения. Описано программи- рование с помощью OpenGL, приведено несколько законченных приложений для вычерчивания линий, в том числе популярного «ковра Серпинского» («Sierpinsky gasket»). Обсуждаются техни- ческие приемы использования OpenGL для рисования различных примитивов, таких как лома- ные линии и полигоны, а также применение мыши и клавиатуры в интерактивных графических приложениях. Практические примеры в конце главы содержат интересные программные проек- ты, помогающие студентам получить четкое начальное представление о том, как создается гра- фическое приложение. О Глава 3. В этой главе вводится центральное понятие отображения окна в порт просмотра (window- to-viewport mapping) для задания размеров и расположения изображений на экране. Обсуждает- ся управление окнами и портами просмотра по принципу «сделай сам» («do-it-yourself»), а также использование OpenGL для проработки деталей. Разрабатывается первый алгоритм отсечения графического изображения границами области (clipping). Кроме того, описываются задание мас- штабов (zooming), панорамирование (panning), наклон (tilting) с целью получения интересных визуальных эффектов, а также простейшая анимация рисунков. Разработан класс Canvas, вклю- чающий в себя все эти инструменты. Здесь же обсуждается рисование кругов, дуг, сложных фи- гур из многоугольников, а также представление двумерных и трехмерных кривых в параметри- ческой форме. О Глава 4. В этой главе дается обзор векторов и основных операций с ними, а также демонстриру- ется большое преимущество применения в графике векторных инструментов. Студенты, знако- мые с векторами, могут только просмотреть эту главу, обращая внимание на то, как с помощью векторов описываются соотношения между геометрическими объектами, которыми они манипу- лируют в своих программах. Там, где это возможно, векторные операции рассматриваются без указания на размерность пространства, но в трехмерном случае уделено специальное внимание применению векторного произведения (cross product). В четвертой главе введено понятие системы координат и показано, как такие системы делают ес- тественной работу с однородными координатами. Для прояснения различия между векторами и точками обсуждаются аффинные комбинации точек (чтобы помочь обойти обычный подводный камень при написании графических приложений). В некоторые приложения включены интерпо- ляция, простейшие кривые Безье (Bezier curves) и пересечения линий. Детально разработан фун- даментальный алгоритм отсечения прямой границами выпуклого многоугольника, а более слож- ные алгоритмы отсечения приведены в практических упражнениях по теме. (В одном из таких упражнений предложен интересный проект «Двумерная трассировка луча».) О Глава 5. Преобразования занимают центральное место в компьютерной графике, но студенты иногда испытывают затруднения при работе с ними, особенно с трехмерными преобразования- ми. В этой главе излагается базовая теория преобразований фигур и систем координат с исполь- зованием аффинных преобразований для двумерных и трехмерных случаев. С самого начала для описания преобразований применяются однородные координаты. Специальное внимание уделе- но трехмерным поворотам, поскольку общеизвестна трудность их визуализации. К инструмен-
Структура книги и планы курса 23 там класса Canvas, введенным в главе 3, добавляются средства для сдвига (shift), масштабирования (scale) и поворота (rotate) фигур посредством «текущего преобразования» («current transformation»), причем для осуществления этих функций привлечены матричные операции OpenGL Далее при- водится обзор конвейера просмотра OpenGL (viewing pipeline), а также описывается значение пре- образований моделирования-вида (modelview), проекции (projection) и порта просмотра. Рассмот- рено рисование трехмерных объектов с помощью инструментов OpenGL Впервые применен язык описания сцен (SDL), а также показано, как использовать интерпретатор SDL для чтения описа- ния трехмерной сцены из файла и рисования объектов, представленных в этом файле. О Глава 6. В этой главе рассматриваются средства моделирования и рисования сложных каркас- ных (mesh) объектов. Приводятся примеры каркасных объектов, в том числе многогранников, таких как додекаэдр и усеченный икосаэдр (buckyball), а также более сложных форм, таких как арки (arches), купола (domes), трубки (tubes), извивающиеся в пространстве, и поверхности вра- щения (surfaces of revolution). Рассмотрена техника визуализации этих объектов с различными способами закрашивания (shading) их поверхностей: плоским (flat) и плавным (smooth). О Глава 7. В этой главе рассматриваются средства для гибкого (flexible) просмотра трехмерных сцен. Задается «искусственная камера» («synthetic camera»), формирующая объемные представ- ления, и обсуждается ее связь с имеющимися в OpenGL средствами просмотра низкого уровня (low-level viewing). Создан удобный класс Camera, инкапсулирующий в себе детали управления камерой и упрощающий пилотирование камеры по сцене в процессе анимации. Подробно рассмотрен математический аппарат построения перспективных проекций (аксоно- метрического представления объемных объектов на плоскости) наряду с обсуждением вопроса о создании в рамках OpenGL перспективных проекций с использованием матричных преобразо- ваний. Подробно рассмотрен алгоритм отсечения, действующий в однородном координатном пространстве (он используется и в OpenGL). Описываются методы создания объемных изобра- жений. В к