《维线画图元及属性》PPT课件

1、第3章二维线画图元及属性,在图形系统的输出设备上生成的画面，都是由各种基本几何元素图形输出基元（简称为输出图元）构成的。画面上最简单的输出图元是点和直线，其他还有多边形、曲线图形以及字符串等。本章介绍一些常用直线段、圆弧的扫描转换算法。,第3章二维线画图元及属性,3.1直线的扫描转换及算法3.2圆和椭圆的扫描转换算法3.3其他输出图元的生成3.4输出图元的属性3.5字符的生成,3.1直线的扫描转换及算法,扫描转换：从图形定义的物空间到进行显示处理的图像空间的转换线画图元的扫描转换：计算出落在线段上或充分靠近它的一串像素，并以此像素集近似替代连续直线段在屏幕上显示的过程。,由像素表示的直线段为均

2、匀填充的实心原点,像素：中心为网格点的圆点，距离均匀，相互不重叠,3.1直线的扫描转换及算法,一、点的生成,点是图形中最基本的图素，直线、曲线以及其它的图元都是点的集合。在几何学中，一个点既没有大小，也没有维数，点只是表示坐标系统中的一个位置。在计算机图形学中，点是用数值坐标表示的。在直角坐标系中点由(x,y)两个数值组成的坐标表示，在三维坐标系中点由(x,y,z)三个数值组成的坐标表示。,在输出设备上输出一个点，首先需要计算出该点的坐标位置（最逼近该点的像素位置），其次需要把应用程序中的坐标信息转换成所用输出设备的相应指令。,3.1直线的扫描转换及算法,二、直线的扫描转换,在数学上，理想的点

3、和直线都是没有宽度的。但是，由于每个像素对应于图形设备上的一个矩形区域，当我们在光栅图形设备上显示一个点时，实际上它是有用一个发光的矩形区域来表示的；当在光栅图形设备上显示一条直线时，我们只能在显示器所给定的有限个像素组成的矩阵中，按扫描线顺序，依次确定最佳逼近于该直线的一组像素，并且对这些像素进行写操作。这个过程称为直线的扫描转换。,3.1直线的扫描转换及算法,二、直线的扫描转换,对于水平线、垂直线和45斜线，选择哪些像素是显而易见的，但是对于其它的直线，确定用哪些像素来表示它就不那麽简单了。本节我们介绍用于直线扫描转换的常用算法：数值微分法Bresenham画线算法中点画线法,3.1直线的

4、扫描转换及算法,象素,线,圆,GeometricGraphicsi|Pi-nearestpixel基本图形的生成算法任务之一就是找出所有的i。,3.1直线的扫描转换及算法,在介绍画线算法之前，我们先讨论画直线的基本要求：直线必须有精确的起点和终点，外观要直，线宽应当均匀一致、且与直线的长度和方向无关，算法速度要快。,3.1直线的扫描转换及算法,直线方程：ykxbk是直线的斜率，b是y方向的截距，若直线的两端点为（x0，y0）及（x1，y1），则k（y1y0）/（x1x0）by1kx1对于一直线，在x方向取间隔dx，则可计算y方向的间隔dydykdx,该方法涉及到浮点数的乘除法、加减法以及取整运

5、算，因此，效率非常低,3.1.1数值微分法,数值微分法即DDA（DigitalDifferentialAnalyzer）基本思想:先对一个方向的坐标取单位步长的变化,然后计算另一方向坐标相应的变化值。假定直线的起点、终点分别为：（X0,Y0),(X1,Y1)，且都为整数。则直线方程和斜率k为：=k*X+Bk=(Y1-Y0)/(X1-X0),3.1.1数值微分法,1.|k|1,则应取y坐标的增量为y=，可得如下X的增量方程：Xi+1=Xi+1/k3.开始端点在右端点,中止端点在左端点,则x1Yi+1=Yiky1Xi+1=Xi1/k,3.1.1数值微分法,算法过程：DxX1X0;DyY1Y0此两参

