清华大学计算机系工程硕士图形学试题

清华大学计算机系图形学试题姓名：学号：单位：一、选择题(4分×5＝20分)1.Siggraph是ba.图形学的杂志b.图形学的组织及其会议c.图形学的标准d.图形学的某个算法2.中点法扫描转换以(1，1)，(6，3)为端点的直线段时，不经过下面哪个点c？a.(2,1)b.(3,2)c.(4,3)d.(5,3)3.六个控制顶点的三次B样条的节点向量应该由几个节点构成d？a.6b.8c.9d.104.Bernstein基函数)(tBni在何参数值处取极值c？a.0b.1c.nid.ni15.属于空间剖分技术的光线跟踪加速方法有：aca.三维DDAb.层次包围盒c.八叉树d.自适应深度控制二、简答题（5分×5题）1.列举三个以上图形学的应用领域？答：计算机辅助设计与制造、可视化、真实感图形实时绘制、自然景物仿真、计算机动画、用户接口、计算机艺术。2.参数曲线曲面有几种表示形式？答：代数形式和几何形式。3.在Phong模型nspdpaaVRKINLKIKII)()(中，三项分别表示何含义？公式中的各个符号的含义指什么？答：三项分别代表环境光、漫反射光和镜面反射光。aI为环境光的反射光强，pI为理想漫反射光强，aK为物体对环境光的反射系数，dK为漫反射系数，sK为镜面反射系数，n为高光指数，L为光线方向，N为法线方向，V为视线方向，R为光线的反射方向。4.依次写出用DDA画线法进行直线扫描转换，从点(5,5)到(20,10)经过的象素点，及给出每步计算步骤。10101/3yykxx55655.3765.7866966.31076.711771277.31387.714881588.31698.717991899.319109.72010105.什么叫反走样，并简述三种以上反走样方法的基本原理。答：在光栅显示器上显示图形时，直线段或图形边界或多或少会呈锯齿状。原因是图形信号是连续的，而在光栅显示系统中，用来表示图形的却是一个个离散的象素。这种用离散量表示连续量引起的失真现象称之为走样；用于减少或消除这种效果的技术称为反走样。反走样的方法有：提高分辨率、区域采样和加权区域采样。三（20分）、三次B样条曲线控制顶点为P0,P1，P2，P3，P4，坐标分别为（0，0），（100，100），（150，120），（200，100），（300，0），节点矢量T=(0,0,0,0,0.4,1,1,1,1)。1)计算曲线上一点21P的值（DeBoor递推算法见附录）。2)对曲线上一点21P，调整其中一个控制顶点P2，使21P精确通过点T＝（150，50），给出新的控制顶点P2。解：（1）使用deBoor递推公式有：4,4jk1000052221215252(0.50.5)(125,110)ttttPPPPPtttt1000036332326363(0.50.5)(175,110)ttttPPPPPtttt100007444343747415()(216.67,83.33)66ttttPPPPPtttt2111135332325353(0.50.5)(150,110)ttttPPPPPtttt211116444343646415()(181.94,91.67)66ttttPPPPPtttt3222254443435454115()()(155.324,106.96)266ttttPPPPPPtttt（2）新控制顶点222,411()()22TPPPN有222,4117()/()(150,120)(5.324,56.96)/()(131.75,75.29)2224PPTPN四（10分）、给出扫描线Z-Buffer消隐算法，并比较与传统Z-Buffer的消隐算法的区别。算法思想：在处理当前扫描线时，开一个一维数组作为当前扫描线的Z-buffer。首先找出与当前扫描线相关的多边形，以及每个多边形中相关的边对。对每一个边对之间的小区间上的各象素，计算深度，并与Z-buffer中的值比较，找出各象素处可见平面，计算颜色，写帧缓存。对深度计算，采用增量算法。算法过程：xl左侧边与扫描线交点的x坐标xl左侧边在扫描线加1时的x坐标增量ylmax左侧边两端点中最大的y值xr右侧边与扫描线交点的x坐标xr右侧边在扫描线加1时的x坐标增量yrmax右侧边两端点中最大的y值zl左侧边与扫描线交点处的多边形深度值IP多边形序号za当沿扫描线方向增加1个象素时，多边形所在平面的z坐标增量，为－a/czb扫描线加1时，多边形所在平面的z坐标增量，为－b/c扫描线Z-buffer算法(){建多边形y表；对每一个多边形根据顶点最小的y值，将多边形置入多边形y表。活化多边形表APT，活化边表AET初始化为空。For(每条扫描线i，i从小到大){1.帧缓存CB置为背景色。2.深度缓存ZB(一维数组)置为负无穷大。3.将对应扫描线i的，多边形y表中的多边形加入到活化多边形表APT中。4.对新加入的多边形，生成其相应的边Y表。5.对APT中每一个多边形，若其边Y表中对应扫描线I增加了新的边，将新的边配对，加到活化边对表AET中。6.对AET中的每一对边：6.1对xlxxr的每一个象素，按增量公式z=z＋za计算各点深度depth。6.2与ZB中的量比较，depthZB(I),则令ZB(I)=depth，并计算颜色值，写帧缓存。7.删除APT中，多边形顶点最大y坐标为I的多边形，并删除相应的边。8.对AET中的每一个边对，作如下处理：8.1删除ylmax或ylmax已等于I的边。若一边对中只删除了其中一边，需对该多边形的边重新配对。8.2用增量公式计算新的xl、xr和zl。xl＝xl＋xl、xr＝xr＋xr和zl＝zl＋xlza+zb}}比较：与Z－buffer算法相比，扫描线Z－buffer算法做了两点改进。一、将整个绘图窗口内的消隐问题分解到一条条扫描线上解决，使所需的Z缓冲器大大减少。二、计算深度值时，利用了面连贯性，只用了一个加法。但它在每个象素处都计算深度值，进行深度比较。因此，被多个多边形覆盖的象素区处还要进行多次计算，计算量仍然很大。五（10分）、给定多项式niiita0，试将其表示为Bernstein基函数的形式？即给出显式表达的系数ib，使niniiniiitBbta00)(解：n0iin0jjinjijinin0iin0jjinjjiniin0iiniin0iiit1tCat1tCtat1ttata)()(令kji，则上式可表示为：n0inikknkknknikinit1tCCCa)(n0inikknkknit1tCnikkina)(!)!(!)!(n0kk0iknkknit1tCnikkina)(!)!(!)!(将指标i,k调换，并与n0iniitBb)(比较可得：ikiinkiiknab0!)!(!)!(六（15分）、(1)写出光线跟踪算法的基本过程。（2）在光线跟踪的递归程序中，递归终止条件有哪几种？（3）描述3维DDA算法的原理。解：（1）算法从视点出发，通过图像平面上每一点像素中心向场景发出一条光线，若光线与场景中景物无交，则光线将射出画面，跟踪结束。否则，光线与景物有交。此时，光线在离视点最近的景物表面交点处的走向有以下三种可能：1）当前交点所在的景物表面为理想漫射面，跟踪结束。2）当前所在的景物表面为理想镜面，光线沿其镜面反射方向继续跟踪。3）当前交点所在的景物表面为规则透射面，光线沿其规则透射方向继续跟踪。（2）光线跟踪算法可以有以下的几种终止条件：1.该光线未碰到任何物体。2.该光线碰到了背景。3.光线在经过许多次反射和折射以后，就会产生衰减，光线对于视点的光强贡献很小（小于某个设定值）。4.光线反射或折射次数即跟踪深度大于一定值。(3)将景物空间均匀分割成为一系列均匀的3维网格，每一个网格均记录其所含景物面片的数据。光线跟踪时，光线只须依次与其所经过的空间网格中所含的景物面片进行求交测试。光线的三维网格跨越算法是利用了直线光栅化的DDA算法直接推广到三维，所以称为三维DDA算法。（下面是具体算法说明，不要求）设光线的方向向量为),,(zyxVVVV，我们先求出被跟踪光线的主轴方向d，是：),,max(zyxdVVVV。设其他两个坐标方向为i和j，那么三维DDA网格跨越过程，可分解为两个二维DDA过程。算法首先将光线垂直投影到交于主轴的两个坐标平面上，然后对两投影线分别执行二维DDA算法。附：k阶B样条曲线求值的deBoor算法：[][1][1]1,0,1,2,,()()(),1,2,,1;1,2,,irrriikriiiikriikriPrijkjkjttttPtPtPtttttrkijkrjkrj