计算机图形学 复习资料

1、计算机图形学复习资料第一章1 图形学定义ISO的定义：计算机图形学是研究怎样利用计算机表示、生成、处理和显示图形的原理、算法、方法和技术的一门学科。通俗定义：计算机图形学以表达现实世界中的对象及景物为主要目标，其核心是解决如何用图形方式作为人和计算机之间传递信息的手段，即人机界面问题。计算机图形学的研究对象图形。图形是从客观世界物体中抽象出来的带有颜色及形状信息的图和形。图形的构成要素：几何要素：点、线、面、体等描述对象的轮廓、形状。非几何要素：描述对象的颜色、材质等。图形的表示方法：点阵法：枚举出图形中所有点(简称图像)。参数法：由图形的形状参数(简称图形)。2 图形与图像图像：狭义上又称为

2、点阵图或位图图像。图像是指整个显示平面以二维矩阵表示，矩阵的每一点称为一个像素，由像素点所取亮度或颜色值不同所构成的二维画面。特点：A文件所占的空间大。B位图放大到一定的倍数后会产生锯齿。C位图图像在表现色彩、色调方面的效果比矢量图更加优越。图形：狭义上又称为矢量图形或参数图形。按照数学方法定义的线条和曲线组成，含有几何属性。或者说更强调场景的几何表示，是由场景的几何模型和景物的物理属性共同组成的。特点：A文件小。B可采取高分辨印刷。C图形可以无限缩放。3 图形学过程3D几何建模、3D动画设置、绘制（光照和纹理）、生成图像的存储和显示4 与图像处理计算机图形学：研究模型及数据的建立和由模型生成

3、图像的过程和方法。（模型到图像）图像处理：将客观景物数字化成图像，研究数字化图像的采集、去噪、压缩、增强、锐化、复原及重建等。（图像到特征）对立统一的关系。5 计算机图形信息的特点图形信息表达直观，易于理解。图形信息表达精确、精炼。图形信息能“实时”的反映事物的分布和变化规律6 计算机图形学的应用计算机辅助设计及计算机辅助制造科学计算可视化地图制图与地理信息系统计算机动画、游戏用户接口计算机艺术7 计算机图形系统作为一个图形系统，至少应具有计算、存储、输入、输出、对话等五个方面的基本功能。计算机图形系统主要有三部分构成：人、图形软件包、图形硬件设备。图像硬件设备通常由图形处理器、图形输入设备和

