计算机图形学第二讲-光栅图形学ppt课件.ppt

《计算机图形学第二讲-光栅图形学ppt课件.ppt》由会员分享，可在线阅读，更多相关《计算机图形学第二讲-光栅图形学ppt课件.ppt（87页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第二讲光栅图形学l光栅图形学部分重要概念l直线的生成l圆的扫描转换l多边形的扫描转换l字符的显示方法l裁剪l反走样l消隐 光栅扫描式显示器是一种画点设备，可看作是一个点阵单元发生器，并可控制每个点阵单元的亮度。每个可寻址的点阵单元称为一个像素（pixel）。显示器在水平和垂直方向上能够寻址的像素数称为分辨率。光栅图显示器特征部分重要概念l区域充填l光栅化（扫描转化）确定最佳逼近图形的像素集合，并用指定属性写像素的过程称为图形的扫描转化或光栅化。确定二维图形内部区域对应的像素集，并用指定的属性或图案进行显示的过程。部分重要概念l走样和反走样l裁剪l消隐（消除隐藏线和隐藏面）确定一个图形的哪些部分

2、在窗口内，必须显示；哪些部分落在窗口之外，不该显示的过程称为裁剪。因像素逼近误差，使图形产生畸变（台阶、锯齿）的现象称之为走样。用于减少或消除走样的技术称为反走样。为了提高图形的真实性，必须把隐藏的部分从图中删除，习惯上称为消除隐藏线和隐藏面，或简称消隐。直线段的扫描转换算法直线的扫描转换直线的扫描转换:确定最佳逼近于该直线的一组象素，并且按扫描线顺序，对这些象素进行写操作。在介绍三个常用算法前，先介绍一种最容易想到的算法：直接计算法！直接计算法！0 直接计算法直接计算法假定直线的起点、终点分别为：（x0,y0),(x1,y1)，且都为整数。计算出斜率k=(y1-y0)/(x1-x0),在Y轴

