计算机图形学-习题库全解.doc

3、画直线的算法有哪几种？画圆弧的算法有哪几种？c1）逐点比较法；（2）数值微分法；（3）Bresenham算法。画弧线的常用方法有：（1）逐点比较法；（2）角度DDA法；（3）Bresenham算法。4、分别写出平移、旋转、缩放及其组合的变换矩阵。1）平移变换：其中， , , 是物体在三个坐标方向上的位移量。2）旋转变换：绕Z轴旋转的公式为：绕X轴旋转的公式为：绕Y轴旋转的公式为：如果旋转所绕的轴不是坐标轴，设其为任意两点p1,p2所定义的矢量，旋转角度为 。则可由7个基本变换组合构成：1 使p1,点与原点重合；2 ，使轴p1p2落入平面xoz内；3 ，使p1p2与z轴重合；4 ，执行绕p1p2轴的 角旋转；5，作3的逆变换；6 ，作2的逆变换；7 作1的逆变换。3）缩放变换：其中， ， ， 是物体在三个方向上的比例变化量。记为 。若对于某个非原点参考点 进行固定点缩放变换，则通过如下的级联变换实现：5、如何用几何变换实现坐标系的变换？坐标系的变换，亦即将某一坐标系lcs1中的点 变换为另一个坐标系lcs2下的坐标 。若 ， 矩阵的推导分三步。1）将lcs1中的点变换到世界坐标系的矩阵 ;x_axis, y_axis, z_axis 为lcs1中x,y,z轴矢量在世界坐标系的表示org为lcs1中原点在世界坐标系的表示2）将世界坐标系的点变换到lcs2中的点矩阵 ;x_axis, y_axis, z_axis 为lcs1中x,y,z轴矢量在世界坐标系的表示org为lcs1中原点在世界坐标系的表示a = - x_axis.x * org.x - x_axis.y * org.y - x_axis.z * org.zb = - y_axis.x * org.x - y_axis.y * org.y - y_axis.z * org.zc = - z_axis.x * org.x - z_axis.y * org.y - z_axis.z * org.z6、写出几种线裁剪算法；写出几种多边形裁剪算法。（1）、矢量裁剪法（2）、编码裁剪法（3）、中点分割裁剪法多边形的裁剪算法：（1）、逐边裁剪法（2）、双边裁剪法7、写出Bezier曲线和面片的几种表达形式。空间给定的n+1个点 ，称下列参数曲线为n次的Bezier曲线。其中 是Bernstein基函数，即 i = 0,1,n空间给定的(n+1)*(m+1)个点 为曲面片的控制顶点（i = 0,1,n; j = 0,1,m）,则下列张量积形式的参数曲面为 次的Bezier曲面：Bezier曲面齐次坐标形式为：其中 为Bernstein多项式。8、写出B样条的矩阵形式和调和函数。为什么使用非均匀有理B样条？n+1个控制点 ,K阶（K-1次）B样条曲线的表达式是：其中 是调和函数，按照递归公式可定义为：其中 是节点值， 是K阶B样条函数的节点矢量。非均匀B样条函数的节点参数沿参数轴的分布是不等距的，近年来，它得到了广泛的发展和应用，主要原因是：（1） 对标准的解析形状（如圆锥曲线，二次曲线，回转面等）和自由曲线，曲面提供了统一的数学表示，无论是解析形状还是自由格式的形状均有统一的表示参数，便于工程数据库的存取和应用。（2） 可通过控制点和权因子来灵活的改变形状。3） 对插入节点，修改，分割，几何插值等的处理工具比较有利。（4） 具有透视投影变换和仿射变换的不变性。（5） 非有理B样条，有理及非有理Bezier曲线，曲面是NURBS的特例表示。9、简述边界表示法（BREP）实体构造表示法（CSG）。边界表示法是用实体的表面来表示实体的形状，它的基本元素是面、边、顶点。它以欧拉公式作为理论基础，要求实体的基本拓扑结构符合欧拉公式。目前采用的比较多的数据结构是翼边数据结构和半边数据结构（又称对称数据结构）。实体构造表示法的基本思想是将简单的实体（又称体素）通过集合运算组成所需要的物体。其中，集合运算的实现过程由一棵二叉树来描述，二叉树的叶子节点表示体素或者几何变换的参数，非终端节点表示施加于其子结点的正则集合算子或几何变换的定义。10、写出透视变换矩阵和各种投影（三视图、正轴测和斜投影）变换矩阵。透视变换矩阵形式为： 主视图： 俯视图： 侧视图： 正轴测： 斜投影：11、观察空间有哪些参数？其作用是什么？写出从物体空间坐标系到观察空间坐标系转换矩阵。参数 名称 作用 VRP 观察参考点 确定观察坐标系原点 VPN 观察平面法向 确定观察平面法向 VUP 观察正向 确定观察平面上v轴的方向 F 前截面距离 确定前截面位置 B 后截面距离 确定后截面位置 Pt 投影类型 定义投影是平行投影还是透视投影 PRP 投影参考点 确定投影中心或投影方向 Umin,Umax,Vmin,Vmax 观察窗口 在观察平面上定义观察窗口 从物体空间坐标系到观察空间坐标系的转换矩阵：12、分别写出对于透视投影和平行投影的从裁剪空间到规范化投影空间的转换矩阵。平行投影：Tvcper=T3T4T5parT6par透视投影：Tvcper=T3T4T5per13、写出从规范化投影空间到图像空间的转换矩阵。14、写出光线与几种常见物体面的求交算法。假设光线射线定义为X=Dt+E (t=0)其中，E=(e1,e2,e3)为射线起点，D=(d1,d2,d3)为射线方向，|D| = 1，X=(x,y,z)为射线上任意点。1）与多边形求交算法假设多边形所在的平面方程为ax+by+cz+d = 0把射线参数方程代入平面方程得到：t0 = - (N * K + d) / (N * D) (N*D0)当N*D = 0时，射线和多边形平行；当N*D0，交点为X0 = Dt0 + E。这时，还要判断交点是否在多边形上。判断时，只要把交点和多边形投影到某个坐标平面上判断即可。2）与球面求交算法设球心在P0(x0,y0,z0)，半径为r的球面方程为(P P0) * (P P0) = r * r代入射线方程，有at*t + bt + c = 0其中a = D*D，b = 2D *(E-P0)，c = (E-P0) * (E-P0) r * r当b*b-4ac0时，无交点。否则，射线与球面交于两点，由求根公式可以求出。3）与柱面求交算法一个底面中心为P0，对称轴方向为AXIS，半径为r，高为h的圆柱定义如下：(P P0) * (P- P0) (AXIS * (P P0) * (AXIS * (P P0) r * r = 0AXIS * (P P0) = 0时，可以由求根公式求出解。求出t以后，还要看是否满足后面两个不等式，才能决定是否在圆柱面上。15简述消隐算法的分类。根据消隐空间的不同，消隐算法可分为两类：（1）物体空间的消隐算法：物体空间是物体所在的空间，即规范化投影空间。这类算法是将物体表面上的K个多边形中的每一个面与其余的K-1个面进行比较，精确求出物体上每条边或每个面的遮挡关系。计算量正比于K2。（2）图象空间的消隐算法：图象空间就是屏幕坐标空间，这类算法对屏幕的每一象素进行判断，以决定物体上哪个多边形在该象素点上是可见的。若屏幕上有mn个象素点，物体表面上有K个多边形，则该类消隐算法计算量正比于mnk。16、简述深度缓存算法及其特点。深度缓存算法是一种典型的、也是最简单的图象空间的消隐算法。在屏幕空间坐标系中， 轴为观察方向，通过比较平行于 轴的射线与物体表面交点的 值（又称为深度值），用深度缓存数组记录下最小的 值，并将对应点的颜色存入显示器的帧缓存。深度缓存算法最大的优点是简单。它在 、 、 方向上都没有进行任何排序，也没有利用任何相关性。算法复杂性正比于 。在屏幕大小，即 一定的情况下，算法的计算量只与多边形个数 成正比。另一个优点是算法便于硬件实现，并可以并行化。17、简述点与多边形之间的包含性检测算法。先将该点变换到多边形所在平面，在二维空间讨论该问题，过该点沿任意方向做一条射线，与多边形边界求交点，若交点个数为偶数，0，2，4，则该点在多边形外部，否则在内部。如果射线与多边形某条边、某个顶点重合，则可以改变射线方向重新测试。18、描述扫描线算法。扫描线算法如下：（1）对于每个多边形，根据多边形顶点的最小的y值，将多边形置入多边形Y桶。（2）有效多边形表APT初始化为空，有效边表初始化为空。（3）对每一条扫描线j，j从最小值1开始，做以下工作： 颜色缓存CB置为背景色。 深度缓存ZB置为机器无穷大。 检查多边形Y桶中对应扫描线j的链中是否有新的多边形。如有，则将新多边形加到有效多边形表APT中。 对于新添到有效多边形表中的多边形，生成对应的边Y桶。 对于有效多边形表APT中的每一个多边形，若其边Y桶中对应扫描线j有新的边，则将新边配对加入到有效边表AET中。 对于有效边表AET中的第一个边对，计算起止x坐标间点的z值，与ZB中对应值比较，若小，在更新ZB的值，并将该点颜色值存入CB。 将CB的内容写入显示器帧缓存的第j行。 检查有效多边形表APT中的个多边形，若多边形顶点的最大Y坐标已等于j，则从APT中删去多边形，释放对应的边Y桶的空间，并从有效边表AET中删去属于该多边形的所有边对。 检查有效边表AET的每一边对，调整相应的起止x坐标，和z值。19、简述几种阴影生成算法。阴影生成算法主要分为如下几种：影域多边形方法：由于物体遮挡光源后在它们后面形成一个影域，所以确定某点是否落在阴影中只要判别该点是否位于影域即可。曲面细节多边形方法：基于多边形区域分类的隐藏面消去算法，通过从光源和视点两次消隐生成阴影。z缓冲器方法：该方法分为两部。首先，利用z缓冲器消隐算法按光源方向对景物进行消隐。在z缓冲器（阴影缓冲器）中记录离光源最近景物点的深度值。第二部，采用z缓冲器消隐算法按视线方向计算画面。将每一象素对应点变换到光源坐标系，并用变换后点的深度值与阴影缓冲器中的深度值比较，若阴影缓冲器中的深度值较小，则说明该点从光源方向不可见，位于阴影中。光线跟踪方法：在光线跟踪算法中，要确定某点是否在某个光源的阴影内，只要从该点出发向光源发出一根测试光线即可。若测试光线在到达给定光源前，先与其它景物相交，在该点位于给定光源的阴影中，否则受到该光源的直接照射。20、试描述您所熟悉的计算机图形系统的硬软件环境。计算机图形系统是计算机硬件、图形输入输出设备、计算机系统软件和图形软件的集合。例如：计算机硬件采用PC、操作系统采用windows2000，图形输入设备有键盘、鼠标、光笔、触摸屏等，图形输出设备有CRT、LCD等，安装3D MAX图形软件。21、图形硬件设备主要包括哪些？请按类别举出典型的物理设备?图形输入设备：鼠标、光笔、触摸屏和坐标数字化仪，以及图形扫描仪等。图形显示设备：CRT、液晶显示器（LCD）等。图形绘制设备：打印机、绘图仪等。图形处理器：GPU（图形处理单元）、图形加速卡等等。22、为什么要制定图形软件标准？可分为哪两类？为了提高计算机图形软件、计算机图形的应用软件以及相关软件的编程人员在不同计算机和图形设备之间的可移植性。图形软件标准通常是指图形系统及其相关应用系统中各界面之间进行数据传送和通信的接口标准，另外还有供图形应用程序调用的子程序功能及其格式标准。23、请列举出当前已成为国际标准的几种图形软件标准，并简述其主要功能。（1）CGI(Computer Graphics Interface)，它所提供的主要功能集包括控制功能集、独立于设备的图形对象输出功能集、图段功能集、输入和应答功能集以及产生、修改、检索和显示以像素数据形式存储的光栅功能集。（2）GKS(Graphcis Kernel System)，提供了应用程序和图形输入输出设备之间的接口，包括一系列交互和非交互式图形设备的全部图形处理功能。主要功能如下：控制功能、输入输出功能、变换功能、图段功能、询问功能等。24、试列举计算机图形学的三个应用实例。（1） CAD/CAM（2） VISC（3） VR.25、在图形设备上如何输出一个点？为输出一条任意斜率的直线，一般受到哪些因素影响？若图形设备是光栅图形显示器，光栅图形显示器可以看作是一个像素的矩阵，光栅图形显示器上的点是像素点的集合。在光栅图形显示器上输出一条任意斜率的直线，主要受到以下因素的影响：（1）光栅图形显示器的分辨率；2）线宽、线型；（3）直线的扫描转换的算法。28、在齐次坐标系中，写出下列变换矩阵：（a） 整个图象放大2倍；（b） y向放大4倍和x向放大3倍；（c） 图象上移10个单位和右移5个单位（d） 保持x=5和y=10 图形点固定，图象y向放大2倍和x向放大3倍；e） 图象绕坐标原点顺时针方向转/2;f） 图象绕点x=2和y=5反时针方向转/4。（a） 整个图象放大2倍；（b） y向放大4倍和x向放大3倍；（c） 图象上移10个单位和右移5个单位；（d） 保持x=5和y=10 图形点固定，图象y向放大2倍和x向放大3倍；(1) 将坐标系平移到点（5，10） T1 =(2) 将图象y向放大2倍和x向放大3倍S =(3) 平移坐标系至（-5，-10）点T2 =T = T2 ST1 =（e） 图象绕坐标原点顺时针方向转/2;R =（f） 图象绕点x=2和y=5反时针方向转/4。(1) 将坐标系平移到点（2，5）；T1 =(2) 将图象绕原点反时针方向转/4；R =(3) 将坐标系平移到点（-2，-5）；T2 =T = T2 RT1 =29、由比例、平移和旋转变换构成的复合变换，仅在某些情况下交换次序不影响总的变换效果，它们是哪几种两个变换的组合。（1） 两个连续的平移变换；（2） 两个连续的比例变换；（3） 两个连续的旋转变换；（4） 比例系数相等的比例变换和旋转变换。38、光栅扫描显示器由哪些部分组成？它们功能分别是什么？简述之。光栅扫描式显示器主要由五个部分组成，（1）显示存储器：它是整个显示器的核心，存放着在屏幕上显示图形的映像（Image）。（2）图像生成器：它的作用是把计算机送来的画线、画短形、画填充区域或写字符等基本画图命令扫描转换成为相应的点阵（称位图），存放在显示存储器中，即存放着需要在荧光屏上显示出来的图形的映像。（3）彩色表：平衡显示存储器不能过大而又尽量满足实际需要。（4）CRT控制器：CRT控制器的作用是一方面使电子束不断地自上而下、自左面右进行屏幕扫描，形成光栅（Raster），产生水平和垂直同步信号送往CRT；另一方面又不断地读取存放在显示存储器的位图数据，作为RGB信号或辉亮信号送往CRT。（5） CRT监视器：CRT监视器是由阴极射线管和有关附加电路（如扫描偏转电路、视频放大电路等组成。类似电视机屏幕，供显示图形用。39、简述编码裁剪法（即Cohen-Sutherland线段裁剪法）的算法过程。由Dan Cohen和Ivan Sutherland提出的区域编码判断方法，采用四位数码来标识线段的端点与窗口区域的关系，然后：（1）检查线段P1P2是否为完全可见，或完全不可见，对于这两种情况或完全取之，或完全弃之，否则 “2”。（2）找到P1P2在窗口外的一个端点P1（或P2）；（3）用窗口的边与P1P2的交点取代端点P1（或P2）；（4）P1P2线段是否完全可见，若是，则结束，否则转到“2“继续执行。40、试述单个凸多面体消隐的基本方法。定义垂直于物体平面且背离物体的直线向量为平面法线向量，定义从视点到物体表面上任一点直线方向为视线向量方向，那么利用这两个矢量之间夹角可以进行背面测试，只有当两个矢量之间夹角小于90O时面为可见面。42、简述在C语言图形程序设计过程中制作动画都可以采取哪些方法？（1）全局画擦画：cleardevice( )（2）局部画擦画：getimage( ) putimage( )（3）页切换：setactivepage( ) setvisualpage( )（4）延时: delay( )（5）函数式（6）图形变换2、写一个画饼分图的程序，用不同的颜色填充各个区域。Draw_pie(int x, int y,float radius ,float *percent) float seed_x,seed_y; int color,i; color=0; float angle=0; draw_circle(x,y,radius); draw_line(x,y,x+radius,y); for(i=0;percenti=0;i+) seed_x=x+radius*cos(angle+PI*percenti/100);seed_y=y+radius*sin(angle+PI*percenti/100);/*在新的扇区中间找一个种子点作为填色之用*/angle=angle+2*PI*percenti/100; draw_line(x,y,x+radius*cos(),y+radius*sin(); seed_filling(seed_x,seed_y,color+,BACKGROUND_COLOR); 8、若窗口函数在定义为平行于用户坐标轴的直立矩形后，还允许此窗口再绕左下角旋转角，写出由旋转后窗口到直立矩形视见区的变换矩阵。假设窗口左下角坐标为（xw1,yw1），右上角坐标为（xw2,yw2）（1） 平移直立矩形视见区的左下角顶点到坐标原点；T1 =（2） 将此窗口再绕左下角逆时针旋转角。R =M-1 = RT1M =9、下面是依次序给出的多边形顶点坐标，请指出哪些是凸多边形？你是如何判断的？(a) （2，3），（7，2），（10，6），（8，11），（3，8）；(b) （1，4），（4，1），（8，3），（8，8），（5，5）；(c) （4，4），（5，1），（7，4），（5，8），（2，4）；(d) （3，8），（7，10），（8，6），（9，2），（3，2）。对凸多边形求出向内法矢量。(a) （2，3），（7，2），（10，6），（8，11），（3，8）；凸多边形；内法向量依次为（-1,-5）, （4,-3）, （5,2）, （-3,5）, （-5,1）(b) （1，4），（4，1），（8，3），（8，8），（5，5）；(c) （4，4），（5，1），（7，4），（5，8），（2，4）；(d) （3，8），（7，10），（8，6），（9，2），（3，2）。(b) (c) (d) 均不是凸多边形。10、对上题中的一个凸多边形求出下列线段经剪取后的端点坐标。 (a) p1 =（3，4），p2 =（7，7）；(b) p1 =（1，4），p2 =（3，14）；(c) p1 =（1，12），p2 =（8，12）；(d) p1 =（13，1），p2 =（6，5）。(a) p1 =（3，4），p2 =（7，7）；在凸多边形内(b) p1 =（1，4），p2 =（3，14）；在凸多边形外(c) p1 =（1，12），p2 =（8，12）；在凸多边形外(d) p1 =（13，1），p2 =（6，5）。(8.275,3.7) 和 (6,5)11、在三维空间中，如果要求沿方向A,B,C产生放大到S倍的图形，推导出变换矩阵。A、B和C分别表示直线在x,y和z轴方向的余弦。(i) 将OP逆时针绕X轴旋转a角，使得OP落在XOZ面上；T1 =(ii) 将OP顺时针绕Y轴旋转b角, 使得OP与Z轴重合；T2 =(iii) 在Z轴上放大S =(iv) 将OP逆时针绕Y轴旋转b角=(v) 将OP顺时针绕X轴旋转a角=cos = sin=cos = sin = AM = S T2 T112、 对于下列变换写出它们的齐次坐标变换矩阵(a) 将x和y放大为原来的三倍，且图形点（0.5，0.2，0.2）保持不动；(b) 绕过点（0，0，1）和点（1，1，1）的直线旋转/4；(c) 产生对原点对称的图形；(d) 产生对3平面对称的图形。对于下列变换写出它们的齐次坐标变换矩阵(a) 将x和y放大为原来的三倍，且图形点（0.5，0.2，0.2）保持不动；T1 = S = T1 =T = T2 S T1 =(b) 绕过点（0，0，1）和点（1，1，1）的直线旋转/4；(i) 平移点（0，0，1）到原点T1 =(ii) 将直线绕X轴逆时针旋转角度T2 =cos = 2 /5, sin = /5(iii) 将直线绕Y轴顺时针旋转角度T3 =cos = /6, sin = /6(iv) 将直线绕Z轴逆时针旋转p/4T4 =(v) 将直线绕Y轴逆时针旋转角度T5 =(vi) 将直线绕X轴顺时针旋转角度T6 =(vii)T7 =M = T7T6T5T4T3T2T1(c) 产生对原点对称的图形；(d) 产生对3平面对称的图形。13、在右手坐标系中从原点到P（x,y,z）的直线，用下面三种次序都可以将此直线旋转到正的轴上。求出变换矩阵。这三个组合变换阵是否相同？(a) 绕x轴旋转到x-z平面上，再绕y轴旋转到z轴上；(b) 绕y轴旋转到y-z平面上，再绕x轴旋转到z轴上；(c) 绕z轴旋转到x-z平面上，再绕y轴旋转到z轴上。(a) 绕x轴旋转到x-z平面上，再绕y轴旋转到z轴上；(i) 绕x轴旋转到x-z平面T1 =(ii) 再绕y轴旋转到z轴T2 =M = T2 T1 =(b) 绕y轴旋转到y-z平面上，再绕x轴旋转到z轴上；(i) 绕y轴旋转到y-z平面上T1 =(ii) 再绕x轴旋转到z轴上T2 =(c) 绕z轴旋转到x-z平面上，再绕y轴旋转到z轴上。(i) 绕z轴旋转到x-z平面上T1 =(ii) 再绕y轴旋转到z轴上T2 =cos =a / sin = b /cos = , sin = c;17、推导以直线ax+by+c=0为对称轴的二维对称变换矩阵。令变换矩阵为T，则 。分下面2种情况加以讨论：（1） b=0这时应有a0（否则不合题意）,直线方程变为 ax+c=0，即x = -c/a，直线为平行于y轴的直线，变换过程可由下列步骤完成：a) 沿x轴，平移直线使之与y轴重合，平移量为c/a，变换矩阵为：b) 做关于y轴的对称变换，变换矩阵为：c) 沿x轴，平移直线，平移量为-c/a，变换矩阵为：这样，整个过程的变换矩阵为：T 。（2） b!=0这时直线变为y=(-a/b)x+(-c/b)，即直线的斜率为-a/b，直线的截距为-c/b，整个变换过程可分以下几个步骤完成：a) 沿y轴，平移直线使之通过原点，平移量为c/b，变换矩阵为：b) 绕原点旋转-（=arctg(-a/b)），使直线与x轴重合，变换矩阵为：c) 做关于x轴的对称变换，变换矩阵为：d) 绕原点回旋，变换矩阵为：e) 沿y轴，平移直线，平移量为-c/b，变换矩阵为：这样，整个过程的变换矩阵为： 。18、已知投影面为xoy坐标平面，投影中心在z轴的正向、z=d的位置上，求透视投影变换矩阵。如图所示，V是投影点，考虑到z为负值，由几何关系得：d /(d-z) = x / xx = d x/(d-z)同样 y = d y/(d-z)设投影矩阵为 P，则。根据上面的式子我们可以得到：20、给定方向（，），试推导沿这方向放大S倍的变换矩阵。分下列情况进行讨论：（1）=0，=0，=0，与题意不符合（2）=0，=0，！=0，即z轴，变换矩阵为：（3）=0，！=0，=0，即y轴，变换矩阵为：（4）!=0，=0，=0，即x轴，变换矩阵为：（5）!=0，！=0，=0，即方向在xoy平面上，设=arctg(/),整个变换过程可由下列步骤完成：a) 绕z轴正方向旋转-,使方向与x轴重合，变换矩阵为b) 沿x轴正方放大s倍,变换矩阵为c) 绕z轴正方向旋转,变换矩阵为这样，整个过程的变换矩阵为：T= 。（6）!=0，=0，！=0，即方向在xoz平面上，设=arctg(/),整个变换过程可由下列步骤完成：a)绕y轴正方向旋转-,使方向与z轴重合，变换矩阵为b)沿z轴正方放大s倍,变换矩阵为c)绕y轴正方向旋转,变换矩阵为这样，整个过程的变换矩阵为：T= 。（7）=0，！=0，!=0，即方向在yoz平面上，设=arctg(/),整个变换过程可由下列步骤完成：a)绕x轴正方向旋转-,使方向与y轴重合，变换矩阵为b)沿y轴正方放大s倍,变换矩阵为c)绕x轴正方向旋转,变换矩阵为这样，整个过程的变换矩阵为：T= 。（8）！=0，！=0，!=0，设=arctg(/),=arctg( )，整个变换