计算机图形学 - GOOGLE CODE.ppt

1、1,第三章 输出图元,所谓 图元的生成，是从图元的参数表示形式 （由图形软件包的使用者指定）到点阵表示形式（光栅显示系统刷新时所需的表示形式）的转换。 这个过程我们也称为扫描转换,主要工作包括确定像素集合及其颜色，显示图形对象。 本章讨论这些常用图形对象的扫描转换算法以及图案、线宽、线型等属性的实现方法，最后两节介绍用于改善光栅图形的视觉效果的技术图形保真技术和半色调技术。,2,图形显示前需要：扫描转换+裁剪 裁剪-扫描转换：最常用，节约计算时间。 扫描转换-裁剪：算法简单； 扫描转换到画布-位块拷贝：算法简单，但耗时耗内存。常用于字符显示。,第三章 输出图元,3,线段的扫描转换算法 圆和椭圆

2、的扫描转换 保持图形对象的数学性质 多边形的扫描转换 区域填充算法 线宽和线型 填充图案 字符技术 图形保真技术 半色调技术,本章内容,第三章 输出图元,4,线段的扫描转换算法 圆和椭圆的扫描转换 保持图形对象的数学性质 多边形的扫描转换 区域填充算法 线宽和线型 填充图案 字符技术 图形保真技术 半色调技术,内 容,线段的扫描转换算法 圆和椭圆的扫描转换 保持图形对象的数学性质 多边形的扫描转换 区域填充算法 线宽和线型 填充图案 字符技术 图形保真技术 半色调技术,内 容,5,3.1线段的扫描转换,DDA算法 Bresenham画线算法 并行画线算法 画线算法的讨论,6,DDA扫描转换直线

3、段,扫描转换直线段 求与直线段充分接近的像素集 假设 直线段的宽度为1,像素间均匀网格 整型坐标系,线段的扫描转换,7,DDA扫描转换直线段,数字微分(DDA)画线算法 （ digital differential analyzer） 条件： 待扫描转换的直线段：P1(x1,y1),P2(x2,y2) x=x2-x1, y=y2-y1 参数方程：x=x1+ x*t y=y1+ y*t 0 t1 直接求交算法： 划分区间0, 1,dt=1/n 计算坐标. 取整.,8,DDA扫描转换直线段,复杂度：乘法+加法+取整 DDA增量算法 xi+1=x1+x*ti+1=xi+x*dt=xi+xinc yi

4、+1=y1+y*ti+1=yi+y*dt=yi+yinc 复杂度：加法+取整,9,DDA扫描转换直线段,算法描述 void DDA_line(int x1, y1, x2, y2) int deltax, deltay, n, i; float x, y, xinc, yinc; deltax = x2 - x1; deltay = y2 y1; if ( abs(deltax)abs(deltay) ) n = abs(deltax); else n = abs(deltay); xinc = (float)deltax / n; yinc = (float)deltay / n; x =

