第四章 基本图形生成算法 （二） 2019/4/25 IBM Confidential

主要内容： 直线的扫描转换 圆与椭圆的扫描算法 区域填充 线宽与线型的处理 字符 裁剪 反走样 2019/4/25

区域填充 区域：点阵表示的图形，像素集合； 表示方法：内点表示、边界表示： 内点表示：－》区域填充算法 枚举处区域内部的所有像素； 内部的所有像素填充同一个颜色； 边界像素填充与内部像素不同的颜色； 边界表示：枚举出边界上所有的像素－》边界填充算法； 边界上的所有像素填充同一颜色； 内部像素填充与边界像素不同的颜色； 区域填充：对区域重新着色的过程，即从给定位置开始涂描直到指定的边界条件为止； 将指定的颜色从种子点扩展到整个区域的过程； 区域填充算法要求区域是连通的； 一般步骤： 确定那些像素位于填充图元的内部； 确定以什么颜色填充这些像素； 2019/4/25

多边形的扫描转换 扫描转换矩形（1/2）： void FillRectangle(Rectangle *rect,int color) { int x,y; for(y = rect->ymin; y <= rect->ymax; y++) for(x = rect->xmin; x <= rect->xmax; x++) PutPixel(x,y,color); }/*end of FillRectangle() */ 2019/4/25

多边形的扫描转换 矩形是简单的多边形，那么为什么要单独处理矩形？ 共享边界如何处理？ 属于谁？ 扫描转换矩形（2/2）： 比一般多边形可简化计算； 应用多: 如窗口系统； 共享边界如何处理？ 原则：左闭右开，下闭上开 属于谁？ 2019/4/25

多边形的扫描转换 多边形的表示方法： 顶点表示：用多边形的顶点序列刻划多边形； 点阵表示：用位于多边形内象素的集合来刻划多边形； 扫描转换多边形：将顶点表示形式转换成点阵表示形式； 三种方法：逐点判断法；扫描线算法；边缘填充法； 2019/4/25

多边形的扫描转换 逐点判断法 #define MAX 100 typedef struct{ int PolygonNum; // 多边形顶点个数 Point vertexces[MAX] //多边形顶点数组 } Polygon // 多边形结构 void FillPolygonPbyP(Polygon *P, int polygonColor) { int x,y; for(y = ymin; y <= ymax;y++) for(x = xmin; x <= xmax;x++) if( IsInside( P, x, y ) ) PutPixel(x, y, polygonColor); else PutPixel(x, y, backgroundColor); }/*end of FillPolygonPbyP() */ 2019/4/25

多边形的扫描转换 逐点判断法 逐个判断绘图窗口内的像素： 如何判断点在多边形的内外关系？ 1）射线法; 2）累计角度法; 3）编码法； 步骤： 1) 从待判别点v发出射线; 2) 求交点个数k; 3) K的奇偶性决定了点与多边形的内外关系; 4)奇异情况处理; 2019/4/25

多边形的扫描转换 逐点判断法 2）累计角度法 步骤: 从v点向多边形P顶点发出 射线，形成有向角; 计算有相交的和，得出结论; 预处理; 离散计算方法：编码方法; 2019/4/25

多边形的扫描转换 P0 逐点判断法 v P1 P2 结论：逐点判断法程序简单，速度太慢，效率低。 3）编码方法：累计角度方法的离散方法 Step: a.预处理，测试点在边上否？ b.V为中点作局部坐标系,对象限按逆时针（或顺时针）编码； c.顶点编码Ipi， d.边编码。PiPi+1: △PiPi+1=Ipi+1-Ipi e.计算∑ △PiPi+1 （其中△PnPn+1 = △PnP0)： 若 ∑ 为0, V在P外；若 ∑ 为+/-4，V 在P内； 结论：逐点判断法程序简单，速度太慢，效率低。 2019/4/25

几个概念： 多边形的扫描转换：扫描线算法： 边的连贯性：某条边与当前扫描线相交，也可能与下一条扫描线相交； 扫描线的连贯性：当前扫描线与各边的交点顺序与下一条扫描线与各边的交点顺序可能相同或类似； 区间连贯性：同一区间上的像素取同一颜色属性； 2019/4/25

扫描线算法： 多边形的扫描转换：扫描线算法： 目标：利用相邻像素之间的连贯性，提高算法效率； 处理对象：非自交多边形 （边与边之间除了顶点外无其它交点）； 2019/4/25

基本思想：一条扫描线与多边形的边有偶数个交点 多边形的扫描转换：扫描线算法： 扫描线算法 基本思想：一条扫描线与多边形的边有偶数个交点 2019/4/25

