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

《【教学课件】第5章基本图形生成算法.ppt》由会员分享，可在线阅读，更多相关《【教学课件】第5章基本图形生成算法.ppt（117页珍藏版）》请在三一办公上搜索。

1、2023/8/6,1,第5章 基本图形生成算法,提出问题,如何在指定的输出设备上根据坐标描述构造基本二维几何图形（点、直线、圆、椭圆、多边形域、字符串及其相关属性等）。,2023/8/6,2,图形的生成：是在指定的输出设备上，根据坐标描述构造二维几何图形。图形的扫描转换：在光栅显示器等数字设备上确定一个最佳逼近于图形的象素集的过程。,2023/8/6,3,5.1 直线的扫描转换,直线的绘制要求：1.直线要直2.直线的端点要准确，即无定向性和断裂情况3.直线的亮度、色泽要均匀4.画线的速度要快5.要求直线具有不同的色泽、亮度、线型等,2023/8/6,4,5.1.1 数值微分法(DDA法),解决

2、的问题：给定直线两端点P0(x0,y0)和P1(x1,y1)，画出该直线。,直线的微分方程：,2023/8/6,5,DDA算法原理：,=1/max(|x|,|y|),2023/8/6,6,max(|x|,|y|)=|x|，即|k|1的情况：,max(|x|,|y|)=|y|，此时|k|1：,2023/8/6,7,程序注意：round(x)=(int)(x+0.5),2023/8/6,8,特点：增量算法直观、易实现不利于用硬件实现,2023/8/6,9,5.1.2 中点Bresenham算法,直线的方程,该直线方程将平面分为三个区域：对于直线上的点，F(x,y)=0；对于直线上方的点，F(x,y

3、)0；对于直线下方的点，F(x,y)0。,2023/8/6,10,2023/8/6,11,基本原理：假定0k1，x是最大位移方向,2023/8/6,12,判别式：,则有：,2023/8/6,13,误差项的递推d0：,2023/8/6,14,误差项的递推d0：,2023/8/6,15,初始值d的计算,2023/8/6,16,0k1时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

4、)更新为(x+1,y)，d更新为d-k。4.当直线没有画完时，重复步骤3。否则结束。,2023/8/6,17,改进：用2dx代替d1.输入直线的两端点P0(x0,y0)和P1(x1,y1)。2.计算初始值x、y、d=x-2y、x=x0、y=y0。3.绘制点(x,y)。判断d的符号。若d0，则(x,y)更新为(x+1,y+1)，d更新为 d+2x-2y；否则(x,y)更新为(x+1,y),d更新为d-2y。4.当直线没有画完时，重复步骤3。否则结束。程序,2023/8/6,18,5.1.3 改进的Bresenham算法,假定直线段的0k1基本原理：,2023/8/6,19,误差项的计算d初=0，