6、数的绝对值哪一个大，哪一个就作为步长参数（n），此参数将作为沿直线所画出点的数目(1)当|Dx|=|Dy|（即|k|X1，则x1，y=k(2)当|Dx|1）时若X0X1，则y1，x=1/k,3.1.1数值微分法,例：画直线段P0(0,0)-P1(5,2)Dx=x2-x1=5,Dy=y2-y1=2DxDyx=1y=2/5=0.4所以x方向上计长，走步数为5取初值x0=0.5,y0=0.5（保证四舍五入）C=1x1=x0+1=1.5，y1=y0+0.4=0.9取点(1，0)C=2x2=x1+1=2.5，y2=y1+0.4=1.3取点(2，1)C=3x3=x2+1=3.5，y3=y2+0.4=1.7

7、取点(3，1)C=4x4=x3+1=4.5，y4=y3+0.4=2.1取点(4，2)C=5x5=x4+1=5.5，y5=y4+0.4=2.5取点(5，2),3.1.1数值微分法,程序实现：,3.1.1数值微分法,DDA算法的优点：使用DDA算法，每生成一条直线做两次除法，每画线中一点做两次加法。因此，用DDA法生成直线的速度是相当快的。DDA算法的缺点：在此算法中，x，y、k必须是float，且每一步都必须对x或y进行舍入取整，不利于硬件实现。,3.1.2Bresenham画线算法,Bresenham算法是计算机图形学领域使用最广泛的直线扫描转换算法。该方法最初是为数字绘图仪设计的，后来被广泛

8、地应用于光栅图形显示和数控（NC）加工。该算法构思巧妙，使得每次只需检测误差项的符号就能决定直线上的下一个像素的位置。,3.1.2Bresenham画线算法,算法原理：过各行、各列像素中心构造一组虚拟网格线，按直线从起点到终点的顺序计算直线与各垂直网格线的交点，然后确定该列像素中与此交点最近的像素.如图所示，先假设直线的斜率在01之间。设Pi-1是已选定的离直线最近的象素，现在要决定下一个象素是Ti还是Si。由图上可直观看出：若st，则应选Ti；即可以通过s-t的正负来判断选Si还是Ti,3.1.2Bresenham画线算法,设直线从（x1，y1）到（x2，y2），经变换后可表示为从（0，0）

9、到（dx，dy），其中：dxx2x1，dyy2y1直线方程：ydy/dx*x设Pi1（r，q），则Si（r1，q），Ti（r1，q1）s=dy/dx*(r+1)-qt=(q+1)-dy/dx*(r+1)则：s-t=2*dy/dx*(r+1)-2q-1所以：dx(s-t)=2(r*dy-q*dx)+2dy-dx令di=dx(s-t)，将r=xi-1，q=yi-1带入上式，,3.1.2Bresenham画线算法,di=2xi-1*dy-2yi-1*dx+2dy-dx以i1代替i（将每一下标加1）：di+1=2xi*dy-2yi*dx+2dy-dx从di+1减去didi+1-di=2dy(xi-xi

10、-1)-2dx(yi-yi-1)因为xi-xi-11di+1=di+2dy-2dx(yi-yi-1)如果di0；则选Ti，yi=yi-1+1，且di+1=di+2（dy-dx)如果di0；则选Si，yi=yi-1，且di+1=di+2dy初值为d1=2dy-dx（x0，y0）（0，0）,3.1.2Bresenham画线算法,当斜率大于1时，可以将x，y交换，即以y方向作为计长方向，每次变化1个单位步长或1个象素单位。对于任意走向的直线，则可以根据其端点的位置来控制其增量的正负。该方法所需的计算量很小，它只包括加法、减法和左移操作。这也是本算法得到广泛应用的原因。,dx=x2-x1=5;dy=y

11、2-y1=2;d12dydx1d10，则选Ti，y2y11d3d2+2（dydx）3以此类推,3.1.2Bresenham画线算法,举例：用Bresenham方法画直线段P1(0,0)P2(5,2),3.1.2Bresenham画线算法,程序如下：BresenhamLine(x0,y0,x1,y1,color)intx0,y0,x1,y1,color;intx,y,dx,dy,e;dx=x1-x0;dy=y1-y0;x=0;y=0;e=2*x*dy-2*y*dx+2*dy-dx;for(i=0;i=0)y+;/y=y+1;x+;d+=2*dy-2*dx;elsex+;d+=2*dy;,3.1.

