《计算机图形生成算法(线)》由会员分享，可在线阅读，更多相关《计算机图形生成算法(线)（34页珍藏版）》请在金锄头文库上搜索。
1、计算机图形生成算法内容： 目标：掌握二维图形学的基本思想，理解 扫描转换法生成图形的基本原理。 要求：掌握图形的扫描转换、区域填充、 裁剪、反走样等概念。 掌握直线段的扫描转换算法、区域填充的扫 描线算法、多边形裁剪算法、反走样的基本思想。 熟悉多边形的扫描转换算法、区域采样的基 本思想。 了解圆弧的扫描转换算法、字符的基本概念 。第三章 输出图元直线段扫描转换 DDA算法 Bresenham画线算法 中点画线法 圆弧扫描转换 Bresenham画圆算法 中点画圆算法 椭圆弧扫描转换 填充区域图元输出图元 输出图元是基本几何结构。 输出图元种类：点、直线线段、圆、圆锥 曲线、二次曲面、样条线段
2、、多边形填色区 域、字符串等。图元的生成 所谓图元的生成，是指完成图元的参 数表示形式（由图形软件包的使用者指定） 到点阵表示形式（光栅显示系统刷新时所需 的表示形式）的转换。通常也称扫描转换图 元。 扫描转换顶点（参数） 表示的图形用户点阵表示 的图形光栅显示系统光栅化像素逼近示意图可寻址点,即显示器可以找到的点，（x ，y）整数地址一个象素，占 有一定面积3.1 直线的扫描转换算法直线的绘制要求： 1.直线要直 2.直线上的点要准确，即无不定向性和断 裂情况 3.直线的亮度、色泽要均匀 4.画线的速度要快 5.要求不同直线可具有不同的色泽、亮度 、线型等直线的扫描转换算法 提出问题：对于给
3、定直线两端点P0(x0,y0) 和P1(x1,y1)，如何在屏幕上画出该直线。 三个常用算法： 数值微分法（DDA） Bresenham算法 中点画线法已知端点A(x1, y1)、 B(x2, y2),直线的微分方程： dy/dx=(y2-y1)/(x2-x1)=常数=myi+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.1 DDA算法(Digital Differenti
4、al Algorithm)通过同时对x,y各增加一个小的增量,计算下一步的x,y值。在一个 迭代算法中,如果每一步的x,y值是用前一步的值加上一个增量来获得, 那么这种算法称为增量算法。光栅中 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, y2y10oxyk1 讨论:oxyk1(xi+1,round(yi+1)）xi+1=xi+1 yi+1=yi+kk x1, y2 y1)以（x1, y1）为起点DDA算法的优
5、、缺点 DDA算法的本质:效率低,不利于硬件实现 直观可行 DDA算法也是一个增量算法 。缺陷: 做除法;须采用浮点数据计算要取整数-算法效率不高算法程序实现 k=abs(x2-x1);if(abs(y2-y1)k)double deltx=(x2-x1)/k; double delty=(y2-y1)/k; for(int i=0;isi+1, 则取Si点(xi+1,yi)ti+1与si+1二者的大小可以由si+1 - ti+1的正负来判定。stTiSi(r,q)3.1.2 直线的Bresenham算法为讨论方便, 假定:直线斜率k在 0,1 之 间起点坐标 A(x1,y1)终点坐标 B(x
6、2,y2)将直线平移到原点 则起点坐标（0，0),终点坐标B(dx,dy) dx=x2-x1dy=y2-y1其中直线方程为：且其中r=xi-1,q=yi-1stTiSi(r,q)所以定义di=dx(s-t)为决策变量经推导 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)
7、到B(5,4)画一直线.di0di0yi=yi-1+1;xi=xi-1+1;yi=yi-1;xi=xi-1+1;一个完整的直线算法应考虑以下几个方面1. 水平线 2. 垂直线4. 直线的斜率为m,|m|1 5. |m| yInter=0d=2(x*dx-y*dy)+2*dy-dx i=1;setpixel(x,y,color)d0YNYNd0x=x+s1y=y+s2 d=d+2(dy-dx)inter=1x=x+s1d=d+2*dyy=y+s2i=i+1YYNNvoid line (int x1, int y1, int x2, int y2, int c) /* 参数c为直线的颜色*/ in
8、t dx,dy,x,y,d,const1,const2,tmp;int s1,s2,inter;dx=abs(x2-x1);dy=abs(y2-y1);if (x2x1) s1=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+
9、=const2;else if(inter=1) y+=s2;else x+=s1;d+=const2;setpiexl(x, y, c); 生成直线算法的进一步改进1987年有人提出二步法，即没循环一次不是绘制一个象素，而 是绘制二个象素，这样无疑可以把生成直线的速度提高一倍。只可能出现的四种情况ABCD同样，我们先考虑当直线的斜率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坐标进 行比较。
10、当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时，则
11、取右上方象素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 = 5 d0 = 2a+b = 1, d1= 2a = - 4, d2 = 2(a+b)=6 ix
12、iyid 1001 210-3 3213 431-15425void Midpoint Line (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;setpixel(x, y, color);while (xx1) if (d0) x+, y+, d+=d2; else x+, d+=d1;setpixel (x, y, color); /* while */ /* mid PointLine */
13、 齐次坐标（Homogeneous Coordinate） 在空间直角坐标系中，任意一点可用一个三维坐标矩 阵x y z表示。如果将该点用一个四维坐标的矩阵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）三维空
14、间点(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。 OpenGLOpenGL建模建模- -描述图元描述图元 点(Point) 用浮点值表示的点称为顶点（Vertex）。所 有顶点在OpenGL内部计算时都作为三维点处理 ，用二维坐标(x, y)定义的点在OpenGL中默认z值 为0。所有顶点
15、坐标用齐次坐标(x, y, z, w) 表示， 如果w不为0.0，这些齐次坐标表示的顶点即为三 维空间点(x/w, y/w, z/w)。编程者可以自己指定w 值，但很少这样做。一般来说，w缺省为1.0。 OpenGLOpenGL建模建模- -描述图元描述图元 线(Line) :在OpenGL中，线代表线段（Line Segment），不是数学意义上的那种沿轴两个 方向无限延伸的线。这里的线由一系列顶点顺 次连结而成，有闭合和不闭合两种。见图。 OpenGLOpenGL建模建模- -描述图元描述图元 多边形(Polygon) :OpenGL中定义的多边 形是由一系列线段依次连结而成的封 闭区域 。这些线段不能交叉，区域内不能有空洞， 多边形必须为凸多边形，否则不能被OpenGL 函数接受。合法和非法多边形图示见图 OpenGLOpenGL建模建模- -描述图元描述图元 定义顶点 ：在OpenGL中，所有几何物体最终都由有 一定顺序的顶点集来描述。函数glVertex234sifdv(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(p
