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

ブレゼンハムのアルゴリズムは、与えられた始点と終点の間に連続した点を置き、近似的な直線を引くためのアルゴリズム。ブレゼンハムの線分描画アルゴリズム、ブレゼンハムアルゴリズムとも。コンピュータのディスプレイに直線を描画するのによく使われ、整数の加減算とビットシフトのみで実装できるので多くのコンピュータで使用可能である。コンピュータグラフィックスの分野の最初期のアルゴリズムの1つである。これを若干拡張すると、円を描くことができる。

アンチエイリアスをサポートした直線描画アルゴリズムもあるが、ブレゼンハムのアルゴリズムの高速性と単純さは今も重要である。プロッターやビデオカードのGPUといったハードウェアで使用されている。ソフトウェアでは多くのグラフィックスライブラリで使用している。非常に単純なので、ビデオカードのファームウェアなどに実装されていることが多い。

1. 歴史
-----

1962年、IBMのジャック・ブレゼンハムが開発した。2001年、ブレゼンハムは次のように記している。

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

ブレゼンハムのアルゴリズムは後に修正を加えられ、円を描画するアルゴリズムにもなっている。こちらのアルゴリズムは midpoint circle algorithm などと呼ばれている。

2. アルゴリズム
---------

一般に次のように取り決める。

左上端が原点  で、ピクセルの座標は右方向と下方向に向かって大きくなる。
各ピクセルの中心が、その整数座標に正確に対応するものとする。直線の両端のピクセルの座標は  と  であり、//x// が横方向、//y// が縦方向の座標である。

このアルゴリズムは当初、1つの象限のみを対象とし、線分は右下に向かう方向のみで、その傾きは1未満でなければならなかった。その場合、 と の間の //x// のそれぞれの位置について、 //y// の位置が一意に定まり、 と の間の //y// のそれぞれの位置には複数のピクセルが描画されうることになる。

ブレゼンハムのアルゴリズムでは、//x// に対応した //y// の値を計算し、それに最も近い整数値を描画すべきピクセルの座標とする。したがって、1つ前の //x// で求めた //y// の整数値と同じか、または1だけ増加することになる。描画すべき線分の方程式は次のようになる。

//x// を順次与えて //y// を求め、最も近い整数値にするので、この式を次のように変形する。

傾き は線分の両端の座標のみから求められるので事前に計算しておくことができる。//x// を順次増やして //y// を求めるが、最初の値は であり、それに傾きを繰り返し加算すればよいことになる。

実際には傾きを加算し続けると精度が悪くなる。しかし //y// を整数値に丸めた値と傾きを加算し続けた値の差のみを保持するようにすれば、その値は -0.5 から 0.5 の間で変化するだけであり、精度は悪くならない。すなわち、//x// を1ずつ増加させ、差に傾きを加算した結果が 0.5 を超えたら //y// をインクリメントして差から1を引けばよい。

以下の擬似コードでは、plot でピクセル描画を行い、abs は絶対値を返すものとする。

function line//int// deltax := x1 - x0//int// deltay := y1 - y0//real// error := 0//real// deltaerr := abs  // deltax != 0 と仮定 // この除算は分数を保持する形で行う必要がある。//int// y := y0for x from x0 to x1 plot error := error + deltaerrif error ≥ 0.5 then y := y + 1 error := error - 1.0

2.1. 最適化
--------

この技法の問題は、error や deltaerr が分数であるためコンピュータでは計算が遅くなる点であり、さらに浮動小数点数を使った場合は加算によって誤差が蓄積していく点である。整数のみを使った方が高速化され正確になる。そこで上の例で分数または小数になっている全ての数に deltax をかけて整数にするという技法を使う。ただしそうするとメインループ内で除算が必要になる。そのため error の初期値を変更し、初期値を0として0.5を越えるまでカウントアップするのではなく、初期値を0.5にし、0になるまでカウントダウンするように変更する。新たなプログラムの擬似コードは次のようになる。

function line//boolean// steep := abs > absif steep then swap swapif x0 > x1 then swap swap//int// deltax := x1 - x0//int// deltay := abs//int// error := deltax / 2//int// ystep//int// y := y0if y0 < y1 then ystep := 1 else ystep := -1for x from x0 to x1if steep then plot else plot error := error - deltayif error < 0 then y := y + ystep error := error + deltax

なお、このプログラムは  と  の位置関係がどうであっても描画できるようにしているが、基本形と逆転していると描画順序が反転する。破線を描く場合など描画順序が重要な場合、2つめのswapを排除して次のように簡略化する必要がある。

function line//boolean// steep := abs > absif steep then swap swap//int// deltax := abs // 修正//int// deltay := abs//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 := -1for x //from// x0 //to// x1 with increment inc // 修正if steep then plot else plot // increment により描画順序が制御される error := error - deltayif error < 0 then y := y + ystep error := error + deltax

2.2. 単純化
--------

誤差を両方向同時に計算すれば、初期化部分の swap を排除できる。function line dx := abs dy := absif x0 < x1 then sx := 1 else sx := -1if y0 < y1 then sy := 1 else sy := -1 err := dx-dy

