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

1、第第3 3章章 基本图形生成技术基本图形生成技术- -区域填充区域填充第3章- 2/40计算机图形学计算机图形学计算机科学与技术学院计算机科学与技术学院第第3 3章章 基本图形生成基本图形生成 3.1 3.1 直线图形生成直线图形生成3.2 3.2 圆及二次曲线生成圆及二次曲线生成 3.3 3.3 区域图形填充区域图形填充 3.4 3.4 字符生成字符生成3.5 3.5 反走样反走样 第第3 3章章 基本图形生成技术基本图形生成技术- -区域填充区域填充第3章- 3/40计算机图形学计算机图形学计算机科学与技术学院计算机科学与技术学院 本次课内容：本次课内容： 3.3 3.3 区域填充算法区域

2、填充算法 3.4 3.4 字符的生成字符的生成 线框多边形物体填充多边形物体区域填充应用实例第第3 3章章 基本图形生成技术基本图形生成技术- -区域填充区域填充第3章- 5/40计算机图形学计算机图形学计算机科学与技术学院计算机科学与技术学院3.3 3.3 区域填充算法区域填充算法单色填充单色填充图案填充图案填充区域填充解决的问题： 1 描述区域边界 曲线围成的区域，可用多边形逼近； 2 确定待填充的象素 检查每一像素是否位于多边形区域内； 3 确定填充要素 颜色或图案。第第3 3章章 基本图形生成技术基本图形生成技术- -区域填充区域填充第3章- 6/40计算机图形学计算机图形学计算机科学

3、与技术学院计算机科学与技术学院名词解释名词解释 1) 区域：一组相邻而且又相连的像素，而且具有相同属 性的封闭区域。 3) 区域填充：在区域内确定种子，并将这种属性扩展到 整个区域的过程。 4）边界的种类：单域 复合域 2) 种子：具有一定填充属性单位的像素或像素组合。第第3 3章章 基本图形生成技术基本图形生成技术- -区域填充区域填充第3章- 7/40计算机图形学计算机图形学计算机科学与技术学院计算机科学与技术学院 5) 区域的建立方式：内定区域 边界定义区域。 内定区域：在所定义的区域内所有的像素具有相同 的属性（如颜色等）,而区域边界上的像素着不 同的颜色； 边界定义区域：区域以的属性

4、来划分，区域内的像 素和边界上的像素可具有不同得属性。边界定义区域内定区域第第3 3章章 基本图形生成技术基本图形生成技术- -区域填充区域填充第3章- 8/40计算机图形学计算机图形学计算机科学与技术学院计算机科学与技术学院 区域填充算法：区域填充算法：1) 种子填充算法内部一个点出发 简单种子算法 扫描线种子算法2) 扫描线填充算法扫描线顺序 有序边表算法 边填充算法3) 图案填充算法填充有结构的图形 影线填充算法 图像填充算法第第3 3章章 基本图形生成技术基本图形生成技术- -区域填充区域填充第3章- 9/40计算机图形学计算机图形学计算机科学与技术学院计算机科学与技术学院1 区域的连

5、通性3.3.1 种子填充算法种子填充算法 4 4连通区域：连通区域：从区域上的一点出发，通过访问已知点的4邻接点，在不越出区域的前提下，遍历区域内的所有象素点。 8 8连通区域：连通区域：从区域上的一点出发，通过访问已知点的8邻接点，在不越出区域的前提下，遍历区域内的所有象素点。prrrrrrrr第第3 3章章 基本图形生成技术基本图形生成技术- -区域填充区域填充第3章- 10/40计算机图形学计算机图形学计算机科学与技术学院计算机科学与技术学院4 4连通区域连通区域8 8连通区域连通区域4连通与8连通区域区别第第3 3章章 基本图形生成技术基本图形生成技术- -区域填充区域填充第3章- 1

6、1/40计算机图形学计算机图形学计算机科学与技术学院计算机科学与技术学院2 基本原理 假设区域内一点已知，以此为种子。从该点出发，沿着区域连通的方向搜索与种子相邻且位于区域内的点，使其成为新种子，接着继续递归地搜索下去。若相邻的点不在区域内，即达到边界。常用算法有： 简单种子填充算法、 扫描线种子填充算法。第第3 3章章 基本图形生成技术基本图形生成技术- -区域填充区域填充第3章- 12/40计算机图形学计算机图形学计算机科学与技术学院计算机科学与技术学院连通区域扩展过程连通区域扩展过程4连通填充连通填充8连通填充连通填充第第3 3章章 基本图形生成技术基本图形生成技术- -区域填充区域填充

