计算机图形学材料整理

《计算机图形学材料整理》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、2．中点画圆法条件：从(0，R)到(，)的1/8圆为例，说明中点画圆法是如何确定最佳逼近于该段圆弧的像素序列的。假定当前已确定了圆弧上的一个像素点为，那么，下一个像素只能是右方的或右下方的。如图所示。图当前像素与下一像素的候选者构造函数，对于圆上的点，；对于圆外的点，；对于圆内的点，。（圆的正负划分性）基本原理：设M是图中和的中点，即。当时，M在圆内，这说明距离圆弧更近，应取作为下一像素。当时，离圆弧更近，应取。当时，可在和之中任取一个，这里约定取。根据上述原理，构造判别式若则应取P1为下一像素，而且再下一像素的判别式

2、为若则应取P2为下一像素，而且下一像素的判别式为由于这里讨论的是按顺时针方向生成第二个八分圆。则第一个像素是(0,R)，判别式d的初始值为：为了避免浮点运算，可令，此时，初始化运算对应于。判别式d<0对应于e<-0.25。又由于e的初值为整数，且在运算过程中的增量也是整数，所以e始终是整数，所以e<-0.25可以用e<0来代替。详细的算法如下所示：MidPointCircle(intr,intcolor){intx,y;inte;x=0;y=r;e=1-r;CirclePoints(x,y,color);while(x

3、<=y){if(e<0)e+=2*x+3;else{e+=2*(x-y)+5;y--;}x++;CirclePoints(x,y,color);}}说明：中点画圆法可以推广到一般二次曲线的生成1．有序边表的扫描线算法活性边和活性边表：与当前扫描线相交的边称为活性边(ActiveEdge)，并把它们按与扫描线交点x坐标递增的顺序存放在一个链表中，称此链表为活性边表(AET)。图一个多边形与若干扫描线下图a为上图所示中Y=6的扫描线的活性边表,(b)图为Y=7的扫描线的活性边表。(a)(b)图活性边表(AET)活性边表的数

4、据结构：第1项保存当前扫描线与边的交点坐标x值；第2项保存从当前扫描线到下一条扫描线间x的增量Dx；原因如下：假定当前扫描线与多边形某一条边的交点的x坐标为xi，则下一条扫描线与该边的交点不要重新计算，而是通过增加一个增量△x来获得。具体方法是：设该边的直线方程为：ax+by+c=0；若y＝yi，x=xi；则当y=yi+1时，其中为常数，（斜率的倒数，即）第3项保存该边所交的最高扫描线号ymax；原因如下：因为使用增量法计算时，还需要知道一条边何时不再与下一条扫描线相交，以便及时把它从活性边表中删除出去。所以保存该边所

5、交的最高扫描线号ymax新边表：为了方便活性边表的建立与更新，可为每一条扫描线建立一个新边表(NET)，存放在该扫描线第一次出现的边。也就是说，若某边的较低端点为ymin，则该边就放在扫描线ymin的新边表中，下图是新边表的示意图。（即如何知道一条扫描线开始与某边相交了）图各条扫描线的新边表NET新边表的每个结点存放对应边的初始信息。如该扫描线与该边的初始交点x（即较低端点的x值），x的增量Δx，以及该边的最大y值ymax。新边表的结点不必排序。新边表的目的：避免盲目求交。当处理一条扫描线时，为了求得它和多边形边的所有

6、交点，必须将它与所有的边进行求交测试，而实际上只有某几条边与该扫描线有交点。例如，假设当前的扫描线为y＝3，由于边所属的类的序号大于3（即下端点的y坐标大于3），那么它们和y＝3根本没用交点，就不用求交测试了。注意：扫描线算法规定多边形的边不自交，则从当前扫描线延续到下一条扫描线的边与下一条扫描线的交点顺序保持不变。否则，到下一条扫描线，必须重新排序。算法过程voidpolyfill(polygon,color)intcolor;多边形polygon;{for(各条扫描线，标示为i){初始化新边表头指针NET[i]；把

7、ymin=i的边放进新边表NET[i];}y=最低扫描线号；初始化活性边表AET为空；for(各条扫描线i){把新边表NET[i]中的边结点用插入排序法插入AET表，使之按x坐标递增顺序排列；遍历AET表，把配对交点区间(左闭右开)上的像素(x,y)，用drawpixel(x,y,color)改写像素颜色值；遍历AET表，把ymax=i的结点从AET表中删除，并把ymax>i结点的x值递增Dx；若允许多边形的边自相交，则用冒泡排序法对AET表重新排序；}}/*polyfill*/