4、输出设备构成。第二章1图形的扫描转换确定一个像素集合及其颜色，用于显示一个图形的过程，称为图形的扫描转换。从本质上讲，图形的扫描转换是由参数表示形式到点阵表示形式的转换过程。PS1：在输出设备上输出一个点，首先需要计算出最逼近该点的像素位置，其次需要把应用程序中的坐标信息转换成所用输出设备的相应指令PS2：在显示器有限个像素中，确定最佳逼近该直线的一组像素，并且按扫描线顺序，对这些像素进行写操作，这个过程称为直线的扫描转换。2 DDA算法最基本思想：从x的左端点x0开始，向x右端点步进，步长=1(个像素)。X步进后，用y=kx+b计算相应的y坐标。最后取像素点(x, 取整round(y)作为当

5、前点的坐标。即当x每递增1，y递增k。PS：实际代码时用Y+0.5替代取整。PS2：当 |k|>1时，必须把x，y地位互换。按照从(x1, y1)到(x2, y2)方向不同，分8个象限。例如对于方向在第1a象限内的直线而言，取增量值Dx=1，Dy=k。对于方向在第1b象限内的直线而言，取增量值Dy=1，Dx=1/k。其余同理。优点：最简单，最直接的画线算法。采用增量的思想，每计算一个像素，只需计算一个加法。缺点：由于斜率很可能是小数（浮点数），因此每个加法都意味着是浮点运算，浮点运算不利于硬件实现；每次加法后还必须进行一次四舍五入后的取整运算。3 中点画线法假设当前像素点为P(xp, y

6、p) ，则下一个像素点为P1（右） 或P2（右上） 。设M=(xp+1, yp+0.5)，为p1与p2之中点，Q为理想直线与x=xp+1垂线的交点。将Q与M的y坐标进行比较。当M在Q的下方，则P2应为下一个像素点；M在Q的上方，应取P1为下一点。具体算式：d=F(M)=F(xp+1,yp+0.5) =a(xp+1)+b(yp+0.5)+c（a=y0-y1， b=x1-x0，c=x0y1-x1y0）当d<0，M在Q点下方，取右上方P2为下一个像素；当d>0，M在Q点上方，取右方P1为下一个像素；当d=0，选P1或P2均可，约定取P1为下一个像素；改进1：根据前一点的判别式值d和整数增

7、量即可得到后一点的判别式值d。 因此可采用增量计算，只有加法，提高运算效率。若当前像素处于d>0情况，则取正右方像素P1 (xp+1, yp ), 要判下一个像素位置，应计算d=d+a；若d<0时，则取右上方像素P2 (xp+1, yp+1)。要判断再下一像素，则要计算 d= d+a+b改进2：由于只判别d 的符号确定下一个像素位置，因此可以用2d来判别，化为整数算法。递推算法中只包含加、减运算，便于硬件实现。d=d+2a；d= d+2（a+b）4 Bresenham算法基本思想：过各行各列像素中心构造一组虚拟网格线。按直线从起点到终点的顺序计算直线与各垂直网格线的交点，然后根据误

8、差项的符号确定该列像素中与此交点最近的像素。算法：假设起始位置像素落在直线上，d = 0；沿横坐标每前进一步，d 的值增加量为k, 即d = d + k；一旦d > 1，即令d = d1， 保证 d 介于0与 1之间。当d > = 0.5 时， 直线接近右上方像素，d < 0.5 时，直线接近右方像素。为便于判别，令 e = d 0.5， 则当e >= 0， 取右上方像素，当 e < 0， 取右方像素。e 的初始值为 0.5。y在递增时，e在取值范围一般介于-0.5与0.5之间。改进：由于只判别 e 的符号，确定像素的取舍，因此可令 e = 2 × e

9、× dx，通过判别 e 的符号确定像素取舍，不但可以避免小数运算，还能避免除法。优点：增量算法、避免了浮点运算、避免了乘除法运算，节省运算量，并适合硬件实现，使用最广泛5 圆的扫描转换若已知圆弧上一点P1C（x, y），利用其对称性便可以得到关于四条对称轴的其它7个点，即：P2C（x,y），P3C（x, y），P4C（x,y），P5C（y，x），P6C（y，x），P7C（y，x），P8C（y，x）。这种性质称为八对称性。因此，只要扫描转换八分之一圆弧，就可以通过圆弧的八对称性得到整个圆。6 中点画圆法函数（圆心在原点为例）： F(x,y)=x2 y2R2，第一点为P（xp，yp）圆上

10、点： F(x,y)= 0；圆外点： F(x,y)> 0；圆内点： F(x,y)< 0设M是待选像素P1，P2的中点, M坐标(xp+1,yp-0.5)，判断d=F(M)若 d<0, 则取右侧P1( xp+1,yp)为下一像素，而且再下一像素的判别式为d=d+2xp+3；若d>=0, 则应取右下P2(Xp+1,Yp-1)为下一像素，而且下一像素的判别式为d=d+2（xp-yp）+5。例：第一个像素是（0,R），第一个M的坐标为(1,R-0.5)，则判别式d的初始值为1.25-R。改进：为了进一步提高算法的效率，可以将上面的算法中的浮点数改写成整数，将乘法运算改成加法运算，

11、即仅用整数实现中点画圆法。即使用e=d-0.25代替d，即e0=1-R。则判别式 d < 0 对应于e < -0.25 ,由于 e0=1-R 的初值为整数， 且在运算中增量为整数，故 e < -0.25 等价于 e < 0 !7 Bresenham画圆法基本思路：通过比较临近像素点到圆弧的距离，设法求出该距离的递推关系，并通过符号判别像素取舍。设从点Pi(xi,yi)出发，顺时针画第一个四分圆。待选点与圆弧只可能有5种关系。下一像素有3种可能的选择：H=(xi+1)2+yi2-R2D=(xi+1)2+(yi-1)2-R2V=xi2 +(yi-1)2-R2 选择像素的原则

12、：使其与实际圆弧的距离平方达到最小具体算法：考察右下角像素D 与实际圆弧的近似程度：D=(xi+1)2+(yi-1)2-R2当D<0时，D在圆内，情形当D=0时，D在圆上，情形当D>0时，D在圆外，情形结论：当D<0时,若2 (D+yi) -1 0，选H若2 (D+yi) -1 >0，选D当D>0时,若2 (D -xi)-1 0，选D 若2 (D -xi)-1 >0，选V当D=0时，选D完整流程：(1) 初值:从(0, R)开始画圆， D=(0+1)2+(0-1)2-R2 =2(1R)；(2) 根据D的符号判断，计算dHD或 dDV，确定选中D、H、V中某点

13、；(3) 若下一像素为H(x,y) (x1，y)，则 D D2x1；(4) 若下一像素为D(x,y) (x1，y1)，则 D D2x2y2；(5) 若下一像素为V(x,y) (x，y1)，则 D D2y1；(6) 重复(2)(5), 直至完成圆弧。第三章1多边形的表示方法A顶点表示：用多边形的顶点序列来刻画多边形。特点：表示方法直观，几何意义强，占内存空间少。但没指明哪些像素在多边形内，不能直接用于着色B点阵表示：用位于多边形内部或边界上的像素集合来刻画多边形。会失去很多重要的几何信息，但它是光栅显示系统显示面着色时所需的图形表示形式。2 扫描转换与区域填充的联系与区别（1）定义多边形的扫描转

14、换：从多边形顶点表示到点阵表示的转换，这种转换称为多边形的扫描转换。这种转换就是给多边形包围的区域着色的过程。即从多边形的给定边界出发，求出位于其内部的各个像素，并将其灰度和颜色值写入帧缓存中相应单元。主要用来填充多边形区域以及由多边形拟合的其他简单曲线区域。区域填充：从给定的位置开始涂描直到指定的边界为止。区域是指一组相邻而又相连的像素，且具有相同的属性。区域填充可用在具有复杂形状边界的多边形以及交互式绘图系统中。（2）联系都是光栅图形面着色，二者可相互转换。当已知顶点表示的多边形内一点作为种子点，并用扫描转换直线段的算法将多边形的边界表示成八连通区域后，多边形扫描转换问题就可转化为区域填充

15、问题；若已知给定区域是多边形区域，并且通过一定的方法求出它的顶点坐标，则区域填充问题便可以转化为多边形扫描转换问题。（3）区别A基本思想不同，各自应用的场合不同。多边形扫描转换是指将多边形的顶点表示转换成点阵表示的方法，而区域填充只改编了区域的填充颜色，没有改变区域的表示方法。B对边界的要求不同。多边形扫描转换不要求多边形的边界封闭。而区域填充为了防止递归填充时跨越区域的边界，需设定边界。C基于的条件不同。多边形扫描转换是从多边形的边界信息出发，利用多种形式的连贯性进行填充；区域填充算法给定区域内一点作为种子点，从这点根据连通性将新的颜色扩散到整个区域。3 矩形填充填充从ymin到ymax每条

16、扫描线位于xmin和xmax之间的区段就可以了。共享边的处理方式：如果像素的中心落在矩形边界的左方或下方时，该像素属于矩形，否则不属于该矩形区域，也就是说，如果象素的中心落在矩形边界的右方或上方时，该象素不属于矩形区域。4 扫描转换三种方法逐点判断算法（射线法、弧长法）；扫描线填充算法；边缘填充算法（1）射线法由被测点向某方向做射线，计算此射线与多边形所有边的交点个数。若交点个数为奇数，则被测点在多边形内部；若交点个数为偶数(包括0)，则该点在多边形的外部。规定射线过顶点时，计数为1；在射线左边的边与该射线相交时交点有效，应计数；而在射线右边的边与射线相交时交点无效，不计数 (左闭右开原则)。

17、（2）弧长法前提：多边形由有向边组成, 即规定沿多边形各边的走向其左侧(或右侧)为多边形的内部。方法：以被测点为圆心作单位圆，将全部有向边向单位圆作径向投影，并计算其在单位圆上弧长的代数和。若代数和为0，则被测点在多边形之外；若代数和为2Pi，则被测点在多边形之内。（效率低）（3）扫描线填充算法算法思想：按扫描线顺序，先计算出扫描线与多边形区域边界的交点，然后判断扫描线上的哪些部分在区域边界之内，最后用要求的颜色对边界内的像素填色。实现方法：依次考察各条扫描线，一条扫描线从左至右与多边形的交点是成对出现的。即A、B点，C、D点之间的像素都位于多边形之内，则A、B为一个区段， C、D为一个区段。

18、对这些区段内的像素用指定的颜色进行填充后，就完成了该扫描线的填充工作，再继续下一条扫描线。实现步骤（四步）：A求交点：计算扫描线与多边形各边的交点B交点排序：把所有交点按递增顺序进行排序C交点配对：第一个交点与第二个交点，第三个交点与第四个交点等,每对交点代表扫描线与多边形的一个相交区间(A、B) (C、D)D区间填色：把这些相交区间内的象素置成多边形颜色，把相交区间外的象素置成背景色。注1：如何保证交点正确配对？答：检查两相邻边在扫描线的哪一侧。若共享顶点的两条边：分别落在扫描线两边，取交点1次；均高于扫描线，取交点2次；均低于扫描线，取交点0次。（具体实现：检查顶点的两条边的另外两个端点的

19、y值，按这两个y值中大于交点y值的个数是0、1、2来决定交点是取零个、一个、两个。）注2：边界上像素的取舍问题？答：落在右/上边界的象素不予填充，而落在左/下边界的象素予以填充。（具体实现：对扫描线与多边形的相交区间，取“左闭右开”；而正确配对则保证了多边形的“下闭上开”。）数据结构：为了求出扫描线与多边形边的交点，最简单的方法是将多边形的所有边放在一个表中,称之为边表，在处理每条扫描线时，从表中顺序取出所有的边，分别求这些边与扫描线的交点。实际上在进行扫描线与多边形边求交点时，应只求那些与扫描线相交的边的交点。把与当前扫描线相交的边称为活性边。并把它们按与扫描线交点 x 坐标递增的顺序存放在

20、一个链表中，称此链表为活性边表。边表(ET)构造：先按端点的纵坐标值对所有边作总分组，再将同一组中的边按端点X坐标递增的顺序进行排序。活性边表(AET) ：假设当前扫描线与多边形的某一条边的交点坐标为x，那么下一条扫描线与该边的交点不必从头计算，只要加上一个增量即可。（设边AB的斜率为k，若其与扫描线yi的交点横坐标为xi，则与扫描线yi1的交点的横坐标为： xi1xi1/k ）活性边表(AET)的结点中至少应为对应边保存如下内容：X: 边与当前扫描线的交点的X坐标； X: 当前扫描线到下一扫描线之间x的增量Ymax: 边所交的最高扫描线号； 算法步骤：优点：A数据结构和算法本身要比逐点判断算

21、法复杂。B速度比逐点判断算法快得多。C利用边的连贯性来加速交点的计算D利用AET以排除盲目求交E利用扫描线的连贯性以避免逐点判别缺点：对各种表的维持和排序开销大。（4）边缘填充算法基本思想：对于每一条扫描线和每条多边形边的交点(x1,y1)，将该扫描线上交点右方的所有像素取补。（对该区域内象素颜色作偶数次取补运算后，该区域内象素的颜色保持不变，而做奇数次取补运算后，该区域内象素的颜色变为M。）优点是算法简单，缺点是对于复杂图形，每一象素可能被访问多次，增加了运算量。（5）(栅栏)边缘填充算法栅栏：指的是一条与扫描线垂直的直线。栅栏位置通常取多边形的顶点，且把多边形分为左右两半。基本思路：对于每

22、个扫描线与多边形的交点，将交点与栅栏之间的象素用多边形的属性值取补。算法特点：A用求补运算代替排序B数据结构和程序结构简单C需要对帧缓存的大量象素反复赋值D运行速度比扫描线算法慢5 区域填充区域：指已经表示成点阵形式的填充图形，它是象素的集合。分类：4连通内部表示区域：可以从任一象素出发，通过上、下、左、右等4个方向的移动，到达另一个象素；8连通内部表示区域：从任一个象素出发，需要通过水平、垂直、对角线等8种方向的移动，到达另一个象素。区域的特点:A一条扫描线上的像素存在着相关性；B在多边形边处，像素性质才发生变化；C将相邻像素放在一起测试，从而减少测试点的数目。区域填充：指先将区域的一点赋予

23、指定的颜色，然后将该颜色扩展到整个区域的过程。区域填充算法要求区域是连通的。区域建立和定义的方式：A1内定义区域：区域内部所有象素具有同一种颜色或亮度值，而区域外的所有象素具有另一种颜色或亮度值。A2漫水法：将该区域内的全部象素都设置为新值的算法，即填充内定义的区域B1边界定义区域：边界上所有象素均具有特定的颜色或亮度值，而在区域内的象素则具有不是新值的某种颜色或亮度值。B2边界填充算法：将边界定义区域中的全部象素值都设置为新值的算法。6 漫水法（种子填充法）基本思想：设（x，y）为四连通区域内部的一点，old_Color为区域内部所有象素的原色。现取（x，y）为种子点，要将整个区域填充为新的

24、颜色new_Color。填充算法：先判别象素（x,y）的颜色：若它的值等于old_Color，说明该象素位于该区域内部，则设置该象素的颜色为new_Color，并对与该象素相邻的上、下、左、右4个相邻象素作递归填充；否则说明该象素的颜色在区域外或已被填充过，不再进行处理。7 边界填充算法基本思想：与漫水法的基本思想一样，只是在测试（x，y）点的象素是否处在区域之内同时又未被访问过时，包括两部分的内容：与边界值相比较，以检测此象素是否为该区域的一部分；与新值相比较，以决定该象素是否已被访问过。前提条件：在初始状态，区域内没有一个象素已设置为新值。但是允许新值等于边界值。在区域内测试（x，y）点的

25、象素是否在区域之内同时又未被访问过，一般采用堆栈的方法。对边界定义的区域进行填充，基本流程如下 ：A种子象素入栈，当栈非空时，执行如下三步操作：B栈顶象素出栈；C将出栈象素置成多边形色；D按上、下、左、右的顺序检查与出栈象素相邻的四个象素，若其中某个象素不在边界上且未置成多边形色，则把该象素入栈。算法特点：A算法程序简单，表达清楚B需要反复递归，其执行效率并不高C未考虑象素间的相关性，而是孤立地对一个个象素进行测试。8 扫描线区域填充算法基本思想：利用了象素之间的连贯性，将扫描线上位于区域内部的相邻象素作为一个区域来考虑，只选一个象素作为代表进栈，从而极大地减少了对栈空间的需求，并且显著地提高

26、了执行效率。算法过程：首先填充当前扫描线上位于区域内部的一个区段，它的颜色为old_Color，现在将fill_Color作为区域填充的新颜色；然后确定与这一区段相邻的上、下两条扫描线上位于区域内部的区段，分别将它们右端象素作为种子点保存起来。反复进行这一过程，直到保存的区段都填充完毕为止。基本步骤：A种子象素压入堆栈；B从包含种子象素的堆栈中推出区段的种子象素；C沿着扫描线对种子象素的左右象素进行填充，直至遇到边界象素为止，标记区段的左、右端点坐标为xl和xr；D在区间xl，xr中检查与当前扫描线y上、下相邻的两条扫描线上的象素。若存在非边界、未填充的象素，则把每一区间的最右象素作为种子点压

27、入堆栈，返回第步。E堆栈为空时结束。第四章1输出图元属性在图元输出之前，可为其指定不同的属性，属性定义了图元在输出设备上的外部特征。如线宽、线型、色彩等。（1）线宽控制顺着扫描所产生的线条轨迹，移动一把具有一定宽度的 “刷子”，刷子的形状可以是一条线段或一个正方形。也可以采用区域填充的办法间接产生有宽度的线。（2）线型控制使用具有不同线型的线条来表示不同的含义，线型属性主要包括实线、虚线、点划线。2线宽控制（1）线刷子法：在扫描转换图元时，同时显示n个像素。这样就将原来绘制单个像素的语句改写成以该像素为中心绘制水平或垂直排列的多个像素。（斜率绝对值小于1，垂直方向上像素复制；斜率绝对值大于1，

28、水平方向上像素复制）优点：算法简单、执行效率高，适合于比较小的线宽。缺点：A线段的两端只有水平或垂直两种情况；B曲线要根据当前绘制像素的斜率来决定是在水平方向还是垂直方向复制像素C在折线连接处由水平复制转为垂直复制时，会产生缺口 D当线宽为偶数个像素时，线条要么粗一个像素，要么细一个像素。（2）方形刷子法：将原来绘制单个像素的语句改写成以该像素为中心绘制画笔位图的语句。也就是将设定宽度为k的画笔的中心沿线段移动，即可产生具有线宽k的线条。（3）区域填充法：根据线条的宽度，计算出线条的外轮廓，然后调用填充图元的生成函数将其填充，产生具有一定线宽的线条。3线型控制显示虚线时：把画线算法修改为沿一直

29、线输出带有间隙的短实线；点划线：是每画一短实线加入一点；其他线型：可通过短划线的长短不同及间隙不同来重新组合得到。*4 字符分类：ASCII码字符、汉字字符表示方法: （1）位图表示对输出字符要求较高时使用。缺点：需占用大量存储空间，可以使用固定大小的字体来产生大小和字形等方面的各种变化，但效果往往不能令人满意。（2）轮廓线表示：采用直线或二、三次Bezier曲线的集合来描述一个字符的轮廓线。特点：可对字符的轮廓线作变换产生一种字体的各种变化，只需存储一套轮廓线表示，可节省大量的存储空间，但扫描转换需要更长的处理时间。字符属性：在输出字符之前，往往需要指定一系列字符属性。包括字体、字形、字符大

30、小、字符间距、字符颜色、字符串对齐方式等5 图形裁剪在放大显示一幅图形的一部分区域时，必须确定图形中哪些部分落在显示区之内，哪些落在显示区之外，以便显示落在显示区内的那部分图形。这个选择过程称为裁剪。实质：决定图形中哪些点、线段、文字、以及多边形在窗口之内。裁剪的基础：图元关于窗口内外关系的判别、图元与窗口的求交。A点裁剪：点(x, y)在窗口内的充分必要条件是，X属于XMIN,XMAX，Y同理B直线裁剪：待裁剪线段和窗口的关系若为线段完全可见、显然不可见，可直接处理；若线段至少有一端点在窗口之外，但非显然不可见，需求交。6直线裁剪算法（1）Cohen-Sutherland法对于每条线段P1P

31、2，若P1P2完全在窗口内则显示该线段P1P2，取之；若P1P2明显在窗口外则丢弃该线段P1P2，弃之；若线段既不满足“取”的条件也不满足“弃”的条件，则把线段分成两段。其中一段完全在窗口外，可弃之。然后对另一段重复上述处理。算法步骤：A建立区域码： 区域码：表示直线端点相对位置的4位二进制代码。区域码按照点与窗口边界的相对位置编码，即区域码的4位分别代表端点位于窗口的上、下、左、右在窗口上边线之上，第4位为1，否则第4位为0；在窗口下边线之下，第3位为1，否则第3位为0；在窗口右边线之右，第2位为1，否则第2位为0；在窗口左边线之左，第2位为1，否则第1位为0；B依区域码裁剪：若code1=

32、0且code2=0，P1P2明显在窗口内，则取若code1&code20，P1P2明显在窗口外，则弃;在交点处把线段分为两段。其中一段完全在窗口外，可弃之。然后对另一段重复上述处理。注：如何判定应该与窗口的那条边求交？答：编码中对应位为1的边。（2）中点分割算法从P0点出发找出离P0最近的可见点，和从P1点出发找出离P1最近的可见点。这两个可见点的连线就是原线段的可见部分算法步骤：与Cohen-Sutherland算法一样首先对线段端点进行编码，并把线段与窗口的关系分为三种情况，对前两种情况进行一样的处理；对于第三种情况，用中点分割的方法求出线段与窗口的交点。具体流程：找距离P0最近可

33、见点A先求出P0P1的中点Pm,B若P0Pm不是显然不可见的，并且P0P1在窗口中有可见部分，则距P0最近的可见点一定落在P0Pm上，所以用P0Pm代替P0P1；C否则取PmP1代替P0P1。D再对新的P0P1求中点Pm。重复上述过程，直到PmP1长度小于给定的控制常数为止，此时Pm收敛于交点。7多边形裁剪：Sutherland-Hodgman算法基本思想：每次用窗口的一条边裁剪多边形。流水线过程(左上右下)：前边的结果是后边的输入。算法实现：窗口的一条边以及延长线构成的裁剪线把平面分成两个部分，多边形的各条边的两端点S、P与裁剪线的位置关系有四种。仅用一条裁剪边对多边形进行裁剪，得到一个顶点

34、序列，作为下一条裁剪边处理过程的输入。缺点：在所裁剪的多边形是一个凹多边形时，最后裁剪生成的区域可能存在两个或多个不相连接的多边形。*8 字符裁剪标准字符一般把字符作为一个整体裁剪；线段组成的字符，可用直线裁剪方法。字符裁剪方法可分为： A以串为单位的裁剪：把整个字符串作为整体来处理。或全部显示，或全不显示。B字符裁剪：每1个字符被一个称为字符框的矩形所包围，然后以这个框和窗口进行比较，若这个框在完全窗口内则显示该字符。C矢量裁剪：把每个字符都看作是一些短直线(笔划)的组合，每一笔划都进行裁剪。9反走样原因：由于在对信号进行数字化处理时，物体上的某坐标点的位置是以光栅上的整数象素位置近似表示的

35、。分类：A阶梯状的边界：即光滑的线段变成了离散的阶梯形状。B图形细节失真：当且仅当象素中心被这些矩形覆盖时象素才被显示。C狭小图形遗失：由于狭小的多边形分布在两条扫描线之间，它们不覆盖任何一个象素中心，因此，没有被显示出来。反走样方法：A提高分辨率：显示器的分辨率提高(代价大)。或使用软件来提高分辨率，即用高分辨率计算，用低分辨率显示(代价小).B反走样线段方法：将位于相邻台阶之间的象素置为过渡颜色或灰度，使得颜色或灰度自然过渡，变化柔和，这样线段看起来就显得平直了，从而可消除台阶效应。C反走样多边形边界算法：根据象素与多边形相交部分的面积来设置象素的亮度，这样能够明显减少多边形边界上的台阶现

36、象。第五章1图形变换：定义：对图形的几何信息经过几何变换后产生新的图形。对于线框图的变换，通常以点变换作为基础，把图形的一系列顶点作几何变换，连接新的顶点系列即可产生新的图形.对于用参数方程描述的图形，可以通过参数方程作几何变换，实现对图形的变换.2平移变换平移是一物体从一个位置到另一个位置所作的直线移动。P=P+T3比例变换用来改变一物体大小的变换，也称为缩放变换。P=S*P4旋转变换物体上的各点绕一固定点沿圆周路径作转动称为旋转变换。P=R *P5齐次坐标技术的引入原因平移变换的处理方法与其他两种变换的形式不一样，希望能够用一种一致的或同类的方法来处理这3种变换，使得这3种基本变换能很容易

37、地结合在一起，形成各种复杂的组合变换。6齐次坐标：基本思想：把一个n维空间的几何问题，转换到n1维空间中去解决。形式：用一个有n1个分量的向量去表示一个有n个分量的向量的方法。如二维平面上的点(x，y)的齐次坐标表示为( hx，hy ，h)，h是任一不为0的比例系数。规格化齐次坐标：齐次坐标表示不是唯一的，通常将h1时的齐次坐标称为规格化的齐次坐标。7齐次坐标表示法在计算机图形处理中的优越性（1）将平移、旋转、缩放3种变换用统一的方式（矩阵乘积）表达。提供了用矩阵运算将二维、三维或更高维空间中的一个点集从一个坐标系变换到另一个坐标系的有效方法。（2）可以表示无穷远点。8几何变换的齐次坐标表示由

38、于齐次坐标表示的点是用3个分量的行向量来表示的，这样变换矩阵也必须是3×3的矩阵，以便于矩阵相乘，当然变换后得到的点也是有3个分量的齐次坐标。8.1平移变换8.2比例变换8.3旋转变换8.4反射变换用来产生物体的镜像。当a=-1, e=1时，与y轴对称的反射变换。当a=1, e=-1时，与x轴对称的反射变换。当a=e=-1时，与原点对称的反射变换。当b=d=1 时，与y=x对称的反射变换。当b=d=-1时，与y=-x对称的反射变换。8.5错切变换使物体产生变形，即物体产生扭转。错切的角度为q，令shxtan q。错切变换引起图形角度关系的改变，甚至导致图形发生变形。1) 当d=0时，

