武汉大学计算机图形学复习整理

1、图形系统的组成

图形系统可定义为是计算机硬件、图形输入输出设备、计算机系统软件和图形软件的集合。

一个计算机图形系统起码应具有计算、存储、对话、输入、输出等5个功能。

2、颜色查找表 P16

为避免帧缓存的增加，采用颜色查找表来提高灰度级别。帧缓存中数据为颜色查找的索引，颜色查找表必须有2N项，每一项具有W位字宽。当W大于N时，可有2W灰度等级，但每次只有2N个不同灰度等级可用。若要使用2N种以外的灰度等级，需改变颜色查找表中的内容。

1、标准化的作用（1）方便不同系统间的数据交换；（2）方便程序移植；（3）硬件隔离，实现图形系统的硬件无关性。

2、图形标准的组成、分类

（1） 面向图形设备标准：计算机图形元文件(CGM) ，(CRT,绘图仪,打印机，…)；计算机图形接口(CGI) ，（设备驱动程序）

（2）面向图形软件标准：官方标准（标准组织制定的标准）：GKS(Graphical Kernel System) ，PHIGS(Programmer’s Hierarchical Interactive Graphics System) ，其它数据标准

工业标准（事实上的标准）：SGI 等公司的OpenGL ，微软公司的DirectX ，Adobe 公司的PostScript 等等

（3）文件格式标准：基本图形转换规范（IGES ）；产品数据转换规范（STEP ）

1、用户接口的常用形式 P130

（1）子程序库：这种形式的基本思想是选择一种合适的高级程序设计语言（如C,C++，Fortran等）作为主语言，用此主语言扩展一系列的过程或函数调用，用以实现有关的图形设计和处理。

GKS ，OpenGL 等

优点： 使用方便、便于扩充、便于将用户自己编写的源程序或目标代码加入相应的子程序中，并且可以充分利用高级语言本身具有的功能。

不足：但需要用户熟悉某种通用程序设计语言，修改麻烦，不形象直观。

（2）专用语言：一般为解释性的语言。 PostScript ，VRML 等

（3）交互命令： 图形界面或命令行方式，进行人机交互。 常用操作：增、删、改操作（常用三表结构实现）

2、输入控制

（1）请求方式 (程序初始化设备，即输入设备的初始化是在应用程序中设置的。)

缺点：效率低，不能同时工作。

（2）取样方式 (程序和设备同时工作)

优点：该模式不像请求模式那样要求用户有一明显的动作，它对连续的信息流输入比较方便，也可同时处理多个输入设备的输入信息。

缺点：当处理某一种输入耗费的时间较长时，可能会失掉某些输入信息。

（3）事件方式 (设备初始化程序)：输入设备和程序运行。

2、区域填充（边界的处理应注意的问题，活化边表算法，种子点，连通区域的概念及其边界条件）

(1)边界的处理应注意的问题

存在问题：

1)多边形顶点与扫描线相交，交点数量计算不当会产生交点配对错误。

解决方式：下闭上开；

2)边界像素是否填充，处理不当造成填充不足或填充范围扩大化。

解决方式：左闭右开

(2)活化边表算法

扫描线算法：

对于一条扫描线填充过程可以分为四个步骤：（1）求交（2）排序（3）配对（4）填色

假定当前扫描线与多边形某一条边的交点的x坐标为x，则下一条扫描线与该边的交点不要重计算，只要加一个增量△x。

设该边的直线方程为：

ax+by+c=0

若y ＝yi ，x ＝xi ；则当y = yi+1 时（即到下一条扫描线时）：

xi11(byi1ci)xib;aa

其中

xba 为常数

优点：

充分利用了多边形各边的连续性和扫描线的连贯性，减少了求交计算，提高了效率；

缺点：

数据结构复杂，只适宜纯软件方式实现，很难用硬件实现。

(3)种子点,连通区域的概念及其边界条件 P185

种子点算法原理：假设在多边形区域内部有一已知像素，由此出发找到区域内的所以元素。

4连通的区域: 取区域内任意两点，在该区域内若从其中一点出发通过上、下、左、右四种运动可到达另一点。

