图形学复习

CH7 光栅化

前几章介绍了几何处理和裁剪变换，接下来的步骤就是光栅化

光栅化是将形式表示的几何图元转换为阵列表示的数据片元的过程，片元中每一个像素对应帧缓冲区中的每一个像素

7.1 线段生成算法

(1)DDA画线算法

设直线表达式为y=mx+b，输入直线两端点坐标(x0,y0)和(xend,yend)，可以计算出m=yend?y0xend?x0和b=y0?m?x0

DAA是基于微分运算的线段生成算法，其主要计算式便是δy=mδx：

若|m|≤1则x方向的变化大于y方向的变化，以x方向为主方向，取δx=1根据m计算δy=mδx

若|m|>1则y方向的变化大于x方向的变化，以y方向为主方向，取δy=1根据m计算δx=1mδy

为了有效的避免了斜率为正无穷时xend?x0=0的除零计算，我们将不直接计算m而是直接比较Δy=|yend?y0|和Δx=|xend?x0|的大小确定步长，计算出步长后每一步从的(x,y)更新到(x+xstep,y+ystep)并计算取整即可(注意，像素永远是整数点)

下面是DDA算法C语言版本代码：

void lineDDA(int x0, int y0, int xend, int yend){

int steps, k;

float xstep, ystep;

float x = x0, y = y0;

int dx = xend - x0;

int dy = yend - y0;

if (fabs(dx) >= fabs(dy))

steps = dx;

else

steps = dy;

xstep = (float)dx / (float)steps;

ystep = (float)dy / (float)steps;

setPixel(round(x), round(y));

for (k = 0; k < steps; k++) {

x += xstep;

y += ystep;

setPixel(round(x), round(y));

}

}

DDA算法避免的迭代时的乘积运算因此比直接用直线表达式求点坐标效率更高，但是，每一步骤中的浮点操作和取整运算开销仍然较大(体系结构告诉我们整数运算和浮点运算效率可以相差几十倍)

(2)Bresenham画线算法

Bresenham画线算法是一种精确而有效的线段生成算法，它运用DDA的思想并通过邻近点的比较避免了浮点操作和取整运算，下面讨论斜率小于1的线段的Bresenham画线算法(斜率大于1只需要类似DDA中的比较、交换即可)

再进一步方便讨论，限定0≤m≤1，我们需要确定的是当前画了点(xk,yk)之后下一步要画的点(xk+1,yk+1)的位置，由于x是主方向所以取xk+1=xk+1毋庸置疑，而x是主方向说明了ystep≤xstep=1，则yk≤yk+1≤yk+1，由于只能去整数点那么yk+1就只能是yk、yk+1二者其中之一，很显然我们只用选一个离yk+1近的就可以了

令dlower=yk+1?yk=f(xk+1)?yk=m(xk+1)+b?yk>0

令dupper=(yk+1)?yk+1=(yk+1)?f(xk+1)=(yk+1)?[m(xk+1)+b]>0

则要比较的就是dlower和dupper，选更小的那个即可，做差有：

dlower?dupper=2[m(xk+1)+b]?2yk?1

那么每次我们可以带入上式计算大于0(dlower更大更靠近上者)yk+1选yk+1，否则选yk，但是上式计算仍然有乘法计算，我们想避免乘法计算获取更高的效率，那么需要引入决策参数Δp(Bresenham算法核心)，令：

Δp=Δx(dlower?dupper)=Δx[2m(xk+1)+2b?2yk?1]=Δx[2m(xk+1)+2b?2yk?1]=Δx[2ΔyΔx(xk+1)+2b?2yk?1]=2Δy?xk?2Δx?yk+c其中c=2Δy+2Δx?(2b?1)是常数

这样仍然存在乘法计算，考虑pk的迭代计算有：

pk+1=pk+2Δy?2Δx(yk+1?yk)

p0=2Δy?Δx，pk决定yk+1?yk取0还是1，因此只用一个if语句即可避免每次迭代中的乘法运算(把2Δy、2Δx存在临时变量中)

