《河南理工大学计算机图形学3章-3 区域填充》由会员分享，可在线阅读，更多相关《河南理工大学计算机图形学3章-3 区域填充（50页珍藏版）》请在金锄头文库上搜索。
1、,第3章 基本图形生成,3.1 直线图形生成 3.2 圆及二次曲线生成 3.3 区域图形填充 3.4 字符生成 3.5 反走样,第3章 二维图形生成技术,本次课内容： 3.3 区域填充算法 3.4 字符的生成,线框多边形物体,填充多边形物体,区域填充应用实例,3.3 区域填充算法,单色填充,图案填充,区域填充解决的问题： 1 描述区域边界 曲线围成的区域，可用多边形逼近； 2 确定待填充的象素 检查每一像素是否位于多边形区域内； 3 确定填充要素 颜色或图案。,名词解释,1) 区域：一组相邻而且又相连的像素，而且具有相同属 性的封闭区域。,3) 区域填充：在区域内确定种子，并将这种属性扩展到
2、整个区域的过程。,4）边界的种类：单域 复合域,2) 种子：具有一定填充属性单位的像素或像素组合。,5) 区域的建立方式：内定区域 边界定义区域。 内定区域：在所定义的区域内所有的像素具有相同 的属性（如颜色等）,而区域边界上的像素着不 同的颜色； 边界定义区域：区域以的属性来划分，区域内的像 素和边界上的像素可具有不同得属性。,区域填充算法：,1) 种子填充算法内部一个点出发 简单种子算法 扫描线种子算法 2) 扫描线填充算法扫描线顺序 有序边表算法 边填充算法 3) 图案填充算法填充有结构的图形 影线填充算法 图像填充算法,1 区域的连通性,3.3.1 种子填充算法,4连通区域：从区域上的
3、一点出发，通过访问已知点的4邻接点，在不越出区域的前提下，遍历区域内的所有象素点。 8连通区域：从区域上的一点出发，通过访问已知点的8邻接点，在不越出区域的前提下，遍历区域内的所有象素点。,4连通区域,8连通区域,4连通与8连通区域区别,2 基本原理,假设区域内一点已知，以此为种子。从该点出发，沿着区域连通的方向搜索与种子相邻且位于区域内的点，使其成为新种子，接着继续递归地搜索下去。若相邻的点不在区域内，即达到边界。,常用算法有： 简单种子填充算法、 扫描线种子填充算法。,连通区域扩展过程,4连通填充,8连通填充,3 简单种子算法 1）算法步骤 确定边界和边界的属性； 确定区域填充的属性值；
4、测试区域内一点的属性值，判定其是否在填充区域内；且未被填充， 若在区域内且和边界的属性值不同，赋予填充属性，以此点为种子； 沿四连通(或八连通)方向，测试其它点； 每测试一个点都与边界属性比较，若不同，赋予填充属性； 若相同，即到达边界，然后转向另一种连通方向； 整个点的测试采用循环递归的方式实现。,扫描线种子填充算法过程,2) 算法特点 算法简单，便于硬件实现； 像素测试效率比较低。,4 扫描线种子填充算法 1）算法的基本思想 用扫描线从上到下扫描由点线段构成的多段多边形。每根扫描线与多边形各边产生一系列交点。将交点按照x(或y)坐标进行分类，然后成对取出，作为两个端点，用填充颜色画水平直线
5、。,扫描线填充算法：yx算法 xy算法。,2）算法的基本过程： 当给定种子点时，首先填充种子点所在的扫描线上的位于给定区域的一个区段，然后确定与这一区段相通的上下两条扫描线上位于给定区域内的区段，并依次保存下来。反复这个过程，直到填充结束。,3.3.2 多边形填充算法,1 多边形表示 顶点表示：用多边形的顶点序列描述多边形。,点阵表示：用位于多边形内的像素几何描述多边形。,把多边形的顶点表示转换为点阵表示。或求出位于多边形内的各个像素点并赋予特定的属性。,射 线 法,任作一条射线,求其与边界的交点,若交点数为偶数,则该点在边界之外,否则在边界之内。,2 主要技术处理 区域内点的快速测试方法,累
6、计角度法,计算各边的夹角的和，若代数和为零，该点域外；若代数和为2，该点域内。,重合点的处理: 当扫描线和边界相交于边界顶点时，同时产生两个交点，通常采用 “起闭终开”或“起开终闭” 。, 水平边处理： 水平边不参加求交计算，跳过。,P1,p2),P4，P5),P2,p3),P5,p1),活性边的构造方法： a) 去除水平边，根据环方向进行开闭区间处理； b) 按照端点的Y坐标大小对各边进行排序，按从大到小 把边存入线性表中； c) 在线性表中加入两个指针，形成活性边表。,活性边表实时刷新 a) 调整两个指针值，确保扫描正常进行； b) 调整两个指针之间边元素值；, 构造活性边表 活性边：与当
7、前扫描线相交的边界线的边。,3 扫描线算法 利用区域的连续性、扫描线的连续性、边界连续性。,1）区域连续性 梯形：部分在内，部分在外，间隔排列。,2）扫描线连续性 交点： 交点数为偶数; 奇到偶数点在域内，偶到奇数点在域外。,3）边界连续性 把边界的端点按其y坐标排列： y0,y1,yi yikyik+1 0 k n-1 设扫描线,y=d ， y10 d y2, 交点有4个。,交点数相等； 同编号的点位于同一条边上。,4 扫描线算法实现步骤 1) 把区域边界顶点按Y坐标排序； 2）确定扫描线的区间； 3）构建边界边的活性边表； 4）求交点； 5）交点排序； 6）交点配对； 7）填充颜色,3.3
8、.3 边填充算法,优点： 最适合于有帧缓存的显示器 可按任意顺序处理多边形的边 仅访问与该边有交点的扫描线上右方的像素，算法简单 缺点： 对复杂图形，每一像素可能被访问多次，输入/输出量大 图形输出不能与扫描同步进行，只有全部画完才能打印,也称正负相消法，对每一扫描线依次求其与边的交点，对交点右侧像素取补，并多边形每条边排序。,3.3.4影线填充算法,图案填充：是在区域内填充有规律的图形组合，而图形可以分解成一族或数族不同类型的线型组合。,影线填充：用一组等距离的平行线(其各段的起、终端点位于区域边界上) 填充区域的过程。,填充图案,影线填充的算法步骤,1) 影线描述,影线采用斜截式定义：y=
9、kx+b,2) 区域边界描述 区域边界描述应考虑如下因素： a) 边界线的形状，直线和圆弧； b) 边界线的位置； c) 区域的类型，单域和复域； d) 边界是封闭性。, 引入假想线，使复域转变成闭合的单域；, 引入特征值，描述边界线的形状和类型；,具体定义如下： a) 直线：特征值为0； b) 假想线：特征值为10-10； c) 圆弧：特征值为R，R0：圆弧由起点逆时针 画至终点，R0：圆弧由起点顺时针画至终点。, 引入有序顶点环表，表示不同类型边界线的位置点。 a) 直线段用起、终端点表示； b) 圆弧用起、圆心点和终点表示；, 特征值赋值： a) 直线由终点携带边界特征值； b) 圆弧的
10、特征值由圆心点携带； c) 圆弧的终点特征值赋为10-10； d) 第一点起点的特征值为边界轮廓顶点总数。,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)时，则有： P(i，j)=L(i)R(j),对于P(i，j)，存在有三种类型的点： 无
11、效点：交点在边界有效线段之外，应当舍弃； 有效点：交点在边界有效线段上，应当纪录； 双重点：交点位于边界顶点处，采用“起闭终开”规 则，舍弃重点，记录有效点。,7）显示影线段 影线交点的顺序规律： 奇点偶点时，影线段在域内，显示影线段； 偶点奇点时，影线段在域外，不显示影线段。,6) 对交点进行排序 按照坐标大小，对有效交点进行从小到大的顺序排队。,3.3.5 图象填充区域算法,1 图像方式: 1）位图不透明方式； 2）位图透明方式； 3）像素图填充方式。,1）使图像在水平和垂直方向周期性排 列，直到所定义的区域全被不重迭 的图像所覆盖。 2）假定每个图像的尺寸是MN，通过 周期性排列构成图像
12、空间。 3）建立区域中各像素与图像各单元间 的映射关系。,2 处理过程,3 建立映射关系 1)整个绘图空间与图像空间的1-1映射 2)区域局部坐标空间与图像空间的1-1映射,3.4 字符的生成,字符生成方法有点阵式、矢量式和编码式。 常用的字符有： ASCII码， 汉字字符， 其它字符， 其它工程专用符号。,1. 点阵式字符,1) 定义模式,点阵式字符将字符表示为一个矩形点阵，由点阵中点的不同值表达字符的形状。,常用的点阵大小有88、1616、 3232等等。,2）点阵字符的处理, 使用点阵式字符时，需将字库中的矩形点阵拷贝到buffer中指定的单元中去。, 在拷贝过程中 ，施加变换，可获得简
13、单的变化 。, 作任意角度的旋转等复杂变换，比较困难。,2.矢量式字符,矢量式字符将字符表达为一个点坐标的序列，相邻两点表示一条矢量，字符的形状便由矢量序列刻划。,1）定义字模 采用正方形网格88、3232、6464、128128等。,2）定义字符 表达字符的内容：定位点坐标、走笔方向和标志等。,采用两种形式 矢量编码：用有限的方向编码来表达一个字符， 通常采用8个或16个方向。 专用编码：采用专用的编码和格式，每一个编码 定义了特定的操作和特定的格式。,3）按结构保存编码。 4）定义并保存结束标志。 5）建立字符库。,以AutoCAD形文件的定义为例： 文件格式：一个标题行， 若干个描述行。
14、 标题行：*形编号， ，。 描述行: 由编码和操作数组成。,采用矢量编码，最高位0表示为十六进制数，后面两位表示高四位和低四位，高四位表示矢量长度，低四位表示画矢量的方向。,二极管符号的定义形式如下： *133，11，EJG 040, 044, 04c, 062, 04c, 040, 048, 04c, 066, 04c, 0。,从字库的字模中读出字符，在显示器或打印机上输出。 计算或确定字符或字符串左下角点的坐标； 读取字符数据：根据编码取出每个节点的数据； 读取字符数据时，应注意考虑以下参数： a) 字符的定位点，一般选择字符的左下角点； b) 确定字符的类型和字符的个数； c) 字符的方
15、向，方向常选取与x轴的夹角，单位为度； d) 确定字符宽度和字符高度，通常选择高度作参数， 把宽度看成高度的比例系数； e) 确定字符的间距，间距选择字符高度的比例系数； 进行坐标变换和处理：可以对字符进行任何操作，如 放大、旋转，甚至透视等； 在确定的位置显示字符。,6）显示字符,3.5 反走样,3.5.1. 光栅图样走样现象,1）阶梯状的图形或边界,2）图形细节失真,2）狭小图形的遗失与动态图形的闪烁,用离散量表示连续量引起的失真现象称之为走样。,3.5.2. 常用反走样技术,用于减少或消除走样现象的技术称为反走样。,1 提高分辨率（过取样，或后滤波） 1）从硬件考虑提高分辨率,方法简单，但代价非常大。 帧缓存容量则增加到原来的4倍，扫描转换要花4倍时间。 只能减轻而不能消除锯齿问题,2）从软件考虑提高分辨率,高分辨率计算，低分辨率显示 把每个像素分为四个子像素，扫描转换算法求得各子像素的灰度值，然后对四像素的灰度值简单平均，作为该像素灰度值。 像素细分技术，相当于后置滤波,只能减轻，不能消除,2 区域取样（或前滤波） 1）简单的区域取样,在整个像素区域内进行采样，该技术称为区域取样。 利用一种求相交区域的近似面积的离散计算方法： (1)将屏幕象素分割成n个更小的子象素， (2)计算中心落在
