Bresenhamの線分描画アルゴリズム
目次
ベースの考え方となるアルゴリズム（傾き$ 0 \leq \theta \leq \pi/4のとき） 最適化
線分の傾きに関して一般化
具体的な実装例
付録. $ -1 \leq \Delta y / \Delta x \leq 1の時のアルゴリズムをしっかり導出する https://scrapbox.io/files/66bb7596202bb3001d4cd0ce.png
目的：$ (x_0, y_0), (x_1, y_2)の2点を結ぶ線分$ lについて次の制約を満たしながら描く。 $ x_0 < x_1, 0 \leq \Delta y / \Delta x\leq 1（$ \Delta y = y_1 - y_0, \Delta x = x_1 - x_0）
線分を描く区間$ x_0 \leq x \leq x_1について、任意の$ xに対して塗られる画素$ (x, y)がただ一つ存在する。
$ xにおいて塗った画素の中心点$ (x, y_p)と、実際に直線が通る点$ (x, y)の誤差$ eを考える。
この誤差が全体において最小になるように、一つずつ点を打っていく。
ベースの考え方となるアルゴリズム（傾き$ 0 \leq \theta \leq \pi/4のとき） $ y_p \leftarrow y_0
for $ x \in \{x_0, x_0 + 1, \cdots, x_1\}
$ xに対して、実際の線分$ l上の点$ (x, y)を求める。
現状$ y_pに対する誤差$ e_p := y - y_pを考える。
誤差$ e_pが$ 0.5を超えたとき、$ y_pに$ 1足す。
（そうすれば、誤差が最小の点$ (x, y_p)を$ xに対して選べる。）
$ (x, y_p)に点を描く。
最適化
最適化1
（$ e_pを一から計算せず、前の計算結果を使ってもっと手早く求める）
$ y_p \leftarrow y_0
$ e_p \leftarrow 0
for $ x \in \{x_0, x_0 + 1, \cdots, x_1\}
$ e_p+= $ \Delta y / \Delta x
if $ e_p > 0.5:
$ y_p += $ 1
$ e_p -= 1
$ (x, y_p)に点を描く。
最適化2.の準備
（分数を扱う処理をなくすべく、$ e_pの計算を全てスケールする）
そのために、誤差をまず0.5減らした上で扱う
その上で、$ 2\Delta x倍にスケールする。
$ f(e) = 2\Delta x( e - 0.5)とする。
関数$ fに通した上で、不等号の条件$ e_p > 0.5を考えても、それは全く同じ意味合いを持つ。
すなわち、$ e_p > 0.5 \Leftrightarrow f(e_p) > f(0.5) = 0
このため、上記における演算はそれぞれ
$ e_p \leftarrow 0を
$ f(e_p) \leftarrow f(0) = -\Delta xに
$ e_p += $ \Delta y/\Delta xを
これは$ e_p \leftarrow e_p + \Delta y / \Delta xと解釈できて
$ f(e_p) \leftarrow f(e_p + \Delta y / \Delta x)
$ = 2\Delta x( e_p + \Delta y /\Delta x - 0.5 )
$ = 2\Delta x( e_p - 0.5 ) + 2 \Delta y
$ = f(e_p) + 2 \Delta y
従って、$ f(e_p) += $ 2\Delta yに
$ e_p -= $ 1を
これは$ e_p \leftarrow e_p - 1と解釈できて
$ f(e_p) \leftarrow f(e_p - 1)
$ = 2\Delta x( e_p - 1- 0.5 )
$ = 2\Delta x( e_p - 0.5 ) - 2 \Delta x
$ = f(e_p) - 2 \Delta x
従って、$ f(e_p) -= $ 2\Delta x
に置き換えられる
最適化2.
$ y_p \leftarrow y_0
$ f(e_p) \leftarrow -\Delta x（ $ f(e_p)を変数として扱っている）
for $ x \in \{x_0, x_0 + 1, \cdots, x_1\}
$ f(e_p)+= $ 2\Delta y
if $ e'_p > f(0.5) = 0:
$ y_p += $ 1
$ f(e_p) -= $ 2 \Delta x
$ (x, y_p)に点を描く。
線分の傾きに関して一般化
ここまでは$ 0 \leq \Delta y/\Delta x \leq 1 \land \Delta x \geq 0のとき、では一般のケースに使えるようにするためには？
まず$ -1 \leq \Delta y / \Delta x \leq 1に拡張してみる。
ざっくりと
誤差$ e_pの性質として、（$ e_p := y - y_p）
$ e_pは、$ y_pの値が変化しない限り、$ \Delta yの符号の方向に進んでいく。
$ |e_p| > 0.5であった時に、上/下のピクセルに移動させることで誤差を$ 1減少させられる。
ということで、$ \Delta yの符号の方向に合うように$ e_pか$ f(e_p)の取り方を反転させれば同じアルゴリズム（誤差の蓄積の計算方法）を使い回すことができる。 つまり、$ \Delta y > 0のときは$ e_p := y - y_p、$ \Delta y < 0のときは$ e_p := y_p - y
（この誤差はいずれの場合も負の値を取りうることに留意する）
$ f(e_p)の初期値として同じく$ -dxを選ぶ。
$ f(e_p)は必ず増える方向に足し合わせる（+=$ |2\Delta y|）。
$ y_p値を更新するときは、傾きが正なら += 1, 負なら -1
さすれば誤差$ f(e_p)はいかなる時でも$ 1減る。
ここからは残ったケースである$ \Delta x < 0 \land \Delta y / \Delta x \notin [-1 , 1\rbrackを求めていく。
$ \Delta x < 0
2点をスワップして対応する。
$ B((x_1, y_1), (x_0, y_0))
これをすると、$ (x_0, y_0), (x_1, y_1)の順に辿りたい時に困るappbird.icon
スワップするのではなく、$ xを$ \Delta xの符号の向きに$ 1ずつ進めたい
その方向に$ \Delta xが進むと誤差は絶対に増える
$ \Delta y / \Delta x < -1 \lor 1 < \Delta y/\Delta xのとき
$ x座標と$ y座標をスワップする（$ y = xに関して描く線分を対称移動してアルゴリズムを走らせる）
ただし、点を打つときは$ (x, y_p)ではなく$ (y_p, x)に点を打つ。
$ B((y_0, x_0), (y_1, x_1))
これにより全てのケースに対応することができた。
なんかもっといい方法はないかな？appbird.icon
コードが一番簡単になるのはこれだと思うappbird.icon
https://scrapbox.io/files/66bb7596202bb3001d4cd0ce.png
具体的な実装例
code:rs
// color色の点を(x, y)に打つ関数
fn draw_pixel(buffer: &mut Vec<u32>, x: usize, y: usize, color: &Color);
/**
* 点p1から点p2への線分をBresenhamの線分描画アルゴリズムによって描画する。
*/
fn draw_line(buffer: &mut Vec<u32>, p1:&Point2, p2:&Point2, color: &Color) {
// どの軸に沿って線形走査を行うかを表す。trueならばx軸に沿って線を描き、falseならy軸に沿って線を描く。
let along_x_axis = (p2.x - p1.x).abs() > (p2.y - p1.y).abs();
// 走査する軸の方向に対して、開始点と到着点が真逆になっていたときはp1とp2を入れ替えておく。
if along_x_axis && p1.x > p2.x || !along_x_axis && p1.y > p2.y {
return draw_line(buffer, p2, p1, color);
}
// |dy/dx| > 1であったときはy = xに対して対称に移動させる。
let flipped_points = (&p1.flipped(), &p2.flipped());
let (p1, p2) = if along_x_axis { (p1, p2) } else { flipped_points };
// Bresenhamのアルゴリズムの実装（ただし、|dy/dx| < 1で実行できるように拡張）
let dx = p2.x - p1.x;
let dy = p2.y - p1.y;
assert!(dy.abs() < dx.abs()); // |dy/dx| < 1
// 誤差が大きくなった場合に描画する画素の対象を正の方向にずらすか負の方向にずらすか
let s = if dy > 0 { 1 } else { -1 };
let mut y = p1.y;
let mut err = -dx;
for x in p1.x..p2.x {
err += 2 * i32::abs(dy);
if err > 0 {
y += s;
err -= 2 * dx;
}
let (x, y) = if along_x_axis {(x, y)} else {(y, x)};
if in_range(0, x, WIDTH as i32) && in_range(0, y, HEIGHT as i32) {
draw_pixel(buffer, x as usize, y as usize, color)
}
}
}
参考文献
付録. $ -1 \leq \Delta y / \Delta x \leq 1の時のアルゴリズムをしっかり導出する 最適化1.のアルゴリズムは$ \Delta y < 0について次のように書き換えられる。（$ e_p := y - y_pの定義をとって考える。）
$ y_p \leftarrow y_0
$ e_p \leftarrow 0
for $ x \in \{x_0, x_0 + 1, \cdots, x_1\}
$ e_p+= $ \Delta y / \Delta x
if $ e_p < -0.5:
$ y_p += $ -1
$ e_p -= $ -1
（つまりこう）
$ g(e_p) = -2\Delta x(e_p + 0.5)と定めれば、最適化2.のアルゴリズムも同じように書き換えられる。
$ y_p \leftarrow y_0
$ g(e_p) \leftarrow -\Delta x
for $ x \in \{x_0, x_0 + 1, \cdots, x_1\}
$ g(e_p)+= $ -2\Delta y
if $ g(e_p) > 0: （符号が入れ替わることに注意する）
$ y_p += $ -1
$ g(e_p) -= $ 2 \Delta x
$ (x, y_p)に点を描く。
総括すると、次のように書ける。$ s = \operatorname{sign}(\Delta y) = (\Delta y > 0)\; ?\; 1:-1としよう。
$ y_p \leftarrow y_0
$ e_p \leftarrow -\Delta x
for $ x \in \{x_0, x_0 + 1, \cdots, x_1\}
$ e_p+= $ 2|\Delta y| (= 2s\Delta y)
if $ e_p > 0:
$ y_p += $ s
$ e_p -= $ 2 \Delta x
$ (x, y_p)に点を描く。