5、每走一步：d=d+k 一旦y方向上走了一步，d=d-1,2023/8/6,20,算法步骤：1.输入直线的两端点P0(x0,y0)和P1(x1,y1)。2.计算初始值x、y、d=0、x=x0、y=y0。3.绘制点(x,y)。4.d更新为d+k，判断d的符号。若d0.5，则(x,y)更新为(x+1,y+1)，同时将d更新为d-1；否则(x,y)更新为(x+1,y)。5.当直线没有画完时，重复步骤3和4。否则结束。,2023/8/6,21,改进1：令e=d-0.5,e初=-0.5，每走一步有e=e+k。if(e0)then e=e-1,2023/8/6,22,算法步骤为：1.输入直线的两端点P0(x

6、0,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/8/6,23,改进2：用2ex来替换ee初=-x，每走一步有e=e+2y。if(e0)then e=e-2x,2023/8/6,24,算法步骤：1.输入直线的两端点P0(x0,y0)和P1(x1,y1)。2.计算初始值x、y、e=-x、x=x0、y=y0。3.绘制点(x,y)。4.e更新为e

7、+2y，判断e的符号。若e0，则(x,y)更新为(x+1,y+1)，同时将e更新为e-2x；否则(x,y)更新为(x+1,y)。5.当直线没有画完时，重复步骤3和4。否则结束。,2023/8/6,25,程序几种画线算法的比较,2023/8/6,26,5.2 圆的扫描转换,解决的问题：绘出圆心在原点，半径为整数R的圆x2+y2=R2,5.2.1 八分法画圆,八分法画圆,2023/8/6,27,(y,x),(-y,x),(-x,y),(-x,-y),(-y,-x),(y,-x),(x,-y),2023/8/6,28,解决问题：,2023/8/6,29,5.2.2 简单方程产生圆弧,算法原理：利用其

8、函数方程，直接离散计算,圆的函数方程为：,2023/8/6,30,圆的极坐标方程为：,2023/8/6,31,5.2.3 中点Bresenham画圆,构造函数F(x,y)=x2-y2-R2。对于圆上的点，有F(x,y)=0；对于圆外的点，F(x,y)0；而对于圆内的点，F(x,y)0。算法原理,2023/8/6,32,2023/8/6,33,当d0时，下一点取Pu(xi+1,yi)；当d0时，下一点取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/8/6,34

9、,误差项的递推d0：,2023/8/6,35,d0：,2023/8/6,36,判别式的初始值,2023/8/6,37,算法步骤：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/8/6,38,改进：用d-0.25代替d算法步骤：1.输入圆的半径R。2.计算初始值d=1-R、x=0、y=R。3.绘制点(x,y)

10、及其在八分圆中的另外七个对称点。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/8/6,39,5.3 椭圆的扫描转换,5.3.1 椭圆的特征,2023/8/6,40,对于椭圆上的点，有F(x,y)=0；对于椭圆外的点，F(x,y)0；对于椭圆内的点，F(x,y)0。解决问题：,2023/8/6,41,以弧上斜率为1的点作为分界将第一象限椭圆弧分为上下两部分。,2023/8/6,42,引理5-1：若在当前中点，法向量的y分

11、量比x分量大，即,而在下一个中点，不等号改变方向，则说明椭圆弧从上部分转入下部分。,法向量,2023/8/6,43,5.3.2 椭圆的中点Bresenham算法,算法原理,2023/8/6,44,先推导上半部分的椭圆绘制公式,2023/8/6,45,判别式,若d10，取Pu(xi+1,yi)若d10，取Pd(xi+1,yi-1),2023/8/6,46,误差项的递推d10：,2023/8/6,47,d10：,判别式的初始值,2023/8/6,49,再来推导椭圆弧下半部分的绘制公式原理,2023/8/6,50,判别式,若d20，取Pl(xi,yi-1)若d20，取Pr(xi+1,yi-1),20

12、23/8/6,51,误差项的递推d20：,2023/8/6,52,d20：,2023/8/6,53,注意：上半部分的终止判别下半部分误差项的初值算法步骤：1.输入椭圆的长半轴a和短半轴b。2.计算初始值d=b2+a2(-b+0.25)、x=0、y=b。3.绘制点(x,y)及其在四分象限上的另外三个对称点。,2023/8/6,54,4.判断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)a2(y-0.5)时，重复步骤3和4。否则转到步骤6

13、。6.用上半部分计算的最后点(x,y)来计算下半部分中d的初值：,2023/8/6,55,7.绘制点(x,y)及其在四分象限上的另外三个对称点。8.判断d的符号。若d0，则先将d更新为b2(2xi+2)+a2(-2yi+3)，再将(x,y)更新为(x+1,y-1)；否则先将d更新为d+a2(-2yi+3)，再将(x,y)更新为(x,y-1)。9.当y0时，重复步骤7和8。否则结束。程序,2023/8/6,56,5.4 多边形的扫描转换与区域填充,多边形的扫描转换主要是通过确定穿越区域的扫描线的覆盖区间来填充，区域填充是从给定的位置开始涂描直到指定的边界条件为止。,2023/8/6,57,5.4

