计算机图形学3-基本图形的扫描转换

1、SetPixelBresenhamo3.1 3.1 直线的扫描转换直线的扫描转换o3.2 3.2 圆的扫描转换圆的扫描转换o3.3 3.3 椭圆的扫描转换椭圆的扫描转换o3.4 3.4 反走样算法反走样算法o3.6 3.6 本章小结本章小结o3.7 3.7 习题习题4什么是扫描转换？直线、圆、椭圆是图形设计的最基本的图形（图元）。图形的扫描转换（光栅化）：在像素点阵中确定最佳逼近于理想图形的像素占集的过程。 5o 步骤如下：n1、确定有关像素n2、用图形的颜色或其它属性，对像素进行写操作。o 对一维图形，不考虑线宽，则用一个像素宽的直线来显示图形。o 二维图形的光栅化，即区域的填充：确定像素集

2、，填色或图案。o 任何图形的光栅化，必须显示在一个窗口内，否则不予显示。即确定一个图形的哪些部分在窗口内，哪些在窗口外，即裁剪。 6图形显示前需要：扫描转换+裁剪裁剪-扫描转换：最常用，节约计算时间。扫描转换-裁剪：算法简单；o 直线的扫描转换直线的扫描转换: 确定最佳逼近于该直线的一组象素，并且按扫描线顺序，对这些象素进行写操作。o 三个常用算法：数值微分法（DDA）中点画线法Bresenham算法。8数值微分法（） 假定直线的起点、终点分别为：（x0,y0), (x1,y1)，且都为整数。(X i+1 ,Yi + k)(X i , Int(Yi +0.5)(X i , Yi)栅格交点表示象

3、素点位置。9o基本思想已知过端点P0 (x0, y0), P1(x1, y1)的直线段Ly=kx+b直线斜率为设x=x1-x0, y=y1-y0设 x y0,让x从起点到终点变化，每步递增1个像素，计算对应的y坐标。0101xxyyk10计算yi+1= kxi+1+b=k(xi+1)+b = kxi+b+k = yi+k o 即：当x每递增1个像素，y递增k(即直线斜率)；o 注意上述分析的算法仅适用于k 1的情形。在这种情况下，x每增加1,y最多增加1。o 当 k 1时，必须把x，y地位互换，怎么实现？11o 增量算法：在一个迭代算法中，如果每一步的x、y值是用前一步的值加上一个增量来获得，

4、则称为增量算法。o DDA算法就是一个增量算法。这种方法直观，但效率太低，因为每一步需要一次浮点乘法和一次舍入运算。 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+) drawpixel (x, int(y+0.5), color); y=y+k; 13o 例：画直线段P0(0,0)-P1(5,2)x int(y+0.5) y+0.5000+0.5100.4+0.5210.

5、8+0.5311.2+0.5421.6+0.5522.0+0.50 1 2 3 4 5321Line: P0(0, 0)- P1(5, 2)o 缺点：缺点： 在此算法中，在此算法中，y y、k k必须必须是是floatfloat，且每一步都必须对且每一步都必须对y y进行舍入取整，不利于硬进行舍入取整，不利于硬件实现。件实现。一、原理：一、原理：o 每次在主位移方向上走一步，另一个方每次在主位移方向上走一步，另一个方向上走不走步取决于中点偏差判别式的向上走不走步取决于中点偏差判别式的值。值。o 给定理想直线的起点坐标为给定理想直线的起点坐标为P0P0（x0 x0，y0y0），终点坐标为），终点