区域填充（扫描线算法） 算法步骤： (1)确定多边形所占有的最大扫描线数，得到多边形顶点的最小和最大y值（ymin 和 ymax）； (2)从y=ymin到y=ymax，每次用一条扫描线进行填充； (3)对一条扫描线填充的过程可分为四个步骤： a.求交：扫描线与各边的交点； b.排序：按X大小对各交点排序； c.交点配对：每对交点表示一个区间； d.区间填色：区间内置填充色；区间外填背景色； 2019/4/25

区域填充（扫描线算法） 例：扫描线6的填充。 1、求交：A(2),B(3.5),C(7),D(11)； 3、交点配对: (0,2),(2,3.5),(3.5,7),(7,11),(11,以后)； 存在问题：当扫描线与多边形顶点相交时，交点的取舍问题。如：扫描线2正确,扫描线7错误。 2019/4/25

解决方法：当扫描线与多边形的顶点相交时： 若共享顶点的两条边分别落在扫描线的两边，交点只算一个； 区域填充（扫描线算法） 解决方法：当扫描线与多边形的顶点相交时： 若共享顶点的两条边分别落在扫描线的两边，交点只算一个； 若共享顶点的两条边在扫描线的同一边，这时交点作为零个或两个。 多边形边界上象素的取舍问题： 例：2×2图形填充：若不加处理则变成3×3； 解决办法：下闭上开；左闭右开； 2019/4/25

扫描线算法： 多边形的扫描转换：扫描线算法： 扫描线与边的交点类型： 第一类交点：新出现的边与扫描线的交点； 第二类交点：位于同一条边上的后继交点； 2019/4/25

用于线画图元扫描转换的四舍五入原则导致部分像素位于多边形之外，从而不可用 多边形的扫描转换：扫描线算法： 扫描线算法： 交点的取整规则 要求：使生成的像素全部位于多边形之内 用于线画图元扫描转换的四舍五入原则导致部分像素位于多边形之外，从而不可用 假定非水平边与扫描线y=e相交，交点的横坐标为x,规则如下： 2019/4/25

扫描线算法： 多边形的扫描转换：扫描线算法： 交点的取整规则 规则1： X为小数，即交点落于扫描线上两个相邻像素之间； (a)交点位于左边之上，向右取整； (b)交点位于右边之上，向左取整； 2019/4/25

扫描线算法： 多边形的扫描转换：扫描线算法： 交点的取整规则 规则2： 边界上象素的取舍问题，避免填充扩大化; 解决方法： 边界象素：规定落在右上边界的象素不予填充； 具体实现时，只要对扫描线与多边形的相交区间左闭右开； 2019/4/25

扫描线算法： 多边形的扫描转换：扫描线算法： 交点的取整规则 规则3： 扫描线与多边形的顶点相交时，交点的取舍，保证交点正确配对。 解决方法： 检查两相邻边在扫描线的哪一侧。 只要检查顶点的两条边的另外两个端点的Y值，两个Y值中大于交点Y值的个数是0，1，2，来决定取0，1，2个交点。 2019/4/25

计算扫描线与多边形各边的交点：最简单的方法： 将多边形的所有边放在一个表中； 缺点：效率低 改进的有效边表算法（Y连贯性算法） 改进原理： 多边形的扫描转换：扫描线算法： 计算扫描线与多边形各边的交点：最简单的方法： 将多边形的所有边放在一个表中； 缺点：效率低 改进的有效边表算法（Y连贯性算法） 改进原理： 处理一条扫描线时，仅对有效边求交； 利用扫描线的连贯性； 利用多边形边的连贯性； 2019/4/25

活性边（Active Edge）：指与当前扫描线相交的多边形的边，也称为活性边。 多边形的扫描转换：扫描线算法： 活性边（Active Edge）：指与当前扫描线相交的多边形的边，也称为活性边。 活性边表（Active Edge Table, AET）：把活性边按与扫描线交点x坐标递增的顺序存放在一个链表中，此链表称活性边表。 活性边表的每个结点： x ymax 1/k next 边表（Edge Table）的构造（1/2）： (1)首先构造一个纵向链表，链表的长度为多边形所占有的最大扫描线数，链表的每个结点，称为一个桶，对应多边形覆盖的每一条扫描线。 (2)将每条边的信息链入与该边最小y坐标（ymin ）相对应的桶处。也就是说，若某边的较低端点为ymin，则该边就放在相应的扫描线桶中。 2019/4/25

