计算机图形学复习材料

1、题型 简答题（20%左右） 填空题（30%左右） 计算题（30%左右） 算法描述题（20%左右）第一章 计算机图形学概述1. 图形学、图形定义计算机图形学(Computer Graphics，CG)是一门研究如何利用计算机表示、生成、显示和处理图形的学科。图形通常由点、线、面、体等几何属性和颜色、纹理、线型、线宽等非几何属性组成。2. 图形分类从生成技术上来看，图形主要分为两类：一类是基于线条信息表示的，如工程图、等高线地图、曲面的线框图等；另一类是真实感图形。3. 图形与图像之间的关系图形与图象是密切相关但又不同的两个概念。图象纯指计算机内以位图(Bitmap)形式存在的亮度和颜色信息；图形

2、则由场景的几何模型和物理属性共同描述。4. 计算机图形学的应用领域（6个）影视；游戏；工业设计；科学研究；艺术；医学；广告；教育；培训；军事等5. OPENGL简介OpenGL是SGI公司开发的一个跨平台的开放式图形编程工具。OpenGL集成了所有造型、变换、材质、纹理、光照、绘制等复杂的计算机图形学算法，将用户从具体的硬件和操作系统中解放了出来。了解：OpenGL本身是一个底层库，在编程实践中还需要一些能简化编程任务、易于在窗口系统上执行的高层库。OpenGL核心函数：OpenGL核心函数以gl开头，可以运行于任何的OpenGL工作平台。OpenGL实用库函数：实用库函数带有前缀glu，是基

3、于OpenGL核心函数而比其更高一层的函数。它们也可以运行于任何OpenGL平台。辅助库函数：它支持的平台较少，并不适合正式产品的开发。Windows专用函数：以wgl开头，用于连接OpenGL和Windows窗口系统。Win32 API函数，用于处理像素格式及缓冲：共6个Win32 API函数，用于处理像素格式及缓冲。要在Windows下使用实用工具库GLUT中的函数进行编程，需要另外下载glut32.dll、glut32.lib以及glut.h三个文件分别放入系统的相应目录。6. 光栅扫描的显示系统和随机扫描的显示系统的特点光栅扫描的显示系统：按照从上到下然后再跳回顶部的顺序逐行扫描。随机

4、扫描的显示系统特点：电子束可随意移动，只扫描屏幕上要显示的部分。7. 帧缓冲存储器用来存储像素颜色（灰度）值的存储器就称为帧缓冲存储器。简称帧缓冲器（显存）。帧缓存中单元数目与显示器上像素的数目相同，单元与像素一一对应，各单元的数值决定了其对应像素的颜色。显示颜色的种类与帧缓存中每个单元的位数有关第二章 计算机图形系统概述1 叙述计算机图形系统的基本功能。他的基本功能是帮助人们设计、分析、采集、存贮图形、视频甚至音乐等信息。2 输入设备可有哪几种逻辑功能？请举出各自对应的物理设备。可以分成以下6类逻辑输入设备：.定位(locator): 指定一个坐标点。对应的物理设备有鼠标器、键盘、数字化仪、

5、触摸屏等。.笔划(stroke): 指示一个坐标点系列, 如指定一条曲线的控制点等。主要物理设备有数字化仪。.送值(valuator): 输入一个数值。最常用的物理设备是键盘的数字键。.字符串（string）：输入一个字符串。键盘字母键.拾取(pick)：各种定位设备.选择(choise): 鼠标器，数字化仪，键盘功能键等3 画出图形软件的层次结构及主要组成。- | 应用程序 | | - | | 图形支撑软件 | | | - | | | 高级语言 | | | | - | | | | 操作系统 | -主要部分： 图形核心系统GKS 计算机图形元文件CGM 计算机图形设备接口CGI程序员层次结构图