14、.1 多边形的扫描转换,顶点表示用多边形的顶点序列来刻划多边形点阵表示是用位于多边形内的象素的集合来刻划多边形扫描转换多边形或多边形的填充：从多边形顶点表示到点阵表示的转换。,1.什么是多边形的扫描转换,2023/8/6,58,2.x-扫描线算法基本思想,2023/8/6,59,算法步骤：(1)确定多边形所占有的最大扫描线数，得到多边形顶点的最小和最大y值（ymin和ymax）。(2)从y=ymin到y=ymax，每次用一条扫描线进行填充。(3)对一条扫描线填充的过程可分为四个步骤：a.求交b.排序c.交点配对d.区间填色,2023/8/6,60,存在问题：当扫描线与多边形顶点相交时，交点的取

15、舍问题。,2023/8/6,61,解决：当扫描线与多边形的顶点相交时，若共享顶点的两条边分别落在扫描线的两边，交点只算一个；若共享顶点的两条边在扫描线的同一边，这时交点作为零个或两个。,2023/8/6,62,0,1,1,1,1,0,2,2,2,填充过程实例,2023/8/6,63,3.改进的有效边表算法（Y连贯性算法）,改进原理：处理一条扫描线时，仅对有效边求交利用扫描线的连贯性利用多边形边的连贯性,2023/8/6,64,有效边（Active Edge）：指与当前扫描线相交的多边形的边，也称为活性边。有效边表（Active Edge Table,AET）：把有效边按与扫描线交点x坐标递增的

16、顺序存放在一个链表中，此链表称为有效边表。有效边表的每个结点：x ymax 1/k next,2023/8/6,65,边表（Edge Table）边表的构造：(1)首先构造一个纵向链表，链表的长度为多边形所占有的最大扫描线数，链表的每个结点，称为一个桶，则对应多边形覆盖的每一条扫描线。(2)将每条边的信息链入与该边最小y坐标（ymin）相对应的桶处。也就是说，若某边的较低端点为ymin，则该边就放在相应的扫描线桶中。,2023/8/6,66,(3)每条边的数据形成一个结点，内容包括：该扫描线与该边的初始交点x（即较低端点的x值），1/k，以及该边的最大y值ymax。x|ymin ymax 1/

17、k NEXT(4)同一桶中若干条边按X|ymin由小到大排序，若X|ymax 相等，则按照1/m由小到大排序。,2023/8/6,67,解决顶点交点计为1时的情形：,2023/8/6,68,2023/8/6,69,2023/8/6,70,算法步骤：(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)，否则结束。,2

18、023/8/6,71,5.4.2 边缘填充算法,边缘填充算法算法简单，但对于复杂图型，每一象素可能被访问多次栅栏填充算法栅栏指的是一条过多边形顶点且与扫描线垂直的直线。它把多边形分为两半。,2023/8/6,72,边标志算法分为两个步骤：(1)打标记(2)填充当用软件实现本算法时，速度与改进的有效边表算法相当，但本算法用硬件实现后速度会有很大提高。,2023/8/6,73,5.4.3 区域填充,区域是指已经表示成点阵形式的填充图形，它是像素集合。4-邻接点和8-邻接点,2023/8/6,74,4-连通区域和8-连通区域把位于给定区域的边界上的象素一一列举出来的方法称为边界表示法。边界填充算法（

19、Boundary-fill Algorithm）。枚举出给定区域内所有象素的表示方法称为内点表示。泛填充算法（Flood-fill Algorithm）,2023/8/6,76,1.边界填充算法算法的输入：种子点坐标(x,y)，填充色和边界颜色。栈结构实现4-连通边界填充算法的算法步骤为：种子象素入栈；当栈非空时重复执行如下三步操作：(1)栈顶象素出栈；(2)将出栈象素置成填充色；(3)检查出栈象素的4-邻接点，若其中某个象素点不是边界色且未置成多边形色，则把该象素入栈。,2023/8/6,77,栈结构实现8-连通边界填充算法的算法步骤为：种子象素入栈；当栈非空时重复执行如下三步操作：(1)栈

