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

第三章基本图形生成算法图形本章将主要研究在光栅显示器上的直线、圆、椭圆等的生成算法。内存显存或缓存设备阵列图形函数入口LINE（）等主机显卡、其他接口确定象素位置写入颜色等属性显示器、打印机等由驱动程序写入设备D/A转换显卡口并行口USB口1整理课件内存插槽CPUGPU：生成点阵图形运行图形程序D/A转换：图形显示2整理课件3整理课件基本图形的生成几何图形Ｇ＝｛Ｐi|

Pi最接近图形的象素

｝基本图形的生成算法任务之一就是找出所有的Ｐi.点表示为象素（Pixel），对应于显存地址单元读写某一象素是硬件设备提供的最基本功能一维图形，由一个象素宽的直线或曲线表示二维图形由确定区域的象素表示线图元的扫描转换是基本图形生算法的基础；4整理课件3.2、直线的生成算法

即是找出逼近直线的一组象素，按扫描线顺序，对这些象素进行写操作。3.2.1.数值微分法（ＤＤＡ）

假定直线的起点、终点分别为：（X0,Y0),(X1,Y1)，且都为整数。

(Xi+1,Yi+k)(Xi,Int(Yi+0.5))(Xi,Yi)栅格交点表示象素点位置5整理课件直线的斜率：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+k6整理课件画直线的DDA算法从起点开始朝终点方向画点(x,y)在x轴或y轴上走一个单位长（沿x轴还是y轴取决于直线的倾斜角）由直线的倾斜程度（斜率或斜率的倒数）决定另一坐标的增量，获得下一点的座标将x或y四舍五入，得(x,y)若(x,y)不是终点则继续起点终点未四舍五入前最后选定的点17234560891234567807整理课件voidDDALine(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｜>１，上述算法会出现什么情况？应如何处理？8整理课件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

当d<0时，M在L(Q点)下方，取P2为下一个象素；

当d>0时，M在L(Q点)上方，取P1为下一个象素；

当d=0时，选P1或P2均可，约定取P1为下一个象素；9整理课件若当前象素处于d>=0情况，则取正右方象素P1(xp+1,yp),要判下一个象素位置，应计算d1=F(xp+2,yp+0.5)=a(xp+2)+b(yp+0.5)=d+a，增量为a。

若d<0时，则取右上方象素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(d<0)

{x++；y++；d+=d2;}else

{x++；d+=d1;}}/*while*/}/*midPointLine*/

10整理课件中点画线算法示例起点终点初始值：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=-111整理课件3.2.3生成直线的Bresenham算法xiXi+1YiYi+1CDBA12整理课件原理：假定直线斜率,0<k<1,起点坐标为(x,y);下一个点亮象素可能是：(x+1,y)或(x+1,y+1)。这可通过d值的大小来确定:d=d+k,当d>1时d=d-1;当d<=0.5取(x+1,y)，否则取(x+1,y+1)。令e=d-0.5,显然e的初值为-0.5。这样可用e的符号来进行判断。dddd13整理课件voidBresenhamline(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;}}}程序如下：14整理课件思考题：如何去除上述程序中的浮点运算、乘除法？15整理课件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}}}

程序改进从速度考虑，还有那些可以改进？16整理课件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讨论象素点的选取是否有规律？有何用17整理课件直线生成算法的改进

如何利用上述算法实现任意直线的绘制？18整理课件关于线型线宽的说明实线就是将选到所有的点都画出来虚线就是在所选的点中选相邻的几个画，然后接着相邻的几个不画点线就是在所选的点中，每隔几个就画一个线宽只对实线有效，实际上就是根据其倾斜角然后选定是在选中的点的(x+-width/2,y)或者(x,y+-width/2)也画出来，相当于一把近似垂直于直线的刷子19整理课件关于多边形和圆形的作图多边形确定多边形的顶点用直线顺序连接起来

圆形根据圆的对称性将其扩展到四个象限即可获得整圆

20整理课件二、圆的生成算法

即是找出逼近圆的一组象素，按扫描线顺序，对这些象素进行写操作。

下面仅以圆心在原点的圆为例，讨论圆的生成算法。1.圆弧扫描算法X2+Y2=R221整理课件Y=Sqrt(R2-X2)在一定范围内，每给定一X值，可得一Y值。当X取整数时，Y须圆整。缺点：浮点运算，开方，圆整，不均匀。2.角度DDA法x=x0+Rcosy=y0+Rsin22整理课件dx=-Rsinddy=Rcosdxn+1=xn+dxyn+1=yn+dyxn+1=xn-(yn-y0)d

yn+1=yn+(xn-x0)d

显然，确定x,y的初值及d

值后，即可以增量方式获得圆周上的坐标，然后取整可得象素坐标。但要采用浮点运算、乘法运算。23整理课件3.中点法利用圆的对称性，只须讨论1/8圆。MP1P2P（Xp，Yp）P为当前点亮象素，那么，下一个点亮的象素可能是P1（Xp+1，Yp）或P2（Xp+1，Yp+1)。24整理课件

构造一函数：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为此，可采用如下判别式：

25整理课件d=F(M)=F(xp+1,yp-0.5)=(xp+1)2+(yp-0.5)2-R2

若d<0,则P1为下一个象素，那么再下一个象素的判别式为：

d=F(xp+2,yp-0.5)=(xp+2)2+(yp-0.5)2-R2

=d+2xp+3即d的增量为2xp+3.26整理课件若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-R27整理课件MidpointCircle(intr){intx,y;floatd;x=0;y=r;d=1.25-r;while(x<y){setpixel(x,y); if(d<0){d+=2*x+3;x++}else{d+=2*(x-y)+5;x++;y--;}}}该程序如何改进，提高效率？28整理课件Bresenham画圆算法讨论、圆的中点算法与Bresenham算法是否一致？29整理课件椭圆的生成算法F(x,y)=b2x2+a2y2-a2b2=0椭圆的对称性，只考虑第一象限椭圆弧生成，分上下两部分，以切线斜率为-1的点作为分界点。椭圆上一点处的法向： N(x,y)=(F)'xi+(F)'yj =2b2xi+2a2yj30整理课件在上半部分,法向量的y分量大在下半部分,法向量的x分量大上半部分下半部分法向量两分量相等M1M2在当前中点处，法向量（2b2(Xp+1)，2a2(Yp-0.5))的y分量比x分量大,即： b2(Xp+1)<a2(Yp-0.5),而在下一中点，不等式改变方向，则说明椭圆弧从上部分转入下部分31整理课件椭圆的中点画法与圆弧中点算法类似：确定一个象素后，接着在两个候选象素的中点计算一个判别式的值，由判别式的符号确定更近的点先讨论椭圆弧的上部分 设(Xp，Yp)已确定，则下一待选像素的中点是(Xp+1,Yp-0.5) d1=F(Xp+1,Yp-0.5)=b2(Xp+1)2+a2(Yp-0.5)2-a2b232整理课件根据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)33