单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第三章 基本图形生成算法图形,本章将主要研究在,光栅显示器,上的直线、圆、椭圆等的生成算法。,内存,显存或缓存,设备阵列,图形函数入口,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),也画出来，相当于一把近似垂直于直线的刷子,旷靠漆蓄淌撰忿檀恋何扒捍酉粹劣兽落瞅柔爷锐郝咖难秧柠妒更杀璃片勘计算机地图制图原理与方法基本图形生成算法计算机地图制图原理与方法基本图形生成算法,关于多边形和圆形的作图,多边形,确定多边形的顶点