计算机图形学课件第2讲直线及圆生成算法

直线及圆生成算法光栅图形学DisplayFrameVideoMonitorprocessorbufferController2光栅图形学x012...012...y3光栅图形学4二维图形的显示

是指完成图元的参数表示形式到点阵表示形式的转换。通常也称扫描转换图元(ScanConversion)

参数表示形式由图形软件包的开发者指定

点阵表示形式是光栅显示系统刷新时所需的表示形式参数:p0,p1点图示法区域图示法5二维图形的显示

像素操作函数（画像素和读像素）

最基本的绘图函数

画（写）像素:SetPixel(x,y,color)

读像素:GetPixel(x,y,*pixel)

注意：(1)具体的语言环境使用的函数名可能不同，这里的函数名仅用于课堂教学坐标原点(2)屏幕坐标系统（GDI默认）为了方便表Y示，课堂上使用常用坐标系统。XOOpenGL中的课堂采用坐标系统可变化。6二维图元的显示用OpenGL实现读/写像素函数voidSetPixel(GLintx,GLinty,GLubyter,GLubyteg,GLubyteb){glColor3ub(r,g,b);glBegin(GL_POINTS)glVertex2i(x,y);glEnd();}GLubyte*GetPixel(GLintx,GLinty){GLubyte*rgb=newGLubyte[3];glReadPixels(x,y,1,1,GL_RGB,GL_UNSIGNED_BYTE,rgb);returnrgb;}7扫描转换直线

扫描转换直线

求与直线段充分接近的像素集，并以此像素集替代原连续直线段在屏幕上显示

约束

像素间均匀网格

整型坐标系

几点假设P1

直线段为：PP0(x0,y0),P1(x1,y1)x0x10

直线段的宽度为1

直线段的斜率k[0,1]8直线生成算法

数值微分法（DDA）

中点画线算法

Bresenham画线算法9数值微分法（DDA）

算法实质：用数值方法微分方程，同时对x和y各增加一个小增量来计算下一步的x,y值。已知过端点P0(x0,y0),P1(x1,y1)的直线段L：y=kx+b直线斜率为：y1y0x1x0k10数值微分法（DDA）

微分：dy=kdx

实现：dx=？

y=kdx=111数值微分法（DDA）intx1=…,x2=…,y1=…,y2=…;//Givenintx;floaty=y1,y=(y2-y1)/(x2-x1);for(x=x1;xx2;++x){setPixel(x,round(y));y=y+y;}13中点画线算法假设x坐标为xp的各像素点中，与直线最近者已确定为P(xp,yp)，那么，下一个与直线最近的像素只能是正右方的P1(xp+1,yp)，或右上方的P2(xp+1,yp+1)两者之一。问题：P1orP2?M15中点画线算法

令M为P1和P2的中点，易知M的坐标为(xp+1,yp+0.5)。设Q是理想直线与垂直线x=xp+1的交点。显然，若M在Q的下方，则P2离直线近，应取为下一个像素；否则应P1。16中点画线算法

问题：判断距离理想直线最近的下一个像素点

已知：线段两端点(x0,y0)，(x1,y1)

直线方程：F(x,y)=ax+by+c=0

a=y0-y1

b=x1-x0

c=x0y1-x1y0P2QM

F(x,y)=0点位于直线上F(x,y)>0点在直线上方F(x,y)<0点在直线下方P=(xp,yp)P1

判断交点Q在中点M的上方还是下方，只要把M的坐标代入F(x,y)中，并判断F(x,y)的符号17中点画线算法

中点？

构造判别式：d=F(M)=F(Xp+1,Y

由d＞0，d＜0可判定下一个象素p+0.5)

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

当d>=0，M在L(Q点)上方，取右方P1为下一个象素；M18中点画线算法

若Yp+1=Yp+1d=F(Xp+2,Yp+1+0.5)-F(Xp+1,Yp+0.5)=a(Xp+2)+b(Yp+1+0.5)+c-a(Xp+1)+b(Yp+0.5)+c=a+b

若Yp+1=Ypd=F(Xp+2,Yp+1+0.5)-F(Xp+1,Yp+0.5)=a(Xp+2)+b(Yp+0.5)+c-a(Xp+1)+b(Yp+0.5)+c=a20中点画线算法

增量算法intx1=…,x2=…,y1=…,y2=…;//Givenintx;floaty=y1,d=0.5*b;floatd1=a+b,d2=a;for(x=x1;xx2;++x){setPixel(x,y);if(d<0){y=y+1.0;d=d+d2;}else{d=y+d1;}只有加法浮点运算}21中点画线算法

