ブレゼンハムのアルゴリズム
ブレゼンハムのアルゴリズムは、DDA(英語版)を若干修正したものと見ることができる(DDAはオーバーラップしない多角形、すなわちポリゴンのラスタライズで使われる)。
除算の代わりに増分誤差を使う原理は、グラフィックスにおいて他にも応用されている。例えば、テクスチャマッピングでのU,V座標(en:UV mapping)計算に使うことができる。また、ゲームでの3次元地形描画でもこの原理が使われることがある。
IBMの Alan Murphy はこのアルゴリズムを拡張した太い直線の描画アルゴリズムを開発した。
y − y 0 y 1 − y 0 = x − x 0 x 1 − x 0 {\displaystyle {\frac {y-y_{0}}{y_{1}-y_{0}}}={\frac {x-x_{0}}{x_{1}-x_{0}}}}
x を順次与えて y を求め、最も近い整数値にするので、この式を次のように変形する。
y = y 1 − y 0 x 1 − x 0 ( x − x 0 ) + y 0 {\displaystyle y={\frac {y_{1}-y_{0}}{x_{1}-x_{0}}}(x-x_{0})+y_{0}}
傾き ( y 1 − y 0 ) / ( x 1 − x 0 ) {\displaystyle (y_{1}-y_{0})/(x_{1}-x_{0})} は線分の両端の座標のみから求められるので事前に計算しておくことができる。x を順次増やして y を求めるが、最初の値は y 0 {\displaystyle y_{0}} であり、それに傾きを繰り返し加算すればよいことになる。
実際には傾きを加算し続けると精度が悪くなる(カハンの加算アルゴリズム参照)。しかし y を整数値に丸めた値と傾きを加算し続けた値の差のみを保持するようにすれば、その値は -0.5 から 0.5 の間で変化するだけであり、精度は悪くならない。すなわち、x を1ずつ増加させ、差に傾きを加算した結果が 0.5 を超えたら y をインクリメントして差から1を引けばよい。
以下の擬似コードでは、plot(x,y) でピクセル描画を行い、abs は絶対値を返すものとする。