ブレゼンハムのアルゴリズムが何で上手くいくかわからなくて悩んだので、備忘録として導出をまとめました。
ブレゼンハムのアルゴリズムとはなんですか？
ブレゼンハムのアルゴリズムは、コンピュータで直線を高速に描画するためのアルゴリズムです。浮動小数点演算や複雑な乗算を使わずに整数のみで計算を行うため、高速で計算が可能です。
擬似コード
// 傾きが0以上1未満のとき用
void drawLine(int x0, int y0, int x1, int y1){
int x = x0;
int y = y0;
int e = -(x1-x0);
while(x<=x1){
drawPoint(x,y);//(x,y)のピクセルを塗りつぶす関数
x++;
e += 2*(y1-y0);
if(e >= 0){
y++;
e -= 2*(x1-x0);
}
}
}
何をやっているの？
やりたいのは、始点から終点までの線分を連続した整数座標で近似することです。
始点$(x_0,y_0$)から終点$(x_1,y_1)$を繋ぐ直線の式は、
$$
\frac{x-x_0}{x_1-x_0}=\frac{y-y_0}{y_1-y_0}
$$
これを一次関数の形に書き直すと、
$$
y= \frac{y_1-y_0}{x_1-x_0} (x-x_0)+y_0
$$
ここで、傾きが$\frac{y_1-y_0}{x_1-x_0}$であることに注目してください。
$x$を1増やすと$、y$は$\frac{y_1-y_0}{x_1-x_0}$増加します。これを繰り返すと、
$(x_0,y0)$→$(x_0+1,y_0+\frac{y_1-y_0}{x_1-x_0})$→$(x_0+2,y_0+2\cdot \frac{y_1-y_0}{x_1-x_0})$→…
と増加していきます。$x$の方は既に整数なので、$y$の方を四捨五入すれば、いい感じに整数値で近似できそうですね、
ただ、この方法には問題があります。
傾きを何度も足すことで、誤差が大きくなってしまうことです。
そこで、その代わりとして、$y$を四捨五入した値$y’$と、真の値との誤差$e=y-y’$を保持することにします。
$e$を誤差として初期値を0にし、$\frac{y_1-y_0}{x_1-x_0}$ずつ増加させていき、0.5を超えたら$y$を1増やして$e$を1減らすことで、四捨五入を再現します。
こうすれば、$y’$は整数だし、-$0.5<e<0.5$なので、加算を繰り返しても誤差はそれほど大きくなりません。
このアルゴリズムで擬似コードを書いてみます。
void drawLine(int x0, int y0, int x1, int y1){
int x = x0;
int y = y0;
int dx = x1 - x0;
int dy = y1 - y0;
double dydx = (double)dy/dx;
double e = 0.0;
while(x<=x1){
drawPoint(x,y);//(x,y)のピクセルを塗りつぶす関数
x++;
e += dydx;
if(e >= 0.5){
y++;
e -= 1.0;
}
}
}
さて、先ほどは誤差がそれほど大きくならないと言いましたが、実はこのコードにもまだ問題があります。
$e$に浮動小数点を使っていることによる誤差です。できれば整数だけで計算を行いたいです。
そこで、誤差$e$に$2(x_1-x_0)$をかけた値を代わりに保持します。
そうすると、eに加算する値は$\frac{y_1-y_0}{x_1-x_0}\cdot 2(x_1-x_0) =2(y_1-y_0)$になり、
条件式は$e >= 0.5 \cdot 2(x_1-x_0)=x1-x0$になり、$e$をint型で扱えるようになります。
このやり方に書き換えたコードが以下です。
void drawLine(int x0, int y0, int x1, int y1){
int x = x0;
int y = y0;
int e = 0;
while(x<=x1){
drawPoint(x,y);//(x,y)のピクセルを塗りつぶす関数
x++;
e += 2*(y1-y0);
if(e >= (x1-x0)){
y++;
e -= 2*(x1-x0);
}
}
}
さらに、$e$の初期値を$-(x1-x0)$にすることで、条件分岐をシンプルにしましょう。
void drawLine(int x0, int y0, int x1, int y1){
int x = x0;
int y = y0;
int e = -(x1-x0);
while(x<=x1){
drawPoint(x,y);//(x,y)のピクセルを塗りつぶす関数
x++;
e += 2*(y1-y0);
if(e >= 0){
y++;
e -= 2*(x1-x0);
}
}
}
これで、上記の擬似コードが得られました。
参考
https://ja.wikipedia.org/wiki/ブレゼンハムのアルゴリズム