6、坐标为P1P1（x1x1，y1y1），则直），则直线的隐函数方程为：线的隐函数方程为：0bkxyy)F(x,0101xxyyxyk01xxx其中，直线的斜率：其中，直线的斜率： 直线水平方向位移直线水平方向位移 直线垂直方向位移直线垂直方向位移01yyy（3-13-1）16理想直线将平面划分成三个区域：理想直线将平面划分成三个区域： 对于直线上的点，对于直线上的点，F(xF(x，y)y)0 0； 对于直线上方的点，对于直线上方的点，F F（x x，y y）0 0； 对于直线下方的点，对于直线下方的点，F F（x x，y y）0 0。假设直线的斜率为假设直线的斜率为0k10k1，则，则 ，所以，

7、所以确定确定x x方向为主位移方向。方向为主位移方向。 按照按照BresenhamBresenham原理，原理，x x方向上每次加方向上每次加1 1，y y方向上加不加方向上加不加1 1取决于中点偏差判别式的取决于中点偏差判别式的值。值。 xy 17 假定直线的当前点是假定直线的当前点是 ，沿主位移沿主位移x x方向走一步，下一点只能方向走一步，下一点只能在在 和和 两点中选取。两点中选取。 和和 的中点的中点为为 ，如图，如图3-23-2所所示。显然，若中点示。显然，若中点M M在理想直线的下在理想直线的下方，则方，则 点距离直线近，点点距离直线近，点亮亮 ；否则点亮；否则点亮。(1,1)u

8、iiPxy(1,)diiPxy,()iiPxyuPdPuPdPuP(1,0.5)iiMxy18F F（x x，y y）00F F（x x，y y）=0=0F F（x x，y y）00直线中点直线中点BresenhamBresenham算法原理算法原理19 从P（xi，yi）点走第一步后，为了进行下一像素点的选取，需将Pu和Pd的中点 M（x i1，y i0.5）代入隐函数方程，构造中点偏差判别式d。bxkyyxFyxFdiiiiMM) 1(5 . 0) 5 . 0, 1(),( （3-2）20当当d0d0d0时，中点时，中点M M在直线的上方，在直线的上方，P Pd d点点离直线距离近，下一像

9、素点应点亮离直线距离近，下一像素点应点亮P Pd d，即，即y y方向上不走步；方向上不走步；当当d d0 0时，中点时，中点M M在直线上，在直线上， P Pu u、P Pd d与直线的距离相等，点亮与直线的距离相等，点亮P Pu u或或P Pd d均均可，约定取可，约定取P Pd d。)0()0(11dydyyiii （3-33-3）21M（x i2，y i1.5）M（x i1，y i0.5）P（xi，yi）M（x i1，y i0.5）M（x i2，y i0.5）P（xi，yi）中点偏差判别式的递推中点偏差判别式的递推d0d01.1.中点偏差判别式的递推公式中点偏差判别式的递推公式 在主位

10、移在主位移x x方向上已走一步的情况下，现方向上已走一步的情况下，现在考虑沿主位移方向再走一步，应该选择哪个中在考虑沿主位移方向再走一步，应该选择哪个中点代入中点偏差判别式以决定下一步该点亮的像点代入中点偏差判别式以决定下一步该点亮的像素，如图素，如图3-33-3所示，分两种情况讨论。所示，分两种情况讨论。22 (1)(1)当当d0d00F F（x x，y y）=0=0F F（x x，y y）0026 圆心在原点、半径为圆心在原点、半径为R R的圆方程的隐的圆方程的隐函数表达式为：函数表达式为：0),(222RyxyxF 圆将平面划分成三个区域：对于圆上圆将平面划分成三个区域：对于圆上的点，的

11、点，F(xF(x，y)y)0 0；对于圆外的点，；对于圆外的点，F F（x x，y y）0 0；对于圆内的点，；对于圆内的点，F F（x x，y y）0 0。 （3-73-7）27 事实上，考虑到圆在第一象限内的对称性，本算法可事实上，考虑到圆在第一象限内的对称性，本算法可以进一步简化。以进一步简化。 因为因为ACAC段圆弧和段圆弧和CBCB段圆弧以对称轴段圆弧以对称轴x xy y完全对称，如完全对称，如图图3-63-6所示，所以可以用四条对称轴所示，所以可以用四条对称轴x x0 0，y y0 0， x x y,xy,xy y把圆分成把圆分成8 8等份。等份。 只要绘制出第一象限内的只要绘制出

12、第一象限内的1/81/8圆弧圆弧，根据对称性就，根据对称性就可绘制出整圆，这称为八分法画圆算法。假定第一象限可绘制出整圆，这称为八分法画圆算法。假定第一象限内的任意点为内的任意点为P P（x,yx,y），可以顺时针确定另外），可以顺时针确定另外7 7个点：个点： P P（y y，x x）P P（y y，x x）,P,P（x,x, y y ） ,P,P（x x，y y），），P P（y y，x x），），P P（y y，x x），），P P（x x，y y）。）。28P P（-y-y，x x）P P（-y-y，-x-x）x=-yx=-yP P（-x-x，-y-y）P P（x x，-y-y）P P

13、（y y，-x-x）P P（y y，x x）P P（x x，y y）P P（-x-x，y y）x=yx=yx=0 x=0y=0y=03-6 3-6 圆的对称性圆的对称性29 本算法只考虑图本算法只考虑图3-63-6所示阴影部分的所示阴影部分的4545圆弧，即第一象限内圆弧，即第一象限内 的的1/81/8圆弧。圆弧。2,0Rx 顺时针确定最佳逼近于该段圆弧的像素点集。顺时针确定最佳逼近于该段圆弧的像素点集。为什么是顺时针画圆？为什么是顺时针画圆？ 中点中点BresenhamBresenham算法的原理简化为：算法的原理简化为：x x方向上方向上每次加每次加1 1，y y方向上减不减方向上减不减1

14、 1取决于中点偏差判别取决于中点偏差判别式的值。式的值。此时中点此时中点BresenhamBresenham算法要从（算法要从（0 0，R R）到）到( ( , ）30 假定圆当前点是假定圆当前点是P（xi，yi）,下一点下一点只能在只能在Pu（x i1，y i）和和Pd（x i1，yi1）中选取，如图中选取，如图3-7所示。所示。Pu和和Pd的中点为的中点为M（x i1，y i0.5）显然，若显然，若M点在理想圆弧的下方，点在理想圆弧的下方，则则Pu点离圆弧近，点亮点离圆弧近，点亮Pu；否则应点；否则应点亮亮Pd。31PuPu（x ix i1 1，y iy i）y yP P（x xi i，y

15、 yi i）M M（x x i+1 i+1，y y i i0.50.5）P Pd d（x x i i1 1，y yi i1 1） 圆中点圆中点BresenhamBresenham算法原理算法原理32 从从P P（x xi i，y yi i）开始，为了进行下一像素点的选取，）开始，为了进行下一像素点的选取，需将需将PuPu和和PdPd的中点的中点M M（x ix i1 1，y iy i0.50.5）代入隐函数，代入隐函数，构造中点偏差判别式：构造中点偏差判别式：222)5 .0()1()5 .0, 1(),(RyxyxFyxFdiiiiMM（3-93-9） 当当d0d0d0时，中点时，中点M M

16、在圆外，下在圆外，下一像素点应点亮一像素点应点亮P Pd d，即，即y y方向退一步；方向退一步；当当d d0 0时，时，中点中点M M在圆上，在圆上， P Pu u、P Pd d和圆的距离相等，点亮和圆的距离相等，点亮P Pu u或或P Pd d均可，约定取均可，约定取P Pd d。因此因此，) 0( 1-) 0( 1dydyyiii（3-103-10）333.2.3 递推公式1.1.中点偏差判别式的递推公式中点偏差判别式的递推公式 现在如果考虑主位移方向再走现在如果考虑主位移方向再走一步，应该选择哪个中点代入中点一步，应该选择哪个中点代入中点偏差判别式以决定下一步应该点亮偏差判别式以决定下

17、一步应该点亮的像素，分两种情况讨论。的像素，分两种情况讨论。34当当d0d0时，下一步的中点坐标为：时，下一步的中点坐标为： M M（x ix i2 2，y iy i0.50.5）。）。所以下一步中点偏差判别式为：所以下一步中点偏差判别式为：2221(1)(0.5)2323riiiiidxyRxdx （3-113-11）当当d0d0时，下一步的中点坐标为：时，下一步的中点坐标为： M M（x ix i2 2，y iy i1.51.5）。）。所以下一步中点偏差判别式为：所以下一步中点偏差判别式为：2221) 5 . 1()2() 5 . 1, 2(RyxyxFdiiiii5)(2)22(32)5

18、 . 0() 1(222iiiiiiiyxdyxRyx（3-123-12）35P（xi，yi）M（x i1，y i0.5）M（x i+2，y i0.5）M（x i1，y i0.5）M（x i2，y i1.5）d0d00F F（x x，y y）=0=0F F（x x，y y）00理想椭圆理想椭圆图图3-9 3-9 椭圆的扫描转换椭圆的扫描转换39 圆心在原点、长半轴为圆心在原点、长半轴为a a、短半轴为、短半轴为b b的椭圆方程的隐函数表达式为：的椭圆方程的隐函数表达式为：0),(222222bayaxbyxF（3-14） 椭圆将平面划分成三个区域：对于椭椭圆将平面划分成三个区域：对于椭圆上的点

19、，圆上的点，F(xF(x，y)y)0 0；对于椭圆外的点，；对于椭圆外的点，F F（x x，y y）0 0；对于椭圆内的点，；对于椭圆内的点，F F（x x，y y）0 0，如图，如图3-93-9所示。所示。40 考虑到椭圆对称性，可以用对称轴考虑到椭圆对称性，可以用对称轴x0，y0，把椭圆分成，把椭圆分成4等份。只要绘制出第一象限等份。只要绘制出第一象限内内1/4椭圆弧，如图椭圆弧，如图3-10的阴影部分的阴影部分和和所所示，根据对称性就可绘制出整个椭圆，这称为示，根据对称性就可绘制出整个椭圆，这称为四分法绘制椭圆算法。已知第一象限内的点四分法绘制椭圆算法。已知第一象限内的点P（x，y），可

20、以顺时针得到另外可以顺时针得到另外3个对称点：个对称点：P（x,y），P（x，y），P（x，y）。P（x，y）P（x，y）P（x，y）y图图3-10 3-10 椭圆的对称性椭圆的对称性41 在处理第一象限的在处理第一象限的1/41/4椭圆弧时，进一步椭圆弧时，进一步以法矢量两个分量相等的点把它分为两部分，以法矢量两个分量相等的点把它分为两部分，上半部分上半部分和下半部分和下半部分（切线斜率为（切线斜率为-1-1所在所在的点作为分界点）。该椭圆上一点的点作为分界点）。该椭圆上一点P P（x x，y y）处）处的法矢量为：的法矢量为： yjaxibjyFixFyxN2222),(（3-153-15

21、）式中，式中，i i和和j j是沿是沿x x轴向和沿轴向和沿y y轴向的单位矢量。轴向的单位矢量。42 在图在图3-113-11所示的部分所示的部分的的ACAC椭圆弧段，法矢椭圆弧段，法矢量的量的x x向分量小于向分量小于y y向分量，斜率向分量，斜率k k处处满足处处满足|k|k|1 1，| |x|x| |y|y|，所以，所以x x方向为主位移方向；在方向为主位移方向；在C C点，法矢量的点，法矢量的x x向分量等于向分量等于y y向分量，斜率向分量，斜率k k满足满足k k1 1，| |x|x| |y|y|；在部分；在部分的的CBCB椭圆弧段，椭圆弧段，法矢量法矢量x x向分量大于向分量大

22、于y y向分量，斜率向分量，斜率k k处处满足处处满足|k|k|1 1，| |y|y| |x|x|，所以，所以y y方向为主位移方向。方向为主位移方向。A（0，b）B（a，0）y向分量向分量法矢量法矢量x向分量向分量图图3-11 3-11 椭圆的法矢量椭圆的法矢量222/bab222/baa43 椭圆的中点椭圆的中点BresenhamBresenham算法的原理：在部分算法的原理：在部分：每次在主位移每次在主位移x x方向上走一步，方向上走一步，y y方向上退不退步方向上退不退步取决于中点偏差判别式的值；在部分取决于中点偏差判别式的值；在部分：每次在：每次在主位移方向主位移方向y y上退一步，

23、上退一步，x x方向上走不走步取决于方向上走不走步取决于中点偏差判别式的值。中点偏差判别式的值。图图3-123-12椭圆中点椭圆中点BresenhamBresenham算法原理算法原理A（0，b）B（a，0）PuPdPlPr44 先考虑图先考虑图3-123-12所示部分所示部分的的ACAC段椭段椭圆弧。此时中圆弧。此时中BresenhamBresenham画椭圆算法要从画椭圆算法要从A A（0 0，b b）到）到（ , ), )顺时针确顺时针确定顺时针确定最佳逼近于该段椭圆弧的像定顺时针确定最佳逼近于该段椭圆弧的像素点集。素点集。 由于由于x x方向为主位移方向，方向为主位移方向，假定当前假定

24、当前点是点是P P（x xi i，y yi i），），下一步只能在正右方下一步只能在正右方的像素的像素P Pu u（x x i i1 1，y y i i）和右下方的像素和右下方的像素P Pd d（x x i i1 1，y yi i1 1）中选取。中选取。222/baa222/bab 45 再考虑图再考虑图3-123-12所示部分所示部分CBCB段椭圆弧。此段椭圆弧。此时中时中BresenhamBresenham画椭圆算法要从画椭圆算法要从C C（ , ), )到到B（a，0）顺时针确定最佳逼近于该段椭圆弧顺时针确定最佳逼近于该段椭圆弧像素点集。像素点集。 由于由于y y方向为主位移方向，方向为

