7-8二维填充图元生成.

中国地质大学(北京)地球物理与信息技术学院生成填充图元的上机实习利用VC++，编程实现多边形的填充地点：教五319时间：周一下午6-7节周二下午6-7节中国地质大学(北京)地球物理与信息技术学院第五章二维填充图元生成一般步骤•确定那些像素位于填充图元的内部；•确定以什么颜色填充这些像素；中国地质大学(北京)地球物理与信息技术学院中国地质大学(北京)地球物理与信息技术学院5.1扫描转换矩形5.2扫描转换多边形逐点判断法、扫描线算法、边缘填充算法5.3区域填充（种子填充法）递归填充算法、扫描线算法5.4以图像填充区域5.5字符的表示与输出5.6混淆与反混淆主要内容5.1扫描转换矩形•方法：voidFillRectangle(Rectangle*rect,intcolor){intx,y;for(y=rect-ymin;y=rect-ymax;y++)for(x=rect-xmin;x=rect-xmax;x++)SetPixel(x,y,color);}/*endofFillRectangle()*/•问题：–矩形是简单的多边形，那么为什么要单独处理矩形？比一般多边形可简化计算。应用非常多，窗口系统。–边界如何处理？•原则：左闭右开，下闭上开属于谁？5.2扫描转换多边形•多边形的表示方法–顶点表示–点阵表示–扫描转换多边形：将顶点表示形式转换成点阵表示形式–三种方法：逐点判断法；扫描线算法；边缘填充法voidFillPolygonPbyP(Polygon*P,intpolygonColor){intx,y;for(y=ymin;y=ymax;y++)for(x=xmin;x=xmax;x++)if(IsInside(P,x,y))SetPixel(x,y,polygonColor);elseSetPixel(x,y,backgroundColor);}/*endofFillPolygonPbyP()*/#defineMAX100Typedefstruct{intPolygonNum;//多边形顶点个数Pointvertexces[MAX];//多边形顶点数组}Polygon;//多边形结构1、逐点判断法•逐个判断绘图窗口内的像素：•如何判断点在多边形的内外关系？1）射线法2）累计角度法3）编码法IsInside(P,x,y)1）射线法•步骤：1.从待判别点v发出射线2.求交点个数K3.K的奇偶性决定了点与多边形的内外关系•奇异情况处理射线与多边形顶点相交时，如何算交点的个数2）累计角度法•步骤1.从V点向多边形P顶点发出射线，形成有向角2.计算有向角的和，得出结论•离散计算方法：编码方法之内位于之外位于，PvPvnii,200i3）编码方法：累计角度方法的离散方法Step:a.预处理，测试点在边上否？b.V为原点作局部坐标系,对象限按逆时针（或顺时针）编码；c.顶点编码Ipi，d.边编码。PiPi+1:△PiPi+1=Ipi+1-Ipie.计算∑△PiPi+1（其中△PnPn+1=△PnP0)：若∑为0,V在P外；若∑为+/-4，V在P内；逐点判断法程序简单，速度太慢，效率低。P0P1P2vv01232、扫描线算法–目标：利用相邻像素之间的连贯性，提高算法效率–处理对象：非自交多边形（边与边之间除了顶点外无其它交点）–基本原理•一条扫描线与多边形的边有偶数个交点步骤(对于每一条扫描线):(1)求交点(2)交点排序(3)交点配对，填充区段。–边的连贯性（确定交点）•第一类交点：位于同一条边上的后继交点（中点算法）•第二类交点：新出现的边与扫描线的交点（顶点即为交点）–交点的取整规则•要求：使生成的像素全部位于多边形之内–用于线画图元扫描转换的四舍五入原则导致部分像素位于多边形之外，从而不可用规则如下假定非水平边与扫描线y=e相交，交点的横坐标为x规则(1)：x为小数时，即交点落于扫描线上两个相邻像素之间(a)交点位于左边之上，向右取整(b)交点位于右边之上，向左取整•规则(2)：交点位于边界上时，象素的取舍问题。边界象素：规定落在右上边界的象素不予填充。具体实现时，只要对扫描线与多边形的相交区间左闭右开•规则(3)：扫描线与多边形的顶点相交时，交点的取舍，保证交点正确配对。解决方法：检查两相邻边在扫描线的哪一侧。只要检查顶点的两条边的另外两个端点的Y值，两个Y值中大于交点Y值的个数是0，1，2，来决定取0，1，2个交点。1）活化边：与当前扫描线相交的边。按交点x（x相同则按deltax）递增顺序存放在一个链表中；该链表称作活化边表（AEL)。-算法所涉及的数据结构：Ymax:与边相交的最高扫描线号X：在AEL中表示当前扫描线与边的交点的x坐标；初值为边的下端点的x坐标(存于ET中)。△X：边的斜率的倒数Nextedge:指向下一条边的指针AEL与ET的结点信息（p75）：typedefstruct{intymax;floatx,deltax;Edge*nextEdge;}Edge;P0P1P2P3P4P5P6672）边的分类表（ET）按照边的下端点y坐标对非水平边进行分类的指针数组。下端点y坐标值等于i的边属于第i类，同一类边按x(x相同则按deltax）递增的顺序排列。typedefstruct{intymax;floatx,deltax;Edge*nextEdge;}Edge;边的分类表的作用是避免盲目求交。当处理一条扫描线时，为了求出它与多边形边的所有交点，必须将它与所有的边进行求交测试。而实际上只有某几条边与该扫描线有交点。边的分类表正是用来排除不必要的求交测试的。例如，P76图4.17–算法1)、建立ET；2)、将扫描线纵坐标y的初值置为ET中非空元素的最小序号，如在上图中，y=1；3)、置AEL为空；4)、执行下列步骤直至ET和AEL都为空．a、如ET中的第y类非空，则将其中的所有边取出并插入AEL中；b、如果有新边插入AEL，则对AEL中各边排序；c、对AEL中的边两两配对，（1和2为一对，3和4为一对，…），将每对边中x坐标按规则取整，获得有效的填充区段，再填充．d、将当前扫描线纵坐标y值递增1；e、将AEL中满足y=ymax边删去（因为每条边被看作下闭上开的）；f、对AEL中剩下的每一条边的x递增deltax，即x=x+deltax．3、边缘填充算法▼求余运算：假定A为一个正整数，则M的余定义为A–M,记为。计算机中取A为n位能表示的最大整数。即，A=0xFFFFFFFF▼由来：光栅图形中，如果某区域已着上值为M的颜色值做偶数次求余运算，该区域颜色不变；而做奇数次求余运算，则该区域颜色变为值为的颜色。这一规律应用于多边形扫描转换，就为边缘填充算法。▼求余运算可用异或显示模式实现。▼算法基本思想：对于每条扫描线和每条多边形边的交点，将该扫描线上交点右方的所有像素取余。AXorMMAMMM算法(1)（以扫描线为中心的边缘填充算法）a、将当前扫描线上的所有象素着上颜色；b、求余：for(i=0;i=m;i++)在当前扫描线上，从横坐标为Xi的交点向右求余；M算法(2)（以边为中心的边缘填充算法）a、将绘图窗口的背景色置为；b、对多边形的每一条非水平边做：从该边上的每个象素开始向右求余；M边缘填充算法•适合用于具有帧缓存的图形系统。处理后，按扫描线顺序读出帧缓存的内容，送入显示设备。•优点：算法简单•缺点：对于复杂图形，每一象素可能被访问多次，输入/输出的量比扫描线算法大得多。5.3区域填充•区域：点阵表示的填充图形，像素集合•表示方法：内点表示、边界表示•内点表示–枚举出区域内部的所有像素–内部的所有像素着同一个颜色–边界像素着不同的颜色•边界表示–枚举出边界上所有的像素–边界上的所有像素着同一颜色–内部像素着不同的颜色区域填充–对区域重新着色的过程–将指定的颜色从种子点扩展到整个区域的过程–区域填充算法要求区域是连通的•连通性4连通、8连通•4连通：•8连通•4连通与8连通区域的区别–连通性：4连通可看作8连通区域，但对边界有要求–对边界的要求–边界表示的4连通区域voidBoundaryFill4(intx,inty,intboundaryColor,intnewColor){intcolor;color=GetPixel(x,y);if((color!=boundaryColor)&&(color!=newColor)){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);}}/*endofBoundaryFill4()*/1、递归填充算法–内点表示的4连通区域voidFloodFill4(intx,inty,intoldColor,intnewColor){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);}}/*endofFloodFill4()*/取(x,y)为种子点中国地质大学(北京)地球物理与信息技术学院(x,y)中国地质大学(北京)地球物理与信息技术学院中国地质大学(北京)地球物理与信息技术学院(1)有些像素会入栈多次，降低算法效率；栈结构占空间。(2)递归执行，算法简单，但效率不高，区域内每一象素都引起一次递归，进/出栈，费时费内存。•改进算法，减少递归次数，提高效率。方法之一使用扫描线填充算法；递归填充法的缺点：2、扫描线算法•扫描线算法–目标：减少递归层次–适用于内点表示的4连通区域–基本过程：当给定种子点时，首先填充种子点所在的扫描线上的位于给定区域的一个区段，然后确定与这一区段相通的上下两条扫描线上位于给定区域内的区段，并依次保存下来。反复这个过程，直到填充结束。1)、确定并填充种子区段；2)、初始化：将种子区段压入堆栈；3)、如果堆栈为空，则算法结束；否则取栈顶元素（y,xLeft,xRight）出栈，以纵坐标=y的扫描线为当前扫描线，[xLeft,xRight]为搜索区间；4)、在上下相邻的两扫描线上，确定和填充新的区段，并压入堆栽，重复(3)(4)。•算法步骤像素中的序号指它所在区段的堆栈位置5.4以图象填充区域•填充方式：–(1)位图不透明：若像素对应的位图单元为1，则以前景色显示该像素；若为0，则以背景色显示该像素；–(2)位图透明：若像素对应的位图单元为1，则以前景色显示该像素；若为0，则不做任何处理。–(3)按像素图方式填充•基本问题–关键是建立区域与图像间的对应关系–1：建立整个绘图空间与图像空间映射适用：动画中漫游图像•2：建立区域局部坐标空间与图像空间的映射适用：图像作为区域表面属性的情况。5.5字符的表示与输出点阵字符矢量字符自学！5.6.1混淆现象5.6.2反混淆方法非加权区域采样加权区域采样5.6反混淆方法5.6.1混淆现象混淆：用离散量(像素)表示连续的量(图形)而引起的失真，叫混淆或叫走样(aliasing)。光栅图形的混淆现象–阶梯状边界；–图形细节失真；–狭小图形遗失：动画序列中时隐时现，产生闪烁。混淆现象（1/3）•不光滑(阶梯状）的图形边界混淆现象（2/3）•图形细节失真混淆现象（3/3）•狭小图形的遗失与动态图形的闪烁•什么是反混淆–在图形显示过程中，用于减少或消除混淆现象的方法1）提高分辨率方法2）非加权区域采