Краткое содержание

Введение............................................................... 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

Описание 3D-сцен с помощью языка проектирования сцен.................................... 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

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. Рисование линий с использованием moveto() и lineto().................................. 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. Рисование линий и многоугольников пунктиром...................... 113

Тематическое задание 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() и lineRel().................................................. 146

3.5.2. Черепашья графика........................................................... 148

3.6. Фигуры на основе правильных многоугольников ........................................... 153

3.6.1. Правильные многоугольники.................................................... 153

3.6.2. Вариации n-угольников........................................................ 155

3.7. Рисование окружностей и дуг.......................................................... 159

3.7.1. Рисование дуг............................................................... 159

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

Тематическое задание 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

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. Тематические задания............................................................... 412

Тематическое задание 6.1. Сетки, записанные в файл ..................................... 412

Тематическое задание 6.2. Вывод метода Ньгаэлла........................................ 414

Тематическое задание 6.3. Призма.................................................... 416

Тематическое задание 6.4. Совокупность призм и экструдированные полосы из четырехугольников ... 417

Тематическое задание 6.5. Трубки и змейки на базе параметрической кривой.................... 418

Тематическое задание 6.6. Построение поверхностей вращения с дискретными шагами....... 419

Тематическое задание 6.7. Списки ребер и каркасные модели ............................... 419

Тематическое задание 6.8. Сводчатые потолки........................................... 420

Тематическое задание 6.9. О Платоновых телах.......................................... 420

Тематическое задание 6.10. Об Архимедовых телах........................................ 420

Тематическое задание 6.11. Алгебраическая форма поверхностей второго порядка................. 420

Тематическое задание 6.12. Сцены с супеквздриками....................................... 422

Тематическое задание 6.13. Рисование гладких параметрических поверхностей................... 422

Тематическое задание 6.14. Сузить, закрутить, изогнуть и расплющить......................... 423

6.8. Дополнительная литература .......................................................... 425

Глава 7. Трехмерный просмотр.......................................426

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. Создание стереоизображений ......................................................... 453

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

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. Применение процедурных 3D-текстур.............................. 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

9.6.2. Определение множества Мандельброта............................................ 590

9.6.3. Определение того, находится ли точка с в пределах множества Мандельброта.........592

9.6.4. Рисование множества Мандельброта .............................................. 593

9.6.5. Некоторые замечания по поводу множества Мандельброта.............................. 595

9.7. Множества Жюлиа.................................................................. 595

9.7.1. Плотное множество Жюлиа K_c................................................... 596

9.7.2. Рисование плотных множеств Жюлиа.............................................. 596

9.7.3. Некоторые замечания относительно неподвижных точек и бассейнов притяжения......596

9.7.4. Множество Жюлиа J_c.......................................................... 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

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

 

 

Глава 12. Теория цвета..............................................770

12.1. Введение........................................................................ 770

12.2. Описания цветов.................................................................. 772

12.2.1. Доминантная длина волны..................................................... 773

12.2.2. Подбор цветов.............................................................. 774

12.3. Международная комиссия по стандартам освещенности..................................... 777

12.3.1. Построение CIE-диаграммы .................................................... 778

12.3.2. Использование хроматической CIE-диаграммы...................................... 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. Рисование CIE-диаграммы...................................... 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

Глава 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. Трассировка лучей с 3D-текстурами.............................. 937

Тематическое задание 14.6. Сглаживание............................................... 937

Тематическое задание 14.7. Трассировка лучей для других примитивов........................ 937

Тематическое задание 14.8. Двумерный трассировщик лучей для работы с преломлением...938

Тематическое задание 14.9. Отраженный и преломленный свет.............................. 938

Тематическое задание 14.10. Трассировка Булевых комбинаций объектов........................ 938

14.15. Дополнительная литература ......................................................... 938

Приложение А. Графический инструментарий: получение OpenGL.........939

А1. Получение и инсталляция OpenGL ...................................................... 939

Приложение Б. Немного математики для компьютерной графики.........941

Б1. Некоторые основные определения, относящиеся к матрицам и операциям над ними.... 941

Б1.1. Действия с матрицами ......................................................... 942

Б1.2. Умножение двух матриц........................................................ 943

Б1.3. Разбиение матрицы на блоки .................................................... 944

Б1.4. Определитель матрицы......................................................... 945

Б1.5. Обращение матрицы........................................................... 946

Б2. Некоторые свойства векторов и операции над ними......................................... 948

Б2.1. Перп вектора; перп-скалярное произведение......................................... 948

Б2.2. Смешанное произведение..................................................... 949

Б2.3. Двойное векторное произведение................................................. 950

Б3. Арифметика комплексных чисел........................................................ 950

Б4. Сферические координаты и направляющие косинусы........................................ 953

Приложение В. Некоторые полезные классы и служебные подпрограммы ... 956

B1. Классы для двумерной графики........................................................ 957

B2. RGBPixmap CLASS................................................................... 961

B3. Класс SCENE и сопутствующие классы.................................................... 966

B4. Класс NOISE....................................................................... 995

B5. Некоторые классы, полезные при трассировке лучей......................................... 998

Приложение Г. Введение в PostScript^®................................ 1001

Г1. О языке 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

Г3. Рисование текста в 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

Д3. Расширение SDL................................................................... 1044

Литература....................................................... 1046

Список терминов..................................................1058

Алфавитный указатель............................................. 1065