计算机图形学的算法基础（原书第2版） (2008 年度畅销榜NO.1143 )

本书从图形学最基础的光栅扫描、区域填充、画直线和圆弧等算法讲起，详细介绍了线裁剪和面裁剪、凸区域裁剪和凹区域裁剪的异同，景物空间消隐算法和图像空间消隐算法的差别，具体讲述了二叉空间剖分(BSP)、八叉树等图形学中常用的数据结构。新版本增加了图形用户界面、椭圆、图像压缩和线条反走样算法等，还增加了Liang-Barsky裁剪算法和Nicholl-Lee-Nicholl裁剪算法。新版本大大扩充了可见面光线跟踪算法。在绘制这一章中新增了基于物理的光照明模型，透明效果，阴影生成，纹理映射，以及锥光束、平面光束、笔形光束和随机光线跟踪算法；详细讨论了光辐射度基础，统一颜色空间，彩色图象量化和印刷介质上的颜色重现等新内容。本书列举了90个例子，具体描述了各类算法的执行细节。这对初学者体会算法的基本原理，比较各类算法执行时的细微差别大有禅益。具备大学数学基础和高级程序设计语言知识的人均可自学本书。\r\n本书适合专业程序员、工程师及科研人员使用。非常适用于作为为高年级本科生和一年级研究生开设的重点讲授绘制技术的计算机图形学课程的教科书。\r\n\r\n
\r\n

