译著《计算机图形学的算法基础》

译 者 前 言

1985年春，美国佛罗里达大学教授、IEEE CG&A学术期刊时任主编John Staudhammer先生应邀来浙江大学讲学，向我们推荐了 David Rogers编写的图形学新著《Procedural Elements of Computer Graphics》。该书取材新颖，内容全面，便于自学，立即引起了大家的浓厚兴趣。当时国内计算机图形学研究正处于起步阶段，有关计算机图形学的中文教材和参考书甚少。因此我们立即着手组织翻译。中译本取名为《计算机图形学的算法基础》，由科学出版社出版。首批5000册不到3个月即销售一空，许多没买到该书的人只好整本地复印。该书的出版，对我国计算机图形学的发展曾起了很好的作用。不少人以这本书为向导，走上了从事图形学研究的道路。

时隔14年，机械工业出版社购买了Rogers教授新版《Procedural Elements of Computer Graphics》翻译版权，并委托我们翻译。我们很高兴接受了这一任务。与第一版相比，新版的篇幅几乎增加了一倍。从80年代到90年代，正是计算机图形学蓬勃发展的黄金时期，光线跟踪和光能辐射度方法逐渐发展成为真实感图形绘制的两大主流技术。新版收集整理了这一期间所涌现出来的大量优秀的算法，包括各种快速光线跟踪算法，带反走样的纹理映射技术以及逐步求精辐射度方法等。此外，新版继续保持了原书概念清晰，举例详细，便于自学的风格。本书从图形学最基础的光栅扫描、区域填充、画直线、圆弧算法开始讲起，详细介绍了线裁剪和面裁剪、凸区域裁剪和凹区域裁剪的异同，景物空间消隐算法和图象空间消隐算法的差别，具体讲述了空间二叉树（BSP）、八叉树等图形学中常用的数据结构。特别需要指出的是，图形学是一门只有通过实践才能掌握的学科，本书列举了90个例子，具体描述了各类算法的执行细节。这对初学者体会算法的基本原理，比较各类算法执行时的细微差别大有裨益。具备大专数学基础和高级语言编程能力的人均可自学本书。

本书的作者David Rogers是一位资深的图形学专家。他长期任职于美国海军科学院，从事计算机图形学的教学与科研。曾出版学术著作4部，主编多部。他编著的《Procedural Elements of Computer Graphics》（第一版），曾被评为美国Top-Five图形学教科书，并先后被翻译成六种语言文字出版。

翻译如此一本学术名著实在是一件困难的事。尽管我们有翻译本书第一版的经验，译稿工作量仍然巨大。本书的前言、第一、二章仍由石教英负责，第三、四、五章仍由彭群生负责。张明敏，赵友兵参与了本书第一、二章的翻译，刘新国、陈莉、冯结青分别参与了第三、四、五章的翻译，全书由石教英、彭群生仔细校对、修改定稿。在翻译过程中，我们也曾遇到一些国内尚未见到，尚无统一译法的名词，如Haloed Line，Pencil tracing，the popularity algorithm等，我们斟酌选用了最能表达其含义的译法，详见本书索引。这些译法是否恰当，仍有待读者认可。由于译者水平和学识均有限，译本中翻译不尽妥当之处在所难免，恳请读者批评指正。

译者

2000年8月

作者与内容简介

一、原作者介绍：

David F.Rogers ，计算机图形学专家兼航空工程师。包括计算机图形学的数学基础在内他一共撰写四部教材，同时他还参与了一些其它书籍的编撰。他的著作已经被翻译为六种语言。迄今他在计算机图形学和航空学领域已发表五十多篇论文和技术报告。

二、本书简介：

作者：David F.Rogers

这本经典的计算机图形学的第二版在很大程度上可以说是一个重写。该书对于学生、程序员和计算机图形学专业人员有特别的价值。新增加的部分主要包括图形用户界面、椭圆、图象压缩和线条反走样算法。裁剪算法除经典的Cohen-Sutherland、 中点二分、Cyrus-Beck、Sutherland-Hodgman算法外还增加了Liang-Barsky、Nicholl-Lee-Nicholl算法。可见面算法这一章在经典算法之外增加了Appel、晕线、A-buffer、二叉树划分(BSP)、八叉树消隐算法和marching cube算法。原来的可见面光线跟踪算法也有很大扩充。绘制一章现在的内容包括基于物理的光照明模型、透明材料、阴影和纹理以及锥光线跟踪、束光线跟踪、笔束光线跟踪和随机光线跟踪等。这个版本还详细介绍了辐射度的基本知识并增加了均匀颜色空间、gamma矫正、彩色图像的量化和印刷介质上的颜色再现等内容，不过它也保留了老版本的许多精雕细琢的例子并作了相应的补充。

目 录

第一章 计算机图形学导论

1-1计算机图形学概述

1-2光栅刷新图形显示器

1-3阴极射线管(CRT)基础知识

1-4视频知识基础

1-5 平板显示器

1-6硬拷贝输出设备

1-7逻辑交互设备

1-8物理交互设备

1-9数据生成设备

1-10 图形用户界面

第一章 光栅扫描图形学

2-1直线生成算法

2-2数字微分分析法

2-3 Bresenham算法

2-4 圆的生成——Bresenham 算法

