河南理工大学计算机图形学3章3区域填充

第3章基本图形生成

§3.1直线图形生成§3.2圆及二次曲线生成§3.3区域图形填充

§3.4字符生成§3.5反走样第3章二维图形生成技术

本次课内容：§3.3区域填充算法§3.4字符的生成

线框多边形物体填充多边形物体区域填充应用实例§3.3区域填充算法单色填充图案填充区域填充解决的问题：1描述区域边界曲线围成的区域，可用多边形逼近；2确定待填充的象素检查每一像素是否位于多边形区域内；3确定填充要素颜色或图案。名词解释

1)区域：一组相邻而且又相连的像素，而且具有相同属性的封闭区域。

3)区域填充：在区域内确定种子，并将这种属性扩展到整个区域的过程。

4）边界的种类：①单域②复合域

2)种子：具有一定填充属性单位的像素或像素组合。

5)区域的建立方式：内定区域边界定义区域。

①内定区域：在所定义的区域内所有的像素具有相同的属性（如颜色等）,而区域边界上的像素着不同的颜色；

②边界定义区域：区域以的属性来划分，区域内的像素和边界上的像素可具有不同得属性。边界定义区域内定区域

区域填充算法：1)种子填充算法——内部一个点出发简单种子算法扫描线种子算法2)扫描线填充算法——扫描线顺序

有序边表算法边填充算法3)图案填充算法——填充有结构的图形影线填充算法图像填充算法1区域的连通性3.3.1种子填充算法

4连通区域：从区域上的一点出发，通过访问已知点的4邻接点，在不越出区域的前提下，遍历区域内的所有象素点。

8连通区域：从区域上的一点出发，通过访问已知点的8邻接点，在不越出区域的前提下，遍历区域内的所有象素点。prrrrprrrrrrrr4－连通区域8－连通区域4连通与8连通区域区别2基本原理假设区域内一点已知，以此为种子。从该点出发，沿着区域连通的方向搜索与种子相邻且位于区域内的点，使其成为新种子，接着继续递归地搜索下去。若相邻的点不在区域内，即达到边界。常用算法有：简单种子填充算法、扫描线种子填充算法。连通区域扩展过程4连通填充8连通填充3简单种子算法1）算法步骤

①确定边界和边界的属性；②确定区域填充的属性值；③测试区域内一点的属性值，判定其是否在填充区域内；且未被填充，④若在区域内且和边界的属性值不同，赋予填充属性，以此点为种子；⑤沿四连通(或八连通)方向，测试其它点；⑥每测试一个点都与边界属性比较，若不同，赋予填充属性；⑦若相同，即到达边界，然后转向另一种连通方向；⑧整个点的测试采用循环递归的方式实现。扫描线种子填充算法过程2)

算法特点

①算法简单，便于硬件实现；

②像素测试效率比较低。4扫描线种子填充算法

1）算法的基本思想用扫描线从上到下扫描由点线段构成的多段多边形。每根扫描线与多边形各边产生一系列交点。将交点按照x(或y)坐标进行分类，然后成对取出，作为两个端点，用填充颜色画水平直线。扫描线填充算法：y－x算法x－y算法。2）算法的基本过程：

当给定种子点时，首先填充种子点所在的扫描线上的位于给定区域的一个区段，然后确定与这一区段相通的上下两条扫描线上位于给定区域内的区段，并依次保存下来。反复这个过程，直到填充结束。3.3.2多边形填充算法1多边形表示顶点表示：用多边形的顶点序列描述多边形。P1P2P4P0点阵表示：用位于多边形内的像素几何描述多边形。把多边形的顶点表示转换为点阵表示。或求出位于多边形内的各个像素点并赋予特定的属性。射线法任作一条射线,求其与边界的交点,若交点数为偶数,则该点在边界之外,否则在边界之内。12323412主要技术处理

①区域内点的快速测试方法

累计角度法

计算各边的夹角的和，若代数和为零，该点∈域外；若代数和为2π，该点∈域内。ABCDEPABCDEPP1P2P3P4P5

②重合点的处理:当扫描线和边界相交于边界顶点时，同时产生两个交点，通常采用“起闭终开”或“起开终闭”。③水平边处理：水平边不参加求交计算，跳过。[P1,p2)[P4，P5)[P2,p3)[P5,p1)活性边的构造方法：a)去除水平边，根据环方向进行开闭区间处理；b)按照端点的Y坐标大小对各边进行排序，按从大到小把边存入线性表中；c)在线性表中加入两个指针，形成活性边表。