39、图形的y坐标不变；当b>0：图形沿+x方向作错切位移。当b<0：图形沿-x方向作错切位移。2)当b=0时， 图形的x坐标不变；当d>0：图形沿+y方向作错切位移。当d<0：图形沿-y方向作错切位移。3) 当b¹0且d¹0时，图形沿x, y两个方向作错切位移。9二维几何变换的一般形式(仿射变换)X=AX+BY+CY=DX+EY+F10二维变换矩阵：对图形进行缩放、旋转、堆成、错切：平移（G H）： 投影（I）：图形整体伸缩（I>1缩小，I<1放大）11组合变换任意一个变换序列均可表示为一个组合变换矩阵。由若干基本变换矩阵相乘求得组合变换矩阵

40、的方法称为矩阵的级联。（1） 组合平移变换：进行连续两次平移，实际上是把平移距离相加。（2） 组合比例变换：连续进行两次比例变换，实际上是把相应的比例因子相乘。（3） 组合旋转变换: 连续旋转实际是把旋转角相加。R(2)*R(1)= R(1+2)12多个基本变换的组合变换（1） 相对于任一固定点的比例变换由基本平移变换矩阵及比例变换矩阵，可得到相对于任一固定点A（xA,yA）的比例运算的组合矩阵。此时实际上是进行由三个基本变换形成的一个变换序列。1）把图形及固定点一起平移，使固定点移到坐标原点上；2）把图形相对于原点进行比例变换3）把图形及固定点一起平移，使固定点又回到原来位置。（2） 围绕任

