Bresenham算法是计算机图形学领域使用最广泛的直线扫描转换方法。bresenham算法是计算机图形学中为了“显示器（萤幕或印表机）系由像素构成”的这个特性而设计出来的算法，使得在求直线各点的过程中全部以整数来运算，因而大幅度提升计算速度。
基本介绍
- 外文名：bresenham算法
- 领域：计算机图形学领域
- 类型：直线扫描转换方法
- 优点：可以採用增量计算
原理
过各行、各列像素中心构造一组虚拟格线线，按直线从起点到终点的顺序计算直线各垂直格线线的交点，然后确定该列像素中与此交点最近的像素。
优点
该算法的优点在于可以採用增量计算，使得对于每一列，只要检查一个误差项的符号，就可以确定该列所求的像素。
公式
void IntegerBresenhamlin(int x0,int y0,int x1,int y1,int color)
{
int x,y,dx,dy,unitx,unity,fabs_dx,fabs_dy,e;
unsigned char i;
dx=x1-x0;
dy=y1-y0;
fabs_dx = (int)fabs(dx);
fabs_dy = (int)fabs(dy);
unitx = dx / fabs_dx ;
unity = dy / fabs_dy ;
x=x0;
y=y0;
if( fabs_dx> fabs_dy )
{
e=-fabs_dx;
for(i=0;i<=fabs_dx;i++)
{
drawpixel(x,y,color);
x+=unitx,e=e+2*fabs_dy;
if(e>=0)
{
y+=unity;e=e-2*fabs_dx;
}
} // for end
}
else
{
// e-=fabs_dy;
e=-fabs_dy
for(i=0;i<=fabs_dy;i++)
{
drawpixel(x,y,color);
y+=unity,e=e+2*fabs_dx;
if(e>=0)
{
x+=unitx;e=e-2*fabs_dy;
}
} // for end
}// if end
} //:~
改进算法
原理:
上述bresenham 算法在计算直线斜率与误差项时用到了小数与除法，可以改用整数以避免除法。由于算法中用到误差项的符号，因此可以做如下替换：e'=2*e*dx.
以下是C++语言方式描述的，在MFC下的核心绘图代码（画圆的算法）
{
CDC* pDC=GetDC();
int p,r,x,y,c,i;
r=50;
p=3-2*r;
c=RGB(0,0,0);
x=0;
y=r;
i=100;
for(;x<=y;)
{
pDC->SetPixel(x+i,y+i,c);
pDC->SetPixel(-x+i,-y+i,c);
pDC->SetPixel(-x+i,y+i,c);
pDC->SetPixel(x+i,-y+i,c);
pDC->SetPixel(y+i,x+i,c);
pDC->SetPixel(-y+i,x+i,c);
pDC->SetPixel(-y+i,-x+i,c);
pDC->SetPixel(y+i,-x+i,c);
if(p<0)p=p+4*x+6;
else {y--;p=p+4*(x-y)+10;}
x++;
}
}
