计算机图形学复习整理qfj_2011.1.16一、图形设备、系统和应用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 ＝y i ，x ＝x i ；则当y = y i+1 时（即到下一条扫描线时）：;)(111ab xc y b a x i i i i -=-⋅-=++ 其中 abx -=∆ 为常数优点：充分利用了多边形各边的连续性和扫描线的连贯性，减少了求交计算，提高了效率； 缺点：数据结构复杂，只适宜纯软件方式实现，很难用硬件实现。

(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的中点P m（可由加法和移位运算实现）；③若P m在窗口内（P m编码为0000），则在P m P1中计算P0的最远可见点；如果P m在窗口外，则P0P m、P m P1必然有一段完全在窗口外侧，丢弃之，然后在另一段中重复算法，计算P0的最远可见点；④重复上述算法，直到算法在③停止（说明P0无最远可见点），或运算到分辨率精度（即P0P m P1为相邻的三个像素），则此时P m即为P0的最远可见点。

4、反走样概念、方法反走样概念：用离散量(像素)表示连续的量(图形)而引起的失真，叫走样（或混淆），走样的现象有：阶梯状边界；图形细节失真；狭小图形遗失：动画序列中时隐时现，产生闪烁。

而用于减少或消除这种效果的的技术称为反走样。

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

②简单区域采样（盒式滤波）每个像素是一个具有一定面积的小区域，将直线段看作具有一定宽度的狭长矩形。

当直线段与像素有交时，求出两者相交区域的面积，然后根据相交区域面积的大小确定该像素的亮度值。

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

③加权区域采样（圆锥滤波）1) 使相交区域对像素亮度的贡献依赖于该区域与像素中心的距离；5、线宽处理的方法（1）线刷子实现简单，但接头出容易出现缺口，粗细不均匀，水平或垂直时为真实宽度，斜率为±1时最细（真实宽度的 21)，只能实现奇数像素宽度。

（2）方刷子：实现简单，粗细不均匀，水平或垂直时为真实宽度，斜率为±1时最粗（真实宽度的 2倍 )，只能实现奇数像素宽度； 可用类似于活化边表填充算法实现。

（3）区域填充方法 优点：生成的图形质量高 缺点 ：计算量大1、曲线相关的概念（1）插值：给定一组有序的数据点P i ，i=0, 1, …, n ，构造一条曲线顺序通过这些数据点，称为对这些数据点进行插值，所构造的曲线称为插值曲线。

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

（3）拟合：构造一条曲线使之在某种意义下最接近给定的数据点( 但未必通过这些点) ，所构造的曲线为拟合曲线。

无完整的数学定义，可用插值和逼近实现。

（4）连续性：① 参数连续性 如果曲线()t =P P 在t t = 处满足左右n 阶导矢均存在且相等，即则称曲线)(t p 在 0t t = 处是n 阶参数连续的，或称C n连续② 几何连续性零阶几何连续（G 0）：如果曲线()t P 位置连续，即00()()t t -+=P P ，则称曲线在t=t 0处零阶几何连续。

一阶几何连续（G 1）:如果曲线()t P 在点t=t 0处满足G 0连续，且切矢量方向相同，即存在常数α>0，使 00()()t t α-+''=P P ,则称曲线在t=t 0处一阶几何连续。

2、 Bezier 曲线定义：给定空间n+1个点的位置矢量P i （i=0，1，2，…，n ），则n 次（n+1阶）Bézier 曲线可定义为：]1,0[),()(,0∈=∑=t t B P t P n i i ni其中，P i 构成该Bézier 曲线的特征多边形，B i,n (t)是n 次Bernstein 基函数：),,1,0( )1()!(!!)1()(,n i t t i n i n t t C t B in i i n i i n n i ⋅⋅⋅=-⋅-=-=--（1）（Bernstein ）基函数性质：P20_21正性、端点性质、权性、对称性、导函数、递推性（2）（Bézier）曲线性质端点性质（位置矢量、切矢量）、对称性、凸包性、几何不变性、变差缩减性、仿射不变性。