计算机图形生成算法线_第1页
计算机图形生成算法线_第2页
计算机图形生成算法线_第3页
计算机图形生成算法线_第4页
计算机图形生成算法线_第5页
已阅读5页,还剩29页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

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*()定义

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论