自分が小さい頃に知ったアルゴリズムで、よくよく考えれば単純なものですが仰々しい名前もついている、そんなものを紹介していきます。
概要
「デジタル差分解析」とは、描画に際して整数の加減算とシフトだけで済ませるための技法です。今回は、簡単な「直線を引く」場合を考えてみます。
前提とするグラフィックス環境
今の時代は、スマホですらGPUがあって3DCGを平然と実行できますが、このアルゴリズムが前提とするのは、VRAMが直接あって、何かを描画するには1ドットずつメモリを書き換える必要がある、そんな原始的な環境です。もちろん、直線を引くAPIなんてあるはずもありません。
そして、SIMDどころか浮動小数点演算、整数の乗除算なども高価な演算とみなされていました。
ということで、ハーフトーンなんて贅沢なことは考えず、ペイントで出てくるような1ドット単位でつないでいく線を描くようなことを考えていきます。
普通にやろうとした場合
水平、垂直な線を引く場合、アルゴリズムを考えることもなく決まりますので、傾きのある線に限定します。$(x_0, y_0)$ から $(x_1, y_1)$ へ引いた線の方程式は、（前述のように $x_0 \neq x_1$ なので）
$$
y= \frac{y_1 - y_0}{x_1 - x_0}(x - x_0) + y_0
$$
のようになります。数学であれば、これを $x_0$ から $x_1$ まで動かす…とすればいいのですが、コンピューターの場合ドットの数が決まっていますのでそうもいきません。
単純化
とりわけ、傾きが1を超える場合、$x$ を動かしてプロットしていては $y$ が飛び飛びになってしまってうまくいかないので、式を逆にして $y$ から $x$ を計算する必要があります。また、実際には起点の位置や線の方向などでいろいろ場合分けしないといけないのですが、アルゴリズムを考える上では煩雑になるので、いったんシンプル化します。
「左下が原点のxy平面で、$(0, 0)$ から $(x_1, y_1)$ まで線を引く（ただし、$y_1 < x_1$ ）」
こうすれば、方程式は $y = (y_1/x_1) x$ までシンプルになります。
演算をシンプルにする
式のとおりに計算するなら、浮動小数点数の乗除算が必要となります。少しシンプルにするには、$x$ を1ずつ動かした場合に $y$ の増える量は $y_1/x_1$ と決まっていますので、これを足し算していけば、そのたびごとの乗除算は不要となります。
さらに、浮動小数点数の演算を不要とするための方法として、「$x$ の1の変化に対して、$y$ の変化は1以下」ということを利用することが考えられます。まず、そのままの演算処理を下のように分解してみます。
-
x = 0, y = 0, yの端数= 0の状態からスタートする -
xを1ずつ増やしつつ。以下の操作を行う-
yの端数にy_1/x_1を足す。 -
yの端数が0.5以上なら、yに1を足して、yの端数から1を引く。
-
ここで、yの端数にx_1を掛け算して処理を進めると考えると、浮動小数演算が不要となります。
-
x = 0, y = 0, yの端数= 0の状態からスタートする -
xを1ずつ増やしつつ。以下の操作を行う-
yの端数にy_1を足す。 -
yの端数がx_1 >> 1以上なら、yに1を足して、yの端数からx_1を引く。
-
このように、「どうせ1ドット単位でしか描画できない」ことを積極的に使って、計算強度を削減していくのが、デジタル差分解析と呼ばれる技法です。