12、3中点画线法,为了讨论方便，假定直线斜率0取P2。M在Q的上方-P1离直线更近更近-取P1M与Q重合，P1、P2任取一点。问题：如何判断M与Q点的关系？,3.1.3中点画线法,假设直线的起点和终点分别为（x0，y0）和（x1，y1），则方程为：ax+by+c=0其中a=y0-y1,b=x1-x0,c=x0y1-x1y0由常识知：欲判断M点是在Q点上方还是在Q点下方，只需把M代入F(x,y),并检查它的符号。,3.1.3中点画线法,构造判别式：M(xi+1,yi+0.5)d=F(M)=F(xi+1,yi+0.5)=a(xi+1)+b(yi+0.5)+c当d0，M在直线(Q点)上方，取右方P1；当

13、d=0，选P1或P2均可，约定取P1；能否采用增量算法呢？,3.1.3中点画线法,若d0-M在直线上方-取P1;此时再下一个象素的判别式为d1=F(xi+2,yi+0.5)=a(xi+2)+b(yi+0.5)+c=a(xi+1)+b(yi+0.5)+c+a=d+a；增量为a,若dM在直线下方-取P2;此时再下一个象素的判别式为d2=F(xi+2,yi+1.5)=a(xi+2)+b(yi+1.5)+c=a(xi+1)+b(yi+0.5)+c+a+b=d+a+b；增量为abd的初始值（第一个象素应取左端点(x0,y0)）d0=F(x0+1,y0+0.5)=a(xp+1)+b(y0+0.5)+c=a