3、的截距b=y0-k*x0y=k*x+b(X i+1,kX i+1+b)(X i,Yi)(X i,Yi)栅格交点表示象素点位置。直接计算法直接计算法这样一来，只要给定这样一来，只要给定 x的值，根据解析式立即的值，根据解析式立即可以计算出对应的可以计算出对应的y值，然后输出值，然后输出(x,round(y).这种方法直观，但效率太低，因为每一步需要这种方法直观，但效率太低，因为每一步需要一次浮点乘法、一次浮点加法和一次舍入运算。一次浮点乘法、一次浮点加法和一次舍入运算。(X i+1,kX i+1+b)(X i,Yi)(X i,Yi)。直线的生成直线段扫描转换算法：直线段扫描转换算法：数值微分法数

4、值微分法DDADDA算法算法 中点画线法中点画线法 BresenhamBresenham画线算法画线算法1 数值微分法（）数值微分法（）假定直线的起点、终点分别为：（x0,y0),(x1,y1)，且都为整数。(X i+1,Yi+k)(X i,Int(Yi+0.5)(X i,Yi)。数值微分(DDA)法基本思想已知过端点P0(x0,y0),P1(x1,y1)的直线段Ly=kx+b直线斜率为考虑当x从xixi+1时y的变化规律：设x=xi+1-xixi+1=xi+x数值微分(DDA)法计算yi+1=kxi+1+b=k(xi+x)+b=kxi+b+kx=yi+kx当x=1;yi+1=yi+k即：当x

5、每递增1，y递增k(即直线斜率)；注意上述分析的算法仅适用于k1的情形。在这种情况下，x每增加1,y最多增加1。当k1时，必须把x，y地位互换数值微分(DDA)法增量算法：在一个迭代算法中，如果每一步的x、y值是用前一步的值加上一个增量来获得，则称为增量算法。DDA算法就是一个增量算法。数值微分(DDA)法voidDDALine(intx0,inty0,intx1,inty1,intcolor)intx；floatdx,dy,y,k;dx,=x1-x0,dy=y1-y0;k=dy/dx,y=y0;for(x=x0;xx1,x+)drawpixel(x,int(y+0.5),color);y=y

6、+k;数值微分(DDA)法例：画直线段P0(0,0)-P1(5,2)k=0.4xyint(y+0.5)00010.4020.8131.2141.6252.02数值微分(DDA)法缺点：在此算法中，y、k必须是float，且每一步都必须对y进行舍入取整，不利于硬件实现。2中点画线法原理：假定直线斜率0KP2离直线更近更近-取P2。M在Q的上方-P1离直线更近更近-取P1M与Q重合，P1、P2任取一点。问题：如何判断M与Q点的关系？中点画线法由常识知：若y=kx+b;F(x,y)=y-kx-b;则有中点画线法假设直线方程为：ax+by+c=0通过两点不能唯一确定a,b,c,取a=y0-y1,b=x

7、1-x0,c=x0y1-x1y0，F(x,y)=ax+by+c;则有欲判断M点是在Q点上方还是在Q点下方，只需把M代入F(x,y),并检查它的符号。中点画线法构造判别式：d=F(M)=F(xp+1,yp+0.5)=a(xp+1)+b(yp+0.5)+c当d0，M在直线(Q点)上方，取右方P1；当d=0，选P1或P2均可，约定取P1；能否采用增量算法呢？中点画线法若d0-M在直线上方-取P1;此时再下一个象素的判别式为d1=F(xp+2,yp+0.5)=a(xp+2)+b(yp+0.5)+c=a(xp+1)+b(yp+0.5)+c+a=d+a；增量为a中点画线法若dM在直线下方-取P2;此时再下

8、一个象素的判别式为d2=F(xp+2,yp+1.5)=a(xp+2)+b(yp+1.5)+c=a(xp+1)+b(yp+0.5)+c+a+b=d+a+b；增量为ab中点画线法画线从画线从(x0 0,y0 0)开始，开始，d的初值的初值d0 0=F(x0 0+1,y0 0+0.5)=a(x0 0+1)+b(y0 0+0.5)+c =F(x0 0,y0 0)+a+0.5b=a+0.5b 由于只用由于只用d 的符号作判断，为了只包含整数运算的符号作判断，为了只包含整数运算,可以用可以用2d代替代替d来摆脱小数，提高效率。来摆脱小数，提高效率。中点画线法voidMidpointLine(intx0,i

9、nty0,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;drawpixel(x,y,color);while(xx1)if(d1则(y0,x0)和(y1,x1)所确定的直线斜率k0,1，适用于前面讨论的情形。对(y0,x0)和(y1,x1)所确定的直线进行扫描转换，每确定一组(x,y)，输出(y,x)。(x0,y0)(x0,y0)(y1,x1)(y1,x1)(x1,y1)(x1,y1)(y0,x0)(y0,x0)斜率不在0,1的直线的处理若-1k0先对(x0

10、,-y0)和(x1,-y1)所确定的直线进行扫描转换，每确定一组(x,y)，输出(x,-y)。(x0,y0)(x0,y0)(x1,-y1)(x1,-y1)(x1,y1)(x1,y1)(x0,-y0)(x0,-y0)斜率不在0,1的直线的处理若k0.5，则(x,y)更新为(x+1,y+1)，同时将d更新为d-1；否则(x,y)更新为(x+1,y)。5.当直线没有画完时，重复步骤3和4。否则结束。改进改进1：令e=d-0.5e初=-0.5，每走一步有e=e+k。if(e0)then e=e-1算法步骤算法步骤为：1.输入直线的两端点P0(x0,y0)和P1(x1,y1)。2.计算初始值x、y、e=

11、-0.5、x=x0、y=y0。3.绘制点(x,y)。4.e更新为e+k，判断e的符号。若e0，则(x,y)更新为(x+1,y+1)，同时将e更新为e-1；否则(x,y)更新为(x+1,y)。5.当直线没有画完时，重复步骤3和4。否则结束。改进改进2：用2ex来替换ee初=-x，每走一步有e=e+2y。if(e0)thene=e-2xe=e+ke=e+y/xxe=xe+ye=-0.52e=-1算法步骤算法步骤：1.输入直线的两端点P0(x0,y0)和P1(x1,y1)。2.计算初始值x、y、e=-x、x=x0、y=y0。3.绘制点(x,y)。4.e更新为e+2 y，判断e的符号。若e0，则(x,

12、y)更新为(x+1,y+1)，同时将e更新为e-2 x；否则(x,y)更新为(x+1,y)。5.当直线没有画完时，重复步骤3和4。否则结束。Bresenham画线算法BresenhamLine(x0,y0,x1,y1,color)int x0,y0,x1,y1,color;int x,y,dx,dy,e;dx=x1-x0;dy=y1-y0;e=-dx;x=x0;y=y0;for(i=0;i=0)e=e-2*dx;y+;举例：用Bresenham方法扫描转换连接两点P0（0,0）和P1（5,2）的直线段。xyee0=-5;dx=5;dy=200-1103(-7)21-3311(-9)42-552

13、-1Bresenham算法Bresenham画线算法 在直线生成的算法中在直线生成的算法中BresenhamBresenham算法算法是最有效的算法之一。令是最有效的算法之一。令 k=y/xk=y/x，就就0k10k1的情况来说明的情况来说明BresenhamBresenham算法。算法。由由DDADDA算法可知：算法可知：y yi+1i+1=y=yi i+k (1)+k (1)由于由于k k不一定是整数，由此式求出的不一定是整数，由此式求出的y yi i也也不一定是整数，因此要用坐标为（不一定是整数，因此要用坐标为（x xi i,y,yirir）的象素来表示直线上的点，其中）的象素来表示直线

14、上的点，其中y yirir表表示最靠近示最靠近y yi i的整数。的整数。实验报告1：名称：直线的扫描转换名称：直线的扫描转换目的要求：理解和掌握直线扫描转换的三目的要求：理解和掌握直线扫描转换的三种算法，并在某种开发环境下将其具体实种算法，并在某种开发环境下将其具体实现。现。实验步骤：（要写出实际实现的程序和结实验步骤：（要写出实际实现的程序和结果，切忌将书上或笔记上的程序照搬）果，切忌将书上或笔记上的程序照搬）要有实验总结。要有实验总结。基本要求基本要求理解图形的扫描转换的含义；掌握DDA、MIDPoint、Bresenham画线算法。（算法的原理、代码表示、特点等）能够编程处理任意直线。

15、课堂测试（一）奇数列：奇数列：解释下列名词：光栅化、区域填充、裁剪解释下列名词：光栅化、区域填充、裁剪请说明中点划线法的基本思想请说明中点划线法的基本思想根据中点划线法用根据中点划线法用C语言完成下列函数语言完成下列函数2012/2/29 /SetPixel 为已有函数，描画点(x,y)void SetPixel(int x,int y,int color);void MidpointLine(int x0,int y0,int x1,int y1,int color)用中点划线法光栅化连接点用中点划线法光栅化连接点p1(0,0)和和p2(6,3)的直线的直线课堂测试（一）偶数列：偶数列：解释

16、下列名词：走样、反走样、消隐解释下列名词：走样、反走样、消隐请说明请说明Bresenham划线法的基本思想划线法的基本思想根据根据Bresenham划线法用划线法用C语言完成下列函数语言完成下列函数2012/2/29 /SetPixel 为已有函数，描画点(x,y)void SetPixel(int x,int y,int color);void MidpointLine(int x0,int y0,int x1,int y1,int color)用用Bresenham划线法光栅化连接点划线法光栅化连接点p1(0,0)和和p2(6,3)的直线的直线圆的扫描转换1 基础知识2 中点画圆法3 Br

17、esenham画圆法1）直接利用圆的方程生成圆）直接利用圆的方程生成圆下面先以圆心在原点、半径r为整数的圆为例，讨论圆的生成算法。假设圆的方程为：x2+y2=r21 基础知识x2+y2=r2y=sqrt(r2-x2)在一定范围内，每给定一x值，可得一y值。当x取整数时，y须取整。缺点：浮点运算，开方，取整，不均匀。yx也可应用圆的参数方程画出分布比较均匀的点x=rcosy=rsin但仍要采用浮点运算、乘法运算、取整运算。(y,x)(-y,x)(-x,y)(-x,-y)(-y,-x)(y,-x)(x,-y)2）八分法画圆）八分法画圆利用圆的对称性：利用圆的对称性：结论：只需对一个八分圆进行扫描转

18、换。结论：只需对一个八分圆进行扫描转换。当圆心坐标(xc，yc)，半径为整数r时：(x-xc)2+(y-yc)2=r2可以先对圆心坐标(0，0)，半径为r的八分圆进行扫描转换，根据圆的对称性，得到八个对称点，再将这八个点进行平移，即可得到原始圆上的对应点。3 3）画任意圆的方法）画任意圆的方法voidCircle8Points(intx0,inty0,intx,inty,COLORREFc)pDC-SetPixel(x0+x,y0+y,c);pDC-SetPixel(x0-x,y0+y,c);pDC-SetPixel(x0+x,y0-y,c);pDC-SetPixel(x0-x,y0-y,c)

19、;pDC-SetPixel(x0+y,y0+x,c);pDC-SetPixel(x0-y,y0+x,c);pDC-SetPixel(x0+y,y0-x,c);pDC-SetPixel(x0-y,y0-x,c);对于圆心在（对于圆心在（x0,y0)、半径为、半径为r的圆，先对圆心在原的圆，先对圆心在原点，半径为点，半径为r的的8分圆进行扫描转换，每确定一个象素，可分圆进行扫描转换，每确定一个象素，可输出原始圆的输出原始圆的8个点。个点。2 中点画圆法利用圆的对称性，只须讨论1/8圆。第二个8分圆。P为当前点亮象素，那么，下一个点亮的象素可能是P1（xp+1，yp）或P2（xp+1，yp+1)。(

20、|dy|=|x/y|*|dx|)MP1P2P（xp，yp）P2构造函数：F（X，Y）=X2+Y2-r2；则F（X，Y）=0（X，Y）在圆上；F（X，Y）0（X，Y）在圆外。设M为P1、P2间的中点，M=(Xp+1,Yp-0.5)MP1有如下结论：F（M）M在圆内-取P1F（M）=0-M在圆外-取P2为此，可采用如下判别式：MP1P2d=F(M)=F(xp+1,yp-0.5)=(xp+1)2+(yp-0.5)2-r2若d=0,则P2为下一个象素，那么再下一个象素的判别式为：d1=F(xp+2,yp-1.5)=(xp+2)2+(yp-1.5)2-r2=d+（2xp+3）+（-2yp+2）即d的增量

21、为2(xp-yp)+5.MP1P2M最后一个问题：判别式最后一个问题：判别式d的初始值的初始值算法步骤算法步骤：1.输入圆的半径R。2.计算初始值d=1.25-R、x=0、y=R。3.绘制点(x,y)及其在八分圆中的另外七个对称点。4.判断d的符号。若d0，则先将d更新为d+2x+3，再将(x,y)更新为(x+1,y)；否则先将d更新为d+2(x-y)+5，再将(x,y)更新为(x+1,y-1)。5.当x=y时，重复步骤3和4。否则结束。中点画圆法程序代码中点画圆法程序代码MidpointCircle(intr,intcolor)intx,y;floatd;x=0;y=r;d=1.25-r;d

22、rawpixel(x,y,color);while(x=y)if(d0)d=d+2*x+3;x+elsed=d+2*(x-y)+5;x+;y-;drawpixel(x,y,color);为了进一步提高算法的效率，可以将上面的算法中的浮点数改写成整数，将乘法运算改成加法运算，即仅用整数实现中点画圆法。使用e=d-0.25代替de0=1-rd0e-0.25由于e的初值为整数，且在运算过程中的增量也是整数，故e始终是整数，所以e-0.25e0。算法优化算法优化算法步骤算法步骤：1.输入圆的半径R。2.计算初始值d=1-R、x=0、y=R。3.绘制点(x,y)及其在八分圆中的另外七个对称点。4.判断d

23、的符号。若d0，则先将d更新为d+2x+3，再 将(x,y)更 新 为(x+1,y)；否 则 先 将 d更 新 为d+2(x-y)+5，再将(x,y)更新为(x+1,y-1)。5.当x=y时，重复步骤3和4。否则结束。中点画圆法程序代码中点画圆法程序代码MidpointCircle(intr,intcolor)intx,y;floatd;x=0;y=r;d=1-r;drawpixel(x,y,color);while(x=y)if(d0)d+=2*x+3;x+elsed+=2*(x-y)+5;x+;y-;drawpixel(x,y,color);上述算法能否再改进呢？上述算法能否再改进呢？注意

24、到注意到d d的增量是的增量是x x,y y的线性函数，的线性函数，每当每当x x递增递增1 1，则，则d d的增量递增的增量递增x x=2=2每当每当y y递减递减1 1，则，则d d的增量递增的增量递增y y=2=2x x初始值初始值=3=3；y y初始值初始值=-2=-2r r+2+2x=0;y=r;d=1-r;.if(d0)d+=2*x+3;x+;elsed+=2*(x-y)+5;x+;y-;x=0;y=r;d=1-r;d1=3;d2=-2*r+2;.if(d0)d+=d1;x+;d1+=2;elsed+=d1+d2;x+;y-;d1+=2;d2+=2MidpointCircle(in

25、t r,int color)int x,y;int d;x=0;y=r;d=1-r;d1=3;d2=-2*r+2;drawpixel(x,y,color);while(x=y)if(d0和和dD0若若pi0，即，即dH 0，必有，必有pi0，dD0，必有，必有pi0。得得出出结结论论：pi做做判判别别量量，pi0选选H点点为为下下一一个个象象素素点，当点，当pi0时，选时，选D点为下一个象素点。点为下一个象素点。HD(xi,yi)从从pi计算计算pi+1HD(xi,yi)dDdH从从pi计算计算pi+1当当pi0时，应选时，应选D点，即选点，即选当当pi0时，应选时，应选H点，即选点，即选 H

26、D(xi,yi)dDdH画画圆圆的的起起始始点点是是(0，R)，即即x1=0，y1=R，代代入入前前式，令式，令i=1，就得到：，就得到：HD(xi,yi)dDdHvoid BresenhamCircle(int R)int x,y,p;x=0;y=R;p=3-2*R;for(;x=0)p+=4*(x-y)+10;y-;else p+=4*x+6;HD(xi,yi)dDdH只只 需需 修修 改改 语语 句句SetPixel(x,y)，画画八八个个对对称称的的点点，就就可可以以画画出出全全部部圆圆周周。若若加加一一个个平平移移，就就可可以以画画出出圆圆心心在在任任意位置的圆周。意位置的圆周。vo

27、id BresenhamCircle(int R)int x,y,p;x=0;y=R;p=3-2*R;for(;x=0)p+=4*(x-y)+10;y-;else p+=4*x+6;xyp05-7615-110259-2347 例例:圆心圆心(0，0)、半径、半径R=5，p0 =3-2*R=-7,演示if(p=0)p+=4*(x-y)+10;y-;else p+=4*x+6;光栅系统的光栅系统的Bresenham画线算法可通过设画线算法可通过设定在每一取样步寻找最接近圆周像素的决策参定在每一取样步寻找最接近圆周像素的决策参数而移植为画圆算法。数而移植为画圆算法。然而，圆方程是非线性的，因此，计

28、算像然而，圆方程是非线性的，因此，计算像素与圆的距离必须进行平方根运算。素与圆的距离必须进行平方根运算。Bresenham画圆算法则通过比较像素与圆画圆算法则通过比较像素与圆的距离的平方而避免了平方根运算。的距离的平方而避免了平方根运算。与与Bresenham直线生成算法一样，其基本直线生成算法一样，其基本思想：利用判别变量来判断选择最近的像素，思想：利用判别变量来判断选择最近的像素，判别变量仅用加减和移位就可计算出来判别变量仅用加减和移位就可计算出来。同样，只考虑同样，只考虑1/8圆，圆，x从到从到R/结束。结束。如果得到第如果得到第k步的步的像素点像素点(xk,yk)，则下一个像素只可则下

29、一个像素只可能是能是 A(xk+1,yk)或或B(xk+1,yk-1),如图。如图。以最高点为初始点，计算判别量初值再根据判别量的正负确定递推关系递推关系的确定需根据图分别不同情况进行讨论（去掉绝对值符号，并进行化简）圆弧上可选点情况初始值的计算n利用增量计算方法加速判别参数的计算注：比较其与中点画圆算法的判别参数。BresenhamBresenham画圆算法代码画圆算法代码voidCircleBres(intradius)intx=0,y=radius,p=3-2*radius;while(xy)Drawpixel(x,y,c);x+;if(p0)p+=(4*x+6);elsep+=(4*(x-y)+10);y-;