5、x1; y = y1; write_pixel(round(x), round(y); for ( i=0; in; i+ ) x += xinc; y += yinc; write_pixel(round(x), round(y); ,10,DDA扫描转换直线段,DDA算法缺点 需要进行浮点数运算 运行效率低 不便于用硬件实现,11,Bresenham扫描转换直线段,Bresenham画线算法 目标：消除DDA算法中 的浮点运算 条件： 同DDA算法 斜 率：0k1 直线段的隐式方程 （(x0,y0)(x1,y1)两端点） F(x,y)=ax+by+c=0 式中 a=y0-y1, b=x1-

6、x0, c=x0y1-x1y0,12,Bresenham扫描转换直线段,分 析 线段的端点坐标:(x1,y1)和(x2,y2) 线段方程: y=k*x+b， 将平面以(x1,y1)为坐标原点划分为八个卦限， 考虑线段在第一卦限，即 x=x2-x10，y=y2-y10， 并且xy的情况 此时xinc=1，yinc=k（0k1）,13,Bresenham扫描转换直线段,Bresenham画线算法示意图,14,Bresenham扫描转换直线段,Bresenham画线算法的特点： 只包括整数的加法、减法和左移（乘2） 操作，效率高。 适合用硬件实现。,!请将第一卦限的Bresenham画线算法推广到其

7、它卦限.,15,并行画线算法,有p个处理器。将线段沿着x方向分为p个区段，区段的宽度为 xp=ceiling(x/p)=(x+p-1) div p 其中x=xe-xs为线段宽度 ceiling(x/p)为 x/p的最小整数 div为整数除法运算 再将这p个区段按照从左向右的次序依次编号为0,1,p-1,则编号为i的区段的起点的x坐标 xi=xs+i* xp,16,并行画线算法,计算编号为i的区段的起点的y坐标yi和判别式fi 的初始值。 区段的高度yp=k*xp yi=y1+round(i*yp) ei=di-0.5 =k*i*xp-round(i*yp)+k-0.5 fi=2*x*ei =2

8、*y*i*xp-2*x*round(i*yp)+2* y- x round(i*yp)=int(i*yp+0.5) =(2*y*i*xp+x) div(2*x) p个区段可以由p个处理器同时用划线算法画出。,17,并行画线算法,让每一个处理器处理一组像素 适用于系统中的处理器非常多的场合,给定一条线段，可以得到它的包围 盒，包围盒中共有x* y个像素。 让每个处理器处理一个像素，设像 素的坐标为(x,y),则像素到线段的垂 直距离。 d=A*x+B*y+C 其中，A=-y/linelength B=x/linelength C=(x1x-y1x)/linelength,线段的包围盒,18,并行

9、画线算法,Linelength=(x2+y2)1/2 d小于某个设定值，该像素就被设置成指定的线段颜色。可以看出，这种并行画线算法特别适合于画具有一定宽度的线段。,19,画线算法的进一步讨论,1.线段端点的次序 线段P1P2与线段P2P1在扫描转换后应 该生成相同的像素集合，这样才能保证同 一线段的像素表示与线段的端点次序无关。 存在问题：见Bresenham算法 解决方法：对于|k|1的线段，总是 以左端点为起点，从左向右生成；对于 |k|1的线段，总是以下端点为起点，从下 向上生成。,画线算法的进一步讨论,20,2.线段的亮度,B,A,现象：A比B亮。原因：A上的像素点密集。解决方法：图形

10、保真技术。,画线算法的进一步讨论,21,3.3 帧缓冲器的装载,1.访问帧缓冲器时的效率 addr(x,y)=addr(0,0)+y*xmax+x addr(x+1,y)=addr(x,y)+1 addr(x+1,y+1)=addr(x,y)+xmax+1,屏幕上(x,y)坐标与帧缓冲器中线性地址的对应关系,22,3.4 OpenGL中画线,void CTwoDShapeView:DrawLines() GLfloat fLineWidth2; glGetFloatv(GL_LINE_WIDTH_RANGE,fLineWidth); glLineWidth(fLineWidth0); glBe

11、gin(GL_LINES); glVertex2f(0.5f,0.5f); glVertex2f(-0.50f,0.0f); glEnd(); ,23,3.4 OpenGL中画线,void CTwoDShapeView:DrawLineStipple() GLfloat fLineWidth2; glGetFloatv(GL_LINE_WIDTH_RANGE,fLineWidth); glLineWidth(fLineWidth1/6.0f); glBegin(GL_LINES); glVertex2f(-0.8f,0.8f); glVertex2f(0.80f,0.8f); glEnd();

12、 glEnable(GL_LINE_STIPPLE); glLineStipple(1,0 x00FF); glBegin(GL_LINES); glVertex2f(-0.8f,0.4f); glVertex2f(0.80f,0.4f); glEnd(); ,24,3.4 OpenGL中画线,glBegin(GL_LINE_STRIP);,glBegin(GL_LINE_LOOP);,25,线段的扫描转换算法 圆和椭圆的扫描转换 保持图形对象的数学性质 多边形的扫描转换 区域填充算法 线宽和线型 填充图案 字符技术 图形保真技术 半色调技术,内 容,26,3.5 圆生成算法,处理对象：圆心在

13、原点的圆弧 圆的八对称性,27,两种直接离散方法： 离散点: x2+y2=R2 (x,sqrt(R2-x2) 离散角度: x=Rcos y=Rsin 缺点：计算量大。,扫描转换圆弧,28,扫描转换圆弧,圆弧的正负划分性 F(x,y)=x2+y2-R2,圆弧外的点：F(X，Y)0 圆弧内的点：F(X，Y)0,29,DDA扫描转换圆弧,DDA 考虑对象：第二个八分圆， 第一象限的八分之一圆弧 x=Rcost y=Rsint 对应的微分方程： dx=-Rsintdt=-yt dy=Rcosdt=xdt 用差分方程近似地代替微分方程，得到： x=-yt y=xt 令=t,若点(xi,yi)在圆上，则

14、xi+1=xi- yi yi+1=yi- xi 而点(xi+1,yi+1)近似地在圆上. 为了使点(xi+1,yi+1)与点(xi,yi)邻 近，应该使 （xi+1-xi）2+（yi+1-yi）2= 2（xi2+yi2）= 2R22 当2n-1R/sqrt(2)2n,取=2-n xi+12+yi+12=(1+2)(xi2+yi2),因此点（xi+1,yi+1）将越来越偏离圆心,圆的对称性,30,中点法扫描转换圆弧,中点画圆算法,中点画圆算法示意图,假设当前列（x=xi列）中最接近圆弧的像素已经取为P(xi,yi)，根据第二卦限1/8圆的走向，下一列（x=xi+1列）中最接近圆弧的像素只能在P的

15、正右方点H(xi+1,yi)或右下方点L(xi+1,yi-1)中选择。,31,DDA扫描转换圆弧,中点画圆算法 中点画圆算法采用H与L的中点作为选择标准。 将H与L的中点记为M，其坐标为(xi+1,yi-0.5)，选择的标准是：如果M在圆内，那么下一点取H；如果M在圆外，那么下一点取L；如果M在圆上，那么下一点可以取L，也可以取H，我们约定取L。 令函数F(x,y)=x2+y2-R2，对于圆上的点，F(x,y)=0；对于圆内的点，F(x,y)0。,32,DDA扫描转换圆弧,中点画圆算法 令判别式di=F(xi+1,yi-0.5)=(xi+1)2+(yi-0.5)2-R2，则有： 1.如果di0

16、，说明M在圆内，下一点取H(xi+1,yi)，即 xi+1=xi+1,yi+1=yi，新的判别式 di+1=F(xi+1+1,yi+1-0.5)=(xi+1+1)2+(yi-0.5)2-R2=di+2xi+3； 2. 如果di0，说明M在圆外或圆上，下一点取L(xi+1,yi-1)，即xi+1=xi+1,yi+1=yi-1，新的判别式 di+1=F(xi+1+1,yi+1-0.5)=(xi+1+1)2+(yi-1-0.5)2-R2=di+2xi-2yi+5。 初始时， x0=0， y0=R， d0=F(x0+1,y0-0.5)=(0+1)2+(R-0.5)2-R2=1.25-R。 但这个算法中

17、仍然有浮点数运算。 令f=d-0.25，那么初始时，x0=0，y0=R，f0=d0-0.25=1-R。 假设已知当前列像素位置(xi,yi)和判别式fi，则有：,33,DDA扫描转换圆弧,中点画圆算法 1）. 如果fi-0.25，那么下一列像素位置 xi+1=xi+1， yi+1=yi， fi+1=fi+2xi+3； 2）. 如果fi-0.25，那么下一列像素位置 xi+1=xi+1， yi+1=yi-1， fi+1=fi+2xi-2yi+5。 f的初始值1-R为整数，每次迭代f的变化量也是整数，即f保持为整数，因此f-0.25等价于f0。,34,DDA扫描转换圆弧,适用于第二卦限的中点画圆程

18、序 void Midpoint_circle(int radius) int x, y, f; x = 0; y = radius; f = 1 - radius; write_pixel(x, y); while ( xy ) if ( f0 ) f += 2*x + 3; else f += 2*(x-y) + 5; y-; x+; write_pixel(x, y); ,35,DDA扫描转换圆弧,中点画圆算法的优点 中点画圆算法只用到整数的加法、减法和左移（乘2）运算 ，效率高并且适合用硬件实现。,当判别式fi0时，下一点取H(xi+1,yi)，fi的变化量为hi=2xi+3；当判别式f

19、i0时，下一点取L(xi+1,yi-1)，fi的变化量为li=2xi-2yi+5。hi和li都是x和y的线性函数，而不是常数，但是，我们也可以用增量算法计算它们的值，从而提高效率。,如果判别式fi0，下一点取H(xi+1,yi)，那么， hi+1=2xi+1+3=2(xi+1)+3=hi+2 li+1=2xi+1-2yi+1+5=2(xi+1)-2yi+5=li+2 如果判别式fi0，下一点取L(xi+1,yi-1)，那么， hi+1=2xi+1+3=2(xi+1)+3=hi+2 li+1=2xi+1-2yi+1+5=2(xi+1)-2(yi-1)+5=li+4 初始时，x0=0，y0=R，h

20、0=3，l0=-2R+5。,36,DDA扫描转换圆弧,另一个中点画圆程序,void Midpoint_circle1(int radius) int x, y, f, h, l; x = 0; y = radius; f = 1 - radius; h = 3; l = 5 2*radius; write_pixel(x, y); while ( xy ) if ( f0 ) f += h; h += 2; l += 2; else f += l; h += 2; l += 4; y-; x+; write_pixel(x, y); ,37,Bresenham扫描转换圆弧,Bresenham画

21、圆算法,假设当前列（x=xi列）中最接近圆弧的像素已经取为P(xi,yi)，根据第二卦限1/8圆的走向，下一列（x=xi+1列）中最接近圆弧的像素只能在P的正右方点H(xi+1,yi)或右下方点L(xi+1,yi-1)中选择。 如上小节所述，中点画圆算法采用H与L的中点作为选择标准，而Bresenham画圆算法采用点到圆心的距离平方与半径平方之差作为选择标准。 令D(H)=(xi+1)2+yi2-R2，D(L)=(xi+1)2+(yi-1)2-R2，则选择的标准是：如果|D(H)|D(L)|，那么下一点取L；如果|D(H)|=|D(L)|，那么下一点可以取L，也可以取H，我们约定取L。,38,

22、Bresenham扫描转换圆弧,Bresenham画圆算法示意图,39,Bresenham扫描转换圆弧,Bresenham画圆算法,选择的标准可以表达为：如果di0，那么下一点 取H； 如果di0，那么下一点取L。 di的计算要用到绝对值，还是比较麻烦的。通过以下 对D(H)及D(L)的讨论可以将计算简化：,1. di=D(H)+D(L) 2,40,Bresenham和中点算法的比较,中点画圆算法的判别式初始值d0M=1.25-R，变化量为2xi+3或2(xi-yi)+5; Bresenham画圆算法的判别式初始值d0B=3-2R，变化量为4xi+6或4(xi-yi)+10，即Bresenham画圆算法的判别式的变化量是中点画圆算法的2倍。 2d0M=2.5-2R，当R为整数时 2.5-2R02.52R1.25R2R42R3-2R0 3-2R032R2.5-2R0 2.5-2R03-2R0 也就是说，当R为整数时，判别式初始值取2.5-2R与取3-2R的效果完全相同，因此，中点画圆算法与Bresenham画圆算法在整数情况下完全等价，产生完全相同的像素序列。,41,正负法