7、第3章- 13/40计算机图形学计算机图形学计算机科学与技术学院计算机科学与技术学院3 简单种子算法 1）算法步骤 确定边界和边界的属性； 确定区域填充的属性值； 测试区域内一点的属性值，判定其是否在填充区域内；且未被填充， 若在区域内且和边界的属性值不同，赋予填充属性，以此点为种子； 沿四连通(或八连通)方向，测试其它点； 每测试一个点都与边界属性比较，若不同，赋予填充属性； 若相同，即到达边界，然后转向另一种连通方向； 整个点的测试采用循环递归的方式实现。第第3 3章章 基本图形生成技术基本图形生成技术- -区域填充区域填充第3章- 14/40计算机图形学计算机图形学计算机科学与技术学院计

8、算机科学与技术学院扫描线种子填充算法过程扫描线种子填充算法过程第第3 3章章 基本图形生成技术基本图形生成技术- -区域填充区域填充第3章- 15/40计算机图形学计算机图形学计算机科学与技术学院计算机科学与技术学院 2) 算法特点 算法简单，便于硬件实现； 像素测试效率比较低。4 扫描线种子填充算法扫描线种子填充算法 1）算法的基本思想 用扫描线从上到下扫描由点线段构成的多段多边形。每根扫描线与多边形各边产生一系列交点。将交点按照x(或y)坐标进行分类，然后成对取出，作为两个端点，用填充颜色画水平直线。 扫描线填充算法：yx算法 xy算法。 第第3 3章章 基本图形生成技术基本图形生成技术-

9、 -区域填充区域填充第3章- 16/40计算机图形学计算机图形学计算机科学与技术学院计算机科学与技术学院2）算法的基本过程： 当给定种子点时，首先填充种子点所在的扫描线上的位于给定区域的一个区段，然后确定与这一区段相通的上下两条扫描线上位于给定区域内的区段，并依次保存下来。反复这个过程，直到填充结束。第第3 3章章 基本图形生成技术基本图形生成技术- -区域填充区域填充第3章- 17/40计算机图形学计算机图形学计算机科学与技术学院计算机科学与技术学院3.3.2 多边形填充算法多边形填充算法1 多边形表示 顶点表示：用多边形的顶点序列描述多边形。P1P2P4P0 点阵表示：用位于多边形内的像素

10、几何描述多边形。 把多边形的顶点表示转换为点阵表示。或求出位于多边形内的各个像素点并赋予特定的属性。第第3 3章章 基本图形生成技术基本图形生成技术- -区域填充区域填充第3章- 18/40计算机图形学计算机图形学计算机科学与技术学院计算机科学与技术学院射射 线线 法法 任作一条射线,求其与边界的交点,若交点数为偶数偶数,则该点在边界之外,否则在边界之内。 1 12 23 32 23 34 41 1 2 2 主要技术处理主要技术处理 区域内点的快速测试方法 第第3 3章章 基本图形生成技术基本图形生成技术- -区域填充区域填充第3章- 19/40计算机图形学计算机图形学计算机科学与技术学院计算

11、机科学与技术学院累计角度法累计角度法 计算各边的夹角的和，若代数和为零，该点域外；若代数和为2，该点域内。ABCDEPABCDEP第第3 3章章 基本图形生成技术基本图形生成技术- -区域填充区域填充第3章- 20/40计算机图形学计算机图形学计算机科学与技术学院计算机科学与技术学院P1P2P3P4P5 重合点的处理:当扫描线和边界相交于边界顶点时，同时产生两个交点，通常采用 “起闭终开”或“起开终闭” 。 水平边处理： 水平边不参加求交计算，跳过。第第3 3章章 基本图形生成技术基本图形生成技术- -区域填充区域填充第3章- 21/40计算机图形学计算机图形学计算机科学与技术学院计算机科学与

12、技术学院 活性边的构造方法： a) 去除水平边，根据环方向进行开闭区间处理； b) 按照端点的Y坐标大小对各边进行排序，按从大到小 把边存入线性表中； c) 在线性表中加入两个指针，形成活性边表。 活性边表实时刷新 a) 调整两个指针值，确保扫描正常进行； b) 调整两个指针之间边元素值； 构造活性边表活性边：与当前扫描线相交的边界线的边。第第3 3章章 基本图形生成技术基本图形生成技术- -区域填充区域填充第3章- 22/40计算机图形学计算机图形学计算机科学与技术学院计算机科学与技术学院 3 3 扫描线算法扫描线算法 利用区域的连续性、扫描线的连续性、边界连续性。 1）区域连续性 梯形：部

