计算机图形学辅导资料习题解答

1、习题4. 在本章第一节说明Bresenham算法如何选择下一个像素点位置的图2-3中，其实是假定了在当前选择的点是(x,y)时，真正直线与横坐标为x+1的直线的交点是在y和y+1之间。如果不是这样，而是下面两种情况：在y到y-1之间。例如从(0,0)到(7,2)的直线，在点(2,1)处向后。在y+1到y+2之间。例如从(0,0)到(7,5)的直线，在点(2,1)处向后。试说明为什么对所列两种情况算法仍能正确地工作。解答：在给出两种情况下，Bresenham算法仍然能够正确工作的原因是判别式d保证了在这两种总情况下，仍然能正确的取到最接近真正直线的像素点。在Bresenham算法中，按照判别式d

2、的正负来决定选择哪一点作为下一个像素点，判别式d如下计算：d = d1 d2。其中d1 = yp y，d2= y + 1 yp，y是当前选中点(x,y)的纵坐标，yp是真正直线与横坐标为x+1的直线的交点的纵坐标。当d0时，取上点，即(x+1,y+1)作为下一个像素点，当d0时，取下点，即(x+1,y)作为下一个像素点。这里还要说明一下，因为此处是按照书上给出的Bresenham算法来进行像素选择的，所以实际上有一个先决条件，即直线的斜率处于0和1之间。只要保证斜率满足条件，在当前选择的点是(x,y)时，真正直线与横坐标为x+1的直线的交点即使不在y和y+1之间，书上所给的Bresenham都

3、可以正确工作。题目所给两种情况中的直线斜率都满足算法的先决条件。在第(1)种情况下，如下图所示：当前选择点为(x,y)，下一点实际为P点，该点处于(x+1,y-1)和(x+1,y)两点之间，实际应取(x+1,y)点作为下一个像素点。现在来看一下为什么一定会取(x+1,y)点作为下一个像素点，而不是取(x+1,y-1)点作为下一个像素点。设Q点为选择(x,y)点作为显示像素点时实际的直线上的点，根据Bresenham算法的特点Q点的纵坐标yq一定满足y-0,5yqy+0.5，否则不会选择(x,y)点作为显示像素点，因为P点的纵坐标处于y和y-1之间，所以y-0.5yqy，否则该直线斜率将不满足条

4、件（直线斜率将小于0）。当y-0,5yqy时，则一定有y-0,5ypy，因为如果ypy-0.5，则P点的纵坐标会比Q点纵坐标更小，这时直线的斜率就不满足先决条件了（直线斜率将小于0）。所以因为直线斜率先决条件的限制，当真正直线与横坐标为x+1的直线的交点是在y和y-1之间时，该实际交点一定更靠近(x+1,y)点，所以一定会取(x+1,y)点作为下一个像素点。再来看一下按照Bresenham算法计算会取哪一点。从图可知，因为P点纵坐标yp在y-1和y之间，所以有ypy，ypy+1，所以有d1=yp-y0，由此可得d=d1-d2y+1，而如果yq1，所以直线斜率大于1）。当yyqy+0.5时，则一

5、定有y+1ypy+1+0.5，因为如果ypy+1+0.5，同时又有yqy+0.5，则yp-yq1，这时直线的斜率大于1，不满足先决条件。所以因为直线斜率先决条件的限制，当真正直线与横坐标为x+1的直线的交点是在y+1和y+2之间时，该实际交点一定更靠近(x+1,y+1)点，所以一定会取(x+1,y+1)点作为下一个像素点。再来看一下按照Bresenham算法计算会取哪一点。从图可知，因为P点纵坐标yp在y+1和y+2之间，所以有ypy，ypy+1，所以有d1=yp-y0，d2=y+1-yp0，所以要取上点(x+1,y+1)作为下一个像素点，跟实际应取的点是一致的，所以在这种情况下Bresenh

6、am算法仍然可以正确工作。综上所述，虽然书中所说算法在当前选择的点是(x,y)时，假定了真正直线与横坐标为x+1的直线的交点是在y和y+1之间，但只要要绘制的直线斜率满足处于0与1之间的先决条件，那么即使真正直线与横坐标为x+1的直线的交点不是在y和y+1之间，书上所介绍的Bresenham算法仍然可以正确工作。习题6. 推广本章第二节给出的Bresenham画圆算法使能够画出一个内部填充的实心圆。解答：因为Bresenham画圆算法在画圆的时候通过绘制对称点来完成整个圆周的绘制，所以只需绘制对称点之间连线上的象素点即可完成对圆形内部的填充。推广算法的实现代码如下：/参数：(x0,y0)为圆心

