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

第三章基本图形生成算法图形本章将主要研究在光栅显示器上的直线、圆、椭圆等的生成算法。内存显存或缓存设备阵列图形函数入口LINE（）等主机显卡、其他接口确定象素位置写入颜色等属性显示器、打印机等由驱动程序写入设备D/A转换显卡口并行口USB口内存插槽CPUGPU：生成点阵图形运行图形程序D/A转换：图形显示基本图形的生成几何图形Ｇ＝｛Ｐi|Pi最接近图形的象素｝基本图形的生成算法任务之一就是找出所有的Ｐi.点表示为象素（Pixel），对应于显存地址单元读写某一象素是硬件设备提供的最基本功能一维图形，由一个象素宽的直线或曲线表示二维图形由确定区域的象素表示线图元的扫描转换是基本图形生算法的基础；3.2、直线的生成算法即是找出逼近直线的一组象素，按扫描线顺序，对这些象素进行写操作。3.2.1.数值微分法（ＤＤＡ）假定直线的起点、终点分别为：（X0,Y0),(X1,Y1)，且都为整数。(Xi+1,Yi+k)(Xi,Int(Yi+0.5))(Xi,Yi)栅格交点表示象素点位置直线的斜率：k=(Y1-Y0)/(X1-X0)为讨论方便，假定|k|=1直线方程：Ｙ=k*X+B设Ｘ的增量为Ｄx=１，可得如下Ｙ的增量方程：Yi+1=kXi+1+B=k(Xi+Dx)+B=kXi+B+kDx=Yi+kDx=Yi+k画直线的DDA算法从起点开始朝终点方向画点(x,y)在x轴或y轴上走一个单位长（沿x轴还是y轴取决于直线的倾斜角）由直线的倾斜程度（斜率或斜率的倒数）决定另一坐标的增量，获得下一点的座标将x或y四舍五入，得(x,y)若(x,y)不是终点则继续起点终点未四舍五入前最后选定的点1723456089123456780voidDDALine(intx0，inty0，intx1，inty1，intcolor){intx；floatdx，dy，y，k；dx=x1-x0；dy=y1-y0；k=dy/dx；y=y0；for(x=x0；x=x1；x++){SetPixel(x，int(y+0.5)，color);y=y+k;}}缺点：浮点运算、取整－－》废时，且不利于硬件实现。问题：为什么｜k｜《１？，若｜k｜１，上述算法会出现什么情况？应如何处理？3.2.2生成直线的中点画线算法假定直线斜率k在0~1之间，当前象素点为（xp,yp），则下一个象素点有两种可选择点P1（xp+1,yp）或P2（xp+1,yp+1）。若P1与P2的中点（xp+1,yp+0.5）称为M，Q为理想直线与x=xp+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(xp+1,yp+0.5)=a(xp+1)+b(yp+0.5)+c当d0时，M在L(Q点)下方，取P2为下一个象素；当d0时，M在L(Q点)上方，取P1为下一个象素；当d=0时，选P1或P2均可，约定取P1为下一个象素；若当前象素处于d=0情况，则取正右方象素P1(xp+1,yp),要判下一个象素位置，应计算d1=F(xp+2,yp+0.5)=a(xp+2)+b(yp+0.5)=d+a，增量为a。若d0时，则取右上方象素P2(xp+1,yp+1)。要判断再下一象素，则要计算d2=F(xp+2,yp+1.5)=a(xp+2)+b(yp+1.5)+c=d+a+b，增量为a＋b。画线从(x0,y0)开始，d的初值d0=F(x0+1,y0+0.5)=F(x0,y0)+a+0.5b，因F(x0,y0)=0，所以d0=a+0.5b。其中，a=y0-y1,b=x1-x0,c=x0y1-x1y0。voidMidpointLine(intx0，inty0，intx1，inty1，intcolor){inta，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)=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.2.3生成直线的Bresenham算法xiXi+1YiYi+1CDBA原理：假定直线斜率,0k1,起点坐标为(x,y);下一个点亮象素可能是：(x+1,y)或(x+1,y+1)。这可通过d值的大小来确定:d=d+k,当d1时d=d-1;当d=0.5取(x+1,y)，否则取(x+1,y+1)。令e=d-0.5,显然e的初值为-0.5。这样可用e的符号来进行判断。ddddvoidBresenhamline(intx0,inty0,intx1,inty1,intcolor){intx,y,dx,dy；floatk,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(e≥0){y++；e=e-1;}}}程序如下：思考题：如何去除上述程序中的浮点运算、乘除法？voidBresenhamline(intx0,inty0,intx1,inty1,intcolor){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(e≥0){y++;e=e-2*dx}}}程序改进从速度考虑，还有那些可以改进？Bresenham画线算法示例起点终点初始值：dx=7;dy=4;k=4/7e=-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=4,e=1/14讨论象素点的选取是否有规律？有何用直线生成算法的改进如何利用上述算法实现任意直线的绘制？关于线型线宽的说明实线就是将选到所有的点都画出来虚线就是在所选的点中选相邻的几个画，然后接着相邻的几个不画点线就是在所选的点中，每隔几个就画一个线宽只对实线有效，实际上就是根据其倾斜角然后选定是在选中的点的(x+-width/2,y)或者(x,y+-width/2)也画出来，相当于一把近似垂直于直线的刷子关于多边形和圆形的作图多边形确定多边形的顶点用直线顺序连接起来圆形根据圆的对称性将其扩展到四个象限即可获得整圆二、圆的生成算法即是找出逼近圆的一组象素，按扫描线顺序，对这些象素进行写操作。下面仅以圆心在原点的圆为例，讨论圆的生成算法。1.圆弧扫描算法X2+Y2=R2Y=Sqrt(R2-X2)在一定范围内，每给定一X值，可得一Y值。当X取整数时，Y须圆整。缺点：浮点运算，开方，圆整，不均匀。2.角度DDA法x=x0+Rcosy=y0+Rsindx=-Rsinddy=Rcosdxn+1=xn+dxyn+1=yn+dyxn+1=xn-(yn-y0)dyn+1=yn+(xn-x0)d显然，确定x,y的初值及d值后，即可以增量方式获得圆周上的坐标，然后取整可得象素坐标。但要采用浮点运算、乘法运算。3.中点法利用圆的对称性，只须讨论1/8圆。MP1P2P（Xp，Yp）P为当前点亮象素，那么，下一个点亮的象素可能是P1（Xp+1，Yp）或P2（Xp+1，Yp+1)。构造一函数：F（X，Y）=X2+Y2-R2F（X，Y）=0（X，Y）在圆上；F（X，Y）0（X，Y）在圆内；F（X，Y）0（X，Y）在圆外。M为P1、P2间的中点，M=(Xp+1,Yp-0.5)有如下结论：F（M）0取P1F（M）=0取P2为此，可采用如下判别式：d=F(M)=F(xp+1,yp-0.5)=(xp+1)2+(yp-0.5)2-R2若d0,则P1为下一个象素，那么再下一个象素的判别式为：d=F(xp+2,yp-0.5)=(xp+2)2+(yp-0.5)2-R2=d+2xp+3即d的增量为2xp+3.若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-RMidpointCircle(intr){intx,y;floatd;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)=b2x2+a2y2-a2b2=0椭圆的对称性，只考虑第一象限椭圆弧生成，分上下两部分，以切线斜率为-1的点作为分界点。椭圆上一点处的法向：N(x,y)=(F)'xi+(F)'yj=2b2xi+2a2yj在上半部分,法向量的y分量大在下半部分,法向量的x分量大上半部分下半部分法向量两分量相等M1M2在当前中点处，法向量（2b2(Xp+1)，2a2(Yp-0.5))的y分量比x分量大,即：b2(Xp+1)a2(Yp-0.5),而在下一中点，不等式改变方向，则说明椭圆弧从上部分转入下部分椭圆的中点画法与圆弧中点算法类似：确定一个象素后，接着在两个候选象素的中点计算一个判别式的值，由判别式的符号确定更近的点先讨论椭圆弧的上部分设(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的符号来决定下一像素是取正右方的那个，还是右上方的那个。若d1＜0，中点在椭圆内，取正右方象素，判别式更新为：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)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若d20,取右下方像素，则d2'=F(Xp+1.5,Yp-2)=d2+b2(2Xp+2)+a2(-2Yp+3)若d2=0,取正下方像素，则d2'=F(Xp+0.5,Yp-2)=d2+a2(-2Yp+3)下半部分弧的终止条件为y=0程序：voiddraw_Ellipe_Mid(inta,intb){intx,y;float