计算机图形学 第四讲 区域填充

第四讲

区域填充计算机图形学中，多边形区域有两种重要的表示方法：顶点表示和点阵表示。所谓顶点表示，即是用多边形的顶点序列来表示多边形。这种表示直观、几何意义强、占内存少，易于进行几何变换，但由于它没有明确指出哪些像素在多边形内，故不能直接用于区域填充。所谓点阵表示，则是用位于多边形内的像素集合来刻画多边形。这种表示丢失了许多几何信息，但便于进行填充。根据区域的定义，可以采用不同的填充算法，其中最具代表性的是：适应于顶点表示的扫描线类算法和适应于点阵表示的种子填充类算法。

复杂边界从内部指定位置开始填充，递归填充直至边界简单边界通过扫描线与边界交点确定填充区域扫描线算法扫描线多边形区域填充算法基本原理是，待填充区域按Y方向(X方向亦可)扫描线顺序扫描生成。具体实现时，首先按扫描线顺序，计算扫描线与多边形的相交区间；再用要求的颜色填充这些区间内的像素，即完成这一条扫描线的填充工作。区间的端点可以通过计算扫描线与多边形边界线的交点获得。对于一条扫描线，多边形的填充过程可以分为四个步骤：(1)求交：计算扫描线与多边形各边的交点；(2)排序：把所有交点按x值递增顺序排序；(3)配对：第一个与第二个，第三个与第四个等等；每对交点代表扫描线与多边形的一个相交区间；(4)填色：把相交区间内的像素置成多边形颜色，把相交区间外的像素置成背景色。为了提高速度，假定当前扫描线与多边形某一条边的交点的x坐标为xi，则下一条扫描线与该边的交点不要重新计算，而是通过增加一个增量△x来获得。具体方法是：设该边的直线方程为：ax+by+c=0；若y＝yi，x=xi；则当y=yi+1=yi+1时，其中为常数，yiyi+1(xi,yi)交点计算交点数的处理多边形Pi的顶点可分为两类：如果(yi-1-yi)(yi+1-yi)≥0，则称顶点Pi为局部最高点或最低点，按两个交点计算，否则按一个交点计算。不计算水平边和扫描线的交点水平边处理数据结构与实现步骤输入参数顶点数和顶点坐标数据结构有序边表活化边表有序边表有序边表的构建按顶点输入顺序依次形成边，存储到每条最小Y值所对应的扫描线位置（水平边除外），相同最小Y值的边按较低顶点X值的升序排列。有序边表结构typedef

struct

tEage{int

yUpper;floatxIntersect;floatdxPerScan;struct

tEage*next;}Eage活化边表把与当前扫描线相交的边称为活化边，并把它们按与扫描线交点X坐标递增的顺序存放在一个链表中，形成活化边表。算法中采用较灵活的数据结构。它由边的分有序边表ET（EdgeTable）和边的活化边表AEL（ActiveEdgeTable

）两部分组成。表结构ET和AET中的基本元素为多边形的边。边的结构由以下四个域组成：

ymax

边的上端点的y坐标；

x在ET中表示边的下端点的x坐标，在AET中则表示边与扫描线的交点的坐标；

Δx边的斜率的倒数；

next指向下一条边的指针。

表结构举例：724^P5P178-1^P2P1620^P4P536-2P3P4560.5^P3P2^^^(Ymax,x,Δx,next)

有序边表活化边表34-2P3P456.50.5^P3P2扫描线2AET指针620P4P5570.5^P3P2扫描线3AET指针(Ymax,x,Δx,next)36-2P3P4560.5^P3P2扫描线1AET指针620P4P557.50.5^P3P2扫描线4AET指针620P4P578-1^P2P1扫描线5AET指针724P5P178-1^P2P1扫描线6AET指针

voidpolyfill(polygon,color){

for(各条扫描线，标识为i) {

初始化新边表头指针NET[i]；把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值递增x；

}}多边形填充的算法流程扫描线算法特点：算法效率较高。缺点：对各种表的维持和排序开销太大，适合软件实现而不适合硬件实现。内外测试目标：鉴别非标准多边形的内部区域自相交多边形。方法奇偶规则非零环绕数规则奇偶规则从位置P作不经过顶点的射线计算射线穿过多边形的边数奇数为内部点，否则为外部点非零环绕数规则环绕数初始为零；从位置P作不经过顶点的射线；多边形从右至左穿过射线，加1；多边形从左至右穿过射线，减1；非零为内部点；举例：种子填充算法区域：用点阵形式表示的填充图形，是像素的集合。区域可采用内点表示和边界表示两种表示形式。内点表示法，指区域内的所有像素着同一颜色；边界表示法，则是指区域的边界点着同一颜色。区域填充算法要求区域是连通的，因为只有在连通区域中，才可能将种子点的颜色扩展到区域内的其它点。区域可分为4向连通区域和8向连通区域。4向连通区域指的是从区域上一点出发，可通过四个方向，即上、下、左、右移动的组合，在不越出区域的前提下，到达区域内的任意像素；8向连通区域指的是从区域内每一像素出发，可通过八个方向，即上、下、左、右、左上、右上、左下、右下这八个方向的移动的组合来到达。

四个方向运动八个方向运动四连通区域八连通区域算法原理：填充区域边界以一种颜色指定，从区域的一个内部点开始，由内至外绘制直到边界。适用于单色边界的填充。四连通的局限性voidFloodFill4(intx,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);}}设(x,y)为内点表示的4连通区域内的一点，oldcolor为区域的原色，要将整个区域填充为新的颜色newcolor。内点表示的4连通区域的递归填充算法:

简单的种子填充算法voidBoundaryFill4(intx,int

y,int

boundarycolor,int

newcolor){

intcolor; 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);}}边界表示的4连通区域的递归填充算法:

扫描线种子填充算法简单种子填充算法原理和程序都很简单，但由于多次递归，费时、费内存，效率不高。为了减少递归次数，提高效率可以采用扫描线种子填充算法。算法的基本过程如下：当给定种子点(x,y)时，首先填充种子点所在扫描线上的位于给定区域的一个区段，然后确定与这一区段相连通的上、下两条扫描线上位于给定区域内的区段，并依次保存下来。反复这个过程，直到填充结束。1234123451234512341234123区域填充的扫描线算法可由下列四个步骤实现：(1)初始化：堆栈置空。将种子点(x，y)入栈；