8连通区域: 取区域内任意两点，若从其中任一点出发，在该区域内通过沿水平方向、垂直方向和对角线方向的八种运动可到达另一点。

简单的种子点填充算法：

给定区域G一种子点（x, y）首先判断该点是否是区域内的一点，如果是，则将该点填充为新的颜色，然后将该点周围的四个点（四连通）或八个点（八连通）作为新的种子点进行同样的处理，通过这种扩散完成对整个区域的填充 。

存在问题：多个像素重复入栈，带来了效率和存储空间的问题

扫描线种子填充算法：

① 将算法设置的堆栈置为空。将给定的种子点（x, y）压入堆栈；

② 如果堆栈为空，算法结束；否则取栈顶元素（x, y）作为种子点；

③ 从种子点（x, y）开始，沿纵坐标为y的当前扫描线向左右两个方向逐个像素用新的颜色值进行填充，直到边界为止。设区间两边界的横坐标分别为xleft 和xright；

④ 在与当前扫描线相邻的上下两条扫描线上，以区间[xleft,xright]为搜索范围，求出需要填充的各小区间，把各小区间中最右边的点并作为种子点压入堆栈，转到②。

3、裁减（编码裁剪、中点分割算法、多边形的逐边裁剪算法及注意的问题）P199

（1）编码裁剪：Cohen-Sutherland裁剪

基本思想：

对于每条线段P1P2分为三种情况处理分为三种情况处理:

若P1P2完全在窗口内，则显示该线段；

若P1P2明显在窗口外，则丢弃该线段；

若线段不满足① 或②的条件，则在窗口（或其延长线）与线段的交点处把线段分为两段。其中一 段完全在窗口外，可弃之；然后对另一段重复上述处理。

为快速判断，采用如下编码方法：每个区域赋予4 位编码

算法：

① 对线段的两个端点P1、P2进行按其所处的位置进行编码，分别记为code1、code2；

② 如果code1=0且code2=0,说明线段在窗口内，全部可见；否则到③；

③ 若code1&code2≠0，则说明线段在某一窗口边的延长线的外侧，全部不可见；否则到④；

④在线段与窗口延长线的交点处把线段分为两段，并对两段分别编码。其中交点看作是两个点，一个在与之相交的窗口延长线外侧，一个在内侧。两段线段分别进行①～④的判断过程，则其中一段必然符合③的条件，可弃之；另一段重复①～④的处理，直到剩余部分的线段完全可见或完全不可见。

（2）中点分割算法

基本思想：

与前一种Cohen-Sutherland算法一样首先对线段端点进行编码，并把线段与窗口的关系分为三种情况:

① 完全可见；

② 完全不可见；

③ 部分可见。

对前两种情况，进行一样的处理。

对于第三种情况，用中点分割的方法求出线段与窗口的交点（最远可见点）。

最远可见点

最远可见点之间的连线即为所求的线段

从P0出发找最远可见点的方法

① 对P0P1端点进行编码判断，如果完全不可见，则无最远可见点，算法结束；否则继续；

② 求出P0P1的中点Pm（可由加法和移位运算实现） ；

③ 若Pm在窗口内（Pm编码为0000），则在PmP1中计算P0的最远可见点 ；如果Pm在窗口外，则P0Pm、 PmP1必然有一段完全在窗口外侧，丢弃之，然后在另一段中重复算法，

计算P0的最远可见点；

④ 重复上述算法，直到算法在③停止（说明P0无最远可见点），或运算到分辨率精度（即P0PmP1为相邻的三个像素），则此时Pm即为P0的最远可见点。

4、反走样概念、方法

反走样概念：用离散量(像素)表示连续的量(图形)而引起的失真，叫走样（或混淆），走样的现象有：阶梯状边界；图形细节失真；狭小图形遗失：动画序列中时隐时现，产生闪烁。而用于减少或消除这种效果的的技术称为反走样。

反走样方法：

① 提高分辨率

优缺点：增加分辨率虽然简单，但是不经济的方法；而且它也只能减轻而不能消除锯齿问题。

