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

直线及圆生成算法

光栅图形学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)x0?x10?直线段的宽度为1?直线段的斜率k?[0,1]8

直线生成算法?数值微分法（DDA）?中点画线算法?Bresenham画线算法9

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

数值微分法（DDA）?微分：dy=kdx?实现：dx=？?y=kdx=111

数值微分法（DDA）intx1=…,x2=…,y1=…,y2=…;//Givenintx;floaty=y1,?y=(y2-y1)/(x2-x1);for(x=x1;x?x2;++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)?当d0，M在L(Q点)下方，取右上方P2为下一个象素；?当d=0，M在L(Q点)上方，取右方P1为下一个象素；M18

中点画线算法?若Yp+1=Yp+1?d=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=Yp?d=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