【什么是扫描转换】
　　按我的理解就是把图形转换成图像。图形是为了描述客观景物的数学模型，比如表示一条直线可以用直线上两个端点坐标表示，表示一个圆可以用圆心坐标和半径长度表示。图形的描述只在数学阶段，而要把图形真正显示在显示器上，则需要转换成图像，为了说清楚图像必须要了解显示器，说白了显示器能表示的图像都是离散的，也就是不连续的点阵，正如我们常说的分辩率，它指的就是点阵的大小，而运用到ＲＧＢ色彩空间的显示器，对每一个像素点进行Ｒ、Ｇ、Ｂ三个分量的同时扫描，进而产生五彩缤纷的图像，尽管现在的分辩率很高但是它还是离散的，它的数学本质没有变，我们从显示器上观察的世界是不真实的，是数字的，离散的。所以在这样的显示设备上显示图像最大的问题就是失真，尽管分辩率够大但理论上的失真是不可避免的，所以我们只能做到效果上最好的图像显示了，也就是用离散的点最佳逼近真实值，也就是图形扫描转换。
【Bresenham算法】
　　简单图形的扫描转换常用算法是Bresenham算法。它的思想在于用误差量来衡量点选取的逼近程度。其过程如下：
　　以平面二维图形的扫描转换为例，设要画的图形方程为F(x,y)=0，要画的区域为[x0,x]（不妨设x方向是最大位移方向，即△x>△y），则Ｆ(x,y)也是一个误差度量函数，我们拿离散的点值代入如果大于0则正向偏离，否则负向偏离，等于0的情况比较少，它表示的是不偏离即恰好与真实点重合。既然x是最大位移方向，那每次对x自增1，相应的y可以选择不增或增1(或-1，具体问题具体分析)，选择的方法就是d=F(x+1,y±0.5)的正负情况进行判断从而选择y的值。实际情况中还要考虑到浮点数的计算问题，因为基本的图形扫描转换算法最好能够硬件实现，所以摆脱浮点数是最好的，常用的方法是对d进行递推，而不是直接由Ｆ(x,y)给出。
【圆的扫描转换算法】
　　以画圆为例，给出圆心的坐标(0,0)和半径Ｒ，求圆图像的最佳逼近点。
圆是中心对称的特殊图形，所以可以将圆八等分，则只须对八分之一圆孤求解，其它圆孤可以由对称变换得到，我们求的八分之一圆孤为(0,R)-(R√2,R√2)，可知最大位移方向是x方向，x0=0,y0=R，每次对x自增，然后判断y是否减1，直到x>=y为止。误差量由Ｆ(x,y)=x^2+y^2-R^2给出。
　　先找递推关系，若当前d=F(x+1,y-0.5)>0，则y须减1，则下一d值为d=F(x+2,y-1.5)=(x+2)^2+(y-1.5)^2-R^2=(x+1)^2+(x-0.5)^2-R^2+2x+3-2y+2=d+2x-2y+5，若当前d=F(x+1,y-0.5)<0，则y不变，只有x增1，则下一d值为d=F(x+2,y-0.5)=d+2x+3。
　　d的初值，d0=F(1,R-0.5)=1.25-R，则可以对d-0.25进行判断，因为递推关系中只有整数运算，所以d-0.25>0即d>0.25，这和d>0等价，所以d取初值1-R。
【Ｃ代码】
［仅以八分圆孤为例］
void BresenhamCircle(R)
{
int x=0,y=R,d=1-R;
while(x<y)
{
  putpixel(x,y);
  if(d>0)
  {
   d+=2*(x-y)+5;
   --y;
  }
  else
  {
   d+=2*x+3;
  }
  ++x;
}
}

评论