计算机地图制图原理与方法基本图形生成算法.ppt

《计算机地图制图原理与方法基本图形生成算法.ppt》由会员分享，可在线阅读，更多相关《计算机地图制图原理与方法基本图形生成算法.ppt（35页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第三章第三章 基本图形生成算法图形基本图形生成算法图形本章将主要研究在本章将主要研究在光栅显示器光栅显示器上的直线、圆、上的直线、圆、椭圆等的生成算法。椭圆等的生成算法。内存内存显存或缓存显存或缓存设备阵列设备阵列图形函数入口LINE（）等主机主机显显卡、其他接口卡、其他接口确定象素位置写入颜色等属性显示器、打印机等显示器、打印机等由驱动程序写入设备D/A转换显卡口并行口USB口内存插槽CPUGPU：生成点阵图形运行图形程序D/A转换：图形显示基本图形的生成基本图形的生成几何图形几何图形i|Pi 最接近图形的象素最接近图形的象素 基本图形的生成算法任务之一就是找出所有的基本图形的生成算法任务之

2、一就是找出所有的i.l点表示为象素（点表示为象素（Pixel），），对应于显存地址单元对应于显存地址单元l读写某一象素是硬件设备提供的最基本功能读写某一象素是硬件设备提供的最基本功能l一维图形，由一个象素宽的直线或曲线表示一维图形，由一个象素宽的直线或曲线表示l二维图形由确定区域的象素表示二维图形由确定区域的象素表示l线图元的扫描转换是基本图形生算法的基础；线图元的扫描转换是基本图形生算法的基础；3.2、直线的生成算法、直线的生成算法即是找出逼近直线的一组象素，按扫描即是找出逼近直线的一组象素，按扫描线顺序，对这些象素进行写操作。线顺序，对这些象素进行写操作。3.2.1.数值微分法（）数值微分

3、法（）假定直线的起点、终点分别为：（假定直线的起点、终点分别为：（X0,Y0),(X1,Y1)，且都为整数。且都为整数。(X i+1,Yi+k)(X i,Int(Yi+0.5)(X i,Yi)栅格交点表示象素点位置栅格交点表示象素点位置直线的斜率：直线的斜率：k=(Y1-Y0)/(X1-X0)为讨论方便，假定为讨论方便，假定|k|=1 直线方程：直线方程：=k*X+B设的增量为设的增量为x=，可得如下的增量方程：可得如下的增量方程：Yi+1 =k Xi+1+B =k(Xi+Dx)+B =kXi+B+k Dx =Yi+k Dx =Yi+k画直线的画直线的DDA算法算法l从起点开始朝终点方向从起点

4、开始朝终点方向l画点画点(x,y)l在在x轴或轴或y轴上走一个单位轴上走一个单位长（沿长（沿x轴还是轴还是y轴取决于轴取决于直线的倾斜角）直线的倾斜角）l由直线的倾斜程度（斜率由直线的倾斜程度（斜率或斜率的倒数）决定另一或斜率的倒数）决定另一坐标的增量，获得下一点坐标的增量，获得下一点的座标的座标l将将x或或y四舍五入，四舍五入，得得(x,y)l若若(x,y)不是终点则继续不是终点则继续起点起点终终点点未未四四舍舍五五入入前前最后选定的点最后选定的点1723456089123456780voidvoid DDALine DDALine(intint x0 x0，intint y0 y0，int

5、int x1 x1，intint y1 y1，intint color)color)int int x x；float float dx dx，dy dy，y y，k k；dx dx=x1-x0=x1-x0；dy dy=y1-y0=y1-y0；k=k=dydy/dxdx；y=y0y=y0；for(x=x0 for(x=x0；x=x1x，上述算法会出现什么情况？应如何处理？上述算法会出现什么情况？应如何处理？3.2.2 3.2.2 3.2.2 3.2.2 生成直线的中点画线算法生成直线的中点画线算法生成直线的中点画线算法生成直线的中点画线算法假定直线斜率假定直线斜率k在在0 01 1之间，当前象

6、素点为之间，当前象素点为（xp,yp），则下一个象素点有则下一个象素点有两种可选择点两种可选择点P1（xp+1,+1,yp）或或P2 2（xp+1,+1,yp+1+1）。）。若若P1与与P2的中点的中点（xp+1,+1,yp+0.5+0.5）称为称为M，Q为理想直线与为理想直线与x=xp+1+1垂线的交点。当垂线的交点。当M在在Q的的下方时，则取下方时，则取P2应为下一个象素点；当应为下一个象素点；当M在在Q的上方时，则取的上方时，则取P1为下一个为下一个象素点。这就是中点画线法的基本原理象素点。这就是中点画线法的基本原理过点过点(x0,y0)、(x1,y1)的直线段的直线段L的方程式为的方程

7、式为F(x,y)=ax+by+c=0，欲判断中点欲判断中点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在在L(Q点点)上方，取上方，取P1为下一个象素；为下一个象素；当当d=0时，选时，选P1或或P2均可，约定取均可，约定取P1为下一个象素；为下一个象素；若当前象素处于若当前象素处于d=d=0 0情况，则取正右方象素情况，则取正右方象素P P1 1(x xp p+1,+1,

8、y yp p),),要判下一个象素要判下一个象素位置，应计算位置，应计算 d d1 1=F F(x xp p+2,+2,y yp p+0.5)=+0.5)=a a(x xp p+2)+2)+b b(y yp p+0.5)=+0.5)=d d+a a，增量为增量为a a。若若d d00时，则取右上方象素时，则取右上方象素P P2 2(x xp p+1,+1,y yp p+1)+1)。要判断再下一象素，要判断再下一象素，则要计算则要计算d d2 2=F F(x xp p+2,+2,y yp p+1.5)=+1.5)=a a(x xp p+2)+2)+b b(y yp p+1.5)+1.5)+c c

