第三章二维图形的生成_直线和圆

1、2022-7-2西安工程大学计算机图形学1第四章、二维图形的生成和变换第四章、二维图形的生成和变换4.1、直线段的扫描转换算法 4.1.1、DDA算法 4.1.2、中点画线法 4.1.3、Bresenham画线算法4.2、圆弧扫描转换算法 4.2.1、中点算法 4.2.2、Bresenham画圆算法 4.2.3、生成圆弧的正负法4.3、椭圆弧生成算法 2022-7-2西安工程大学计算机图形学2 对一维图形，不考虑线宽，则用一个像素宽的直线来显示图形。二维图形的光栅化，即区域的填充：确定像素集，填色或图案。 任何图形的光栅化，必须显示在一个窗口内，否则不予显示。即确定一个图形的哪些部分在窗口内，

2、哪些在窗口外，即裁剪。 图形的扫描转换（光栅化）：确定一个像素集合，用于显示一个图形的过程。步骤如下：1、确定有关像素2、用图形的颜色或其它属性，对像素进行写操作2022-7-2西安工程大学计算机图形学3图形显示前需要：扫描转换+裁剪u裁剪-扫描转换：最常用，节约计算时间。u扫描转换-裁剪：算法简单；2022-7-2西安工程大学计算机图形学4v图形显示器是由一个个排列有序的像素构成，划分的像素点越多分辨率就越高。例如640X480的显示器，分成640X480个网格，网格单元视为像素，一条线段就是由一些连续可见的像素所组成，如下图所示：4.1 直线段的扫描转换算法v在数学上，理想的直线是没有宽度

3、的，是由无数个在它上面的点构成的集合。直线可以向一个方向及其相反的方向无限延长。v在图形学中研究的对象是直线段，它是一条具有一个Pixel或多个Pixel宽的直线段。2022-7-2西安工程大学计算机图形学5由上图可知：由上图可知：画一条直线实际上就是根据一系列计算出来并与画一条直线实际上就是根据一系列计算出来并与该直线靠近的像素绘制的该直线靠近的像素绘制的。Line: P0(0,0)P1(5,2)0143215234各行各列像素中心构成的一组虚拟网格线像素单元4.1 直线段的扫描转换算法直线段的扫描转换算法0123456 701234562022-7-2西安工程大学计算机图形学6v直线的扫描

4、转换直线的扫描转换: : 确定最佳逼近于该直线的一组象素，并且按扫描线顺序，对这些象素进行写操作。v直线段是最基本的图形，因此直线段生成的质量好直线段是最基本的图形，因此直线段生成的质量好坏与速度快慢将直接影响整个图形生成的质量和速坏与速度快慢将直接影响整个图形生成的质量和速度。度。v三个常用算法：数值微分法（DDA）中点画线法Bresenham算法。4.1 直线段的扫描转换算法直线段的扫描转换算法2022-7-2西安工程大学计算机图形学74.1.1、数值微分法（） 假定直线的起点、终点分别为:(x0,y0),(x1,y1)，且都为整数。栅格交点表示象素点位置(X i+1 ,Yi + k)(X

5、 i , Yi)4.1 直线段的扫描转换算法直线段的扫描转换算法2022-7-2西安工程大学计算机图形学8v基本思想 已知直线L两端点位P0 (x0, y0), P1(x1, y1)4.1 直线段的扫描转换算法直线段的扫描转换算法kdxdy斜率即0101xxyyxy可以通过x方向的增量x，计算y的增量y来生成直线。yyyii 1xxxyyyyii0101101011xxyyyyii当1x得4.1.1、数值微分法（）2022-7-2西安工程大学计算机图形学9v即：当x方向每递增1像素，y方向递增k(即直线斜率)；每次通过上式计算出（xi，yi）取整后输出显示器。v注意上述分析的算法仅适用于k 1