⑤活性边表实时刷新a)调整两个指针值，确保扫描正常进行；b)调整两个指针之间边元素值；④构造活性边表活性边：与当前扫描线相交的边界线的边。3扫描线算法利用区域的连续性、扫描线的连续性、边界连续性。

1）区域连续性梯形：部分在内，部分在外，间隔排列。

2）扫描线连续性交点：⑴交点数为偶数;

⑵奇到偶数点在域内，偶到奇数点在域外。123456123456789101234

3）边界连续性把边界的端点按其y坐标排列：

y0,y1,…..,yiyik≥yik+1

0≤

k≤

n-1

设扫描线,y=d，y10≤

d≤

y2,交点有4个。

⑴交点数相等；⑵同编号的点位于同一条边上。

4扫描线算法实现步骤

1)把区域边界顶点按Y坐标排序；

2）确定扫描线的区间；

3）构建边界边的活性边表；

4）求交点；

5）交点排序；

6）交点配对；

7）填充颜色012345671234567yx88910P4P1P2P3P5I1I2I3I4扫描线区间3.3.3边填充算法

优点：★最适合于有帧缓存的显示器★可按任意顺序处理多边形的边★仅访问与该边有交点的扫描线上右方的像素，算法简单缺点：★对复杂图形，每一像素可能被访问多次，输入/输出量大★图形输出不能与扫描同步进行，只有全部画完才能打印

也称正负相消法，对每一扫描线依次求其与边的交点，对交点右侧像素取补，并多边形每条边排序。3.3.4影线填充算法图案填充：是在区域内填充有规律的图形组合，而图形可以分解成一族或数族不同类型的线型组合。影线填充：用一组等距离的平行线(其各段的起、终端点位于区域边界上)填充区域的过程。填充图案影线填充的算法步骤

1)影线描述

影线采用斜截式定义：y=kx+b2)区域边界描述

①区域边界描述应考虑如下因素：a)边界线的形状，直线和圆弧；b)边界线的位置；c)区域的类型，单域和复域；d)边界是封闭性。

②引入假想线，使复域转变成闭合的单域；

③

引入特征值，描述边界线的形状和类型；D△yyx具体定义如下：a)直线：特征值为0；b)假想线：特征值为10-10；c)圆弧：特征值为±R，R＞0：圆弧由起点逆时针画至终点，R＜0：圆弧由起点顺时针画至终点。

④引入有序顶点环表，表示不同类型边界线的位置点。a)直线段用起、终端点表示；b)圆弧用起、圆心点和终点表示；

⑤特征值赋值：a)直线由终点携带边界特征值；b)圆弧的特征值由圆心点携带；c)圆弧的终点特征值赋为10-10；d)第一点起点的特征值为边界轮廓顶点总数。3）确定影线的总数①求出边界上通过各顶点影线在y轴上的截距bi；②求出bi中最大和最小截距bmax和bmin；③求出△b的值，△b=/cosa，a为影线的倾角；④确定影线的总数，N=(bmax－bmin)/△b；4）确定第一条影线的位置

取第一条影线的截距，b=bmin+△b，而第一条影线的方程，y=kx+b。5）求影线与边界的交点若把第i条影线记为L(i)，轮廓线佣R(j)表示，交点为P(i,j)时，则有：P(i，j)=L(i)∩R(j)对于P(i，j)，存在有三种类型的点：①无效点：交点在边界有效线段之外，应当舍弃；②有效点：交点在边界有效线段上，应当纪录；③双重点：交点位于边界顶点处，采用“起闭终开”规则，舍弃重点，记录有效点。

7）显示影线段影线交点的顺序规律：奇点—偶点时，影线段在域内，显示影线段；偶点—奇点时，影线段在域外，不显示影线段。

6)对交点进行排序按照坐标大小，对有效交点进行从小到大的顺序排队。3.3.5图象填充区域算法1图像方式:1）位图不透明方式；2）位图透明方式；3）像素图填充方式。YX图像空间区域定义1）使图像在水平和垂直方向周期性排列，直到所定义的区域全被不重迭的图像所覆盖。2）假定每个图像的尺寸是M×N，通过周期性排列构成图像空间。3）建立区域中各像素与图像各单元间的映射关系。2处理过程3建立映射关系1)整个绘图空间与图像空间的1-1映射2)区域局部坐标空间与图像空间的1-1映射(x,y)(x1,y1)3.4字符的生成字符生成方法有点阵式、矢量式和编码式。常用的字符有：①

