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

ブレゼンハムの線アルゴリズムは、2 点間の直線の近似値を形成するために選択する必要があるn次元ラスターの点を決定する線描画アルゴリズムです。これは、歴史的に一般的なコンピュータ アーキテクチャでは非常に負荷の少ない操作である整数の加算、減算、およびビット シフトのみを使用するため、ビットマップ イメージ(コンピュータ画面など)に線プリミティブを描画するためによく使用されます。これは増分誤差アルゴリズムであり、コンピュータ グラフィックスの分野で開発された最も初期のアルゴリズムの 1 つです。中点円アルゴリズムと呼ばれる元のアルゴリズムの拡張は、円の描画に使用できます。

Wu のアルゴリズムなどのアルゴリズムもアンチエイリアシングをサポートできるため、現代のコンピュータグラフィックスで頻繁に使用されていますが、Bresenham のラインアルゴリズムは、その速度と単純さから依然として重要です。このアルゴリズムは、プロッターなどのハードウェアや、現代のグラフィックスカードのグラフィックスチップで使用されています。また、多くのソフトウェアグラフィックスライブラリにも含まれています。このアルゴリズムは非常に単純なため、現代のグラフィックスカードのファームウェアまたはグラフィックスハードウェアのいずれかに実装されることがよくあります。

「Bresenham」というラベルは現在、Bresenham のオリジナルのアルゴリズムを拡張または変更したアルゴリズムのファミリに使用されています。

ブレゼンハムの直線アルゴリズムは、1962年にIBMで開発したジャック・エルトン・ブレゼンハムにちなんで名付けられました。2001年にブレゼンハムは次のように書いています: ^[1]

私はIBMのサンノゼ開発研究所の計算ラボで働いていました。Calcompプロッタは、 1407タイプライターコンソールを介してIBM 1401に接続されていました。[アルゴリズム]は1962年夏、おそらく1か月ほど前には実用化されていました。当時のプログラムは企業間で自由に交換されていたため、Calcomp（Jim NewlandとCalvin Hefte）はコピーを持っていました。1962年秋にスタンフォードに戻ったとき、私はコピーをスタンフォード計算センターの図書館に置きました。線描画ルーチンの説明は、コロラド州デンバーで開催された1963年のACM全国大会での発表に採用されました。その年は議事録が出版されず、講演者の議題とトピックがCommunications of the ACMの号に掲載されただけでした。私が発表した後、IBM Systems Journalの担当者が論文を出版してもよいかと尋ねてきました。私は喜んで同意し、1965年に論文が印刷されました。

以下の規則が使用されます。

• 左上は（0,0）であり、ピクセル座標は右方向と下方向に増加する（例えば、（7,4）のピクセルは（7,5）のピクセルの真上にある）。
• ピクセルの中心は整数座標を持ちます。

線の終点はとのピクセルです。ここで、ペアの最初の座標は列、2 番目の座標は行です。 ${\displaystyle (x_{0},y_{0})}$${\displaystyle (x_{1},y_{1})}$

このアルゴリズムは、最初は、線分が右下に伸び（および）、その水平投影が垂直投影よりも長い（線の傾きが1未満である）八分円に対してのみ提示されます。この八分円では、との間の各列xに対して、線のピクセルを含む行yが 1 つだけ（アルゴリズムによって計算）ありますが、との間の各行には複数のラスタライズされたピクセルが含まれる場合があります。 ${\displaystyle x_{0}\leq x_{1}}$${\displaystyle y_{0}\leq y_{1}}$${\displaystyle x_{1}-x_{0}}$${\displaystyle y_{1}-y_{0}}$${\displaystyle x_{0}}$${\displaystyle x_{1}}$${\displaystyle y_{0}}$${\displaystyle y_{1}}$

ブレゼンハムのアルゴリズムは、同じxに対して理想的な (分数) yに最も近いピクセル中心に対応する整数y を選択します。後続の列では、y は同じままか、1 ずつ増加します。端点を通る線の一般的な方程式は、次の式で与えられます。

${\displaystyle {\frac {y-y_{0}}{y_{1}-y_{0}}}={\frac {x-x_{0}}{x_{1}-x_{0}}}}$。