边表（Edge Table）的构造（2/2）： 多边形的扫描转换：扫描线算法： 边表（Edge Table）的构造（2/2）： (3)每条边的数据形成一个结点，内容包括：该扫描线与该边的初始交点x（即较低端点的x值），1/k，以及该边的最大y值ymax。 x|ymin ymax 1/k NEXT (4)同一桶中若干条边按X|ymin由小到大排序，若X| ymin相等，则按照1/k由小到大排序。 2019/4/25

多边形的扫描转换：扫描线算法： 算法涉及的数据结构: 1）活性边：与当前扫描线相交的边。按交点x的增量顺序存放在一个链表中；该链表称作活性边表（AET); AET的结点信息： Ymax: 所交边的最高扫描线号; X：当前扫描线与边的交点的x坐标; △X：边的斜率的倒数; Nextage: 下一条边的指针; typedef struct {int ymax; float x,deltax; Edge *nextEdge; }Edge; 2019/4/25

2）新边表:按照边的下端点y坐标对非水平边进行分类的指针数组,下端点y坐标值等于i的边属于第i类; 多边形的扫描转换：扫描线算法： 2）新边表:按照边的下端点y坐标对非水平边进行分类的指针数组,下端点y坐标值等于i的边属于第i类; 作用：方便活性边表的建立与更新。 typedef struct {int ymax; float x,deltax; Edge *nextEdge; }Edge; 作用:避免盲目求交: 处理一条扫描线时，为求出它与多边形边的所有交点，必须将它与所有的边进行求交测试。实际上只有某几条边与该扫描线有交点。边的新建表正是用来排除不必要的求交测试。 2019/4/25

(2)将第一个不空的ET表中的边与AET表合并； (3)由AET表中取出交点对进行填充。填充之后删除y=ymax的边； 多边形的扫描转换：扫描线算法： 活性边表算法步骤 ： (1)初始化：构造边表，AET表置空； (2)将第一个不空的ET表中的边与AET表合并； (3)由AET表中取出交点对进行填充。填充之后删除y=ymax的边； (4)yi+1=yi+1,根据xi+1=xi+1/m计算并修改AET表，同时合并ET表中y=yi+1桶中的边，按次序插入到AET表中，形成新的AET表； (5)AET表不为空则转(3)，否则结束。 2019/4/25

多边形的扫描转换：边填充算法： 边填充算法： A – M, 记为 。计算机中取A为n位能表示的最大整数。即，A=0xFFFFFFFF ▼求余运算可用异或显示模式实现: ▼算法基本思想：对于每条扫描线和每条多边形边的交点，将该扫描线上交点右方的所有象素取余。 2019/4/25

多边形的扫描转换 边填充算法： 算法1（以扫描线为中心的边填充算法）： 1、将当前扫描线上的所有象素着上颜色 ； 2、求余： 1、将当前扫描线上的所有象素着上颜色 ； 2、求余： for(i = 0;i <= m; i++)在当前扫描线上从横坐标为Xi的交点向右求余； 2019/4/25

多边形的扫描转换 边填充算法： 算法2（以边为中心的边填充算法）： 1、将绘图窗口的背景色置为 ； 1、将绘图窗口的背景色置为 ； 2、对多边形的每一条非水平边做：从该边上的每个象素开始向右求余； 2019/4/25

多边形的扫描转换 边填充算法： 结论： 适于具有帧缓存的图形系统。处理后，按扫描线顺序读出帧缓存的内容，送入显示设备； 优点：算法简单； 缺点：对于复杂图形，每一象素可能被访问多次，输入/输出的量比扫描线算法大得多； 2019/4/25

区域填充（多边形域填充） 栅栏填充算法： 栅栏: 一条经过多边形顶点且与扫描线垂直的直线。它把多边形分为两半； 基本思想：对于每个扫描线与多边形边的交点,将交点与栅栏之间的象素取补。若交点位于栅左边,则将交点之右,栅栏之左的所有像素取补;若交点位于栅栏右边,则将栅栏之右交点之左的象素取补； 左图为采用栅栏填充算法填充多边形的示意图： 缺点：还是有些象素会重复访问 2019/4/25

区域填充（多边形域填充） 边标志算法：分为两步骤： 第一步，对多边形的每条边进行直线扫描转换，亦即对多边形边界所经过的象素打上边标志； 第二步，填充。对每条与多边形相交的扫描线，依从左到右顺序，逐个访问该扫描线上象素。使用一个布尔量inside来指示当前点的状态，若点在多边形内，则inside为真。若点在多边形外，则inside为假。inside的初始值为假，每当当前访问象素为被打上边标志的点，就把inside取反。对未打标志的象素，inside不变。若访问当前象素时，对inside作必要操作之后，inside为真，则把该象素置为多边形色。 当用软件实现本算法时，速度与改进的有效边表算法相当，但用硬件实现后速度会有很大提高； 2019/4/25

