本书从图形学最基础的光栅扫描、区域填充、画直线和圆弧等算法讲起，详细介绍了线裁剪和面裁剪、凸区域裁剪和凹区域裁剪的异同，景物空间消隐算法和图像空间消隐算法的差别，具体讲述了二叉空间剖分(BSP)、八叉树等图形学中常用的数据结构。新版本增加了图形用户界面、椭圆、图像压缩和线条反走样算法等，还增加了Liang-Barsky裁剪算法和Nicholl-Lee-Nicholl裁剪算法。新版本大大扩充了可见面光线跟踪算法。在绘制这一章中新增了基于物理的光照明模型，透明效果，阴影生成，纹理映射，以及锥光束、平面光束、笔形光束和随机光线跟踪算法；详细讨论了光辐射度基础，统一颜色空间，彩色图象量化和印刷介质上的颜色重现等新内容。本书列举了90个例子，具体描述了各类算法的执行细节。这对初学者体会算法的基本原理，比较各类算法执行时的细微差别大有禅益。具备大学数学基础和高级程序设计语言知识的人均可自学本书。
本书适合专业程序员、工程师及科研人员使用。非常适用于作为为高年级本科生和一年级研究生开设的重点讲授绘制技术的计算机图形学课程的教科书。
我在第1版的序言中曾说过“计算机图形学已经成为成熟的学科了”，当时我们很少有人能预见到它这20余年来的发展。那个时候，光线跟踪还只是一个活跃的研究方向—但现在即便是个人电脑也可随意使用这类程序了；那时，辐射度的研究才刚刚起步，但今天的商品化绘制软件已经普遍使用了这项技术；那时，纹理是软件实现的，但现在硬件纹理加速已经很普遍了；那时，彩色图像的量化算法只在计算机图形学界中得到有限使用，但今天即便从万维网上下载图片也要用到图像量化技术。还可以找到一长串图形技术进步的例子。总之，今天的计算机图形学已经紧密地与日常生活结合在一起，它所涉及的领域遍及广告、娱乐、医学、教育、科学、工程、航空，等等。大部分计算机软件，包括使用频率最高的操作系统，都使用了图形化的用户界面。
在这一版中，我改写了第1版的很大一部分内容，这样做的结果是新版本的篇幅差不多是原来的两倍。增加的内容主要集中于图形用户界面以及直线、圆、椭圆的生成和图像压缩等算法的扩充。新版本还给出了直线和多边形裁剪的新算法，特别是在介绍经典的Cohen-Sutherland裁剪算法、中点分割算法、Cyrus-Beck裁剪算法和Sutherland-Hodgman裁剪算法的同时，重点讨论了Liang-Barsky裁剪算法和Nicholl-Lee-Nicholl裁剪算法。
可见面算法这一章在讨论二叉空间剖分(Binary Space Partitioning, BSP)、八义树和移动立方体等算法的同时，还用专门的篇幅介绍了Appel、晕线和A—buffer等算法。可见面光线跟踪算法也有很大扩充。
绘制这一章也增加了不少内容。对基于物理的光照明模型、透明性、阴影和纹理等处理方法进行了扩充。在讨论辐射度基本理论的同时，我们还介绍了光线跟踪的最新进展，如锥光线跟踪、束光线跟踪、笔束光线跟踪和随机光线跟踪等。颜色一节补充了均匀颜色空间，并对gamma矫正进行了更为详细的讨论。还专门讨论了彩色图像的量化和在印刷介质上的颜色再现问题。
本书适合专业程序员、工程师及科研人员使用。本书也非常适用于为高年级本科生和一年级研究生开设的重点讲授绘制技术的计算机图形学课程的教科书。如果与本书的姊妹篇《Mathematical Elements for Computer Graphics》(计算机图形学的数学基础)配合使用，课程内容就会扩大到包含各种可操纵变换、曲线和曲面等。在保留第1版例子的基础上，这一版还给出了一些新例子，共有90个。只要具有大学数学和程序设计语言基本知识的人都可以使用本书。
任何不给出算法的计算机图形学书籍都将是不完整的。本书介绍的算法采用三种方法来描述。第一种是用列表的形式给出的语言描述；第二种是详细算法的过程描述；第三种是更为形式化的伪代码描述。尽管现在许多书籍用C语言描述算法，但我不赶这个时髦。我相信只有真正实现一个算法才能对其有深刻的理解，并对算法的细枝末节有所体会，这是书本所不能涵盖的。而且只有在实现算法时才能领会实现语言所特有的效率。实现那些用伪码表示的算法比实现其他两类算法相对要更直观些。
如果没有他人的帮助，要完成一本书是不可能的。衷心感谢阅读了手稿各个部分的同事们。其中，JohnDill和他的学生阅读了有关裁剪的第3章，并提出了许多有价值的建议。PaulHeckbert审阅了彩色图像量化和纹理这两节，他的建议为这两部分增色不少。Maureen Stone在颜色再现方面给了我很多帮助。Eric Haines对光线跟踪部分提出了相当多的建议。我还从后来的讨论中受益匪浅。John Wallace阅读了有关辐射度的部分，并就关键几点为我指点迷津。如果仍有不当之处的话，那是我的错。
我要向在法国Grenoble从事iMAGIS项目的同事Fran峯is Sillion和Peter Kipfer表示特别的感谢，他们应用自行开发的层次光线跟踪软件，在极短的时间内制作了封面图像。他们热情地完成了我所要求的修改，和他们合作我感到十分愉快。
还要提一下和我合作25年之久的编辑B. J. Clark，虽然他现在已经不再从事这一万面的工作了，但想想当年我还只是一个有志于在计算机图形学方面出一本书的年轻学者时，如果没有他对我的信任，以及多年来他无微不至的鼓励和关怀，就不会有我今天的一切。还要感谢Fine Line Illustrations公司的Fred Eckardt及其同事，他们在绘制本书插图方面帮了我大忙，他们甚至惠允我使用部分原始文件。McGraw-Hill出版公司的Kari Geltemeyer. Laurie Entringer和Heather Burbridge等也做出了很大贡献。
最后要提一下我的妻子Nancy，把她放在最后当然不意味着她的贡献小。我要向她致以特别的谢意。她不仅在我写作过程中表现出了极大的耐心，而且还做了大量的誊写、编辑、校对和打字工作。我想Nancy现在绝对是一个TEX编辑高手。
David F．Rogers
石教英 彭群生 等：暂无简介
1985年春，美国佛罗里达大学教授、IEEE CG&A学术期刊时任主编John Staudhammer先生应邀来浙江大学讲学，向我们推荐了 David Rogers编写的图形学新著《Procedural Elements of Computer Graphics》。该书取材新颖，内容全面，便于自学，立即引起了大家的浓厚兴趣。当时国内计算机图形学研究正处于起步阶段，有关计算机图形学的中文教材和参考书甚少。因此我们立即着手组织翻译。中译本取名为《计算机图形学的算法基础》，由科学出版社出版。首批5000册不到3个月即销售一空，许多没有买到该书的人只好整本地复印。该书的出版，对我国计算机图形学的发展曾起了很好的作用。不少人以这本书为向导，走上了从事图形学研究的道路。
时隔14年，机械工业出版社购买了Rogers教授新版《Procedural Elements of Computer Graphics》的翻译版权，并委托我们翻译。我们很高兴接受了这一任务。与第1版相比，新版的篇幅几乎增加了一倍。从80年代到90年代，正是计算机图形学蓬勃发展的黄金时期，光线跟踪和光能辐射度方法逐渐发展成为真实感图形绘制的两大主流技术。新版收集整理了这一期间所涌现出来的大量优秀的算法，包括各种快速光线跟踪算法，带反走样的纹理映射技术以及逐步求精辐射度方法等。此外，新版继续保持了原书概念清晰、举例详细、便于自学的风格。本书从图形学最基础的光栅扫描、区域填充、画直线和圆弧等算法开始讲解，详细介绍了线裁剪和面裁剪、凸区域裁剪和凹区域裁剪的异同，景物空间消隐算法和图象空间消隐算法的差别，具体讲述了二叉空间剖分（BSP）、八叉树等图形学中常用的数据结构。每一章都增添了新的内容，反映了在该领域图形学的最新研究成果。特别需要指出的是，图形学是一门只有通过实践才能掌握的学科，本书列举了90个例子，具体描述了各类算法的执行细节。这对初学者体会算法的基本原理，比较各类算法执行时的细微差别大有裨益。具备大学数学基础和高级程序设计语言知识的人均可自学本书。
本书的作者David Rogers是一位资深的图形学专家。他长期任职于美国海军科学院，从事计算机图形学的教学与科研。曾出版学术著作4部，主编多部。他编著的《Procedural Elements of Computer Graphics》（第1版），曾被评为美国Top-Five(前5名)图形学教科书，并先后被翻译成六种语言文字出版。
翻译如此一本学术名著实在是一件困难的事。尽管我们有翻译本书第1版的经验，翻译工作量仍然巨大。本书的前言、第1、2章仍由石教英负责，第3～5章仍由彭群生负责。张明敏、赵友兵参与了本书第1、2章的翻译，刘新国、陈莉、冯结青分别参与了第3～5章的翻译，全书由石教英、彭群生仔细校对、修改定稿。梁友栋教授校对了第3～5节清样，并提出了许多宝贵意见。在翻译过程中，我们发现原书的一些错误之处，其中大部分为排版和印刷错误，译文中已一一作了订正。我们也曾遇到一些国内尚未见到、尚无统一译法的名词，如Haloed Line、Pencil tracing、the popularity algorithm等，我们斟酌选用了最能表达其含义的译法，详见本书索引。这些译法是否恰当，仍有待读者认可。由于译者水平和学识有限，译本中翻译不尽妥当之处在所难免，恳请读者批评指正。
译 者
2000年11月
第1版序
第1章 计算机图形学导论 1
1.1 计算机图形学概述 1
1.1.1 图形的表示方法 1
1.1.2 表示图形的数据准备 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 数据生成设备 34
1.10 图形用户界面 37
第2章 光栅扫描图形学 46
2.1 直线生成算法 46
2.2 数字微分分析法 47
2.3 Bresenham算法 50
2.3.1 整数Bresenham算法 53
2.3.2 通用Bresenham算法 54
2.3.3 快速直线光栅化算法 56
2.4 圆的生成—Bresenham算法 57
2.5 椭圆的生成 64
2.6 一般函数的光栅化 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 区域图像压缩 79
2.9 显示直线、字符和多边形 82
2.9.1 线段显示 82
2.9.2 字符显示 84
2.9.3 实区域扫描转换 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 多边形内部 113
2.16.4 简单区域反走样 114
2.16.5 卷积积分与反走样算法 117
2.16.6 滤波函数 119
2.17 半色调技术 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 凸区域的二维参数化线段裁剪 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 非规则窗口 156
3.6 Liang-Barsky二维裁剪 157
3.7 Nicholl-Lee-Nicholl二维裁剪 164
3.8 内裁剪和外裁剪 167
3.9 凸多边形的判定和内法线确定 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 内法矢量和三维凸集合的确定 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 凹裁剪区域—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 函数插值 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 优先级排序表算法 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 区间扫描线算法 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 优先级排序 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 映射函数 402
5.12.2 两步纹理映射 405
5.12.3 环境映射 407
5.12.4 凹凸纹理 409
5.12.5 过程纹理 411
5.12.6 纹理反走样 413
5.12.7 Mipmapping 417
5.12.8 区域求和表 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 从光源出发的光线跟踪 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 镜面环境的辐射度 457
5.17.14 绘制方程 458
5.18 光线跟踪和辐射度的结合 458
5.19 颜色 462
5.19.1 色度 462
5.19.2 颜色的三刺激理论 463
5.19.3 原色系统 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 颜色系统之间的相互转化 473
5.19.10 NTSC颜色系统 476
5.19.11 颜色立方体 477
5.19.12 CMYK颜色系统 477
5.19.13 Ostwald颜色系统 478
5.19.14 HSV颜色系统 478
5.19.15 HLS颜色系统 481
5.19.16 Munsell颜色系统 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 颜色重现 497
5.21.1 平版打印 497
5.21.2 分色 498
5.21.3 色调重现 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 粒子系统 503
附录A 习题 504
参考文献 510
索引 536