列x がわかっているので、ピクセルの行yは、この量を最も近い整数に丸めることで求められます。

${\displaystyle y={\frac {y_{1}-y_{0}}{x_{1}-x_{0}}}(x-x_{0})+y_{0}}$。

傾斜は終点の座標のみに依存し、事前に計算することができ、連続する整数値のxに対する理想的なy は、傾斜 から始めて繰り返し追加することで計算できます。${\displaystyle (y_{1}-y_{0})/(x_{1}-x_{0})}$${\displaystyle y_{0}}$

実際には、アルゴリズムは y 座標を追跡しません。y 座標は、xが 1 増加するたびにm = ∆y/∆xずつ増加します。各段階で誤差境界を保持します。誤差境界は、(a) 線がピクセルから出るポイントから (b) ピクセルの上端までの距離の負数を表します。この値は、(ピクセルの中心座標を使用しているため) 最初に に設定され、x座標が 1 増加するたびにmずつ増加します。誤差が0.5を超えると、線が 1 ピクセル上方に移動したことがわかり、y座標を増分して、新しいピクセルの上端からの距離を表すように誤差を再調整する必要があります。これは、誤差から 1 を引くことによって行われます。^[2]${\displaystyle y_{0}-0.5}$

ブレゼンハムのアルゴリズムを導くには、2 つのステップを踏む必要があります。最初のステップは、直線の方程式を典型的な傾きと切片の形から別のものに変換し、この新しい方程式を使用して、誤差の蓄積という考え方に基づいて直線を描くことです。

直線の傾きと切片の形は次のように表される。

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

ここで、 は傾き、は y 切片です。これは のみの関数であるため、垂直線を表すことはできません。したがって、任意の角度で線を描画できるようにするには、この式を と の両方の関数として記述すると便利です。線の角度 (または傾き) は、「上昇 / 距離」、つまり として表すことができます。次に、代数操作を使用して、 ${\displaystyle m}$${\displaystyle b}$${\displaystyle x}$${\displaystyle x}$ ${\displaystyle y}$${\displaystyle \Delta y/\Delta x}$

${\displaystyle {\begin{aligned}y&=mx+b\\y&={\frac {\Delta y}{\Delta x}}x+b\\(\Delta x)y&=(\Delta y)x+(\Delta x)b\\0&=(\Delta y)x-(\Delta x)y+(\Delta x)b\end{aligned}}}$

この最後の式を と の関数とすると、次のように書ける。 ${\displaystyle x}$${\displaystyle y}$

${\displaystyle f(x,y):=Ax+By+C=0}$

ここで定数は

• ${\displaystyle A=\Delta y=y_{1}-y_{0}}$
• ${\displaystyle B=-\Delta x=-(x_{1}-x_{0})}$
• ${\displaystyle C=(\Delta x)b=(x_{1}-x_{0})b}$

直線は、任意の任意の定数 、 、 に対して定義されます。つまり、直線上にない任意の に対して、となります。定数、、 は整数として定義されている ため、この形式には、 およびが整数である場合にのみ整数が含まれます。${\displaystyle A}$${\displaystyle B}$${\displaystyle C}$${\displaystyle f(x,y)=0}$${\displaystyle (x,y)}$${\displaystyle f(x,y)\neq 0}$${\displaystyle x}$${\displaystyle y}$${\displaystyle A}$${\displaystyle B}$${\displaystyle C}$

例えば、直線は と書くことができます。点 (2,2) は直線上にあります。 ${\textstyle y={\frac {1}{2}}x+1}$${\displaystyle f(x,y)=x-2y+2}$

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

そして点（2,3）は直線上にはない

${\displaystyle f(2,3)=(2)-2(3)+2=2-6+2=-2}$

そして、ポイント（2,1）も

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

点 (2,1) と点 (2,3) は直線の反対側にあり、正または負に評価されることに注意してください。直線は平面を半分に分割し、負の値を持つ半平面は負の半平面、もう半分は正の半平面と呼ばれます。この観察は、導出の残りの部分で非常に重要です。 ${\displaystyle f(x,y)}$${\displaystyle f(x,y)}$

スタート地点はライン上にあります

