Роджерс Д. Алгоритмические основы машинной графики:
Пер. с англ.

ОГЛАВЛЕНИЕ

Предисловие редакторов перевода.......................................5

Предисловие к русскому изданию.......................................7

Предисловие............................................................9

ГЛАВА 1. ВВЕДЕНИЕ В МАШИННУЮ ГРАФИКУ...................13

1.1. Обзор машинной графики....................................13

1.2. Типы графических устройств..................................15

1.3. Графические дисплеи на запоминающей трубке................16

1.4. Векторные графические дисплеи с регенерацией изображения..18

1.5. Растровые графические дисплеи с регенерацией изображения...23

1.6. Устройство электронно-лучевой трубки........................30

1.7. Устройство цветной растровой ЭЛТ..........................31

1.8. Системы с телевизионным растром...........................33

1.9. Диалоговые устройства.......................................36

1.10. Резюме.......................................................46

1.11. Литература...................................................46

ГЛАВА 2. РАСТРОВАЯ ГРАФИКА...................................48

2.1. Алгоритмы вычерчивания отрезков...........................48

2.2. Цифровой дифференциальный анализатор.....................50

2.3. Алгоритм Брезенхема.........................................54

2.4. Целочисленный алгоритм Брезенхема.........................59

2.5. Общий алгоритм Брезенхема.................................60

2.6. Алгоритм Брезенхема для генерации окружности..............63

2.7. Растровая развертка — способ генерация изображения........73

2.8. Растровая развертка в реальном времени.....................73

2.9. Групповое кодирование.......................................80

2.10. Клеточное кодирование.......................................83

2.11. Буферы кадра................................................85

2.12. Адресация растра.............................................87

2.13. Изображение отрезков........................................89

2.14. Изображение литер...........................................91

2.15. Растровая развертка сплошных областей......................92

2.16. Заполнение многоугольников..................................93

2.17. Растровая развертка многоугольников.........................94

2.18. Простой алгоритм с упорядоченным списком ребер...........97

2.19. Более эффективные алгоритмы с упорядоченным списком

ребер.........................................................99

2.20. Алгоритм заполнения по ребрам.............................105

2.21. Алгоритм со списком ребер и флагом.......................107

2.22. Алгоритмы заполнения с затравкой..........................10О

2.23. Простой алгоритм заполнения с затравкой...................111

2.24. Построчный алгоритм заполнения с затравкой...............114

2.25. Основы методов устранения ступенчатости...................119

2.26. Простой метод устранения лестничного эффекта.............123

2.27. Свертка и устранение ступенчатости.........................127

2.28. Аппроксимация полутонами..................................131

2.29. Литература..................................................139

ГЛАВА 3. ОТСЕЧЕНИЕ.............................................142

3.1. Двумерное отсечение........................................143

3.2. Алгоритм отсечения Сазерленда — Коэна, основанный на разбиении отрезка..............................................153

3.3. Алгоритм разбиения средней точкой.........................158

3.4. Обобщение: отсечение двумерного отрезка выпуклым окном.166

3.5. Алгоритм Кируса — Бека...................................170

3.6. Внутреннее и внешнее отсечение.............................181

3.7. Определение факта выпуклости многоугольника и вычисление его внутренних нормалей....................................182

3.8. Разбиение невыпуклых многоугольников......................187

3.9. Трехмерное отсечение........................................188

3.10. Трехмерный алгоритм разбиения средней точкой.............192

3.11. Трехмерный алгоритм Кируса — Бека.......................194

3.12. Отсечение в однородных координатах........................198

3.13. Определение выпуклости трехмерного тела и вычисление внутренних нормалей к его граням...............................201

3.14. Разрезание невыпуклых тел..................................203

3.15. Отсечение многоугольников..................................206

3.16. Последовательное отсечение многоугольника — алгоритм Сазерленда — Ходжмана......................................207

3.17. Невыпуклые отсекающие области — алгоритм Вейлера — Азертона...............................;....................220

3.18. Отсечение литер.............................................227

3.19. Литература..................................................228

ГЛАВА 4. УДАЛЕНИЕ НЕВИДИМЫХ ЛИНИЙ И ПОВЕРХНОСТЕЙ.. 230

4.1. Введение....................................................230

4.2. Алгоритм плавающего горизонта............................233

4.3. Алгоритм Робертса..........................................250

4.4. Алгоритм Варнока..........................................290

4.5. Алгоритм Вейлера — Азертона..............................315

4.6. Алгоритм разбиения криволинейных поверхностей............320

4.7. Алгоритм, использующий г-буфер............................321

4.8. Алгоритмы, использующие список приоритетов..............329

4.9. Алгоритмы построчного сканирования.......................338

4.10. Алгоритм построчного сканирования, использующий

г-буфер......................................................339

4.11. Интервальный алгоритм построчного сканирования..........345

4.12. Алгоритмы построчного сканирования для криволинейных поверхностей................................................ 355

4.13. Алгоритм определения видимых поверхностей путем трассировки лучей...............................................360

4.14. Резюме.....................................................373

4.15. Литература.................................................374

ГЛАВА 5. ПОСТРОЕНИЕ РЕАЛИСТИЧЕСКИХ ИЗОБРАЖЕНИЙ....377

5.1. Введение....................................................377

5.2. Простая модель освещения..................................380

5.3. Определение нормали к поверхности.........................386

5.4. Определение вектора отражения.............................388

5.5. Закраска методом Гуро......................................391

5.6. Закраска Фонга..............................................394

5.7. Простая модель освещения со специальными эффектами.....399

5.8. Более полная модель освещения.............................401

5.9. Прозрачность................................................410

5.10. Тени........................................................416

5.11. Фактура.....................................................427

5.12. Глобальная модель освещения с трассировкой лучей.........437

5.13. Более полная глобальная модель освещения с трассировкой лучей........................................................454

5.14. Направления современных исследований......................457

5.15. Цвет........................................................458

5.16. Литература..................................................487

Приложение А. Псевдокод............:...............................490

Приложение В. Задачи................................................495