6、形系统PHIGS 4 颜色查找表的概念及实现原理。它是为了让我们能够在每个祯缓存单元的位数不增加，却能具有在很大范围内挑颜色的能力。此时由祯缓存读出来的值并不是相应像素的值，而是彩色表中的一个编号。按照这个编号在彩色表中取出的数才是该像素的彩色值。5 光栅扫描显示器结构与工作原理。 其一, 由计算机执行相应的图形应用程序, 图像生成系统接受指令将图形的矢量表示转换成像素表示, 再将像素值存入显示存储器; 其二, 图像生成系统直接把图形输入设备(摄像机、扫描仪等)输入的图形图像直接或经过主存储器间接地存放到显示存储器中。 显示控制器生成水平和垂直同步扫描信号送到监视器,使CRT电子束进行水平扫描

7、和垂直扫描形成光栅; 另一方面又根据电子束在屏幕上的行、列位置, 不断地读出显示存储器中对应位置的像素值。 利用彩色表将读出的像素值转换成R、G、B三原色的亮度值, 来控制CRT的R、G、B电子束,在屏幕对应点生成需要的像素颜色。 为了使屏幕上显示的画面不闪烁, (2)(3)应反复进行, 一般要求5060帧/秒。6 为什么要制订图形软件标准？举例说明它的分类。制定图形软件标准的目的在于使图形软件能够在不同的计算机和图形设备之间进行移植,以便提高图形软件的利用率, 降低开发成本,缩短研制周期, 使图形软件向着通用、高级与设备无关的方向发展。可以分为两类: .数据接口标准(CGM,PHIGS) .

8、子程序接口标准（GKS,CGI）第三章 基本图形生成算法1 Bresenham 直线生成算法原理。它与DDA 算法相比，有何改进？ 算法思想: 根据直线的斜率确定选择X或者Y方向作为计长方向, 在此方向上每次递增一个单位步长(或者一个像素单位), 另一个方向上是否同时产生一个单位增量由一个计算量很小的判别式来判断。void Bresenhamline (int x0,int y0,int x1, int y1,int color) int x, y, dx, dy; float k, e; dx = x1-x0, dy = y1- y0, k=dy/dx; e=-0.5, x=x0, y=y0

9、; for (i=0; i£dx; i+) drawpixel (x, y, color); x=x+1，e=e+k; if (e³0) y+, e=e-1; DDA为增量算法。它根据每一次增长时在另一轴上的增长计算下一个点应该画在哪里。Bresenham算法与它相比，由于全部采用了整数计算，使算法效率比起DD有大大提高，程序中只含有 + - 和*2的计算，便于使用计算机内硬件实现。2 比较几种常用画圆弧算法的原理和效率。1）Bresenham算法思想 其基本方法是从一个起点出发, 利用判别式选择下一个显示点。判别式的值通过简单计算获得, 其符号用作判断。只计算出1/8圆的

10、点的位置，就可以画出整个圆来，效率高。 2）正负法：首先区分不同象限的圆弧，然后，选定圆弧起点后，在输出圆弧过程中，根据当前点位置与理想圆弧的关系和所在象限，决定下一次的走向每次只在X或Y方向走步取点，这样一点一点逼近圆弧形状。在整个计算过程中，只使用了+ - 和*2运算，提高了硬件使用率。比起Bre算法 ，它更为简单。但生成的点数要比Bre多。3 简述两种字符生成方法。有两种基本的字符生成技术：一种是在计算机中用笔划(矢量)方式来表示,然后通过扫描转换生成, 这是目前常用的方法,生成的字符效果好, 但计算量大;另一种是在计算机内用位图(点阵)来表示, 存储在字符高速缓冲区(字符发生器)里,

11、显示时可以直接通过像素拷贝将其装入显示缓冲区中。这是传统的方法, 简单、速度快, 但不灵活。4、已知一直线段起点(0,0), 终点(5,2)，利用中点算法生成此直线段，写出生成过程中坐标点及判别式d的变换情况，并在下面的方格中，标出直线上各点。321参考答案：0 1 2 3 4 5 .15xyd001 110 2-3 321 43 531 6-1 742 85 952 105、已知一直线段起点(0,0), 终点(5,2)，利用Bresenham算法生成此直线段，写出生成过程中坐标点及判别式p的变换情况，并在下面的方格中，标出直线上各点。321参考答案：0 1 2 3 4 5 .15xyp00-

