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

《维基本图形元素生成算法.ppt》由会员分享，可在线阅读，更多相关《维基本图形元素生成算法.ppt（65页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第三章二维基本图形元素生成算法1 基本概念基本概念n所谓图元的生成，是指完成图元的参数表示形式（由图形软件包的使用者指定）到点阵表示形式（光栅显示系统刷新时所需的表示形式）的转换。通常也称扫描转换图元2课课程内容程内容 3.1 简单简单的二的二维图维图形形显显示流程示流程 3.2 直直线线段的段的扫扫描描转换转换 3.3 圆圆弧的弧的扫扫描描转换转换 3.4 易画曲易画曲线线的正的正负负法法 3.5 线线画画图图元的属性控制元的属性控制33.1 简单简单的二的二维图维图形形显显示流程示流程裁剪和扫描显示图元图3-1-1二维图形显示流程裁剪和裁剪和扫扫描描图形显示前需要进行扫描转换+裁剪，这一过

2、程有三种方法：裁剪-扫描转换：最常用，节约计算时间。扫描转换-裁剪：算法简单；扫描转换到画布-位块拷贝：算法简单，但耗时耗内存。常用于字符显示。53.2 直直线线段的段的扫扫描描转换转换n 目目标标：求与直：求与直线线段充分接近的像素集段充分接近的像素集n 两点假两点假设设1.直线段的宽度为12.直线段的斜率:像素间均匀网格整型坐标系图3-2-16n 描描绘线绘线条条图图形的要求形的要求q直线段要显得笔直q线段端点位置要准确q线段的亮度要均匀q转换算法速度要快73.2.1 DDA（digitaldifferentialanalyzer）算法算法q条件：条件：n待待扫扫描描转换转换的直的直线线段