ASCII码，②

汉字字符，

③

其它字符，④其它工程专用符号。1.点阵式字符

1)定义模式点阵式字符将字符表示为一个矩形点阵，由点阵中点的不同值表达字符的形状。

常用的点阵大小有8×8、16×16、32×32等等。2）点阵字符的处理

①使用点阵式字符时，需将字库中的矩形点阵拷贝到buffer中指定的单元中去。

②在拷贝过程中，施加变换，可获得简单的变化。

③作任意角度的旋转等复杂变换，比较困难。2.矢量式字符矢量式字符将字符表达为一个点坐标的序列，相邻两点表示一条矢量，字符的形状便由矢量序列刻划。

1）定义字模采用正方形网格8×8、32×32、64×64、128×128等。

2）定义字符表达字符的内容：定位点坐标、走笔方向和标志等。采用两种形式

①

矢量编码：用有限的方向编码来表达一个字符，通常采用8个或16个方向。

②

专用编码：采用专用的编码和格式，每一个编码定义了特定的操作和特定的格式。3）按结构保存编码。4）定义并保存结束标志。5）建立字符库。以AutoCAD形文件的定义为例：文件格式：一个标题行，若干个描述行。标题行：*〈形编号〉，<字节大小>，<形名称>。描述行:由编码和操作数组成。采用矢量编码，最高位0表示为十六进制数，后面两位表示高四位和低四位，高四位表示矢量长度，低四位表示画矢量的方向。二极管符号的定义形式如下：*133，11，EJG040,044,04c,062,04c,040,048,04c,066,04c,0。从字库的字模中读出字符，在显示器或打印机上输出。①计算或确定字符或字符串左下角点的坐标；②读取字符数据：根据编码取出每个节点的数据；读取字符数据时，应注意考虑以下参数：a)字符的定位点，一般选择字符的左下角点；b)确定字符的类型和字符的个数；c)字符的方向，方向常选取与x轴的夹角，单位为度；d)确定字符宽度和字符高度，通常选择高度作参数，把宽度看成高度的比例系数；e)确定字符的间距，间距选择字符高度的比例系数；③进行坐标变换和处理：可以对字符进行任何操作，如放大、旋转，甚至透视等；④在确定的位置显示字符。6）显示字符3.5反走样3.5.1.光栅图样走样现象

1）阶梯状的图形或边界

2）图形细节失真

2）狭小图形的遗失与动态图形的闪烁用离散量表示连续量引起的失真现象称之为走样。3.5.2.常用反走样技术

用于减少或消除走样现象的技术称为反走样。1提高分辨率（过取样，或后滤波）

1）从硬件考虑提高分辨率

★方法简单，但代价非常大。

★帧缓存容量则增加到原来的4倍，扫描转换要花4倍时间。

★只能减轻而不能消除锯齿问题2）从软件考虑提高分辨率1111算术平均122142121加权平均

★高分辨率计算，低分辨率显示把每个像素分为四个子像素，扫描转换算法求得各子像素的灰度值，然后对四像素的灰度值简单平均，作为该像素灰度值。★像素细分技术，相当于后置滤波

只能减轻，不能消除2区域取样（或前滤波）

1）简单的区域取样在整个像素区域内进行采样，该技术称为区域取样。利用一种求相交区域的近似面积的离散计算方法：(1)将屏幕象素分割成n个更小的子象素，(2)计算中心落在直线段内的子象素的个数m，(3)m/n为线段与象素相交区域面积的近似值。特点：(1)直线段像素亮度与其重叠区域的面积成正比；(2)相同面积重叠区域的像素灰度值或颜色值相同；(3)不适用动态图形显示。1）加权区域取样

假想一个连续的加权曲面（或过滤函数）覆盖象素。当直线条经过该象素时，该象素的灰度值是在二者重叠区域上对滤波器（过滤函数）进行积分的积分值。特点：(1)接近理想直线的象素将被分配更多的灰度值；(2)相邻两个象素的滤波器相交，有利于缩小直线条上相邻象素的灰度差。常用过滤函数内容回顾：

作业：

1.认