ブレゼンハムのアルゴリズム

ブレゼンハムのアルゴリズム(Bresenham's line algorithm)は、与えられた始点と終点の間に連続した点を置き、近似的な直線を引くためのアルゴリズム。ブレゼンハムの線分描画アルゴリズム、ブレゼンハムアルゴリズムとも。コンピュータのディスプレイに直線を描画するのによく使われ、整数の加減算とビットシフトのみで実装できるので多くのコンピュータで使用可能である。コンピュータグラフィックスの分野の最初期のアルゴリズムの1つである。これを若干拡張すると、円を描くことができる。
アンチエイリアスをサポートした直線描画アルゴリズム（例えば、Xiaolin Wu's line algorithm）もあるが、ブレゼンハムのアルゴリズムの高速性と単純さは今も重要である。プロッターやビデオカードのGPUといったハードウェアで使用されている。ソフトウェアでは多くのグラフィックスライブラリで使用している。非常に単純なので、ビデオカードのファームウェアなどに実装されていることが多い。

歴史

1962年、IBMのジャック・ブレゼンハムが開発した。2001年、ブレゼンハムは次のように記している。
当時私はサンノゼのIBMの開発研究室で働いていた。Calcomp製プロッター (Calcomp plotter)  が1407タイプライター型コンソール経由で IBM 1401 に接続されていた。このアルゴリズムは1962年夏には使われており、開発したのは1カ月ほど前だったかもしれない。当時プログラムは無償で交換されるものだったので、Calcomp（Jim Newland と Calvin Hefte）もそのコピーを持っていた。1962年秋、私がスタンフォードに戻ったときもコピーをスタンフォードの計算センターのライブラリに入れた。
この直線描画ルーチンについて、1963年コロラド州デンバーで開催されたACM全国大会で発表した。ただし、その年は発表内容が出版されることはなく、単に日程表などに私の発表の題名が掲載されただけだった。その後IBMの Systems Journal が発表した論文を掲載したいと申し出てきたので、よろこんで提供し、1965年に出版された。
ブレゼンハムのアルゴリズムは後に修正を加えられ、円を描画するアルゴリズムにもなっている。こちらのアルゴリズムは midpoint circle algorithm などと呼ばれている。

最適化

この技法の問題は、error や deltaerr が分数であるためコンピュータでは計算が遅くなる点であり、さらに浮動小数点数を使った場合は加算によって誤差が蓄積していく点である。整数のみを使った方が高速化され正確になる。そこで上の例で分数または小数になっている全ての数（定数0.5も含む）に deltax をかけて整数にするという技法を使う。ただしそうするとメインループ内で除算が必要になる。そのため error の初期値を変更し、初期値を0として0.5を越えるまでカウントアップするのではなく、初期値を0.5（に deltax をかけた値）にし、0になるまでカウントダウンするように変更する。新たなプログラムの擬似コードは次のようになる。
 function line(x0, y0, x1, y1)
     boolean steep := abs(y1 - y0) > abs(x1 - x0)
     if steep then
         swap(x0, y0)
         swap(x1, y1)
     if x0 > x1 then
         swap(x0, x1)
         swap(y0, y1)
     int deltax := x1 - x0
     int deltay := abs(y1 - y0)
     int error := deltax / 2
     int ystep
     int y := y0
     if y0 < y1 then ystep := 1 else ystep := -1
     for x from x0 to x1
         if steep then plot(y,x) else plot(x,y)
         error := error - deltay
         if error < 0 then
             y := y + ystep
             error := error + deltax
なお、このプログラムは (x0, y0) と (x1, y1) の位置関係がどうであっても描画できるようにしているが、基本形と逆転していると描画順序が反転する。破線を描く場合など描画順序が重要な場合、2つめのswapを排除して次のように簡略化する必要がある。
function line(x0, y0, x1, y1)
     boolean steep := abs(y1 - y0) > abs(x1 - x0)
     if steep then
         swap(x0, y0)
         swap(x1, y1)
     int deltax := abs(x1 - x0)
     int deltay := abs(y1 - y0)
     int error := deltax / 2
     int ystep
     int y := y0
  
     int inc // 追加
     if x0 < x1 then inc := 1 else inc := -1 // 追加
 
     if y0 < y1 then ystep := 1 else ystep := -1
     for x from x0 to x1 with increment inc // 修正
         if steep then plot(y,x) else plot(x,y)
         // increment により描画順序が制御される         error := error - deltay
         if error < 0 then
             y := y + ystep
             error := error + deltax

単純化

誤差を両方向同時に計算すれば、初期化部分の swap を排除できる。
 function line(x0, y0, x1, y1)
   dx := abs(x1-x0)
   dy := abs(y1-y0) 
   if x0 < x1 then sx := 1 else sx := -1
   if y0 < y1 then sy := 1 else sy := -1
   err := dx-dy
 
   loop
     setPixel(x0,y0)
     if x0 = x1 and y0 = y1 exit loop
     e2 := 2*err
     if e2 > -dy then 
       err := err - dy
       x0 := x0 + sx
     end if
     if e2 <  dx then 
       err := err + dx
       y0 := y0 + sy 
     end if
   end loop

導出

ブレゼンハムのアルゴリズムは2段階で導出される。第一段階は傾きを係数とする通常の直線の方程式を別の形式に変換するものである。そして、その新しい方程式を使い、誤差の累積という考え方に基づいて直線を描画する。

全象限について

ここまで述べてきたのは、第一象限の傾きが45度以下の場合（第一八分円）のみについてである。したがって、直交座標系のあらゆる場合を網羅するには全部で8つのケースを考慮する必要がある。

類似のアルゴリズム

ブレゼンハムのアルゴリズムは、DDAを若干修正したものと見ることができる（DDAはオーバーラップしない多角形、すなわちポリゴンのラスタライズで使われる）。
除算の代わりに増分誤差を使う原理は、グラフィックスにおいて他にも応用されている。例えば、テクスチャマッピングでのU,V座標計算に使うことができる。また、ゲームでの3次元地形描画でもこの原理が使われることがある。
IBMの Alan Murphy はこのアルゴリズムを拡張した太い直線の描画アルゴリズムを開発した。