\r\n第1版序\r\n第1章 计算机图形学导论 1\r\n1.1 计算机图形学概述 1\r\n1.1.1 图形的表示方法 1\r\n1.1.2 表示图形的数据准备 2\r\n1.1.3 图形的显示 2\r\n1.2 光栅刷新图形显示器 4\r\n1.3 阴极射线管的基础知识 9\r\n1.4 视频知识基础 11\r\n1.4.1 美国标准视频制式 11\r\n1.4.2 高清晰度电视 12\r\n1.5 平板显示器 13\r\n1.5.1 平板式CRT 13\r\n1.5.2 等离子显示器 13\r\n1.5.3 荧光显示器 15\r\n1.5.4 液晶显示器 16\r\n1.6 硬拷贝输出设备 18\r\n1.6.1 静电绘图仪 18\r\n1.6.2 喷墨绘图仪 19\r\n1.6.3 热敏绘图仪 22\r\n1.6.4 染料升华打印机 22\r\n1.6.5 笔墨绘图仪 23\r\n1.6.6 激光打印机 25\r\n1.6.7 彩色胶片照相机 27\r\n1.7 逻辑交互设备 28\r\n1.8 物理交互设备 28\r\n1.9 数据生成设备 34\r\n1.10 图形用户界面 37\r\n第2章 光栅扫描图形学 46\r\n2.1 直线生成算法 46\r\n2.2 数字微分分析法 47\r\n2.3 Bresenham算法 50\r\n2.3.1 整数Bresenham算法 53\r\n2.3.2 通用Bresenham算法 54\r\n2.3.3 快速直线光栅化算法 56\r\n2.4 圆的生成—Bresenham算法 57\r\n2.5 椭圆的生成 64\r\n2.6 一般函数的光栅化 69\r\n2.7 扫描转换—显示的生成 71\r\n2.7.1 实时扫描转换 71\r\n2.7.2 使用指针的简单活化边表 72\r\n2.7.3 排序活化边表 72\r\n2.7.4 使用链表的活化边表 74\r\n2.7.5 修改链表 74\r\n2.8 图像压缩 77\r\n2.8.1 行程编码 77\r\n2.8.2 区域图像压缩 79\r\n2.9 显示直线. 字符和多边形 82\r\n2.9.1 线段显示 82\r\n2.9.2 字符显示 84\r\n2.9.3 实区域扫描转换 84\r\n2.10 多边形填充 85\r\n2.11 简单的奇偶扫描转换算法 88\r\n2.12 有序边表多边形扫描转换 90\r\n2.12.1 简单的有序边表算法 90\r\n2.12.2 更有效的有序边表算法 92\r\n2.13 边填充算法 95\r\n2.14 边标志算法 97\r\n2.15 种子填充算法 99\r\n2.15.1 简单的种子填充算法 102\r\n2.15.2 扫描线种子填充算法 102\r\n2.16 图形反走样基础 106\r\n2.16.1 超采样 107\r\n2.16.2 直线 107\r\n2.16.3 多边形内部 113\r\n2.16.4 简单区域反走样 114\r\n2.16.5 卷积积分与反走样算法 117\r\n2.16.6 滤波函数 119\r\n2.17 半色调技术 120\r\n2.17.1 模版化 121\r\n2.17.2 阈值和误差分布 124\r\n2.17.3 有序抖动 128\r\n第3章 裁剪 131\r\n3.1 二维裁剪 131\r\n3.1.1 简单可见性判别算法 131\r\n3.1.2 端点编码 133\r\n3.2 Cohen-Sutherland线段细分裁剪算法 136\r\n3.3 中点分割算法 140\r\n3.4 凸区域的二维参数化线段裁剪 144\r\n3.5 Cyrus-Beck算法 148\r\n3.5.1 部分可见线段 150\r\n3.5.2 完全可见线段 151\r\n3.5.3 完全不可见线段 151\r\n3.5.4 Cyrus-Beck算法的形式化描述 153\r\n3.5.5 非规则窗口 156\r\n3.6 Liang-Barsky二维裁剪 157\r\n3.7 Nicholl-Lee-Nicholl二维裁剪 164\r\n3.8 内裁剪和外裁剪 167\r\n3.9 凸多边形的判定和内法线确定 168\r\n3.10 凹多边形分割 172\r\n3.11 三维裁剪 172\r\n3.12 三维中点分割算法 175\r\n3.13 三维Cyrus-Beck算法 177\r\n3.14 Liang-Barsky三维裁剪 181\r\n3.15 齐次坐标裁剪 185\r\n3.15.1 Cyrus-Beck算法 185\r\n3.15.2 Liang-Barsky算法 186\r\n3.16 内法矢量和三维凸集合的确定 189\r\n3.17 凹体分割 190\r\n3.18 多边形裁剪 192\r\n3.19 逐次多边形裁剪—Sutherland-\r\nHodgman算法 193\r\n3.19.1 确定一个点的可见性 194\r\n3.19.2 线段求交 196\r\n3.19.3 算法 197\r\n3.20 Liang-Barsky多边形裁剪 202\r\n3.20.1 进点和出点 203\r\n3.20.2 折点 203\r\n3.20.3 算法设计 205\r\n3.20.4 水平边和垂直边 207\r\n3.20.5 算法 208\r\n3.21 凹裁剪区域—Weiler-Atherton算法 211\r\n3.22 字符裁剪 218\r\n第4章 可见面 220\r\n4.1 引言 220\r\n4.2 浮动水平线算法 221\r\n4.2.1 上浮水平线 221\r\n4.2.2 下浮水平线 222\r\n4.2.3 函数插值 223\r\n4.2.4 走样 226\r\n4.2.5 算法 227\r\n4.2.6 交叉影线 233\r\n4.3 Roberts算法 235\r\n4.3.1 体矩阵 235\r\n4.3.2 平面方程 237\r\n4.3.3 取景变换和体矩阵 240\r\n4.3.4 自隐藏面 241\r\n4.3.5 被其他物体遮挡的线 244\r\n4.3.6 贯穿体 252\r\n4.3.7 完全可见线段 252\r\n4.3.8 算法 255\r\n4.4 Warnock算法 263\r\n4.4.1 四叉树结构 265\r\n4.4.2 分割准则 265\r\n4.4.3 多边形与窗口的关系 267\r\n4.4.4 多边形与窗口关系的分层次辨别 272\r\n4.4.5 寻找包围多边形 273\r\n4.4.6 基本算法 275\r\n4.5 Appel算法 280\r\n4.6 附着光晕的线消隐算法 282\r\n4.7 Weiler-Atherton算法 284\r\n4.8 曲面分割算法 287\r\n4.9 Z缓冲器算法 288\r\n4.9.1 采用增量法计算深度值 290\r\n4.9.2 层次Z缓冲器算法 295\r\n4.10 A缓冲器算法 296\r\n4.11 优先级排序表算法 298\r\n4.12 Newell-Newell-Sancha算法 299\r\n4.13 二叉空间剖分算法 302\r\n4.13.1 Schumacker算法 303\r\n4.13.2 二叉空间剖分树 304\r\n4.13.3 构造BSP树 304\r\n4.13.4 BSP树遍历 306\r\n4.13.5 背面剔除 308\r\n4.13.6 小结 308\r\n4.14 扫描线算法 308\r\n4.15 扫描线Z缓冲器算法 309\r\n4.16 区间扫描线算法 312\r\n4.16.1 不可见相关性 319\r\n4.16.2 景物空间扫描线算法 320\r\n4.17 曲面扫描线算法 320\r\n4.18 八叉树 323\r\n4.18.1 八叉树显示 325\r\n4.18.2 线性八叉树 327\r\n4.18.3 八叉树的操作 327\r\n4.18.4 布尔运算 328\r\n4.18.5 搜索相邻单元 328\r\n4.19 移动立方体算法 328\r\n4.20 可见面光线跟踪算法 332\r\n4.20.1 包围体 334\r\n4.20.2 丛 337\r\n4.20.3 建立丛的树结构 338\r\n4.20.4 优先级排序 338\r\n4.20.5 空间剖分 339\r\n4.20.6 均匀空间剖分 340\r\n4.20.7 非均匀空间剖分 342\r\n4.20.8 光线－物体求交 344\r\n4.20.9 不透明可见面算法 347\r\n4.21 小结 350\r\n第5章 绘制 351\r\n5.1 引言 351\r\n5.2 光照模型 352\r\n5.3 一个简单的光照模型 353\r\n5.3.1 镜面反射 354\r\n5.3.2 中值矢量 357\r\n5.4 确定表面法向 359\r\n5.5 确定反射光线矢量 360\r\n5.6 Gouraud明暗处理 363\r\n5.7 Phong明暗处理 366\r\n5.8 具有特殊效果的简单光照模型 370\r\n5.9 基于物理的光照模型 372\r\n5.9.1 能量和辐射强度 372\r\n5.9.2 基于物理的光照模型 373\r\n5.9.3 Torrance-Sparrow关于粗糙表面\r\n的模型 374\r\n5.9.4 与波长相关的菲涅耳项 377\r\n5.9.5 颜色转变 378\r\n5.9.6 光源的物理特性 379\r\n5.10 透明 380\r\n5.10.1 透明材料的折射效果 381\r\n5.10.2 简单的透明模型 382\r\n5.10.3 Z缓冲器算法中的透明处理 383\r\n5.10.4 伪透明 384\r\n5.11 阴影 385\r\n5.11.1 扫描转换阴影算法 388\r\n5.11.2 多步可见面阴影算法 389\r\n5.11.3 阴影体算法 391\r\n5.11.4 半影 394\r\n5.11.5 光线跟踪阴影算法 396\r\n5.12 纹理 397\r\n5.12.1 映射函数 402\r\n5.12.2 两步纹理映射 405\r\n5.12.3 环境映射 407\r\n5.12.4 凹凸纹理 409\r\n5.12.5 过程纹理 411\r\n5.12.6 纹理反走样 413\r\n5.12.7 Mipmapping 417\r\n5.12.8 区域求和表 417\r\n5.13 随机模型 418\r\n5.14 采用光线跟踪的整体光照模型 420\r\n5.15 采用光线跟踪的更完整的\r\n整体光照模型 431\r\n5.16 光线跟踪技术的最新进展 433\r\n5.16.1 圆锥跟踪 433\r\n5.16.2 光束跟踪 434\r\n5.16.3 一般光束跟踪 434\r\n5.16.4 随机采样 435\r\n5.16.5 从光源出发的光线跟踪 437\r\n5.17 辐射度 437\r\n5.17.1 封闭性 439\r\n5.17.2 形状因子 440\r\n5.17.3 半立方体 442\r\n5.17.4 绘制 447\r\n5.17.5 子结构 447\r\n5.17.6 逐步求精 448\r\n5.17.7 排序 449\r\n5.17.8 泛光贡献 449\r\n5.17.9 自适应剖分 450\r\n5.17.10 半立方体方法的不精确性 451\r\n5.17.11 半立方体方法外的其他方法 454\r\n5.17.12 层次辐射度和聚集 456\r\n5.17.13 镜面环境的辐射度 457\r\n5.17.14 绘制方程 458\r\n5.18 光线跟踪和辐射度的结合 458\r\n5.19 颜色 462\r\n5.19.1 色度 462\r\n5.19.2 颜色的三刺激理论 463\r\n5.19.3 原色系统 464\r\n5.19.4 颜色匹配实验 464\r\n5.19.5 色度图 466\r\n5.19.6 1931年CIE色度图 468\r\n5.19.7 均匀颜色空间 471\r\n5.19.8 颜色域的局限 472\r\n5.19.9 颜色系统之间的相互转化 473\r\n5.19.10 NTSC颜色系统 476\r\n5.19.11 颜色立方体 477\r\n5.19.12 CMYK颜色系统 477\r\n5.19.13 Ostwald颜色系统 478\r\n5.19.14 HSV颜色系统 478\r\n5.19.15 HLS颜色系统 481\r\n5.19.16 Munsell颜色系统 483\r\n5.19.17 Panetoneㄏ低?484\r\n5.19.18 Gamma校正 484\r\n5.20 彩色图像的量化 485\r\n5.20.1 位截断法 486\r\n5.20.2 流行色法 487\r\n5.20.3 中分截断法 489\r\n5.20.4 八叉树量化 491\r\n5.20.5 顺序标量量化 494\r\n5.20.6 其他量化算法 496\r\n5.21 颜色重现 497\r\n5.21.1 平版打印 497\r\n5.21.2 分色 498\r\n5.21.3 色调重现 498\r\n5.21.4 灰度平衡 498\r\n5.21.5 黑色分离 498\r\n5.21.6 量化效果 498\r\n5.21.7 校准 499\r\n5.21.8 色域映射 499\r\n5.22 特殊绘制效果 501\r\n5.22.1 双色套印 501\r\n5.22.2 绘制自然物体 503\r\n5.22.3 粒子系统 503\r\n附录A 习题 504\r\n参考文献 510\r\n索引 536 \r\n
\r\n

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月

无封面