計(jì)算機(jī)圖形學(xué)的算法基礎(chǔ)（原書第2版）

第1版序
第1章   計(jì)算機(jī)圖形學(xué)導(dǎo)論 1
1.1   計(jì)算機(jī)圖形學(xué)概述 1
1.1.1   圖形的表示方法 1
1.1.2   表示圖形的數(shù)據(jù)準(zhǔn)備 2
1.1.3   圖形的顯示 2
1.2   光柵刷新圖形顯示器 4
1.3   陰極射線管的基礎(chǔ)知識(shí) 9
1.4   視頻知識(shí)基礎(chǔ) 11
1.4.1   美國(guó)標(biāo)準(zhǔn)視頻制式 11
1.4.2   高清晰度電視 12
1.5   平板顯示器 13
1.5.1   平板式CRT 13
1.5.2   等離子顯示器 13
1.5.3   熒光顯示器 15
1.5.4   液晶顯示器 16
1.6   硬拷貝輸出設(shè)備 18
1.6.1   靜電繪圖儀 18
1.6.2   噴墨繪圖儀 19
1.6.3   熱敏繪圖儀 22
1.6.4   染料升華打印機(jī) 22
1.6.5   筆墨繪圖儀 23
1.6.6   激光打印機(jī) 25
1.6.7   彩色膠片照相機(jī) 27
1.7   邏輯交互設(shè)備 28
1.8   物理交互設(shè)備 28
1.9   數(shù)據(jù)生成設(shè)備 34
1.10   圖形用戶界面 37
第2章   光柵掃描圖形學(xué) 46
2.1   直線生成算法 46
2.2   數(shù)字微分分析法 47
2.3   Bresenham算法 50
2.3.1   整數(shù)Bresenham算法 53
2.3.2   通用Bresenham算法 54
2.3.3   快速直線光柵化算法 56
2.4   圓的生成—Bresenham算法 57
2.5   橢圓的生成 64
2.6   一般函數(shù)的光柵化 69
2.7   掃描轉(zhuǎn)換—顯示的生成 71
2.7.1   實(shí)時(shí)掃描轉(zhuǎn)換 71
2.7.2   使用指針的簡(jiǎn)單活化邊表 72
2.7.3   排序活化邊表 72
2.7.4   使用鏈表的活化邊表 74
2.7.5   修改鏈表  74
2.8   圖像壓縮 77
2.8.1   行程編碼 77
2.8.2   區(qū)域圖像壓縮 79
2.9   顯示直線. 字符和多邊形 82
2.9.1   線段顯示 82
2.9.2   字符顯示 84
2.9.3   實(shí)區(qū)域掃描轉(zhuǎn)換 84
2.10   多邊形填充 85
2.11   簡(jiǎn)單的奇偶掃描轉(zhuǎn)換算法 88
2.12   有序邊表多邊形掃描轉(zhuǎn)換 90
2.12.1   簡(jiǎn)單的有序邊表算法 90
2.12.2   更有效的有序邊表算法 92
2.13   邊填充算法 95
2.14   邊標(biāo)志算法 97
2.15   種子填充算法 99
2.15.1   簡(jiǎn)單的種子填充算法 102
2.15.2   掃描線種子填充算法 102
2.16   圖形反走樣基礎(chǔ) 106
2.16.1   超采樣 107
2.16.2   直線 107
2.16.3   多邊形內(nèi)部 113
2.16.4   簡(jiǎn)單區(qū)域反走樣 114
2.16.5   卷積積分與反走樣算法 117
2.16.6   濾波函數(shù) 119
2.17    半色調(diào)技術(shù) 120
2.17.1   模版化 121
2.17.2   閾值和誤差分布 124
2.17.3   有序抖動(dòng) 128
第3章   裁剪 131
3.1   二維裁剪 131
3.1.1   簡(jiǎn)單可見性判別算法 131
3.1.2   端點(diǎn)編碼 133
3.2   Cohen-Sutherland線段細(xì)分裁剪算法 136
3.3   中點(diǎn)分割算法 140
3.4   凸區(qū)域的二維參數(shù)化線段裁剪 144
3.5   Cyrus-Beck算法 148
3.5.1   部分可見線段 150
3.5.2   完全可見線段 151
3.5.3   完全不可見線段 151
3.5.4   Cyrus-Beck算法的形式化描述 153
3.5.5   非規(guī)則窗口 156
3.6   Liang-Barsky二維裁剪 157
3.7   Nicholl-Lee-Nicholl二維裁剪 164
3.8   內(nèi)裁剪和外裁剪 167
3.9   凸多邊形的判定和內(nèi)法線確定 168
3.10   凹多邊形分割 172
3.11   三維裁剪 172
3.12   三維中點(diǎn)分割算法 175
3.13   三維Cyrus-Beck算法 177
3.14   Liang-Barsky三維裁剪 181
3.15   齊次坐標(biāo)裁剪 185
3.15.1   Cyrus-Beck算法 185
3.15.2   Liang-Barsky算法 186
3.16   內(nèi)法矢量和三維凸集合的確定 189
3.17   凹體分割 190
3.18   多邊形裁剪 192
3.19   逐次多邊形裁剪—Sutherland-
Hodgman算法 193
3.19.1   確定一個(gè)點(diǎn)的可見性 194
3.19.2   線段求交 196
3.19.3   算法 197
3.20   Liang-Barsky多邊形裁剪 202
3.20.1   進(jìn)點(diǎn)和出點(diǎn) 203
3.20.2   折點(diǎn) 203
3.20.3   算法設(shè)計(jì) 205
3.20.4   水平邊和垂直邊 207
3.20.5   算法 208
3.21   凹裁剪區(qū)域—Weiler-Atherton算法 211
3.22   字符裁剪 218
第4章   可見面 220
4.1   引言 220
4.2   浮動(dòng)水平線算法 221
4.2.1   上浮水平線 221
4.2.2   下浮水平線 222
4.2.3   函數(shù)插值 223
4.2.4   走樣 226
4.2.5   算法 227
4.2.6   交叉影線 233
4.3   Roberts算法 235
4.3.1   體矩陣 235
4.3.2   平面方程 237
4.3.3   取景變換和體矩陣 240
4.3.4   自隱藏面 241
4.3.5   被其他物體遮擋的線 244
4.3.6   貫穿體 252
4.3.7   完全可見線段 252
4.3.8   算法 255
4.4   Warnock算法 263
4.4.1   四叉樹結(jié)構(gòu) 265
4.4.2   分割準(zhǔn)則 265
4.4.3   多邊形與窗口的關(guān)系 267
4.4.4   多邊形與窗口關(guān)系的分層次辨別 272
4.4.5   尋找包圍多邊形 273
4.4.6   基本算法 275
4.5   Appel算法 280
4.6   附著光暈的線消隱算法 282
4.7   Weiler-Atherton算法 284
4.8   曲面分割算法 287
4.9   Z緩沖器算法 288
4.9.1   采用增量法計(jì)算深度值 290
4.9.2   層次Z緩沖器算法 295
4.10   A緩沖器算法 296
4.11   優(yōu)先級(jí)排序表算法 298
4.12   Newell-Newell-Sancha算法 299
4.13   二叉空間剖分算法 302
4.13.1   Schumacker算法 303
4.13.2   二叉空間剖分樹 304
4.13.3   構(gòu)造BSP樹 304
4.13.4   BSP樹遍歷 306
4.13.5   背面剔除 308
4.13.6   小結(jié) 308
4.14   掃描線算法 308
4.15   掃描線Z緩沖器算法 309
4.16   區(qū)間掃描線算法 312
4.16.1   不可見相關(guān)性 319
4.16.2   景物空間掃描線算法 320
4.17   曲面掃描線算法 320
4.18   八叉樹 323
4.18.1   八叉樹顯示 325
4.18.2   線性八叉樹 327
4.18.3   八叉樹的操作 327
4.18.4   布爾運(yùn)算 328
4.18.5   搜索相鄰單元 328
4.19   移動(dòng)立方體算法 328
4.20   可見面光線跟蹤算法 332
4.20.1   包圍體 334
4.20.2   叢 337
4.20.3   建立叢的樹結(jié)構(gòu) 338
4.20.4   優(yōu)先級(jí)排序 338
4.20.5   空間剖分 339
4.20.6   均勻空間剖分 340
4.20.7   非均勻空間剖分 342
4.20.8   光線－物體求交 344
4.20.9   不透明可見面算法 347
4.21   小結(jié) 350
第5章   繪制 351
5.1   引言 351
5.2   光照模型 352
5.3   一個(gè)簡(jiǎn)單的光照模型 353
5.3.1   鏡面反射 354
5.3.2   中值矢量 357
5.4   確定表面法向 359
5.5   確定反射光線矢量 360
5.6   Gouraud明暗處理 363
5.7   Phong明暗處理 366
5.8   具有特殊效果的簡(jiǎn)單光照模型 370
5.9   基于物理的光照模型 372
5.9.1   能量和輻射強(qiáng)度 372
5.9.2   基于物理的光照模型 373
5.9.3   Torrance-Sparrow關(guān)于粗糙表面
的模型 374
5.9.4   與波長(zhǎng)相關(guān)的菲涅耳項(xiàng) 377
5.9.5   顏色轉(zhuǎn)變 378
5.9.6   光源的物理特性 379
5.10   透明 380
5.10.1   透明材料的折射效果 381
5.10.2   簡(jiǎn)單的透明模型 382
5.10.3   Z緩沖器算法中的透明處理 383
5.10.4   偽透明 384
5.11   陰影 385
5.11.1   掃描轉(zhuǎn)換陰影算法 388
5.11.2   多步可見面陰影算法 389
5.11.3   陰影體算法 391
5.11.4   半影 394
5.11.5   光線跟蹤陰影算法 396
5.12   紋理 397
5.12.1   映射函數(shù) 402
5.12.2   兩步紋理映射 405
5.12.3   環(huán)境映射 407
5.12.4   凹凸紋理 409
5.12.5   過程紋理 411
5.12.6   紋理反走樣 413
5.12.7   Mipmapping 417
5.12.8   區(qū)域求和表 417
5.13   隨機(jī)模型 418
5.14   采用光線跟蹤的整體光照模型 420
5.15   采用光線跟蹤的更完整的
整體光照模型 431
5.16   光線跟蹤技術(shù)的最新進(jìn)展 433
5.16.1   圓錐跟蹤 433
5.16.2   光束跟蹤 434
5.16.3   一般光束跟蹤 434
5.16.4   隨機(jī)采樣 435
5.16.5   從光源出發(fā)的光線跟蹤 437
5.17   輻射度 437
5.17.1   封閉性 439
5.17.2   形狀因子 440
5.17.3   半立方體 442
5.17.4   繪制 447
5.17.5   子結(jié)構(gòu) 447
5.17.6   逐步求精 448
5.17.7   排序 449
5.17.8   泛光貢獻(xiàn) 449
5.17.9   自適應(yīng)剖分 450
5.17.10   半立方體方法的不精確性 451
5.17.11   半立方體方法外的其他方法 454
5.17.12   層次輻射度和聚集 456
5.17.13   鏡面環(huán)境的輻射度 457
5.17.14   繪制方程 458
5.18   光線跟蹤和輻射度的結(jié)合 458
5.19   顏色 462
5.19.1   色度 462
5.19.2   顏色的三刺激理論 463
5.19.3   原色系統(tǒng) 464
5.19.4   顏色匹配實(shí)驗(yàn) 464
5.19.5   色度圖 466
5.19.6   1931年CIE色度圖 468
5.19.7   均勻顏色空間 471
5.19.8   顏色域的局限 472
5.19.9   顏色系統(tǒng)之間的相互轉(zhuǎn)化 473
5.19.10   NTSC顏色系統(tǒng) 476
5.19.11   顏色立方體 477
5.19.12   CMYK顏色系統(tǒng) 477
5.19.13   Ostwald顏色系統(tǒng) 478
5.19.14   HSV顏色系統(tǒng) 478
5.19.15   HLS顏色系統(tǒng) 481
5.19.16   Munsell顏色系統(tǒng) 483
5.19.17   Panetoneㄏ低?484
5.19.18   Gamma校正 484
5.20   彩色圖像的量化 485
5.20.1   位截?cái)喾?486
5.20.2   流行色法 487
5.20.3   中分截?cái)喾?489
5.20.4   八叉樹量化 491
5.20.5   順序標(biāo)量量化 494
5.20.6   其他量化算法 496
5.21   顏色重現(xiàn) 497
5.21.1   平版打印 497
5.21.2   分色 498
5.21.3   色調(diào)重現(xiàn) 498
5.21.4   灰度平衡 498
5.21.5   黑色分離 498
5.21.6   量化效果 498
5.21.7   校準(zhǔn) 499
5.21.8   色域映射 499
5.22   特殊繪制效果 501
5.22.1   雙色套印 501
5.22.2   繪制自然物體 503
5.22.3   粒子系統(tǒng) 503
附錄A   習(xí)題 504
參考文獻(xiàn) 510
索引 536