计算机图形学

1、 第二章第二章 光栅图形学光栅图形学 2.1 2.1 直线段的扫描转换算法直线段的扫描转换算法2.2 2.2 圆弧的扫描转换算法圆弧的扫描转换算法2.3 2.3 多边形的扫描转换与区域填充多边形的扫描转换与区域填充2.4 2.4 字符字符2.5 2.5 裁剪裁剪2.6 2.6 反走样反走样2.7 2.7 消隐消隐2.1 直线段的扫描转换算法直线段的扫描转换算法 数值微分法（DDA算法） 中点画线法 Bresenham画线算法 数值微分法（数值微分法（Digital Differential Analyzer ）l基本思想基本思想 假定直线的起点、终点分别为：（x0,y0), (x1,y1)，且

2、都为整数。 已知过端点P0 (x0, y0), P1(x1, y1)的直线段L(P0,P1);直线斜率为0101xxyyk按照y=kx+b计算相应的y坐标。数值微分数值微分(DDA)法法设步长为x，有xi+1 =xi + x 则yi+1= kxi+1+b= kxi+kx+b= yi+kx 因为光栅点的单位是1，对每一个x方向的增量x =1时; 有yi+1 = yi+k 。即：当x每递增1，y递增k(即直线斜率)。 经过round()函数处理得到显示的光栅点(x,round(y)坐标。 xi+1 =xi+1 yi+1= yi+k栅格交点表示像素点位置(X i , Yi)(X i+1 ,Yi +

3、k)(X i , Int(Yi +0.5)。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; 数值微分数值微分(DDA)法法 例：画直线段P0(0,0)-P1(5,2)0 1 2 3 4 5321Line: P0(0, 0)- P1(5, 2)x y+0.5 int(y+0.5 )0 0+0.5

4、01 0.4+0.5 02 0.8+0.5 13 1.2+0.5 14 1.6+0.5 25 2.0+0.5 2优点优点：在同一坐标上,不可能连续停留两次。缺点缺点： 在此算法中，y、k必须是float，且每一步都必须对y进行舍入取整，不利于硬件实现。算法特点:注意：网格点表示像素注意：网格点表示像素l增量算法：增量算法：在一个迭代算法中，如果每一步的x、y值是用前一步的值加上一个增量来获得，则称为增量算法。DDA算法就是一个增量算法。l缺点缺点注意上述分析的算法仅适用于k 1的情形。在这种情况下，x每增加1,y最多增加1。当 k 1时，必须把x，y地位互换，y每增加1，x相应增加1/k。在此

5、算法中，y、k必须是float，且每一步都必须对y进行舍入取整，有浮点数取整运算,不利于硬件实现。 效率低数值微分数值微分(DDA)法法l原理：假定直线斜率0K P2离直线更近更近-取P2 。M在Q的上方- P1离直线更近更近-取P1M与Q重合， P1、P2任取一点。P=(xp,yp)QP2P1算法原理算法原理如何判断如何判断M点在点在Q点上方还是在点上方还是在Q点下方？点下方？l已知：线段两端点(x0,y0)，(x1,y1)l直线方程为： F(x,y)=ax+by+c=0 其中a=y0-y1, b=x1-x0, c=x0y1-x1y0点在直线下方点在直线上方点在直线上面0,0,0,yxFyx

6、FyxFP=(xp,yp)QP2P1M中点画线法中点画线法欲判断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；能否采用增量算法呢？P=(xp,yp)QP2P1中点画线法中点画线法l若d0，中点M在直线上方，取正右方像素P1 (Xp+1,Yp)再下一个像素的判别式为： d1=F(Xp+1)+1,Yp+0.5)=a(Xp+2)+b(Yp+0.5)+c = d+a d的增量为al若d0，中点M在直

7、线下方，取右上方像素P2 (Xp+1,Yp+1)再下一个像素的判别式为： d2=F(Xp+1)+1,(Yp+1)+0.5)= a(Xp+2)+b(Yp+1.5)+c =d+a+b d的增量为a+bMP1P2MP1P2分两种情形考虑再下一个像素的判定：分两种情形考虑再下一个像素的判定：l画线从(x0, y0)开始，d的初值d0=F(x0+1, y0+0.5) = a(x0 +1)+b(y0 +0.5)+c = F(x0, y0)+a+0.5b = a+0.5b 由于只用d 的符号作判断，为了只包含整数运算, 可以用2d代替d来摆脱小数，提高效率。l优点：只有整数运算，不含乘除法可用硬件实现中点画

