CG第3章基本图形生成算法C课件

1、第5章 基本图形生成算法 图形生成: 是在指定的输出设备上根据坐标描述构造基本二维几何图形（点、直线、圆、椭圆、多边形域、字符串及其相关属性等）。对于光栅显示器来说，将屏幕看作像素矩阵，在该矩阵上。确定一个像素集合来逼近图形。2022/7/2715.1 直线的扫描转换The lines of this objectappear continuousHowever, they aremade of pixels2022/7/272图形的扫描转换 在光栅显示器等设备上确定一个最佳逼近于图形象素集的过程，如下图所示：5.1 直线的扫描转换2022/7/2735.1 直线的扫描转换直线的绘制要求：1.

2、直线要直2.直线的端点要准确， 即无定向性和断裂情况3.直线的亮度、色泽要均匀4.画线的速度要快5. 直线具有不同的色泽、亮度、线型等直线绘制算法有：逐点比较法、正负法、数值微分法和中点Breshenham算法等。2022/7/274数值微分法（DDA方法， Digital Differential Analyzer ）要解决的问题：给定直线两端点P0(x0,y0)和P1(x1,y1)，画出该直线。直线的方程为注：1、仅需要计算一次m； 2、x每增加一个单位，y只需加上一个m， 回避了乘法运算，提高了运算效率。2022/7/275问题：若|m|1, ?x与y互换；m与1/m互换x=x+1y=y