12、1 110 23 321 4-3 531 61 742 8-5 952 10第四章 区域填充1. 图形学中多边形的两种表示方式，各自优缺点 顶点表示：用多边形的有序顶点序列表示多边形 点阵表示：用位于多边形内部的像素集合来表示多边形4 顶点表示：l 优点l 直观l 几何意义明显l 存贮量小l 不足l 难以判断哪些像素位于多边形内部l 不能直接用于多边形着色点阵表示：l 优点l 便于用帧缓冲器(frame buffer)表示图形l 面着色所需的图形表示l 缺点l 丢失了几何信息l 占用存储空间多2. 区域表示的方式，内部表示和边界表示3. 四连通区域和八连通区域的定义、它们之间关系l 四连通区域

13、：区域内任意两个像素，从一个像素出发，可以通过上、下、左、右四种运动，到达另一个像素l 八连通区域：区域内任意两个像素，从一个像素出发，可以通过水平、垂直、正对角线、反对角线八种运动，到达另一个像素关系： 四连通区域 Í 八连通区域 (反之不成立) 四连通区域的边界是八连通区域 八连通区域的边界是四连通区域4. 内部表示区域种子填充算法l 假设内部表示区域为G，其中的像素原有颜色为G0，需要填充的颜色为G1。l 算法需要提供一个种子点(x,y)，它的颜色为G0。l 具体算法如下(四连通区域)Flood_Fill_4(x, y, G0, G1)if(GetPixel(x,y) =G0

14、) / GetPixel(x,y) 返回(x,y)的颜色SetPixel(x, y, G1); /将(x,y)的添上颜色G1 Flood_Fill_4(x-1, y, G0, G1);Flood_Fill_4(x, y+1, G0, G1); Flood_Fill_4(x+1, y, G0, G1); Flood_Fill_4(x, y-1, G0, G1);5. 边界表示区域种子填充算法Fill_Boundary_4_Connnected(x, y, BoundaryColor, InteriorColor)/ (x,y) 种子像素的坐标；/ BoundaryColor 边界像素颜色； In

