《计算机图形学第二讲光栅图形学ppt课件.ppt》由会员分享，可在线阅读，更多相关《计算机图形学第二讲光栅图形学ppt课件.ppt（87页珍藏版）》请在三一办公上搜索。
1、第二讲 光栅图形学,光栅图形学部分重要概念直线的生成圆的扫描转换多边形的扫描转换字符的显示方法裁剪反走样消隐,光栅扫描式显示器是一种画点设备，可看作是一个点阵单元发生器，并可控制每个点阵单元的亮度。 每个可寻址的点阵单元称为一个像素（ pixel ）。 显示器在水平和垂直方向上能够寻址的像素数称为分辨率。,光栅图显示器特征,部分重要概念,区域充填,光栅化（扫描转化）,确定最佳逼近图形的像素集合，并用指定属性写像素的过程称为图形的扫描转化或光栅化。,确定二维图形内部区域对应的像素集，并用指定的属性或图案进行显示的过程。,部分重要概念,走样和反走样,裁剪,消隐（消除隐藏线和隐藏面）,确定一个图形的
2、哪些部分在窗口内，必须显示；哪些部分落在窗口之外，不该显示的过程称为裁剪。,因像素逼近误差，使图形产生畸变（台阶、锯齿）的现象称之为走样。用于减少或消除走样的技术称为反走样。,为了提高图形的真实性，必须把隐藏的部分从图中删除，习惯上称为消除隐藏线和隐藏面，或简称消隐。,直线段的扫描转换算法,直线的扫描转换: 确定最佳逼近于该直线的一组象素，并且按扫描线顺序，对这些象素进行写操作。在介绍三个常用算法前，先介绍一种最容易想到的算法： 直接计算法！,0 直接计算法,假定直线的起点、终点分别为：（x0,y0), (x1,y1)，且都为整数。 计算出斜率k=(y1-y0)/(x1-x0) , 在Y轴的截
3、距b=y0-k*x0 y=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),。,。,。,。,直线的生成,直线段扫描转换算法： 数值微分法DDA算法 中点画线法 Bresenham画线算法,1 数值微分法（）,假定直线的起点、终点分别为：（x0,
4、y0), (x1,y1)，且都为整数。,(X i+1 ,Yi + k),(X i , Int(Yi +0.5),(X i , Yi),。,。,。,。,数值微分(DDA)法,基本思想已知过端点P0 (x0, y0), P1(x1, y1)的直线段L y=kx+b直线斜率为考虑当x从xixi+1时y的变化规律： 设x=xi+1- xi xi+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每递增1，y递增k(即直线斜率)；注意上述分析的算法仅适用于k 1的情形。在这种
5、情况下，x每增加1,y最多增加1。当 k 1时，必须把x，y地位互换,数值微分(DDA)法,增量算法：在一个迭代算法中，如果每一步的x、y值是用前一步的值加上一个增量来获得，则称为增量算法。DDA算法就是一个增量算法。,数值微分(DDA)法,void DDALine(int x0,int y0,int x1,int y1,int color) int x；float dx, 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+k; ,数值
6、微分(DDA)法,例：画直线段P0(0,0)-P1(5,2) k=0.4x y int(y+0.5) 0 0 0 0.40 0.8 131.2 141.6252.02,数值微分(DDA)法,缺点： 在此算法中，y、k必须是float，且每一步都必须对y进行舍入取整，不利于硬件实现。,2 中点画线法,原理：,假定直线斜率0K1，且已确定点亮象素点P（Xp ,Yp ）,则下一个与直线最接近的像素只能是P1点或P2点。设M为中点，Q为交点现需确定下一个点亮的象素。,中点画线法,当M在Q的下方- P2离直线更近更近-取P2 。M在Q的上方- P1离直线更近更近-取P1M与Q重合， P1、P2任取一点。
7、问题：如何判断M与Q点的关系？,中点画线法,由常识知：若y=kx+b;F(x,y)=y-kx-b;则有,中点画线法,假设直线方程为：ax+by+c=0通过两点不能唯一确定a,b,c,取 a=y0-y1, b=x1-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
8、在直线上方-取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;此时再下一个象素的判别式为 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, y0)开始，d的初值d0=F(x0+1, y0+0.5)= a(x0 +1)+b(y0 +0.5)+c = F(x0, y0)+a
9、+0.5b = a+0.5b 由于只用d 的符号作判断，为了只包含整数运算, 可以用2d代替d来摆脱小数，提高效率。,中点画线法,void 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; drawpixel(x, y, color); while (xx1) if (d0) x+; y+; d+=d2; else x+; d+=d1; drawpixel (x,
10、 y, color); /* while */ /* mid PointLine */,中点画线法,例：用中点画线法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-1425,斜率不在0,1的直线的处理,设起点和终点分别为(x0,y0)和(x1,y1) 若k1则(y0,x0)和(y1,x1)所确定的 直线斜率k 0,1， 适用于前面讨论的情形。对(y0,x0)和(y1,x1)所确定的 直线进行扫描转换， 每确定一组(x,y)，输出(y,x)。,斜率不在0,1的直线的处理
11、,若-1k0先对(x0,-y0)和(x1,-y1)所确定的 直线进行扫描转换， 每确定一组(x,y)，输出(x,-y)。,(x0,y0),(x1,-y1),(x1,y1),(x0,-y0),斜率不在0,1的直线的处理,若k-1对(-y0,x0)和(-y1,x1)所确定的 直线进行扫描转换， 每确定一组(x,y)， 输出(y,-x)。,(x0,y0),(x1,-y1),(x1,y1),(x,-y0),(-y0,x0),(-y1,x1),3 Bresenham算法(教材上介绍的),假定直线段的0k1基本原理：,Bresenham算法原理,误差项d的计算d初=0，每走一步：d=d+k 一旦y方向上走
12、了一步，d=d-1,算法步骤：1.输入直线的两端点P0(x0,y0)和P1(x1,y1)。2.计算初始值x、y、d=0、x=x0、y=y0。3.绘制点(x,y)。4.d更新为d+k，判断d的值。若d0.5，则(x,y)更新为(x+1,y+1)，同时将d更新为d-1；否则(x,y)更新为(x+1,y)。5.当直线没有画完时，重复步骤3和4。否则结束。,改进1：令e=d-0.5,e初=-0.5，每走一步有e=e+k。if (e0) then e=e-1,算法步骤为：1.输入直线的两端点P0(x0,y0)和P1(x1,y1)。2.计算初始值x、y、e=-0.5、x=x0、y=y0。3.绘制点(x,y
13、)。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) then e=e-2x,e=e+ke=e+y/xx e= x e+ 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+2y，判断e的符号。若e0，则(x,y)更新为(x+1,y+1)，同时将e更新
14、为e-2x；否则(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）的直线段。,x y e e0=-5; dx=5;dy=20 0 -1 1 0 3 (-7 )
15、2 1 -3 3 1 1(-9)4 2 -5 5 2 -1,Bresenham算法,Bresenham画线算法,在直线生成的算法中Bresenham算法是最有效的算法之一。令 k=y/x，就0k1的情况来说明Bresenham算法。由DDA算法可知：yi+1=yi+k (1) 由于k不一定是整数，由此式求出的yi也不一定是整数，因此要用坐标为（xi,yir）的象素来表示直线上的点，其中yir表示最靠近yi的整数。,实验报告1：,名称：直线的扫描转换目的要求：理解和掌握直线扫描转换的三种算法，并在某种开发环境下将其具体实现。实验步骤：（要写出实际实现的程序和结果，切忌将书上或笔记上的程序照搬）要
16、有实验总结。,基本要求,理解图形的扫描转换的含义；掌握DDA、MIDPoint、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),用中点划线法光栅化连接点p1(0,0)和p2(6
17、,3)的直线,课堂测试（一）,偶数列：解释下列名词：走样、反走样、消隐请说明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 Bresenham画圆法,1）直接利用圆的方程生成圆
18、下面先以圆心在原点、半径r为整数的圆为例，讨论圆的生成算法。假设圆的方程为： x2 + y2 = r2,1 基础知识,x2 + y2 = r2y = sqrt(r2 - x2)在一定范围内，每给定一x值，可得一y值。当x取整数时，y须取整。缺点：浮点运算，开方，取整，不均匀。,也可应用圆的参数方程画出分布比较均匀的点x = rcosy = rsin 但仍要采用浮点运算、乘法运算、取整运算。,(y,x),(-y,x),(-x,y),(-x,-y),(-y,-x),(y,-x),(x,-y),2）八分法画圆利用圆的对称性：,结论：只需对一个八分圆进行扫描转换。,当圆心坐标(xc ，yc ) ，半径
19、为整数r时： (x-xc)2+(y-yc)2=r2 可以先对圆心坐标(0 ，0 ) ，半径为r的八分圆进行扫描转换，根据圆的对称性，得到八个对称点，再将这八个点进行平移，即可得到原始圆上的对应点。,3）画任意圆的方法,void Circle8Points(int x0,int y0, int x,int y,COLORREF c) 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); pDC-SetPixel(x0+y,y0+x,c)
20、; 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)。(|dy|=|x/y|*|dx|),M,P1,P2,P（xp ，yp ）,P2,构造函数：F（X，Y）=X2 + Y2 - r2 ；则 F（X
21、，Y）= 0 （X，Y）在圆上； F（X，Y） 0 （X，Y）在圆外。设M为P1、P2间的中点，M=(Xp+1,Yp-0.5),M,P1,有如下结论： F（M）M在圆内- 取P1 F（M）= 0 -M在圆外- 取P2为此，可采用如下判别式：,M,P1,P2,d = F(M) = F(xp + 1, yp - 0.5) =(xp + 1)2 + (yp - 0.5) 2 - r2 若d0, 则P1 为下一个象素，那么再下一个象素的判别式为： d1 = F(xp + 2, yp - 0.5) = (xp + 2)2 + (yp - 0.5) 2 - r2 = d + 2xp +3 即d 的增量为
22、2xp +3.,M,P1,P2,M,若d=0, 则P2 为下一个象素，那么再下一个象素的判别式为： d1 = F(xp + 2, yp - 1.5) = (xp + 2)2 + (yp - 1.5) 2 - r2 = d + （2xp + 3）+（-2 yp + 2） 即d 的增量为 2 (xp - yp) +5.,M,P1,P2,M,最后一个问题：判别式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
23、更新为d+2(x-y)+5，再将(x,y)更新为(x+1,y-1)。5.当x=y时，重复步骤3和4。否则结束。,中点画圆法程序代码,MidpointCircle(int r, int color) int x,y; float d; x=0; y=r; d=1.25-r; drawpixel(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); ,为了进一步提高算法的效率，可以将上面的算法中的浮点数改写成整数，将乘法运算改成加法运算，即仅用整数实现中点画圆法。
24、使用e=d-0.25代替de0=1-rd0e-0.25由于e的初值为整数，且在运算过程中的增量也是整数，故e始终是整数，所以e-0.25 e0。,算法优化,算法步骤：1.输入圆的半径R。2.计算初始值d=1-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(int r, int color) int x,y; fl
25、oat d; 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); ,上述算法能否再改进呢？注意到d的增量是x,y的线性函数，每当x递增1，则d的增量递增x=2每当y递减1，则d的增量递增y=2x初始值=3；y初始值=-2r+2,x=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
26、;d2=-2*r+2; .if(d0) d+ = d1; x+;d1+=2 ;elsed+ = d1+d2; x+;y-; d1+=2;d2+=2 ,MidpointCircle(int 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) d+ = d1; x+;d1+=2 else d+ = d1+d2; x+;y-; d1+=2;d2+=2; drawpixel(x,y,color); ,例:圆心(0，0)、半径R=10， x =3，y =
27、 2 R R = -18d = 1 R = -9,3 Bresenham画圆法,Bresenham画圆法与中点画圆法有很多共同之处，不同之处主要是判别式的设计。,在0 xy的1/8圆周上，象素坐标x值单调增加，y值单调减少。 设第i步已确定（xi,yi）是要画圆上的象素点，看第i+1步象素点（xi+1,yi+1）应如何确定。下一个象素点只能是（xi+1,yi）或者（xi+1,yi-1）中的一个,算法四：Bresenham画圆算法,构造判别式：,构造判别式：1.精确圆弧是，则dH 0和dD0若pi0，必有pi0，dD0，必有pi0。得出结论： pi做判别量， pi0选H点为下一个象素点，当pi0
28、时，选D点为下一个象素点。,从pi计算pi+1,从pi计算pi+1,当pi0时，应选D点，即选,当pi0时，应选H点，即选,画圆的起始点是(0，R)，即x1=0，y1=R，代入前式，令i=1，就得到：,void 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;,只需修改语句SetPixel(x,y)，画八个对称的点，就可以画出全部圆周。若加一个平移，就可以画出圆心在任意位置的圆周。,void BresenhamCircle(int R) int x,y,p;x=0
29、; y=R;p=3-2*R;for(;x=0)p+=4*(x-y)+10;y-;else p+=4*x+6;,例:圆心(0，0)、半径R=5， p0 = 3 - 2 * R = -7,演示,if(p=0)p+=4*(x-y)+10;y-;else p+=4*x+6;,光栅系统的Bresenham画线算法可通过设定在每一取样步寻找最接近圆周像素的决策参数而移植为画圆算法。 然而，圆方程是非线性的，因此，计算像素与圆的距离必须进行平方根运算。 Bresenham画圆算法则通过比较像素与圆的距离的平方而避免了平方根运算。 与Bresenham直线生成算法一样，其基本思想：利用判别变量来判断选择最近的
30、像素，判别变量仅用加减和移位就可计算出来 。,同样，只考虑1/8圆，x从到R/ 结束。,如果得到第k步的像素点(xk,yk)， 则下一个像素只可能是 A(xk+1,yk) 或B(xk+1,yk-1), 如图。,以最高点为初始点，计算判别量初值再根据判别量的正负确定递推关系递推关系的确定需根据图分别不同情况进行讨论（去掉绝对值符号，并进行化简）,初始值的计算,利用增量计算方法加速判别参数的计算,注：比较其与中点画圆算法的判别参数。,Bresenham画圆算法代码,void CircleBres(int radius) int x=0,y=radius,p=3-2*radius; while (xy) Drawpixel(x,y,c) ; x+; if (p0) p+=(4*x+6); else p+=(4*(x-y)+10); y-; ,
