假定当前扫描线与多边形某一条边的交点的x坐标为x,则下一条扫描线与该边的交点不要重计算,只要加 个增量△x。设该边的直线方程为:ax+by+c=0 若y=y,x=xi:则当y=yin时, 1(by1 b △x 其中 为常数 另外使用增量法计算时,我们需要知道一条边何时不再与下一条扫描线相交,以便及时把它从活性边表 中删除出去。综上所述,活性边表的结点应为对应边保存如下内容:第1项存当前扫描线与边的交点坐标x 值:第2项存从当前扫描线到下一条扫描线间ⅹ的增量Δx:第3项存该边所交的最高扫描线号y 为了方便活性边表的建立与更新,我们为每一条扫描线建立一个新边表(NET),存放在该扫描线第一次出 现的边。也就是说,若某边的较低端点为y細,则该边就放在扫描线y的新边表中。 76543210 P4P5 P5P6 28·5+1.57 )|8A [2|07A 532-[51313∧ 图2.3.4上图所示各条扫描线的新边表NET 算法过程 void polyfill (polygon, color) int color;多边形 polygon for(各条扫描线i) 初始化新边表头指针NET 把ymn=i的边放进边表NET[i] y=最低扫描线号: 初始化活性边表AET为空; for(各条扫描线i) 把新边表NET[订]中的边结点用插入排序法插入AET表,使之按x坐标递增顺序排列 遍历AET表,把配对交点区间(左闭右开)上的象素(x,y),用 drawpixel(x,y, color)改写象素颜 色值 遍历AET表,把y==i的结点从AET表中删除,并把ymx>i结点的x值递增x 若允许多边形的边自相交,则用冒泡排序法对AET表重新排序 1 /* polyfill * 扫描线与多边形顶点相交时,必须正确的交点的取舍 扫描线与多边形相交的边分处扫描线的两侧,则计一个交点,如点P,P6 扫描线与多边形相交的边分处扫描线同侧,且y<y,y<ym,则计2个交点(填色),如P2。若y>yi y,则计0个交点(不填色),如P1 扫描线与多边形边界重合(当要区分边界和边界内区域时需特殊处理),则计1个交点。 具体实现时,只需检查顶点的两条边的另外两个端点的y值。按这两个y值中大于交点y值的个数是0,1,2 来决定。 计算机图形学第二章第23页共27页计算机图形学 第二章 第 23 页 共 27 页 假定当前扫描线与多边形某一条边的交点的 x 坐标为 x，则下一条扫描线与该边的交点不要重计算，只要加 一个增量△x。设该边的直线方程为：ax+by+c=0； 若 y＝yi，x=x i；则当 y = y i+1时， 其中 为常数， 另外使用增量法计算时，我们需要知道一条边何时不再与下一条扫描线相交，以便及时把它从活性边表 中删除出去。综上所述，活性边表的结点应为对应边保存如下内容：第 1 项存当前扫描线与边的交点坐标 x 值；第 2 项存从当前扫描线到下一条扫描线间 x 的增量 x；第 3 项存该边所交的最高扫描线号 ymax。 为了方便活性边表的建立与更新，我们为每一条扫描线建立一个新边表（NET）,存放在该扫描线第一次出 现的边。也就是说，若某边的较低端点为 ymin，则该边就放在扫描线 ymin的新边表中。 图 2.3.4 上图所示各条扫描线的新边表 NET 算法过程 void polyfill (polygon, color) int color;多边形 polygon; { for (各条扫描线 i ) { 初始化新边表头指针 NET [i]； 把 y min = i 的边放进边表 NET [i]; } y = 最低扫描线号； 初始化活性边表 AET 为空； for (各条扫描线 i ) { 把新边表 NET[i]中的边结点用插入排序法插入 AET 表，使之按 x 坐标递增顺序排列； 遍历 AET 表，把配对交点区间(左闭右开)上的象素(x, y)，用 drawpixel (x, y, color) 改写象素颜 色值； 遍历 AET 表，把 y max= i 的结点从 AET 表中删除，并把 y max > i 结点的 x 值递增 x； 若允许多边形的边自相交，则用冒泡排序法对 AET 表重新排序； } } /* polyfill */ 扫描线与多边形顶点相交时，必须正确的交点的取舍。 · 扫描线与多边形相交的边分处扫描线的两侧，则计一个交点，如点 P5，P6。 · 扫描线与多边形相交的边分处扫描线同侧，且 yi<yi-1，yi<yi+1，则计 2 个交点(填色)，如 P2。 若 yi>yi-1， yi>yi+1，则计 0 个交点(不填色)，如 P1。 · 扫描线与多边形边界重合 (当要区分边界和边界内区域时需特殊处理)，则计 1 个交点。 具体实现时，只需检查顶点的两条边的另外两个端点的 y 值。按这两个 y 值中大于交点 y 值的个数是 0,1,2 来决定