6、的情形。在这种情况下，x每增加1,y最多增加1。4.1 直线段的扫描转换算法直线段的扫描转换算法01011xxyyyyii当1x得4.1.1、数值微分法（）2022-7-2西安工程大学计算机图形学10v注：当 时，必须把x,y位置互换，即利用递推式 ，y每增加1，x相应增加 。所以取 和 中较大者为步进方向，如下图1 kykxxii 11k112xx 12yy 1k 当时x为步进方向为步进方向y为步进方向为步进方向4.1 直线段的扫描转换算法直线段的扫描转换算法2022-7-2西安工程大学计算机图形学110 1 2 3 4 5321Line: P0(0, 0)- P1(5, 2)v例：画直线段

7、P0(0,0)-P1(5,2) k=0.4 x y+k 四舍五入int（y+0.5) 0 0 0 1 0.4 0 2 0.8 1 3 1.2 1 4 1.6 2 5 2 24.1 直线段的扫描转换算法直线段的扫描转换算法4.1.1、数值微分法（）2022-7-2西安工程大学计算机图形学12void 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+) putpixel (x, int(y+0.5

8、), color); y=y+k; 4.1 直线段的扫描转换算法直线段的扫描转换算法4.1.1、数值微分法（）2022-7-2西安工程大学计算机图形学13v增量算法：在一个迭代算法中，如果每一步的x、y值是用前一步的值加上一个增量来获得，则称为增量算法。vDDA算法就是一个增量算法。4.1 直线段的扫描转换算法直线段的扫描转换算法v该算法的优点是绘制实数直线效果好，误差小。缺点是实现较复杂，不利于硬件实现。v该算法涉及到实数乘除法运算，y与k必须用浮点数表示，而且每一步都要对y进行四舍五入后取整。4.1.1、数值微分法（）2022-7-2西安工程大学计算机图形学144.1.2、中点画线法v原理