2-5 椭圆的生成

2-6 一般函数的光栅化

2-7扫描转换——显示的生成

2-8 图像压缩

2-9显示直线、字符和多边形

2-10 多边形填充

2-11简单的奇偶扫描转换算法

2-12有序边表多边形扫描转换

2-13边填充算法

2-14 边标志算法

2-15 种子填充算法

2-16 图形反走样基础

第三章 裁剪

3-1 两维裁剪

一个简单的可见线算法

端点编码

3-2 Cohen-Suthealand 区域编码线裁剪算法

3-3 中点分割算法

3-4 凸边界区域的二维线裁剪算法

部分可见线段

3-5 Cyrus-Beck算法

部分可见线段

完全可见线段

完全不可见线段

Cyrus-Beck算法的形式化描述

非规则窗口

3-6 梁—Barsky二维裁

与Cyrus-Bedck算法的比例

3-7 Nicholl-Lee-Nicholl二维裁剪

3-8 内裁剪和外裁剪

3-9 凸多边形的判定和内法线确定

3-10 凹多边形分

3-11 三维裁剪

3-12 三维中点分割算法

3-13 三维Cyrus-Beck算法

3-14 梁—Barsky三维裁剪

3-15 齐次坐标裁剪

Cyrus-Bedk算法

梁—Barsky算法

3-16 内法矢量和三维凸集合的决定

3-17 凹体分割

3-18 多边形裁剪

3-19 逐次多边形裁剪—Sutherland-Hodgman算法

确定一个点的可见性

线段求交算法

3-20 梁—Barsky多边形裁剪

进点和出点

折点

算法设计

水平边和垂直边

算法

3-21 凹裁剪区域—Weiler-Htherton算法

特殊情形

3-22 字符裁剪

第四章 可见面

4-1 引言

4-2 浮动水平线算法

上浮水平线

下浮水平线

函数插值

走样

交叉影线

4-3 Roberts算法

体矩阵

平面方程

取景变换和体矩阵

自隐藏面

被其它物体遮挡的线

贯穿体

完全可见线段算法

4-4 Warnock算法

四叉树结构

分割准则

多边形与窗口的关系

多边形与窗口关系的分层次辨别

寻找包围多边形

基本算法

4-5 Appel算法

4-6 附着光晕的线的消隐算法

4-7 Weiler-Atherton算法

4-8 曲面分割算法

4-9 Z缓冲器算法

采用增量法计算深度值

层次Z缓冲器算法

4-10 A缓冲器算法

4-11 优先级排序表算法

4-12 Newell-Newell-Sancha算法测试

4-13 二叉空间剖分算法

Schumaker算法

二叉空间剖分树

构造BSP树

BSP树遍历

背面剔除

小结

4-14 扫描线算法

4-15 扫描线Z缓冲器算法

4-16 区间扫描线算法

不可见相关性

景物空间扫描线算法

4-17 曲面扫描线算法

4-18 八叉树

八叉树显示

线性八叉树

八叉树的操作

布尔运算

搜索相邻单元

4-19 移动立方体算法

二叉性面

4-20 可见面光线跟踪算法

包围体丛

建立丛的树结构

优先级排序

空间剖分

均匀空间分割

非均匀空间分割

光线一物体求交

不透明可见面算法

4-21 小结

第五章 绘制

5-1 引言

5-2 光照模型

5-3 一个简单的光照模型

镜面反射

角平分矢量

5-4 确定表面法向

5-5 确定表面反射矢量

5-6 Gouraud明暗处理

5-7 Phong明暗处理

快速Phong明暗处理

5-8 一个带特殊效果的简单光照模型

5-9 基于物理的光照模型

光能和光亮度

基于物理的光照模型

Torrance-Sparrow表面模型

波长相关性—菲湟耳项

色彩

光源的属性

5-10 透明

透明材料的折射效果

简单透明光照模型

Z缓冲器透明算法

伪透明

5-11 阴影

基于扫描转换的阴影算法

多步可见算法

阴影算法

影域体算法

半影

光线跟踪阴影算法

5-12 纹理

映射函数

两步法纹理映射

环境映照

凹凸纹理

过程纹理

纹理反走样

Mipmapping（图象金字塔）

区域求和表

5-13 随机模型

5-14 基于光线跟踪的整体光照模型

5-15 基于光线跟踪的更完整的整体光照模型

5-16 光线跟踪新技术

园锥跟踪

光束跟踪

中心轴光束跟踪（Pencil tracing）

随机采样

从光源出发的光线跟踪

5-17 光能辐射度方法

封闭环境

形状因子

半立方体

绘制

子结构

逐步求精

排序

泛光贡献

自适应分割

半立方体算法的误差

层次辐射度方法和分丛

镜面环境的辐射度方法

绘制方程

5-18 光线跟踪和辐射度方法的合成

扩展的二步法

5-19 颜色

色彩

颜色的三剌激理论

三原色系统

颜色匹配试验

色度图

1931 CIE色度图

均匀颜色空间

色域局限

颜色系统之间的转换

NTSC颜色系统

颜色立方体

CMYK颜色系统

Ostwald颜色系统

HSV颜色系统

HLS颜色系统

孟塞尔颜色系统

Pantone系统

Gemma校正