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++;

}

}