上述即是Bresenham画线算法的思想，下面给出二维全空间的**Bresenham画线算法**C语言源代码：

void line_Bresenham(int x1, int y1, int x2, int y2){

int dx = abs(x2 - x1);

int dy = abs(y2 - y1);

bool morethan_45 = dy > dx;

if (morethan_45) {

swap(x1, y1);

swap(x2, y2);

dx = abs(x2 - x1);

dy = abs(y2 - y1);

}

if (x1 > x2) {

swap(x1, x2);

swap(y1, y2);

}

int ystep = y2 > y1 ? 1 : -1;

int y = y1;

int x = x1;

int twody = 2 * dy;

int twody_minus_twodx = 2 * dy - 2 * dx;

int p = twody - dx;

while (x <= x2) {

if (morethan_45) {

plot_point(y + size, x);

} else {

plot_point(x, y + size);

}

if (p < 0) {

p += twody;

} else {

p += twody_minus_twodx;

y += ystep;

}

x++;

}

}

对称说明：

我们在1.Bresenham画线算法中给出的算法是在0 <= m <= 1的情况下的，所以对于全二维空间的直线我们需要做两次对称。

(1)x轴对称

做x轴对称将m取值范围扩展到|m| <= 1：

其他不变，引入变量ystep表示y的运动方向和步长。

0 <= m <= 1时，ystep = 1；-1 <= m < 0时，ystep = -1。

那么算法的第四步迭代y坐标时将1换成ystep即可。

(2)y=x对称

处理完|m| <= 1情况后，再处理|m| > 1的情况：

任意一条|m| > 1的直线都和一条|m| <= 1的直线关于y=x对称，那么则没必要写一次y方向为主方向的画线算法。直接在输入坐标后将端点坐标做一次y=x对称变换，当作一条|m| <= 1的直线来完成Bresenham画线算法的相应计算。最后在画点时再做一次y=x对称变换得到正确位置即可。

7.2 圆和椭圆生成算法

(1)中点画圆算法

中点画圆算法和Bresenham画线算法一样，通过引入决策参数来消除浮点和乘法运算

把圆划分成8个18圆(弧)，可以通过做对称变换画出整个圆，下面以一象限内0

从x=0到x=y枚举点，在弧A上x的变化大于y的变换(x是主方向)，那么画了(xk,yk)之后下一步要画的点(xk+1,yk+1)只能取(xk+1,yk)或(xk+1,yk?1)

中点画圆的思想就是：判断如果yk+1取yk和yk?1的中点yk?12，改点在圆外还是圆内

取决策参数pk=fcircle(xk+1,yk?12)=(xk+1)2+(yk?12)2?r2，则

pk<0，中点位于圆内，yk更靠近圆周边界

否则，yk?1更靠近圆周边界

同样有迭代思想求pk：

p0=54?r

若pk<0，则迭代yk+1=yk,2yk+1=2yk,pk+1=pk+2xk+1+1

否则，迭代yk+1=yk?1,2xk+1=2xk,2yk+1=2yk?2,pk+1=pk+2xk+1+1?2yk+1

两种情况均有xk+1=xk+1,2xk+1=2xk+2

注意上述描述的是以原点为中心点的画圆算法，若中心点需要在(xc,yc)的话，所有画的点均平移到(x+xc,y+yc)即可

(2)中点画椭圆算法

中点画椭圆算法和中点画圆算法基本一样，只是需要在一象限分两个区域1、2讨论，令fellipse=r2yx2+r2xy2?r2yr2x

区域1中：

p1k+1=?????p1k+2r2yxk+1+r2y,p1k<0p1k+2r2yxk+1+r2y?2r2xyk+1,p1k≥0

区域2中：

p2k+1=?????p2k?2r2xyk+1+r2x,p2k<0p2k?2r2xyk+1+r2y?2r2yxk+1,p2k≥0

注意区域2中小于0选(xk,yk?1)，否则选(xk+1,yk?1)

7.3 通用扫描线填充算法

多边形扫描线填充的方法是沿多条平行于x轴的直线y=c逐像素扫描，若像素点落在多边形内部则填充为指定颜色

