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

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

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

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

3、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+kl从起点开始朝终点方向从起点开始朝终点方向l画点画点(x,y)l在在x轴或轴或y轴上走一个单位轴上走一个单位长（沿长（沿x轴还是轴还是y

4、轴取决于轴取决于直线的倾斜角）直线的倾斜角）l由直线的倾斜程度（斜率由直线的倾斜程度（斜率或斜率的倒数）决定另一或斜率的倒数）决定另一坐标的增量，获得下一点坐标的增量，获得下一点的座标的座标l将将x或或y四舍五入，得四舍五入，得(x,y)l若若(x,y)不是终点则继续不是终点则继续起点起点终终点点未四舍五入前未四舍五入前最后选定的点最后选定的点1723456089123456780void DDALine(int x0void DDALine(int x0，int y0int y0，int x1int x1，int y1int y1，int color)int color)int x int

5、x；float dxfloat dx，dydy，y y，k k；dx=x1-x0dx=x1-x0；dy=y1-y0dy=y1-y0；k=dy/dxk=dy/dx；y=y0y=y0；for(x=x0for(x=x0；x=x1x，上述算法会出现什么情况？应如何处理？上述算法会出现什么情况？应如何处理？假定直线斜率假定直线斜率k在在0 01 1之间，当前象素点为之间，当前象素点为（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）称

6、为）称为M，Q为理想直线与为理想直线与x=xp+1+1垂线的交点。当垂线的交点。当M在在Q的的下方时，则取下方时，则取P2应为下一个象素点；当应为下一个象素点；当M在在Q的上方时，则取的上方时，则取P1为下一个为下一个象素点。这就是中点画线法的基本原理象素点。这就是中点画线法的基本原理过点过点(x0,y0)、(x1,y1)的直线段的直线段L的方程式为的方程式为F(x,y)=ax+by+c=0，欲判断中点，欲判断中点M在在Q点的上方还点的上方还是下方，只要把是下方，只要把M代入代入F（x，y），并判断它），并判断它的符号即可。为此，我们构造判别式的符号即可。为此，我们构造判别式:d=F(M)=F

7、(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,y+1,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+

8、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=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 y

9、0 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。void MidpointLine(int x0void MidpointLine(int x0，int y0int y0，int int x1x1，int y1int y1，int color)int color)int a int a，b b，d1d1，d2d2，d d，x x，y y；a=y0-y1

10、a=y0-y1；b=x1-x0b=x1-x0；d=2d=2*a+ba+b；d1=2d1=2*a a；d2=2d2=2*(a+b)(a+b)；x=x0 x=x0；y=y0y=y0；while(x=x1)while(x=x1)SetPixel(x SetPixel(x，y y，color);color);if(d0)if(d0)x+x+；y+y+；d+=d2;d+=d2;elseelse x+x+；d+=d1;d+=d1;/*while while*/*midPointLine midPointLine*/起点起点终点终点初始值：初始值：a=-4;b=7;d=2*a+b=-1;d1=2*a=-8;

11、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=-1原理：原理：假定直线斜率假定直线斜率,0k1 时时 d=d-1;当当d=0.5取取(x+1,y)，否则取，否则取(x+1,y+1)。令。令e=d-0.5,显然显然 e 的初值为的初值为-0.5。这样可用。这样可用e的符号来进行判断。的符号来进行判断。ddddvoid Bresenhamlin

12、e(int x0,int y0,int x1,int void Bresenhamline(int x0,int y0,int x1,int y1,int color)y1,int color)int x,y,dx,dy int x,y,dx,dy；float k,e;float k,e;dx=x1-x0 dx=x1-x0；dy=y1-y0dy=y1-y0；k=dy/dxk=dy/dx；x=x0,x=x0,；y=y0y=y0；e=-0.5e=-0.5；for(i=0for(i=0；i=dxi=dx；i+)i+)Setpixel(x,y,color);Setpixel(x,y,color);x=

13、x+1 x=x+1；e=e+k;e=e+k;if(e0)if(e0)y+y+；e=e-1;e=e-1;程序如下：思考题：思考题：如何去除上述程序中的浮点运算、乘除法？如何去除上述程序中的浮点运算、乘除法？void Bresenhamline(int x0,int y0,int x1,void Bresenhamline(int x0,int y0,int x1,int y1,int color)int y1,int color)dx=x1-x0,dx=x1-x0,；dy=y1-y0,dy=y1-y0,；e=-dx;e=-dx;x=x0 x=x0；y=y0;y=y0;for(i=0;i=dx;i

14、+)for(i=0;i=dx;i+)Setpixel(x,y,color);Setpixel(x,y,color);e=e+2 e=e+2*dy;x+;dy;x+;if(e0)y+;e=e-2 if(e0)y+;e=e-2*dxdx 从速度考虑，还有那些可以改进？起点起点终点终点初始值：初始值：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/14

15、712345612345678008、X6=7,Y6=4,e=1/14讨论象素点的选取是否有规律？有何用l实线就是将选到所有的点都画出来实线就是将选到所有的点都画出来l虚线就是在所选的点中选相邻的几个画，然后虚线就是在所选的点中选相邻的几个画，然后接着相邻的几个不画接着相邻的几个不画l点线就是在所选的点中，每隔几个就画一个点线就是在所选的点中，每隔几个就画一个l线宽只对实线有效，实际上就是根据其倾斜角线宽只对实线有效，实际上就是根据其倾斜角然后选定是在选中的点的然后选定是在选中的点的(x+-width/2,y)或者或者(x,y+-width/2)也画出来，相当于一把近似垂直于也画出来，相当于一

16、把近似垂直于直线的刷子直线的刷子 多边形多边形l确定多边形的顶点确定多边形的顶点l用直线顺序连接起来用直线顺序连接起来 圆形圆形l根据圆的对称性将其扩展根据圆的对称性将其扩展到四个象限即可获得整圆到四个象限即可获得整圆 二、圆的生成算法二、圆的生成算法 即是找出逼近圆的一组象素，按扫描线即是找出逼近圆的一组象素，按扫描线顺序，对这些象素进行写操作。顺序，对这些象素进行写操作。下面仅以圆心在原点的圆为例，讨论圆下面仅以圆心在原点的圆为例，讨论圆的生成算法。的生成算法。1.圆弧扫描算法圆弧扫描算法 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