计算机图形生成算法线

1、计算机图形生成算法内容：目标：掌握二维图形学的基本思想，理解扫描转换法生成图形的基本原理。要求：掌握图形的扫描转换、区域填充、裁剪、反走样等概念。掌握直线段的扫描转换算法、区域填充的扫描线算法、多边形裁剪算法、反走样的基本思想。熟悉多边形的扫描转换算法、区域采样的基本思想。了解圆弧的扫描转换算法、字符的基本概念。1第三章 输出图元直线段扫描转换DDA算法Bresenham画线算法中点画线法圆弧扫描转换Bresenham画圆算法中点画圆算法椭圆弧扫描转换填充区域图元2输出图元输出图元是基本几何结构。输出图元种类：点、直线线段、圆、圆锥曲线、二次曲面、样条线段、多边形填色区域、字符串等。3图元的生

2、成所谓图元的生成，是指完成图元的参数表示形式（由图形软件包的使用者指定）到点阵表示形式（光栅显示系统刷新时所需的表示形式）的转换。通常也称扫描转换图元。 扫描转换顶点（参数）表示的图形用户点阵表示的图形光栅显示系统光栅化4像素逼近示意图可寻址点,即显示器可以找到的点，（x，y）整数地址一个象素，占有一定面积53.1 直线的扫描转换算法直线的绘制要求：1.直线要直2.直线上的点要准确，即无不定向性和断裂情况3.直线的亮度、色泽要均匀4.画线的速度要快5.要求不同直线可具有不同的色泽、亮度、线型等6直线的扫描转换算法提出问题：对于给定直线两端点P0(x0,y0)和P1(x1,y1)，如何在屏幕上画

3、出该直线。三个常用算法：数值微分法（DDA）Bresenham算法中点画线法7已知端点A(x1, y1)、B(x2, y2),直线的微分方程：dy/dx=(y2-y1)/(x2-x1)=常数=m yi+1yi+ (y2-y1)/(x2-x1)*x= yi + m* x yi =m xi + Byi+1 = m xi +1 + B = m (xi + x ) +B A(x1,y1)B(x2,y2)Pi(xi,yi)Pi+1(xi+1,yi+1)dy=kdxdx3.1.1DDA算法(Digital Differential Algorithm)通过同时对x,y各增加一个小的增量,计算下一步的x,y

4、值。在一个迭代算法中,如果每一步的x,y值是用前一步的值加上一个增量来获得,那么这种算法称为增量算法。8光栅中 x=1直线的递推公式 yi+1yi+ (y2-y1)/(x2-x1)xi+1xi+1double x=x1, y=y1;m=(y2-y1)/(x2-x1);int k=abs(x2-x1);for( int i=0; ix10, y2y109oxyk1讨论:oxyk1(xi+1,round(yi+1)）xi+1=xi+1yi+1=yi+kk x1, y2 y1)以（x1, y1）为起点11DDA算法的优、缺点 DDA算法的本质:效率低,不利于硬件实现 直观可行 DDA算法也是一个增量

5、算法。缺陷:做除法;须采用浮点数据计算要取整数-算法效率不高算法程序实现k=abs(x2-x1);if(abs(y2-y1)k)double deltx=(x2-x1)/k;double delty=(y2-y1)/k;for(int i=0;i=k;i+)x+=deltx;/x=x+deltx;y+=delty;/y=y+delty;k=abs(y2-y1);setpixel(int)x,(int)y,2);用数值方法解微分方程(数值微分法)x=x1; y=y1;121.问题的提出 2.基本思想 a.效率的意义b.希望找到一个简单的判决条件,迅速确定直线上的点。借助于一个决策变量 d的正负符

6、号 ,来确定下一个该点亮的象素点。最逼近Pi+1点的象素点是Ti+1点还是Si+1点？由ti+1与si+1二者的相对大小决定。若ti+1si+1, 则取Si点(xi+1,yi)ti+1与si+1二者的大小可以由si+1 - ti+1的正负来判定。stTiSi(r,q)3.1.2直线的Bresenham算法13为讨论方便, 假定:直线斜率k在 0,1 之 间起点坐标 A(x1,y1)终点坐标 B(x2,y2)将直线平移到原点则起点坐标（0，0),终点坐标B(dx,dy)dx=x2-x1dy=y2-y1其中直线方程为：且其中r=xi-1,q=yi-1stTiSi(r,q)所以定义di=dx(s-t

7、)为决策变量14经推导 di+1=di+2dy-2dx*(yi-yi-1 )如果1) 当di0，即s-t0,st,则点亮Ti，2) 当di0，即s-t0,s=0点亮点（1，1）点亮点（2，1）d3= d2+2dy-12*4=7=0d2= d1+2(dy-dx)12*(4-5)=-1=0点亮点（4，3）d4= d3+2(dy-dx)52*(4-5)=3=0点亮点（5，4）举例:从点A(0,0)到B(5,4)画一直线.di0di0yi=yi-1+1;xi=xi-1+1;yi=yi-1;xi=xi-1+1;16一个完整的直线算法应考虑以下几个方面1. 水平线2. 垂直线4. 直线的斜率为m,|m|1