41、一基准点的旋转变换1）把物体平移，使基准点与坐标原点重合。2）把物体绕原点旋转。3）把物体平移，使基准点回到原来位置（3） 关于任意轴的对称变换1）平移使l过坐标原点，记变换为T1，图形A被变换到A12）旋转q角，使l和ox轴重合，记变换为R1，图形A1被变换到A23）求图形A关于x轴的对称图形A3，记变换为RFx4）旋转-q角，记变换为R2，图形A3被变换到A45）平移使l回到其原先的位置，记变换为T2，图形A4被变换到A5，A5即为A关于l的对称图形。*13 三维变换三维图形的平移、比例及旋转变换是对二维变换的扩展，即三维情况下应附加考虑z坐标的变换。对于三维空间点需要用4个数来表示，而相

42、应的变换矩阵是4×4阶矩阵。左手坐标系、右手坐标系3*3比例旋转、3*1平移*14 窗口和视图（1） 用户区 ：程序员用来定义草图的整个自然空间（2） 窗口区：用户指定的任一区域。窗口区小于或等于用户域.（3） 屏幕域：设备输出图形的最大区域，如显示器分辨率。（4） 视图区：任何小于或等于屏幕域的区域。视图区用设备坐标定义在屏幕域中。窗口区显示在视图区，需做窗口区到视图区的坐标转换。第六章1 曲线的表示形式（1）显式表示，Y=F(X)，特点：不能表示封闭或多值曲线（2）隐式表示，F(X,Y)=0，特点：与坐标轴相关；会出现斜率为无穷大的情况；不便于计算和编程。（3）参数表示：X=X(

43、T)，Y=Y(T),T属于(0,1)矢量形式为：2参数表示优点A有更大的自由度来控制曲线、曲面的形状。B对非参数方程表示的曲线、曲面进行变换，必须对曲线、曲面上的每一个型值点进行几何变换，而对参数曲线、曲面可对其参数方程直接进行几何变换，节省计算量。C便于处理斜率为无穷大的问题，不会因此中断计算。D参数方程中，代数、几何相关和无关的变量是完全分离的，且对变量个数不限，便于将低维空间扩展到高维空间。E参数变量定义了几何分量的界限。F易于用矢量和矩阵表示几何分量，简化了计算。3插值 给定函数f(x)在区间a,b中互异的n个点的值f(xi) i=1,2,n，基于这个列表数据，寻找一个函数g(x)去逼