${\displaystyle f(x_{0},y_{0})=0}$

これは、線が整数座標で始まり、整数座標で終わるように定義されているためです (ただし、非整数の終点を持つ線を描画したいと考えるのはまったく合理的です)。

傾きが最大 であることを念頭に置くと、次の点が にあるべきか にあるべきかという問題が生じます。おそらく直感的には、 における直線にどちらが近いかに基づいて点を選択する必要があります。前者に近い場合は前者の点を直線に含め、後者に近い場合は後者の点を含めます。これに答えるには、これら 2 つの点の中間点で直線関数を評価します。 ${\displaystyle 1}$${\displaystyle (x_{0}+1,y_{0})}$${\displaystyle (x_{0}+1,y_{0}+1)}$${\displaystyle x_{0}+1}$

${\displaystyle f(x_{0}+1,y_{0}+{\tfrac {1}{2}})}$

この値が正の場合、理想的な直線は中点より下にあり、候補点に近くなります。つまり、y 座標が増加するはずです。そうでない場合、理想的な直線は中点を通過するか中点より上であり、y 座標は同じままです。その場合、点が選択されます。この中点における線関数の値は、どの点を選択するかを決定する唯一の要因です。 ${\displaystyle (x_{0}+1,y_{0}+1)}$${\displaystyle (x_{0}+1,y_{0})}$

隣の画像は、緑色の 2 つの候補点 (3,2) と (3,3) がある線上に選択された青色の点 (2,2) を示しています。黒色の点 (3, 2.5) は、2 つの候補点の中間点です。

あるいは、中間点で f(x,y) を評価する代わりに、点間の差を使用することもできます。この代替方法では整数のみの演算が可能になり、一般に浮動小数点演算を使用するよりも高速になります。他の方法を導出するには、差を次のように定義します。

${\displaystyle D_{i}=f(x_{i}+1,y_{i}+{\tfrac {1}{2}})-f(x_{0},y_{0})}$

最初の決定については、開始点で は中点法と同等です。この式を簡略化すると次のようになります。${\displaystyle f(x_{0},y_{0})=0}$

${\displaystyle {\begin{array}{rclcl}D_{0}&=&\left[A(x_{0}+1)+B\left(y_{0}+{\frac {1}{2}}\right)+C\right]&-&\left[Ax_{0}+By_{0}+C\right]\\&=&\left[Ax_{0}+By_{0}+C+A+{\frac {1}{2}}B\right]&-&\left[Ax_{0}+By_{0}+C\right]\\&=&A+{\frac {1}{2}}B=\Delta y-{\frac {1}{2}}\Delta x\end{array}}}$

中点法と同様に、が正の場合は を選択し、それ以外の場合は を選択します。 ${\displaystyle D_{0}}$${\displaystyle (x_{0}+1,y_{0}+1)}$${\displaystyle (x_{0}+1,y_{0})}$

を選択した場合、 の変更は次のようになります。 ${\displaystyle (x_{0}+1,y_{0})}$${\displaystyle D_{i}}$

${\displaystyle {\begin{array}{lclcl}\Delta D&=&f(x_{0}+2,y_{0}+{\tfrac {1}{2}})-f(x_{0}+1,y_{0}+{\tfrac {1}{2}})&=&A&=&\Delta y\\\end{array}}}$

を選択した場合、変更は次のようになります。 ${\displaystyle (x_{0}+1,y_{0}+1)}$${\displaystyle D_{i}}$

${\displaystyle {\begin{array}{lclcl}\Delta D&=&f(x_{0}+2,y_{0}+{\tfrac {3}{2}})-f(x_{0}+1,y_{0}+{\tfrac {1}{2}})&=&A+B&=&\Delta y-\Delta x\end{array}}}$

新しい D が正の場合、が選択され、そうでない場合は が選択されます。この決定は、後続の各ポイントの誤差を累積することによって一般化できます。 ${\displaystyle (x_{0}+2,y_{0}+1)}$${\displaystyle (x_{0}+2,y_{0})}$

アルゴリズムの導出はすべて完了しました。パフォーマンス上の問題の 1 つは、D の初期値の 1/2 係数です。これはすべて累積差の符号に関するものなので、すべてを 2 倍にしても影響はありません。

