計算機圖形學的算法基礎（原書第2版）

第1版序
第1章   計算機圖形學導論 1
1.1   計算機圖形學概述 1
1.1.1   圖形的表示方法 1
1.1.2   表示圖形的數(shù)據(jù)準備 2
1.1.3   圖形的顯示 2
1.2   光柵刷新圖形顯示器 4
1.3   陰極射線管的基礎知識 9
1.4   視頻知識基礎 11
1.4.1   美國標準視頻制式 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   硬拷貝輸出設備 18
1.6.1   靜電繪圖儀 18
1.6.2   噴墨繪圖儀 19
1.6.3   熱敏繪圖儀 22
1.6.4   染料升華打印機 22
1.6.5   筆墨繪圖儀 23
1.6.6   激光打印機 25
1.6.7   彩色膠片照相機 27
1.7   邏輯交互設備 28
1.8   物理交互設備 28
1.9   數(shù)據(jù)生成設備 34
1.10   圖形用戶界面 37
第2章   光柵掃描圖形學 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   掃描轉換—顯示的生成 71
2.7.1   實時掃描轉換 71
2.7.2   使用指針的簡單活化邊表 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   實區(qū)域掃描轉換 84
2.10   多邊形填充 85
2.11   簡單的奇偶掃描轉換算法 88
2.12   有序邊表多邊形掃描轉換 90
2.12.1   簡單的有序邊表算法 90
2.12.2   更有效的有序邊表算法 92
2.13   邊填充算法 95
2.14   邊標志算法 97
2.15   種子填充算法 99
2.15.1   簡單的種子填充算法 102
2.15.2   掃描線種子填充算法 102
2.16   圖形反走樣基礎 106
2.16.1   超采樣 107
2.16.2   直線 107
2.16.3   多邊形內(nèi)部 113
2.16.4   簡單區(qū)域反走樣 114
2.16.5   卷積積分與反走樣算法 117
2.16.6   濾波函數(shù) 119
2.17    半色調(diào)技術 120
2.17.1   模版化 121
2.17.2   閾值和誤差分布 124
2.17.3   有序抖動 128
第3章   裁剪 131
3.1   二維裁剪 131
3.1.1   簡單可見性判別算法 131
3.1.2   端點編碼 133
3.2   Cohen-Sutherland線段細分裁剪算法 136
3.3   中點分割算法 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   三維中點分割算法 175
3.13   三維Cyrus-Beck算法 177
3.14   Liang-Barsky三維裁剪 181
3.15   齊次坐標裁剪 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   確定一個點的可見性 194
3.19.2   線段求交 196
3.19.3   算法 197
3.20   Liang-Barsky多邊形裁剪 202
3.20.1   進點和出點 203
3.20.2   折點 203
3.20.3   算法設計 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   浮動水平線算法 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   四叉樹結構 265
4.4.2   分割準則 265
4.4.3   多邊形與窗口的關系 267
4.4.4   多邊形與窗口關系的分層次辨別 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   采用增量法計算深度值 290
4.9.2   層次Z緩沖器算法 295
4.10   A緩沖器算法 296
4.11   優(yōu)先級排序表算法 298
4.12   Newell-Newell-Sancha算法 299
4.13   二叉空間剖分算法 302
4.13.1   Schumacker算法 303
4.13.2   二叉空間剖分樹 304
4.13.3   構造BSP樹 304
4.13.4   BSP樹遍歷 306
4.13.5   背面剔除 308
4.13.6   小結 308
4.14   掃描線算法 308
4.15   掃描線Z緩沖器算法 309
4.16   區(qū)間掃描線算法 312
4.16.1   不可見相關性 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   布爾運算 328
4.18.5   搜索相鄰單元 328
4.19   移動立方體算法 328
4.20   可見面光線跟蹤算法 332
4.20.1   包圍體 334
4.20.2   叢 337
4.20.3   建立叢的樹結構 338
4.20.4   優(yōu)先級排序 338
4.20.5   空間剖分 339
4.20.6   均勻空間剖分 340
4.20.7   非均勻空間剖分 342
4.20.8   光線－物體求交 344
4.20.9   不透明可見面算法 347
4.21   小結 350
第5章   繪制 351
5.1   引言 351
5.2   光照模型 352
5.3   一個簡單的光照模型 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   具有特殊效果的簡單光照模型 370
5.9   基于物理的光照模型 372
5.9.1   能量和輻射強度 372
5.9.2   基于物理的光照模型 373
5.9.3   Torrance-Sparrow關于粗糙表面
的模型 374
5.9.4   與波長相關的菲涅耳項 377
5.9.5   顏色轉變 378
5.9.6   光源的物理特性 379
5.10   透明 380
5.10.1   透明材料的折射效果 381
5.10.2   簡單的透明模型 382
5.10.3   Z緩沖器算法中的透明處理 383
5.10.4   偽透明 384
5.11   陰影 385
5.11.1   掃描轉換陰影算法 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   隨機模型 418
5.14   采用光線跟蹤的整體光照模型 420
5.15   采用光線跟蹤的更完整的
整體光照模型 431
5.16   光線跟蹤技術的最新進展 433
5.16.1   圓錐跟蹤 433
5.16.2   光束跟蹤 434
5.16.3   一般光束跟蹤 434
5.16.4   隨機采樣 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   子結構 447
5.17.6   逐步求精 448
5.17.7   排序 449
5.17.8   泛光貢獻 449
5.17.9   自適應剖分 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   光線跟蹤和輻射度的結合 458
5.19   顏色 462
5.19.1   色度 462
5.19.2   顏色的三刺激理論 463
5.19.3   原色系統(tǒng) 464
5.19.4   顏色匹配實驗 464
5.19.5   色度圖 466
5.19.6   1931年CIE色度圖 468
5.19.7   均勻顏色空間 471
5.19.8   顏色域的局限 472
5.19.9   顏色系統(tǒng)之間的相互轉化 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   位截斷法 486
5.20.2   流行色法 487
5.20.3   中分截斷法 489
5.20.4   八叉樹量化 491
5.20.5   順序標量量化 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   校準 499
5.21.8   色域映射 499
5.22   特殊繪制效果 501
5.22.1   雙色套印 501
5.22.2   繪制自然物體 503
5.22.3   粒子系統(tǒng) 503
附錄A   習題 504
參考文獻 510
索引 536