《计算机地图制图原理与方法-基本图形生成算法》由会员分享，可在线阅读，更多相关《计算机地图制图原理与方法-基本图形生成算法（35页珍藏版）》请在金锄头文库上搜索。
1、第三章 基本图形生成算法图形,本章将主要研究在光栅显示器上的直线、圆、椭圆等的生成算法。,内存,显存或缓存,设备阵列,图形函数入口LINE（）等,主机,显卡、其他接口,确定象素位置写入颜色等属性,显示器、打印机等,由驱动程序写入设备D/A转换,显卡口并行口USB口,内存插槽,CPU,GPU：生成点阵图形,运行图形程序,D/A转换：图形显示,基本图形的生成,几何图形i | Pi 最接近图形的象素 基本图形的生成算法任务之一就是找出所有的i .,点表示为象素（Pixel），对应于显存地址单元读写某一象素是硬件设备提供的最基本功能一维图形，由一个象素宽的直线或曲线表示二维图形由确定区域的象素表示线图
2、元的扫描转换是基本图形生算法的基础；,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 =
3、 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
4、-y0； k=dy/dx；y=y0； for (x=x0；x，上述算法会出现什么情况？应如何处理？,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点的上方还是下方，
5、只要把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.
6、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
7、， 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
8、,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；
9、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 ,程序改进,从速度考虑，还有那些可以改进？,Bre
10、senham画线算法示例,起点,终点,初始值：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,讨论象素点的选取是否有规律？有何用,直线生成算法的改进,如何利用上述算法实现任意直线的绘制
11、？,关于线型线宽的说明,实线就是将选到所有的点都画出来虚线就是在所选的点中选相邻的几个画，然后接着相邻的几个不画点线就是在所选的点中，每隔几个就画一个线宽只对实线有效，实际上就是根据其倾斜角然后选定是在选中的点的(x+-width/2, y)或者(x, y+-width/2)也画出来，相当于一把近似垂直于直线的刷子,关于多边形和圆形的作图,多边形确定多边形的顶点用直线顺序连接起来 圆形根据圆的对称性将其扩展到四个象限即可获得整圆,二、圆的生成算法 即是找出逼近圆的一组象素，按扫描线顺序，对这些象素进行写操作。 下面仅以圆心在原点的圆为例，讨论圆的生成算法。1. 圆弧扫描算法 X2 + Y2 =
12、 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
13、,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.,