この結果、整数演算のみを使用するアルゴリズムが生成されます。

プロットライン(x0, y0, x1, y1)
    dx = x1 - x0
    dy = y1 - y0
    d = 2*dy - dx
    y = y0

    xはx0からx1まで
        プロット(x, y)
        D > 0の場合
            y = y + 1
            D = D - 2*dx
        終了の場合
        D = D + 2*dy

このアルゴリズムを(0,1)から(6,4)まで実行すると、dx=6およびdy=3の場合の次の差が得られます。 ${\displaystyle f(x,y)=x-2y+2}$

Ｄ＝２＊３−６＝０
0から6までループ
 * x=0: plot(0, 1)、D≤0: D=0+6=6
 * x=1: plot(1, 1)、D>0: D=6-12=-6、y=1+1=2、D=-6+6=0
 * x=2: plot(2, 2)、D≤0: D=0+6=6
 * x=3: plot(3, 2)、D>0: D=6-12=-6、y=2+1=3、D=-6+6=0
 * x=4: plot(4, 3)、D≤0: D=0+6=6
 * x=5: plot(5, 3)、D>0: D=6-12=-6、y=3+1=4、D=-6+6=0
 * x=6: plot(6, 4)、D≤0: D=0+6=6

このプロットの結果は右側に示されています。プロットは、線の交点 (青い円) にプロットするか、ピクセル ボックス (黄色の四角) に塗りつぶすことで表示できます。いずれの場合も、プロットは同じです。

ただし、前述のように、これはオクタント0、つまり原点から始まり、傾きが 0 から 1 の間の線で、反復ごとに x が正確に 1 増加し、y が 0 または 1 増加する線に対してのみ機能します。

このアルゴリズムは、yが増加するか減少するか（つまりdy < 0）をチェックすることで、0から-1の間の傾きをカバーするように拡張できる。

プロットラインLow(x0, y0, x1, y1)
    dx = x1 - x0
    dy = y1 - y0
    y = 1 です
    dy < 0の場合
        yi = -1
        dy = -dy
    終了の場合
    d = (2 * dy) - dx
    y = y0

    xはx0からx1まで
        プロット(x, y)
        D > 0の場合
            y = y + yi
            D = D + (2 * (dy - dx))
        それ以外
            D = D + 2*dy
        終了の場合

x軸とy軸を入れ替えることで、正または負の急勾配の実装は次のように記述できます。

プロットライン高(x0, y0, x1, y1)
    dx = x1 - x0
    dy = y1 - y0
    xi = 1
    dx < 0の場合
        xi = -1
        dx = -dx
    終了の場合
    d = (2 * dx) - dy
    x = x0

    yがy0からy1まで
        プロット(x, y)
        D > 0の場合
            x = x + xi
            D = D + (2 * (dx - dy))
        それ以外
            D = D + 2*dx
        終了の場合

完全な解決策としては、x1 > x0かy1 > y0かを検出し、描画前に入力座標を反転する必要がある。

plotLine(x0, y0, x1, y1)
     、 abs(y1 - y0) < abs(x1 - x0)
         、 x0 > x1の場合
            プロットラインLow(x1, y1, x0, y0)
        それ以外
            プロットラインLow(x0, y0, x1, y1)
        終了 if 
    else 
        if y0 > y1
            プロットライン高(x1, y1, x0, y0)
        それ以外
            プロットライン高(x0, y0, x1, y1)
        終了の場合
    終了の場合

ビデオ メモリに直接アクセスする低レベルの実装では、垂直線と水平線の特殊なケースは高度に最適化できるため、別々に処理するのが一般的です。

いくつかのバージョンでは、ブレゼンハムの整数増分誤差の原理を使用してすべての八分線の描画を実行し、x座標とy座標間の正負の誤差のバランスをとります。^[3]

プロットライン(x0, y0, x1, y1)
    dx = 絶対値(x1 - x0)
    sx = x0 < x1 ? 1 : -1
    dy = -abs(y1 - y0)
    sy = y0 < y1 ? 1 : -1
    誤差 = dx + dy
    
    真実である
        プロット(x0, y0)
        x0 == x1 && y0 == y1の場合ブレーク
        e2 = 2 * 誤差
        e2 >= dyの場合
            エラー = エラー + dy
            x0 = x0 + sx
        
        e2 <= dxの場合終了
            誤差 = 誤差 + dx
            y0 = y0 + sy
        終了の場合
    終了の場合