loop//setPixel//if x0 = x1 and y0 = y1 exit loop e2 := 2*errif e2 > -dy then err := err - dy x0 := x0 + sxend ifif e2 < dx then err := err + dx y0 := y0 + syend ifend loop

3. 導出
-----

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

3.1. 直線の方程式
-----------

傾きを係数とする直線の方程式は次のとおりである。

ここで m が傾き、b がy軸上の値である。この方程式は x についての関数だが、これを x と y の関数に変換することで扱いやすくする。傾きを と表し、代数学的変換を施す。

この最後の式を x と y の関数として次のように表せる。

ここで、各定数は次の通り。

この場合、直線はA、B、Cという定数で定義され、 となる点の集合となる。直線上にない任意の座標 では となる。x と y が整数しかとらないなら、定数も全て整数で表され、この式には整数しか関与しないことになる点が重要である。

例えば で表される直線は、 と書くこともできる。点  はこの直線上にある。

また、点  は直線上にはない。

点  も同様である。

 と  はこの直線をはさんで反対側にあり、どちら側になるかは f の値が正か負かで決まる。すなわち、直線は平面を2つの半平面に分割するものであり、f が負になる半平面と正になる半平面が存在する。この性質はアルゴリズムの導出において重要である。

3.2. アルゴリズム
-----------

線分の始点は明らかに直線上にある。

この場合、直線は始点と終点を整数座標で指定することで定義される。

傾きは1以下なので、問題は次の点を と のどちらにすべきかということに帰結する。直観的には のときの直線の通る位置がどちらの点に近いかで選択すればよい。そこで、2点の中間点を考える。

の計算結果が負なら中間点は直線より下にあり、正なら中間点は直線より上にある。中間点が直線より下なら、直線は に近いのでその点を選び、逆なら を選べばよい。この中間点における関数の値のみで選択すべき点が決まる。

右図において、青い点  は直線上にあり、緑の  と  が次に選択すべき点の候補である。黒い点  はその2つの候補点の中間点である。

3.2.1. 整数演算の場合
--------------

中間点での関数値を求める代わりに、2点における関数値の差を使うことができる。それにより整数のみで計算可能となり、浮動小数点数を使うより一般に高速となる。この代替技法を導出するため、その差を次のように定義する。

始点では であるため、この式は中間点の関数値を求めることと等価である。この式を変形すると次のようになる。

中間点の関数値を求める場合と同様、Dが正なら を選び、さもなくば を選ぶ。

さらに2つ目の点の選択は次のようになる。

この差が正なら を選び、さもなくば を選ぶ。この選択は誤差の蓄積によって一般化される。

以上でアルゴリズムの導出が完了した。性能上問題となるのは、Dの初期値で1/2という係数を使っている点である。ここで必要なのは累積差分の正負の符号だけなので、全てを2倍にしても結果には影響しない。

その結果、次のように整数のみでこのアルゴリズムを実装できる。

plot dx=x1-x0 dy=y1-y0

D = 2*dy - dx plot y=y0

for x from x0+1 to x1 if D > 0 y = y+1 plot D = D +  else plot D = D + 

で表される直線の  から  までをこのアルゴリズムで計算した場合の経過を以下に示す。dx=6、dy=3 である。

D=2*3-6=0
plot
1から6までループ
x=1: D≤0: plot, D=6
x=2: D>0: y=2, plot, D=6+=0
x=3: D≤0: plot, D=6
x=4: D>0: y=3, plot, D=6+=0
x=5: D≤0: plot, D=6
x=6: D>0: y=4, plot, D=6+=0この描画結果を右図に示す。描画は座標上の交点またはピクセルで示されている。

3.3. 全象限について
------------

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

4. 類似のアルゴリズム
------------

ブレゼンハムのアルゴリズムは、DDA を若干修正したものと見ることができる。

除算の代わりに増分誤差を使う原理は、グラフィックスにおいて他にも応用されている。例えば、テクスチャマッピングでのU,V座標計算に使うことができる。また、ゲームでの3次元地形描画でもこの原理が使われることがある。

IBMの Alan Murphy はこのアルゴリズムを拡張した太い直線の描画アルゴリズムを開発した。

5. 脚注
-----

6. 参考文献
-------

[1], by Colin Flanagan

7. 関連文献
-------

[2] MICAD '87 proceedings on CAD/CAM and Computer Graphics, page 591 - ISBN 2-86601-084-1. ブレゼンハムのアルゴリズムを応用して3次元グラフィックスで隠れて見えない直線を削除する技法を示したもの
[3], A.S. Murphy, IBM Technical Disclosure Bulletin, Vol. 20, No. 12, May 1978. ブレゼンハムのアルゴリズムを拡張して太い線を描画する技法を示したもの

8. 外部リンク
--------

[4]
[5]
[6]
[7]
[8]
[9]
[10] – 直線、円、楕円、ベジェ曲線をプロットする単純な実装例