14、x0+by0+c+a+0.5b=F(x0,y0)+a+0.5b=a+0.5b（2a+b）,3.1.3中点画线法,举例：用中点画线法画直线段P1(0,0)P2(5,2),3.1.2中点画线法,MidpointLine(X0,Y0,X1,Y1,Color)intX0,Y0,X1,Y1,Color;inta,b,d1,d2,d,x,y;a=Y0-Y1;b=X1-X0;d=a+a+b;d1=a+a;d2=a+b+a+b;x=X0;y=Y0;drawpixle(x,y,Color);while(xX1)if(d=0,则选择D，且yi1yi1di=0,代入上式，得di0，应选D,如何简化di的计算？,3.

15、2.2Bresenham画圆法,di=HD=(xi+1)2+yi2-R2(xi+1)2+(yi-1)2-R2用i1代i，得di1=(xi1+1)2+yi12-R2(xi1+1)2+(yi1-1)2-R2如果di=0，选D，xi1xi1，yi1yi-1，得di1=di4(xi-yi)10对于i0，x00，y0R，则初值d032R这个算法中计算量很小，因此，算法效率很高,3.2.2Bresenham画圆法,画圆算法,基本思想：与中点画线法基本思想相类似。对于第1a象限内从(0,R)到（R/2,R/2）顺时针确定最佳逼近于圆弧的像素序列，假定P点像素位置已经确定P=(xi,yi)，则下一个像素只能是

16、NE=(xi+1,yi)或E=(xi+1,yi-1)。设M为中点，即M=(xi+1,yi-0.5)；Q为交点。显然，当Q在M的上方，应取NE；当Q在M的下方，应取E；当M与Q重合时，NE、E任取一点。以后依次类推。,3.2.3中点画圆法,3.2.3中点画圆法,构造函数：F(x,y)=x2+y2-R2，圆上的点，F(x,y)=0；圆内的点，F(x,y)0由此得到判别式：di=F(M)=F(xi+1,yi-0.5)=(xi+1)2+(yi-0.5)2-R2（）当di0，M在Q点下方，取上方NE，即，且再下一像素的判别式为：di+1=F(xi+2,yi-0.5)=(xi+2)2+(yi-0.5)2-

17、R2=di+2xi+3（2）当d0，M在Q点上方，取下方E，再下一像素的判别式为：di+1=F(xi+2,yi-1.5)=(xi+2)2+(yi-1.5)2-R2=di+2(xi-yi)+5对于在第1a象限内，第一像素是(0,R)，判别式d的初值为d0=F(x0+1,y0-0.5)=12+(R-0.5)2-R2=1.25-R,3.2.3中点画圆法,中点画圆算法只用到整数的加法、减法和左移（乘2）运算，故效率高且适合硬件实现。,3.2.3中点画圆法,程序示例,3.2.4正负法画圆,基本思想：确保用于表示圆弧的点均在圆弧附近，且使逼近于圆弧的像素序列在圆弧内外交替出现，即F(xi,yi)时正时负，

18、故称正负法。,3.2.4正负法画圆,设圆的方程为F(x,y)=x2+y2-R2=0;点(x,y)在圆上，有F(x,y)0点(x,y)在圆内，有F(x,y)0假设求得Pi的坐标为(xi,yi)；当Pi在圆内时，F(xi,yi)0，下一像素取下方、向圆内；即求得Pi点后选择下一个象素点Pi+1的规则为：当F(xi,yi)0时，取xi+1=xi+1，yi+1=yi;当F(xi,yi)0时，取xi+1=xi，yi+1=yi-1;这样用于表示圆弧的点均在圆弧附近，且使F(xi,yi)时正时负，故称正负法。,3.2.4正负法画圆,3.2.5椭圆的扫描转换,可以把画圆算法扩展到既可画圆又可画椭圆。椭圆的标准

19、方程为：,可以修改前面讲过的Bresenham画圆算法，使它也可生成椭圆。要画椭圆，只要在计算di时用椭圆方程代替圆的方程。画椭圆算法与画圆算法的唯一差别是参数d的形式不同。,3.3其他输出图元的生成,常用的其他曲线：正弦函数曲线、指数函数曲线、多项式函数曲线、概率分布曲线、样条函数曲线。如果函数曲线可以用yf（x）形式来表示，则可指定x间隔计算出相应的y值，由各x，y值画出此曲线由若干离散数据点所定义的曲线，可用其他方法绘出，（1）先画出各个数据点，然后用直线连接这些点。（2）用曲线拟合技术平滑地逼近数据点所定义的曲线,3.4输出图元的属性,在图元输出之前，可为其指定不同的属性，属性定义了图

20、元在输出设备上的外部特征。例如，可用属性为输出图元定义线型、线宽、色彩等。本节将讨论如何在扫描转换的同时控制输出图元的线宽和线型。,3.4.1线宽控制,1.复制像素法（1）基本思想：在扫描转换图元时，同时显示n个像素。这样就将原来绘制单个像素的语句改写成以该像素为中心绘制水平或垂直排列的多个像素，因此，可产生具有一定线宽的线条。（2）复制方法斜率绝对值小于1，垂直方向上像素复制斜率绝对值大于1，水平方向上像素复制,斜率绝对值1,3.4.1线宽控制,（3）特点算法简单、执行效率高，适合于比较小的线宽。当线宽较大时，该算法的缺点是：a）线段的两端只有水平或垂直两种情况b）曲线要根据当前绘制像素的斜

21、率来决定是在水平方向还是垂直方向复制像素c）在折线连接处由水平复制转为垂直复制时，会产生缺口,复制像素法产生的缺口,用复制像素法绘制圆弧,3.4.1线宽控制,2.移动画笔法基本思想：将原来绘制单个像素的语句改写成以该像素为中心绘制画笔位图的语句。也就是将设定宽度为k的画笔的中心沿线段移动，即可产生具有线宽k的线条。,端点是方的,斜率接近1时，宽度最大,3.4.1线宽控制,3.区域填充法基本思想：根据线条的宽度，计算出线条的外轮廓，然后调用填充图元的生成函数将其填充，产生具有一定线宽的线条。,用区域填充法绘制圆弧,3.4.2线型控制,在图形系统中经常使用具有不同线型的线条来表示不同的含义，线型属性主要包括实线、虚线、点划线。在显示虚线时，把画线算法修改为沿一直线输出带有间隙的短实线点划线则是每画一短实线加入一点其他线型可通过短划线的长短不同及间隙不同来重新组合