3、+12022/7/276若直线为参数方程表示：其中：令：则t 的每次增量为：故，第 i 步时：于是：其中： 均为常数，上式即给出了一个迭代算法。 2022/7/277特别地：当 max(|x|,|y|)=|x|，即 |m|1时：当 max(|x|,|y|)=|y|，即 |m|1时：2022/7/278 DDA是一种增量算法,直观、易实现；但其中的x，y，m都要用浮点数，计算较大, 且要对x，y作取整运算，费时且不利于用硬件实现。 图5-3 DDA算法生成直线段(xi,yi)(xi+1,round(yi+m)(round(xi+1/m),yi+1)2022/7/279Bresenham算法（Br

4、esenhams algorithm (1965)）J.E. Bresenham, Algorithm for computer control of a digital plotter, IBM Systems Journal, 1965, 3, pp. 25-30.该算法仅使用整数运算，运算速度大大提高，是最有效的算法之一。核心思想：分析直线与网格线的交点与网格点的距离。该距离与1/2的差称为误差项。2022/7/2710同样给定直线两端点P1(x1, y1)和P2(x2, y2)，可得直线的方程如下：该直线方程将平面分为三个区域：直线上的点， F(x,y)=0；直线上方的点，F(x,y)

5、0；直线下方的点，F(x,y)0。2022/7/2711 基本原理： 假定0m1，x是最大位移方向，每次在x方向上加1，y方向上加1或0。图5-5 Brensemham算法生成直线的原理Q2022/7/2712由中点M可得判别式：有：Q问题：算法结束了吗？ 有无优化的可能？注意：计算di 的运算量并不小.2022/7/2713误差项的递推若di0，有di0Q2022/7/2714误差项的递推若di0，有Q2022/7/2715初始值d 的计算：故，关于di ，有:关于yi+1 ，有:2022/7/2716 由于只关心d 的符号, 故可用2xd 代替d 来摆脱小数计算, 得到整数运算, 于是：

6、d0 = 0.5 - k 2xd0 =x-2y d 0 时: d=d+1-m 2x d = 2x d+2x - 2y ；d 0 时: d=d - m 2x d = 2x d - 2y 。 整数级Bresenham算法2022/7/2717 0m1时Bresenham算法的步骤为： 1. 输入直线的两端点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

7、。 4. 当直线没有画完时，转步骤3；否则结束。2022/7/2718void Bresenham (int xl, int yl, int xr, int yr)int x, y; /* coordinates of pixel being drawn */int dy=yr-y1, dx=xr-x1;int ie; /* integer scaled error term */x=xl; y=yl; /* start at left endpoint */ie =dx-2 *dy; /* initialize the error term */while (x = xr) /* pixel

8、-drawing loop */PlotPixel (x, y); /* draw the pixel */if (ie 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。构造判别式：2022/7/2727误差项的递推 d0： 2022/7/2728d0： 误差项的递推2022/7/2729判别式的初始值2022/7/2730算法步骤：1.输入圆的半径R。2.计算初始值d=1.25-R、x=0、y=R。3.绘制点(x,y)及其在八分圆

9、中的另外七个对称点。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)2022/7/2739误差项的递推 d10：2022/7/2740误差项的递推 d10： 2022/7/2741判别式的初始值 ( 弧的起点为(0，b) )椭圆弧下半部分的绘制方法类似。5.4 多边形的扫描转换与区域填充 填充的意义：1.表示区域，2 .真实感显示。 多边形的扫描转换主要是从多边形的顶点表示到点阵表示的转换。 区域填充是从给定

10、的位置开始涂描直到指定的边界条件为止。2022/7/27435.4.1 多边形的扫描转换 多边形的表示方法有顶点表示和点阵表示。前者用多边形的顶点序列来刻划多边形,几何意义强,占内存少，但不能直接用于显示；后者用位于多边形内的象素的集合来刻划多边形,方便显示,但几何意义丢失。 故需要进行多边形扫描转换,即: 从多边形的顶点表示到点阵表示的转换。1. 什么是多边形的扫描转换2022/7/27445.4.1 多边形的扫描转换1. 逐点判断算法基本思想：帧缓冲器中对每个象素进行扫描，确定它们是否在多边形内（从该象素点出发向外发射射线，若有奇数个交点，则在多边形内，否则在多边形外）。使用一个布尔量in

11、side (P, x, y)来指示当前点是否在多边形内的状态，从而给出多边形内的点的集合。然后对多边形内的点着多边形颜色，否则着背景色。特点：程序简单，但速度太慢。原因: (1) 割断了各项素之间的联系；(2) 孤立地考察各象素与多边形的内外关系，使得几乎所有象素都要判断；(3) 每次判断需要多次求交，需要大量乘除运算，效率较低。2022/7/27455.4.1 多边形的扫描转换2. 扫描线算法特点：综合利用了相邻象素之间的连贯性，避免了对象素的逐点判断和反复求交的运算，达到了减少运算次数和提高速度的目的。具体地：综合利用了（1）区域的连贯性； （2）扫描线连贯性； （3）边的连贯性。2022

12、/7/2746 2.1. x-扫描线算法 基本思想：按扫描线顺序计算扫描线与多边形相交区间，再用指定的颜色显示这些区间的象素。 y3的扫描线与多边形的边界相交于点(2,3)、(4,3)、(7,3)、(9,3)，定义了多边形内的两个区间，其中的象素应取填充色。2022/7/2747算法步骤：(1)确定多边形所占有的最大扫描线数，得到多边形顶点的最小和最大y值（ymin和ymax）。(2)从y=ymin到y=ymax，每次用一条扫描线进行填充。(3)对一条扫描线填充的过程可分为四个步骤： a. 求交， b. 排序， c. 交点配对， d. 区间填色2022/7/2748 存在问题：当扫描线与多边形

13、顶点相交时，交点如何取舍? 若共享顶点的两条边分别落在扫描线的两边，交点只算一个； 若共享顶点的两条边在扫描线的同一边，这时交点作为零个或两个。2022/7/27492.2. y连贯性算法 也叫有效(活性)边表算法,是对x-扫描线算法的改进。处理一条扫描线时，仅对有效边求交；利用扫描线的连贯性；利用多边形边的连贯性 xi+1=xi+1/k。2022/7/2750有效边（Active Edge）：指与当前扫描线相交的多边形的边，也称为活性边。有效边表（Active Edge Table, AET）：把有效边按与扫描线交点x坐标递增的顺序存放在一个链表中，此链表称为有效边表。2022/7/2751

14、多边形及其有效边表和边表 边表（Edge Table，ET）的构造：1234567891011123-1/3353/485-1/2891/21122/5712-1795桶p3p2p3p4p5p4p5p6p2p1p0p1p0p6x|yminymax1/knext(c) 边表62022/7/2752 边表（Edge Table）的构造：(1)首先构造一个纵向链表,链表的长度为多边形所占有的最大扫描线数,链表的每个结点(称为一个桶)则对应于多边形覆盖的每一条扫描线。(2)将每条边的信息链入与该边最小y坐标（ymin ）相对应的桶处。也就是说,若某边的较低端点为ymin, 则该边就放在相应的扫描线桶中

15、。2022/7/2753(3)每条边的数据形成一个结点,内容包括：该扫描线与该边的初始交点x(即较低端点的x值)、1/k、该边的最大y值ymax。有效边表的结点存放对应边的有关信息：(4)同一桶中若干条边按x|ymin由小到大排序，若x|ymax 相等，则按照1/ k由小到大排序。x|ymin ymax 1/k NEXT2022/7/2754多边形及其有效边表和边表2022/7/27551.4 12 0.47 12 -17 9 511.5 9 0.5 y=8 的有效边表 有效边表（ Active Edge Table, AET ）的构造：2.5 12 0.4 7 12 -1 y=11的有效边表

16、 2022/7/2756解决顶点交点计为1时的情形：2022/7/2757算法步骤：(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)，否则结束。2022/7/27585.4.3 区域填充 区域是指已经表示成点阵形式的填充图形,它是像素集合。 区域表示可用边界表示法和内点表示法。4-邻接点和8-邻接点，4-连通区

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

18、栈。2022/7/27628-连通边界填充算法 用栈结构实现，步骤为：种子象素入栈；当栈非空时重复执行如下三步操作：(1)栈顶象素出栈；(2)将出栈象素置成填充色；(3)检查出栈象素的8-邻接点，若其中某个象素点不是边界色且未置成多边形色，则把该象素入栈。2022/7/2763 特点：可以用于填充带有内孔的平面区域，但把太多的象素压入堆栈 改进：通过沿扫描线填充水平象素段，来代替处理4-邻接点和8-邻接点。2022/7/2764沿扫描线填充象素段的4-连通边界填充算法: (P131 图5-34)2022/7/27652022/7/2766 种子象素入栈；当栈非空时作如下三步操作：(1)栈顶象素

19、出栈；(2)填充出栈象素所在扫描行的连续象素段,直到遇到边界象素为止；(3)在区间中检查与当前扫描线相邻的上下两条扫描线的有关象素,若存在非边界、未填充的象素，则把每一区间的最右象素取作种子象素入栈。2022/7/27672.泛填充算法 用于区域重新着色。 算法的输入包括: 种子点坐标(x,y)，填充色和内部点的颜色。 算法原理：算法从指定的种子(x,y)开始，用指定的填充颜色赋给所有当前为给定内部颜色的象素点。也分为：4-连通泛填充算法和8-连通泛填充算法2022/7/2768 4 -连通(8-连通)泛填充算法步骤如下： 种子象素入栈；当栈非空时重复执行如下三步操作： (1)栈顶象素出栈；

20、(2)将出栈象素置成填充色； (3)检查出栈象素的4-邻接点(8-邻接点),若其中某个象素点不是给定内部点的颜色且未置成新的填充色，则把该象素入栈。2022/7/27695.5 字符处理 ASCI码：“美国信息交换用标准代码集”(American Standard Code for Information Interchange)。 国标码：“中华人民共和国国家标准信息交换编码”，简称为国标码，代号GB231280。 字库：字库中储存了每个字符的字符编码和图形信息。 矢量字库和点阵字库。 数字、字母和汉字等符号用于图形标注。2022/7/27705.5.1 点阵字符 在点阵表示中，每个字符由一

21、个点阵位图来表示，有7x9、9x16等多种。 显示时：形成字符的象素图案。 定义和显示直接、简单，但所占存储空间大，需采用压缩技术。5.5.2 矢量字符 矢量字符采用直线和曲线段来描述字符形状,矢量字符库中记录的是笔划信息。采用轮廓字形法来表示,如右图所示。 显示时,解释字符的每个笔划信息。2022/7/27725.6 属性处理图素和图段的外观,由其属性来控制。使用当前属性值进行显示输出。 5.6.1 线型和线宽1.线型处理 实心段和中间空白段的长度（象素数目）可用象素模板(pixel mask)来指定。 存在问题：如何保持任何方向的划线长度近似地相等2022/7/2773 解决办法：可根据线

22、的斜率来调整实心段和中间空白段的象素数目。2022/7/27742.线刷子和方刷子处理线宽 线刷子：垂直刷子、水平刷子2022/7/2775线刷子的优缺点：实现简单、效率高。斜线与水平(或垂直)线不一样粗。当线宽为偶数个象素时，线的中心将偏移半个象素。利用线刷子生成线的始末端总是水平或垂直的，看起来不太自然。故需添加“线帽（line cap）”2022/7/2776当比较接近水平的线与比较接近垂直的线汇合时，汇合处外角将有缺口。可采用斜角连接（miter join）、圆连接（round join）、斜切连接（bevel join）。2022/7/2777方刷子 方刷子绘制的线条（斜线）比用线刷子所绘制的线条要粗一些 方刷子绘制的斜线与水平（或垂直）线不一样粗 方刷子绘制的线条自然地带有一个“方线帽”2022/7/27784. 曲线的线型和线宽 线型：可采用象素模板的方法。 线宽：可采用线刷子、方刷子、圆弧刷子和区域填充方法。3. 处理线宽的其它方法 包括区域填充和改变刷子形状等。2022/7/27795.6.2 字符的属性 常用的属性有：字体、字形、字号、字间距、行间距等等。 一般字体确定风格,字形确定外观,字号确定尺寸。 字符的常用属性参数如图5-46所示。字符串的属性 文本高度、文本宽度（扩展/压缩因子）、字符方向、文本路径方向、对齐方式（左对齐