② 简单区域采样（盒式滤波）

每个像素是一个具有一定面积的小区域，将直线段看作具有一定宽度的狭长矩形。当直线段与像素有交时，求出两者相交区域的面积，然后根据相交区域面积的大小确定该像素的亮度值。

缺点：像素的亮度与相交区域的面积成正比，而与相交区域落在像素内的位置无关，这仍然会导致锯齿效应；直线条上沿理想直线方向的相邻两个像素有时会有较大的灰度差。

③ 加权区域采样（圆锥滤波）

1) 使相交区域对像素亮度的贡献依赖于该区域与像素中心的距离；

5、线宽处理的方法

（1）线刷子

实现简单，但接头出容易出现缺口，粗细不均匀，水平或垂直时为真实宽度，斜率为±1时最细（真实宽度的 12 )，只能实现奇数像素宽度。

（2）方刷子：实现简单，粗细不均匀，水平或垂直时为真实宽度，斜率为±1时最粗（真实宽度的 2 倍 )，只能实现奇数像素宽度；

可用类似于活化边表填充算法实现。

（3）区域填充方法

优点：生成的图形质量高

缺点 ：计算量大

1、曲线相关的概念

（1）插值：给定一组有序的数据点Pi ，i=0, 1, …, n ，构造一条曲线顺序通过这些数据点，称为对这些数据点进行插值，所构造的曲线称为插值曲线。

（2）逼近：型值点（插值点）比较多时，很难用低次函数进行内插，因此可选用一个低次函数尽量的逼近这些点。

（3）拟合：构造一条曲线使之在某种意义下最接近给定的数据点( 但未必通过这些点) ，所构造的曲线为拟合曲线。 无完整的数学定义，可用插值和逼近实现。

（4）连续性：

① 参数连续性

如果曲线 PP(t) 在 tt0 处满足左右n 阶导矢均存在且相等，即

则称曲线p(t) 在

tt0 处是n 阶参数连续的，或称Cn 连续

② 几何连续性

零阶几何连续（G0）：如果曲线

P(t0)P(t0)P(t) 位置连续，即

，则称曲线在t=t0处零阶几何连续。

一阶几何连续（G1）:如果曲线 即存在常数>0，使 阶几何连续。

P(t) 在点t=t0处满足G0连续，且切矢量方向相同，

,则称曲线在t=t0处一

P(t0)P(t0)2、Bezier 曲线

定义：给定空间n+1个点的位置矢量Pi（i=0，1，2，…，n），则n次（n+1阶）Bézier曲线可定义为：

nP(t)PiBi,n(t),i0t[0,1]

其中，Pi构成该Bézier曲线的特征多边形，Bi,n(t)是n次Bernstein基函数：

n!ti(1t)nii!(ni)! (i0,1,,n)

iiBi,n(t)Cnt(1t)ni（1）（Bernstein）基函数性质：P20_21

正性、端点性质、权性、对称性、导函数、递推性

（2）（Bézier）曲线性质

端点性质（位置矢量、切矢量）、对称性、凸包性、几何不变性、变差缩减性、仿射不变性。

（3）Bézier曲线拼接注意事项：P306--307

P(t)和Q（t）:两条Bézier曲线及其特征多边形，并且P（t）的终点Pn和Q(t)的始点Q0重合，即它们已达C0连续。

（1）要使它们达到G1连续的充要条件是，Pn-1,Pn=Qn,Q1三点共线；即b1=а an(а>0).当а=1时，C1连续。

（2）要使它们达到C2连续的充要条件是要在C1连续的前提下再增加两个条件：

① 密切平面重合，副法线矢量同向；

② 曲率相等。

1、概念：

（1）齐次坐标 P361

优越性：（1）提供了用矩阵运算进行图形变换的有效方法；（2）表达的一致性，便于硬件运算；（3） 简化了复合图形变换的形式，提高了效率；（4）可以表达无穷远点。

（2）复合变换：P368 复合变换是指图形作一次以上的几何变换，变换结果是每次变换矩阵相乘。

（3）灭点、主灭点、一（二、三）点透视 P380~384