(1)扫描线算法

扫面线算法利用以下相邻像素连贯性，提高扫描效率：

边的连贯性：某条边与扫描线相交，它可能和下一条扫描线也相交

扫描线的连贯性：当前扫描线的交点顺序可能和下一条扫描线的交点顺序相同或类似

区间的连贯性：同一区间上像素取相同颜色填充

扫描线算法的一般步骤为：

求交点

交点排序

交点配对

(2)有序边表算法

有序边表算法就是一种经典的扫描线算法

定义活性边是与当前扫描线相交的边，边结构如下：

typedef struct {

int ymax; //边最大y值，即与相交的最大扫面线号

float x; //当前扫描线与边相交的x坐标

float dx; //边斜率的倒数

Edge *next; //指向下一条边的指针

} Edge;

那么活性边表AEL就是活性边按x递增的顺序构成的链表，和活动边表相关的是当前的扫描线，随着扫描线的移动按照如下的规则维护AEL：

如果一条边和下一条扫描线有交点，则根据该边的边斜率倒数dx来更新和下一条扫面线相交的x坐标点，即x=x+dx

如果一条边和下一条扫描线没有交点了，那么这条边不再是活动边，则删除AEL中的这条边

如果有其它新边和下一条扫描线相交，那么需要把新边加入AEL

上述新边的定义是：若某条(非水平)边的下端点是y，那么称之为扫面线y的新边；很容易发现要构造AEL就先要构造定义新边表NET，NEL无序排列因此构造NET枚举一遍边即可

下面给出有序边表算法的算法描述：

枚举所有边，构造NET

取y的初始值为NET中最小的非空元素，即最低扫描线的y坐标

置AEL为空

(循环开始)若NET中扫描边y的新边不为空则将所有边“取出”并插入AEL，AEL排序

AEL边中的x两两配对(x按取整规则取整)，获取了有效区间后在第y行填充各区段

y=y+1

AEL中删除ymax=y的边

AEL中剩下的每条边做x更新，x=x+dx

(跳转)若AEL和NET有一个非空则转第4步循环

7.4 反走样

(1)走样与反走样策略

走样是指：用离散的像素来连续的图形时引起的失真，常见的走样有：

阶梯状边界(阶梯状斜线、阶梯状圆弧)

图形细节失真(图形比一个像素点小但被生成算法扩充成一个像素，细节展现削弱)

狭小图形直接遗失(图形比一个像素点小并且直接被生成算法“抛弃”，细节遗失)

反走样有一下几种策略：

提高分辨率

非加权区域采样

加权区域采样

提高分辨率可取但成本高，显示器首先要重新设计(提高1倍的分辨率需要4倍的像素点阵和帧缓存容量)其次图元生成、片元生成等算法开销均要增大

区域采样是把直线段看作具有一定宽度的狭长矩形，当直线段与某象素有交时，求出两者相交区域的面积，根据相交区域的面积，加权或不加权地确定该象素的亮度值，如下图展示：

非加权区域采样需要直接计算相交的三角形或梯形或其他多边形的区域的面积，运算量大(设计乘法运算)，一种近似策略是分割像素点为更小的子像素，计算子像素落在直线内部的比例从而得到近似面积

非加权区域采样有一个问题就是像素中靠外面的子像素对近似面积的贡献和靠里面的子像素对近似面积的贡献相同，这样的得到的反走样图像不是很平顺，一般采用加权区域采样

我们可以仿照图像处理中滤波器的思想来设计反走样立方体滤波器以及圆锥体滤波器等等来确定权重

(2)直线反走样算法

直线反走样算法中应用最广泛的是Wu直线反走样算法，Wu反走样的算法和Bresenham画线算法思想很类似，同样是在比较dupper和dlower大小：

设背景色是C1，线条颜色是C2，那么如图的H点和L点的颜色分别是C1dupper+C2dlowerdupper+dlower、C1dlower+C2dupperdupper+dlower

对于黑线白背景我们用RGBA颜色的不透明度alpha表示灰度颜色，且栅格距离为1，则有H、L点不透明度分别为dlower、dupper