20、顶象素出栈；(2)将出栈象素置成填充色；(3)检查出栈象素的8-邻接点，若其中某个象素点不是边界色且未置成多边形色，则把该象素入栈。,2023/8/6,78,特点：可以用于填充带有内孔的平面区域。把太多的象素压入堆栈改进通过沿扫描线填充水平象素段，来代替处理4-邻接点和8-邻接点。,2023/8/6,79,沿扫描线填充水平象素段的4-连通边界填充算法步骤：种子象素入栈；当栈非空时作如下三步操作：(1)栈顶象素出栈；(2)填充出栈象素所在扫描行的连续象素段，直到遇到边界象素为止，即每出栈一个象素，就对包含该象素的整个扫描线区间进行填充；(3)在区间中检查与当前扫描线相邻的上下两条扫描线的有关象素

21、是否全为边界象素或已填充的象素，若存在非边界、未填充边界的象素，则把每一区间的最右象素取作种子象素入栈。,2023/8/6,80,2.泛填充算法算法的输入：种子点坐标(x,y)，填充色和内部点的颜色。算法原理：算法从指定的种子(x,y)开始，用所希望的填充颜色赋给所有当前为给定内部颜色的象素点。,2023/8/6,81,8-连通泛填充算法步骤如下：种子象素入栈；当栈非空时重复执行如下三步操作：(1)栈顶象素出栈；(2)将出栈象素置成填充色；(3)检查出栈象素的8-邻接点，若其中某个象素点不是给定内部点的颜色且未置成新的填充色，则把该象素入栈。,2023/8/6,82,注意：当以边界表示时，4-

22、连通边界填充算法只能填充4-连通区域，8-连通边界填充算法也只能填充8-连通区域。当以内点表示时，8-连通泛填充算法可以填充8-连通区域也可以填充4-连通区域，当然4-连通泛填充算法还是只能填充4-连通区域。,2023/8/6,83,5.4.4 其他相关的概念,1.内-外测试不自交的多边形、自相交的多边形奇-偶规则（Odd-even Rule）从任意位置p作一条射线，若与该射线相交的多边形边的数目为奇数，则p是多边形内部点，否则是外部点。,2023/8/6,84,非零环绕数规则（Nonzero Winding Number Rule）首先使多边形的边变为矢量。将环绕数初始化为零。再从任意位置p

23、作一条射线。当从p点沿射线方向移动时，对在每个方向上穿过射线的边计数，每当多边形的边从右到左穿过射线时，环绕数加1，从左到右时，环绕数减1。处理完多边形的所有相关边之后，若环绕数为非零，则p为内部点，否则，p是外部点。,2023/8/6,85,2.曲线边界区域的填充相交计算,2023/8/6,86,5.5 字符处理,ASCI码：“美国信息交换用标准代码集”(American Standard Code for Information Interchange)，简称ASCI码。国际码：“中华人民共和国国家标准信息交换编码，简称为国际码，代号GB231280。字库：字库中储存了每个字符的图形信息。

24、矢量字库和点阵字库,5.5.1 点阵字符,在点阵表示中，每个字符由一个点阵位图来表示显示时：形成字符的象素图案,2023/8/6,88,5.5.2 矢量字符,矢量字符采用直线和曲线段来描述字符形状，矢量字符库中记录的是笔划信息。显示时：解释字符的每个笔划信息,2023/8/6,89,5.6 属性处理,当前属性值表,5.6.1 线型和线宽,1.线型处理实心段和中间空白段的长度（象素数目）可用象素模板(pixel mask)指定。存在问题：如何保持任何方向的划线长度近似地相等,2023/8/6,90,解决可根据线的斜率来调整实心段和中间空白段的象素数目。,2023/8/6,91,2.线刷子和方刷子