9、=d d+a a+b b，增量为增量为a ab b。画线从画线从(x x0 0,y y0 0)开始，开始，d d的初值的初值 d d0 0=F F(x x0 0+1,+1,y y0 0+0.5)=+0.5)=F F(x x0 0,y y0 0)+)+a a+0.5+0.5b b，因因 F F(x x0 0,y y0 0)=0)=0，所以所以d d0 0=a a+0.5+0.5b b。其中，其中，a=ya=y0 0-y y1 1,b b=x x1 1-x x0 0,c c=x x0 0y y1 1-x x1 1y y0 0。voidvoid MidpointLineMidpointLine (i

10、ntint x0 x0，intint y0y0，intint x1x1，int int y1 y1，intint color)color)int int a a，b b，d1 d1，d2 d2，d d，x x，y y；a=y0-y1 a=y0-y1；b=x1-x0 b=x1-x0；d=2*a+bd=2*a+b；d1=2*a d1=2*a；d2=2*(a+b)d2=2*(a+b)；x=x0 x=x0；y=y0y=y0；while(x=x1)while(x=x1)SetPixel SetPixel(x(x，y y，color);color);if(d0)x+if(d0)x+；y+y+；d+=d2;

11、d+=d2;else x+else x+；d+=d1;d+=d1;/*while*/*while*/*/*midPointLine midPointLine*/*/中点画线算法示例中点画线算法示例起点起点终点终点初始值：初始值：a=-4;b=7;d=2*a+b=-1;d1=2*a=-8;d2=2*(a+b)=61、X0=0,Y0=0,d=-12、X1=1,Y1=1,d=53、X2=2,Y2=1,d=-34、X3=3,Y3=2,d=35、X4=4,Y4=2,d=-56、X5=5,Y5=3,d=17、X6=6,Y6=3,d=-7712345612345678008、X6=7,Y6=4,d=-13.

12、2.3 3.2.3 3.2.3 3.2.3 生成直线的生成直线的生成直线的生成直线的BresenhamBresenham算法算法算法算法x xi iX Xi i+1+1Y Yi iY Yi+1i+1C CD DB BA A原理：原理：假定直线斜率假定直线斜率,0k1 时时 d=d-1;当当d=0.5取取(x+1,y)，否则取否则取(x+1,y+1)。令令e=d-0.5,显然显然 e 的初值为的初值为-0.5。这样可用。这样可用e的符号来进行判断。的符号来进行判断。ddddvoidvoid BresenhamlineBresenhamline (intint x0,x0,intint y0,y0

13、,intint x1,x1,intint y1,y1,intint color)color)int int x,y,x,y,dx dx,dy dy；float k,e;float k,e;dx dx=x1-x0=x1-x0；dydy=y1-y0=y1-y0；k=k=dydy/dxdx；x=x0,x=x0,；y=y0y=y0；e=-0.5 e=-0.5；for(i=0 for(i=0；i=i=dxdx；i+)i+)Setpixel Setpixel(x,y,color);(x,y,color);x=x+1 x=x+1；e=e+k;e=e+k;if(e0)if(e0)y+y+；e=e-1;e=e-