9、：假定直线斜率0K P2离直线更近更近-取P2 。M在Q的上方- P1离直线更近更近-取P1M与Q重合， P1、P2任取一点。问题：如何判断M与Q点的关系？P=(xp,yp)QP2P1M4.1 直线段的扫描转换算法直线段的扫描转换算法4.1.2、中点画线法2022-7-2西安工程大学计算机图形学16欲判断中点M点是在Q点上方还是在Q点下方，只需把M代入F(x,y),并检查它的符号。在直线下方点在直线上方点在直线上面点),(0,),(0,),(0,yxyxFyxyxFyxyxFP=(xp,yp)QP2P1M4.1 直线段的扫描转换算法直线段的扫描转换算法4.1.2、中点画线法 假设直线方程为：a

10、x+by+c=0 其中a=y0-y1, b=x1-x0, c=x0y1-x1y02022-7-2西安工程大学计算机图形学17当d=0，选P1或P2均可，约定取P1；P=(xP=(xp p,y,yp p) )QP P2P P14.1 直线段的扫描转换算法直线段的扫描转换算法4.1.2、中点画线法构造判别式： d=F(M)=F(xp+1,yp+0.5) =a(xp+1)+b(yp+0.5)+c当d0，M在直线(Q点)上方，取右方P1；能否采用增量算法呢？M2022-7-2西安工程大学计算机图形学18情形1.若d0 -M在直线上方-取P1; 此时再下一个象素的判别式为 d1=F(xp+2, yp+0

11、.5)=a(xp+2)+b(yp+0.5)+c = a(xp +1)+b(yp +0.5)+c +a =d+a； 即d的增量为a,QP2P14.1 直线段的扫描转换算法直线段的扫描转换算法P=(xP=(xp p,y,yp p) )M4.1.2、中点画线法2022-7-2西安工程大学计算机图形学19情形2.若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 ；即d的增量为abP=(xp,yp)QP2P14.1 直线段的扫描转换算法直线段的扫

12、描转换算法M4.1.2、中点画线法2022-7-2西安工程大学计算机图形学20 画线从(x0, y0)开始，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 来摆脱小数，提高效率。4.1 直线段的扫描转换算法直线段的扫描转换算法即d02*a+b 若d 0 增量为2*a 若d0 增量为2*(a+b)4.1.2、中点画线法2022-7-2西安工程大学

13、计算机图形学210 1 2 3 4 5321例：用中点画线法P0(0,0) P1(5,2) a=y0-y1=-2 b=x1-x0=5 d0=2a+b=1 d1=2a=-4 d2=2(a+b)=6 ixiyid 1001 210-3 3213 431-1 54254.1 直线段的扫描转换算法直线段的扫描转换算法4.1.2、中点画线法2022-7-2西安工程大学计算机图形学22中点画线法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=

14、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 */ /* mid PointLine */4.1 直线段的扫描转换算法直线段的扫描转换算法2022-7-2西安工程大学计算机图形学234.1.3、直线的Bresenham算法 4.1 直线段的扫描转换算法直线段的扫描转换算法 算法原理：过各行各列象素中心构造一组虚拟网格线。按直线从起点到终点的顺序计

15、算直线与各垂直网格线的交点，然后确定该列象素中与此交点最近的象素。该算法的巧妙之处在于采用增量计算，使得对于每一列，只要检查一个误差项的符号，就可以确定该列的所求象素。 2022-7-2西安工程大学计算机图形学24 为了讨论方便，我们假定直线的斜率在01之间，其它情况类似处理如右图所示，设直线方程为 ),(iiyx其中k=dy/dx。 假设当前象素已经确定为(xi, yi)那么下一个象素的列坐标为xi1，而行坐标要么不变为yi，要么递增1为yi1。 xkyxxkyyiiiii )(11yx4.1 直线段的扫描转换算法直线段的扫描转换算法4.1.3、直线的Bresenham算法 bkxy则有20

16、22-7-2西安工程大学计算机图形学25 是否增1取决于如图所示误差项 d 的值。因为直线的起始点在象素中心，所以误差项 d 的初值d00 因为x 每增加1，d 的值相应递增直线的斜率值 k，即ddk。1、当d0.5时，直线与xi1列垂直网格交点最接近的象素为 右上方象素（xi+1，yi1）；）； 2 2、当d0.5时，更接近直线的为正右方象素（xi1，yi）。 4.1 直线段的扫描转换算法直线段的扫描转换算法注：一旦y方向上走一步，d=d-1。图5-8 改进的Brensemham算法绘制直线的原理ddddkkkkk2022-7-2西安工程大学计算机图形学26为方便计算，令ed0.5，e 的初

17、值为0.5，增量为 k。结论：1. d 的初值d00， ddk；2.当 d 0.5时，下一个像素取为，右上方象素（xi+1，yi1）；）；3.当 d 0.5时，下一个像素取为 正右方象素（xi1，yi）。）。 2.2.当e00，则(x,y)更新为(x+1,y+1)，同时将e更新为e-1；否则(x,y)更新为(x+1,y)。5.当直线没有画完时，重复步骤3和4。否则结束。2022-7-2西安工程大学计算机图形学28 举例举例1:用用BresenhamBresenham方法扫描转换连接两点方法扫描转换连接两点P0（0,0）和和P1（5,2）的直线段的直线段。斜率斜率K=2/5=0.4e0=-0.5

18、 e=d-0.5 , d=d+k, k=dy/dx当当e0时，取当前像素的右上方像素为下一个像素时，取当前像素的右上方像素为下一个像素当当e0时，取当前像素的正右方像素为下一个像素时，取当前像素的正右方像素为下一个像素4.1 直线段的扫描转换算法直线段的扫描转换算法0143215234xe y e-10 0.5 01 0.1 02 0.3 1 0.73 0.3 14 0.1 2 0.95 0.5 22022-7-2西安工程大学计算机图形学29Bresenham画线算法参考程序画线算法参考程序 (0k1)：void Bresenhamline (int x0,int y0,int x1, int

19、 y1,int color) q int x,y,i;q float dx, dy ,k, e;q dx = x1-x0, dy = y1- y0, k=dy/dx;q e=-0.5, x=x0, y=y0;p for (i=0; i=0) y+, e=e-1;p p 4.1 直线段的扫描转换算法直线段的扫描转换算法因为因为一旦一旦y方向上走方向上走一步，就减去一步，就减去1。没有摆脱浮点没有摆脱浮点数计算数计算2022-7-2西安工程大学计算机图形学30v 上述bresenham算法在计算误差项与直线斜率时用到小数与除法。可以改用整数以避免除法。由于算法中只用到误差项的符号，因此可作如下替换

20、： xyxyee210改进的Bresenham画线算法程序：4.1 直线段的扫描转换算法直线段的扫描转换算法yxex22xee 2xe0递增量递增量y2初始量初始量原先原先10eeexxexe222即即xeee202022-7-2西安工程大学计算机图形学31void Bresenhamline (int x0,int y0,int 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; 2022-7-2西安工程大学计算机图

21、形学32Bresenham Bresenham 算法的优点算法的优点是：是：1 1、不必计算直线之斜率，因此不做除法；、不必计算直线之斜率，因此不做除法；2 2、不用浮点数，只用整数；、不用浮点数，只用整数；3 3、只做整数加减法和乘、只做整数加减法和乘2 2运算，运算， 而乘而乘2 2运算可以用硬件移位实现。运算可以用硬件移位实现。Bresenham Bresenham 算法速度很快，并适于用硬件实现算法速度很快，并适于用硬件实现。4.1 直线段的扫描转换算法直线段的扫描转换算法4.1.3、直线的Bresenham算法 2022-7-2西安工程大学计算机图形学33(1)(1)上述算法只对斜率

22、在上述算法只对斜率在0101之间的直线段生成适合，之间的直线段生成适合， 当直线的斜率大于当直线的斜率大于1 1时，算法应该如何改进时，算法应该如何改进? ?Max xMax y(0,0)(50,20)Max yMax x(0,0)(50,20)dddd注意：此时注意：此时d d或或e e的增量为的增量为 kk1 kdd1 几点讨论和思考几点讨论和思考4.1 直线段的扫描转换算法直线段的扫描转换算法2022-7-2西安工程大学计算机图形学34pfor(i=0;i=0)p x=x+1;p e=e-1;p pv(2)(2)Bresenham画线算法参考程序画线算法参考程序 (k1)：vBresen

23、ham_line (int x0,int y0,int x1,int y1, int color)vint x,i,y;v float dx,dy,k,k1,e;v dx=x1-x0;v dy=y1-y0;v k=dy/dx;v k1=1/k;v e=-0.5;v x=x0;v y=y0;4.1 直线段的扫描转换算法直线段的扫描转换算法2022-7-2西安工程大学计算机图形学35v(3)(3)根据上述的思想，我们如何将算法扩展到，任根据上述的思想，我们如何将算法扩展到，任一八分圆坐标空间图，从而形成一般一八分圆坐标空间图，从而形成一般BresenhamBresenham算算法？法？ 如下图：如

24、下图：4.1 直线段的扫描转换算法直线段的扫描转换算法v(4)(4)适用于任意斜率的适用于任意斜率的BresenhamBresenham直线生成算法直线生成算法程序示例程序示例2022-7-2西安工程大学计算机图形学364.2 圆的扫描转换算法 下面仅以圆心在原点、半径R为整数的圆为例，讨论圆的生成算法。假设圆的方程为： X2 + Y2 = R2 若圆心不在原点可以通过坐标变换画出任意位置的圆。2022-7-2西安工程大学计算机图形学374.2.1圆弧扫描算法 X2 + Y2 = R2 Y = Sqrt(R2 - X2)在一定范围内，每给定一X值，可得一Y值。当X取整数时，Y须取整。缺点：浮点

25、运算，开方，取整，不均匀。yx2022-7-2西安工程大学计算机图形学384.2.2 角度DDA法 xn+1 = x n + dx = x n R sin d =x n (y ny 0 )d y n+1 = y n + dy = y n + R cos d =y n + (x nx 0 )d 给定圆上的初始值x1，y1及d值后，即可以增量方式获得圆周上的坐标，然后取整可得象素坐标。但要采用浮点运算、乘法运算、取整运算。圆的极坐标方程 x = x0 + Rcos y = y0 + Rsin 求微分 dx = Rsin d dy = Rcos d 记 xn+1xn dx yn+1yn dy2022

26、-7-2西安工程大学计算机图形学394.2.3 中点画圆法第二个8分圆P为当前点亮象素，那么，下一个点亮的象素可能是P1(Xp+1，Yp)或P2(Xp +1，Yp 1)。MP1P2P（Xp ，Yp ）利用圆的对称性，只须讨论1/8圆。XYY=XY=-X2022-7-2西安工程大学计算机图形学40构造判别函数： 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)MP1P24.2.3 中点画圆法2022-7-2西安工程大学计算机图形学41有如下结论： F(M) = 0

27、 M在圆外 取P2为此，可采用如下判别式： MP1P2P(xp,yp)4.2.3 中点画圆法2022-7-2西安工程大学计算机图形学42 d = 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）+（-2 yp + 2）即即d 的增量为的增量为 2 (xp - yp) +5. d的

28、初值的初值:d0 = F(1, R-0.5)= 1 + (R-0.5)2 - R2 即即：d0 = 1.25 - RMP1P2P2P(xp,yp)4.2.3 中点画圆法2022-7-2西安工程大学计算机图形学44 MidpointCircle(int r, int color) int x,y; float d; x=0; y=r; d=1.25-r; putpixel(x,y,color); while(xy) if(d=0)v putpixel(x,y,color);v if(deltaD0)v deltaHD=2*(deltaD+y)1;v if(deltaHD0) vdeltaDV=2

29、*(deltaD-x)-1; if(deltaDV=0)direction=2;velse direction=3; else direction=2;switch(direction) v case1: x+;v deltaD+=2*x+1;v break;case2: x+; y-; deltaD+=2*(x-y+1); break;case3: y-; deltaD+=(-2*y+1); break; /*switch*/ /*while*/*Bresenham_Ciecle*/HDVDV2022-7-2西安工程大学计算机图形学66Bresenham画圆算法 现在从(0,R)点开始向右下

30、方逐点来寻找圆弧上的点。如图中点Pi是已选中的一个表示圆弧上的点，根据圆弧的走向，下一个点应该从Hi或者Li中选择。显然应选离圆弧最近的点作为显示圆弧的点。PiHiLi假设圆的半径为R，显然，当 xhi2 + yhi2 -R2 R2 - (xli2 + yli2)时应该取Li。否则取Hi。令di = xhi2 + yhi2 + xli2 + yli2 2R2 显然， 当di 0 时应该取Li。否则，取Hi。2022-7-2西安工程大学计算机图形学67di = (xi+1)2+yi2+(xi+1)2 +(yi-1)2-2R2 =2(xi+1)2 + 2yi2 - 2yi +1- 2R2 当当di

31、0 -取取Hi ( (xi+1,+1,yi) ) ，则，则PiHiLi 下步就是如何快速的计算di。设图中Pi的坐标(xi,yi)则Hi 和Li 的坐标为(xi+1,yi)和(xi1,yi-1 )di+1=(xi+1+1)2+yi2+(xi+1+1)2+(yi-1)2- 2R2 =2(xi+1)2+ 2yi2 - 2yi +1 - 2R2 + 4xi + 6 =di + 4xi + 6Bresenham画圆算法2022-7-2西安工程大学计算机图形学68当当d di i00时时-取取L Li i(x(xi i1,y1,yi i-1 )-1 ) ，则，则 di+1+1 = ( = (xi +1+

32、1)+1+1)2 2 +( +(yi-1)-1)2 2 + + ( (xi+1+1)+1+1)2 2 +( +(yi-1-1)-1-1)2 2 - -2R2 2 = =di + 4( + 4(xi - - yi)+10 )+10 PiHiLi 易知易知 x0 0=0=0，y0 0= =R, ,x1 1= =x0 0+1+1 因此因此 d0 0=12 2 + +y0 02 2+1+12 2+(+(y0 0-1)-1)2 2 - -2R2 2 = 3 - 2 = 3 - 2y0 0 = 3 - 2 = 3 - 2RBresenham画圆算法2022-7-2西安工程大学计算机图形学69生成圆弧的正负

33、法 原理： 设圆的方程为F(x,y)=X2+ Y2- - R2=0; 假设求得Pi的坐标为(xi,yi)；则 当Pi在圆内时- F(xi , yi) 向右- 向圆外 当Pi在圆外时- F(xi , yi)0 - 向下- 向圆内2022-7-2西安工程大学计算机图形学70即求得Pi点后选择下一个象素点Pi+1的规则为： 当F(xi,yi) 0 取xi+1 = xi+1，yi+1 = yi; 当F(xi,yi) 0 取xi+1 = xi， yi+1 = yi - 1; 这样用于表示圆弧的点均在圆弧附近，且使F(xi,yi) 时正时负，故称正负法。 快速计算的关键是F(xi,yi) 的计算，能否采用

34、增量算法？ 生成圆弧的正负法2022-7-2西安工程大学计算机图形学71v若若F(xF(xi i,y,yi i) ) 已知，计算已知，计算F(xF(xi+1i+1,y,yi+1i+1) ) 可分两种可分两种情况：情况：v1 1、F(xF(xi i,y,yi i)0- x)0- xi+1i+1 = x = xi i+1+1，y yi+1i+1 = y = yi i; ;v - F(x - F(xi+1i+1,y,yi+1i+1)= (x)= (xi+1 i+1 ) )2 +(y+(yi+1i+1 ) )2 -R-R2v - = (x- = (xi i+1)+1)2+ y+ yi i2 -R-R2

35、 = F(x= F(xi i,y,yi i) +2x) +2xi i +1+1v2 2、 F(xF(xi i,y,yi i) )0- x0- xi+1i+1 = x = xi i，y yi+1i+1 = y = yi i -1;-1;v - F(x - F(xi+1i+1,y,yi+1i+1)= (x)= (xi+1 i+1 ) )2 +(y+(yi+1i+1 ) )2 -R-R2v - = x- = xi i2+(y+(yi i 1)1)2-R-R2 = F(x= F(xi i,y,yi i) - 2y) - 2yi i +1+1v3 3、初始值：略、初始值：略生成圆弧的正负法2022-7-

36、2西安工程大学计算机图形学724.3 椭圆的扫描转换vF(x , y)=b2x2+a2y2-a2b2=0v椭圆的对称性，只考虑第一象限椭圆弧生成，分上下两部分，以切线斜率为-1的点作为分界点.也就是法向量中x 和y 分量相等的点.v椭圆上一点处的法向：N(x,y) = Fx i + Fy j = 2b2 x i + 2a2 y j上半部分上半部分下半部分下半部分2022-7-2西安工程大学计算机图形学73上半部分,法向量的y 分量大。法向量法向量两分量相等两分量相等在当前中点处，法向量（ 2b2 (Xp+1) ，2a2 (Yp-0.5)的y分分量量比x分量分量大,即： b2 (Xp+1) =0

37、=0，中点在椭圆外，取正下方象素，判别式更新为： d2= =F F(X(Xp+0.5,Y+0.5,Yp-2)=-2)=d2+ +a2 2(3-2Y(3-2Yp) )d2的增量为的增量为a2(3-2Y Yp).4.3 椭圆的扫描转换vd1的初始值：椭圆弧起点为(0，b)；第一个中点为(1,b-0.5) .初始判别式：d10=F(1,b-0.5)=b*b+a*a(-b+0.25)v转入下部分，下一象素可能是正下方或右下方，此时判别式要初始化。假定上半部分最后一像素为(xp,yp),下一步像素的中点即为: (xp+0.5,yp-1), d20=F(xp+0.5,yp-1)=b2(xp+0.5)2+a

38、2(yp-1)2-a2b2v下半部分弧的终止条件为 y = 02022-7-2西安工程大学计算机图形学78程序：MidpointEllipe(a,b, color)int a,b,color; int x,y; float d1,d2; x = 0; y = b; d1 = b*b +a*a*(-b+0.25); putpixel(x,y,color); while( b*b*(x+1) a*a*(y-0.5) if (d10) if (d2 0) d2 +=b*b*(2*x+2)+a*a*(-2*y+3); x+; y-； else d2 += a*a*(-2*y+3); y-; putpixel(x,y,color); 一、反走样技术的定义和概述 前面介绍的各种光栅化算法，除水平或垂直的直线外或多或少会产生锯齿或阶梯状，如图所示。由于直线和多边形边界的数学描述是连续的，而在光栅显示器中，像素点是占有一定面积是离散的。我们把这种用离散量表示连续量引起的失真称为走样(Aliasing)。走样是数字化发展的必然产物。所谓的反走样(Antialiasing)技术，就是减缓或者消除走样效果的技术。 4.4反走样技术 第一类方法是通过提高采样频率(提高光栅分辨率)