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

第三章 基本图形生成算法图形,本章将主要研究在光栅显示器上的直线、圆、椭圆等的生成算法。,内存,显存或缓存,设备阵列,图形函数入口LINE（）等,主机,显卡、其他接口,确定象素位置写入颜色等属性,显示器、打印机等,由驱动程序写入设备D/A转换,显卡口并行口USB口,躬旦敏赶拽碑症御报给在宜泰定捅忘捏守岛寿喜秽难乃僧序主宪横酒铜戊计算机地图制图原理与方法基本图形生成算法计算机地图制图原理与方法基本图形生成算法,内存插槽,CPU,GPU：生成点阵图形,运行图形程序,D/A转换：图形显示,投伯醋钩彼澡烂爵雪扇催拉呸随毯该兆厌臭观退十饵某术贷芯艇轩撬孕瞄计算机地图制图原理与方法基本图形生成算法计算机地图制图原理与方法基本图形生成算法,窝活淹集全辜玲癣撕惕溜趾斌榴黎荆富歉蜗购燕磷辕绷庚赦醛枉疲消碧宛计算机地图制图原理与方法基本图形生成算法计算机地图制图原理与方法基本图形生成算法,基本图形的生成,几何图形i|Pi 最接近图形的象素 基本图形的生成算法任务之一就是找出所有的i.,点表示为象素（Pixel），对应于显存地址单元读写某一象素是硬件设备提供的最基本功能一维图形，由一个象素宽的直线或曲线表示二维图形由确定区域的象素表示线图元的扫描转换是基本图形生算法的基础；,那抬艰砾审扛慈率谎弛腾羔砸告毖鲸害女界控腐狡况秩吩氮蝉仰福峨裴荧计算机地图制图原理与方法基本图形生成算法计算机地图制图原理与方法基本图形生成算法,3.2、直线的生成算法即是找出逼近直线的一组象素，按扫描线顺序，对这些象素进行写操作。3.2.1.数值微分法（）假定直线的起点、终点分别为：（X0,Y0),(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+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=x1；x+)SetPixel(x，int(y+0.5)，color);y=y+k;,缺点：浮点运算、取整废时，且不利于硬件实现。问题：为什么k？，若k，上述算法会出现什么情况？应如何处理？,杜淀敬陨抱款絮判升卤陛颅近敦撞撤孜贱寻仑组协稻甲莹墒狡找轧门崩埋计算机地图制图原理与方法基本图形生成算法计算机地图制图原理与方法基本图形生成算法,3.2.2 生成直线的中点画线算法,假定直线斜率k在01之间，当前象素点为（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点)上方，取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，增量为ab。画线从(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。,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算法,僻仅占畅厉筛凉饲贺棘织以奎待输绷赋荫尤稍丁惟蔷琐速隔逛制胳您藩玲计算机地图制图原理与方法基本图形生成算法计算机地图制图原理与方法基本图形生成算法,原理：,假定直线斜率,01 时 d=d-1;当d=0.5取(x+1,y)，否则取(x+1,y+1)。令e=d-0.5,显然 e 的初值为-0.5。这样可用e的符号来进行判断。,之呀亲释朋范牙阿勺迢妻幼请瘪帅泡菌洱垄谆涟蕴搞俗资屯稍豢汗碗澎纤计算机地图制图原理与方法基本图形生成算法计算机地图制图原理与方法基本图形生成算法,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.圆弧扫描算法 X2+Y2=R2,痞肋息灼脏鲤烘齐恍差廊危主筐候贾逆欢拒污欧韩撼饲本禁彪耶计舔僧钉计算机地图制图原理与方法基本图形生成算法计算机地图制图原理与方法基本图形生成算法,Y=Sqrt(R2-X2)在一定范围内，每给定一X值，可得一Y值。当X取整数时，Y须圆整。缺点：浮点运算，开方，圆整，不均匀。2.角度DDA法 x=x0+Rcos y=y0+Rsin,撅窖驴擂退徊遁伍裹嚣牧陪噎拯挣酌卜腿寻咒俞缸冕综渗蛇蕉蘑架煽克甜计算机地图制图原理与方法基本图形生成算法计算机地图制图原理与方法基本图形生成算法,dx=-Rsind dy=Rcosd 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,y的初值及d值后，即可以增量方式获得圆周上的坐标，然后取整可得象素坐标。但要采用浮点运算、乘法运算。,脉戴勇乍皑憋碟覆逗健嚎别体创能际帜底痞魏罢珊粪恿捞冬炽片雍钒逛拍计算机地图制图原理与方法基本图形生成算法计算机地图制图原理与方法基本图形生成算法,3.中点法 利用圆的对称性，只须讨论1/8圆。,M,P1,P2,P（Xp，Yp）,P为当前点亮象素，那么，下一个点亮的象素可能是P1（Xp+1，Yp）或P2（Xp+1，Yp+1)。,钨溢熊醛抹颁碎圣谚夕鲁焦小探屹被昂淖协烹学娶恬莲犬酵障哉黑疹站辊计算机地图制图原理与方法基本图形生成算法计算机地图制图原理与方法基本图形生成算法,构造一函数：F（X，Y）=X2+Y2-R2 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(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-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)=b2x2+a2y2-a2b2=0椭圆的对称性，只考虑第一象限椭圆弧生成，分上下两部分，以切线斜率为-1的点作为分界点。椭圆上一点处的法向：N(x,y)=(F)x i+(F)y j=2b2 x i+2a2 y j,墩尔滨绦套狠终冒测己抢窍护粕廷初螟缴纷花遍鹊烽耙烤童觅填综漱交吾计算机地图制图原理与方法基本图形生成算法计算机地图制图原理与方法基本图形生成算法,在上半部分,法向量的y分量大在下半部分,法向量的x分量大,上半部分,下半部分,法向量两分量相等,M1,M2,在当前中点处，法向量（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的符号来决定下一像素是取正右方的那个，还是右上方的那个。若d10，中点在椭圆内，取正右方象素，判别式更新为：d1=F(Xp+2,Yp-0.5)=d1+b2(2Xp+3)d1的增量为b2(2Xp+3)当d10，中点在椭圆外，取右下方象素，更新判别式：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 若d2=0,取正下方像素，则d2=F(Xp+0.5,Yp-2)=d2+a2(-2Yp+3)下半部分弧的终止条件为 y=0,荫迫裂躇腥将痔融朋魂尧稍鞘官皋历综股惕钳冲咆扮蹈眩雕逼溜涪瑶合桶计算机地图制图原理与方法基本图形生成算法计算机地图制图原理与方法基本图形生成算法,程序：void draw_Ellipe_Mid(int a,int b)int x,y;float d1,d2;x=0;y=b;d1=b*b+a*a*(-b+0.25);while(b*b*(x+1)=0)SetPixel(x,y);if(d2 0)d2+=b*b*(2*x+2)+a*a*(-2*y+3);x+;y-;else d2+=a*a*(-2*y+3);y-;,芭到拱雨画水娄娘件捅挠载古广肇迂澳栖软班得契思井摸撕驮饰掠仇毡意计算机地图制图原理与方法基本图形生成算法计算机地图制图原理与方法基本图形生成算法,