ラスタ化による図形の描画

点や線、図形を数式で表したベクタ表現を、画素の集まりであるラスタ表現へ変換することをラスタ化 といいます。数式で表された図形を画素の格子に落とし込むには、「どの画素を塗ればよいか」を具体的に決める必要があります。
線分・円・ポリゴンを例に、ラスタ化の仕組みを具体的に見ていきましょう。

走査変換と画像座標系

CG

図形をラスタ化する処理は、図形の上を画素ごとに走査しながら塗るべき画素を決めていくことから、走査変換とも呼ばれます。
言い換えると、走査変換とは、図形の方程式を「どの画素を塗るか」という整数の問題に置き換える処理です。連続的な数式の世界から、離散的な画素の世界へと橋渡しする工程だといえます。

その舞台となるのが、画素の位置を表す画像座標系です。
画像座標系は、画像の左上を原点とし、x軸を右向き、y軸を下向きにとった整数の格子です。
数学で使う座標系とはy軸の向きが逆になっている点に注意が必要です。これは、画像が上の行から下の行へと走査されることに対応しています。

走査変換では、図形を構成する連続的な線を、この格子の上の画素で近似することになります。そのため、本来はなめらかな線も、拡大すると階段状のギザギザが見えてしまいます。

線分のラスタ化

CG

最も基本的な図形である線分から考えてみましょう。
始点と終点が決まった線分は、次の直線の方程式で表すことができます。$a$は直線の傾き、$b$は切片（y軸と直線が交わる点のy座標）です。

$$y=ax+b$$

素朴に考えれば、x座標を1ずつ進めながら、そのつど上の式でyを計算し、最も近い画素（yを四捨五入して整数にした座標）を塗っていけばよさそうです。

しかし、この方法では、画素ごとに傾き$a$との乗算が必要になります。画素は何万、何百万と並ぶため、トータルでの計算時間が膨れ上がってしまいます。

増分法

ここで役立つのが、増分法という考え方です。
増分法とは、計算を毎回ゼロからやり直すのではなく、1つ前のステップの結果に一定の差分（増分）を加えるだけで次の値を求める方法です。

直線の傾きは、x座標が1進んだときにy座標がどれだけ変化するかを表すものです。つまり、x座標が1増えるたびに、yの値は傾き$a$だけ増えることになります。

$$y_{n+1}=y_n+a$$

つまり、前の画素のyの値に$a$を足すだけで次のyが求まり、毎回の掛け算を省けます。
この「前の結果に増分を加える」というアイデアは、線分だけでなく、このあと見る円やポリゴンのラスタ化にも共通して使われる、走査変換の土台となる考え方です。

ただし、こうして求まるyは一般に小数になるため、実際にどの画素を塗るかを決めるには、毎回yの値を四捨五入して整数の画素に対応づける必要があります。

誤差による増分法

線分を画素に当てはめる際に知りたいのは、小数点以下を含めた厳密なyの座標ではありません。次にどの画素へ進むべきか？だけ分かればよいのです。
そこで、yの値そのものではなく、いま塗っている画素の中心からの「ずれ」だけを追いかける方法を考えます。

画素の中心を基準とし、描きたい直線がそこからy方向にどれだけ離れているかを誤差として持つようにします。x座標を1進めるごとに、傾き$a$を加えていくことで、誤差を更新していきます。

この誤差を使うと、次の画素を選ぶルールは非常にシンプルになります。

• 誤差が0.5より小さいうちは、直線はまだ同じ画素の範囲に収まっているため、y座標は更新しない
• 誤差が0.5を超えたら、直線は現在の画素の外（1つ上の行）へはみ出したことになるので、塗る画素のy座標を1増やし、誤差から1を引く

このように、誤差と0.5との大小だけで、次に塗る画素を決めることができます。この手順を擬似コードで表すと、次のようになります。

e <- 0  // 画素中心からの誤差
y <- y_start
for x = x_start to x_end:
    plot(x, y)  // 画素 (x, y) を塗る
    e <- e + a  // a = dy / dx（傾き）
    if e > 0.5:
        y <- y + 1
        e <- e - 1

ブレゼンハムのアルゴリズム

誤差による増分法は直感的ですが、誤差$e$には傾き$a$という小数の加算が含まれ、しきい値0.5との比較にも小数が登場します。画素ごとに小数の演算が残っている点で、まだ高速化の余地があります。

