線分の描画

二次元図形のデジタル画像への変換処理を効率的に実行しよう． 今回は線分を対象とする．

走査変換

現代のコンピュータスクリーン（LCD や CRT）を利用する場合， 三次元の図形を CG 画像として表示するためには， まず，図形の構成要素（ポリゴンなど）を二次元に投影し， 更に，その二次元図形をディジタル画像（画素の集合） へ変換する必要がある． この画像化処理が 走査変換（scan-conversion，rasterize）である．

実用的な CG では，膨大な量の図形要素を取り扱うことになるので， 走査変換の高速化が非常に重要な技術となっている． そこで今回は，走査変換について， 次の２通りの方法でプログラミングしてみよう．

• 直接解法（低速版）

図形の方程式を直接的に解析して画像化する． 一般に，実数や乗除算（コンピュータが苦手とする演算） や冗長な計算を含むので非効率である．

ただし，最近はプロセッサ（計算用ハードウェア）の 性能進化（実数演算，並列処理，等）も著しいため， かえって，直接解法の方が高速な場合もある．
• インクリメンタル解法（高速版）

図形の方程式を差分法的に解析する． 整数の加減算（コンピュータが得意とする演算） のみで計算できるように工夫すれば，さらに効率的となる．

こうした効率的な解析法は， DDA（digital difference analyzer；ディジタル微分解析器）と総称される． 特に有力な手法としてブレゼンハムのアルゴリズム（Bresenham's algorithm）があり， 多様な図形の描画のために応用されている．

これらの手法の分類については諸説あるようです． 「ブレゼンハムは DDA の一種」とか 「ブレゼンハムは DDA と同じ」だけでなく 「ブレゼンハムは DDA とは異なる」という意見も見られます． 担当教員的には「結果は同じだが方法は異なる」と考えています．

問題の設定（線分の描画）

次のような仮定のもとで， Fig.1 のような線分（有限長の直線）を描くことにする：

• 始点を \( (x_1, \ y_1) \) ， 終点を \( (x_2, \ y_2) \) とする．

  また， \( x \) 方向の増分を \( d_x = x_2 - x_1 \) ， \( y \) 方向の増分を \( d_y = y_2 - y_1 \) と定義しておく．

• 簡単のため，２点の位置関係は \( x_1 \lt x_2 \) かつ \( y_1 \lt y_2 \) とする．
  もし，この位置関係にない場合には， 始点と終点の交換などによって対処できる．
• 簡単のため，直線の傾きは 0 〜 45度の範囲内とする．
もし，45度を越える場合には， \( x \) と \( y \) の交換によって対処できる．

直接解法および DDA による線分描画プログラムの実装例を示しておく：

• サンプルソースファイル：line.c
• コンパイル方法・実行方法：省略（ソースコードを参照せよ．）

低速アルゴリズム（直接解法）

もっとも単純な線分描画アルゴリズムは次の通り：

• 座標値 \( x \) を \( x_1 \) から \( x_2 \) まで 1 ずつ増やしながら繰り返す．
• 直線の方程式によって座標値 \( y \) を求める：
\[ y = \F{d_y}{d_x} \P({x - x_1}) + y_1 \]
• 画素 \( (x,\ y) \) を点灯する．
座標を計算 → 画素を点灯．

このアルゴリズムでは， １画素についての計算はさほど複雑ではないが， 同じような結果をもたらす乗算・除算を何度も繰り返すことになるので， 線分全体として見ると，効率が悪い．

高速アルゴリズム（インクリメンタル解法）

以下，ブレゼンハムのアルゴリズムについて解説する． DDA については，サンプルソースコードを参照せよ．

直線の方程式を変形すると：

この左辺を２倍し，誤差関数 \( f(x,\ y) \) を定義しておく：

この関数の値は：

• 直線上では \( f = 0 \)
• 直線の左上側の領域では \( f \lt 0 \)
• 直線の右下側の領域では \( f \gt 0 \)