25、主位移方向，假定当前点假定当前点是是P（xi i，yi i），下一步只能在正下方像素下一步只能在正下方像素Pl l（x i i，y i i1）和右下方的像素和右下方的像素PrPr（x ix i1 1，yiyi1 1）中选取。中选取。222/baa222/bab46 在上半部分在上半部分，x x方向每次加方向每次加1 1，y y方向上减不方向上减不减减1 1取决于中点偏差判别式的值。取决于中点偏差判别式的值。从从P P（x xi i，y yi i）走第走第一步，为了选取下一像素点的，需将一步，为了选取下一像素点的，需将P Pu u（x x i i1 1，y y i i）和和P Pd d（x x

26、i i1 1，y yi i1 1）的中点的中点M M（x x i i1 1，y y i i0.50.5）代入隐函数，构造中点偏差判别式代入隐函数，构造中点偏差判别式：2222221) 5 . 0() 1() 5 . 0, 1(),(bayaxbyxFyxFdiiiiMM 当当d10d10d0时，中点时，中点M M在椭圆外，在椭圆外，下一像素点应点亮下一像素点应点亮P Pd d，即，即y y方向退一步；当方向退一步；当d d0 0时，时，中点中点M M在椭圆上，在椭圆上，P Pu u、P Pd d和椭圆的距离相等，点亮和椭圆的距离相等，点亮P Pu u或或P Pd d均可，约定取均可，约定取P

27、Pd d，如图，如图3-133-13所示。所示。（3-16）47P（xi，yi）Pu（x i1，y i）M（x i+1，y i-0.5）Pd（x i1，yi1）图图3-13 3-13 上半部分像素点的选取上半部分像素点的选取因此因此，)0( 1-)0( 111dydyyiii（3-173-17）48P（xi，yiM（x i1，y i0.5）M（x i2，y i0.5）P（xi，yi）M（x i1，y i0.5）M（x i2，y i1.5）d10d10图图3-14 3-14 上半部分中点偏差判别式的递推上半部分中点偏差判别式的递推 图图3-133-13中，中，为了能够继续判断椭圆上的每个点，为了

28、能够继续判断椭圆上的每个点，需要给出中点偏差判别式需要给出中点偏差判别式d1d1的递推公式和初始值。的递推公式和初始值。49 现在如果考虑主位移方向再走一步，现在如果考虑主位移方向再走一步，应该选取哪个中点代入应该选取哪个中点代入中点偏差判别式中点偏差判别式以决定应该点亮的像素，如图以决定应该点亮的像素，如图3-14所示，所示，分两种情况讨论。分两种情况讨论。 当当d10时，下一步的中点坐标为：时，下一步的中点坐标为：M（x i2，y i-0.5）。所以下一步中。所以下一步中点偏差判别式为：点偏差判别式为：222222) 1( 1) 5 . 0() 2() 5 . 0, 2(bayaxbyxF

29、diiiii) 32() 32() 5 . 0() 1(212222222iiiiixbdxbbayaxb（3-18）50当当d10d10时，下一步的中点坐标为：时，下一步的中点坐标为：M M（x ix i2 2，y iy i1.51.5）。所以下一步中）。所以下一步中点偏差判别式为：点偏差判别式为：222222) 1( 1) 5 . 1() 2() 5 . 1, 2(bayaxbyxFdiiiii) 22() 32 () 5 . 0() 1(22222222iiiiyaxbbayaxb)22() 32(221iiiyaxbd（3-19）51 2.2.中点偏差判别式中点偏差判别式d1d1的初值

30、的初值 上半部分椭圆的起点为上半部分椭圆的起点为A A（0 0，b b），因此，），因此，第一个中点是（第一个中点是（1 1，b b0.50.5），对应的），对应的d1d1的的初值为：初值为：2222 210(1,0.5)(0.5)dFbba ba b（3-20）22(0.25)bab 52（3-21）yxP（xi，yi）Pr（x i1，yi1）图图3-15 3-15 下半部分像素点的选取下半部分像素点的选取3.3.4 构造中点偏差判别式构造中点偏差判别式构造中点偏差判别式：2222222) 1() 5 . 0() 1, 5 . 0(),(bayaxbyxFyxFdiiiiMMPl（x i，y

31、 i1）53 当当d20d20d20时，中点时，中点M M在椭圆外，下在椭圆外，下一像素点应点亮一像素点应点亮P Pl l，即，即x x方向上不走步；当方向上不走步；当d2d20 0时，时，中点中点M M在椭圆上，在椭圆上，P Pl l、P Pr r和椭圆的距离相等，点亮和椭圆的距离相等，点亮P Pl l或或P Pr r均可，约定取均可，约定取P Pl l，如图，如图3-153-15所示。所示。因此因此，)0( )0( 1221dxdxxiii（3-22）541.1.中点偏差判别式的递推公式中点偏差判别式的递推公式 现在如果考虑主位移方向上再走一步，应该现在如果考虑主位移方向上再走一步，应该选

32、择哪个中点代入中点偏差判别式以决定应该点选择哪个中点代入中点偏差判别式以决定应该点亮的像素，如图亮的像素，如图3-163-16所示，分两种情况讨论。所示，分两种情况讨论。P（xi，yi）M（x i0.5，y i1）M（x i1.5，y i2）d20P（xi，yi）M（x i0.5，y i1）M（x i0.5，y i2）d20图图3-16 3-16 下半部分中点偏差判别式的递推下半部分中点偏差判别式的递推55 当当d20d20时，下一步的中点坐标为：时，下一步的中点坐标为：M M（x x i i1.51.5，y y i i2 2）。所以下一步中点偏差判别式为：）。所以下一步中点偏差判别式为：22

33、2222) 1( 2) 2() 5 . 1() 2, 5 . 1(bayaxbyxFdiiiii) 32() 22() 1() 5 . 0(22222222iiiiyaxbbayaxb)32()22(222iiiyaxbd（3-23）当当d20d20时，下一步的中点坐标为：时，下一步的中点坐标为：M M（x x i i0.50.5，y y i i2 2）。所以下一步中点偏差判别式为：）。所以下一步中点偏差判别式为：222222) 1(2) 2() 5 . 0() 2, 5 . 0(bayaxbyxFdiiiii) 32() 1() 5 . 0(2222222iiiyabayaxb)32(22i

34、iyad（3-24） 56ya22则对于则对于上半部分椭圆上一点任意上半部分椭圆上一点任意P P（x xi i，y yi i）如果在其当前中点如果在其当前中点M M（x xi i1 1，y yi i0.50.5）处，）处，满足满足x x向分量小于向分量小于y y 向分量：向分量：2.2.中点偏差判别式中点偏差判别式d d2 2的初值的初值 由图由图3-113-11知道，在上半部分知道，在上半部分，法，法矢量矢量的的x x向分量小于向分量小于y y向分量；在向分量；在C C点，法点，法矢量矢量的的x x向分量向分量等于等于y y向分量；在下半部分向分量；在下半部分，法，法矢量矢量的的x x向分量

35、向分量大于大于y y向分量。由公式向分量。由公式3-153-15知道：知道：x x向分量为：向分量为：y y向分量为：向分量为： ) 5 . 0() 1(22iiyaxb（3-253-25）xb2257 假定图假定图3-173-17中中P P（x xi i，y yi i）点是椭）点是椭圆上半部分圆上半部分的最后一个像素，的最后一个像素，MM（x xi i1 1，y yi i0.50.5）是用于判断点亮）是用于判断点亮P Pu u和和P Pd d像素的中点。像素的中点。 由于下一像素转入了下半部分由于下一像素转入了下半部分，所以其中点改为判断所以其中点改为判断P Pl l和和P Pr r的中点的

36、中点MM（x xi i0.50.5，y yi i1 1），所以下半部），所以下半部分的初值分的初值d d2020为：为：22222220) 1() 5 . 0(bayaxbd（3-263-26）58P（xi，yi）Pu（xi1，yi）Pl（xi，yi1）M（xi1，yi0.5）Pd（xi1，yi1）= Pr（xi1，yi1）图图3-17 3-17 下半部分的初值下半部分的初值593.43.4 反走样算法反走样算法 考虑将偏差考虑将偏差e e作为加权参数，同时用上下（或左作为加权参数，同时用上下（或左右）两个像素点的颜色来表示交点右）两个像素点的颜色来表示交点f f的颜色。像素的颜色。像素a a

37、的颜色为的颜色为c1c1RGBRGB（e e255255，e e255255，e e255255），），像素像素b b的颜色为的颜色为c2 c2 RGBRGB（1 1e e）255255，（，（1 1e e）255255，（，（1 1e e）255255），两个像素点颜色的），两个像素点颜色的各个相应分量级别之和等于各个相应分量级别之和等于255255。 60 当偏差当偏差e越小时，越小时，c1的分量的分量e255值越小，值越小，颜色越暗，同时颜色越暗，同时c2的分量（的分量（1e）255值越大，颜色越亮；反之亦然。用两个像素值越大，颜色越亮；反之亦然。用两个像素来表示理想线条上的一个点，并依

38、据两个像来表示理想线条上的一个点，并依据两个像素与理想直线的距离而调节其灰度级别，所素与理想直线的距离而调节其灰度级别，所绘制的线条可以达到视觉上消除阶梯的效果。绘制的线条可以达到视觉上消除阶梯的效果。61P P6 6P P4 4P P2 2P P3 3P P1 1P P5 51 12 23 3距离理想直线距离理想直线0.80.8个像素远的个像素远的像素灰度为像素灰度为8080距离理想直线距离理想直线0.20.2个像素远个像素远的像素灰度为的像素灰度为2020距离理想直线距离理想直线0.450.45个像素远的像素灰个像素远的像素灰度为度为4545距离理想直线距离理想直线0.10.1个像素远的像

39、素个像素远的像素灰度为灰度为1010距离理想直线距离理想直线0.550.55个像素远的个像素远的像素灰度为像素灰度为5555距离理想直线距离理想直线0.90.9个像素远的像素个像素远的像素灰度为灰度为9090A AB B62 本章主要讲解了直线、圆和椭圆的中点Bresenham算法原理以及直线的反走样技术。直线、圆和椭圆作为图形基本图元，其生成算法的优劣对整个图形系统的效率至关重要。在像素级生成算法中，中点Bresenham 算法避免了复杂运算，使用了最小的计算量，使单点基本图形生成算法已无优化的余地，已经成为使用最广泛的扫描转换算法。走样是直线光栅化扫描转换的必然结果，只能减轻，不可避免，如

40、何设计直线的反走样算法是计算机图形学的前沿研究课题。 631.1.计算起点坐标为（计算起点坐标为（0,00,0），终点坐标（），终点坐标（12,912,9）直线的中点直线的中点BresenhamBresenham算法的每一步坐标值以及算法的每一步坐标值以及中点偏差判别式中点偏差判别式d d的值，填入表的值，填入表3-13-1中，并用黑色中，并用黑色点亮图点亮图3-293-29中的直线像素。中的直线像素。图图3-293-29像素点阵像素点阵 64表表3-1 3-1 x,yx,y和和d d的值的值xydxyd00-0.2575-0.511086-0.2521-0.7597032-0.5107-0.

41、7543-0.25118-0.5540129-0.2564-0.75652.2.给定直线给定直线的起点的起点坐标为坐标为P P0 0（x x0 0，y y0 0）、终点坐标为终点坐标为P P1 1（x x1 1，y y1 1），容易计算出直），容易计算出直线的斜率线的斜率k k。假设。假设0 0k k1 1且且x x0 0 x x1 1，则，则x x方向为主位移方向，绘制直线的递推公式方向为主位移方向，绘制直线的递推公式为：为：kyyxxiiii111这称为数值微分法（这称为数值微分法（Digital Digital Differential AnalyzerDifferential Analyzer，DDADDA），请），请使用使用M