13、分在内，部分在外，间隔排列。 2）扫描线连续性 交点： 交点数为偶数; 奇到偶数点在域内，偶到奇数点在域外。123456第第3 3章章 基本图形生成技术基本图形生成技术- -区域填充区域填充第3章- 23/40计算机图形学计算机图形学计算机科学与技术学院计算机科学与技术学院123456789101234 3）边界连续性 把边界的端点按其y坐标排列： y0,y1,.,yi yikyik+1 0 k n-1 设扫描线,y=d ， y10 d y2, 交点有4个。第第3 3章章 基本图形生成技术基本图形生成技术- -区域填充区域填充第3章- 24/40计算机图形学计算机图形学计算机科学与技术学院计算

14、机科学与技术学院 4 4 扫描线算法实现步骤扫描线算法实现步骤 1) 把区域边界顶点按Y坐标排序； 2）确定扫描线的区间； 3）构建边界边的活性边表； 4）求交点； 5）交点排序； 6）交点配对； 7）填充颜色012345671234567yx88910P4P1P2P3P5I1I2I3I4扫描线区间第第3 3章章 基本图形生成技术基本图形生成技术- -区域填充区域填充第3章- 25/40计算机图形学计算机图形学计算机科学与技术学院计算机科学与技术学院3.3.3 边填充算法边填充算法 优点优点：最适合于有帧缓存的显示器可按任意顺序处理多边形的边仅访问与该边有交点的扫描线上右方的像素，算法简单缺点

15、：缺点：对复杂图形，每一像素可能被访问多次，输入/输出量大图形输出不能与扫描同步进行，只有全部画完才能打印 也称正负相消法，对每一扫描线依次求其与边的交点，对交点右侧像素取补，并多边形每条边排序。P5P1P2P3P4P5P1P2P3P4P5P1P2P3P4P5P1P2P3P4P5P1P2P3P4(a)(b)(c)(d)(e)第第3 3章章 基本图形生成技术基本图形生成技术- -区域填充区域填充第3章- 26/40计算机图形学计算机图形学计算机科学与技术学院计算机科学与技术学院3.3.4影线填充算法影线填充算法 图案填充：是在区域内填充有规律的图形组合，而图形可以分解成一族或数族不同类型的线型组

16、合。影线填充：用一组等距离的平行线(其各段的起、终端点位于区域边界上) 填充区域的过程。 填充图案第第3 3章章 基本图形生成技术基本图形生成技术- -区域填充区域填充第3章- 27/40计算机图形学计算机图形学计算机科学与技术学院计算机科学与技术学院 1) 1) 影线描述影线描述 影线采用斜截式定义：y=kx+b2) 区域边界描述 区域边界描述应考虑如下因素： a) 边界线的形状，直线和圆弧； b) 边界线的位置； c) 区域的类型，单域和复域； d) 边界是封闭性。 引入假想线，使复域转变成闭合的单域； 引入特征值，描述边界线的形状和类型；D Dy yy yx x第第3 3章章 基本图形生

17、成技术基本图形生成技术- -区域填充区域填充第3章- 28/40计算机图形学计算机图形学计算机科学与技术学院计算机科学与技术学院具体定义如下： a) 直线：特征值为0； b) 假想线：特征值为10-10； c) 圆弧：特征值为R，R0：圆弧由起点逆时针 画至终点，R0：圆弧由起点顺时针画至终点。 引入有序顶点环表，表示不同类型边界线的位置点。 a) 直线段用起、终端点表示； b) 圆弧用起、圆心点和终点表示； 特征值赋值： a) 直线由终点携带边界特征值； b) 圆弧的特征值由圆心点携带； c) 圆弧的终点特征值赋为10-10； d) 第一点起点的特征值为边界轮廓顶点总数。 第第3 3章章 基

