计算机图形学扫描线种子填充算法.pptVIP

计算机图形学讲义第2章 基本图形的生成与计算 黄可坤 嘉应学院 主要内容 逐点判断填充算法 种子填充算法 2.1 深度递归的种子填充算法 2.2 扫描线种子填充算法 扫描线多边形填充算法 １.逐点判断填充算法 区域填充的基本(初级)方法:逐点判断填充算法 逐点判断绘图窗口内的每一个像素； 若在区域的内部：用指定的属性设置该点； 否则不予处理； 取矩形R(x1≤x≤x2,y1≤y≤y2)，使R包围D， 则逐点判断填充算法如下： for(y=y1;y=y2;y++) for(x=x1;x=x2;x++) if(inside(D,x,y)) drawpixel(x,y,color); 上述算法原理简单、实用，但效率低；效率低的原因是没有考虑各象素之间的联系，孤立地考察象素与区域的关系，使得几十万甚至几百万个象素都要一一判别，每次判别又要多次求交点，需要做大量的乘除运算，花费很多时间。 　　如何判断点在多边形的内或外？即包含性检查。 2.种子填充算法 2.1 深度递归的种子填充算法 2.2 扫描线种子填充算法 2.1 深度递归的种子填充算法 3、内点(x,y)的检测条件 (1) if(getpixel(x,y)!=边界色 getpixel(x,y)!=填充色) (2) if(getpixel(x,y)!=背景色) 这两个条件任何一个都可以用来检测象素点(x,y)是不是尚未填充。推荐使用条件(1)进行象素点检测。 深度递归的种子填色算法的优缺点 种子填充的递归算法原理和程序都很简单，容易理解。 但由于多次递归，费时、费内存，效率不高。太大的区域会由于递归太深而不能运行。虽然也可利用栈非递归实现，但也有同样的问题。 可以考虑利用队列进行广度优先填色，但是也是逐点判断，而且要重复判断一个点很多次，效率也不高。 为了减少递归次数，提高效率可以采用采用扫描线种子算法。 2.2 扫描线种子填充算法 算法的基本过程如下：当给定种子点(x,y)时，首先填充种子点所在扫描线上的位于给定区域的一个区段，然后确定与这一区段相连通的上、下两条扫描线上位于给定区域内的区段，确定新种子点，并依次保存下来。反复这个过程，直到填充结束。 上述算法对于每一个待填充区段，只需压栈一次；而在递归算法中，每个象素都需要压栈。因此，扫描线填充算法提高了区域填充的效率。 扫描线种子填充算法的具体步骤 初始化：堆栈置空。将种子点（x，y）入栈。 出栈：若栈空则结束。否则取栈顶元素（x，y），以y作为当前扫描线。 填充并确定种子点所在区段：从种子点（x，y）出发，沿当前扫描线向左、右两个方向填充，直到非内部。分别标记区段的左、右端点坐标为xl和xr。 并确定新的种子点：在区间[xl，xr]中检查与当前扫描线y上、下相邻的两条扫描线上的象素。若存在非边界、未填充的象素，则把每一区间的最右象素作为种子点压入堆栈，返回第（2）步。 动画演示 扫描线种子填充算法特点 该算法考虑了扫描线上象素的相关性，种子象素不再代表一个孤立的象素，而是代表一个尚未填充的区段。 进栈时，只将每个区段选一个象素进栈（每个区段最右边或最左边的象素），这样解决了堆栈溢出的问题。 种子出栈时，则填充整个区段。 这样有机的结合：一边对尚未填充象素的登记（象素进栈），一边进行填充（象素出栈），既可以节省堆栈空间，又可以实施快速填充。 3.扫描线多边形填充算法 扫描线多边形区域填充算法是按扫描线顺序，计算扫描线与多边形的相交区间，再用要求的颜色显示这些区间的象素，即完成填充工作。 区间的端点可以通过计算扫描线与多边形边界线的交点获得。 对于一条扫描线，多边形的填充过程可以分为四个步骤： （1）求交：计算扫描线与多边形各边的交点； （2）排序：把所有交点按x值递增顺序排序； （3）配对：第一个与第二个，第三个与第四个等等；每对交点代表扫描线与多边形的一个相交区间; （4）填色：把相交区间内的象素置成多边形颜色; 为了方便活性边表的建立与更新，我们为每一条扫描线建立一个新边表（NET）,存放在该扫描线第一次出现的边。也就是说， 若某边的较低端点为ymin， 则该边就放在扫描线ymin 的新边表中。 扫描线多边形填充算法的主要步骤 建立NET(NewEdgeList) 从最低扫描线开始到最高扫描线循环： 建立或调整AET(ActiveEdgeList)； 按照AET中的接点顺序填充； 动画演示 扫描线多边形填充算法的特点 该算法充分利用多边形的边相关性和扫描线的相关性，使用ET表对多边形的非水平边进行登记； 用AET表的建立和更新来支持填充