因此Wu反走样计算十分简单，直观上也能理解：线条离H点更近因此H点有更大的不透明度(dlower)，L点反之；当线条过HL中点时H、L两个像素点的颜色应该具有同样的不透明度，符合常理

dlower、dupper的计算我们通过维护error——直线上坐标与画点坐标偏差来完成：

当0 < error < 0.5时，y(xk+1) > yk 且主点是(xk+1, yk)在下，dupper＝1 - error，dlower＝error，即主点不透明度1 - error，副点不透明度error。

当-0.5 <= error <= 0时，y(xk+1) < yk 且主点是(xk+1, yk)在上，dupper＝1 ＋ error，dlower＝-error，即主点不透明度1 + error，副点不透明度-error。

Bresenham画线算法稍加修改即可得到Wu直线反走样算法，略

(3)多边形填充区域边界反走样算法

多边形填充区域边界反走样算法和直线反走样算法类似，只是它只考虑多边形外部边界的反走样，内部均填充为多边形指定颜色

或者直接按直线反走样算法，然后做扫描填充时不考虑边界像素点，只按最大亮度/不透明度填充内部像素点即可

《《计算机图形学》有序边表填充算法》由会员分享，可在线阅读，更多相关《《计算机图形学》有序边表填充算法(10页珍藏版)》请在人人文库网上搜索。

1、实 验 报 告一、 实验目的1、 掌握有序边表算法填充多边形区域；2、 理解多边形填充算法的意义；3、 增强C语言编程能力。二、 算法原理介绍根据多边形内部点的连续性知：一条扫描线与多边形的交点中，入点和出点之间所有点都是多边形的内部点。所以，对所有的扫描线填充入点到出点之间所有的点就可填充多边形。判断扫描线上的点是否在多边形之内，对于一条扫描线，多边形的扫描转换过程可以分为四个步骤：(1)求交：计算扫描线与多边形各边的交点；(2)排序：把所有交点按x值递增顺序排序；(3)配对：第一个与第二个，第三个与第四个等等；每对交点代表扫描线与多边 形的一个相交区间;(4)着色：把相交区间内的象素置成多。

2、边形颜色，把相交区间外的象素置成背景色。p1,p3,p4,p5属于局部极值点，要把他们两次存入交点表中。 如扫描线y=7上的交点中，有交点(2,7,13)，按常规方法填充不正确，而要把顶点(7,7)两次存入交点表中(2,7,7,13)。p2，p6为非极值点，则不用如上处理。为了提高效率，在处理一条扫描线时，仅对与它相交的多边形的边进行求交运算。把与当前扫描线相交的边称为活性边，并把它们按与扫描线交点x坐标递增的顺序存放在一个链表中，称此链表为活性边表(AET)。 对每一条扫描线都建立一个与它相交的多边形的活性边表(AET)。每个AET的一个节点代表一条活性边，它包含三项内容1. x -当前扫描。

3、线与这条边交点的x坐标；2. x -该边与当前扫描线交点到下一条扫描线交点的x增量；3. ymax -该边最高顶点相交的扫描线号。每条扫描线的活性边表中的活性边节点按照各活性边与扫描线交点的x值递增排序连接在一起。当扫描线y移动到下一条扫描线y = y+1时，活性边表需要更新，即删去不与新扫描线相交的多边形边，同时增加与新扫描线相交的多边形边，并根据增量法重新计算扫描线与各边的交点x。当多边形新边表ET构成后，按下列步骤进行：1 对每一条扫描线i，初始化ET表的表头指针ETi；2 将ymax = i的边放入ETi中；3 使y =多边形最低的扫描线号；4 初始化活性边表AET为空；5 循环，直到。

4、AET和ET为空。l 将新边表ET中对应y值的新边节点插入到AET表。l 遍历AET表，将两两配对的交点之间填充给定颜色值。l 遍历AET表，将 ymax= y的边节点从AET表中删除，并将ymax y的各边节点的x值递增x；并重新排序。l y增加1。三、 程序源代码#include graphics.h#define WINDOW_HEIGHT 480#define NULL 0#include alloc.h#include stdio.h#include dos.h#include conio.htypedef struct tEdge /*typedef是将结构定义成数据类型*/ in。

