非零环绕数规则
• 环绕数初始为零； • 从位置P作不经过 顶点的射线； • 多边形从右至左穿 过射线，加1； • 多边形从左至右穿 过射线，减1； • 非零为内部点；
举例：
种子填充算法
区域：用点阵形式表示的填充图形，是像素的集合。 区域可采用内点表示和边界表示两种表示形式。 内点表示法，指区域内的所有像素着同一颜色；
i1
a
i1
i
a
其中 x
b 为常数， a
交点数的处理
• 多边形Pi的顶点可分为两类：如果(yi-1 - yi)(yi+1 - yi)≥0，则称顶点Pi为局 部最高点或最低点，按两个交点计算， 否则按一个交点计算。
水平边处理
• 不计算水平边和 扫描线的交点
数据结构与实现步骤
• 输入参数 顶点数和顶点坐标 • 数据结构 有序边表 活化边表
(1) 求交：计算扫描线与多边形各边的交点；
(2) 排序：把所有交点按x值递增顺序排序； (3) 配对：第一个与第二个，第三个与第四 个等等；每对交点代表扫描线与多边形的一 个相交区间；
(4)填色：把相交区间内的像素置成多边形 颜色，把相交区间外的像素置成背景色。
交点计算
为了提高速度，假定当前扫描线与多边形某一条边的交点的 x 坐标为 xi ，则下一条扫描线与该边的交点不要重新计算，而是 通过增加一个增量△x来获得。具体方法是： 设该边的直线方程为：ax+by+c=0； 若y＝yi，x=xi；则当y = yi+1= yi+1时， yi+1 yi b 1 (xi,yi) x ( b y c ) x ;
扫描线种子填充算法
简单种子填充算法原理和程序都很简单，但由于多次递归， 费时、费内存，效率不高。为了减少递归次数，提高效率可 以采用扫描线种子填充算法。 算法的基本过程如下：当给定种子点 (x,y)时，首先填充种子 点所在扫描线上的位于给定区域的一个区段，然后确定与这 一区段相连通的上、下两条扫描线上位于给定区域内的区段， 并依次保存下来。反复这个过程，直到填充结束。
活化边表
把与当前扫描线 相交的边称为活 化边，并把它们 按与扫描线交点 X坐标递增的顺 序存放在一个链 表中，形成活化 边表。
表结构
算法中采用较灵活的数据结构。它由边的分有序边 表ET（Edge Table）和边的活化边表AEL（Active Edge Table ）两部分组成。 表结构ET和AET中的基本元素为多边形的边。边 的结构由以下四个域组成： ymax 边的上端点的y坐标； x 在ET中表示边的下端点的x坐标，在 AET中则表示边与扫描线的交点的坐标； Δx 边的斜率的倒数； next 指向下一条边的指针。
第四讲 区域填充
计算机图形学中，多边形区域有两种重要的表示方法：顶 点表示和点阵表示。 所谓顶点表示，即是用多边形的顶点序列来表示多边形。 这种表示直观、几何意义强、占内存少，易于进行几何变换， 但由于它没有明确指出哪些像素在多边形内，故不能直接用 于区域填充。 所谓点阵表示，则是用位于多边形内的像素集合来刻画多 边形。这种表示丢失了许多几何信息，但便于进行填充。 根据区域的定义，可以采用不同的填充算法，其中最具代表 性的是：适应于顶点表示的扫描线类算法和适应于点阵表示 的种子填充类算法。
P 2 P1
扫描线6
7
2
4
7
8
-1
^
多边形填充的算法流程
void polyfill (polygon, color)
{
for (各条扫描线，标识为i) { 初始化新边表头指针NET [i]； 把ymin = i 的边放进边表NET [i]； } y = 最低扫描线号； 初始化活性边表AET为空； for (各条扫描线i)
举例：
有序边表
^ 7
P5 P1
2 4 ^
P2 P1 7 ^ 6 ^ 3 8 -1 ^
(Ymax, x,Δ x, next)
P4 P5 2 0 ^ P3 P2 5 6 0.5 ^
P3 P4 6 -2
•活化边表
AET指针 扫描线1 3
P3 P4 6 -2 P3 P4 5
P3 P2 6 0.5 P3 P2 ^
•简单边界 通过扫描线与边 界交点确定填充 区域
•复杂边界 从内部指定位置 开始填充，递归 填充直至边界
扫描线算法
扫描线多边形区域填充算法基本原理是，待填充区域按 Y方向 (X 方向亦可 ) 扫描线顺序扫描生成。具体实现时，首先按扫描 线顺序，计算扫描线与多边形的相交区间；再用要求的颜色填 充这些区间内的像素，即完成这一条扫描线的填充工作。区间 的端点可以通过计算扫描线与多边形边界线的交点获得。对于 一条扫描线，多边形的填充过程可以分为四个步骤：
} }
扫描线算法
• 特点：算法效率较高。
• 缺点：对各种表的维持和排序开销太 大，适合软件实现而不适合硬件实现。
内外测试
• 目标：鉴别非标准多边形的内部区域 自相交多边形。 • 方法 奇偶规则 非零环绕数规则
奇偶规则
• 从位置P作不经 过顶点的射线 • 计算射线穿过多 边形的边数 • 奇数为内部点， 否则为外部点
4 3 2 1
5 4 3 2 1
5 4 3 2 1
4 3 2 1
4 3 2 1
3 2 1
区域填充的扫描线算法可由下列四个步骤实现：
(1)初始化：堆栈置空。将种子点(x，y)入栈；
(2)出栈：若栈空则结束。否则取栈顶元素(x，y)，以y作为当 前扫描线；
(3)填充并确定种子点所在区段：从种子点(x，y)出发，沿当 前扫描线向左、右两个方向填充，直到边界。分别标记区段 的左、右端点坐标为xl和xr； (4)并确定新的种子点：在区间[xl，xr]中检查与当前扫描线y 上、下相邻的两条扫描线上的像素。若存在非边界、未填充 的像素，则把每一区间的最右像素作为种子点压入堆栈，返 回第(2)步。
四个方向运动 八个方向运动
四连通区域
八连通区域
算法原理：
填充区域边界 以一种颜色指 定，从区域的 一个内部点开 始，由内至外 绘制直到边界。 适用于单色边 界的填充。
四连通的局限性
简单的种子填充算法
设(x,y)为内点表示的4连通区域内的一点，oldcolor为区域的 原色，要将整个区域填充为新的颜色newcolor。内点表示的 4连通区域的递归填充算法: void FloodFill4(int x,int y,int oldcolor,int newcolor) { if(GetPixel(x,y)==oldcolor) { SetPixel(x,y,newcolor); FloodFill4(x,y+1,oldcolor,newcolor); FloodFill4(x,y-1,oldcolor,newcolor); FloodFill4(x-1,y,oldcolor,newcolor); FloodFill4(x+1,y,oldcolor,newcolor); } }
有序边表
• 有序边表的构建
按顶点输入顺序依次形 成边，存储到每条最小 Y值所对应的扫描线位 置（水平边除外），相 同最小Y值的边按较低 顶点X值的升序排列。
有序边表结构
typedef struct tEage{ int yUpper; float xIntersect; float dxPerScan; struct tEage *next; } Eage
边界表示法，则是指区域的边界点着同一颜色。
表示内点
表示边界点
区域填充算法要求区域是连通的，因为只有在连通区域中，才 可能将种子点的颜色扩展到区域内的其它点。区域可分为4向 连通区域和8向连通区域。
4向连通区域指的是从区域上一点出发，可通过四个方向， 即上、下、左、右移动的组合，在不越出区域的前提下，到达 区域内的任意像素； 8向连通区域指的是从区域内每一像素出发，可通过八个方 向，即上、下、左、右、左上、右上、左下、右下这八个方向 的移动的组合来到达。
AET指针 扫描线2
AET指针 扫描线3 6
3
4
P 4 P5 2
-2
5
6.5 0.5
P3 P2
^
0
5
7
0.5பைடு நூலகம்
^
(Ymax, x,Δ x, next)
AET指针 扫描线4 AET指针 6
P4 P5 2 0 5
P 3 P2 7.5 0.5 P 2 P1 ^
P4 P5
扫描线5
AET指针
6
2
0
7
8
-1
^
P5 P1
边界表示的4连通区域的递归填充算法:
void BoundaryFill4(int x,int y,int boundarycolor,int newcolor) { int color; if(color!=newcolor && color!=boundarycolor) { SetPixel(x,y,newcolor); BoundaryFill4 (x,y+1, boundarycolor,newcolor); BoundaryFill4 (x,y-1, boundarycolor,newcolor); BoundaryFill4 (x-1,y, boundarycolor,newcolor); BoundaryFill4 (x+1,y, boundarycolor,newcolor); } }
{
把新边表NET[i]中的边结点用插入排序法插入AET表，使之按x坐标递增顺序排列； 遍历AET表，把配对交点区间上的像素(x, y)，用drawpixel (x, y, color)改写像素颜色 值； 遍历AET表，把y max= i的结点从AET表中删除，并把y max > i结点的x值递增x；