15、teriorColor 需要填充的内部像素颜色if(GetPixel(x,y) != BoundaryColor && GetPixel(x,y)!= InteriorColor ) / GetPixel(x,y): 返回像素(x,y)颜色SetPixel(x, y, InteriorColor); / 将像素(x, y)置成填充颜色 Fill_Boundary_4Connnected(x, y+1, BoundaryColor, InteriorColor)；Fill_Boundary_4Connnected(x, y-1, BoundaryColor, InteriorCo

16、lor)；Fill_Boundary_4Connnected(x-1, y, BoundaryColor, InteriorColor)；Fill_Boundary_4Connnected(x+1, y, BoundaryColor, InteriorColor)；6. 判断一点是否位于多边形内部的射线法l 从当前像素发射一条射线，计算射线与多边形的交点个数 内部：奇数个交点 外部：偶数个交点7. 逐点判断算法逐个像素判别其是否位于多边形内部l 算法描述for(y=0; y<=y_resolution; y+)for(x=0; x<=x_resolution; x+)if(insi

17、de(polygon, x, y)setpixel(framebuffer,x,y,polygon_color)elsesetpixel(framebuffer,x,y,background_color)8. 逐点判断算法的不足l 速度慢：几十万甚是几百万像素的多边形内外判断，大量的求交、乘除运算l 没有考虑像素之间的联系l 结论：逐点判断算法不可取9. 多边形扫描转换算法（具体计算）10. 多边形扫描转换的优点与不足优点：l 充分利用多边形的区域、扫描线和边的连贯性，避免了反复求交的大量运算不足：l 算法的数据结构和程序结构复杂l 对各种表的维持和排序开销太大，适合软件实现而不适合硬件实现1

18、1. 多边形扫描转换与区域填充比较l 基本思想不同n 多边形扫描转换将多边形顶点表示转换为点阵表示，扫描过程利用了多边形的各种连贯性n 区域填充只改变区域的颜色，不改变区域的表示方法。填充过程利用了区域的连贯性l 对边界的要求不同n 多边形扫描转换只要求每一条扫描线与多边形有偶数个交点n 区域填充中u 四连通区域必须是封闭的八连通边界u 八连通区域必须是封闭的四连通边界l 出发点不同n 区域填充：知道需要区域内一个种子点(复杂计算)n 多边形扫描转换：没有要求12、何谓四连通和八连通？写出一种边界表示的八连通区域填充算法。区域的像素连通方式可以分为两类：4连通区域：取区域中的任何两个像素,从一

19、象素出发,通过上、下、左、右4种运动,只经过该区域的点可以达到另一像素。8连通区域：取区域中的任何两个像素,从一象素出发通过上、下、左、右、两条对角线方向共8种运动,只经过该区域的点可以达到另一像素。4连通区域是8连通区域的一种特殊情况。4连通区域的边界必定是8连通式的；8连通区域的边界必定是4连通式的。8连通区域(边界表示)填充漫水算法Procedure flood-fill-8(x,y,boundary-color,new-color:integer)beginif getpixel(framebuffer,x,y)<>boundary-color andgetpixel(fr

20、amebuffer,x,y)<>new-colorthen beginsetpixel(framebuffer,x,y,newcolor);flood-fill-8(x,y+1, boundary-color,new-color);flood-fill-8(x,y-1, boundary-color,new-color);flood-fill-8(x+1,y, boundary-color,new-color);flood-fill-8(x-1,y, boundary-color,new-color);flood-fill-8(x+1,y+1, boundary-color,new

21、-color);flood-fill-8(x+1,y-1, boundary-color,new-color);flood-fill-8(x-1,y+1, boundary-color,new-color);flood-fill-8(x-1,y-1, boundary-color,new-color);endend13、解释活化边表的思想，以多边形区域填充为例介绍它的应用。边的活化链表AEL：记录当前扫描线与棱边的交点序列。初值为空,在处理过程中利用ET表和求交点的递推关系不断刷新。.链表AEL的边元素由以下4个域组成：ymax：该棱边的上端点的y坐标；x：该棱边与当前扫描线交点的x坐标；Dx

22、：该棱边的斜率m的倒数；next：指向下一条棱边的指针。（应用略）14、已知多边形各个顶点的坐标为(2,2), (2,4), (8,6), (12,2), (8,1), (6,2)及(2,2), 在用扫描线填充算法实现扫描转换时, 写出其边表(ET)和全部的活化边表(AET)的内容。（应用略）第章五 图形变换与裁剪1、 三维变换的具体计算（平移、缩放、旋转）（计算题）2、 三维变换流程图局部坐标系世界坐标系视点坐标系图像坐标系规格化设备坐标系屏幕坐标系造型变换取景变换投影变换设备变换视窗变换3、裁剪算法分类（裁剪窗口的维数、裁剪窗口、对象维数、实现方式）l 裁剪窗口的维数：二维、三维l 裁剪窗

23、口：规则(矩形、六面体)和不规则的(任意多边形和多面体)l 对象维数：点、线、多边形、多面体实现方式：软件和硬件实现4、什么是灭点?在我们从一定的视角看3D图形时，会看到彼此平行的直线在远处有交点，这个交点就叫做灭点。5、试用几种不同顺序的简单几何变换,求出将平面上的任一线段P1(x1,y1), P2(x2, y2)变换成与X 轴重合的变换阵,并说明其等效性。几种常见的几何变换阵：平移变换阵： / 1 0 0 T = | 0 1 0 | Tx Ty 1 /(其中Tx,Ty分别是在X和Y轴上的平移量) 比例变换阵： / Sx 0 0 T = | 0 Sy 0 | 0 0 1 /(其中Sx,Sy分

24、别是在X和Y轴上的比例系数)旋转变换阵： / cos sin 0 T = | -sin cos 0 | 0 0 1 /(其中是绕原点逆时针旋转的角度)对称变换阵：对Y轴对称 / -1 0 0 T = | 0 1 0 | 0 0 1 /对X轴对称 / 1 0 0 T = | 0 -1 0 | 0 0 1 /对原点对称 / -1 0 0 T = | 0 -1 0 | 0 0 1 /对称于直线y=x / 0 1 0 T = | 1 0 0 | 0 0 1 /对称于直线y=-x / 0 -1 0 T = | -1 0 0 | 0 0 1 /题目中给出的线段，斜率为 k = （y2-y1）/ x2-x1

25、 ,可以使用以下几种方法进行变换：a. 先把它平移到原点处，再旋转成水平线。其变换矩阵为 /1 0 0 / cos sin 0 T = | 0 1 0 | | -sin cos 0 | -x1 y1 1 / 0 0 1 / (其中 = arctag(k) )b. 先旋转，使它水平，再平移到X轴上 / cos sin 0 /1 0 0 T = | -sin cos 0 | 0 1 0 | 0 0 1 / Tx 0 1 / (其中Tx 可由几何计算得出)c. 先平移，使原点在其所在的直线上，再旋转 /1 0 0 / cos sin 0 T = | 0 1 0 | | -sin cos 0 | 0

26、My 1 / 0 0 1 /其中My = x1*(y2-y1)/(x2-x1) y1 由计算结果可知，三者是等价的。6、已知OXYZ 坐标系下平面方程是x+y+z+d=0，试求变换距阵T，使该平面在OXYZ坐标系下变成z=0。三维坐标变换：比例变换： / a 0 0 0 T = | 0 e 0 0 | | 0 0 i 0 | 0 0 0 1 /其中a,e,i分别为在X，Y，Z坐标上的比例改变平移变换： / 1 0 0 0 T = | 0 1 0 0 | | 0 0 1 0 | l m n 1 /其中a,e,i分别为在X，Y，Z坐标上的平移量旋转变换：（手写）7、试简述二维图形裁剪的基本原理及可

27、选用的裁剪策略. 裁剪的原理: . 在显示图形之前, 组成图形的每一个基本元素都要经过裁剪, 因此裁剪算法直接影响整个图形系统的效率。. 裁剪的基本目的是判断图形元素是否在所考虑的区域内。如在区域内, 则进一步求出在区域内的那一部分。因此裁剪处理包含两部分内容:1)点在区域内外的判断;2)计算图形元素与区域边界的交点。1. 编码裁剪法(Sutherland-Cohen算法)2. 中点分割裁剪法多边形的裁剪 1. 逐边裁剪法2. 双边裁剪法8、写出梁友栋-Barsky二维直线段裁剪算法的伪代码void LB_LineClip(x1,y1,x2,y2,XL,XR,YB,YT)float x1,y1