7、，R为半径，edgeColor为圆形边界颜色，inColor为圆形内部填充颜色void CDraw:BresenhamFillCircle(CDC *pDC, int x0, int y0, int R, COLORREF edgeColor, COLORREF inColor)int x,y,p;int i;x = 0;y = R;p = 3 - (R1);for (;x=y;x+)for (i=-y+y0;iSetPixel(-x+x0,i,inColor);pDC-SetPixel(x+x0,i,inColor);for (i=-y+x0;iSetPixel(i,x+y0,inColor

8、);pDC-SetPixel(i,-x+y0,inColor);/绘制圆弧上对称的八个像素点pDC-SetPixel(x + x0, y + y0, edgeColor);pDC-SetPixel(-x + x0, y + y0, edgeColor);pDC-SetPixel(x + x0, -y + y0, edgeColor);pDC-SetPixel(-x + x0, -y + y0, edgeColor);pDC-SetPixel(y + x0, x + y0, edgeColor);pDC-SetPixel(-y + x0, x + y0, edgeColor);pDC-SetPi

9、xel(y + x0, -x + y0, edgeColor);pDC-SetPixel(-y + x0, -x + y0, edgeColor);if (p 0)p+=(x2) + 6);elsep+=(x-y)2) + 10);y-;习题8. 本章第三节叙述了使用活跃边表的多边形扫描转换算法中ET表的填写方法。试写一个算法，输入多边形顶点坐标的逆时针序列，输出正确填写的ET表。解答：下面直接给出获得ET表的实现代码，为了构造书中所给样式的ET表，需要定义如下两个结构：struct EdgeNode/边节点int ymax;/最大y值，吊桶数据double xmin;/小y值端点的x值，吊桶

10、数据double fm;/斜率倒数，吊桶数据EdgeNode* next;/连接下一个边;struct HeadNode/头节点int ymin;/最小y值，ET表中登记项的y值EdgeNode* link;/连接边节点HeadNode* next;/连接下一个头节点;下面的实现代码用户获得构造完成的ET的头节点的头指针。其中参数points存放多边形的顶点的逆时针序列。HeadNode* CTestAView:GetET(CArray* points)HeadNode* pHead= NULL;int ymin;/记录正在处理的当前边的最小y值int nymin,nymax;/记录与正在处理

11、的当前边连接的下一边的最小y值和最大y值/循环点列表构造最初的边链表for (int i=0;iGetSize();i+)/获得当前点和下一点，构成一条边CPoint point1 = (CPoint)points-GetAt(i);CPoint point2;/如果当前点已经是最后一个点，则和第一点构成一条边if (i = points-GetSize() -1)point2 = (CPoint)points-GetAt(0);elsepoint2 = (CPoint)points-GetAt(i+1);/边平行于x轴，舍弃if (point1.y = point2.y)continue;/

12、构造边结构EdgeNode* edge = new EdgeNode();edge-next = NULL;/计算斜率倒数edge-fm = (double)(point2.x - point1.x)/(point2.y - point1.y);/设置ymin，ymax和xminif (point1.y point2.y)edge-ymax = point1.y;ymin = point2.y;edge-xmin = point2.x;elseedge-ymax = point2.y;ymin = point1.y;edge-xmin = point1.x;CPoint point3;/获得比