44、近f(x)。若要求g(x)在xi处与f(x)相等，就称这样的函数逼近问题为插值。称g(x)为f(x)的插值函数。xi为插值节点。（1） 线性插值设给定函数f(x)在两个不同点x1和x2的值，y1=f(x1)，y2=f(x2)，要求用一个线性函数： Y=AX+B近似代替y=f(x)。（Y的表达式：点斜式/两点式）（2） 抛物线插值又称二次插值。设已知f(x)在三个互异点x1、x2、x3的函数值为y1、y2、y3，要求构造一个函数：Y=AX2+BX+C，使其在节点xi处与f(x)在xi处的值相等。4插值 当型值点太多时，构造插值函数使其通过所有的型值点相当困难。选择一个次数较低的函数，在某种意义上

45、最佳逼近这些型值点。假设已知一组型值点(xi,yi)（i=1,2,n)，要求构造一个m(m<n-1)次多项式函数y=F(x)逼近这些型值点。最常用的方法为最小二乘法。逼近的好坏常用各点偏差的平方和最小或加权的方差最小。其中关键是确定出F(x)系数aj，使偏差平方和达到极小。这里有m+1个方程，可解出m+1个未知数a0,a1,am，代入定义即可求得多项式函数F(x)逼近已知的n个型值点。5光顺、拟合光顺是指曲线的拐点不能太多，对平面曲线而言，相对光顺的条件是：具有二阶几何连续(G2)、不存在多余拐点和奇异点、曲率变化较小。拟合指的是曲线、曲面的设计过程中，用插值或逼近方法是生成的曲线、曲面

