维基本图形元素生成算法.ppt

第三章 二维基本图形元素生成算法,基本概念,所谓图元的生成，是指完成图元的参数表示形式（由图形软件包的使用者指定）到点阵表示形式（光栅显示系统刷新时所需的表示形式）的转换。通常也称扫描转换图元,2,课程内容,3.1 简单的二维图形显示流程 3.2 直线段的扫描转换 3.3 圆弧的扫描转换 3.4 易画曲线的正负法 3.5 线画图元的属性控制,3,3.1 简单的二维图形显示流程,图3-1-1 二维图形显示流程,裁剪和扫描,图形显示前需要进行扫描转换+裁剪，这一过程有三种方法：裁剪-扫描转换：最常用，节约计算时间。扫描转换-裁剪：算法简单；扫描转换到画布-位块拷贝：算法简单，但耗时耗内存。常用于字符显示。,5,3.2 直线段的扫描转换,目标：求与直线段充分接近的像素集 两点假设1.直线段的宽度为12.直线段的斜率:,像素间均匀网格整型坐标系,图3-2-1,6,描绘线条图形的要求直线段要显得笔直线段端点位置要准确线段的亮度要均匀转换算法速度要快,7,3.2.1 DDA（digital differential analyzer）算法,条件：待扫描转换的直线段：斜率：，其中直线方程：,8,3.2.1 DDA算法,直接求交算法：划分区间x,x1:计算纵坐标：取整：复杂度：乘法+加法+取整,图3-2-2,9,3.2.1 DDA算法,DDA算法（增量算法）复杂度：加法+取整算法,图3-2-3,10,3.2.1 DDA算法,DDA算法程序：void LineDDA(int x0,int y0,int x1,int y1,int color)/*假定x0 x1,-1=k=1*/int x,y；float dx,dy,k;dx=float(x1-x0);dy=float(y1-y0);k=dy/dx;y=y0;for(x=x0;x=x1,x+)Putpixel(x,int(y+0.5),color);y+=k;,11,3.2.1 DDA算法,举例：用DDA方法扫描转换连接两点P0(0,0)和P1(5,2)的直线段x int(y+0.5)y+0.50 0 01 0 0.4+0.52 1 0.8+0.53 1 1.2+0.54 2 1.6+0.5,图3-2-4,12,3.2.1 DDA算法,特点1 注意上述分析的算法仅适用于|k|1的情形。在这种情况下，x每增加1,y最多增加1。当|k|1时，必须把x，y地位互换，y每增加1，x相应增加1/k。特点2 在这个算法中，y与k必须用浮点数表示，而且每一步都要对y进行四舍五入后取整。这使得它不利于硬件实现。,13,3.2.1 DDA算法,改进算法（增量DDA）优化点：增加斜率判断并改变循环参数,14,算法,DDA画线算法程序（改进）void LineDDA(int x0,int y0,int x1,int y1,int color)int x,y；float dx,dy,k,l,m;dx=float(x1-x0);dy=float(y1-y0);k=dy/dx;if(abs(k)x1怎么办？,15,3.2.2 画线中点算法,目标：消除DDA算法中的浮点运算（浮点数取整运算，不利于硬件实现；DDA算法，效率低）条件：同DDA算法斜 率：直线段的隐式方程（(x0,y0)(x1,y1)两端点）F(x,y)=ax+by+c=0 式中 a=y0-y1,b=x1-x0,c=x0y1-x1y0,16,基本原理：画直线段的过程中，当前象素点为(xp,yp)，一个象素点有两种可选择点p1(xp+1,yp)或p2(xp+1,yp+1)。若M=(xp+1,yp+0.5)为p1与p2之中点，Q为理想直线与x=xp+1垂线的交点。当M在Q的下方，则P2 应为下一个象素点；M在Q的上方，应取P1 为下一点。,图3-2-5,17,3.2.2 画线中点算法,3.2.2 画线中点算法,点与直线的关系：on:F(x,y)=0;up:F(x,y)0;down:F(x,y)0;,图3-2-6,直线的正负划分性,18,3.2.2 画线中点算法,欲判断中M在Q点的上方还是下方，只要把M代F(x,y)并 判断它的符号。构造判别式:d=F(M)=F(xp+1,yp+0.5)=a(xp+1)+b(yp+0.5)+c 当d0，M在Q点上方，取P1为下一个象素；当d=0，选P1或P2均可，约定取P1为下一个象素,19,问题：判断距直线最近的下一个象素点 构造判别式：d=F(M)=F(xp+1,yp+0.5)由d0，d0可判定下一个象素，,P,P2,P1,图3-2-7,20,3.2.2 画线中点算法,要判定再下一个象素，分两种情形考虑：1）若d0，取正右方象素P1，再下一个象素判定，由 d1=F(xp+2,yp+0.5)=a(xp+2)+b(yp+0.5)+c=d+a，d的增量 是a 2）若d0，取右上方象素P2，再下一个象素，由：d2=F(xp+2,yp+1.5)=d+a+b d的增量为a+b,P2,P,P1,图3-2-8,21,3.2.2 画线中点算法,d的初始值d0=F(x0+1,y0+0.5)=F(z0,y0)+a+0.5*b因(x0,y0)在直线上，F(x0,y0)=0,所以，d0=a+0.5*b d的增量都是整数，只有初始值包含小数，可以用2d代替d,2a改写成a+a。算法中只有整数变量，不含乘除法，可用硬件实现。,22,3.2.2 画线中点算法,中点算法程序 MidPointLine(x0,y0,x1,y1,color)int x0,y0,x1,y1,color;int a,b,d1,d2,x,y;a=y0-y1;b=x1 x0;d=2*a+b;d1=2*a;d2=2*(a+b);x=x0;y=y0;PutPixel(x,y,color);while(xx1)if(d0)x+;y+;d+=d2;else x+;d+=d1;PutPixel(x,y,color);,23,3.2.2 画线中点算法,举例 用中点画线方法扫描转换连接两点P0(0,0)和P1(5,2)的直线段:a=y0-y1=-2；b=x1-x0=5；d0=2*a+b=1；d1=2*a=-4；d2=2*(a+b)=6 x y d 0 0 1 1 0-3 d1 2 1 3 d2 3 1-1 d1 4 2 5 d2 5 2 1,图3-2-9,24,3.2.2 画线中点算法,3.2.3 画线Bresenham算法,Bresenham算法是计算机图形学领域使用最广泛的直线扫描转换算法。该方法类似于中点法，由误差项符号决定下一个象素取右边点还是右上点。算法原理如下：过各行各列象素中心构造一组虚拟网格线。按直线从起点到终点的顺序计算直线与各垂直网格线的交点，然后确定该列象素中与此交点最近的象素。该算法的巧妙之处在于采用增量计算，使得对于每一列，只要检查一个误差项的符号，就可以确定该列的所求象素。,25,如下图所示。设直线方程为，其中k=dy/dx。假设x列的象素已经确定为xi，其行坐标为yi。那么下一个象素的列坐标为xi1，而行坐标要么不变为yi，要么递增1为yi1。,图3-2-10,26,3.2.3 画线Bresenham算法,是否增1取决于如图所示误差项d的值。因为直线的起始点在象素中心，所以误差项d的初值d00。x下标每增加1，d的值相应递增直线的斜率值k，即ddk。一旦d1，就把它减去1，这样保证d在0和1之间。当d0.5时，直线与xi1列垂直网格交点最接近于当前象素(xi,yi)的右上方象素(xi 1,yi 1)；而当d0.5时，更接近于右方象素(xi 1,yi)。,图3-2-10,27,3.2.3 画线Bresenham算法,为方便计算，令ed0.5，e的初值为0.5，增量为k。当e0时，取当前象素(xi,yi)的右上方象素(xi1,yi1)；而当e0时，更接近于右方象素(xi1,yi)。,28,3.2.3 画线Bresenham算法,Bresenham画线算法程序 void Bresenhamline(int x0,int y0,int x1,int y1,int color)int x,y,dx,dy;float k,e;dx=x1-x0;dy=y1-y0;k=dy/dx;e=-0.5;x=x0;y=y0;for(i=0;i=0)y+,e=e-1;,29,3.2.3 画线Bresenham算法,举例：用Bresenham方法扫描转换连接两点P0(0,0)和P1(5,2)的直线段。x y e0 0-0.51 0-0.1 0.3-12 1-0.73 1-0.3 0.1-14 2-0.95 2-0.5,图3-2-11,30,3.2.3 画线Bresenham算法,上述bresenham算法在计算直线斜率与误差项时用到小数与除法。可以改用整数以避免除法。由于算法中只用到误差项的符号，因此可作如下替换：e=e*2dx改进的Bresenham画线算法程序：void InterBresenhamline(int x0,int y0,int x1,int y1,int color)dx=x1-x0;dy=y1-y0;e=-dx;x=x0;y=y0;for(i=0;i=0)y+;e=e-2*dx;,31,3.2.3 画线Bresenham算法,3.3圆弧的扫描转换,处理对象：圆心在原点的圆弧圆的八对称性,图3-3-1,32,两种直接离散方法：离散点:离散角度:缺点：开根，三角函数运算，计算量大，不可取。,33,3.3圆弧的扫描转换,角度DDA法转换圆弧,x=x0+Rcos y=y0+Rsindx=-Rsin ddy=Rcos dxn+1=xn+dxyn+1=yn+dyxn+1=xn+dx=xn-Rsin d=xn-(yn-y0)dyn+1=yn+dy=yn+Rcos d=yn+(xn-x0)d,显然，确定x,y的初值及d值后，即可以增量方式获得圆周上的坐标，然后取整可得象素坐标。但要采用浮点运算、乘法运算、取整运算,34,圆弧的正负划分性,圆弧外的点：F(x，y)0圆弧内的点：F(x，y)0,3.3.1 角度DDA法转换圆弧,图3-3-2,35,生成圆弧的中点算法考虑对象：第二个八分圆，第一象限的八分之一圆弧,3.3.1 角度DDA法转换圆弧,图3-3-3,36,问题：与直线情形类似圆弧的隐函数：F(x,y)=x2+y2-R2=0 切线斜率m in-1,0中点 M=(xp+1,yp-0.5),当F(M)0时，M在圆内，说明P1距离圆弧更近，取P1；当F(M)0时，P取P2；,3.3.1 角度DDA法转换圆弧,37,构造判别式 d=F(M)=F(xp+1,yp-0.5)=(xp+1)2+(yp-0.5)2-R2 1）若d0，取P1，再下一个象素的判别式为：d1=F(xp+2,yp-0.5)=d+2xp+3，沿正右方向，d的增量为2xp+3；2）若d0，取P2，再下一个象素的判别式为：d2=F(xp+2,yp-1.5)=d+(2xp+3)+(-2yp+2)沿右下方向，d的增量为2(xp-yp)+5d的初始值(在第一个象素(0,R)处),d0=F(1,R-0.5)=1.25-R，算法中有浮点数，用e=d-0.25代替,角度DDA法转换圆弧,38,所以：初始化运算d0=1.25 R 对应于 e 0=1-R判别式 d 0 对应于 e-0.25 又因为：e的初值e0为整数，运算过程中的分量也为整数，故e始终为整数所以：e-0.25 等价于 e 0程序如下（完全用整数实现）：,MidpointCircle(r,color)Int r,color;int x,y,d;x=0;y=r;d=1-r;putpixcel(x,y,color);,while(x y)if(d 0)d+=2*x+3;x+;else d+=2*(x-y)+5;x+;y-;putpixcel(x,y,color);,39,3.3.2 Bresenham画圆算法,现在从A点开始向右下方逐点来寻找弧AB要用的点。如图中点Pi-1是已选中的一个表示圆弧上的点，根据弧AB的走向，下一个点应该从Hi或者Li中选择。显然应选离AB最近的点作为显示弧AB的点。假设圆的半径为R，显然，当xHi2+yHi2-R2 R2-(xLi2+yLi2)时，应该取Li。否则取Hi。令di=xHi2+yHi2+xli2+yli2-2R2 显然，当di 0 时应该取Li。否则取Hi。,图3-3-4,40,剩下的问题是如何快速的计算di。设图中Pi-1的坐标为(xi-1,yi-1)，则Hi和Li的坐标为(xi,yi-1)和(xi,yi-1-1)di=xi2+yi-12+xi2+(yi-1-1)2-2R2=2xi2+2yi-12-2yi-1+1-2R2,3.3.2 Bresenham画圆算法,di+1=(xi+1)2+yi2+(xi+1)2+(yi-1)2-2R2=2xi2+4xi+2yi2-2yi-2R2+3,41,当di取Hi-yi=yi-1，则 di+1=di+4xi-1+6当di 0时-取Li-yi=yi-1-1，则 di+1=di+4(xi-1-yi-1)+10,3.3.2 Bresenham画圆算法,易知 x0=0，y0=R,x1=x0+1 因此 d0+1=12+y02+12+(y0-1)2-2R2=3-2y0=3-2R,42,1、求误差初值，p1=3-2R;i=1；画点(0,r)；2、求下一个光栅位置：x(i+1)=x(i)+1；如果pi0则y(i+1)=y(i)，否则y(i+1)=y(i)-1；3、画点（x(i+1),y(i+1)）;4、计算下一个误差：if p(i)0 则p(i+1)=p(i)+4x(i)+6；否则 p(i+1)=p(i)+4(x(i)-y(i)+10；5、i=i+1;if x=y 则end；否则返2。,3.3.2 Bresenham画圆算法,43,3.3.2 Bresenham画圆算法,44,3.3.3 椭圆的扫描转换,F(x,y)=b2x2+a2y2-a2b=0椭圆的对称2性，只考虑第一象限椭圆弧生成，分上下两部分，以切线斜率为-1的点作为分界点。椭圆上一点处的法向：N(x,y)=F(xi)+F(yj)=2b2 xi+2a2 yj,图3-3-5,45,M2,在当前中点处，法向量(2b2(xp+1)，2a2(yp-0.5)的y分量比x分量大,即：b2(xp+1)a2(yp-0.5),而在下一中点，不等式改变方向，则说明椭圆弧从上部分转入下部分。,3.3.3 椭圆的扫描转换,46,椭圆的中点算法 与圆弧中点算法类似：确定一个象素后，接着在两个候选象素的中点计算一个判别式的值，由判别式的符号确定更近的点。先讨论椭圆弧的上部分(xp,yp)中点(xp+1,yp-0.5)d1=F(xp+1,yp-0.5)=b2(xp+1)2+a2(yp-0.5)2-a2b2,3.3.3 椭圆的扫描转换,47,根据d1的符号来决定下一像素是取正右方的那个，还是右下方的那个。若d10，中点在椭圆内，取正右方象素，判别式更新为：d1=F(xp+2,yp-0.5)=d1+b2(2xp+3)d1的增量为b2(2xp+3)当d1 0，中点在椭圆外，取右下方象素，更新判别式：d1=F(xp+2,yp-1.5)=d1+b2(2xp+3)+a2(-2yp+2)d1的增量为b2(2xp+3)+a2(-2yp+2),3.3.3 椭圆的扫描转换,48,d1的初始条件：椭圆弧起点为(0，b)，第一个中点为(1,b-0.5)初始判别式：d10=F(1,b-0.5)=b*b+a*a(-b+0.25)转入下一部分，下一象素可能是一正下方或右下方，此时判别式要初始化。d2=F(Xp+0.5,Yp-1)=b2(Xp+0.5)2+a2(Yp-1)2-a2b2 若d2=0,则d2=F(Xp+0.5,Yp-2)=d2+a2(-2Yp+3)下半部分弧的终止条件为 y=0,椭圆的扫描转换,49,程序：MidpointEllipe(a,b,color)int a,b,color;int x,y;float d1,d2;x=0;y=b;d1=b*b+a*a*(-b+0.25);putpixel(x,y,color);while(b*b*(x+1)a*a*(y-0.5)if(d10)d1+=b*b*(2*x+3);x+;else d1+=(b*b*(2*x+3)+a*a*(-2*y+2)x+;y-;putpixel(x,y,color);/上部分,50,3.3.3 椭圆的扫描转换,d2=sqr(b*(x+0.5)+sqr(a*(y-1)sqr(a*b);while(y 0)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,color);,51,3.3.3 椭圆的扫描转换,3.3.4 生成圆弧的多边形逼近法,用正多边形近似代替圆,显示多边形的边可用扫描转换直线段的中点算法来实现。,圆的正内接多边形迫近法圆的等面积正多边形迫近法,52,圆的正内接多边形迫近法原理计算多边形各顶点的递推公式 Xi+1cos a-sin a Xi=Yi+1sin a cosa Yi因为:a是常数，sin a，cosa只在开始时计算一次所以，一个顶点只需4次乘法，共4n次乘法，外加直线段的中点算法的计算量。,生成圆弧的多边形逼近法,图3-3-7,53,图3-3-8,问题：给定最大逼近误差（最大 距离）DELTA，如何确定多边形的边数n或a？,另外，用矢量运算可以简化计算，推出求顶点的逆推公式(p60),d=R Rcos(a/2)=(R DELTA)/R a=2 arc cos(R DELTA)/R,amax=2 arccos(R DELTA)/Rn=360/a,54,3.3.4 生成圆弧的多边形逼近法,图3-3-10,圆的等面积正多边形迫近法,步骤：求多边形径长，从而求所有顶点生标值由逼近误差值，确定边所对应的圆心角,图3-3-9,55,3.3.4 生成圆弧的多边形逼近法,扇形ODCE的面积=三角形OPiPi+1的面积(P60页),图3-3-10,56,3.3.4 生成圆弧的多边形逼近法,3.4 易画曲线的正负法,正负法简介基本原理假定初始点P0G0，沿某方向(假定为X轴）前进X时，到达G+或G-(假定为G-)中的P1,在沿另外一方向(Y轴)前进Y,到达P2。若P2G+，则改变前进方向，否则继续向G+前进。易画曲线F(x,y)具有正负划分性F(x,y)二阶连续曲线上各点曲率半径足够大,图3-4-1,57,初始定向确定 的符号,3.4 易画曲线的正负法,58,前进规则取判别式,3.4 易画曲线的正负法,59,正负法生成圆弧考虑第一像限圆弧段圆弧是易画曲线取初始点P0(x0,y0)=(0,R)初始定向为：D=4,X=1,y=-1则P1为(x0+1,y0)=(1,R);又因为 D(Pi)=F(Pi)F(P1)=F(Pi)F(1,R)所以由前进规则得前进点递推公式1）当D(Pi)=0时，xi+1=xi,yi+1=yi-1;2）当D(Pi)0时，xi+1=xi+1,yi+1=yi；判别式D(Pi+1)的递推公式见：P63判别式的初值D(P1)=F(P1)=F(1,R)=1,3.4 易画曲线的正负法,图3-4-2,60,3.5 线画图元的属性控制（1/5）,线宽控制像素复制方法优点：实现简单缺点：线段两端要么为水平的，要么是竖直的折线顶点处有缺口,图3-5-1,图3-5-2,61,图元的宽度不均匀产生宽度为偶数像素的图元效果不好,图3-5-3,3.5 线画图元的属性控制（2/5）,62,移动刷子,3.5 线画图元的属性控制（3/5）,图3-5-4,63,利用填充图元优点：生成的图形质量高缺点计算量大有些图形的等距线难以获得,图3-5-4,3.5 线画图元的属性控制（4/5）,64,线型控制,3.5 线画图元的属性控制（5/5）,图3-5-5,65,