Bresenham's line algorithm

ウィキペディア

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

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/05/26 07:45 UTC 版)

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

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

歴史

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

当時私はサンノゼのIBMの開発研究室で働いていた。Calcomp製プロッター (Calcomp plotter)  が1407タイプライター型コンソール経由で IBM 1401 に接続されていた。このアルゴリズムは1962年夏には使われており、開発したのは1カ月ほど前だったかもしれない。当時プログラムは無償で交換されるものだったので、Calcomp（Jim Newland と Calvin Hefte）もそのコピーを持っていた。1962年秋、私がスタンフォードに戻ったときもコピーをスタンフォードの計算センターのライブラリに入れた。

この直線描画ルーチンについて、1963年コロラド州デンバーで開催されたACM全国大会で発表した。ただし、その年は発表内容が出版されることはなく、単に日程表などに私の発表の題名が掲載されただけだった。その後IBMの Systems Journal が発表した論文を掲載したいと申し出てきたので、よろこんで提供し、1965年に出版された。

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

アルゴリズム

ブレゼンハムのアルゴリズムで描画した直線の例。左上端の格子が (0,0) で、直線は (1,1) から (11,5) までひかれている。

以下が成り立つものとして説明していく。

• 左上端が原点 (0,0) で、ピクセルの座標は右方向と下方向に向かって大きくなる（例えば、(7,4) という座標のピクセルは (7,5) という座標のピクセルに接して上にある）。
• 各ピクセルの中心が、その整数座標に正確に対応するものとする。

いま、x が横方向、y が縦方向の座標であるとして、直線の両端のピクセルの座標が (x₀, y₀) と (x₁, y₁) として与えられたとする。

まず、1つの象限のみを対象とし、線分は右下に向かう方向のみ（すなわち、x₀≤x₁ かつ y₀≤y₁）で、その傾きは1未満（すなわち、${\displaystyle x_{1}-x_{0}}$

y=f(x)=.5x+1 or f(x,y)=x-2y+2

正と負の半平面

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

${\displaystyle y=f(x)=mx+b}$

青は候補点 (2,2)、緑は候補点 (3,2) と (3,3)

傾きは1以下なので、問題は次の点を ${\displaystyle (x_{0}+1,y_{0})}$

(0,1) から (6,4) までの直線のプロットの様子を格子線とピクセルで示した図

以上でアルゴリズムの導出が完了した。性能上問題となるのは、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)

${\displaystyle f(x,y)=x-2y+2}$

ウィキメディア・コモンズには、ブレゼンハムのアルゴリズムに関連するカテゴリがあります。