13、较局部极大极小的第三点，该点和第二点够成一条边/如果前两点已经取到顶点序列尾部，则顺序从头取点作为第三点int j = i+2;doif (jGetSize()point3 = (CPoint)points-GetAt(j);elsepoint3 = (CPoint)points-GetAt(j-points-GetSize();j+;while(point2.y = point3.y);if (point2.y point3.y)/计算point2和point3点对应的ymin和ymaxnymax = point2.y;nymin= point3.y;elsenymax = point3.y

14、;nymin= point2.y;/下面判断局部极大极小并缩短相应的边/如果连续的两条边的ymin值和ymax值都不同/表示连接两边的节点不为局部极大或极小if (ymin != nymin & edge-ymax != nymax)/缩短当前边/如果当前边的ymax值较大，则缩短当前边的ymin值if (edge-ymax nymax)ymin+;edge-xmin += edge-fm;else/否则，缩短当前边的ymax值edge-ymax-;/以下处理将当前边加入ET表if (pHead = NULL)/当前没有头节点pHead = new HeadNode();pHead-ymin

15、= ymin;pHead-link = edge;pHead-next = NULL;elseAddEdge(pHead,ymin,edge);/返回获得的ET表头指针return pHead;在上面的实现代码中用到了一个添加边函数，该函数作用是将处理完成的一条边加入到当前已有的ET表中，该函数的实现代码如下：void CTestAView:AddEdge(HeadNode* head, int ymin, EdgeNode* edge)HeadNode* temphead;while (head != NULL)/循环头节点if (head-ymin = ymin)/找到了对应的头节点Edg

16、eNode* p = head-link;/获得头节点对应的第一条边节点if (p-xmin edge-xmin)/新加入边的xmin值较小head-link = edge;edge-next = p;return;while (p-next != NULL)/循环当前头节点下所有边节点if (p-next-xmin edge-xmin)edge-next = p-next;p-next = edge;return;p = p-next;/到这里说明新加入的边的xmin值比原有的都大p-next = edge;return;else if (head-ymin ymin)/当前头节点的ymin

17、值大于新加入的边的ymin/下面处理新加入头节点HeadNode* newhead = new HeadNode();newhead-ymin = head-ymin;newhead-link = head-link;newhead-next = head-next;head-ymin = ymin;head-link = edge;head-next = newhead;return;temphead = head;head = head-next;/到这里说明新加入的边的ymin值比原有的头节点的ymin值都大HeadNode* newhead = new HeadNode();newhe

18、ad-ymin = ymin;newhead-link = edge;newhead-next = NULL;temphead-next = newhead;获得ET的实现函数中有两处需要说明：判断局部极大极小时，是用多边形顶点序列中相邻的3个点所构成的两条边进行判断，这是要求这两个边不能存在平行于x轴的边，因为当取得point1和point2点时已经判断了确定的边是否平行于x轴，所以主要处理在于确保获得的point3点，不会和point2点同时在一条平行于x轴的直线上，如果获得的point3点与point2点的y坐标相同，就按顶点序列继续取下一点作为point3点，直到point2点的y坐标

19、与取得的point3点的y坐标不同为止。在判断不是局部极大或极小后，缩短的都是当前处理的边，这样做可以保证边一次处理完毕，否则就会有处理当前边时，却需要去缩短以前处理的边或者还没有处理的边的情况存在。对当前边处理的方式就是如果当前边的ymax最大，则在ymin方向上缩短当前边，否则就在ymax方向上缩短当前边。为了检测以上构造的ET表是否正确，下面编写实现了使用上面方法构造的ET表完成多边形扫描转换算法。代码如下：void CTestAView:Polygonfill(CDC *pDC, CArray* points, COLORREF color)/获得ET表HeadNode* pET =

20、GetHEET(points);/AET表EdgeNode* pAET = NULL;/最小y值int y = pET-ymin;/最大y值int ymax = y;/有需要处理的扫描线while (y ymin = y)/将当前头节点对应的边合并到AET表中/获得当前要合并的头节点下边链表的头指针EdgeNode* p = pET-link;if (pAET = NULL) pAET = p;elseEdgeNode* q = pAET;while (q-next != NULL) q = q-next;q-next = p;/清除已经处理过的头节点，并释放空间HeadNode* delet

21、ehead = pET;pET = pET-next;delete deletehead;/根据移动过来的边，修改ymax值while (p!=NULL)if (ymax ymax)ymax = p-ymax;p=p-next;/排序SortAET(pAET);EdgeNode* pFill = pAET;/填充AET表中的区间while (pFill != NULL)/填充当前边和下一条边之间的区间for (int i=(int)pFill-xmin;inext-xmin;i+)pDC-SetPixel(i,y,color);/AET表中的边应成对出现pFill = pFill-next-n

22、ext;/将AET表中ymax为当前扫描线的边清除出表pFill = pAET;EdgeNode* pFore = NULL;while (pFill != NULL)/当前边ymax等于扫描线if (pFill-ymax = y)if (pFore != NULL)/说明要删除的不是第一个节点pFore-next = pFill-next;/修改上一条边的指向else/说明要删除的是第一个节点pAET = pFill-next;/需要修改AET表头指针指向下一条边/销毁已经清除出链表的边对象EdgeNode* deleteedge = pFill;/移动到下一条边pFill = pFill-

23、next;delete deleteedge;else/记录当前边作为下次处理时的上一边pFore = pFill;/移动到下一条边pFill = pFill-next;/AET表中仍然有边if (pAET != NULL)/重新计算AET中各边的xmin值pFill = pAET;while (pFill != NULL)pFill-xmin+=pFill-fm;pFill = pFill-next;/重新排序SortAET(pAET);/处理下一条扫描线y+;上面代码中使用到对AET表进行排序的函数，其代码如下：void CTestAView:SortAET(EdgeNode *pEDGE

24、)/要排序的边链表中第一个边EdgeNode* p1 = pEDGE;/第一个边的下一个边EdgeNode* p2 = NULL;while (p1 != NULL)p2 = p1-next;/获得下一条边while (p2 != NULL)/如果前一条边的xmin大于后一条边if (p1-xmin p2-xmin)/交换数据int cid;double cdd;cid = p1-ymax;p1-ymax = p2-ymax;p2-ymax = cid;cdd = p1-xmin;p1-xmin = p2-xmin;p2-xmin = cdd;cdd = p1-fm;p1-fm = p2-fm

25、;p2-fm = cdd;/下一条边p2 = p2-next;/下一条边p1 = p1-next;以上代码均测试通过。习题8. 若窗口在定义为平行于用户坐标轴的直立矩形后，还允许此窗口再绕左下角点旋转角，写出由旋转后窗口到直立矩形视见区的变换矩阵。解答：设在绕左下角点旋转角之前，窗口的左下角点坐标为（wxl, wyl），右上角点坐标为（wxh, wyh），直立矩形视见区的左下角点坐标为（vxl, vyl），右上角点坐标为（vxh, vyh）。变换矩阵可按如下方式求得：首先平移窗口，使其左下角点与坐标系原点重合，然后绕原点旋转角，使窗口变回直立矩形，然后对其作比例变换使其大小与视见区相同，最后通

26、过平移使其与视见区重合。由此得到视见变换矩阵为：习题10. 求完成如下空间图形变换的变换矩阵：产生对平面对称的图形。绕过原点和（1，1，1）的直线旋转。解答：(3) 变换矩阵如下：(4) 在以过坐标原点的任意直线为旋转轴作旋转变换的变换矩阵中代入向量值及旋转角度，得变换矩阵如下：习题14. 等轴投影是投影方向与三个坐标轴有相等夹角时的正交投影，设要实现一个投影方向为（1，1，1）的等轴投影，可以先绕轴再绕轴做旋转变换使投影方向重合于轴正方向，然后就可以进行正交投影了。试用这个想法推导出做等轴投影的变换矩阵，然后验证三根坐标轴上的单位向量被相等地缩短，并且可以使三个坐标轴的投影具有相等的夹角。解

27、答：已知：xxzy(x1,y1,z1)(0, y1,v)O在视觉坐标系下可得如下变换：获得变换矩阵为在观察坐标系下可得如下变换矩阵：因为：，即三个坐标轴上的单位向量以相同比例系数缩短三个坐标轴上的单位向量在投影平面上的点为，三个坐标轴上的投影具有相等的夹角。习题20. 修改Cohen-Sutherland直线裁剪算法，使其成为一个直线“开窗”算法，即指定一个窗口后，窗口内舍弃，窗口外保留。解答：根据题意，可知只需要对原Cohen-Sutherland算法中的两处进行修改即可满足要求。第一处是判断C1和C2的逻辑乘结果不为0时，此时如果该条件满足，表示线段完全在窗外，原算法此处需要将原线段完全舍

28、弃，这里就需要将原线段完全绘制出来即可。第二处是最后要将原线段中窗口中可见部分绘制出来，此时原算法已经完成对原线段的裁剪，得出来原线段在窗口内的部分，这里只需要改成将原线段去掉窗口以内部分后的线段绘制出来即可。根据以上分析，修改Cohen-Sutherland直线裁剪算法为直线“开窗”算法如下：double xl, xr, yt, yb; (这里事先给出窗口的位置，四个数值是已知的)，修改的部分用蓝色表示void Cohen_Sutherland(double x0, y0, x2, y2)int c, c1, c2;double x, y;/需要将原线段的端点保存起来，以备后面需要确定原线段

29、去除窗口内部分时使用double x00=x0,y00=y0,x22=x2,y22=y2;makecode(x0, y0,c1); makecode(x2, y2, c2);while (c1!=0 | c2!=0)if (c1&c2!=0) showline(x00, y00, x22, y22);/显示原线段，能走到这说明原线段都在窗口外return;c=c1; if (c=0) c=c2;if (c&1=1) y=y0+(y2-y0)*(x1-x0)/(x2-x0); x=x1;else if (c&2=2) y=y0+(y2-y0)*(xr-x0)/(x2-x0); x=xr;else

30、 if (c&4=4) x=x0+(x2-x0)*(yb-y0)/(y2-y0); y=yb;else if (c&8=8) x=x0+(x2-x0)*(yt-y0)/(y2-y0); y=yt;if (c=c1)x0=x; y0=y; makecode(x, y, c1);elsex2=x; y2=y; makecode(x, y, c2);/因为原算法的线段分割保证了端点的顺序性，所以采用如下的方法可确定原线段在窗口外的部分if (x00!=x0 | y00!=y0) showline(x00,y00,x0,y0);if (x2!=x22 | y2!=y22) showline(x2,y2

31、,x22,y22);此算法已经编码实现并测试通过。另一种方法是在分割线段的同时绘制窗口外的线段，该方法无需记录初始点坐标。double xl, xr, yt, yb; (这里事先给出窗口的位置，四个数值是已知的)，修改的部分用蓝色表示void Cohen_Sutherland(double x0, y0, x2, y2)int c, c1, c2;double x, y;makecode(x0, y0,c1); makecode(x2, y2, c2);while (c1!=0 | c2!=0)if (c1&c2!=0) /显示线段，此时绘制的是分割完后，完全在窗口外同侧的线段showline

32、(x0, y0, x2, y2); return;c=c1; if (c=0) c=c2;if (c&1=1) y=y0+(y2-y0)*(x1-x0)/(x2-x0); x=x1;else if (c&2=2) y=y0+(y2-y0)*(xr-x0)/(x2-x0); x=xr;else if (c&4=4) x=x0+(x2-x0)*(yb-y0)/(y2-y0); y=yb;else if (c&8=8) x=x0+(x2-x0)*(yt-y0)/(y2-y0); y=yt;if (c=c1)showline(x0,y0,x,y);/绘制被分割抛弃的线段x0=x; y0=y; make

33、code(x, y, c1);elseshowline(x,y,x2,y2);/绘制被分割抛弃的线段x2=x; y2=y; makecode(x, y, c2);此算法已经编码实现并测试通过。习题10. 设平面上四点设平面上四点(1，1)，(2，3)，(4，3)，(3，1)确定的Bezier曲线是P(t)，如果在点P(1/2)处将它分为两段，求前后两段做为Bezier曲线各自的四个控制点坐标。解答：使用分裂法，有：PP0(1,1)R0P1(2,3)R1P2(4,3)R2P3(3,1)R3R0=(3/2,2)R1=(3,3)R2=(7/2,2)R0=(9/4,5/2)R1=(13/4,5/2)R

34、0=(11/4,5/2)i=0i=1i=2Q0Q1Q2Q3前半段四个控制点Q0(1,1)，Q1(3/2,2)，Q2(9/4,5/2)，Q3(11/4,5/2)，0t1/2；后半段四个控制点R0(11/4,5/2)，R1(13/4,5/2)，R2(7/2,2)，R3(3,1)，1/2t1。习题17. 设给定n个型值点，问如何作出一条均匀4阶3次B样条曲线，使曲线分别以和为起点和终点，并与边和边相切。解答：解法1：根据题意，在已有的n个型值点前面增加两个型值点和，在后面增加两个型值点和。第一段曲线由，控制，要求曲线要以为起点，并且与边相切，则有：解上面方程可得出和为：最后一段曲线由，控制，要求曲线要以为终点，并且与边相切，则有：解上面方程可得出和为：增加如上4点到已有的型值点中，可使作出的均匀4阶3次B样条曲线满足题目要求。解法2：也可以只在前后各增加一个型值点和。第一段曲线由，控制，要求曲线要以为起点，