14、1;程序如下：思考题：思考题：如何去除上述程序中的浮点运算、乘除法如何去除上述程序中的浮点运算、乘除法？void void BresenhamlineBresenhamline (intint x0,x0,intint y0,y0,intint x1,x1,intint y1,y1,intint color)color)dx dx=x1-x0,=x1-x0,；dydy=y1-y0,=y1-y0,；e=-e=-dxdx;x=x0 x=x0；y=y0;y=y0;for(i=0;i=for(i=0;i=dxdx;i+);i+)SetpixelSetpixel(x,y,color);(x,y,colo

15、r);e=e+2*e=e+2*dydy;x+;x+;if(e0)y+;e=e-2*if(e0)y+;e=e-2*dxdx 程序改进程序改进从速度考虑，还有那些可以改进？Bresenham画线算法示例画线算法示例起点起点终点终点初始值：初始值：dx=7;dy=4;k=4/7 e=-7/141、X0=0,Y0=0,e=1/142、X1=1,Y1=1,e=-5/143、X2=2,Y2=1,e=3/144、X3=3,Y3=2,e=-3/145、X4=4,Y4=2,e=5/146、X5=5,Y5=3,e=-1/147、X6=6,Y6=3,e=7/14712345612345678008、X6=7,Y6=

16、4,e=1/14讨论象素点的选取是否有规律？有何用直线生成算法的改进 如何利用上述算法实现任意直线的绘制？如何利用上述算法实现任意直线的绘制？关于线型线宽的说明关于线型线宽的说明l实线就是将选到所有的点都画出来实线就是将选到所有的点都画出来l虚线就是在所选的点中选相邻的几个画，然后虚线就是在所选的点中选相邻的几个画，然后接着相邻的几个不画接着相邻的几个不画l点线就是在所选的点中，每隔几个就画一个点线就是在所选的点中，每隔几个就画一个l线宽只对实线有效，实际上就是根据其倾斜角线宽只对实线有效，实际上就是根据其倾斜角然后选定是在选中的点然后选定是在选中的点的的(x+-width/2,y)或者或者(

17、x,y+-width/2)也画出来，相当于一把近似垂也画出来，相当于一把近似垂直于直线的刷子直于直线的刷子关于多边形和圆形的作图关于多边形和圆形的作图 多边形多边形l确定多边形的顶点确定多边形的顶点l用直线顺序连接起来用直线顺序连接起来 圆形圆形l根据圆的对称性将其扩展根据圆的对称性将其扩展到四个象限即可获得整圆到四个象限即可获得整圆 二、圆的生成算法二、圆的生成算法 即是找出逼近圆的一组象素，按扫描线即是找出逼近圆的一组象素，按扫描线顺序，对这些象素进行写操作。顺序，对这些象素进行写操作。下面仅以圆心在原点的圆为例，讨论圆下面仅以圆心在原点的圆为例，讨论圆的生成算法。的生成算法。1.圆弧扫描

18、算法圆弧扫描算法 X2 +Y2 =R2 Y=Sqrt(R2-X2)在一定范围内，每给定在一定范围内，每给定一一X值，可得一值，可得一Y值。值。当当X取整数时，取整数时，Y须圆整。须圆整。缺点：浮点运算，开方，圆整，不均匀。缺点：浮点运算，开方，圆整，不均匀。2.角度角度DDA法法 x=x0+Rcos y=y0+Rsin dx=-Rsin d dy=Rcos d xn+1=x n+dx y n+1=y n+dy xn+1=x n-(y n-y 0)d y n+1=y n+(x n-x 0)d 显然，确定显然，确定x,y的初值的初值及及d 值后，即可以值后，即可以增量方式获得圆周上的坐标，然后取整

19、增量方式获得圆周上的坐标，然后取整可得象素坐标。但要采用浮点运算、乘可得象素坐标。但要采用浮点运算、乘法运算。法运算。3.中点法中点法 利用圆的对称性，只须讨论利用圆的对称性，只须讨论1/8圆。圆。MP1P2P（Xp，Yp）P为当前点亮象素，那么，下一个点亮的象为当前点亮象素，那么，下一个点亮的象素可能是素可能是P1（Xp+1，Yp）或或P2（Xp+1，Yp+1)。构造一函数：构造一函数：F（X，Y）=X2 +Y2-R2 F（X，Y）=0 （X，Y）在圆上；在圆上；F（X，Y）0 （X，Y）在圆外。在圆外。M为为P1、P2间的中点间的中点，M=(Xp+1,Yp-0.5)有如下结论：有如下结论：

