扫描转换的必要性光栅图形的表示方法是点阵式，它的主要特点是面着色，即在指定的平面区域着上所需要的颜色。与单纯由线条所构成的线划图形相比，采用面着色绘制的光栅图形显得更为生动、直观，真实感更强。3.1生成直线的常用算法已知一条直线段L（P0,P1）,其端点坐标为：P0(x0,y0),P1(x1,y1)。可计算出直线的斜率k为：假定端点坐标均为整数，取直线起点P0(x0,y0)作为初始坐标。画线过程从x的左端点x0开始，向x右端点步进，每步x递增1，y递增k（即直线斜率）；取像素点（x，round（y））作为当前点的坐标。3.1.2中点画线算法假设x坐标为xp的各像素点中，与直线最近者已确定，为P（xp,yp），那么，下一个与直线最近的像素只能是正右方的P1(xp+1,yp)，或右上方的P2（xp+1,yp+1）两者之一。令M为P1和P2的中点，易知M的坐标为（xp+1,yp+0.5）。设Q是理想直线与垂直线x=xp+1的交点。显然，若M在Q的下方，则P2离直线近，应取为下一个像素；否则应取P1。令a=y0-y1，b=x1-x0，c=x0y1-x1y0。构造判别式：d=a(xp+1)+b(yp+0.5)+cd的初始值d0=a+0.5b在d≥0的情况下，取正右方像素P1，d1=a(xp+2)+b(yp+0.5)+c=d+a在d<0的情况下，取右上方像素P2，d2=a(xp+2)+b(yp+1.5)=d+a+b由于我们使用的只是d的符号，而且d的增量都是整数，只是其初始值包含小数。因此，我们可以用2d代替d，来摆脱小数。如果进一步把算法中2*a改为a+a等等，那么这个算法不仅只包含整数变量，而且不包含乘除法，适合硬件实现。3.1.3Bresenham画线算法过各行各列像素中心构造一组虚拟网格线，按直线从起点到终点的顺序计算直线与各垂直网格线的交点，然后确定该列像素中与此交点最近的像素。由图3-5不难看出：若s<t，则Si比较靠近理想直线，应选Si;若s≥t，则Ti比较靠近理想直线，应选Ti。令dx=x2-x1，dy=y2-y1递推公式：di的初值：当di≥0时，选Ti，当di<0时，选Si，由于只包含加、减法和左移（乘2）的运算，而且下一个像素点的选择只需检查di的符号，因此Bresenham画线算法很简单，速度也相当快。3.1.4直线属性1．线型2．线宽3．线色3.2生成圆弧的常用算法3.2.2中点画圆算法假设x坐标为xp的各像素点中，与该圆弧最近者已确定，为P（xp,yp），那么，下一个与圆弧最近的像素只能是正右方的P1(xp+1,yp)，或右下方的P2（xp+1,yp-1）两者之一。令M为P1和P2的中点，易知M的坐标为（xp+1,yp-0.5）。显然，若M在圆内，则P1离圆弧近，应取为下一个像素；否则应取P2。判别式d：d的初始值为：在d≥0的情况下，取右下方像素P2，在d<0的情况下，取正右方像素P1，3.2.3Bresenham画圆算法假设生成圆心在坐标原点，半径为r，从x=0到x=y的1/8圆弧。xi+1=xi+1相应的y则在两种可能中选择：y=yi，或者y=yi-1选择的原则是考察理想的y值是靠近yi还是靠近yi-1。假设在圆弧生成过程中，当前象素点为P(xp,yp),则下一个象素只能是其正右方象素p1(x+1,y)和右下方象素p2(x+1,y-1)二者之一,各点之间的相互位置关系如图所示。P1,p2两点到圆心的距离的平方与圆弧上一点到圆心的距离的平方之差分别为:D(p1)=(x+1)2+y2-R2D(p2)=(x+1)2+(y-1)2-R2如果|D(p1)|≥|D(p2)|则点p2比点p1更接近实际的圆弧；反之，则应选择点p1。若定义：d=|D(p1)|-|D(p2)|若d≥0选p2，若d<0选p1。为了提高算法效率，对判别式进行简化改进。判别式：di=D(p1i)+D(p2i)=2(xi+1)2+yi2+(yi-1)2-2r2用i+1代替i,得：di+1=D(p1i+1)+D(p2i+1)=2(xi+1+1)2+yi+12+(yi+1-1)2-2r2判断式d的初始值为：d0=3-2r。如果di>=0，则选p2i,yi+1=yi-1，di+1=2(xi+2)2+(yi-1)2+(yi-2)2-2r2=di+4(xi-yi)+10如果di<0，则选p1i,yi+1=yi，di+1=2(xi+2)2+yi2+(yi-1)2-2r2=di+4xi+6voidBresenhamCircle(intx0,inty0,doubler,intcolor){intx=0,y,d