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

ブレゼンハムのアルゴリズム(Bresenham's line algorithm)は、与えられた始点と終点の間に連続した点を置き、近似的な直線を引くためのアルゴリズム。ブレゼンハムの線分描画アルゴリズム、ブレゼンハムアルゴリズムとも。コンピュータのディスプレイに直線を描画するのによく使われ、整数の加減算とビットシフトのみで実装できるので多くのコンピュータで使用可能である。コンピュータグラフィックスの分野の最初期のアルゴリズムの1つである。これを若干拡張すると、円を描くことができる。
アンチエイリアスをサポートした直線描画アルゴリズム（例えば、）もあるが、ブレゼンハムのアルゴリズムの高速性と単純さは今も重要である。プロッターやビデオカードのGPUといったハードウェアで使用されている。ソフトウェアでは多くので使用している。非常に単純なので、ビデオカードのファームウェアなどに実装されていることが多い。
歴史.
1962年、IBMのジャック・ブレゼンハムが開発した。2001年、ブレゼンハムは次のように記している。
当時私はサンノゼのIBMの開発研究室で働いていた。Calcomp製プロッター が1407タイプライター型コンソール経由で IBM 1401 に接続されていた。このアルゴリズムは1962年夏には使われており、開発したのは1カ月ほど前だったかもしれない。当時プログラムは無償で交換されるものだったので、Calcomp（Jim Newland と Calvin Hefte）もそのコピーを持っていた。1962年秋、私がスタンフォードに戻ったときもコピーをスタンフォードの計算センターのライブラリに入れた。
この直線描画ルーチンについて、1963年コロラド州デンバーで開催されたACM全国大会で発表した。ただし、その年は発表内容が出版されることはなく、単に日程表などに私の発表の題名が掲載されただけだった。その後IBMの Systems Journal が発表した論文を掲載したいと申し出てきたので、よろこんで提供し、1965年に出版された。
ブレゼンハムのアルゴリズムは後に修正を加えられ、円を描画するアルゴリズムにもなっている。こちらのアルゴリズムは などと呼ばれている。
アルゴリズム.
一般に次のように取り決める。
直線の両端のピクセルの座標は ("x"0, "y"0) と ("x"1, "y"1) であり、"x" が横方向、"y" が縦方向の座標である。
このアルゴリズムは当初、1つの象限のみを対象とし、線分は右下に向かう方向のみ（すなわち、"x"0≤"x"1 かつ "y"0≤"y"1）で、その傾きは1未満（すなわち、formula_1 の方が formula_2 より長い）でなければならなかった。その場合、formula_3 と formula_4 の間の "x" のそれぞれの位置について、（このアルゴリズムでの計算で） "y" の位置が一意に定まり、formula_5 と formula_6 の間の "y" のそれぞれの位置には複数のピクセルが描画されうることになる。
ブレゼンハムのアルゴリズムでは、"x" に対応した "y" の値（小数値）を計算し、それに最も近い整数値を描画すべきピクセルの座標とする。したがって、1つ前の "x" で求めた "y" の整数値と同じか、または1だけ増加することになる。描画すべき線分の方程式は次のようになる。
"x" を順次与えて "y" を求め、最も近い整数値にするので、この式を次のように変形する。
傾き formula_9 は線分の両端の座標のみから求められるので事前に計算しておくことができる。"x" を順次増やして "y" を求めるが、最初の値は formula_5 であり、それに傾きを繰り返し加算すればよいことになる。
実際には傾きを加算し続けると精度が悪くなる（カハンの加算アルゴリズム参照）。しかし "y" を整数値に丸めた値と傾きを加算し続けた値の差のみを保持するようにすれば、その値は -0.5 から 0.5 の間で変化するだけであり、精度は悪くならない。すなわち、"x" を1ずつ増加させ、差に傾きを加算した結果が 0.5 を超えたら "y" をインクリメントして差から1を引けばよい。
以下の擬似コードでは、codice_1 でピクセル描画を行い、codice_2 は絶対値を返すものとする。
 function line(x0, x1, y0, y1)
 "int" deltax := x1 - x0
 "int" deltay := y1 - y0
 "real" error := 0
 "real" deltaerr := abs (deltay / deltax) // deltax != 0 と仮定（垂直な線は扱わない）
 // この除算は分数を保持する形で行う必要がある。
 "int" y := y0
 for x from x0 to x1
 plot(x,y)
 error := error + deltaerr
 if error ≥ 0.5 then
 y := y + 1
 error := error - 1.0
最適化.
この技法の問題は、codice_3 や codice_4 が分数であるためコンピュータでは計算が遅くなる点であり、さらに浮動小数点数を使った場合は加算によって誤差が蓄積していく点である。整数のみを使った方が高速化され正確になる。そこで上の例で分数または小数になっている全ての数（定数0.5も含む）に codice_5 をかけて整数にするという技法を使う。ただしそうするとメインループ内で除算が必要になる。そのため codice_3 の初期値を変更し、初期値を0として0.5を越えるまでカウントアップするのではなく、初期値を0.5（に codice_5 をかけた値）にし、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
単純化.
誤差を両方向同時に計算すれば、初期化部分の codice_8 を排除できる。
 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段階で導出される。第一段階は傾きを係数とする通常の直線の方程式を別の形式に変換するものである。そして、その新しい方程式を使い、誤差の累積という考え方に基づいて直線を描画する。
直線の方程式.
傾きを係数とする直線の方程式は次のとおりである。
ここで m が傾き、b がy軸上の値（y軸との交点）である。この方程式は x についての関数だが、これを x と y の関数に変換することで扱いやすくする。傾きを formula_12 と表し、代数学的変換を施す。
この最後の式を x と y の関数として次のように表せる。
ここで、各定数は次の通り。
この場合、直線はA、B、Cという定数で定義され、formula_18 となる点の集合となる。直線上にない任意の座標 formula_19 では formula_20 となる。x と y が整数しかとらないなら、定数も全て整数で表され、この式には整数しか関与しないことになる点が重要である。
例えば formula_21 で表される直線は、formula_22 と書くこともできる。点 (2,2) はこの直線上にある。
また、点 (2,3) は直線上にはない。
点 (2,1) も同様である。
(2,1) と (2,3) はこの直線をはさんで反対側にあり、どちら側になるかは f(x,y) の値が正か負かで決まる。すなわち、直線は平面を2つの半平面に分割するものであり、f(x,y) が負になる半平面と正になる半平面が存在する。この性質はアルゴリズムの導出において重要である。
アルゴリズム.
線分の始点は明らかに直線上にある。
この場合、直線は始点と終点を整数座標で指定することで定義される。
傾きは1以下なので、問題は次の点を formula_27 と formula_28 のどちらにすべきかということに帰結する。直観的には formula_29 のときの直線の通る位置がどちらの点に近いかで選択すればよい。そこで、2点の中間点を考える。
の計算結果が負なら中間点は直線より下にあり、正なら中間点は直線より上にある。中間点が直線より下なら、直線は formula_31 に近いのでその点を選び、逆なら formula_32 を選べばよい。この中間点における関数の値のみで選択すべき点が決まる。
右図において、青い点 (2,2) は直線上にあり、緑の (3,2) と (3,3) が次に選択すべき点の候補である。黒い点 (3, 2.5) はその2つの候補点の中間点である。
整数演算の場合.
中間点での関数値を求める代わりに、2点における関数値の差を使うことができる。それにより整数のみで計算可能となり、浮動小数点数を使うより一般に高速となる。この代替技法を導出するため、その差を次のように定義する。
始点では formula_34 であるため、この式は中間点の関数値を求めることと等価である。この式を変形すると次のようになる。
中間点の関数値を求める場合と同様、Dが正なら formula_32 を選び、さもなくば formula_31 を選ぶ。
さらに2つ目の点の選択は次のようになる。
この差が正なら formula_40 を選び、さもなくば formula_41 を選ぶ。この選択は誤差の蓄積によって一般化される。
以上でアルゴリズムの導出が完了した。性能上問題となるのは、Dの初期値で1/2という係数を使っている点である。ここで必要なのは累積差分の正負の符号だけなので、全てを2倍にしても結果には影響しない。
その結果、次のように整数のみでこのアルゴリズムを実装できる。
 plot(x0,y0, x1,y1)
 dx=x1-x0
 dy=y1-y0
 D = 2*dy - dx
 plot(x0,y0)
 y=y0
 for x from x0+1 to x1
 if D > 0
 y = y+1
 plot(x,y)
 D = D + (2*dy-2*dx)
 else
 plot(x,y)
 D = D + (2*dy)
formula_42 で表される直線の (0,1) から (6,4) までをこのアルゴリズムで計算した場合の経過を以下に示す。dx=6、dy=3 である。
この描画結果を右図に示す。描画は座標上の交点（青い点）またはピクセル（黄色い四角形）で示されている。
全象限について.
ここまで述べてきたのは、第一象限の傾きが45度以下の場合（第一八分円）のみについてである。したがって、直交座標系のあらゆる場合を網羅するには全部で8つのケースを考慮する必要がある。
類似のアルゴリズム.
ブレゼンハムのアルゴリズムは、を若干修正したものと見ることができる（DDAはオーバーラップしない多角形、すなわちポリゴンのラスタライズで使われる）。
除算の代わりに増分誤差を使う原理は、グラフィックスにおいて他にも応用されている。例えば、テクスチャマッピングでのU,V座標()計算に使うことができる。また、ゲームでの3次元地形描画でもこの原理が使われることがある。
IBMの Alan Murphy はこのアルゴリズムを拡張した太い直線の描画アルゴリズムを開発した。