20、F（M）=0 取取P2为此，可采用如下判别式为此，可采用如下判别式：d=F(M)=F(xp+1,yp-0.5)=(xp+1)2+(yp-0.5)2-R2 若若d=0,则则P2 为下一个象素，那么再下一个象为下一个象素，那么再下一个象素的判别式为：素的判别式为：d=F(xp+2,yp-1.5)=(xp+2)2+(yp-1.5)2-R2 =d+2(xp-yp)+5 即即d 的增量为的增量为 2(xp-yp)+5.d的初值的初值:d0=F(1,R-0.5)=1+(R-0.5)2-R2 =1.25-R MidpointCircle(int r)int x,y;float d;x=0;y=r;d=1.2

21、5-r;while(xy)setpixel(x,y);if(d0)d+=2*x+3;x+else d+=2*(x-y)+5;x+;y-;该程序如何改进，提高效率？BresenhamBresenham画圆算法画圆算法讨论、圆的中点算法与讨论、圆的中点算法与BresenhamBresenham算法是否一致？算法是否一致？椭圆的生成算法椭圆的生成算法lF(x,y)=b2x2+a2y2-a2b2=0l椭椭圆圆的的对对称称性性，只只考考虑虑第第一一象象限限椭椭圆圆弧弧生生成成，分分上上下下两两部部分分，以以切切线线斜斜率率为为-1的点作为分界点。的点作为分界点。l椭圆上一点处的法向：椭圆上一点处的法向：

22、N(x,y)=(F)x i +(F)y j =2b2 x i +2a2 y j在上半部分在上半部分,法向量的法向量的y分量大分量大在下半部分在下半部分,法向量的法向量的x分量大分量大上半部分上半部分下半部分下半部分法向量法向量两分量相等两分量相等M1M2在当前中点处，法向量（在当前中点处，法向量（2b2(Xp+1)，2a2(Yp-0.5)的的y分量比分量比x分分量大量大,即：即：b2(Xp+1)a2(Yp-0.5),而在下一中点，不等式改变方而在下一中点，不等式改变方向，则说明椭圆弧从上部分转入下部分向，则说明椭圆弧从上部分转入下部分椭圆的中点画法椭圆的中点画法l与与圆圆弧弧中中点点算算法法类

23、类似似：确确定定一一个个象象素素后后，接接着着在在两两个个候候选选象象素素的的中中点点计计算算一一个个判判别别式式的的值值，由判别式的符号确定更近的点由判别式的符号确定更近的点先讨论椭圆弧的上部分先讨论椭圆弧的上部分设设(Xp，Yp)已已确确定定，则则下下一一待待选选像像素素的的中中点点是是(Xp+1,Yp-0.5)d1=F(Xp+1,Yp-0.5)=b2(Xp+1)2+a2(Yp-0.5)2-a2b2 根根据据d1的的符符号号来来决决定定下下一一像像素素是是取取正正右右方方的的那那个个，还是右上方的那个。还是右上方的那个。l若若d10，中中点点在在椭椭圆圆内内，取取正正右右方方象象素素，判判

24、别别式更新为：式更新为：d1=F(Xp+2,Yp-0.5)=d1+b2(2Xp+3)d1的增量为的增量为b2(2Xp+3)l当当d10，中中点点在在椭椭圆圆外外，取取右右下下方方象象素素，更更新新判判别式：别式：d1=F(Xp+2,Yp-1.5)=d1+b2(2Xp+3)+a2(-2Yp+2)d1的增量为的增量为b2(2Xp+3)+a2(-2Yp+2)l d1的初始条件：椭圆弧起点为的初始条件：椭圆弧起点为(0，b)；l第一个中点为第一个中点为(1,b-0.5)初始判别式：初始判别式：d10=F(1,b-0.5)=b*b+a*a(-b+0.25)l转转入入下下一一部部分分，下下一一象象素素可可

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程序：程序：void draw_Ellipe_Mid(int a,int b)int x,y;float d1,d2;x=0;y=b;d1=b*b+a*a*(-b+0.25);while(b*b*(x+1)a*a*(y-0.5)SetPixel(x,y);if(d1=0)SetPixel(x,y);if(d2 0)d2+=b*b*(2*x+2)+a*a*(-2*y+3);x+;y-;else d2+=a*a*(-2*y+3);y-;