となる． したがって，誤差関数の値がゼロとなるようなすべての画素を 探し出して点灯すれば直線が描かれることになる．

しかし，ディジタル画像（各画素の座標値は整数のみ）なので， 誤差が丁度ゼロになるような画素はほとんど存在しない． つまり，誤差ゼロの画素だけを点灯するだけでは， 直線のつもりが点線になってしまうだろう． そこで実際には，誤差関数の値がゼロに近い画素の集合を探索することになる．

なお，現在画素 \( (x,\ y) \) に対して， 隣接画素の候補は \( (x+1,\ y) \) と \( (x+1,\ y+1) \) の２箇所あるが， Bresenham のアルゴリズムでは， それらの中間地点 \( (x+1,\ y+1/2) \) の１箇所の誤差関数を検査するだけで， 正しい隣接画素を合理的に決定する．

Fig.2 は，このアルゴリズムの説明図である． 判定点（×印）と直線の位置関係に応じて， 画素 P，Q，R が順次点灯されて行く．

さらに，この処理をインクリメンタルに （実数や乗除算を使わず，整数の加減算のみで高速に）実行する：

• 座標値 \( x \) を \( x_1 \) から \( x_2 \) まで １ずつ増やしながら繰り返す．
  実装上は，０から \( d_x \) までね．
  誤差値 \( f \) と座標値 \( y \) についても初期化が必要． 始点では，\( f = 0 \) ， \( y = y_1 = 0 \) だよね．
  • 画素 \( (x,\ y) \) を点灯する．
    処理順序は，直接解法とは逆に，まず画素を点灯→ 次の座標を計算．
  • 判定点 \( (x+1,\ y+1/2) \) における \( f \) を求める．
    \[ f(x+1,\ y+1/2) = f(x,\ y) + 2 d_y - d_x \]
  • もし，\( f \lt 0 \) ならば， 直線は判定点より下側を通る．

    したがって， 次に点灯する画素は \( (x+1, y) \)となる． その座標における \( f \) を求めておく．

    \[ f(x+1,\ y) = f(x+1,\ y+1/2) + d_x \]
    なお，処理効率的には， ループ内では条件式を使いたくはないが， この判定１個だけは仕方ない．
  • でなければ（\( f \ge 0 \) の場合）， 直線は判定点より上側（または判定点上）を通る．

    したがって， 次に点灯する画素は \( (x+1,\ y+1) \) となる． その座標における \( f \) を求め， さらに \( y \) を１だけ増やしておく．

    \[ f(x+1,\ y+1) = f(x+1,\ y+1/2) - d_x\]
    条件式を無闇に増やすなー!! ...つ else
  これらの式の右辺の \( f \) には，すでに求めた数値を流用すること． 再度計算しなおすのは非効率．

DDA との比較

Fig.3 は実数版 DDA（digital differential analyzer）法の説明図である． 判定点を用いることなく， 誤差 \( e \) の蓄積を抑えながら描画経路を定めている． Fig.2 と比較せよ．

本日の課題

サンプルソースファイル line.c の中に， ブレゼンハムのアルゴリズムによる高速線分描画関数 FastDrawLineBA( ) を定義せよ．

また，処理時間を測定し，他の手法の結果と比較せよ． （処理時間は一定ではない．３回程度ずつ測定せよ．）

補足

描画結果のスクリーンショット画像を作るには， import コマンドを使えばよい．

# 撮影対象のウィンドウを前面に出しておき...
$ import  画像ファイル.png
# 対象をクリック

# 画像の確認には...
$ display 画像ファイル.png &

line.c の Raspberry Pi3 での処理時間の例：

直接解法：	0.242998 sec
DDA1：		0.168930 sec
DDA2：		0.156392 sec
DDA3：		0.151798 sec
DDA4：		0.148544 sec
BA：		...

アルゴリズムの工夫により，少しずつだが，高速化していることがわかる． RasPi のような低性能マシンだと差異が明確． 実験室の PC のような高性能マシンだと差異が不明確だったり，逆転する場合もある．