5、t ymax; /* 边所交的最高扫描线号 */float x; /*当前扫描线与边的交点的x值 */float dx; /*从当前扫描线到下一条扫描线之间的x增量*/struct tEdge *next;Edge;typedef struct pointint x,y;POINT;/*将结点插入边表的主体函数*/void InsertEdge(Edge *list,Edge *edge)/*活性边edge插入活性边表list中*/ Edge *p,*q=list;p=q-next; /*记住q原来所指之结点*/while(p!=NULL) /*按x值非递减顺序增加边表*/if(edge-xx。

6、) /*要插入的边的x较大不应该在当前插入*/p=NULL; else /*要插入的边的x较小应该在当前插入*/q=p;p=p-next;edge-next=q-next; /*使欲插入之结点edge指向q原来所指之结点*/q-next=edge; /*使q指向插入之结点*/int yNext(int k,int cnt,POINT *pts) /*对于多边形中的某个顶点序号k(0,1.6)，返回下一顶点的纵坐标,如果这2个顶点所在边是 水平的，则顺延，即返回第(k+2)个顶点的纵坐标),cnt是顶点个数+1,pts指向多边形顶点结构体的指针*/int j;if(k+1)(cnt-1)/*当前。

7、顶点为最后一个顶点，则下一个顶点为第0个顶点 */j=0;elsej=k+1; /*当前顶点不是最后一个顶点，下一个顶点为数组下标加一*/while(ptsk.y=ptsj.y)/*扫描线扫过平行顶点，需分情况找到当前顶点下下个顶点*/if(j+1)(cnt-1)j=0;elsej+;return(ptsj.y); /*返回下一个顶点的y值 */* 计算增量，修改AET*/*生成边表结点，并插入到边表中的主体函数*/void MakeEdgeRec(POINT lower,POINT upper,int yComp,Edge *edge,Edge *edges) /*把边结点edge,放到lo。

8、wer.y扫描线所在的边结点指针数组edges中 */edge-dx=(float)(upper.x-lower.x)/(upper.y-lower.y);edge-x=lower.x;if(upper.yymax=upper.y-1; /*缩短上层顶点*/*奇点，应该把这点当作两个点而分开，所以把y的最大值减一，向下移动*/elseedge-ymax=upper.y; /*不是奇点，不需改变y值 */insertEdge(edgeslower.y,edge); /*插入一个边缘扫描线，插入到列表 */ /*创建边表的主体函数*/void BuildEdgeList(int cnt,POINT。

9、 *pts,Edge *edges) /*建立新边表,cnt:多边形顶点个数+1,edges:指向活性边结点的指针数组*/Edge *edge;POINT v1,v2;int i,yPrev=ptscnt-2.y;/*当前顶点的前一个顶点的y值，在当前顶点不是奇点时使用该参数*/v1.x=ptscnt-1.x;v1.y=ptscnt-1.y;for(i=0;inext; /*查找当前扫描线对应的y桶*/while(p) /*y桶不空*/q=p-next; /*找到最后一个边结点，插入*/InsertEdge(active,p); /*把更新后的边表重新插入边表中保存*/p=q;/*填充一对交点。

10、的主体函数*/void FillScan(int scan,Edge *active,int color) /*填充扫描线:填充扫描线上,且在下一结点到再下一结点之间的点*/Edge *p1,*p2;int i;p1=active-next;while(p1)p2=p1-next;for(i=p1-x;ix;i+)putpixel(int)i,scan,color); /*画出图形内部的点*/p1=p2-next; /*活性表的下一条边表 */void DeleteAfter(Edge *q) /*删除链表中结点,删除边结点q的后续结点p*/ Edge *p=q-next;q-next=p-n。

11、ext; /*删除结点*/free(p);/* 删除 y=ymax 的边 */*填充完后，更新活动边表的主体函数*/void UpdateActiveList(int scan,Edge *active) /*删除扫描线scan完成交点计算的活性边,同时更新交点x域*/Edge *q=active,*p=active-next;while(p)if(scan=p-ymax) /*扫描线超过边的最大y值，此条边的节点应该删掉*/p=p-next;deleteAfter(q);else /*扫描线未超过边的最大y值，相应的x值增加*/p-x=p-x+p-dx;q=p;p=p-next;/*对活性边。

12、表结点重新排序的主体函数*/void ResortActiveList(Edge *active) /*活性边表active中的结点按x域从小到大重新排序*/Edge *q,*p=active-next;active-next=NULL;while(p)q=p-next;InsertEdge(active,p); /*把更新后的边表重新插入边表中保存 */p=q;/*多边形填充的主体程序*/void ScanFill(int cnt,POINT *pts,int color) /*填充函数,输入:多边形顶点个数+1=cnt, 指向多边形顶点的指针数组pts*/Edge *edgesWINDOW。

13、_HEIGHT,*active;int i,scan,scanmax=0,scanmin=WINDOW_HEIGHT;for(i=0;iptsi.y)scanmin=ptsi.y;for(scan=scanmin;scannext=NULL;BuildEdgeList(cnt,pts,edges); /*建立有序边表*/active=(Edge *)malloc(sizeof(Edge);active-next=NULL;for(scan=scanmin;scannext) /*活性边表不为空*/FillScan(scan,active,color); /*填充当前扫描线*/UpdateAct。

14、iveList(scan,active); /*更新活化边表*/ResortActiveList(active); /*重排活化边表*/*开始菜单*/void main() POINT pts7; /*保存数组*/int gdrive=DETECT,gmode;pts0.x=100;pts0.y=40; /*多边形顶点x、y坐标*/pts1.x=220;pts1.y=140;pts2.x=280;pts2.y=80;pts3.x=350;pts3.y=300;pts4.x=200;pts4.y=380;pts5.x=50;pts5.y=280;pts6.x=100;pts6.y=40; /*合。

15、并桶中的新边，按次序插入到 AET 中*/ initgraph(&gdrive,&gmode,C:TC3.0BGI); /*设置graphic模式*/ScanFill(7,pts,2);getch();四、 实验结果图1 用有序边表算法生成的多边形五、 总结与体会实验步骤1) 分析多边形区域扫描线填充算法的原理，确定算法流程1 初始化：构造边表，AET表置空2 将第一个不空的ET表中的边插入AET表3 由AET表取出交点进行配对(奇偶)获得填充区间，依次对这些填充区间着色4 y=yi+1时，根据x=xi+1/k修改AET表所有结点中交点的x坐标。同时如果相 应的ET表不空，则将其中的结点插入A。

16、ET表，形成新的AET表5 AET表不空，则转(3)，否则结束。2) 编程实现1 首先确定多边形顶点和ET/AET表中结点的结构2 编写链表相关操作(如链表结点插入、删除和排序等)3 根据1)中的算法结合上述已有的链表操作函数实现多边形区域扫描线填充的主体功能4 编写主函数，测试该算法通过运用C语言环境下的图像显示设置，本次实验我学会了多边形区域扫描线填充的有序边表算法，设计相关的数据结构(如链表结构、结点结构等)，并将实现的算法应用于任意多边形的填充，为深一步的学习做好了铺垫。六、 参考文献1张家广 等编著.计算机图形学(第3版).北京：清华大学出版社,1998年9月.2陈传波，陆枫主编，计算机图形学基础，电子工业出版社，2002年3月。