8、线法中点画线法因因(X0,Y0)在直线上，在直线上，所以所以F(X0,Y0)=0void 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, y, color); /* while */

9、/* 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)=60 1 2 3 4 5321I xi yi d 1 0 0 12 1 0 -33 2 1 34 3 1 -15 4 2 56 5 2 1Bresenham算法算法l基本思想过各行各列像素中心构造一组虚拟网格线。按直线从起点到终点的顺序计算直线与各垂直网格线的交点，然后根据误差项的符号确定该列像素中与此交点最近的像素。dddd设直线方程为： ，其中k=dy/dx。 因为直线的起始点在像素中心，

10、所以误差项d的初值d00。X下标每增加1，d的值相应递增直线的斜率值k，即ddk。一旦d1，就把它减去1，这样保证d在0、1之间。当d0.5时时，最接近于当前像素的右上方像素（xi1，yi1）而当当d0.5时时，更接近于右方像素（xi1，yi）。为方便计算，令ed-0.5，e的初值为-0.5，增量为k。当e0时时，取当前像素（xi，yi）的右上方像素（xi1，yi1）；而当当e0，则(x,y)更新为(x+1,y+1)，同时将e更新为e-1；否则(x,y)更新为(x+1,y)。5.当直线没有画完时，重复步骤3和4。否则结束。Bresenham算法算法 程序如下： BresenhamLine(in

11、t x0,int y0,int x1,int y1,int color) int x,y,dx,dy; float k,e; dx = x1-x0; dy = y1-y0; k = dy/dx; e = -0.5; x=x0; y=y0; for( i=0; i=0) y+;e=e-1; Bresenham算法算法例：Line: P0(0, 0), P1(5,2) k=dy/dx=0.40 1 2 3 4 5321x y e0 0 -0.51 0 -0.12 1 -0.73 1 -0.34 2 -0.95 2 -0.5缺点缺点： 在此算法中，计算直线斜率与误差项时用到了小数与除法，不利于硬件实

12、现。可以改用整数以避免除法。Bresenham算法算法改进改进：用2ex来替换ele初=-x，l每走一步有e=e+2y。lif (e0) then e=e-2x算法步骤算法步骤：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更新为e-2x；否则(x,y)更新为(x+1,y)。5.当直线没有画完时，重复步骤3和4。否则结束。Bresenham算法算法 程序如下： BresenhamLine(int x0,int y0,i

13、nt x1,int y1,int color) int x,y,dx,dy,e; dx = x1-x0; dy = y1-y0; e = -dx; x=x0; y=y0; for( i=0; i=0) y+;e=e-2*dx; l优点整数运算，速度快精度高乘2运算可用移位实现，适于硬件实现斜率不同时： 以上讨论的是 0 k 1 的情况，即 0yx 的情况； 若是 0 xy 的情况，则需将 x 和 y 的位置交换。方向不同时： 若y0或x0时，要将算法中的 yy1换成yy1、 xx1换成xx1。思考讨论：思考讨论：几种画线算法的比较lDDA算法直观，易于实现，但是x、y、和k必须用浮点数表示，而

14、且每一步都需要对x和y进行舍入取整，不利于硬件实现。l中点算法可以替换成整数运算，便于硬件实现。lBresenham算法不计算斜率，不用浮点数，只做整数的加减运算或乘2运算，而乘2运算可以用移位操作来实现，因此Bresenham算法是速度最快的。实验一实验一 直线的生成直线的生成l在Visual C+6.0环境中设计MFC单文档程序，利用消息处理函数，搭建能运行图形算法程序的平台。l实现直线段的3种生成算法：DDA算法(考虑k大于或小于等于1的情况)、中点法和Bresenham算法（原算法和改进算法）。 第二章第二章 光栅图形学光栅图形学 2.1 2.1 直线段的扫描转换算法直线段的扫描转换算

15、法2.2 2.2 圆弧的扫描转换算法圆弧的扫描转换算法2.3 2.3 多边形的扫描转换与区域填充多边形的扫描转换与区域填充2.4 2.4 字符字符2.5 2.5 裁剪裁剪2.6 2.6 反走样反走样2.7 2.7 消隐消隐2.2 圆弧的扫描转换算法圆弧的扫描转换算法直接离散生成算法中点画圆法Bresenham画圆算法椭圆的中点画法圆弧扫描算法圆弧扫描算法yx(-x,y)(x,y)(-y,x)(y,x)(y,-x)(-y,-x)(-x,-y)(x,-y)oRl下面仅以圆心在原点、半径R为整数的圆为例，讨论圆的生成算法。 假设圆的方程为： x2+y2=R2 l圆的八对称性可以用四条对称轴x0，y0

16、， x y，xy把圆分成8等份。只要绘制出第一象限内的1/8圆弧，根据对称性就可绘制出整圆，这称为八八分法画圆算法分法画圆算法。(x,y)yy=-xy=x(y,x)(-y,x)(-x,y)(-x,-y)(-y,-x)(y,-x)(x,-y)P（y，x） P（y，x）, P（x, y ） , P（x，y），），P（y，x），），P（y，x），），P（x，y）。）。假定第一象限内的任意点为假定第一象限内的任意点为P（x，y），可以确定另外），可以确定另外7个点：个点：圆弧扫描算法圆弧扫描算法22)(xxryyccyxl两种直接离散生成方法离散点l开方运算离散角度l三角函数运算l缺点：计算量大所画像

17、素位置间的间距不一致、 不均匀iciiciryyrxxsincos圆弧扫描算法圆弧扫描算法lSimpleCircle (int r, int color) int x,y; for （x=0; x=r;x+) y=Round(sqrt(r*r-x*x)； circlepoints(x,y,color); lParameterCircle (int r, int color) int x,y; for （float t=0; t= /2;t+=0.05) x=Round(r*cos(t)； y=Round(r*sin(t)； circlepoints(x,y,color); 第二个8分圆P（Xp

18、 ，Yp ）P为当前点亮像素，那么，下一个点亮的像素可能是P1（Xp+1，Yp）或P2（Xp +1，Yp -1)。MP1P2中点画圆法中点画圆法中点画圆法中点画圆法lF(X,Y)=X2+Y2-R2=0l中点 M=(Xp+1,Yp-0.5)l当F(M)0时，M在圆内，P1距离圆弧近，取P1l当F(M)0时，M在圆外，P2距离圆弧近，取P2MP1P2222)5 . 0() 1()5 . 0, 1()(RyxyxFMFdpppp中点画圆法中点画圆法l 若 d=0, 取P1为下一像素，再下一像素的判别式为l 初始像素是（0,R），判别式d的初值为32)5 . 0()2()5 . 0, 2(222ppp

19、ppxdRyxyxFd5)(2)5 . 1()2()5 . 1, 2(222ppppppyxdRyxyxFdRRFd25. 1)5 . 0, 1 (0P=(xp,yp)P1P2MP1(Xp+1,Yp)P2(Xp+1,Yp-1)算法步骤算法步骤：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.当xy时，重复步骤3和4。否则结束。中点画圆法（一般算法）中点画

20、圆法（一般算法） MidpointCircle(int r, int color) int x,y; float d; x=0; y=r; d=1.25-r; circlepoints(x,y,color); while(xy) if(d0) d+ = 2*x+3; x+ else d+ = 2*(x-y) + 5; x+;y-; circlepoints(x,y,color); 中点画圆法（一般算法）中点画圆法（一般算法）思考题：思考题：如何将上面算法中的浮点如何将上面算法中的浮点数改写成整数，将乘法运算改成加数改写成整数，将乘法运算改成加法运算，即仅用整数实现中点画圆法运算，即仅用整数实现

21、中点画圆法，以进一步提高算法的效率？法，以进一步提高算法的效率？l为了进一步提高算法的效率，可以将上面的算法中的浮点数改写成整数，将乘法运算改成加法运算，即仅用整数实现中点画圆法。l因为中点画圆算法的半径是整数，而用于该算法符号判别的变量d采用浮点运算，会花费较多的时间。为了将其改造成整数计算，对d作如下变换：使用d=d-0.25代替dld=1-Rl判别式d0等价于d-0.25,在d为整数的情况下，d-0.25与d0等价，仍将d写成d，可得到中点圆整数算法中点画圆法中点画圆法算法步骤算法步骤：1.输入圆的半径R。2.计算初始值d=1-R、x=0、y=R。3.绘制点(x,y)及其在八分圆中的另外

22、七个对称点。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.当xy时，重复步骤3和4。否则结束。程序程序中点画圆法（整数算法）中点画圆法（整数算法） MidpointCircleInt(int r, int color) int x,y,d; x=0; y=r; d=1-r; circlepoints(x,y,color); while(xy) if(d0) d+ = 2*x+3; x+ else d+ = 2*(x-y) + 5; x+;y-; circlepoints

23、(x,y,color); 中点画圆法（整数算法）中点画圆法（整数算法） 如图中点Pi-1是已选中的一个表示圆弧上的点，根据弧的走向，下一个点应该从Hi或者Li中选择。选择的原则是：考察精确值是靠近Hi还是Li ，即精确值y是靠近yi还是yi-1 假设圆的半径为R，计算式为 y2=R2- (xi+1)2 令d1、d2分别为yi(Hi)到y和yi-1(Li)到y的距离，可知： d1=yi2- y2 = yi2-R2+ (xi+1)2 d2=y2-(yi-1) 2 =R2 - (xi+1)2 - (yi-1) 2 Bresenham画圆算法画圆算法（1）如果）如果di0，则，则y=yi，即选择当前像

24、素的正右方作为下一即选择当前像素的正右方作为下一个像素，递推公式为：个像素，递推公式为：（2）如果）如果di0，则，则y=yi-1，即选择当前像素的右下方作为下，即选择当前像素的右下方作为下一个像素，递推公式为：一个像素，递推公式为：（3）计算判别式的初值。初始点为（）计算判别式的初值。初始点为（0，R），则：），则：641111iiiiiiixddyyxx10)(411111iiiiiiiiyxddyyxxRRRRd232) 1(2222022222) 1() 1(2ryyxdiiii令判断式di=d1-d2，并代入d1、d2，则有：Bresenham画圆算法画圆算法l算法步骤算法步骤：1.

25、求误差初值d1=3-2r，i=1，画点（，画点（0，r）。2.求下一个光栅位置，其中xi+1=xi+1 ，如果di0则则yi+1=yi ，否则， yi+1=yi-1 。3.画点（xi+1，yi+1）。4.计算下一个误差，如果di0，中点在椭圆外，取右下方像素Pd(xi+1,yi-1)p(xi,yi)pu(xi+1,yi)pd(xi+1,yi-1)M(xi+1,yi-0.5)上半部分椭圆弧的绘制原理0),(222222bayaxbyxF判别式递推公式为：判别式递推公式为：d10：(a) d0： )22() 32( )22() 32()5 . 0() 1( )5 . 1()2()5 . 1, 2(

26、221222222222222221iiiiiiiiiiyaxbdyaxbbayaxbbayaxbyxFd(b) d0的情况Pxixi+2xi+1yi-1yiyi-2判别式递推公式为：判别式递推公式为：判别式的初始值判别式的初始值 )25. 0( )5 . 0()5 . 0, 1 (222222210babbababbFdp(xi,yi)pl(xi,yi-1)pr(xi+1,yi-1)M(xi+1,yi-0.5)下半部分椭圆弧的绘制原理再来推导椭圆弧下半部分的绘制公式原理原理设椭圆当前点为pi(xi,yi),对应的下一候选像素是正下方的pl(xi,yi-1),或右下方的pr(xi+1,yi-1

27、),判别式判别式 其中点是其中点是M(xi+0.5,yi-1)2222222) 1()5 . 0() 1, 5 . 0(bayaxbyxFdiiii若d20，中点在椭圆外，取正下方像素Pl(xi,yi-1)若d20，中点在椭圆内，取右下方像素Pr(xi+1,yi-1)p(xi,yi)pl(xi,yi-1)pr(xi+1,yi-1)M(xi+1,yi-0.5)下半部分椭圆弧的绘制原理0),(222222bayaxbyxF判别式递推公式为：判别式递推公式为：d20：)y(ad )y(aba)(ya)(xb ba)(ya)(xb),yF(xdiiiiiiii323215 . 025 . 025 . 0 2222222222222222(a) d0的情况Pxiyi-2xi+1yiyi-1xi+2d20：) 32()22( ) 32()22() 1()5 . 0( )2()5 . 1()2, 5 . 1(222222222222222222iiiiiiii