计算机图形生成算法(线).ppt

计算机图形生成算法,内容：目标：掌握二维图形学的基本思想，理解扫描转换法生成图形的基本原理。要求：掌握图形的扫描转换、区域填充、裁剪、反走样等概念。掌握直线段的扫描转换算法、区域填充的扫描线算法、多边形裁剪算法、反走样的基本思想。熟悉多边形的扫描转换算法、区域采样的基本思想。了解圆弧的扫描转换算法、字符的基本概念。,第三章输出图元,直线段扫描转换DDA算法Bresenham画线算法中点画线法圆弧扫描转换Bresenham画圆算法中点画圆算法椭圆弧扫描转换填充区域图元,输出图元,输出图元是基本几何结构。输出图元种类：点、直线线段、圆、圆锥曲线、二次曲面、样条线段、多边形填色区域、字符串等。,图元的生成,所谓图元的生成，是指完成图元的参数表示形式（由图形软件包的使用者指定）到点阵表示形式（光栅显示系统刷新时所需的表示形式）的转换。通常也称扫描转换图元。,光栅化,像素逼近示意图,可寻址点,即显示器可以找到的点，（x，y）整数地址,一个象素，占有一定面积,3.1直线的扫描转换算法,直线的绘制要求：1.直线要直2.直线上的点要准确，即无不定向性和断裂情况3.直线的亮度、色泽要均匀4.画线的速度要快5.要求不同直线可具有不同的色泽、亮度、线型等,直线的扫描转换算法,提出问题：对于给定直线两端点P0(x0,y0)和P1(x1,y1)，如何在屏幕上画出该直线。三个常用算法：数值微分法（DDA）Bresenham算法中点画线法,=yi+m*x,yi=mxi+B,yi+1=mxi+1+B,=m(xi+x)+B,3.1.1DDA算法(DigitalDifferentialAlgorithm),通过同时对x,y各增加一个小的增量,计算下一步的x,y值。在一个迭代算法中,如果每一步的x,y值是用前一步的值加上一个增量来获得,那么这种算法称为增量算法。,光栅中x=1,直线的递推公式,如果x2x10,y2y10,讨论:,xi+1=xi+1yi+1=yi+k,因而造成隔行显示,解决办法:,将y看作自变量,结论：第一象限的直线DDA算法：,起点（x1,y1），终点（x2,y2）(x2x1,y2y1),以（x1,y1）为起点,DDA算法的优、缺点,DDA算法的本质:,效率低,不利于硬件实现,直观可行,DDA算法也是一个增量算法。,缺陷:,做除法;,须采用浮点数据计算,要取整数-算法效率不高,算法程序实现,k=abs(x2-x1);,if(abs(y2-y1)k),doubledeltx=(x2-x1)/k;,doubledelty=(y2-y1)/k;,for(inti=0;i=0,d2=d1+2(dy-dx)12*(4-5)=-1=0,点亮点（4，3）,d4=d3+2(dy-dx)52*(4-5)=3=0,点亮点（5，4）,一个完整的直线算法应考虑以下几个方面,1.水平线,2.垂直线,4.直线的斜率为m,|m|1,5.|m|1,6.yy1)s2=1;elses2=-1;if(dydx)tmp=dx;dx=dy;dy=tmp;inter=1;elseinter=-1;d=2*dy-dx;const1=2*dy;/*注意此时误差的*/const2=2*(dy-dx);/*变化参数取值.*/x=x1;y=y1;setpixel(x,y,c);for(i=1;i=0)y+=s2;x+=s1;d+=const2;elseif(inter=1)y+=s2;elsex+=s1;d+=const2;setpiexl(x,y,c);,生成直线算法的进一步改进,1987年有人提出二步法，即没循环一次不是绘制一个象素，而是绘制二个象素，这样无疑可以把生成直线的速度提高一倍。,只可能出现的四种情况,同样，我们先考虑当直线的斜率m属于区间0，1时，在x方向每增加两个单元,2.1.3中点画线法,基本思想当前象素点为(xp,yp)。下一个象素点为P1或P2。设M=(xp+1,yp+0.5)，为p1与p2之中点，Q为理想直线与x=xp+1垂线的交点。将Q与M的y坐标进行比较。当M在Q的下方，则P2应为下一个象素点；M在Q的上方，应取P1为下一点。,构造判别式:d=F(M)=F(xp+1,yp+0.5)=a(xp+1)+b(yp+0.5)+c其中a=y0-y1,b=x1-x0,c=x0y1-x1y0当d0，M在L(Q点)上方，取右方P1为下一个象素；当d=0，选P1或P2均可，约定取P1为下一个象素；d是xp,yp的线性函数，因此可采用增量计算，提高运算效率。,若当前象素处于d0情况，则取正右方象素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=a+0.5b。可以用2d代替d来摆脱小数，提高效率。令d0=2a+b,d1=2a,d2=2a+2b,我们有如下算法。,例：用中点画线法P0（0,0)P1（5,2)a=y0-y1=-2,b=x1-x0=5d0=2a+b=1,d1=2a=-4,d2=2(a+b)=6ixiyid1001210-33213431-15425,voidMidpointLine(intx0,inty0,intx1,inty1,intcolor)inta,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;setpixel(x,y,color);while(xx1)if(d0)x+,y+,d+=d2;elsex+,d+=d1;setpixel(x,y,color);/*while*/*midPointLine*/,齐次坐标（HomogeneousCoordinate）在空间直角坐标系中，任意一点可用一个三维坐标矩阵xyz表示。如果将该点用一个四维坐标的矩阵HxHyHzH表示时，则称为齐次坐标表示方法。在齐次坐标中，最后一维坐标H称为比例因子。在OpenGL中，二维坐标点全看作三维坐标点，所有的点都用齐次坐标来描述，统一作为三维齐次点来处理。每个齐次点用一个向量(x,y,z,w)表示，其中四个元素全不为零。齐次点具有下列几个性质：1）如果实数a非零，则(x,y,x,w)和(ax,ay,az,aw)表示同一个点，类似于x/y=(ax)/(ay)。2）三维空间点(x,y,z)的齐次点坐标为(x,y,z,1.0)，二维平面点(x,y)的齐次坐标为(x,y,0.0,1.0)。3）当w不为零时，齐次点坐标(x,y,z,w)即三维空间点坐标(x/w,y/w,z/w)；当w为零时，齐次点(x,y,z,0.0)表示此点位于某方向的无穷远处。注意：OpenGL中指定w大于或等于0.0。,OpenGL建模-描述图元,点(Point)用浮点值表示的点称为顶点（Vertex）。所有顶点在OpenGL内部计算时都作为三维点处理，用二维坐标(x,y)定义的点在OpenGL中默认z值为0。所有顶点坐标用齐次坐标(x,y,z,w)表示，如果w不为0.0，这些齐次坐标表示的顶点即为三维空间点(x/w,y/w,z/w)。编程者可以自己指定w值，但很少这样做。一般来说，w缺省为1.0。,OpenGL建模-描述图元,线(Line):在OpenGL中，线代表线段（LineSegment），不是数学意义上的那种沿轴两个方向无限延伸的线。这里的线由一系列顶点顺次连结而成，有闭合和不闭合两种。见图。,OpenGL建模-描述图元,多边形(Polygon):OpenGL中定义的多边形是由一系列线段依次连结而成的封闭区域。这些线段不能交叉，区域内不能有空洞，多边形必须为凸多边形，否则不能被OpenGL函数接受。合法和非法多边形图示见图,OpenGL建模-描述图元,定义顶点：在OpenGL中，所有几何物体最终都由有一定顺序的顶点集来描述。函数glVertex234sifdv(TYPEcoords)可以用二维、三维或齐次坐标定义顶点。举例如下：glVertex2s(2,3);glVertex3d(0.0,1.0,3.1414926535);glVertex4f(2.4,1.0,-2.2,2.0);GLfloatpp3=5.0,2.0,10.2;glVertex3fv(pp);第一例子表示一个空间顶点(2,3,0)，第二个例子表示用双精度浮点数定义一个顶点，第三个例子表示用齐次坐标定义一个顶点，其真实坐标为(1.2,0.5,-1.1)，最后一个例子表示用一个指针（或数组）定义顶点。,OpenGL建模-绘制图元,构造几何图元在实际应用中，通常用一组相关的顶点序列以一定的方式组织起来定义某个几何图元，而不采用单独定义多个顶点来构造几何图元。在OpenGL中，所有被定义的顶点必须放在glBegain()和glEnd()两个函数之间才能正确表达一个几何图元或物体，否则，glVertex*()不完成任何操作。如：glBegin(GL_POLYGON);glVertex2f(0.0,0.0);glVertex2f(0.0,3.0);glVertex2f(3.0,3.0);glVertex2f(4.0,1.5);glVertex2f(3.0,0.0);glEnd();以上这段程序定义了一个多边形，如果将glBegin()中的参数GL_POLYGON改为GL_POINTS，则图形变为一组顶点（5个），见图所示。,OpenGL建模-描述图元,OpenGL建模-绘制图元,点函数glBegin(GLenummode)标志描述一个几何图元的顶点列表的开始，其参数mode表示几何图元的描述类型。所有类型及说明见表7-1所示，相应的图示见图；函数glEnd()标志顶点列表的结束,OpenGL建模-绘制图元,在glBegin()和glEnd()之间最重要的信息就是由函数glVertex*()定义的顶点，必要时也可为每个顶点指定颜色、法向、纹理坐标或其他，即调用相关的函数，见表7-2所示,glBegin(GL_POINTS);g