8、5. |m|16. y07. x yInter=0d=2(x*dx-y*dy)+2*dy-dxi=1;setpixel(x,y,color)d0YNYNd0 x=x+s1 y=y+s2d=d+2(dy-dx)inter=1x=x+s1d=d+2*dyy=y+s2i=i+1YYNN18void line (int x1, int y1, int x2, int y2, int c) /* 参数c为直线的颜色*/ int dx,dy,x,y,d,const1,const2,tmp; int s1,s2,inter; dx=abs(x2-x1);dy=abs(y2-y1); if (x2x1) s1

9、=1;else s1=-1; if(y2y1) s2=1;else s2=-1; if (dydx) tmp=dx;dx=dy;dy=tmp;inter=1; else inter=-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; else if(inter=1) y+=s2;else x+=s1; d+=const2; setpiexl(x, y, c); 19生成

10、直线算法的进一步改进1987年有人提出二步法，即没循环一次不是绘制一个象素，而是绘制二个象素，这样无疑可以把生成直线的速度提高一倍。只可能出现的四种情况ABCD同样，我们先考虑当直线的斜率m属于区间0，1时，在x方向每增加两个单元202.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为下一点。21构造判别式:d=F(M)=F(xp+1,yp+0.5) =a(xp+1)+b(

11、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的线性函数，因此可采用增量计算，提高运算效率。22若当前象素处于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=

12、d+a+b ；增量为ab23画线从(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,我们有如下算法 。24例：用中点画线法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-1542525void Midpoint Line (int x0,int y0,int x1, int

13、 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; setpixel(x, y, color); while (xx1) if (d0) x+, y+, d+=d2; else x+, d+=d1; setpixel (x, y, color); /* while */ /* mid PointLine */26齐次坐标（Homogeneous Coordinate） 在空间直角坐标系中，任意一点可用一个三维坐标矩阵x y z表示。如果将该点用

14、一个四维坐标的矩阵Hx Hy Hz H表示时，则称为齐次坐标表示方法。在齐次坐标中，最后一维坐标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不为零时

15、，齐次点坐标(x, y, z, w)即三维空间点坐标(x/w, y/w, z/w)；当w为零时，齐次点(x, y, z, 0.0)表示此点位于某方向的无穷远处。注意：OpenGL中指定w大于或等于0.0。 OpenGL建模-描述图元27点(Point) 用浮点值表示的点称为顶点（Vertex）。所有顶点在OpenGL内部计算时都作为三维点处理，用二维坐标(x, y)定义的点在OpenGL中默认z值为0。所有顶点坐标用齐次坐标(x, y, z, w) 表示，如果w不为0.0，这些齐次坐标表示的顶点即为三维空间点(x/w, y/w, z/w)。编程者可以自己指定w值，但很少这样做。一般来说，w缺省

16、为1.0。 OpenGL建模-描述图元28线(Line) :在OpenGL中，线代表线段（Line Segment），不是数学意义上的那种沿轴两个方向无限延伸的线。这里的线由一系列顶点顺次连结而成，有闭合和不闭合两种。见图。 OpenGL建模-描述图元29 多边形(Polygon) :OpenGL中定义的多边形是由一系列线段依次连结而成的封 闭区域。这些线段不能交叉，区域内不能有空洞，多边形必须为凸多边形，否则不能被OpenGL函数接受。合法和非法多边形图示见图 OpenGL建模-描述图元30定义顶点 ：在OpenGL中，所有几何物体最终都由有一定顺序的顶点集来描述。函数glVertex234

17、sifdv(TYPE coords)可以用二维、三维或齐次坐标定义顶点。举例如下：glVertex2s(2,3);glVertex3d(0.0,1.0,3.1414926535);glVertex4f(2.4,1.0,-2.2,2.0);GLfloat pp3=5.0,2.0,10.2;glVertex3fv(pp);第一例子表示一个空间顶点(2, 3, 0)，第二个例子表示用双精度浮点数定义一个顶点，第三个例子表示用齐次坐标定义一个顶点，其真实坐标为(1.2, 0.5, -1.1)，最后一个例子表示用一个指针（或数组）定义顶点。 OpenGL建模-绘制图元31构造几何图元在实际应用中，通常用

18、一组相关的顶点序列以一定的方式组织起来定义某个几何图元，而不采用单独定义多个顶点来构造几何图元。在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建模-描述图元32OpenGL建模-绘制图元点函数glBegin(GLenum mode)标志描述一个几何图元的顶点列表的开始，其参数mode表示几何图元的描述类型。所有类型及说明见表7-1所示，相应的图示见图 ；函数glEnd()标志顶点列表的结束 33OpenGL建模-绘制图元在glBegin()和glEnd()之间最重要的信息就是由函数glVertex*()定义