ブレゼンハム(Blesenham)アルゴリズムで直線描画
メ インへ戻る

画面上で 始点(x1, y1) から 終点(x2, y2) まで直線を描く手順を考えます。

あ、もちろん直線コマンド使わずに、直線上の点を一点づつ打っていく手順です。（＾＾）

あと、話を簡単にするために画面の左上から右下に直線を描くとします。また直線の傾きは45°以下とします。(すみませんね。条件多くて。）

ブレゼンハムアルゴリズムでの手順は以下のような感じになります。

(手順1) 始点(x1, y1) に点を打つ。
(手順2)  ｘ１＋１に移動する
(手順3)  直線とy1 との誤差 σ1 を計算する
(手順4)  σ1 が 0.5 より小さいので、(x1+1, y1) に点を打つ。
－－－
(手順5)  x1+2 に移動する。
(手順6) 直線とy1 との誤差 σ2 を計算する
(手順7)  σ2 が 0.5 以上なので、(x1+2, y1+1) に点を打つ。
－－－
(手順8)  x1+3 に移動する。
(手順9) 直線とy1+1 との誤差 σ3 を計算する
(手順10)  σ3 が 0.5 より小さいので、(x1+3, y1+1) に点を打つ。
．．．ｘ２に移動するまで続ける。

図から予想して、誤差の計算は以下のような感じになるかと思われます。



ここでよく見ると、誤差 σ の式は、Δx で割ったり、0.5 で判定したりと、実数計算になっています。

これを何とか整数だけの計算にできないかなと考えます。パソコンでは、整数計算のほうが速いですからね。

で、0.5と比較とか、Δｘで割るとかいうのを消すために、式の両辺に 2*Δx を掛けることにします。



まんまと実数計算がなくなりました。

よくみると というのが何度も出てきてうるさいので、



として、式を簡単にします。



この誤差の式を使って、上の(手順１)．．．を実行するプログラムを作ります。

(プログラム例)
こちらです → bresenham.cpp

プログラム例には、比較のため普通に直線の式を使って直線描画するルーチンも入っています。

(コンパイル方法)
MinGW の場合
$ gcc bresenham.cpp libgraphics.a

Borland C の場合
$ bcc32 bresenham.cpp graphics_bc.LIB

なお、グラフィックライブラリとヘッダファイルはこちらで配布しております。良かったら使ってみて下さい。
ここ → graphics.lib

(実行結果)
My 0.8GHz マシンで、(200,200)-(300,300)の直線を1000回描画した結果です。

$ a
elapsed = 341.983129140714820 (msec) ← こっちがブレゼンハムアルゴリズムの所要時間です。
elapsed = 363.814674770117450 (msec) ← こっちは直線の式を用いて描画した場合の所要時間です。

全然早くなってないですね。ｏｒｚ

アルゴリズムが早い遅いという以前に点を打つコマンドが遅すぎるみたいです。

一応、点を打たずに座標を計算する部分だけで勝負した場合は、こちらのような結果になります。

$ a
elapsed = 3.021892447224438 (msec) ← こっちがブレゼンハムアルゴリズム
elapsed = 8.237080411057830 (msec) ← こっちは直線の式

おお！やはりブレゼンハムさん速いじゃないですか！！

ということで、まあ、いまどきのＰＣだと普通に実数計算で直線描画してもいいのかもしれませんね。

以上です。ご機嫌よろしく。

[参考書]
「Cアルゴリズム全科 基礎からグラフィクスまで」 千葉則茂 村岡一信 小沢一文 海野啓明 著 近代科学社
(2007-05-06)
Copyright (C) 2007 Nakayama Masahito