この小数演算をすべて整数演算に置き換えたのがブレゼンハムのアルゴリズムです。
考え方はシンプルで、画素を1つ上げるかどうかの判定式そのものを整数の式に書き換えます。

x座標を1進めたときの誤差はe + aで、これが0.5 = 1 / 2を超えたらy座標を上げるのでした。傾きa = dy / dxを代入し、両辺に2dxを掛けると、次のように小数が消えていきます。

$$\begin{array}{rl}e+\frac{dy}{dx}& >\frac{1}{2}\\ & \\ 2dx\cdot e+2dy& >dx\\ & \\ 2dx\cdot e+2dy-dx& >0\end{array}$$

最後の式の左辺を判定変数dとおけば、画素を上げる条件はd > 0という符号の判定だけになります。この判定変数は、誤差が0.5を上回っているかどうかを正負だけで表せるよう、誤差を2dx倍してずらした整数の量だといえます。

描き始めの誤差はe = 0なので、判定変数の初期値は整数だけで決まります。

$$d=2dy-dx$$

そして、0.5との比較は判定変数の正負の判定になり、誤差の更新も整数の加算に置き換わります。

d <- 2 * dy - dx  // 判定変数の初期値
y <- y_start
for x = x_start to x_end:
    plot(x, y)
    if d > 0: // 誤差が 0.5 を超えた -> 直線が上の行へ
        y <- y + 1
        d <- d + 2 * (dy - dx)
    else:
        d <- d + 2 * dy

判定変数dの更新式は、誤差eの動きをそのまま2dx倍した世界に置き換えたものです。

x座標を1進めると誤差には傾きa = dy / dxが加わりますが、これは2dx倍された世界では2dx * a = 2dyを足すことに対応します。この2dyの加算は、y座標を動かすかどうかによらず、毎ステップ必ず行われる更新です。

誤差が0.5を超えなければ、y座標はそのままなので、2dyの加算だけを行います。

    else:
        d <- d + 2 * dy

誤差が0.5を超えてy座標を1上げるときも、x座標は同じように1進んでいるため、同様に2dyの加算が必要です。これに加えて、誤差から1を引く操作（2dx倍の世界では2dxを引く操作）が重なります。そのため、加算する量は2dyから2dxを引いた2dy - 2dx、すなわち2(dy - dx)になります。

    if d > 0:
        y <- y + 1
        d <- d + 2 * (dy - dx)

ループの中に現れるのは整数の足し算と、判定変数の符号を見るだけの比較です。
小数の乗算や四捨五入を完全に排除できるため、ブレゼンハムのアルゴリズムは非常に高速で、線分描画の定番として広く使われています。

円のラスタ化

CG

線分で培った増分法の考え方は、曲線である円にも応用できます。

円を整数演算でラスタ化する代表的な手法がミッチェナーのアルゴリズムです。
これは、ブレゼンハムのアルゴリズムと同じく、各ステップで判定変数を更新しながら、円周に最も近い画素を整数演算だけで選んでいく方法です。

円のラスタ化で特に効いてくるのが、円がもつ高い対称性です。
円は中心を通る軸について上下左右に対称なだけでなく、45度の対角線についても対称です。そのため、円周のうち1/8の弧について塗る画素を計算すれば、残りの7/8は座標を符号や順序を入れ替えるだけで求められます。

つまり、実際に判定変数で計算するのは円周のごく一部だけでよく、残りは対称性を使って一気に埋められるのです。これがミッチェナーのアルゴリズムが効率的である理由です。

ポリゴンのラスタ化

CG

線分や円は図形の「輪郭」を描く処理でした。
これに対して、三角形などのポリゴン（多角形）をラスタ化するときは、輪郭の内側を面として塗る必要があります。ここで使われるのがスキャンラインアルゴリズムです。

デジタル画像を扱うときは、水平方向の画素の列が処理の基本単位となることが多く、この水平な走査線をスキャンラインと呼びます。

スキャンラインアルゴリズムでは、ポリゴンの上端から下端まで、スキャンラインを1行ずつ下へずらしていき、各スキャンラインがポリゴンの辺と交わる点を求めます。
この交点のx座標も、スキャンラインを1行進めるごとに辺の傾きの分だけ変化するため、線分のラスタ化と同様の手法で効率よく求められます。

こうして求めた左右の交点の間が、塗るべき内部の区間になります。
交点の内側を実際に塗りつぶす方法については、塗りつぶし処理 で扱います。