if(p1.y!=p2.y){
edge=(Edge*)malloc(sizeof(Edge)); if(p1.y makeEdgerec(p1,p2,yNext(i,cnt,points),edge,edges); else makeEdgerec(p2,p1,yprev,edge,edges); } yprev=p1.y; p1=p2; } } void buildActiveList(int scan,Edge * active,Edge *edges[]) { Edge * p,* q; p=edges[scan]->next; while(p){ q=p->next; insertEdge(active,p); p=q; } } void fillScan(int scan,Edge * active,CDC *pDC) { Edge *p1,*p2; int i; p1=active->next; while(p1){ p2=p1->next; for(i=p1->xIntersect;i void deleteAfter(Edge * q) { Edge * p=q->next; q->next=p->next; free(p); } void updateActiveList(int scan,Edge * active) { Edge *q=active,*p=active->next; while(p){ if(scan>=p->yUpper) { p=p->next; deleteAfter(q); } else{ p->xIntersect=p->xIntersect+p->dxPerScan; q=p;p=p->next; } } } void resortActiveList(Edge * active) { Edge *q,*p=active->next; active->next=NULL; while(p){ q=p->next; insertEdge(active,p); p=q; } } void scanFill(int cnt,CPoint * points,CDC *pDC) { Edge * edges[WINDOW_HEIGHT],* active; int i,scan; for(i=0;i edges[i]=(Edge*)malloc(sizeof(Edge)); edges[i]->next=NULL; } buildEdgeList(cnt,points,edges); active=(Edge*) malloc(sizeof(Edge)); active->next=NULL; for(scan=0;scan fillScan(scan,active,pDC); updateActiveList(scan,active); resortActiveList(active); } } } 3.7简述边缘填充算法和边界标志算法的基本思想、步骤以及优缺点。 答：边缘填充基本思想：对于多边形P的每一非水平边PiPi+1(I=0,1,┅n) 上的各个像素做向右求反运算即可.优缺点：边缘填充算法的数据结构和程序结构都简单的多，缺点：执行时许对帧缓冲器中的大批元素反复赋值，故速度不必扫描线算法快，另外，如果区域内原来有其他的颜色，也不能保证最后的区域内的颜色是多边形的颜色。 边界标志算法的基本思想：首先用一种特殊的颜色在帧缓冲器中将多边形的边界（水平边的部分边界除外）勾画出来。然后再把位于多边形内的各个像素着上所需的颜色 步骤1：以值为boundary-color 的特殊颜色勾画多边形P的边界。设多边形顶点 为Pi= (xi, yi),0≤i≤n， xi, yi均为整数；置Pn+1=P0。每一条扫描线上着上这种特殊颜色的点的个数必定是偶数(包括零)。 ?步骤2：设interior_point 是一布尔变量。对每一条扫描线从左到右进行搜索， 如果当前是像素位于多边形P内，则interior_point=true，需要填上值为polygon_color的颜色；否则该像素在多边形P外，需要填上值为background_color的颜色 优缺点：避免了对帧缓冲器中的大量元素的多次赋值，但需逐条扫描线并对帧缓 冲器中的元素进行搜索和比较。 3.8区域种子填充在图形学应用中有何作用？ 答案：区域种子填充在只改变区域的颜色属性，不改变区域的表示方法时使用，尤其适用于交互改变区域颜色时，比如：墨水瓶、油漆桶等。 3.9请简要叙述种子算法的基本思想及其用堆栈实现八连通算法原理。 答：种子算法充分利用了递归调用的机理，在前一种子点确定并变为新颜色后， 按照自身调用的八向顺序依次查找新的种子点，找到即变为新颜色，继续下一种子的查找。未查的方向被压栈保存，等退栈时继续查找，最终完成蔓延至整个区域所有点都变为新颜色。 3.10简述几种主要反走样算法的基本思想及优缺点。 答：1提高分辨率基本思想：提高硬件的分辨率。优缺点：：能在非反走样算法 的基础上进行反走样的工作。 2线段反走样算法的基本思想：因为线段是有宽度的，将向段看作是狭长的矩形，具有一定的面积，当线段通过某象素时，可以求出两者面积得交，之后根据每个象素与线段相交部分的面积只决定该象素的颜色值或灰度值 优缺点：极大改善了线段显示时的线形质量，但是由于要计算面积，使得计算量大大增加，不适合动态的交互式图形显示。 3多边形反走样算法基本思想：采用反走样线段的思想来改善多边形边界的显示质量。当某象素玉多边形区域相交时，求出两者相交的面积，然后以此面积值来决定该象素的颜色值或灰度值。 优缺点 3.11扩展Bresenham算法，实现一个反走样程序，从而调整直线路径附近的像素亮度。 m = 2*(ye–ys)/(xe-xs); y = ys; x= xs; e = m-0.5; nloop =(xe-xs)/2; for (i=1;i<=nloop;i++) { if( e>1){ DrawPixels(pattern4,x,y); //gl_Point(x+1,y+1); gl_Point(x+2,y+2); y= y+2; e= e-2; } else if (e>0 && e<=1) { if (e>0.5) Draw Pixels(pattern3,x,y); else Draw Pixels(pattern2,x,y); y = y+1; e = e-1; } else Draw Pixels(pattern1,x,y); e = e+m; x = x+2; }//end for gl_Point(xe,ye); 3.12在区域填充的扫描线算法中加上反走样程序，使用连续性来减少连续扫描线上的计算量。 答案： deltax=xe-xs; deltay=ye-ys; m=deltay/deltax; y=ys; x=xs; a=1-m; d=0.5; for(I=1;I setpixel(framebuffer,x,y,d); if(d>=a) { y=y+1; d=d-a; } else d=d+m; x=x+1; } 第四章作业与答案 第四章 变换 习题 4.1 下面有关平面几何投影的叙述中，哪些是正确的？ (1). 平面几何投影中，透视投影的投影中心到投影平面的距离是有限的。(Y) (2). 平面几何投影中，一组平行线的投影仍保持平行。(N) (3). 平行投影与透视投影相比，视觉效果更有真实感，而且能真实地反映物体的精确集合尺 寸与形状。(N) (4). 在三维空间中的平行投影变换不可能产生灭点。(Y) 4.2写出下列二维图形变换的变换矩阵： (1). 沿x轴正向移动一个绘图单位，同时，沿y轴负向移动一个绘图单位。 ?x'??101??x?x'10x1?????????????y? y'?01?1,???y'??01??y???1????????????????1??001??1???????(2). 绕原点逆时针旋转90度 ?x'??0?1??x??y'???10??y? ??????(3). 沿x轴负向移动2个绘图单位，同时，沿y轴正向移动2个绘图单位。 ?x'??10?2??x??x'??10??x???2??????y? y'?012,???y'??01??y??2????????????????1??001??1???????(4). 坐标轴为对称轴的反射图形。 ?x'??10??x??x'???10??x?X轴为对称轴??????y?,y轴为对称轴?y'???01??y? y'0?1????????????(5). y=x为对称轴的反射图形。 ?x'??01??x??y'???10??y? ??????4.3证明三维变换矩阵的乘积对以下运算顺序是可交换的： (1). 任意两个连续平移。