線分の描画

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

走査変換

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

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

• 直接解法（低速版）

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

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

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

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

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

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

• 始点は（x₁，y₁）， 終点は（x₂，y₂）であるとする．

また，x 方向の増分を d_x＝x₂ーx₁， y 方向の増分を d_y＝y₂ーy₁ と定義しておく．

• 簡単のため，2 点の位置関係は x₁ ＜ x₂ かつ y₁ ＜ y₂ であるとする．
この位置関係にない場合には， 始点と終点の交換などによって対処できる．
• 簡単のため，直線の傾きは 0 〜 45度の範囲内とする．
45 度を越える場合には， x と y の交換によって対処できる．

Fig.1.　線分

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

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

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

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

• 座標値 x を x₁ から x₂ まで 1 ずつ増やしながら繰り返す．
• 直線の方程式によって座標値 y を求める：

• 画素（x，y）を点灯する．

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

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

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

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

この左辺を２倍し，誤差関数 f（x，y）を定義しておく：

この関数の値は：

• 直線上では f ＝ 0
• 直線の左上側の領域では f ＜ 0
• 直線の右下側の領域では f ＞ 0

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

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

なお，現在画素（x，y）に対して， 隣接画素の候補は２個 ｛（x+1，y）と（x+1，y+1）｝存在するが， Bresenham のアルゴリズムでは， それらの中間地点（x+1，y+1/2）１箇所の誤差関数を検査するだけで， 正しい隣接画素を合理的に決定する． さらに，この処理をインクリメンタルに （実数や乗除算を使わず，整数の加減算のみで高速に）実行する：

• 座標値 x を x₁ から x₂ まで 1 ずつ増やしながら繰り返す．
誤差値 f と座標値 y についても初期化しておく必要がある． f = 0，y = 0． （本来は y = y₁ だが，実装上は 0 とみなして...）
• 画素（x，y）を点灯する．
• 判定点（x＋1，y＋1/2）における f を求める．

• f（x＋1，y＋1/2）< 0 ならば， 直線は判定点より下側を通る．

したがって， 次に点灯する画素は（x＋1，y）となる． その座標における f を求める．


• または f（x＋1，y＋1/2）≥ 0 ならば， 直線は判定点より上側（または判定点上）を通る．

したがって， 次に点灯する画素は（x＋1，y＋1）となる． その座標における f を求め，y を１だけ増やす．


これらの式の右辺の f には，すでに求めた値を流用すること． 再度計算しなおすのは非効率．

Fig.2 は，このアルゴリズムの説明図である． 判定点（×印）と直線の位置関係に応じて， 画素 P，Q，R が順次点灯されて行く． （Fig.2 では，格子点が画素の中心点を表わしている．四角形が画素ではない．）

Fig.2.　ブレゼンハムのアルゴリズムによる線分の描画

本日の課題

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

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

ソースコードのありがちなまちがい：

• 誤差関数 f(x, y) の定義式をそのままソースコードに記述...
説明を良く読め．漸化式で計算するんだ． 数学的には誤差「関数」と呼んではいるが， Ｃ言語的には誤差「変数」として実装する． また，誤差の初期値も重要．
• 実数型変数を使用...
使うなー．整数型だけを使うんだ．

よくある変な描画結果：

• 水平な線分しか描けない...
• 45度の線分しか描けない...
条件分岐の処理を見直そう． 座標 y のインクリメントの有無などを中心に...

上級者向け：

• 問題の設定における制限 （傾きが 0 〜 45°範囲内とか増分が正とか）を解除してみよう．

基本的には，計算部をそのまま流用しておき， 画素点灯時に，｛x と y｝とか｛＋ と ー｝とかを交換するだけで済むハズ．

• 上に紹介したアルゴリズムには， わかり易さのために，ちょっとだけ無駄な計算が含まれている． それを効率化してみよう．

足し算の後で足し直したり引き直したりしている部分が無駄． （結果的には，サンプルソースの DDA4 とかと同じになるだろう．）

コードをわずかに変更するだけでも，実行速度が劇的に変化する場合がある． 最速コードを見つけ出そう．
• 実行環境（PC の機種等）を変えて実験してみよう．
コンパイラ，OS，CPU，等が異なれば，測定結果の傾向も異なる． 高速版のハズなのに低速になってしまう場合もある．

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

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

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