第三章++基本图形的扫描转换1

第三章◆扫描转换的基本概念◆绘制像素点函数SetPixel的用法◆直线圆和椭圆的中点Bresenham原理◆直线反走样原理3.1直线的扫描转换3.2圆的扫描转换3.3椭圆的扫描转换3.4反走样算法3.6本章小结3.7习题直线、圆和椭圆是图形设计的最基本图形（图元），从光栅扫描显示器的显示原理和真实感图形生成技术的需要出发，需要使用像素点函数来绘制这些基本图形。光栅扫描显示器的绘图过程就是在像素点阵中确定最佳逼近于理想图形的像素点集的过程，这个过程称为“图形的扫描转换”，也称为“图形光栅化”。3.1直线的扫描转换3.1.1算法原理3.1.2构造中点偏差判别式3.1.3递推公式直线的扫描转换就是在屏幕像素点阵中用指定颜色点亮最佳逼近于理想直线的像素点集的过程。yx3.1.1算法原理直线的中点Bresenham算法的原理：每次在主位移方向上走一步，另一个方向上走不走步取决于中点偏差判别式的值。yx给定理想直线的起点坐标为P0（x0，y0），终点坐标为P1（x1，y1），则直线的隐函数方程为：(,)0Fxyykxb1010yyykxxx10xxx其中，直线的斜率：直线水平方向位移：直线垂直方向位移：（3-1）10yyy理想直线将平面划分成三个区域：对于直线上的点，F(x，y)＝0；对于直线上方的点，F（x，y）＞0；对于直线下方的点，F（x，y）＜0。假设直线的斜率为0≤k≤1，则，所以确定x方向为主位移方向。按照Bresenham原理，x方向上每次加1，y方向上加不加1取决于中点偏差判别式的值。xy假定直线的当前点是，沿主位移x方向走一步，下一点只能在和两点中选取。和的中点为，如图3-2所示。显然，若中点M在理想直线的下方，则点距离直线近，点亮；否则点亮。(1,1)uiiPxy(1,)diiPxy,()iiPxyuPdPuPdPuP(1,0.5)iiMxyF（x，y）0F（x，y）=0F（x，y）0直线中点Bresenham算法原理(1,1)uiiPxy(1,)diiPxy,()iiPxy(1,0.5)iiMxy3.1.2构造中点偏差判别式从P（xi，yi）点走第一步后，为了进行下一像素点的选取，需将Pu和Pd的中点M（xi＋1，yi＋0.5）代入隐函数方程，构造中点偏差判别式d。(,)(1,0.5)0.5(1)MMiiiidFxyFxyykxb（3-2）当d0时，中点M在直线的下方，Pu点离直线距离近，下一像素点应点亮Pu，即y方向上走一步；当d0时，中点M在直线的上方，Pd点离直线距离近，下一像素点应点亮Pd，即y方向上不走步；当d＝0时，中点M在直线上，Pu、Pd与直线的距离相等，点亮Pu或Pd均可，约定取Pd。)0()0(11dydyyiii（3-3）3.1.3递推公式M（xi＋2，yi＋1.5）M（xi＋1，yi＋0.5）P（xi，yi）M（xi＋1，yi＋0.5）M（xi＋2，yi＋0.5）P（xi，yi）中点偏差判别式的递推d0d≥01.中点偏差判别式的递推公式在主位移x方向上已走一步的情况下，现在考虑沿主位移方向再走一步，应该选择哪个中点代入中点偏差判别式以决定下一步该点亮的像素，如图3-3所示，分两种情况讨论。(1)当d0时bxkyyxFdiiiii)2(5.1)5.1,2(1kdkbxkyiii11)1(5.0⑵当d≥0时bxkyyxFdiiiii)2(5.0)5.0,2(1kdkbxkyiii)1(5.0（3-5）（3-4）直线的起点坐标为P0（x0，y0），x为主位移方向。因此，第一个中点是（x0＋1，y0＋0.5），相应的d的初始值为：bxkyyxFd)1(5.0)5.0,1(000005.000kbkxy其中，因为（x0，y0）在直线上，所以000bkxy则：kd5.00（3-6）2.中点偏差判别式的初始值3.2圆的扫描转换3.2.1算法原理3.2.2构造中点偏差判别式3.2.3递推公式本节主要讲解仅包含加减操作的顺时针绘制1/8圆的中点Bresenham算法原理。圆的扫描转换yx理想圆F（x，y）0F（x，y）=0F（x，y）03.2.1算法原理圆心在原点、半径为R的圆方程的隐函数表达式为：0),(222RyxyxF圆将平面划分成三个区域：对于圆上的点，F(x，y)＝0；对于圆外的点，F（x，y）＞0；对于圆内的点，F（x，y）＜0。（3-7）事实上，考虑到圆在第一象限内的对称性，本算法可以进一步简化。因为AC段圆弧和CB段圆弧以对称轴x＝y完全对称，如图3-6所示，所以可以用四条对称轴x＝0，y＝0，x＝y,x＝－y把圆分成8等份。只要绘制出第一象限内的1/8圆弧Ⅰ，根据对称性就可绘制出整圆，这称为八分法画圆算法。假定第一象限内的任意点为P（x,y），可以顺时针确定另外7个点：P（y，x）P（y，－x）,P（x,－y）,P（－x，－y），P（－y，－x），P（－y，x），P（－x，y）。P（-y，x）P（-y，-x）x=-yP（-x，-y）P（x，-y）P（y，-x）P（y，x）P（x，y）P（-x，y）x=yx=0y=0图3-6圆的对称性本算法只考虑图3-6所示阴影部分的45°圆弧，即第一象限内的1/8圆弧。此时中点Bresenham算法要从]2,0[Rx中点Bresenham算法的原理简化为：x方向上每次加1，y方向上减不减1取决于中点偏差判别式的值。顺时针确定最佳逼近于该段圆弧的像素点集。假定圆当前点是P（xi，yi）,下一点只能在Pu（xi＋1，yi）和Pd（xi＋1，yi－1）中选取，如图3-7所示。Pu和Pd的中点为M（xi＋1，yi－0.5）显然，若M点在理想圆弧的下方，则Pu点离圆弧近，点亮Pu；否则应点亮Pd。(0,)(/2,/2)RRRPu（xi＋1，yi）yP（xi，yi）M（xi+1，yi－0.5）Pd（xi＋1，yi－1）圆中点Bresenham算法原理3.2.2构造中点偏差判别式从P（xi，yi）开始，为了进行下一像素点的选取，需将Pu和Pd的中点M（xi＋1，yi－0.5）代入隐函数，构造中点偏差判别式：222(,)(1,0.5)(1)(0.5)MMiiiidFxyFxyxyR（3-9）当d0时，中点M在圆内，下一像素点应点亮Pu，即y方向不退步；当d0时，中点M在圆外，下一像素点应点亮Pd，即y方向退一步；当d＝0时，中点M在圆上，Pu、Pd和圆的距离相等，点亮Pu或Pd均可，约定取Pd。因此，)0(1-)0(1dydyyiii（3-10）3.2.3递推公式1.中点偏差判别式的递推公式现在如果考虑主位移方向再走一步，应该选择哪个中点代入中点偏差判别式以决定下一步应该点亮的像素，分两种情况讨论。⑴当d0时，下一步的中点坐标为：M（xi＋2，yi－0.5）。所以下一步中点偏差判别式为：2221(1)(0.5)2323riiiiidxyRxdx（3-11）⑵当d≥0时，下一步的中点坐标为：M（xi＋2，yi－1.5）。所以下一步中点偏差判别式为：2221)5.1()2()5.1,2(RyxyxFdiiiii5)(2)22(32)5.0()1(222iiiiiiiyxdyxRyx（3-12）P（xi，yi）M（xi＋1，yi－0.5）M（xi+2，yi－0.5）M（xi＋1，yi－0.5）M（xi＋2，yi－1.5）d0d≥0中点偏差判别式的递推2.中点偏差判别式的初始值圆的起点为P0（0，R），x为主位移方向。因此，第一个中点是（1，R-0.5），对应的d的初始值为：022(1,0.5)1(0.5)1.25dFRRRR（3-13）