《计算机图形学教案第5章基本图形生成算法.ppt》由会员分享，可在线阅读，更多相关《计算机图形学教案第5章基本图形生成算法.ppt（129页珍藏版）》请在三一办公上搜索。
1、第5章 基本图形生成算法,本章要解决的问题 如何在指定的输出设备上根据坐标描述构造基本二维几何图形。,图形的生成：在指定的输出设备上，根据坐标描述构造二维几何图形。图形的扫描转换：在光栅显示器等数字设备上确定一个最佳逼近于图形的象素集的过程（连续图形到象素集的转换）。,5.1 直线的扫描转换,给定直线两端点P0(x0,y0)和P1(x1,y1)，画出该直线。要求：直、端点准确、色泽均匀、速度快等。,数值微分法(DDA法),直线的微分方程：,DDA算法原理：,=1/max(|x|,|y|),max(|x|,|y|)=|x|，即|k|1的情况：,max(|x|,|y|)=|y|，此时|k|1：,注
2、：round(x)=(int)(x+0.5),void DDAline(int x0,int y0,int x1,int y1)int dx,dy,epsl,k;float x,y,xIncre,yIncre;dx=x1-x0;dy=y1-y0;x=x0;y=y0;if(abs(dx)abs(dy)epsl=abs(dx);else epsl=abs(dy);xIncre=(float)(dx)/epsl;yIncre=(float)(dy)/epsl;for(k=0;k=epsl;k+)putpixel(int)(x+0.5),(int)(y+0.5);x+=xIncre;y+=yIncre
3、;,特点：增量算法直观、易实现不利于用硬件实现,中点Bresenham算法,该直线方程将平面分为三个区域：对于直线上的点，F(x,y)=0；对于直线上方的点，F(x,y)0；对于直线下方的点，F(x,y)0。,直线的方程：,基本原理：假定0k1，x是最大位移方向,判别式：,则有：,误差项的递推d0：,误差项的递推d0：,初始值d的计算,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
4、；否则(x,y)更新为(x+1,y)，d更新为d-k。4.当直线没有画完时，重复步骤3。否则结束。,改进：用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。否则结束。,2(0.5-k)x=x-2y,2(1-k)x=2x-2y,2(-k)x=-2y,void MidBhline(int x0,int y0,int x1,in
5、t y1)int dx,dy,d,UpIncre,DownIncre,x,y,xend;if(x0 x1)x=x1;x1=x0;x0=x;y=y1;y1=y0;y0=y;x=x0;y=y0;dx=x1-x0;dy=y1-y0;d=dx-2*dy;UpIncre=2*dx-2*dy;DownIncre=-2*dy;while(x=x1)putpixel(x,y);x+;if(d0)y+;d+=UpIncre;else d+=DownIncre;,改进的Bresenham算法,假定直线段的0k1基本原理：,误差项的计算d初=0，每走一步：d=d+k 一旦y方向上走了一步，d=d-1,算法步骤：1.
6、输入直线的两端点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。否则结束。,改进1：令e=d-0.5,e初=-0.5，每走一步有e=e+k。if(e0)then e=e-1,算法步骤为：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的符号
7、。若e0，则(x,y)更新为(x+1,y+1)，同时将e更新为e-1；否则(x,y)更新为(x+1,y)。5.当直线没有画完时，重复步骤3和4。否则结束。,改进2：用2ex来替换ee初=-x，每走一步有e=e+2y。if(e0)then e=e-2x,算法步骤：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。否则结束。,void B
8、hline(int x0,int y0,int x1,int y1)int x,y,dx,dy,e;if(x0 x1)x=x1;x1=x0;x0=x;y=y1;y1=y0;y0=y;dx=x1-x0;dy=y1-y0;x=x0;y=y0;e=-dx;while(x0)y+;e=e-2*dx;,思考题,对于前述几种直线生成算法和程序：1.当最大位移方向是y时，应如何修改？2.要达到通用时，应如何修改？,5.2 圆的扫描转换,解决的问题：绘出圆心在原点，半径为整数R的圆x2+y2=R2,八分法画圆,(y,x),(-y,x),(-x,y),(-x,-y),(-y,-x),(y,-x),(x,-y),
9、解决问题：,八分法画圆程序：,void circlePoint(int x,int y)putpixel(x,y);putpixel(y,x);putpixel(-y,x);putpixel(-x,y);putpixel(-x,-y);putpixel(-y,-x);putpixel(y,-x);putpixel(x,-y);,考虑通用：,void circlePoint(int x0,int y0,int x,int y)putpixel(x-x0,y-y0);putpixel(y-x0,x-y0);putpixel(-y+x0,x-y0);putpixel(-x+x0,y-y0);putp
10、ixel(-x+x0,-y+y0);putpixel(-y+x0,-x+y0);putpixel(y-x0,-x+y0);putpixel(x-x0,-y+y0);,简单方程产生圆弧,算法原理：利用其函数方程，直接离散计算,圆的函数方程为：,圆的极坐标方程为：,中点Bresenham画圆,构造函数F(x,y)=x2-y2-R2。对于圆上的点，有F(x,y)=0；对于圆外的点，F(x,y)0；而对于圆内的点，F(x,y)0。算法原理,当d0时：下一点取Pu(xi+1,yi)；当d0时：下一点取Pd(xi+1,yi-1)。,构造判别式：,误差项的递推d0：,d0：,判别式的初始值,算法步骤：1.输
11、入圆的半径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。否则结束。,改进：用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
12、，再将(x,y)更新为(x+1,y-1)。5.当xy时，重复步骤3和4。否则结束。,d 0.25,中点Bh画圆程序,void MidBhcircle(int r)int x,y,d;x=0;y=r;d=1-r;while(xy)circlePoint(x,y);if(d0)d+=2*x+3;else d+=2*(x-y)+5;y-;x+;,5.3 椭圆的扫描转换,椭圆的特征,椭圆上：F(x,y)=0椭圆内：F(x,y)0只需计算第一象限,四分椭圆,以弧上斜率为1的点作为分界将第一象限椭圆弧分为上下两部分。,两部分的最大位移方向不同,引理5-1：若在当前中点，法向量的y分量比x分量大，即,而在下
13、一个中点，不等号改变方向，则说明椭圆弧从上部分转入下部分。,法向量,椭圆的中点Bresenham算法,算法原理,x步长为1,y步长为1,先推导上半部分的椭圆绘制公式,判别式,若d10，取Pu(xi+1,yi)若d10，取Pd(xi+1,yi-1),误差项的递推d10：,d10：,判别式的初始值,再来推导椭圆弧下半部分的绘制公式原理,判别式,若d20，取Pl(xi,yi-1)若d20，取Pr(xi+1,yi-1),5-19 下半部分椭圆弧的绘制原理,误差项的递推d20：,d20：,注意：上半部分的终止判别:b2(x+1)a2(y-0.5)下半部分误差项的初值:用上半部的(x,y)计算算法步骤：1
14、.输入椭圆的长半轴a和短半轴b。2.计算初始值d=b2+a2(-b+0.25)、x=0、y=b。3.绘制点(x,y)及其在四分象限上的另外三个对称点。,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。6.用上半部分计算的最后点(x,y)来计算下半部分中d的初值：,7.绘制点(x,y)及其在四分象限上的另外三个对称点。8.判断d的符号。若d0，则先将d更新为b2(2xi+2)+
15、a2(-2yi+3)，再将(x,y)更新为(x+1,y-1)；否则先将d更新为d+a2(-2yi+3)，再将(x,y)更新为(x,y-1)。9.当y0时，重复步骤7和8。否则结束。,第一象限椭圆弧的扫描转换程序,void MidBhllipse(int a,int b)int x,y;float d1,d2;x=0;y=b;d1=b*b+a*a*(-b+0.25);putpixel(x,y);putpixel(-x,-y);putpixel(-x,y);putpixel(x,-y);,while(b*b*(x+1)a*a*(y-0.5)if(d1=0)d1+=b*b*(2*x+3);x+;el
16、se d1+=(b*b*(2*x+3)+a*a*(-2*y+2);x+;y-;putpixel(x,y);putpixel(-x,-y);putpixel(-x,y);putpixel(x,-y);/*上半部*/,d2=b*b*(x+0.5)*(x+0.5)+a*a*(y-1)*(y-1)-a*a*b*b;while(y0)if(d2=0)d2+=b*b*(2*x+2)+a*a*(-2*y+3);x+;y-;else d2+=a*a*(-2*y+3);y-;putpixel(x,y);putpixel(-x,-y);putpixel(-x,y);putpixel(x,-y);,5.4 多边形的
17、扫描转换与区域填充,多边形的扫描转换多边形填充 给定多边形顶点，填充多边形多边形内的所有点。区域填充种子填充 给定区域内的一点（种子），填充围定该点的边界内的所有点。,多边形的扫描转换,从多边形顶点表示到点阵表示的转换。顶点表示：用多边形的顶点序列来刻划多边形。点阵表示：用位于多边形内的象素的集合来刻划多边形。,x-扫描线算法,基本思想,用水平扫描线扫描填充多边形区域,算法步骤：(1)确定多边形所占有的最大扫描线数，得到多边形顶点的最小和最大y值（ymin和ymax）。(2)从y=ymin到y=ymax，每次用一条扫描线进行填充。(3)对一条扫描线填充的过程可分为四个步骤：a.求交 b.排序c
18、.交点配对 d.区间填色,存在问题：当扫描线与多边形顶点相交时，交点的取舍问题。,解决：当扫描线与多边形的顶点相交时，若共享顶点的两条边分别落在扫描线的两边，交点只算一个；若共享顶点的两条边在扫描线的同一边，这时交点作为零个或两个。,改进的有效边表算法（Y连贯性算法）,改进原理：处理一条扫描线时，仅对有效边求交利用扫描线的连贯性利用多边形边的连贯性,有效边：指与当前扫描线相交的多边形的边，也称为活性边。有效边表：把有效边按与扫描线交点x坐标递增的顺序存放在一个链表中，此链表称为有效边表。有效边表的每个结点：x ymax 1/k next,边表的构造：(1)首先构造一个纵向链表，链表的长度为多边
19、形所占有的最大扫描线数，链表的每个结点称为一个桶，对应多边形覆盖的每一条扫描线。(2)将每条边的信息链入与该边最小y坐标（ymin）相对应的桶处。即：若某边的较低端点为ymin，则该边就放在相应的扫描线桶中。,(3)每条边的数据形成一个结点，内容包括：该扫描线与该边的初始交点x（即较低端点的x值），1/k，以及该边的最大y值ymax。x|ymin ymax 1/k NEXT(4)同一桶中若干条边按X|ymin由小到大排序，若X|ymax 相等，则按照1/k由小到大排序。,解决顶点交点计为1时的情形：,算法步骤：(1)初始化：构造边表，AET表置空；(2)将第一个不空的ET表中的边与AET表合并
20、；(3)由AET表中取出交点对进行填充。填充之后删除y=ymax的边；(4)yi+1=yi+1,根据xi+1=xi+1/k计算并修改AET表，同时合并ET表中y=yi+1桶中的边，按次序插入到AET表中，形成新的AET表；(5)AET表不为空则转(3)，否则结束。,边缘填充算法,基本思想：按任意顺序处理多边形的每条边，对于每条扫描线和每条多边形边的交点，将该扫描线上交点右方的所有象素取补。,算法依据：,多边形外的象素总是被访问偶数次，而多边形内的象素总是被访问奇数次。,对象素作偶数次取补则颜色不变，作奇数次取补则颜色被改变。,算法特点：,处理边的顺序任意,适合用于具有帧缓存的图形系统,算法简单
21、,每一象素可能被访问多次,栅栏填充算法,引入栅栏，以减少填充算法访问象素的次数。栅栏：与扫描线垂直的直线，通常过一顶点，且把多边形分为左右二半。基本思想：扫描线与多边形的边求交，将交点与栅栏之间的象素取补。减少了象素重复访问数目，但不彻底。,边界标志算法,对多边形的每一条边进行扫描转换，即对多边形边界所经过的象素作一个边界标志。填充。对每条与多边形相交的扫描线，按从左到右的顺序，逐个访问该扫描线上的象素，根据标志决定象素点的内外状态。,适合于硬件实现,区域填充算法,区域 指已经表示成点阵形式的填充图形，它是象素的集合。区域填充 指先将区域的一点赋予指定的颜色，然后将该颜色扩展到整个区域的过程。
22、区域填充算法要求区域是连通的。,内点表示 泛填充算法枚举区域内部像素内部像素着同一颜色边界与内部像素颜色不同边界表示 边界填充算法枚举边界像素边界上像素着同一颜色内部像素与边界颜色不同,4连通：8连通：,区域填充要求区域是连通的,边界填充算法,算法的输入：种子点坐标(x,y)填充色和边界颜色,栈结构实现4-连通边界填充算法的算法步骤为：种子象素入栈；当栈非空时重复执行如下三步操作：栈顶象素出栈；将出栈象素置成填充色；检查出栈象素的4-邻接点，若有非边界色象素点且未置成多边形色，则把该象素入栈。,特点：可以用于填充带有内孔的平面区域。把太多的象素压入堆栈。改进 通过沿扫描线填充水平象素段，来代替
23、处理4-邻接点和8-邻接点。,基于扫描线的4-连通边界填充算法步骤：种子象素入栈；当栈非空时作如下三步操作：栈顶象素出栈；填充出栈象素所在扫描行的连续象素段，直到遇到边界象素为止，即每出栈一个象素，就对包含该象素的整个扫描线区间进行填充；在区间中检查与当前扫描线相邻的上下两条扫描线的有关象素是否全为边界象素或已填充的象素，若存在非边界、未填充边界的象素，则把每一区间的最右象素取作种子象素入栈。,泛填充算法,算法的输入：种子点坐标(x,y)，填充色和内部点的颜色。算法原理：算法从指定的种子(x,y)开始，用所希望的填充颜色赋给所有当前为给定内部颜色的象素点。,4-连通泛填充算法步骤如下：种子象素
24、入栈；当栈非空时重复执行如下三步操作：栈顶象素出栈；将出栈象素置成填充色；检查出栈象素的4-邻接点，若其中某个象素点是给定内部点的颜色且未置成新的填充色，则把该象素入栈。,其他相关的概念,奇偶规则从任意位置p作一条射线，若与该射线相交的多边形边的数目为奇数，则p是多边形内部点，否则是外部点。,非零环绕数规则 首先使多边形的边变为矢量。将环绕数初始化为零。再从任意位置p作一条射线。当从p点沿射线方向移动时，对在每个方向上穿过射线的边计数，每当多边形的边从右到左穿过射线时，环绕数加1，从左到右时，环绕数减1。处理完多边形的所有相关边之后，若环绕数为非零，则p为内部点，否则，p是外部点。,曲线边界区
25、域的填充 关键在于扫描线与曲线的相交计算。,5.5 字符处理,ASCII码：“美国信息交换用标准代码集”(American Standard Code for Information Interchange)，简称ASCII码。国标码：“中华人民共和国国家标准信息交换编码，简称为国标码，代号GB231280。字库：字库中储存了每个字符的图形信息。矢量字库和点阵字库,点阵字符,内存中用一个点阵位图来表示一个字符，输出时根据点阵位图形成字符的象素图案。,点阵字符特点：,（1）占空间小，且规则。（2）不便缩放。适用于小字。,矢量字符,采用直线和曲线段来描述字符形状，矢量字符库中记录的是笔划信息。显示
26、时：解释字符的每个笔划信息,矢量字符特点：,（1）占空间大，且不规则。（2）便于无级缩放。,5.6 属性处理,字符的属性包括：亮度、颜色、线型等。输出时由当前属性表确定字符的属性。当前属性表可以设置和更改。,线型和线宽,线型处理 可用象素模板指定实心段和空白段的长度。存在问题：如何保持任何方向的划线长度近似地相等。,可根据线的斜率来调整实心段和中间空白段的象素数目。,解决：,线刷子和方刷子处理线宽 线刷子：垂直刷子、水平刷子,特点 实现简单、效率高。斜线与水平(或垂直)线不一样粗。当线宽为偶数个象素时，线的中心将偏移半个象素。利用线刷子生成线的始末端总是水平或垂直的，看起来不太自然。解决：添加
27、“线帽（line cap）”,当比较接近水平的线与比较接近垂直的线汇合时，汇合处外角将有缺口,解决：斜角连接（miter join）、圆连接（round join）、斜切连接（bevel join）,方刷子：,特点：方刷子绘制的线条（斜线）比用线刷子所绘制的线条要粗一些方刷子绘制的斜线与水平（或垂直）线不一样粗方刷子绘制的线条自然地带有一个“方线帽”,其它线宽处理方式 区域填充 改变刷子形状：,曲线的线型和线宽 线型：可采用象素模板的方法,线宽：线刷子 方刷子要显示一致的曲线宽度可通过旋转刷子方向以使其在沿曲线移动时与斜率方向一致，圆弧刷子采用填充的办法。,字符的属性,字体、字形、字号、字间距
28、、行间距等等。一般字体确定风格，字形确定外观，字号确定尺寸。字符的常用属性,字符串的属性 文本高度、文本宽度（扩展/压缩因子）、字符方向、文本路径方向、对齐方式（左对齐，中心对齐，或右对齐，指定起始、终止点）、文本字体、字符的颜色属性等。反绘（从右到左）、倒绘（旋转180）、写方式（替换或与方式）等。,区域填充属性,区域填充属性选择包括颜色、图案和透明度。,根据图案和透明度属性来填充平面区域的基本思想是：首先用模板定义各种图案。然后，修改填充的扫描转换算法：在确定了区域内一象素之后，不是马上往该象素填色而是先查询模板位图的对应位置。若是以透明方式填充图案，则当模板位图的对应位置为1时，用前景色
29、写象素，否则，不改变该象素的值。若是以不透明方式填充图案，则视模板位图对应位置为1或0来决定是用前景色还是背景色去写象素。,确定区域与模板之间的位置关系（对齐方式）：一种对齐方式是把有模板原点与填充区域边界或内部的某点对齐一种对齐方式是把模板原点与填充区域外部的某点对齐,5.7 反走样,用离散量表示连续量引起的失真，就叫做走样（Liasing）。,走样现象：一是光栅图形产生的阶梯形一是图形中包含相对微小的物体时，这些物体在静态图形中容易被丢弃或忽略，在动画序列中时隐时现，产生闪烁,用于减少或消除这种效果的技术，称反走样（antialiasing）。一种简单方法：提高设备分辨率,过取样（supe
30、rsampling），或后滤波区域取样（area sampling），或前滤波,过取样,简单过取样,克服走样的原理？颜色过度,重叠过取样,基于加权模板的过取样,强调中心点的影响，按距离加权,简单的区域取样,象素点的亮度设置成与线条重合的面积成正比,如何计算直线段与象素相交区域的面积？,1/2DD/k,可用一种求相交区域的近似面积的离散计算方法：(1)将屏幕象素分割成n个更小的子象素，(2)计算中心落在直线段内的子象素的个数m，(3)m/n为线段与象素相交区域面积的近似值。特点：直线段对一个象素亮度的贡献与两者重叠区域的面积成正比 相同面积的重叠区域对象素的贡献相同,加权区域取样,加权区域取样原理假想一个连续的加权曲面（或过滤函数）覆盖象素。当直线条经过该象素时，该象素的灰度值是在二者重叠区域上对滤波器（过滤函数）进行积分的积分值。,特点：接近理想直线的象素将被分配更多的灰度值；相邻两个象素的滤波器相交，有利于缩小直线条上相邻象素的灰度差。,