25、处理线宽线刷子：垂直刷子、水平刷子,2023/8/6,92,特点实现简单、效率高。斜线与水平(或垂直)线不一样粗。当线宽为偶数个象素时，线的中心将偏移半个象素。利用线刷子生成线的始末端总是水平或垂直的，看起来不太自然。解决：添加“线帽（line cap）”,2023/8/6,93,2023/8/6,94,当比较接近水平的线与比较接近垂直的线汇合时，汇合处外角将有缺口,2023/8/6,95,解决：斜角连接（miter join）、圆连接（round join）、斜切连接（bevel join）,2023/8/6,96,方刷子,特点：方刷子绘制的线条（斜线）比用线刷子所绘制的线条要粗一些方刷子绘

26、制的斜线与水平（或垂直）线不一样粗方刷子绘制的线条自然地带有一个“方线帽”,3.其它线宽处理方式区域填充改变刷子形状：,2023/8/6,98,4.曲线的线型和线宽线型：可采用象素模板的方法,2023/8/6,99,线宽：线刷子方刷子要显示一致的曲线宽度可通过旋转刷子方向以使其在沿曲线移动时与斜率方向一致，圆弧刷子采用填充的办法。,5.6.2 字符的属性,字体、字形、字号、字间距、行间距等等。一般字体确定风格，字形确定外观，字号确定尺寸。字符的常用属性,2023/8/6,101,字符串的属性文本高度、文本宽度（扩展/压缩因子）、字符方向、文本路径方向、对齐方式（左对齐，中心对齐，或右对齐，指定

27、起始、终止点）、文本字体、字符的颜色属性等。反绘（从右到左）、倒绘（旋转180）、写方式（替换或与方式）等。,5.6.3 区域填充属性,区域填充属性选择包括颜色、图案和透明度。,2023/8/6,103,根据图案和透明度属性来填充平面区域的基本思想是：首先用模板定义各种图案。然后，修改填充的扫描转换算法：在确定了区域内一象素之后，不是马上往该象素填色而是先查询模板位图的对应位置。若是以透明方式填充图案，则当模板位图的对应位置为1时，用前景色写象素，否则，不改变该象素的值。若是以不透明方式填充图案，则视模板位图对应位置为1或0来决定是用前景色还是背景色去写象素。,2023/8/6,104,确定区

28、域与模板之间的位置关系（对齐方式）：一种对齐方式是把有模板原点与填充区域边界或内部的某点对齐一种对齐方式是把模板原点与填充区域外部的某点对齐,2023/8/6,105,5.7 反走样,用离散量表示连续量引起的失真，就叫做走样（Liasing）。,2023/8/6,106,走样现象：一是光栅图形产生的阶梯形一是图形中包含相对微小的物体时，这些物体在静态图形中容易被丢弃或忽略，在动画序列中时隐时现，产生闪烁,2023/8/6,107,2023/8/6,108,用于减少或消除这种效果的技术，称为反走样（antialiasing）。一种简单方法：,过取样（supersampling），或后滤波区域取样

29、（area sampling），或前滤波,2023/8/6,109,5.7.1 过取样,简单过取样,2023/8/6,110,重叠过取样,2023/8/6,111,基于加权模板的过取样,2023/8/6,112,5.7.2 简单的区域取样,2023/8/6,113,如何计算直线段与象素相交区域的面积？,2023/8/6,114,可以利用一种求相交区域的近似面积的离散计算方法：(1)将屏幕象素分割成n个更小的子象素，(2)计算中心落在直线段内的子象素的个数m，(3)m/n为线段与象素相交区域面积的近似值。特点：直线段对一个象素亮度的贡献与两者重叠区域的面积成正比相同面积的重叠区域对象素的贡献相同,2023/8/6,115,5.7.3 加权区域取样,加权区域取样原理假想一个连续的加权曲面（或过滤函数）覆盖象素。当直线条经过该象素时，该象素的灰度值是在二者重叠区域上对滤波器（过滤函数）进行积分的积分值。,2023/8/6,116,2023/8/6,117,特点：接近理想直线的象素将被分配更多的灰度值；相邻两个象素的滤波器相交，有利于缩小直线条上相邻象素的灰度差。,