18、本图形生成技术基本图形生成技术- -区域填充区域填充第3章- 29/40计算机图形学计算机图形学计算机科学与技术学院计算机科学与技术学院3）确定影线的总数确定影线的总数 求出边界上通过各顶点影线在y轴上的截距bi； 求出bi中最大和最小截距bmax和bmin； 求出b的值，b=/cosa，a为影线的倾角； 确定影线的总数， N=(bmaxbmin)/b；4）确定第一条影线的位置确定第一条影线的位置 取第一条影线的截距，b= bmin+b， 而第一条影线的方程，y=kx+b。5）求影线与边界的交点求影线与边界的交点 若把第i条影线记为L(i)，轮廓线佣R(j)表示，交点为P(i,j)时，则有：

19、P(i，j)=L(i)R(j)第第3 3章章 基本图形生成技术基本图形生成技术- -区域填充区域填充第3章- 30/40计算机图形学计算机图形学计算机科学与技术学院计算机科学与技术学院对于P(i，j)，存在有三种类型的点： 无效点：交点在边界有效线段之外，应当舍弃； 有效点：交点在边界有效线段上，应当纪录； 双重点：交点位于边界顶点处，采用“起闭终开”规 则，舍弃重点，记录有效点。 7）显示显示影线段影线段 影线交点的顺序规律： 奇点偶点时，影线段在域内，显示影线段； 偶点奇点时，影线段在域外，不显示影线段。 6) 对交点进行排序对交点进行排序 按照坐标大小，对有效交点进行从小到大的顺序排队。

20、第第3 3章章 基本图形生成技术基本图形生成技术- -区域填充区域填充第3章- 31/40计算机图形学计算机图形学计算机科学与技术学院计算机科学与技术学院3.3.5 图象填充区域算法图象填充区域算法 1 1 图像方式图像方式: : 1）位图不透明方式； 2）位图透明方式； 3）像素图填充方式。YX图像空间区域定义 1）使图像在水平和垂直方向周期性排 列，直到所定义的区域全被不重迭 的图像所覆盖。2）假定每个图像的尺寸是MN，通过 周期性排列构成图像空间。3）建立区域中各像素与图像各单元间 的映射关系。2 2 处理过程处理过程3 3 建立映射关系建立映射关系 1)整个绘图空间与图像空间的1-1映

21、射 2)区域局部坐标空间与图像空间的1-1映射(x,y)(x1,y1)第第3 3章章 基本图形生成技术基本图形生成技术- -区域填充区域填充第3章- 32/40计算机图形学计算机图形学计算机科学与技术学院计算机科学与技术学院字符生成方法有点阵式、矢量式和编码式。常用的字符有： ASCII码， 汉字字符， 其它字符， 其它工程专用符号。 点阵式字符将字符表示为一个矩形点阵，由点阵中点的不同值表达字符的形状。 常用的点阵大小有88、1616、 3232等等。 第第3 3章章 基本图形生成技术基本图形生成技术- -区域填充区域填充第3章- 33/40计算机图形学计算机图形学计算机科学与技术学院计算机

22、科学与技术学院2）点阵字符的处理点阵字符的处理 使用点阵式字符时，需将字库中的矩形点阵拷贝到buffer中指定的单元中去。 在拷贝过程中 ，施加变换，可获得简单的变化 。 作任意角度的旋转等复杂变换，比较困难。 矢量式字符将字符表达为一个点坐标的序列，相邻两点表示一条矢量，字符的形状便由矢量序列刻划。 1）定义字模 采用正方形网格88、3232、6464、128128等。 2）定义字符 表达字符的内容：定位点坐标、走笔方向和标志等。 第第3 3章章 基本图形生成技术基本图形生成技术- -区域填充区域填充第3章- 34/40计算机图形学计算机图形学计算机科学与技术学院计算机科学与技术学院采用两种

23、形式 矢量编码：用有限的方向编码来表达一个字符， 通常采用8个或16个方向。 专用编码：采用专用的编码和格式，每一个编码 定义了特定的操作和特定的格式。3）按结构保存编码。4）定义并保存结束标志。5）建立字符库。 第第3 3章章 基本图形生成技术基本图形生成技术- -区域填充区域填充第3章- 35/40计算机图形学计算机图形学计算机科学与技术学院计算机科学与技术学院以AutoCAD形文件的定义为例：文件格式：一个标题行， 若干个描述行。标题行：*形编号， ，。描述行: 由编码和操作数组成。 采用矢量编码，最高位0表示为十六进制数，后面两位表示高四位和低四位，高四位表示矢量长度，低四位表示画矢量

