本科生图形学试卷(此卷以算法为主)

第1页共4页一、(12分，每小题4分)简述题1.简述CRT显示器工作原理，并说明帧缓冲区与显示器分辨率间的关系。2.选做一题：a)简述汉字库的数据保存形式及用途。b)图形学算法在3DAMX或其它图形软件中的应用。3.举例说明三种图形输入输出设备及其用途。评分标准：每选4分，未选或选错均扣分。二、(8分)判断题（请在后面括号中打√或×）：1.若帧缓冲区大小一定，则屏幕分辨率与最大颜色数成正比。(×)2.许多图形算法可由硬件实现，而硬件图形算法不可由软件实现。(×)3.k阶B样条曲线随着控制顶点的增加，会导致曲线次数的增加。(×)4.汉字显示点阵字库与打印点阵字库是一样的。(×)5.齐次坐标系不可以表示坐标轴的无穷远点。(×)6.二平行直线经线性变换后仍然平行。(√)7.Bezier曲线和均匀结点B样条曲线都具有对称性。(√)8.单凸多面体的消隐只要判断面的外法向与视线的夹角关系即可。(√)评分标准：每选1分（第1题2分），未选或选错均扣分。三、(10分)直线点生成的中点算法(条件为x1-x0y1-y00)1、推导直线点生成中点算法；（3分）2、算法描述直线的点生成的中点算法；（7分）1、推导：直线段方程：F(x,y)=ax+by+c，其中：a=y0-y1，b=x1-x0，c=;初值为（x0,y0）,终止条件为x=x1;此时，x递增，y递减，且有x1-x0=y1-y0=0，故有：xi+1=xi+1;yi+1=yi+1或yi+1=yi；中点算法判别式：d=F(M)=F(x+1,y+0.5)当di=0,yi+1=yi+1；当di0,yi+1=yi；⊿d=di+1-di=F(xi+1+1,yi+1-0.5)-F(xi+1,yi-0.5)=a*(xi+1+1)+b*(yi+1+0.5)+c-[a*(xi+1)+b*(yi+0.5)+c]=a+b当di=0,yi+1=yi+1；=a当di0,yi+1=yi；为了保持整数运算，将d*2，有：初值：x=x0;y=y0;d=b+2*a;⊿d=di+1-di=F(xi+1+1,yi+1-0.5)-F(xi+1,yi-0.5)=2*a+2*b当di=0,yi+1=yi+1；=2*a当di0,yi+1=yi；推毕。评分标准：推导共3分a)列出中点算法判别式,得1分。b)推导中点算法递推式,得2分。c)扣分视完整性定。2）、算法描述：1、置初值：x=x0;y=y0;d=a+2*b;画(x,y)2、终止条件：while(xx1)3、递推：{if(d=0){d=d+2*(a-b);y=y+1;}elsed=d+2*a;x=x+1;4、画点：(x,y);}评分标准：a)算法描述共7分。初始条件：2分，递推式3分，中止条件1分，画1分。b)画圆改圆填色2分。c)扣分视完整性定。四、线段裁剪算法(14分)Cohen-Sutherland窗口裁剪算法，当取编码顺序为（Ｃt,Ｃr,Ｃb,Ｃl）时：1、给出线段GH二端点的相应编码0010、0100；(1分)2、(4分)当满足条件：C1=C2=0000，线段完全可见；下列线段中有：EF当满足条件：C1&C2≠0000，线段完全不可见；下列线段中有：KL、AB3、给出判断可能部分可见线段的Liang-Barsky或Cohen-Sutherland算法的算法描述；(6分)4、根据上述算法图示计算线段CD的可见部分计算过程，给出判断结论。(3分)第2页共4页ＪＫＤＬAF0100ＥＨＣB0010ＧＩ解答：1、答案见上。评分标准：共1分，有一标错扣1分。2、答案见上述第2题填空部分。评分标准：共4分，每空格1分第四空，标AB或KL，或二者均得分，多标GH不扣分。3、答案为算法分二步：第一步：先编码判断完全可线段和完成不可见线段求出各线段的二端点的编码C1、C2；若C1=C2=0000，线段完全可见；若C1&C2≠0000，线段完全不可见；否则，第二步求不可见部分时，可选以下三种算法之一：a)Cohen-Sutherland算法：1）对二端点编码中为1的边，直接计算直线与该边交点，求可见部分；2）余下的可见部分重复1），直到所有编码为1的求可见部分结束。3）最后余下部分为可见部分。b)Liang-Barsky算法：1）求线段与窗口上、下平行线的交点，记为（t0,t1）;2）求线段与窗口左、右平行线的交点，记为（tt0,tt1）;3）可见线段部分为：[t’,t”]，其中，t’=max{0,t0,tt0},t”=min{1,t1,tt1}且t’t”。评分标准：共6分1）第一步未做，扣2分；计算交线部分4分。2）Liang-Barsky算法中若未注明t’t”，扣1分；3）a)和c)算法中，未提所有编码为1的，扣1分。4）叙述不准确或有误，视情扣分。4、根据描述的算法给出相应的图示。评分标准：共3分结果错扣2分，图示不正确或有误，视情扣分。五、(16分)Bezier曲线与B样条曲线：1、B样条的非均匀周期性结点向量（t0,t1,…,tn,…,tn+k）的取法中有二个特例：（4分）当结点向量为0,0,1,2,3,…,n,n时,特例为控制多边形;当结点向量为0,0,0,0,1,1,1,…1时,特例为Bezier曲线;2、算法描述二次B样条曲线的生成算法；或算法描述Bezier曲线的递归分裂作图算法。（二选一，6分）A．二次B样条算法简述：分n-2段，每段细分count段直线段。参数：P[i]—控制顶点坐标，n—顶点数，count—直线段数MoveTo((p[0]+p[1])/2);for(i=0;i=n-2;i++)//画n-2段{for(j=1;j=count;j++)//画一段{t=j/count;q=((t*t-2*t+1)*p[i].x+(-2*t*t+2*t+1)*p[i+1]+t*t*p[i+2])/2;LineTo(q);}}B．算法简述：经一次分割算法，原Pi分割为二段Bezier曲线。参数：Pi—控制顶点坐标，n—顶点数，k—递归次数#defineMAX50voidSplitBezier(floatp[][2],intn,intk){floatq[MAX][2];inti,j;for(i=0;i=n;i++){q[i][0]=p[0][0];q[i][1]=p[0][1];for(j=0;jn-i;j++){p[i][0]=(p[i][0]+p[i+1][0])/2;p[i][1]=(p[i][1]+p[i+1][1])/2;}}if(k0){k--;SplitBezier(p,n,k);SplitBezier(p,n,k);}else{DrawBezier(p,n);DrawBezier(p,n);}}voidDrawBezier(floatp[][2],intn){moveto(p[0][0],p[0][1]);for(inti=0;i=n;i++)lineto([i][0],p[i][1]);}评分标准：共5分扣分视完整性定。P4第3页共4页3、给出下列控制多边形，请分别画出Bezier曲线、二次B样条曲线、三次B样条曲线，并标出端点切向量。控制多边形如下：(6分)评分标准：共6分要求：草图要求基本符合三种曲线的端点性质.a)三条曲线,每条2分；b)未标矢量，分别各扣1分。六、线填色算法：(10分)1、算法描述栏栅求余线填色算法；（6分）2、根据下图多边形,图示栏栅求余线填色算法过程。（4分）P0P1P2P5P4P3算法描述：（栅栏填空算法）参数：多边形顶点坐标P[i]，多边形点数n，color—填空色1.取多边形任一顶点，记为（X,Y）作垂直栅栏；2.遍历多边形所有边;3.{遍历边上所有点；{从此点至垂直栅栏，判断各点；若为已画点：则取销该点，否则画该点，即求余；｝评分标准：算法部分为6分，扣分视完整性定。算法部分为4分，扣分视完整性定。七、(每小题5分)二维图形变换：(写出相应每步的加边矩阵)1.在二维坐标Oxy中，求关于对称轴y=22x的对称变换。2．求对于下面左图变换到右图变换矩阵。Ｄ(0,1)Ｄ’(1,2)C’(2,2)P4P5P6P1P2P3P0(4)(6)第4页共4页A(-1,0)C(1,0)A’(0,0)B’(1,0)B(0,-1)评分标准：每一小题各5分扣分视完整性定。八、(每小题5分)三维图形变换：(写出相应每步的加边矩阵)1．整体放大1/2倍，再透视投影到Y-Z平面，视点为(0,10,0)，视线为Y轴。2．以点P(3,-1,2)为中心的X、Y、Z向分别缩放2、-3、1/4倍，并投影到Y-Z平面。评分标准：每一小题各5分扣分视完整性定。九、(10分)算法描述Z缓冲区面消隐算法（深度缓冲区算法），并逐步图示下面图形的面消隐过程。1、算法描述：a)对图形进行平行投影或透视投影变换用数组Z-Buffer(,x,y)保存当前填色点的最大Z值;Color(x,y)保存当前颜色值;b)数组初始化:Z-Buffer(x,y)=Zmin;Color(x,y)=背景色;c)遍历所有多边形面(次序无关){判断面法向量与视线夹角，若为锐角，则不可见；若为钝角，则为可见。if(面为可见){扫描转换该多边形;for(多边形中每个像素(x,y)){多边形中和每个像素的深度值z(x,y);if(z(x,y)Z-Buffer(x,y)){Z-Buffer(x,y)=z(x,y);Color(x,y)=(x,y)点的颜色;}]}评分标准：共8分a)部分未叙述，扣1分；b)部分不准确，扣2分；c)部分循环条件不准确，扣2分；d）循环体核心部分错误扣4分.