实验报告

实验目的

1、掌握有序边表算法填充多边形区域;

2、理解多边形填充算法的意义；

3、增强C语言编程能力。

算法原理介绍

根据多边形内部点的连续性知：一条扫描线与多边形的交点中，入点和出点之间所 有点都是多边形的内部点。所以，对所有的扫描线填充入点到出点之间所有的点就可填 充多边形。

判断扫描线上的点是否在多边形之内，对于一条扫描线，多边形的扫描转换过程可 以分为四个步骤：

(1)求交：计算扫描线与多边形各边的交点；

(2)排序：把所有交点按x值递增顺序排序；

(3)配对：第一个与第二个，第三个与第四个等等；每对交点代表扫描线与多边 形的一个相交区间；

(4)着色：把相交区间内的象素置成多边形颜色，把相交区间外的象素置成背景 色。

p1,p3,p4,p5属于局部极值点，要把他们两次存入交点表中。如扫描线y=7上的交

点中，有交点(2,7,13)，按常规方法填充不正确，而要把顶点(7,7)两次存入交点表中 (2,7,7,13)。p2, p6为非极值点，则不用如上处理。

为了提高效率，在处理一条扫描线时，仅对与它相交的多边形的边进行求交运算。 把与当前扫描线相交的边称为活性边，并把它们按与扫描线交点x坐标递增的顺序存放 在一个链表中，称此链表为活性边表(AET)。

