ブレゼンハムのアルゴリズム
Wikipedia(en):Bresenham's line algorithm
始点と終点を結ぶ線分を描画する*1アルゴリズム。基本的に加減算だけしか利用しないので高速だとか*2。以下、メモ。ちなみに、これは本来のアルゴリズムとはちょっと違うとかなんとか。
図の上で
とりあえず図*3のような線分を考える。なんだか不自然に見えるかもしれないが、y軸が下向きに正なのでこれが自然なのだ。それと、傾きが1より小さい場合だけを考えることにする*4。
さて、まず、(x1, y1)を塗るのは確実だが、その次に塗るピクセルは(x1+1, y1)または(x1+1, y1+1)である*5。この二つのどちらを塗るかの判定を繰り返していけばきちんとした線分が描けるのだ。
ではどのようにして判定するのか。図の点*6(x1+1, y1+0.5)から出ている矢印*7に注目してほしい。この矢印はx=x1+1における線分とy=y1+0.5との距離を表している。矢印が下を向いている*8ということは、x=x1+1において線分がピクセル(x1+1, y1+1)に入り込んでいるということである。ということで、ピクセル(x1, y1)の次はその斜め下、(x1+1, y1+1)を塗る。
その次は、点(x1+2, y1+1.5)から出ている矢印に注目する。と、今度は上を向いている。つまり、x=x1+2ではまだ線分がピクセル(x1+2, y1+2)に入り込んでいないということなので、ピクセル(x1+2, y1+1)を塗る。その次は矢印は下を向いているので斜め下に移動して、ここで終点。
もう少しまとめよう。
x軸方向へ自動的に移動しながら描画していると考えるともう少し簡単。
- 隣の矢印が上を向いている
- 移動なし
- 隣の矢印が下を向いている
- ひとつ下のピクセルへ移動し、矢印もひとつ下へずらす
さて、これを終点まで繰り返せば線分が描ける。では、矢印の向きを決定する方法を考えよう。
式にする
さて、数学しよう。x方向の変化量をb、y方向の変化量をaとする*9と、この二点を結ぶ直線の方程式はy=(a/b)x+cと表される。ここで、cはいわゆる「y切片」であるが、とりあえずcのまま置いておく。
さて、さっきの式を変形すると、by-ax-bc=0となる。両辺にbをかけて移項しただけだ。これを少しいじってf(x, y)=by-ax-bcとすると、f(x, y)は点(x, y)が直線の上にあるのか下にあるのかを判定する関数となる。
さて、いまピクセル(x, y)にいるとすると、次に着目すべき矢印は(x+1, y+0.5)に存在する。つまり、この点と直線の位置関係を調べればよい。具体的には、f(x, y)に代入して得られる値b(y+0.5)-a(x+1)-bcの符号を確認して、正ならばそのまま次へ進み、負ならばyに1を加算して進むことを繰り返せば、各xに対して描画すべき点のy座標値が求まる。
しかし、これでは効率が悪い。第一に、毎回乗算が存在する。それどころか、整数倍以外が存在する。0.5倍の部分は全体を2倍しておけば結果は変わらず整数にできるが、ともかく乗算処理が多すぎる。第二に、cが消えていない！
ということで、乗算を加算で済ませることにする。べつに難しくは無い。y軸方向の移動が必要な場合とそうでない場合それぞれのf(x, y)の変化量を計算する。まず必要な場合。
f(x1+m+1, y1+n+1)-f(x1+m, y1+n)
={b(y1+n+1)-a(x1+m+1)-bc}-{b(y1+n)-a(x1+m)-bc}
=b-a
つまり、fが負ならば、yに1を加算した次のfは前のfより(b-a)だけ大きいということ。fが関数である必要がだんだんなくなってきました。次は移動が必要でない場合。
f(x1+m+1, y1+n)-f(x1+m, y1+n) =-a
これでさらに単純になった。はじめにd=f(x1+1, y1+0.5)として、
- dが負ならば
- yに1を加算、dにb-aを加算、描画
- dが正ならば
- dに-aを加算、描画
を終点まで繰り返せばOK。
さいごに、dの初期値を求めよう。一番最初に着目する矢印は(x1+1, y1+0.5)だから
d=b(y1+0.5)-a(x1+1)-bc
ところで、点(x1, y1)はちょうど線上にあるから、by1-ax1-bc=0、すなわちbc=by1-ax1だ。これを代入すると、
d=b(y1+0.5)-a(x1+1)-(by1-ax1) =0.5b-a
となる。整数演算だけで済ませたいのだが、必要なのはdの符号だけだから、全体を二倍にしてもかまわない。ということで、最終的に
- dの初期値は(b-2a)
- dが負ならば(2b-2a)を加算、yに1を加算、最初に戻る
- dが正ならば(-2a)を加算、最初に戻る
ということになる。ほらできた。
コードにする
ということで、一応コードを書こう。D言語で恐縮*10だが、まぁCが読める人なら読めるだろう。あと、高速化案募集。
そういえば、abs()関数と条件分岐、どちらが高速だろう。絶対値を取る関数はプロセッサに存在したりするのか？
//始点(x1, y1),終点(x2, y2); int a = abs(y2 - y1), b = abs(x2 - x1); //x, yに加算される値。線分の向きによって符号が変わる。 int dx = 1, dy = 1; if(x2 < x1) dx = -1; if(y2 < y1) dy = -1; bool swap = (a > b); if(swap) { //適宜xとyを入れ替える a = abs(x2 - x1); b = abs(y2 - y1); } //`<<'はビットシフト。高速に二倍する(はず)。 int df1 = ((b - a) << 1); //dが負のときに加算(2b-2a) int df2 = -(a << 1); //dが正のときに加算(-2a) int d = b - (a << 1); //dの初期値(b-2a) //始点だけ別個に描画する。 //ここで(x1, y1)に描画 if(swap) { //xy反転バージョン //終点まで回れ while(y1 != y2) { //下へ移動 y1 += dy; if(d < 0) { //横へ移動 x1 += dx; d += df1; } else d += df2; //ここで(x1, y1)に描画 } } else { //普通に //終点まで回れ while(x1 != x2) { //横へ移動 x1 += dx; if(d < 0) { //下へ移動 y1 += dy; d += df1; } else d += df2; //ここで(x1, y1)に描画 } }