增量算法intx1=…,x2=…,y1=…,y2=…;//Givenintx;inty=y1,d=b;intd1=(a+b)<<1,d2=a<<1;for(x=x1;xx2;++x){if(d<0){d02abdi2adi0y=y+1;d=d+d2;di1

}else{di2a2bdi0yidi0yi1di0d=y+d1;}setPixel(x,y);yi1

}xi1xi122中点画线算法例：利用中点画线算法绘制一条直线：两端点分别为P0(0,0)、P1(5,2)。解：首先计算斜率k=0.4,因为斜率k小于1，故适用推导。a=y0-y1=-2,b=x1-x0=5,d0=b=5d1=2a=-4,d2=2(a+b)=6首先绘制初始点(0,0)，并确定沿线路径的其余像素位置为：x012345y0011222d1-33-15123中点画线算法优点：

只有整数运算，不含乘除法

适于硬件实现24Bresenham画线算法

使用最广泛

与中点画线法的思想类似

由误差项符号决定下一个象素取正右方像素还是右上方像素25Bresenham画线算法

工作原理：

过各行各列像素中心构造一组虚拟网格线，按直线从起点到终点的顺序计算直线与各垂直网格线的交点，然后确定该列像素中与此交点最近的像素。26Bresenham画线算法

如何确定d

增量算法

设初始d=0

di+1=y(x+1)-yi+1=k

y(x)=kx+b

yi+1=yi

若d>=0.5

yi+1=yi+1

更新d=d-1

若d<0.5

yi+1=yi+127Bresenham画线算法例：利用Bresenham画线算法，绘制一条端点为P0(0,0)和P1(5,2)的直线。解：首先计算斜率k=0.4,d=0首先绘制初始点(0,0)，并确定沿线路径的其余像素位置为：x12345y01122d0.4-0.20.2-0.4028Bresenham画线算法intx1=…,x2=…,y1=…,y2=…;//Givenintx,y=y1;intdx=x2–x1,dy=y2–y1;floaterror=0.0for(x=x1;xx2;++x){setPixel(x,y);error=error+dy;if(error>=0.5*dx){++y;error=error-dx;}}29Bresenham画线算法intx1=…,x2=…,y1=…,y2=…;//Givenintx,y=y1,floaterror=0.0,y=(y2-y1)/(x2-x1);for(x=x1;xx2;++x){setPixel(x,y);error=error+y;if(error>=0.5){++y;error=error-1.0;}}与DDA极为相似30Bresenham画线算法intx1=…,x2=…,y1=…,y2=…;//Givenintx,y=y1,floaterror=0.0,y=(y2-y1)/(x2-x1);for(x=x1;xx2;++x){setPixel(x,y);error=error+y;if(error>=0.5){++y;error=error-1.0;}}只有加法浮点运算32斜率的问题

当斜率k>1,DDA,Bresenham算法：34斜率的问题

规则化：x每增加1，y最多增加1

交换x←→y,x0←→x0,y0←→y1区域|dx|>|dy|?xy1a1b2a2b3a3b4a4bTrue1k1k12b1bFalse1/k2a1aTrue-13a4aFalse-1/k3b4bTrue-1-k-1-k-1False-1/kTrue1False1/k35直线算法在GIS中的应用

栅矢转换36直线算法在GIS中的应用

空间分析（三维地形上的通视分析）P1P2DEM37扫描转换圆弧

处理对象：圆心在原点的圆弧

其它情况如何考虑?平移到原点，扫描转换后再平移到原位置

圆的八对称性

只需要扫描转换八分之一圆弧即可38扫描转换圆弧

两种直接计算方法

离散点利用隐函数方程x2y2R2(xi,yiR2xi2)取整（xi，yi,r)

离散角度xRcosyRsin利用参数方程(round(Rcosi),round(Rsini))

缺点：开平方，三角函数运算，计算量大，不可取40圆的生成算法

中点画圆算法

Bresenham画圆算法41中点画圆法

假设中心在原点，半径为整数R的圆的1b区域的1/8圆部分，如何从x=0到x=y顺时针确定离理想圆弧最近的像素集合假设x坐标为xp的各像素点中，与该圆弧最近者已确定，为P（xp,yp），那么，下一个与圆弧最近的像素只能是正右方的P1(xp+1,yp)，或右下方的P2(xp+1,yp-1)两者之一。42中点画圆法

令M为P1和P2的中点，易知M的坐标为（xp+1,yp-0.5）。显然，若M在圆内，则P1离圆弧近，应取为下一个像素；否则应取P2。

F(x,y)=x2+y2-R2=0

将M点的坐标（xp+1,yp-0.5）代入圆方程，得到判别式d：d=F(M)=F(xp+1,yp-0.5)=(xp+1)2+(yp-0.5)2–R243中点画圆法

可知：d≥0点在圆外应取P2作为下一个像素d<0点在圆内应取P1作为下一个像素

d的增量表达：

在d≥0的情况下，取右下方像素P2，而且再下一个象素的判别式为：d'=F