3、：段：n斜率：斜率：，其中，其中n直直线线方程：方程：83.2.1 DDA算法算法q直接求交算法：直接求交算法：n划分区划分区间间x,x1:n计计算算纵纵坐坐标标：n取整：取整：n复复杂杂度：乘法度：乘法+加法加法+取整取整图3-2-293.2.1 DDA算法算法qDDA算法（增量算法）算法（增量算法）n复复杂杂度：加法度：加法+取整取整n算法算法图3-2-3103.2.1 DDA算法算法nDDA算法程序：voidLineDDA(intx0,inty0,intx1,inty1,intcolor)/*假定x0 x1,-1=k=1*/intx,y；floatdx,dy,k;dx=float(x1-

4、x0);dy=float(y1-y0);k=dy/dx;y=y0;for(x=x0;x1时，必须把x，y地位互换，y每增加1，x相应增加1/k。n特点2在这个算法中，y与k必须用浮点数表示，而且每一步都要对y进行四舍五入后取整。这使得它不利于硬件实现。133.2.1 DDA算法算法改进算法（增量DDA）n优化点：增加斜率判断并改变循环参数14算法算法nDDA画线算法程序（改进）voidLineDDA(intx0,inty0,intx1,inty1,intcolor)intx,y；floatdx,dy,k,l,m;dx=float(x1-x0);dy=float(y1-y0);k=dy/dx;i

5、f(abs(k)1)for(x=x0;x=x1,x+)Putpixel(x,int(y+0.5),color);y+=k;elsefor(y=y0;yx1怎么办？153.2.2 画画线线中点算法中点算法q目目标标：消除：消除DDA算法中的浮点运算算法中的浮点运算（浮点数取整运算，不利于硬件实现；DDA算法，效率低）q条件：条件：n同同DDA算法算法n斜斜 率：率：q直直线线段的段的隐隐式方程式方程（(x0,y0)(x1,y1)两端点）F(x,y)=ax+by+c=0式中a=y0-y1,b=x1-x0,c=x0y1-x1y016q基本原理基本原理：画直线段的过程中，当前象素点为(xp,yp)，一

6、个象素点有两种可选择点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-5173.2.2 画画线线中点算法中点算法3.2.2 画画线线中点算法中点算法点与直线的关系：on:F(x,y)=0;up:F(x,y)0;down:F(x,y)0;图3-2-6q直直线线的正的正负负划分性划分性183.2.2 画画线线中点算法中点算法欲判断中M在Q点的上方还是下方，只要把M代F(x,y)并判断它的符号。构造判别式:d=F(M)=F(x

7、p+1,yp+0.5)=a(xp+1)+b(yp+0.5)+c当d0，M在Q点上方，取P1为下一个象素；当d=0，选P1或P2均可，约定取P1为下一个象素19q问题：判断距直线最近的下一个象素点构造判别式：d=F(M)=F(xp+1,yp+0.5)由d0，d0可判定下一个象素，PP2P1图3-2-7203.2.2 画画线线中点算法中点算法q要判定再下一个象素，分两种情形考虑：1）若d0，取正右方象素P1，再下一个象素判定，由d1=F(xp+2,yp+0.5)=a(xp+2)+b(yp+0.5)+c=d+a，d的增量是a2）若d0，取右上方象素P2，再下一个象素，由：d2=F(xp+2,yp+1

8、.5)=d+a+bd的增量为a+bP2PP1图3-2-8213.2.2 画画线线中点算法中点算法qd的初始值qd0=F(x0+1,y0+0.5)=F(z0,y0)+a+0.5*bq因(x0,y0)在直线上，F(x0,y0)=0,所以，d0=a+0.5*bqd的增量都是整数，只有初始值包含小数，可以用2d代替d,2a改写成a+a。q算法中只有整数变量，不含乘除法，可用硬件实现。223.2.2 画画线线中点算法中点算法q中点算法程序MidPointLine(x0,y0,x1,y1,color)intx0,y0,x1,y1,color;inta,b,d1,d2,x,y;a=y0-y1;b=x1x0;

9、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;elsex+;d+=d1;PutPixel(x,y,color);233.2.2 画画线线中点算法中点算法q举例用中点画线方法扫描转换连接两点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)=6xyd00110-3d1213d231-1d1425d2521图3-2-9243.2.2 画画线线中点算法中点算法3.2.3 画画线线Bres

10、enham算法算法nBresenham算法是计算机图形学领域使用最广泛的直线扫描转换算法。该方法类似于中点法，由误差项符号决定下一个象素取右边点还是右上点。n算法原理如下：过各行各列象素中心构造一组虚拟网格线。按直线从起点到终点的顺序计算直线与各垂直网格线的交点，然后确定该列象素中与此交点最近的象素。该算法的巧妙之处在于采用增量计算，使得对于每一列，只要检查一个误差项的符号，就可以确定该列的所求象素。25如下图所示。设直线方程为，其中k=dy/dx。假设x列的象素已经确定为xi，其行坐标为yi。那么下一个象素的列坐标为xi1，而行坐标要么不变为yi，要么递增1为yi1。图3-2-10263.2

11、.3 画画线线Bresenham算法算法是否增1取决于如图所示误差项d的值。因为直线的起始点在象素中心，所以误差项d的初值d00。x下标每增加1，d的值相应递增直线的斜率值k，即ddk。一旦d1，就把它减去1，这样保证d在0和1之间。当d时，直线与xi1列垂直网格交点最接近于当前象素(xi,yi)的右上方象素(xi1,yi1)；而当d时，更接近于右方象素(xi1,yi)。图3-2-10273.2.3 画画线线Bresenham算法算法为方便计算，令ed，e的初值为，增量为k。当e0时，取当前象素(xi,yi)的右上方象素(xi1,yi1)；而当e0时，更接近于右方象素(xi1,yi)。283.

12、2.3 画画线线Bresenham算法算法nBresenham画线算法程序voidBresenhamline(intx0,inty0,intx1,inty1,intcolor)intx,y,dx,dy;floatk,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;293.2.3 画画线线Bresenham算法算法n举例：用Bresenham方法扫描转换连接两点P0(0,0)和P1(5,2)的直线段。xye00图3-2-11303.2.3 画画线线Bresenham算法算法上述bresenham算法在计算直线斜率

13、与误差项时用到小数与除法。可以改用整数以避免除法。由于算法中只用到误差项的符号，因此可作如下替换：e=e*2dxn改进的Bresenham画线算法程序：voidInterBresenhamline(intx0,inty0,intx1,inty1,intcolor)dx=x1-x0;dy=y1-y0;e=-dx;x=x0;y=y0;for(i=0;i=0)y+;e=e-2*dx;313.2.3 画画线线Bresenham算法算法圆圆弧的弧的扫扫描描转换转换n处处理理对对象：象：圆圆心在原点的心在原点的圆圆弧弧n圆圆的八的八对对称性称性图3-3-132n两种直接离散方法：两种直接离散方法：离散点:

14、离散角度:缺点：缺点：开根，三角函数运算，计算量大，不可取。33圆圆弧的弧的扫扫描描转换转换角度角度DDA法法转换圆转换圆弧弧x=x0+Rcosy=y0+Rsindx=-Rsin ddy=Rcosdxn+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值后，即可以增量方式获得圆周上的坐标，然后取整可得象素坐标。但要采用浮点运算、乘法运算、取整运算34n圆圆弧的正弧的正负负划分性划分性圆弧外的点：F(x，y)0圆弧内的点：F(x，y)03.3.1 角度角度D

15、DA法法转换圆转换圆弧弧图3-3-235n生成生成圆圆弧的中点算法弧的中点算法考考虑对虑对象：象：第二个八分第二个八分圆圆，第一象限的八分之一第一象限的八分之一圆圆弧弧 PP1P23.3.1 角度角度DDA法法转换圆转换圆弧弧图3-3-336问题：与直线情形类似圆弧的隐函数：F(x,y)=x2+y2-R2=0切线斜率min-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-R21）若

16、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，算法中有浮点数，用e=d代替角度角度DDA法法转换圆转换圆弧弧38所以：初始化运算d0=1.25R对应于e0=1-R判别式d0对应于e-0.25又因为：e的初值e0为整数，运算过程中的分量也为整数，故e始终为整数所以：e-0.25等价于e0程序如下（完全用整数实现）：

17、MidpointCircle(r,color)Intr,color;intx,y,d;x=0;y=r;d=1-r;putpixcel(x,y,color);while(xy)if(d0)d+=2*x+3;x+;elsed+=2*(x-y)+5;x+;y-;putpixcel(x,y,color);393.3.2 Bresenham画画圆圆算法算法 现在从A点开始向右下方逐点来寻找弧AB要用的点。如图中点Pi-1是已选中的一个表示圆弧上的点，根据弧AB的走向，下一个点应该从Hi或者Li中选择。显然应选离AB最近的点作为显示弧AB的点。假设圆的半径为R，显然，当xHi2+yHi2-R2R2-(xL

18、i2+yLi2)时，应该取Li。否则取Hi。令di=xHi2+yHi2+xli2+yli2-2R2显然，当di0时应该取Li。否则取Hi。Pi-1HiLi图3-3-440剩下的问题是如何快速的计算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-2R23.3.2 Bresenham画画圆圆算法算法di+1=(xi+1)2+yi2+(xi+1)2+(yi-1)2-2R2=2xi2+4xi+2yi2-2yi-2R2+3Pi-1HiLi

19、图3-3-441当di取Hi-yi=yi-1，则di+1=di+4xi-1+6当di0时-取Li-yi=yi-1-1，则di+1=di+4(xi-1-yi-1)+103.3.2 Bresenham画画圆圆算法算法Pi-1HiLi图3-3-4易知x0=0，y0=R,x1=x0+1因此d0+1=12+y02+12+(y0-1)2-2R2=3-2y0=3-2R421、求误差初值，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、计算下一个误差：ifp

20、(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;ifx=y则end；否则返2。3.3.2 Bresenham画画圆圆算法算法433.3.2 Bresenham画画圆圆算法算法443.3.3 椭圆椭圆的的扫扫描描转换转换nF(x,y)=b2x2+a2y2-a2b=0n椭圆的对称2性，只考虑第一象限椭圆弧生成，分上下两部分，以切线斜率为-1的点作为分界点。n椭圆上一点处的法向：N(x,y)=F(xi)+F(yj)=2b2xi+2a2yj图3-3-545M2在当前中点处，法向量(2b2(xp+1)，2a2(yp-0.5)的y

21、分量比x分量大,即：b2(xp+1)a2(yp-0.5),而在下一中点，不等式改变方向，则说明椭圆弧从上部分转入下部分。3.3.3 椭圆椭圆的的扫扫描描转换转换在上半部分,法向量的y分量大在下半部分,法向量的x分量大上半部分下半部分法向量两分量相等M1图3-3-646n椭圆的中点算法与圆弧中点算法类似：确定一个象素后，接着在两个候选象素的中点计算一个判别式的值，由判别式的符号确定更近的点。先讨论椭圆弧的上部分(xp,yp)中点(xp+1,yp-0.5)d1=F(xp+1,yp-0.5)=b2(xp+1)2+a2(yp-0.5)2-a2b23.3.3 椭圆椭圆的的扫扫描描转换转换47根据d1的符

22、号来决定下一像素是取正右方的那个，还是右下方的那个。n若d10，中点在椭圆内，取正右方象素，判别式更新为：d1=F(xp+2,yp-0.5)=d1+b2(2xp+3)d1的增量为b2(2xp+3)n当d10，中点在椭圆外，取右下方象素，更新判别式：d1=F(xp+2,yp-1.5)=d1+b2(2xp+3)+a2(-2yp+2)d1的增量为b2(2xp+3)+a2(-2yp+2)3.3.3 椭圆椭圆的的扫扫描描转换转换48nd1的初始条件：椭圆弧起点为(0，b)，第一个中点为(1,b-0.5)初始判别式：d10=F(1,b-0.5)=b*b+a*a(-b+0.25)转入下一部分，下一象素可能是

23、一正下方或右下方，此时判别式要初始化。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)inta,b,color;intx,y;floatd1,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)if(d20)d2+=b*b*(2*x+2)+a*a*(

24、-2*y+3);x+;y-；elsed2+=a*a*(-2*y+3);y-;putpixel(x,y,color);513.3.3 椭圆椭圆的的扫扫描描转换转换3.3.4 生成生成圆圆弧的多弧的多边边形逼近法形逼近法用正多边形近似代替圆,显示多边形的边可用扫描转换直线段的中点算法来实现。圆的正内接多边形迫近法圆的等面积正多边形迫近法52q圆的正内接多边形迫近法圆的正内接多边形迫近法n原理原理n计算多边形各顶点的递推公式计算多边形各顶点的递推公式 Xi+1cos a-sin a Xi =Yi+1sin a cosa Yi因为:a是常数，sin a，cosa只在开始时计算一次所以，一个顶点只需4次

25、乘法，共4n次乘法，外加直线段的中点算法的计算量。生成圆弧的多边形逼近法生成圆弧的多边形逼近法图3-3-753图3-3-8问题问题：给给定最大逼近定最大逼近误误差（最大差（最大 距离）距离）DELTA，如何确定多，如何确定多边边形形的的边边数数n或或a？另外，用矢量运算可以简化计算，推出求顶点的逆推公式(p60)d=RRcos(a/2)=(RDELTA)/Ra=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)=13.4 易画曲易画

26、曲线线的正的正负负法法图3-4-2603.5 线线画画图图元的属性控制（元的属性控制（1/5）n线宽线宽控制控制q像素复制方法像素复制方法n优优点：点：q实现简单实现简单n缺点：缺点：q线线段两端要么段两端要么为为水平的，水平的，要么是要么是竖竖直的直的q折折线顶线顶点点处处有缺口有缺口图3-5-1图3-5-261q图图元的元的宽宽度不均匀度不均匀q产产生生宽宽度度为为偶数像素的偶数像素的图图元效果不好元效果不好图3-5-33.5 线线画画图图元的属性控制（元的属性控制（2/5）62q移移动动刷子刷子3.5 线线画画图图元的属性控制（元的属性控制（3/5）图3-5-463q利用填充利用填充图图元元n优优点：点：q生成的生成的图图形形质质量高量高n缺点缺点q计计算量大算量大q有些有些图图形的等距形的等距线难线难以以获获得得图3-5-43.5 线线画画图图元的属性控制（元的属性控制（4/5）64n线线型控制型控制1111001111001111003.5 线线画画图图元的属性控制（元的属性控制（5/5）图3-5-565