对每一条扫描线都建立一个与它相交的多边形的活性边表(AET。每个AET的一

个节点代表一条活性边，它包含三项内容

x -当前扫描线与这条边交点的x坐标；

△ x -该边与当前扫描线交点到下一条扫描线交点的x增量；

ymax -该边最高顶点相交的扫描线号。

每条扫描线的活性边表中的活性边节点按照各活性边与扫描线交点的x值递增排序

连接在一起。

当扫描线y移动到下一条扫描线y = y+1时，活性边表需要更新，即删去不与新扫 描线相交的多边形边，同时增加与新扫描线相交的多边形边，并根据增量法重新计 算扫描线与各边的交点x。

当多边形新边表ET构成后，按下列步骤进行：

对每一条扫描线i，初始化ET表的表头指针ET[i];

将ymax = i的边放入ET[i]中；

使y=多边形最低的扫描线号；

初始化活性边表AET为空；

循环，直到AET和ET为空。

将新边表ET中对应y值的新边节点插入到AET表。

遍历AET表，将两两配对的交点之间填充给定颜色值。

遍历AET表，将ymax= y的边节点从AET表中删除，并将ymax> y的各边节点 的x值递增△ x;并重新排序。

y增加1。

三、程序源代码

#in elude "graphics.h"

#defi ne WINDOW_HEIGHT 480

#define NULL 0

#i nclude "alloc.h"

#i nclude "stdio.h"

#i nclude "dos.h"

#i nclude "con io.h"

typedefstruct tEdge/*typedef是将结构定义成数据类型*/

{ int ymax;/*边所交的最高扫描线号*/

float x;/*当前扫描线与边的交点的x值*/

float dx;/*从当前扫描线到下一条扫描线之间的 x增量*/

struct tEdge *n ext;

}Edge;

typedef struct poi nt{int x,y;}POINT;/*将结点插入边表的主体函数

typedef struct poi nt{int x,y;}POINT;

/*将结点插入边表的主体函数*/

void In sertEdge(Edge *list,Edge *edge)/* {

Edge *p,*q=list;

p=q->n ext;/*

while(p!=NULL)/*

{

if(edge->xx) /* p=NULL;

else/*

{q=p; p=p->n ext;

}

}

edge->n ext=q->n ext; q->n ext=edge;

}

活性边edge插入活性边表list中*/

记住q原来所指之结点*/ 按x值非递减顺序增加边表*/ 要插入的边的x较大不应该在当前插入*/

要插入的边的x较小应该在当前插入*/

/* 使欲插入之结点edge指向q原来所指之结点*/

/*使q指向插入之结点*/

int yNext(int k,int cnt,POINT *pts)

/*对于多边形中的某个顶点序号k(0,1...6)，返回下一顶点的纵坐标,如果这2 个顶点所在边是 水平的，则顺延，即返回第(k+2)个顶点的纵坐标),cnt是顶点个数 +1,pts指向多边形顶点结构体的指针*/

{

int j;

if((k+1)>(cnt-1))/*当前顶点为最后一个顶点，则下一个顶点为第0个顶点*/

j=0;

e