计算机图形学基础(第二版)部分习题答案

驭剑天下——收集整理华中科技大学计算机图形学课后习题指导一、第五章5.3试用中点Bresenham算法画直线段的原理推导斜率为负且大于1的直线段绘制过程（要求写清原理、误差函数、递推公式及最终画图过程）。分析：这是典型的算法推导题，推导时需要首先确定最大位移方向，然后根据最大位移方向确定候选点，并利用候选点的中点构造判别式；根据判别式确定选择候选点的条件，然后确定判别式的递推公式以及初值。解：驭剑天下——收集整理5.7利用中点Bresenham画圆算法的原理推导第一象限x＝y到y＝0圆弧段的扫描转换算法（要求写清原理、误差函数、递推公式及最终画图过程）。分析：这是典型的算法推导题，推导时需要首先确定最大位移方向，然后根据最大位移方向确定候选点，并利用候选点的中点构造判别式；根据判别式确定选择候选点的条件，然后确定判别式的递推公式以及初值。圆算法应该注意的是算法是从理想圆与坐标轴交点开始的。解：在x=y到y=0的圆弧中，（R,0）点比在圆弧上，算法从该点开始。最大位移方向为y，由（R,0）点开始，y渐增，x渐减，每次y方向加1，x方向减1或减0。（注意算法的起始点）设P点坐标（xi,yi）,下一个候选点为Pr（xi,yi+1）和Pl（xi－1,yi+1），取Pl和Pr的中点M（xi－0.5,yi+1），设理想圆与y=yi+1的交点Q，构造判别式：d=F(xM,yM)=(x－0.5)2+(y+1)2－R2当d0时，M在Q点左方，取Pr（xi,yi+1）；当d0时，M在Q点右方，取Pl（xi－1,yi+1）；当d＝0时，M与Q点重合，约定取Pl（xi－1,yi+1）。驭剑天下——收集整理5.11如图所示多边形，若采用扫描转换算法（ET边表算法）进行填充，试写出该多边形的ET表和当扫描线Y＝4时的有效边表（AET表，活性边表）。分析：改进的有效边表算法是用软件方法实现扫描转换效率较高的算法，它利用了边表来构造有效边表。需要注意的有以下几点：（1）构造边表时，水平边不需要构造，算法能够获取到水平边的两个端点，配对填充后水平边被填充，因此水平边的数据不参与计算。（2）边表中纵向链表的长度等于多边形覆盖的扫描线数，并且是从多边形覆盖的最低扫描线处开始。（3）边表与有效边表中每个结点的第三项为1/k；驭剑天下——收集整理（4）构造有效边表时，每个结点的第一项，即当前扫描线与多边形边交点处的x坐标不需要四舍五入，否则在计算下一条扫描线时可能会造成误差。解：ET表y＝4时的AET表5.12构造两个例子，一个是4－连通图，其边界是8－连通的，另一个是8－连通图，其边界是4－连通的。分析：由于八邻接点中包含四邻接点，所以四连通区域也可以看作八连通区域，但是四连通区域与八连通区域的边界条件是不同的，通常在边界表示的区域中，四连通区域边界（内环和外环边界）的连通性是八连通，而八连通区域边界（内环和外环边界）的连通性是四连通。在一些特殊的情况下一个区域的连通性可能既是四连通也是八连通，例如内点表示的四连通区域（内点表示没有显示的边界），或者将边界表示的四连通区域的所有边界（内环和外环边界）都改为四连通性质。解：驭剑天下——收集整理二、第六章6.7如图所示四边形ABCD，求绕P(5,4)点分别旋转45°的变换矩阵，并求出各端点坐标，画出变换后的图形。分析：对于变换的计算，重点在于分析变换的过程。一般来说，基于点的变换是将图形与点一起平移使点与原点重合，然后相对于原点变换，最后将点与图形一起平移使点回到原来的位置。解：变换的过程包括：（1）平移：将P点平移至原点，变换矩阵为：（2）旋转：图形绕原点（P点）旋转45度，变换矩阵为：（3）反平移：将P点移回原处，变换矩阵为：变换矩阵为：驭剑天下——收集整理变换过程为：6.11试用编码裁剪算法裁剪如图所示线段AB。分析：编码裁剪法的特点是能够快速的接受和拒绝可见和不可见的直线段，但是其求交的过程相对复杂。解：1）首先对AB进行编码，A的编码code1为1010，B的编码code2为0101；由于code1|code2≠0，且code1&code2=0，因此对直线段AB既不能简取也不能简弃。（2）求交处理。A的编码为1010，右起第二位编码不为0，故求出直线段AB与窗口右边界的交点C(2,11/5)；C的编码为1000，由于该编码不为0，所以求出的交点为虚交点，继续求交。驭剑天下——收集整理C点编码的最高位不为0，故求直线段AB与上边界的交点D(7/4,2)，其编码为0000，此时AD必在窗口外，可以用D点的坐标和编码代替A点的坐标和编码，code1＝0000由于code1|code2≠0，且code1&code2=0，直线段A（D）B仍然不能简取也不能简弃。（3）求交处理。A（D点）的编码为0000，交换code1与code2的值以及AB点的坐标值保证起点在窗口外，此时code1=0101，code2=0000由于code1=0101，右起第一位编码不为0，故求出直线段A（B）B（D）与窗口左边界的交点E(0,3/5)；E点的编码为0000，此时EA（B）必在窗口外，可简弃。用E点坐标和编码代替A（B）点坐标和编码由于code1|code2=0，直线段A（E）B（C）简取。6.14用梁友栋算法裁剪如图所示线段AB。分析：梁友栋算法是参数法裁剪在标准窗口下的特例，只要按照公式，先构造直线的参数方程，然后计算p，q，u值，最后求出umax和umin值，再代入到参数方程，求出直线段裁剪结果的边界坐标。解：以A（3，3）为起点，B(－2，－1)为终点（这里起点和终点可以互换，但这样直线的参数方程将会改变）。所以有x1=3，y1=3，x2=－2，y2=－1，wxl=0，wxr=2，wyb=0，wyt=2构造直线参数方程：计算各个p和q值有：驭剑天下——收集整理由于umaxumin，故此直线AB有一部分在裁减窗口内，将umax和umin代入直线参数方程，得到直线在窗口内部分的端点C（7／4，2）和D(0，3／5)。6.15试用Sutherland-Hodgeman算法对如下图所示多边形进行裁剪，要求画出每次裁剪对应的图形，并标明输入和输出的顶点。分析：Sutherland-Hodgeman算法是按照规定的策略，在每条边界裁剪的时候，输出顶点序列。注意裁剪时使用的交点是窗口边界及其延长线与多边形边的交点。解：驭剑天下——收集整理6.16试用Weiler-Atherton算法对如下图所示多边形进行裁剪，要求画出每次裁剪对应的图形，并标明输入和输出的顶点。分析：Weiler-Atherton算法是沿着窗口边界和多边形边界裁剪，处理时可以先利用直线段裁剪算法用窗口边界裁剪多边形的边，如果遇到由窗口内到窗口外的情况则需要用对应交点所在的窗口边界与多边形所有的边求交，求出实交点后排序，根据裁剪的方向求得所要的点，如果没有则需要输出一段窗口边界，然后用下一条边界继续求交，直到找到所要的点为止。但多边形所有的边处理完以后，则根据输出的直线段端点连接成一个或者多个多边形。解：如下图所示，输入顶点序列ABCDE。逆时针处理多边形，此时沿窗口边界处理的顺序也是逆时针。驭剑天下——收集整理（1）输入AB，由不可见侧进入可见侧，输出直线段IB；（2）输入BC，由可见侧进入不可见侧，输出直线段BJ，并从J点沿窗口逆时针找到距离最近的交点L，输出直线段JK和KL；（3）输出CD，由不可见侧进入不可见侧，不输出；（4）输出DE，由不可见侧进入可见侧再进入不可见侧，输出直线段LF，并从F点沿窗口逆时针找到距离最近的交点G，输出直线段FG；（5）输出EA，由不可见侧进入可见侧再进入不可见侧，输出直线段GH，并从H点沿窗口逆时针找到距离最近的交点I，输出直线段HI；驭剑天下——收集整理三、第七章7.5求将下图中的空间四面体关于P(2,－2,2)点整体放大两倍的变换矩阵，写出复合变换后图形各顶点的规范化齐次坐标。分析：三维变换的过程与二维变换的过程类似。解：关于P点整体放大两倍，可以先将P点平移至原点，再进行比例变换，最后反平移。变换矩阵为：变换过程为：所以变换后各点的规范化齐次坐标（注意要转换成规范化齐次坐标）分别为：（2，2，－2，1），（2，6，－2，1），（－2，6，－2，1），（2，6，2，1）变换矩阵为：驭剑天下——收集整理变换过程：所以变换后各点的规范化齐次坐标分别为：（2，2，－2，1），（2，6，－2，1），（－2，6，－2，1），（2，6，2，1）7.6假定一空间直线AB的两端点坐标为A(0,0,0)和B(2,2,2),试写出绕AB旋转30o的三维复合变换矩阵。分析：三维空间中绕任意轴旋转是较为复杂的过程。在经过平移使轴通过原点之后，通常需要经过两次旋转才能使轴与某个坐标轴重合：第一次将轴与某个坐标轴构造成一个面，并将这个面绕这个坐标轴旋转到某个坐标平面内，然后在该坐标平面中通过旋转使轴与该平面中的任意一个坐标轴重合；在绕轴旋转之后需要反旋转使轴回到原来的方向，最后反平移使轴回到原始的位置。这里需要注意旋转角度的正负以及角度值的确定。解：变换步骤如下(1)将ABB'绕x轴逆时针旋转α角，则AB旋转到xoz平面上。驭剑天下——收集整理(2)将OB绕y轴顺时针旋转β角，则OB旋转到z轴上。(3)此时AB轴与z轴重合，绕AB轴的旋转转换为绕z轴的旋转。(4)最后，求TRx，TRy的逆变换，回到AB原来的位置。最后的变换矩阵是这5个矩阵相乘的形式：驭剑天下——收集整理7.7试作出下图中空间四面体的三视图，要求写清变换式（设平移矢量均为1）。分析：三视图是最为简单的一种正投影，可以利用主视、俯视和侧视图的公式直接计算。解：（1）主视图（主视图不需要平移）（2）俯视图驭剑天下——收集整理（3）侧视图最后的图形为：驭剑天下——收集整理注意：三个图要画在一个坐标系中，以及点与点的连接关系以及直线的可见性问题。