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

单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第三章 基本图形生成算法图形,本章将主要研究在,光栅显示器,上的直线、圆、椭圆等的生成算法。,内存,显存或缓存,设备阵列,图形函数入口,LINE（）等,主机,显卡、其他接口,确定象素位置,写入颜色等属性,显示器、打印机等,由驱动程序写入设备,D/A转换,显卡口,并行口,USB口,内存插槽,CPU,GPU：生成点阵图形,运行图形程序,D/A转换：图形显示,基本图形的生成,几何图形,i,|,P,i 最接近图形的象素,基本图形的生成算法任务之一就是找出所有的,i,.,点表示为象素（,Pixel），,对应于显存地址单元,读写某一象素是硬件设备提供的最基本功能,一维图形，由一个象素宽的直线或曲线表示,二维图形由确定区域的象素表示,线图元的扫描转换是基本图形生算法的基础；,3.2、直线的生成算法,即是找出逼近直线的一组象素，按扫描线顺序，对这些象素进行写操作。,3.2.1.,数值微分法（）,假定直线的起点、终点分别为：（X0,Y0),(X1,Y1)，且都为整数。,(X,i+1,Y,i,+k),(X,i,Int(Y,i,+0.5),(X,i,Y,i,),栅格交点表示象素点位置,直线的斜率：,k=(Y1-Y0)/(X1-X0),为讨论方便，假定|k|=1,直线方程：,=k*X+B,设的增量为x=，可得如下的增量方程：,Y,i+1,=k X,i+1,+B,=k(X,i,+Dx)+B,=kX,i,+B+k Dx,=Y,i,+k Dx,=Y,i,+k,画直线的DDA算法,从起点开始朝终点方向,画点(x,y),在x轴或y轴上走一个单位长（沿x轴还是y轴取决于直线的倾斜角）,由直线的倾斜程度（斜率或斜率的倒数）决定另一坐标的增量，获得下一点的座标,将x或y四舍五入，得(x,y),若(x,y)不是终点则继续,起点,终点,未四舍五入前,最后选定的点,1,7,2,3,4,5,6,0,8,9,1,2,3,4,5,6,7,8,0,void DDALine(int x0，int y0，int x1，int y1，int color),int x；,float dx，dy，y，k；,dx=x1-x0；dy=y1-y0；,k=dy/dx；y=y0；,for(x=x0；x，,上述算法会出现什么情况？应如何处理？,3.2.2 生成直线的中点画线算法,假定直线斜率,k,在0,1之间，当前象素点为,（,x,p,y,p,）,，则下一个象素点有两种可选择点,P,1,（,x,p,+1,y,p,）或,P,2,（,x,p,+1,y,p,+1）。若,P,1,与,P,2,的中点（,x,p,+1,y,p,+0.5）称为,M,，,Q,为理想直线与,x,=,x,p,+1垂线的交点。当,M,在,Q,的下方时，则取,P,2,应为下一个象素点；当,M,在,Q,的上方时，则取,P,1,为下一个象素点。这就是中点画线法的基本原理,过点,(,x,0,y,0,)、(,x,1,y,1,),的直线段,L,的方程式为,F,(,x,y,),=ax+by+c=,0,，欲判断中点,M,在,Q,点的上方还是下方，只要把,M,代入,F,（,x,，,y,），并判断它的符号即可。为此，我们构造判别式,:,d,=,F,(,M,)=,F,(,x,p,+1,y,p,+0.5)=,a,(,x,p,+1)+,b,(,y,p,+0.5)+,c,当,d,0,时，,M,在,L,(,Q,点,),上方，取,P,1,为下一个象素；,当,d=,0,时，选,P,1,或,P,2,均可，约定取,P,1,为下一个象素；,若当前象素处于,d=,0情况，则取正右方象素,P,1,(,x,p,+1,y,p,),要判下一个象素位置，应计算,d,1,=,F,(,x,p,+2,y,p,+0.5)=,a,(,x,p,+2)+,b,(,y,p,+0.5)=,d,+,a,，增量为,a,。,若,d,0时，则取右上方象素,P,2,(,x,p,+1,y,p,+1)。要判断再下一象素，则要计算,d,2,=,F,(,x,p,+2,y,p,+1.5)=,a,(,x,p,+2)+,b,(,y,p,+1.5)+,c,=,d,+,a,+,b,，增量为,a,b,。画线从(,x,0,y,0,)开始，,d,的初值,d,0,=,F,(,x,0,+1,y,0,+0.5)=,F,(,x,0,y,0,)+,a,+0.5,b，,因,F,(,x,0,y,0,)=0，所以,d,0,=,a,+0.5,b,。,其中，,a=y,0,-,y,1,b,=,x,1,-,x,0,c,=,x,0,y,1,-,x,1,y,0,。,void MidpointLine(int x0，int y0，int x1，int y1，int color),int a，b，d1，d2，d，x，y；,a=y0-y1；b=x1-x0；d=2*a+b；,d1=2*a；d2=2*(a+b)；,x=x0；y=y0；,while(x=x1),SetPixel(x，y，color);,if(d0)x+；y+；d+=d2;,else x+；d+=d1;,/*while*/,/*midPointLine*/,中点画线算法示例,起点,终点,初始值：a=-4;b=7;d=2*a+b=-1;d1=2*a=-8;d2=2*(a+b)=6,1、X0=0,Y0=0,d=-1,2、X1=1,Y1=1,d=5,3、X2=2,Y2=1,d=-3,4、X3=3,Y3=2,d=3,5、X4=4,Y4=2,d=-5,6、X5=5,Y5=3,d=1,7、X6=6,Y6=3,d=-7,7,1,2,3,4,5,6,1,2,3,4,5,6,7,8,0,0,8、X6=7,Y6=4,d=-1,3.2.3 生成直线的,Bresenham,算法,x,i,X,i+1,Y,i,Y,i+1,C,D,B,A,原理：,假定直线斜率,0k1 时 d=d-1;,当d=0.5取(x+1,y)，否则取(x+1,y+1)。令e=d-0.5,显然 e 的初值为-0.5。这样可用e的符号来进行判断。,d,d,d,d,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；,x=x0,；y=y0；,e=-0.5；,for(i=0；i=dx；i+),Setpixel(x,y,color);,x=x+1；e=e+k;,if(e0),y+；e=e-1;,程序如下：,思考题：,如何去除上述程序中的浮点运算、乘除法？,void Bresenhamline(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=dx;i+),Setpixel(x,y,color);,e=e+2*dy;x+;,if(e0)y+;e=e-2*dx,程序改进,从速度考虑，还有那些可以改进？,Bresenham画线算法示例,起点,终点,初始值：dx=7;dy=4;k=4/7,e=-7/14,1、X0=0,Y0=0,e=1/14,2、X1=1,Y1=1,e=-5/14,3、X2=2,Y2=1,e=3/14,4、X3=3,Y3=2,e=-3/14,5、X4=4,Y4=2,e=5/14,6、X5=5,Y5=3,e=-1/14,7、X6=6,Y6=3,e=7/14,7,1,2,3,4,5,6,1,2,3,4,5,6,7,8,0,0,8、X6=7,Y6=4,e=1/14,讨论象素点的选取是否有规律？有何用,直线生成算法的改进,如何利用上述算法实现任意直线的绘制？,关于线型线宽的说明,实线就是将选到所有的点都画出来,虚线就是在所选的点中选相邻的几个画，然后接着相邻的几个不画,点线就是在所选的点中，每隔几个就画一个,线宽只对实线有效，实际上就是根据其倾斜角然后选定是在选中的点的(x+-width/2,y)或者(x,y+-width/2)也画出来，相当于一把近似垂直于直线的刷子,关于多边形和圆形的作图,多边形,确定多边形的顶点,用直线顺序连接起来,圆形,根据圆的对称性将其扩展到四个象限即可获得整圆,二、圆的生成算法,即是找出逼近圆的一组象素，按扫描线顺序，对这些象素进行写操作。,下面仅以圆心在原点的圆为例，讨论圆的生成算法。,1.圆弧扫描算法,X,2,+Y,2,=R,2,Y=,Sqrt(R,2,-X,2,),在一定范围内，每给定一X值，可得一Y值。,当X取整数时，Y须圆整。,缺点：浮点运算，开方，圆整，不均匀。,2.角度DDA法,x=x,0,+Rcos,y=y,0,+Rsin,dx=-Rsin,d,dy=Rcos,d,x,n+1,=x,n,+dx,y,n+1,=y,n,+dy,x,n+1,=x,n,-(y,n,-y,0,)d,y,n+1,=y,n,+(x,n,-x,0,)d,显然，确定x,y的初值及d,值后，即可以增量方式获得圆周上的坐标，然后取整可得象素坐标。但要采用浮点运算、乘法运算。,3.中点法,利用圆的对称性，只须讨论1/8圆。,M,P1,P2,P（Xp，Yp）,P为当前点亮象素，那么，下一个点亮的象素可能是P1（Xp+1，Yp）或P2（Xp+1，Yp+1)。,构造一函数：,F（X，Y）=X,2,+Y,2,-R,2,F（X，Y）=0 （X，Y）在圆上；,F（X，Y）0 （X，Y）在圆外。,M为P1、P2间的中点，M=(Xp+1,Yp-0.5),有如下结论：,F（M）=0 取P2,为此，可采用如下判别式：,d=F(M),=F(x,p,+1,y,p,-0.5),=(x,p,+1),2,+(y,p,-0.5),2,-R,2,若d=0,则P2 为下一个象素，那么再下一个象素的判别式为：,d=F(x,p,+2,y,p,-1.5),=(x,p,+2),2,+(y,p,-1.5),2,-R,2,=d+2(x,p,-y,p,)+5,即d 的增量为 2(x,p,-y,p,)+5.,d,的初值:,d0=F(1,R-0.5),=1+(R-0.5),2,-R,2,=1.25-R,MidpointCircle(int r),int x,y;,float d;,x=0;y=r;d=1.25-r;,while(xy),setpixel(x,y);,if(d0),d+=2*x+3;x+,else,d+=2*(x-y)+5;,x+;y-;,该程序如何改进，提高效率？,Bresenham画圆算法,讨论、圆的中点算法与Bresenham算法是否一致？,椭圆的生成算法,F(x,y)=b,2,x,2,+a,2,y,2,-a,2,b,2,=0,椭圆的对称性，只考虑第一象限椭圆弧生成，分上下两部分，以切线斜率为-1的点作为分界点。,椭圆上一点处的法向：,N(x,y)=(F),x,i +(F),y,j,=2b,2,x i +2a,2,y j,在上半部分,法向量的y分量大,在下半部分,法向量的x分量大,上半部分,下半部分,法向量,两分量相等,M1,M2,在当前中点处，法向量（2b,2,(Xp+1)，2a,2,(Yp-0.5)的y分量比x分,量大,即：b,2,(Xp+1)a,2,(Yp-0.5),而在下一中点，不等式改变方,向，则说明椭圆弧从上部分转入下部分,椭圆的中点画法,与圆弧中点算法类似：确定一个象素后，接着在两个候选象素的中点计算一个判别式的值，由判别式的符号确定更近的点,先讨论椭圆弧的上部分,设(Xp，Yp)已确定，则下一待选像素的中点是(Xp+1,Yp-0.5),d1=F(Xp+1,Yp-0.5)=b,2(,Xp+1),2,+a,2(,Yp-0.5),2,-a,2,b,2,根据d1的符号来决定下一像素是取正右方的那个，还是右上方的那个。,若d10，中点在椭圆内，取正右方象素，判别式更新为：,d1=F(Xp+2,Yp-0.5)=d1+b