目的

原理

Bresenham改进算法(原理 算法)

目的

bresenham算法是计算机图形学中为了“显示器（屏幕或打印机）系由像素构成”的这个特性而设计出来的算法，使得在求直线各点的过程中全部以整数来运算，因而大幅度提升计算速度

原理

Bresenham算法是计算机图形学领域使用最广泛的直线扫描转换方法。

其原理是：

过各行、各列像素中心构造一组虚拟网格线，按直线从起点到终点的

顺序计算直线各垂直网格线的交点，然后确定该列像素中与此交点最近

的像素。

该算法的优点在于可以采用增量计算，使得对于每一列，只要检查一个误差项

的符号，就可以确定该列所求的像素。

以下是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++;

}

}

Bresenham改进算法

原理

上述bresenham 算法在计算直线斜率与误差项时用到了小数与除法，可以改用整数以避免除法。由于算法中用到误差项的符号，因此可以做如下替换：e'=2*e*dx.

算法

void IntegerBresenhamlin(int x0,int y0,int x1,int y1,int color)

{

int x,y,dx,dy,unitx,unity,fabs_dx,fabs_dy,e;

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=-dx;

for(i=0;i<=fabs_dx;i++)

{

drawpixel(x,y,color);

x+=unitx,e=e+2*dy;

if(e>=0)

{

y+=unity;e=e-2*dx;

}

} // for end

}

else

{

e=-dy;

for(i=0;i<=fabs_dy;i++)

{

drawpixel(x,y,color);

y+=unity,e=e+2*dx;

if(e>=0)

{

x+=unitx;e=e-2*dy;

}

} // for end

}// if end

} //:~