24、的方向。 二极管符号的定义形式如下：*133，11，EJG040, 044, 04c, 062, 04c, 040, 048, 04c, 066, 04c, 0。第第3 3章章 基本图形生成技术基本图形生成技术- -区域填充区域填充第3章- 36/40计算机图形学计算机图形学计算机科学与技术学院计算机科学与技术学院从字库的字模中读出字符，在显示器或打印机上输出。 计算或确定字符或字符串左下角点的坐标； 读取字符数据：根据编码取出每个节点的数据；读取字符数据时，应注意考虑以下参数： a) 字符的定位点，一般选择字符的左下角点； b) 确定字符的类型和字符的个数； c) 字符的方向，方向常选取与x

25、轴的夹角，单位为度； d) 确定字符宽度和字符高度，通常选择高度作参数， 把宽度看成高度的比例系数； e) 确定字符的间距，间距选择字符高度的比例系数； 进行坐标变换和处理：可以对字符进行任何操作，如 放大、旋转，甚至透视等； 在确定的位置显示字符。6）显示字符 第第3 3章章 基本图形生成技术基本图形生成技术- -区域填充区域填充第3章- 37/40计算机图形学计算机图形学计算机科学与技术学院计算机科学与技术学院 1）阶梯状的图形或边界 2）图形细节失真 2）狭小图形的遗失与动态图形的闪烁用离散量表示连续量引起的失真现象称之为走样。第第3 3章章 基本图形生成技术基本图形生成技术- -区域填

26、充区域填充第3章- 38/40计算机图形学计算机图形学计算机科学与技术学院计算机科学与技术学院用于减少或消除走样现象的技术称为反走样。1 提高分辨率（过取样，或后滤波） 1）从硬件考虑提高分辨率 方法简单，但代价非常大。 帧缓存容量则增加到原来的4倍，扫描转换要花4倍时间。 只能减轻而不能消除锯齿问题第第3 3章章 基本图形生成技术基本图形生成技术- -区域填充区域填充第3章- 39/40计算机图形学计算机图形学计算机科学与技术学院计算机科学与技术学院 2）从软件考虑提高分辨率1111算术平均122142121加权平均 高分辨率计算，低分辨率显示 把每个像素分为四个子像素，扫描转换算法求得各子

27、像素的灰度值，然后对四像素的灰度值简单平均，作为该像素灰度值。 像素细分技术，相当于后置滤波 第第3 3章章 基本图形生成技术基本图形生成技术- -区域填充区域填充第3章- 40/40计算机图形学计算机图形学计算机科学与技术学院计算机科学与技术学院2 区域取样（或前滤波） 1）简单的区域取样 在整个像素区域内进行采样，该技术称为区域取样。 利用一种求相交区域的近似面积的离散计算方法： (1)将屏幕象素分割成n个更小的子象素， (2)计算中心落在直线段内的子象素的个数m， (3)m/n为线段与象素相交区域面积的近似值。 特点： (1)直线段像素亮度与其重叠区域的面积成正比； (2)相同面积重叠区

28、域的像素灰度值或颜色值相同； (3)不适用动态图形显示。第第3 3章章 基本图形生成技术基本图形生成技术- -区域填充区域填充第3章- 41/40计算机图形学计算机图形学计算机科学与技术学院计算机科学与技术学院1）加权区域取样 假想一个连续的加权曲面（或过滤函数）覆盖象素。当直线条经过该象素时，该象素的灰度值是在二者重叠区域上对滤波器（过滤函数）进行积分的积分值。特点： (1)接近理想直线的象素将被分配更多的灰度值； (2)相邻两个象素的滤波器相交，有利于缩小直线条上相邻象素的灰度差。常用过滤函数第第3 3章章 基本图形生成技术基本图形生成技术- -区域填充区域填充第3章- 42/40计算机图

29、形学计算机图形学计算机科学与技术学院计算机科学与技术学院 1.1.认真阅读课文内容认真阅读课文内容 2 2. .解释名词：区域、区域填充、种子、活性边。解释名词：区域、区域填充、种子、活性边。 3.3.掌握区域内点的测试方法掌握区域内点的测试方法. . 4. 4.能准确区分区域的连通性能准确区分区域的连通性 5.5.理解掌握区域、扫描线、边界连续性。理解掌握区域、扫描线、边界连续性。 6.6.了解掌握扫描线填充算法的原理与步骤。了解掌握扫描线填充算法的原理与步骤。 7.7.系统中常用字符有几种？字符生成方法有几种？系统中常用字符有几种？字符生成方法有几种？ 1 区域填充算法区域填充算法 2 字符生成算法字符生成算法 3 反