透视投影的视线（投影线）是从视点（观察点）出发，视线是不平行的。不平行于投影平面的平行线投影后汇聚的一点称为灭点，在坐标轴上的灭点叫做主灭点。按照主灭点的个数，个数为一的为一点透视，个数为二的为二点透视，和个数为三的为三点透视。

（4）投影空间 P384

相对于二维的窗口概念，三维的投影窗口称为投影空间，一般在观察坐标系下定义投影窗口。透视投影空间为四棱台体，平行投影空间为四棱柱体。

1、凸多面体自隐藏面的消隐

概念：视点与第i个面上一点连线方向为（li,mi,ni）,那么，当点积（ai,bi,ci).（li,mi,ni）<0时，平面i为自隐藏面。任意两个自隐藏面的交线称为自隐藏线。例如：指向面内部的法向量（a,b,c）,视点为（m,n,k）,面上一点为（x,y,z）;则l=（x,y,z）-（m,n,k）,,若（a,b,c）.l<0，面消隐。

2、光照模型、平滑明暗处理（ Gouraud 、 Phong模型 ）

光照模型（明暗模型）：用数学公式来近似计算物体表面按什么样的规律，什么样的比例来反射或透射光，该公式称为明暗模型。

反射光分为三部分：泛光（环境光）、漫反射光和镜面反射光。

Gouraud模型 P507~508

算法思想

将曲面表面某一点的光亮度做近似表示，近似值为该曲面的各多边形顶点光亮度的双线性插值。

顶点光亮度采用：环境光＋漫反射

顶点的法向量为周围面的法向量的平均值。

多边形各顶点光亮度计算

法向量计算

取和顶点关联的各多边形面片的平均法向量作为该顶点的法向量

取多边形各顶点处原始曲面的真正法向量

将法向量代入光照明模型进行光亮度计算。

优点：

采用Gouraud明暗处理不但可以克服有多边形近似表示的曲面的光亮度不连续现象，而且计算量也很小。

为了进一步提高计算效率，线性插值可使用增量法进行计算，其计算量仅涉及一次加法计算。

缺点：

不能正确地模拟高光，这是因为采用光亮度插值后将使多边形内的高光丢失；

动态物体表面明暗度不规则变化；

光源与视线方向之间的夹角不能太大，否则不能正确表达实际情况。

克服这些缺点的一种方法是采用Phong明暗处理

Phong模型:

基本步骤：先计算多边形各顶点出的法向量，再用双线性插值的方法求得每个像素处的法向量，最后对每个像素所得法向量按Phong光照模型，求出明暗度值。环境光+漫反射+镜面反射。

1) 它的基本思想是对多边形顶点处（平均）法向量做双线性插值，以增加一定的计算量为代价克服了Gouraud明暗处理的缺点。

2) Phong明暗处理能正确地模拟高光。

3) 也可采用扫描线双线性插值方法。

3、颜色模型（基色、CIE色度图）

（1）影响颜色的三个要素是：（1）光（2）物体（3）观察者

（2）颜色模型：所谓颜色模型指的是某个三维颜色空间中的一个可见光子集，它包含某个颜色域的所有颜色。采用颜色模型的目的是在某个颜色域中方便的指定颜色。

（3）基色：在颜色模型中，用来生成其它颜色的两种或三种颜色称为基色（primitive color），缺少其中一种基色则不能生成第三种颜色。

（4）国际照明委员会（简称CIE），通常把CIE规定的一组基色称为XYZ颜色模型

任何一种颜色C可以表示成：

CxXyYzZxyz1XxXYZYyXYZZzXYZ

进行规范化后，色度空间中的锥体（在第一卦限中）与X+Y+Z＝1的平面相交，交平面图形投影到XOY平面，得到CIE色度图。参数x和y称为色度值，因为它们仅依赖于色彩和纯度。

其中,z=1-x-y。这样我们就可以用色度坐标 (x,y)在二维图形中表示所有颜色。

用途：（1）显示基色组的颜色范围，定义颜色域； （2）计算补色；（3）计算某种颜色的主波长与色纯度。