46、达到某些设计要求。6参数曲线的代数形式和几何形式（1）代数形式（2）几何形式对曲线两端点，P0=A0,P(1)=A0+A1+A2+A3,P(0)=A0, P(1)=A1+A2+A3解得A0A3，代入有P(t)=F1P0+F2P1+F3P0+F4P1，P0P1为几何系数，F1F4为调和函数。7 Bezier曲线Bezier曲线由一组折线（Bezier特征多边形）定义，曲线的起点和终点与该多边形的起点和终点重合，且多边形的第一条边和最后一条边表示了曲线在起点和终点处的切矢量方向。曲线的形状趋于特征多边形的形状。.调和函数的性质：正性、权性、对称性、递归性曲线的性质：（1）对称性保持顶点Pi的位置不

47、变，将其次序颠倒过来，则新的Bezier曲线形状不变，只是走向相反。（2）凸包性曲线上各点均落在Bezier特征多边形构成的凸包内。（3）几何不变性曲线的几何特征不随一定的坐标变换而变化性质。缺点：（1）特征多边形顶点个数决定了Bezier曲线的阶次，并且当n较大时，特征多边形对曲线的控制将会减弱。（2）Bezier曲线不能作局部修改，即改变某一个控制点的位置对整个曲线都有影响。*8 B样条曲线由空间的n+1个控制点生成的k阶B样条曲线是由L段B样条曲线逼近而成，每个曲线段的形状仅由点列中的k个顺序排列的点所控制。由不同节点矢量构成的均匀B样条函数所描绘的形状相同，可以看成是同一个B样条函数的简单平移。性质：局部性、连续性、几何不变性（曲线的形状和位置与坐标系的选择无关）、变差缩小性（平面内任一直线与曲线的交点不多于和外接多边形的交点）、造型灵活性第七章1 用户接口用户接口是为方便用户使用计算机资源所建立的用户和计算机之间的联系。一个图形系统，必须允许用户能动态的输入位置坐标、指定选择功能、拾取操作对象、设置变换参数等，即需要一个用户接口。良好的用户接口可以缩短人们与计算机之间的距离，使得计算机易学易理解，方便了用户，提高了工作效率，减少了使用计算机的出错率。常用接口类