《扫描线填充算法讲解》由会员分享，可在线阅读，更多相关《扫描线填充算法讲解（21页珍藏版）》请在金锄头文库上搜索。
1、扫描线算法(Scan-Line Filling)扫描线算法适合对矢量图形进行区域填充，只需要直到多边形区域的几何位置, 不需要指定种子点，适合计算机自动进行图形处理的场合使用，比如电脑游戏 和三维CAD软件的渲染等等。对矢量多边形区域填充，算法核心还是求交。计算几何与图形学有关的几种 常用算法一文给出了判断点与多边形关系的算法-扫描交点的奇偶数判断 算法，利用此算法可以判断一个点是否在多边形内，也就是是否需要填充，但 是实际工程中使用的填充算法都是只使用求交的思想，并不直接使用这种求交 算法。究其原因，除了算法效率问题之外，还存在一个光栅图形设备和矢量之 间的转换问题。比如某个点位于非常靠近边
2、界的临界位置，用矢量算法判断这 个点应该是在多边形内，但是光栅化后，这个点在光栅图形设备上看就有可能 是在多边形外边（矢量点没有大小概念，光栅图形设备的点有大小概念），因 此，适用于矢量图形的填充算法必须适应光栅图形设备。扫描线算法的基本思想扫描线填充算法的基本思想是：用水平扫描线从上到下（或从下到上）扫描由 多条首尾相连的线段构成的多边形，每根扫描线与多边形的某些边产生一系列 交点。将这些交点按照x坐标排序，将排序后的点两两成对，作为线段的两个 端点，以所填的颜色画水平直线。多边形被扫描完毕后，颜色填充也就完成了。 扫描线填充算法也可以归纳为以下4个步骤：（1）求交，计算扫描线与多边形的交点
3、（2）交点排序，对第2步得到的交点按照x值从小到大进行排序；（3）颜色填充，对排序后的交点两两组成一个水平线段，以画线段的方式进 行颜色填充；（4）是否完成多边形扫描？如果是就结束算法，如果不是就改变扫描线，然 后转第1步继续处理；整个算法的关键是第1步，需要用尽量少的计算量求出交点，还要考虑交点是 线段端点的特殊情况，最后，交点的步进计算最好是整数，便于光栅设备输出 显示。观察多边形与扫描线的交点情况，可以得到以下两个特点：（1）每次只有相关的几条边可能与扫描线有交点，不必对所有的边进行求交 计算；（2）相邻的扫描线与同一直线段的交点存在步进关系，这个关系与直线段所 在直线的斜率有关；第一个
4、特点是显而易见的，为了减少计算量，扫描线算法需要维护一张由“活动 边”组成的表，称为“活动边表（AET） ”。例如扫描线4的“活动边表”由P1P2和P3P4两条边组成，而扫描线7的“活动边表”由P1P2、P6P1、P5P6和P4P5 四条边组成。第二个特点可以进一步证明，假设当前扫描线与多边形的某一条边的交点已经 通过直线段求交算法计算出来，得到交点的坐标为（x,y）,则下一条扫描线与 这条边的交点不需要再求交计算，通过步进关系可以直接得到新交点坐标为（x+ x, y + 1）。前面提到过，步进关系AX是个常量，与直线的斜率有关，下面 就来推导这个AX。假设多边形某条边所在的直线方程是：ax
5、+ by + c = 0,扫描线yi和下一条扫 描线yi+1与该边的两个交点分别是（召，yi）和（xi+1，yi+1），则可得到以下两 个等式：axi + byi + c = 0 （等式 1）axi+1 + byi+1 + c = 0 （等式 2）由等式1可以得到等式3：xi = -（byi + c） / a （等式 3）同样，由等式2可以得到等式4：Xj+i = -（byi+i + c） / a （等式 4）由等式4-等式3可得到xi+i - xi = -b 山+1 - y） / a由于扫描线存在yi+1 = yi + 1的关系，将代入上式即可得到：xi+1 一 xi = -b / a即ax
6、 = -b / a，是个常量（直线斜率的倒数）。“活动边表”是扫描线填充算法的核心，整个算法都是围绕者这张表进行处理的。 要完整的定义“活动边表”，需要先定义边的数据结构。每条边都和扫描线有个 交点，扫描线填充算法只关注交点的x坐标。每当处理下一条扫描线时，根据 x直接计算出新扫描线与边的交点x坐标，可以避免复杂的求交计算。一条边 不会一直待在“活动边表”中，当扫描线与之没有交点时，要将其从“活动边表”中 删除，判断是否有交点的依据就是看扫描线y是否大于这条边两个端点的y坐 标值，为此，需要记录边的y坐标的最大值。根据以上分析，边的数据结构可 以定义如下：65 typedef struet t
7、agEDGE66 67 double xi;68 double dx;69 int ymax;74 EDGE;根据EDGE的定义，扫描线4和扫描线7的“活动边表就分别如图（7）和图（8） 所示：图（7）扫描线4的活动边表图（8）扫描线7的活动边表前面提到过，扫描线算法的核心就是围绕“活动边表（AET）”展开的，为了方 便活性边表的建立与更新，我们为每一条扫描线建立一个“新边表（NET）”， 存放该扫描线第一次出现的边。当算法处理到某条扫描线时，就将这条扫描线 的噺边表”中的所有边逐一插入到“活动边表”中。噺边表”通常在算法开始时建 立，建立“新边表”的规则就是：如果某条边的较低端点（y坐标较小
8、的那个点） 的y坐标与扫描线y相等，则该边就是扫描线y的新边，应该加入扫描线y的 噺边表”。上例中各扫描线的噺边表”如下图所示：图（9）各扫描线的新边表讨论完“活动边表（AET） ”和噺边表（NET） ”，就可以开始算法的具体实现了, 但是在进一步详细介绍实现算法之前，还有以下几个关键的细节问题需要明确：（1）多边形顶点处理在对多边形的边进行求交的过程中，在两条边相连的顶点处会出现一些特殊情 况，因为此时两条边会和扫描线各求的一个交点，也就是说，在顶点位置会出 现两个交点。当出现这种情况的时候，会对填充产生影响，因为填充的过程是 成对选择交点的过程，错误的计算交点个数，会造成填充异常。假设多边
9、形按照顶点P1、P2和P3的顺序产生两条相邻的边，P2就是所说的 顶点。多边形的顶点一般有四种情况，如图（10）所展示的那样，分别被称为 左顶点、右顶点、上顶点和下顶点：左顶点F2P2(d)下顶点(c)上顶点图(10)多边形顶点的四种类型左顶点P1、P2和P3的y坐标满足条件：yl y2 y2 y3；上顶点P1、P2和P3的y坐标满足条件：y2 yl & y2 y3；下顶点P1、P2和P3的y坐标满足条件：y2 yl & y2 y3；对于左顶点和右顶点的情况，如果不做特殊处理会导致奇偶奇数错误，常采用 的修正方法是修改以顶点为终点的那条边的区间，将顶点排除在区间之外，也 就是删除这条边的终点，
10、这样在计算交点时，就可以少计算一个交点，平衡和 交点奇偶个数。结合前文定义的“边”数据结构：EDGE，只要将该边的ymax修 改为ymax - 1就可以了。对于上顶点和下顶点，一种处理方法是将交点计算做0个，也就是修正两条边 的区间，将交点从两条边中排除；另一种处理方法是不做特殊处理，就计算2 个交点，这样也能保证交点奇偶个数平衡。（2）水平边的处理水平边与扫描线重合，会产生很多交点，通常的做法是将水平边直接画出（填 充），然后在后面的处理中就忽略水平边，不对其进行求交计算。（3）如何避免填充越过边界线边界像素的取舍问题也需要特别注意。多边形的边界与扫描线会产生两个交点, 填充时如果对两个交点
11、以及之间的区域都填充，容易造成填充范围扩大，影响 最终光栅图形化显示的填充效果。为此，人们提出了“左闭右开”的原则，简单 解释就是，如果扫描线交点是1和9,则实际填充的区间是1,9），即不包括x 坐标是9的那个点。扫描线算法实现扫描线算法的整个过程都是围绕“活动边表（AET） ”展开的，为了正确初始化 “活动边表”，需要初始化每条扫描线的“新边表（NET） ”，首先定义“新边表”的 数据结构。定义“新边表”为一个数组，数组的每个元素存放对应扫描线的所有 噺边”。因此定义噺边表”如下：510 std:vector std:list slNet（ymax - ymin +）;ymax和ymin是多
12、边形所有顶点中y坐标的最大值和最小值，用于界定扫描线 的范围。sINet中的第一个元素对应的是ymin所在的扫描线，以此类推，最后 一个元素是ymax所在的扫描线。在开始对每条扫描线处理之前，需要先计算 出多边形的ymax和ymin并初始化噺边表”：503 void ScanLinePolygonFill（const Polygon& py, int color）504 505 assert（）;506506 int ymin = ;507 int ymax = ;508 GetPolygonMinMax（py, ymin, ymax）;509 std:vector std:list slNe
13、t(ymax - ymin +);510 InitScanLineNewEdgeTable(slNet, py, ymin, ymax);511 ush_front(e);344一345 else346 347 =;348 if =349 =- 1；350 else351 =;352 slNet - ymin.push_front(e);353 一354 355 356 多边形的定义Polygon和本系列第一篇计算几何与图形学有关的几种常用算 法一文中的定义一致，此处就不再重复说明。算法通过遍历所有的顶点获得 边的信息，然后根据与此边有关的前后两个顶点的情况确定此边的ymax是否 需要-1修正
14、。ps和pe分别是当前处理边的起点和终点，pss是起点的前一个 相邻点，pee是终点的后一个相邻点，pss和pee用于辅助判断ps和pe两个 点是否是左顶点或右顶点，然后根据判断结果对此边的ymax进行-1修正，算 法实现非常简单，注意与扫描线平行的边是不处理的，因为水平边直接在 Horizo nEdgeFill()函数中填充了。ProcessSca nLin eFill()函数开始对每条扫描线进行处理，对每条扫描线的处理 有四个操作，如下代码所示，四个操作分别被封装到四个函数中：467 void ProcessScanLineFill(std:vector std:list & slNet,
15、468 int ymin, int ymax, int color)469 470 std:list aet;471471 for(int y = ymin; y = ymax; y+)472 473 InsertNetListToAet(slNety - ymin, aet);474 FillAetScanLine(aet, y, color);475 /删除非活动边476 RemoveNonActiveEdgeFromAet(aet, y);477 /更新活动边表中每项的xi值，并根据xi重新排序478 UpdateAndResortAet(aet);479 480 InsertNetListToAet()函数负责将扫描线对应的所有新边插入到aet中，插入操 作到保证aet还是有序表，应用了插入排序的思想，实现简单，此处不多解释。 FillAetScanLine()函数执行具体的填充动作，它将aet中的边交点成对取出组成 填充区间，然后根据咗闭右开”的原则对每