区域填充（多边形域填充） 种子填充算法 区域填充 – 对区域重新着色的过程； 将指定的颜色从种子点扩展到整个区域的过程； 区域填充算法要求区域是连通的； 连通性：4连通、8连通； 4连通： －》 8连通： －》 2019/4/25

区域填充（多边形域填充） 4连通与8连通区域的区别： 连通性： 4连通可看作8连通区域，但对边界有要求； 对边界的要求： 2019/4/25

区域填充（多边形域填充） 递归填充算法 内点表示的4连通区域 取(x,y)为种子点 void FloodFill4(int x, int y, int oldColor,int newColor) { if(GetPixel(x,y) == oldColor) PutPixel(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); } }/*end of FloodFill4() */ 2019/4/25

区域填充（多边形域填充） 2019/4/25

区域填充（多边形域填充） 递归填充算法 问题： 内点表示与边界表示的8连通区域？ 缺点： (1) 有些象素会入栈多次，降低算法效率；栈结构占空间； (2) 递归执行，算法简单，但效率不高，区域内每一象素都引起一次递归，进/出栈，费时费内存； 改进算法，减少递归次数，提高效率； 方法之一：使用扫描线填充算法； 2019/4/25

扫描转换扇形区域(1/5) 扇形区域的描述: 原理：同扫描转换多边形； 问题：如何确定扫描线与直线段和圆弧段的相交顺序； 方法：分类： 按点 和 点所处象限的不同，需要将扇形区域分成4×4=16种情况； 2019/4/25

扫描转换扇形区域(2/5) 假设 点落在第一象限 ,扇形区域的扫描转换分四种情况（1/3）： 1、 落在第一象限 2019/4/25

扫描转换扇形区域(3/5) 2、落在第二象限时分两种情况 当 时 2019/4/25

扫描转换扇形区域(4/5) 3、落在第三象限 4、落在第四象限 2019/4/25

扫描转换扇形区域(5/5) 遗留问题：当 落在其它区域时? 其它方法：多边形逼近法 2019/4/25

区域填充 – 圆域的填充 将多边形区域填充原理推广到圆域的填充； 1）计算每条扫描线与圆域的相交区间； 2）把区间内象素用指定颜色填充； 相交区间的确定： 中点画圆法－》计算交点－》确定相交区间； 函数F的计算可以采用增量法提高效率； 2019/4/25

主要内容： 直线的扫描转换 圆与椭圆的扫描算法 区域填充 线宽与线型的处理 字符 裁剪 反走样 2019/4/25

线宽与线型的处理 直线线宽处理 线刷子：垂直刷子、水平刷子； 特点 （1/2） 实现简单、效率高。 斜线与水平(或垂直)线不一样粗。 当线宽为偶数个象素时，线的中心将偏移半个象素。 问题：利用线刷子生成线的始末端总是水平或垂直的，看起来不太自然。 解决：添加“线帽（line cap）” 2019/4/25

线宽与线型的处理 直线线宽处理 线刷子特点(2/2) 当比较接近水平的线与比较接近垂直的线汇合时，汇合处外角有缺口; 解决：斜角连接（miter join）、圆连接（round join）、斜切连接（bevel join）; 2019/4/25

线宽与线型的处理 直线线宽处理 方刷子： 特 点:方刷子绘制的线条（斜线）比线刷子所绘制的线条要粗一些(k=1或-1时最粗:1.414倍); 方刷子绘制的斜线与水平（或垂直）线不一样粗; 方刷子绘制的线条自然地带有一个“方线帽”; 2019/4/25

线宽与线型的处理 其它线宽处理方式 区域填充 改变刷子形状： 2019/4/25

线宽与线型的处理 曲线线宽处理 线刷子 方刷子 要显示一致的曲线宽度可通过旋转刷子方向,使其在沿曲线移动时与斜率方向一致; 圆弧刷子 采用填充的办法。 2019/4/25

线宽与线型的处理 直线线型处理 实心段和中间空白段的长度（象素数目）可用象素模板(pixel mask)指定； 存在问题：如何保持任何方向的划线长度近似地相等？ 解决：根据线的斜率来调整实心段和中间空白段的象素数目； 曲线线型处理 采用象素模板的方法； 2019/4/25

Thank you! Best Wishes! 谢谢! 2019/4/25