28、,x2,y2,XL,XR,YB,YT;float dx,dy,u1,u2;tl=0;tu=1;dx =x2-x1;dy =y2-y1; if(ClipT(-dx,x1-Xl,&u1,&u2) if(ClipT(dx,XR-x1, &u1,&u2) if(ClipT(-dy,y1-YB, &u1,&u2) if(ClipT(dy,YT-y1, &u1,&u2) displayline(x1+u1*dx,y1+u1*dy, x1+u2*dx,y1+u2*dy) return; bool ClipT(p,q,u1,u2) float p

29、,q,*u1,*u2; float r;if(p<0)r=q/p; if(r>*u2) return FALSE; else if(r>*u1) *u1=r;return TRUE; else if(p>0)r=p/q;if(r<*u1)return FALSE;else if(r<*u2) *u2=r;return TRUE; else if(q<0) return FALSE; /p=0 return TRUE;9、如果裁剪窗口为圆形，试提出一种二维直线段的裁剪算法。算法思想：把直线段和圆的关系分为3种：（1）直线段完全在圆内：直线段的2个端点都在

30、圆内（2）直线段和圆相离/相切：圆心到直线段的距离大于/等于半径（3）直线段和圆相交 算法步骤:（1）判断直线段的2个端点是否都在圆内，若是，则此线段就是裁剪结果，算法结束，否则转（2）（2）判断圆心到直线的距离，如果大于或等于半径，弃此直线段，算法结束；否则，直线和圆相交，转到（3）。（3）计算直线段和圆的交点。若2个端点都在圆外，则2个交点之间的线段就是裁减结果，否则在直线段上的交点和圆内的端点决定的线段为裁剪结果10、描述Cohen-SutherLand二维直线段裁剪算法的基本原理，并以图形示意。算法的的基本原理：对于每条线段P1P2分为三种情况处理。（1）若P1P2完全在窗口内，则显示

31、该线段P1P2简称“取”之。（2）若P1P2在裁剪边界的一侧，则丢弃该线段，简称“弃”之。（3）若线段既不满足“取”的条件，也不满足“弃”的条件，则在交点处把线段分为两段。其中一段完全在窗口外，可弃之。然后对另一段重复上述处理。 为使计算机能够快速判断一条直线段与窗口属何种关系，采用如下编码方法。窗口的四条边把整个平面分成九个区域，每一个区域采用四位编码表示：(1)在x=xL左侧的区域,编码的第四位是1；(2)在x=xR右侧的区域,编码的第三位是1； (3)在y=yB下侧的区域,编码的第二位是1；(4)在y=yT上侧的区域,编码的第一位是1。11、写出从裁剪窗口映射到规范化视口的变换矩阵。其中

32、裁剪窗口和视口的左下角坐标分别为(xwmin,ywmin) 和(xvmin,yvmin)，右上角坐标分别为(xwmax,ywmax) 和 (xvmax,yvmax)。（1）把裁剪窗口的中心移到原点（2）把裁剪窗口以原点为固定点进行缩放，缩放到和视口大小一致（3）把裁剪窗口的中心（原点）移到视口的左下角总的变换矩阵为 12、根据下列参数，写出从世界坐标系到观察坐标系的变换矩阵。(1) 观察原点 P0 (2,1,2)(2) 参考点 Pref(1,0,2), 观察平面法向量 N的方向为Pref 指向P0(3) 观察向上向量V(0,1,0)13、设投影中心为点O（0，0，0），投影平面为平行于平面XO

33、Z，且y6。请写出此透视投影变换矩阵，并求端点A（4，12，6）和C（6，9，15）的直线段AC在该投影平面的投影。投影变换矩阵：端点A的投影A：，即(2,6,3)端点C的投影C： ，即（4，6，10）直线段AC在该投影平面的投影为由端点A和端点C决定的直线段14、写出裁剪窗口映射到规范化正方形的变换矩阵，其中裁剪窗口的左下角和右上角坐标分别为(xwmin,ywmin) 和 (xwmax,ywmax)，规范化正方形x,y范围为-1,1。（1）把裁剪窗口的中心平移到原点（2）以原点为固定点进行缩放，缩放到和正方形大小一致总的变换矩阵为15、写出绕指定轴逆时针旋转q的变换矩阵。其中，由P1(1,2

34、,3) 和P2(4,6,8)确定旋转轴，且沿着从P2到P1的轴进行观察。16、将点P1(3,6) 绕基准点Pr(5,7)顺时针旋转60度。写出变换矩阵，并计算点P1旋转后的坐标。第六章 自由曲线1. 世界坐标系与局部坐标系的适用范围，以及相关的坐标变换的OPENGL函数世界坐标系适用几何场景，由许多物体组成 ；局部坐标系使几何物体的表示最简单，便于进行几何操作 glPushMatrix(); 当前状态矩阵入栈glPopMatrix(); 状态矩阵出栈glTranslatef(0.0f, 0.5f, 0.0f); 平移glRotatef(90, 0.0f, 1.0f, 0.0f); 旋转glScalef(0.5,0.5,0.5);