二维填充图元生成

生成填充图元的上机实习利用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); else SetPixel(x,y,backgroundColor);}/*endofFillPolygonPbyP() */#defineMAX100Typedefstruct{intPolygonNum;//多边形顶点个数 Pointvertexces[MAX];//多边形顶点数组 }Polygon;//多边形结构1、逐点判断法逐个判断绘图窗口内的像素：北大计算机系多媒体与人机交互如何判断点在多边形的内外关系？1）射线法2）累计角度法3）编码法IsInside(P,x,y)1）射线法步骤：从待判别点v发出射线求交点个数KK的奇偶性决定了点与多边形的内外关系奇异情况处理射线与多边形顶点相交时，如何算交点的个数北大计算机系多媒体与人机交互2）累计角度法步骤从V点向多边形P顶点发出射线，形成有向角计算有向角的和，得出结论离散计算方法：编码方法北大计算机系多媒体与人机交互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内；逐点判断法程序简单，速度太慢，效率低。P0P1P2vv0123北大计算机系多媒体与人机交互2、扫描线算法目标：利用相邻像素之间的连贯性，提高算法效率处理对象：非自交多边形（边与边之间除了顶点外无其它交点）北大计算机系多媒体与人机交互基本原理一条扫描线与多边形的边有偶数个交点步骤(对于每一条扫描线):(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;P0P1P2P3P4P5P667北大计算机系多媒体与人机交互2）边的分类表（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的颜色值做偶数次求余运算，该区域颜色不变；而做奇数次求余运算，则该区域颜色变为值为 的颜色。这一规律应用于多边形扫描转换，就为边缘填充算法。▼求余运算可用异或显示模式实现。▼算法基本思想：对于每条扫描线和每条多边形边的交点，将该扫描线上交点右方的所有像素取余。北大计算机系多媒体与人机交互算法(1)（以扫描线为中心的边缘填充算法）a、将当前扫描线上的所有象素着上颜色；b、求余： for(i=0;i<=m;i++) 在当前扫描线上，从横坐标为Xi的交点向右求余；

北大计算机系多媒体与人机交互算法(2)（以边为中心的边缘填充算法） a、将绘图窗口的背景色置为； b、对多边形的每一条非水平边做： 从该边上的每个象素开始向右求余；北大计算机系多媒体与人机交互边缘填充算法适合用于具有帧缓存的图形系统。处理后，按扫描线顺序读出帧缓存的内容，送入显示设备。优点：算法简单缺点：对于复杂图形，每一象素可能被访问多次，输入/输出的量比扫描线算法大得多。北大计算机系多媒体与人机交互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）非加权区域采样 3）加权区域采样

5.6.2反混淆方法北大计算机系多媒体与人机交互1、提高分辨率的反混淆方法 方法简单，但代价非常大。

显示器的水平、竖直分辩率各提高一倍，则显示器的点距减少一倍，帧缓存容量则增加到原来的4倍，而扫描转换同样大小的图元却要花4倍时间。北大计算机系多媒体与人机交互2、非加权区域采样方法方法由来两点假设1、数学上，象素是抽象的点，它的面积为0，它的亮度由覆盖该点的图形的亮度所决定；2、直线段是数学上抽象直线段，它的宽度为0。现实像素的面积不为0；直线段的宽度至少为1个像素；假设与现实的矛盾是导致混淆出现的原因之一北大计算机系多媒体与人机交互2、非加权区域采样方法解决方法：改变直线段模型，由此产生算法方法步骤：1、将直线段看作具有一定宽度的狭长矩形；2、当直线段与某象素有交时，求出两者相交区域的面积；3、根据相交区域的面积，确定该象素的亮度值

关键：如何计算这个面积？北大计算机系多媒体与人机交互非加权区域采样方法--计算相交区域的面积DD.m面积=(m*D*D)/2D------m像素实际显示的灰度值==所得面积*该像素的最大灰度值北大计算机系多媒体与人机交互反混淆方法求相交区域的近似面积的离散计算方法1、将屏幕象素分割成n个更小的子象素；2、计算中心点落在直线段内的子象素的个数，记为k，3、k/n为线段与象素相交区域面积的近似值目的：简化计算n=16,k=3近似面积=3/16北大计算机系多媒体与人机交互方法性质：非加权区域采样方法1）直线段对一个像素亮度的贡献与两者相交区域的面积成正比，从而和像素中心点距直线段的距离成反比(因为像素中心点距直线段距离越元，相交区域的面积越小）；2）当直线段和某个像素不相交时，它对该像素的亮度无影响；3）相同面积的相交区域对像素的亮度贡献相同，而与这个相交区域落在像素内的位置无关。北大计算机系多媒体与人机交互3、加权区域采样方法改进非加权区域采样方法的第3条性质：相交区域对象素亮度的贡献依赖于该区域与象素中心的距离北大计算机系多媒体与人机交互加权区域采样方法权函数W(x,y)以象素A的中心