Bresenham アルゴリズムは、わずかに修正されたデジタル微分解析器として解釈できます(重複しないポリゴンのラスタライズに必要な 0 ではなく、エラーしきい値として 0.5 を使用します)。

除算演算の代わりに増分誤差を使用する原理は、グラフィックスの他の用途にも応用されています。この手法を使用して、テクスチャマップされたポリゴンのラスタースキャン中にU、V座標を計算することができます。 ^[4]一部のPCゲームで見られるボクセル高さマップソフトウェアレンダリングエンジンもこの原理を使用しています。

ブレゼンハムは、ランスライス計算アルゴリズムも発表しました。上記のランレングスアルゴリズムが長軸上でループを実行するのに対し、ランスライスのバリエーションは逆方向にループします。^[5] この方法は、いくつかの米国特許で表現されています。

アルゴリズムは次のように拡張されました。

• 任意の太さの線を描く。IBMのアラン・マーフィーが開発したアルゴリズム。^[6]
• 複数の種類の曲線（円、楕円、3次、2次、有理ベジェ曲線）とアンチエイリアスされた直線と曲線を描画します。Alois Zinglによるアルゴリズムのセット。^[3]

• デジタル微分解析器（グラフィックスアルゴリズム）、線と三角形をラスタライズするためのシンプルで一般的な方法
• Xiaolin Wuのラインアルゴリズムは、アンチエイリアシングを使用して線を描く同様に高速な方法です。
• 中点円アルゴリズム、円を描くための同様のアルゴリズム

• Bresenham, JE (1965). 「デジタルプロッタのコンピュータ制御アルゴリズム」(PDF) . IBM Systems Journal . 4 (1): 25–30. doi :10.1147/sj.41.0025. 2008年5月28日時点のオリジナル(PDF)からアーカイブ。
• 「ブレゼンハム線描画アルゴリズム」、コリン・フラナガン著
• Abrash, Michael (1997)。Michael Abrash のグラフィックス プログラミング ブラック ブック。ニューヨーク州アルバニー: Coriolis。pp. 654–678。ISBN 978-1-57610-174-2。ビデオゲームで使用するためにCとアセンブリでアルゴリズムを非常に最適化したバージョンで、内部の仕組みの詳細も完全に記載されています。
• Zingl, Alois (2012)。「曲線を描画するためのラスタライズ アルゴリズム」(PDF)。ブレゼンハムのアルゴリズムの美しさ

• パトリック・ギレスバンダ論文、3D隠線除去を実行するためのブレゼンハム線描画アルゴリズムの拡張を含む
  • MICAD '87 の CAD/CAM およびコンピュータ グラフィックスに関する議事録、591 ページにも掲載されています ( ISBN 2-86601-084-1)。 
• Bresenham のアルゴリズムの修正による線の太さの変更、AS Murphy、IBM Technical Disclosure Bulletin、第 20 巻、第 12 号、1978 年 5 月。
• ブレゼンハム、ジャック(1977 年 2 月)。「円弧の増分デジタル表示のた​​めの線形アルゴリズム」。Communications of the ACM。20 ( 2 ): 100–106。doi :10.1145/359423.359432。– 技術レポート 1964年1月27日 -11- サークルアルゴリズム TR-02-286 IBMサンノゼ研究所

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

• マイケル・アブラッシュのグラフィックスプログラミングブラックブック特別版: 第 35 章: ブレゼンハムは高速、そして高速であることは良いことだ
• コリン・フラナガンによるブレゼンハム線描画アルゴリズム
• ブレゼンハムのアルゴリズムに関する国立標準技術研究所のページ
• Calcomp 563 インクリメンタル プロッタ情報
• いくつかのプログラミング言語におけるブレゼンハムアルゴリズム
• ブレゼンハムのアルゴリズムの美しさ - 直線、円、楕円、ベジェ曲線をプロットするシンプルな実装