【教学课件】第5章基本图形生成算法.ppt

第5章基本图形生成算法提出问题提出问题如何在指定的输出设备上根据坐标描述构造基本二维几何图形（点、直线、圆、椭圆、多边形域、字符串及其相关属性等）。2023/1/91图图形形的的生生成成：是在指定的输出设备上，根据坐标描述构造二维几何图形。图图形形的的扫扫描描转转换换：在光栅显示器等数字设备上确定一个最佳逼近于图形的象素集的过程。2023/1/925.1 直线的扫描转换直线的扫描转换直线的绘制要求：直线的绘制要求：1.直线要直2.直线的端点要准确，即无定向性和断裂情况3.直线的亮度、色泽要均匀4.画线的速度要快5.要求直线具有不同的色泽、亮度、线型等2023/1/935.1.1 数值微分法数值微分法(DDA法)解决的问题解决的问题：给定直线两端点P0(x0,y0)和P1(x1,y1)，画出该直线。直线的微分方程：2023/1/94DDA算法原理算法原理：=1/max(|x|,|y|)2023/1/95max(|x|,|y|)=|x|，即|k|1的情况：max(|x|,|y|)=|y|，此时|k|1：2023/1/96程序程序注意注意：round(x)=(int)(x+0.5)2023/1/97特点特点：增量算法直观、易实现不利于用硬件实现2023/1/985.1.2 中点中点Bresenham算法算法直线的方程该直线方程将平面分为三个区域：对于直线上的点，F(x,y)=0；对于直线上方的点，F(x,y)0；对于直线下方的点，F(x,y)0。2023/1/992023/1/910基本原理基本原理：假定0k1，x是最大位移方向2023/1/911判别式判别式：则有：2023/1/912误差项的递推误差项的递推d0：2023/1/913误差项的递推误差项的递推d0：2023/1/914初始值初始值d的计算的计算2023/1/9150k1时Bresenham算法的算法步骤算法步骤为：1.输入直线的两端点P0(x0,y0)和P1(x1,y1)。2.计算初始值x、y、d=0.5-k、x=x0、y=y0；3.绘制点(x,y)。判断d的符号；若d0，则(x,y)更新为(x+1,y+1)，d更新为d+1-k；否则(x,y)更新为(x+1,y)，d更新为d-k。4.当直线没有画完时，重复步骤3。否则结束。2023/1/916改进改进：用2dx代替d1.输入直线的两端点P0(x0,y0)和P1(x1,y1)。2.计算初始值x、y、d=x-2y、x=x0、y=y0。3.绘制点(x,y)。判断d的符号。若d0.5，则(x,y)更新为(x+1,y+1)，同时将d更新为d-1；否则(x,y)更新为(x+1,y)。5.当直线没有画完时，重复步骤3和4。否则结束。2023/1/920改进改进1：令e=d-0.5e初=-0.5，每走一步有e=e+k。if(e0)thene=e-12023/1/921算法步骤算法步骤为：1.输入直线的两端点P0(x0,y0)和P1(x1,y1)。2.计算初始值x、y、e=-0.5、x=x0、y=y0。3.绘制点(x,y)。4.e更新为e+k，判断e的符号。若e0，则(x,y)更新为(x+1,y+1)，同时将e更新为e-1；否则(x,y)更新为(x+1,y)。5.当直线没有画完时，重复步骤3和4。否则结束。2023/1/922改进改进2：用2ex来替换ee初=-x，每走一步有e=e+2y。if(e0)thene=e-2x2023/1/923算法步骤算法步骤：1.输入直线的两端点P0(x0,y0)和P1(x1,y1)。2.计算初始值x、y、e=-x、x=x0、y=y0。3.绘制点(x,y)。4.e更新为e+2y，判断e的符号。若e0，则(x,y)更新为(x+1,y+1)，同时将e更新为e-2x；否则(x,y)更新为(x+1,y)。5.当直线没有画完时，重复步骤3和4。否则结束。2023/1/924程序程序几种画线算法的比较2023/1/9255.2 圆的扫描转换圆的扫描转换解决的问题：解决的问题：绘出圆心在原点，半径为整数R的圆x2+y2=R25.2.1 八分法画圆八分法画圆八分法画圆八分法画圆2023/1/926(y,x)(-y,x)(-x,y)(-x,-y)(-y,-x)(y,-x)(x,-y)2023/1/927解决问题解决问题：2023/1/9285.2.2 简单方程产生圆弧简单方程产生圆弧算法原理算法原理：利用其函数方程，直接离散计算圆的函数方程为：2023/1/929圆的极坐标方程为：2023/1/9305.2.3 中点中点Bresenham画圆画圆构造函数F(x,y)=x2-y2-R2。对于圆上的点，有F(x,y)=0；对于圆外的点，F(x,y)0；而对于圆内的点，F(x,y)0时，下一点取Pd(xi+1,yi-1)。M的坐标为：M(xi+1,yi-0.5)当F(xM,yM)0时，取Pd(xi+1,yi-1)当F(xM,yM)=0时，约定取Pu。构造判别式构造判别式：2023/1/933误差项的递推误差项的递推d0：2023/1/934d0：2023/1/935判别式的初始值判别式的初始值2023/1/936算法步骤算法步骤：1.输入圆的半径R。2.计算初始值d=1.25-R、x=0、y=R。3.绘制点(x,y)及其在八分圆中的另外七个对称点。4.判断d的符号。若d0，则先将d更新为d+2x+3，再将(x,y)更新为(x+1,y)；否则先将d更新为d+2(x-y)+5，再将(x,y)更新为(x+1,y-1)。5.当xy时，重复步骤3和4。否则结束。2023/1/937改进：改进：用d-0.25代替d算法步骤算法步骤：1.输入圆的半径R。2.计算初始值d=1-R、x=0、y=R。3.绘制点(x,y)及其在八分圆中的另外七个对称点。4.判断d的符号。若d0，则先将d更新为d+2x+3，再将(x,y)更新为(x+1,y)；否则先将d更新为d+2(x-y)+5，再将(x,y)更新为(x+1,y-1)。5.当x0；对于椭圆内的点，F(x,y)0，取Pd(xi+1,yi-1)2023/1/945误差项的递推误差项的递推d10：2023/1/946d10：2023/1/947判别式的初始值判别式的初始值再来推导椭圆弧下半部分的绘制公式原理原理2023/1/949判别式判别式若d20，取Pl(xi,yi-1)若d20，取Pr(xi+1,yi-1)2023/1/950误差项的递推误差项的递推d20：2023/1/951d20：2023/1/952注意注意：上半部分的终止判别下半部分误差项的初值算法步骤算法步骤：1.输入椭圆的长半轴a和短半轴b。2.计算初始值d=b2+a2(-b+0.25)、x=0、y=b。3.绘制点(x,y)及其在四分象限上的另外三个对称点。2023/1/9534.判断d的符号。若d0，则先将d更新为d+b2(2x+3)，再 将(x,y)更 新 为(x+1,y)；否 则 先 将 d更 新 为d+b2(2x+3)+a2(-2y+2)，再将(x,y)更新为(x+1,y-1)。5.当b2(x+1)0时，重复步骤7和8。否则结束。程序程序2023/1/9555.4 多边形的扫描转换与区域填充多边形的扫描转换与区域填充多多边边形形的的扫扫描描转转换换主要是通过确定穿越区域的扫描线的覆盖区间来填充，区区域域填填充充是从给定的位置开始涂描直到指定的边界条件为止。2023/1/9565.4.1 多边形的扫描转换多边形的扫描转换顶点表示顶点表示用多边形的顶点序列来刻划多边形点阵表示点阵表示是用位于多边形内的象素的集合来刻划多边形扫扫描描转转换换多多边边形形或或多多边边形形的的填填充充：从多边形顶点表示到点阵表示的转换。1.什么是多边形的扫描转换2023/1/9572.x-扫描线算法基本思想基本思想2023/1/958算法步骤算法步骤：(1)确定多边形所占有的最大扫描线数，得到多边形顶点的最小和最大y值（ymin和ymax）。(2)从y=ymin到y=ymax，每次用一条扫描线进行填充。(3)对一条扫描线填充的过程可分为四个步骤：a.求交b.排序c.交点配对d.区间填色2023/1/959存存在在问问题题：当扫描线与多边形顶点相交时，交点的取舍问题。2023/1/960解决：当扫描线与多边形的顶点相交时，若共享顶点的两条边分别落在扫描线的两边，交点只算一个；若共享顶点的两条边在扫描线的同一边，这时交点作为零个或两个。2023/1/961011110222填充过程实例2023/1/9623.改进的有效边表算法（改进的有效边表算法（Y连贯性算法）连贯性算法）改进原理改进原理：处理一条扫描线时，仅对有效边求交利用扫描线的连贯性利用多边形边的连贯性2023/1/963有有效效边边（Active Edge）：指与当前扫描线相交的多边形的边，也称为活性边。有有效效边边表表（Active Edge Table,AET）：把有效边按与扫描线交点x坐标递增的顺序存放在一个链表中，此链表称为有效边表。有效边表的每个结点：xymax1/knext2023/1/964边表（边表（Edge Table）边表的构造：(1)首先构造一个纵向链表，链表的长度为多边形所占有的最大扫描线数，链表的每个结点，称为一个桶，则对应多边形覆盖的每一条扫描线。(2)将每条边的信息链入与该边最小y坐标（ymin）相对应的桶处。也就是说，若某边的较低端点为ymin，则该边就放在相应的扫描线桶中。2023/1/965(3)每条边的数据形成一个结点，内容包括：该扫描线与该边的初始交点x（即较低端点的x值），1/k，以及该边的最大y值ymax。x|yminymax1/kNEXT(4)同一桶中若干条边按X|ymin由小到大排序，若X|ymax相等，则按照1/m由小到大排序。2023/1/966解决顶点交点计为解决顶点交点计为1时的情形时的情形：2023/1/9672023/1/9682023/1/969算法步骤算法步骤：(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)，否则结束。2023/1/9705.4.2 5.4.2 边缘填充算法边缘填充算法边缘填充算法边缘填充算法算法简单，但对于复杂图型，每一象素可能被访问多次栅栏填充算法栅栏填充算法栅栅栏栏指的是一条过多边形顶点且与扫描线垂直的直线。它把多边形分为两半。2023/1/971边标志算法边标志算法分为两个步骤：(1)打标记(2)填充当用软件实现本算法时，速度与改进的有效边表算法相当，但本算法用硬件实现后速度会有很大提高。2023/1/9725.4.3 5.4.3 区域填充区域填充区区域域是指已经表示成点阵形式的填充图形，它是像素集合。4-邻接点邻接点和8-邻接点邻接点2023/1/9734-连通区域连通区域和8-连通区域连通区域把位于给定区域的边界上的象素一一列举出来的方法称为边界表示法边界表示法。边界填充算法边界填充算法（Boundary-fillAlgorithm）。枚举出给定区域内所有象素的表示方法称为内点表示内点表示。泛填充算法（泛填充算法（Flood-fill Algorithm）2023/1/9741.边界填充算法算法的输入：种子点坐标(x,y)，填充色和边界颜色。栈结构实现4-连通边界填充算法连通边界填充算法的算法步骤算法步骤为：种子象素入栈；当栈非空时重复执行如下三步操作：(1)栈顶象素出栈；(2)将出栈象素置成填充色；(3)检查出栈象素的4-邻接点，若其中某个象素点不是边界色且未置成多边形色，则把该象素入栈。2023/1/976栈结构实现8-连通边界填充算法连通边界填充算法的算法步骤算法步骤为：种子象素入栈；当栈非空时重复执行如下三步操作：(1)栈顶象素出栈；(2)将出栈象素置成填充色；(3)检查出栈象素的8-邻接点，若其中某个象素点不是边界色且未置成多边形色，则把该象素入栈。2023/1/977特点特点：可以用于填充带有内孔的平面区域。把太多的象素压入堆栈改进改进通过沿扫描线填充水平象素段，来代替处理4-邻接点和8-邻接点。2023/1/978沿扫描线填充水平象素段的4-连通边界填充算法步骤连通边界填充算法步骤：种子象素入栈；当栈非空时作如下三步操作：(1)栈顶象素出栈；(2)填充出栈象素所在扫描行的连续象素段，直到遇到边界象素为止，即每出栈一个象素，就对包含该象素的整个扫描线区间进行填充；(3)在区间中检查与当前扫描线相邻的上下两条扫描线的有关象素是否全为边界象素或已填充的象素，若存在非边界、未填充边界的象素，则把每一区间的最右象素取作种子象素入栈。2023/1/9792.泛填充算法算法的输入：种子点坐标(x,y)，填充色和内部点的颜色。算法原理算法原理：算法从指定的种子(x,y)开始，用所希望的填充颜色赋给所有当前为给定内部颜色的象素点。2023/1/9808-连通泛填充连通泛填充算法步骤算法步骤如下：种子象素入栈；当栈非空时重复执行如下三步操作：(1)栈顶象素出栈；(2)将出栈象素置成填充色；(3)检查出栈象素的8-邻接点，若其中某个象素点不是给定内部点的颜色且未置成新的填充色，则把该象素入栈。2023/1/981注意注意：当以边界表示时，4-连通边界填充算法只能填充4-连通区域，8-连通边界填充算法也只能填充8-连通区域。当以内点表示时，8-连通泛填充算法可以填充8-连通区域也可以填充4-连通区域，当然4-连通泛填充算法还是只能填充4-连通区域。2023/1/9825.4.4 5.4.4 其他相关的概念其他相关的概念1.内-外测试不自交的多边形不自交的多边形、自相交的多边形自相交的多边形奇奇-偶规则偶规则（Odd-evenRule）从任意位置p作一条射线，若与该射线相交的多边形边的数目为奇数，则p是多边形内部点，否则是外部点。2023/1/983非零环绕数规则非零环绕数规则（NonzeroWindingNumberRule）首先使多边形的边变为矢量。将环绕数初始化为零。再从任意位置p作一条射线。当从p点沿射线方向移动时，对在每个方向上穿过射线的边计数，每当多边形的边从右到左穿过射线时，环绕数加1，从左到右时，环绕数减1。处理完多边形的所有相关边之后，若环绕数为非零，则p为内部点，否则，p是外部点。2023/1/9842.曲线边界区域的填充相交计算2023/1/9855.5 5.5 字符处理字符处理ASCI码码：“美国信息交换用标准代码集”(AmericanStandard Code for Information Interchange)，简称ASCI码。国国际际码码：“中华人民共和国国家标准信息交换编码，简称为国际码，代号GB231280。字库字库：字库中储存了每个字符的图形信息。矢量字库矢量字库和点阵字库点阵字库2023/1/9865.5.1 5.5.1 点阵字符点阵字符在点阵表示中，每个字符由一个点阵位图点阵位图来表示显示时显示时：形成字符的象素图案字符的象素图案5.5.2 5.5.2 矢量字符矢量字符矢量字符采用直线和曲线段来描述字符形状，矢量字符库中记录的是笔划信息笔划信息。显示时显示时：解释字符的每个笔划信息2023/1/9885.6 5.6 属性处理属性处理当前属性值表当前属性值表5.6.1 5.6.1 线型和线宽线型和线宽1.线型处理实心段和中间空白段的长度（象素数目）可用象象素素模模板板(pixel mask)指定。存在问题存在问题：如何保持任何方向的划线长度近似地相等2023/1/989解决解决可根据线的斜率来调整实心段和中间空白段的象素数目。2023/1/9902.线刷子和方刷子处理线宽线刷子：垂直刷子、水平刷子线刷子：垂直刷子、水平刷子2023/1/991特点特点实现简单、效率高。斜线与水平(或垂直)线不一样粗。当线宽为偶数个象素时，线的中心将偏移半个象素。利用线刷子生成线的始末端总是水平或垂直的，看起来不太自然。解决解决：添加“线帽（linecap）”2023/1/9922023/1/993当比较接近水平的线与比较接近垂直的线汇合时，汇合处外角将有缺口2023/1/994解解决决：斜角连接（miter join）、圆连接（roundjoin）、斜切连接（beveljoin）2023/1/995方刷子方刷子特点特点：方刷子绘制的线条（斜线）比用线刷子所绘制的线条要粗一些方刷子绘制的斜线与水平（或垂直）线不一样粗方刷子绘制的线条自然地带有一个“方线帽”2023/1/9963.其它线宽处理方式区域填充区域填充改变刷子形状改变刷子形状：4.曲线的线型和线宽线型线型：可采用象素模板象素模板的方法2023/1/998线宽线宽：线刷子线刷子方刷子方刷子要显示一致的曲线宽度可通过旋转刷子方向以使其在沿曲线移动时与斜率方向一致，圆弧刷子圆弧刷子采用填充的办法采用填充的办法。2023/1/9995.6.2 5.6.2 字符的属性字符的属性字体字体、字形字形、字号字号、字间距、行间距等等。一般字体确定风格，字形确定外观，字号确定尺寸。字符的常用属性字符的常用属性字符串的属性字符串的属性文本高度、文本宽度（扩展/压缩因子）、字符方向、文本路径方向、对齐方式（左对齐，中心对齐，或右对齐，指定起始、终止点）、文本字体、字符的颜色属性等。反绘（从右到左）、倒绘（旋转180）、写方式（替换或与方式）等。2023/1/91015.6.3 5.6.3 区域填充属性区域填充属性区域填充属性选择包括颜色颜色、图案图案和透明度透明度。根据图案和透明度属性来填充平面区域的基本思想是：首先用模板定义各种图案。然后，修改填充的扫描转换算法：在确定了区域内一象素之后，不是马上往该象素填色而是先查询模板位图的对应位置。若是以透明方式填充图案，则当模板位图的对应位置为1时，用前景色写象素，否则，不改变该象素的值。若是以不透明方式填充图案，则视模板位图对应位置为1或0来决定是用前景色还是背景色去写象素。2023/1/9103确定区域与模板之间的位置关系（对齐方式）：一种对齐方式是把有模板原点与填充区域边界或内部的某点对齐一种对齐方式是把模板原点与填充区域外部的某点对齐2023/1/91045.7 5.7 反走样反走样用离散量表示连续量引起的失真，就叫做走样（走样（Liasing）。2023/1/9105走样现象走样现象：一是光栅图形产生的阶梯形一是图形中包含相对微小的物体时，这些物体在静态图形中容易被丢弃或忽略，在动画序列中时隐时现，产生闪烁2023/1/91062023/1/9107用于减少或消除这种效果的技术，称为反反走走样样（antialiasing）。一种简单方法：过取样（过取样（supersampling），或后滤波后滤波区域取样（区域取样（area sampling），或前滤波前滤波2023/1/91085.7.1 过取样过取样简单过取样简单过取样2023/1/9109重叠过取样重叠过取样2023/1/9110基于加权模板的过取样基于加权模板的过取样2023/1/91115.7.2 5.7.2 简单的区域取样简单的区域取样2023/1/9112如何计算直线段与象素相交区域的面积？2023/1/9113可以利用一种求相交区域的近似面积的离散计算方法：(1)将屏幕象素分割成n个更小的子象素，(2)计算中心落在直线段内的子象素的个数m，(3)m/n为线段与象素相交区域面积的近似值。特点特点：直线段对一个象素亮度的贡献与两者重叠区域的面积成正比相同面积的重叠区域对象素的贡献相同2023/1/91145.7.3 5.7.3 加权区域取样加权区域取样加权区域取样原理加权区域取样原理假想一个连续的加权曲面（或过滤函数）覆盖象素。当直线条经过该象素时，该象素的灰度值是在二者重叠区域上对滤波器（过滤函数）进行积分的积分值。2023/1/91152023/1/9116特点特点：接近理想直线的象素将被分配更多的灰度值；相邻两个象素的滤波器相交，有利于缩小直线条上相邻象素的灰度差。2023/1/9117