線分の描画

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

本ウェブページ内の数式表示には， MathJax （外部サービス）を利用させていただいております． 学内から正しく閲覧するには，プロキシ経由での接続が必要です．

走査変換

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

走査変換による CG は ラスタグラフィックスと呼ばれている． ラスタとは，昔のCRT（ブラウン管）の水平走査線のことだ．

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

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

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

Fig.1.　線分

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

なお，表示される画像中の \( y \) 軸の正方向は， 上向きではなく下向きであることに注意． （一方，IT 界のスクリーン座標系では，歴史的な慣例で，y 軸は下向き． 数学界のグラフ座標系とは異なる．）

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

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

プログラムの実装の際には，簡単化・効率化のために， 始点を \( ( x_1 = 0 ,\ y_1 = 0 ) \) ， 終点を \( ( x_2 = d_x ,\ y_2 = d_y ) \) とみなす． そして， 方程式 \( y = \DS\F{d_y}{d_x} x \) の計算について， \( x \) を 0 から \( d_x \) まで変化させて繰り返す． 最後に座標を元に戻し， 画素 \( ( x + x_1,\ y + y_1 ) \) を点灯する． 今回のサンプルプログラムでも，この方法を利用している． （以下の理論展開では，この方法は使われていない． 適切に読み替えるんですよー．）

また，計算式自体は実数演算だが， 画面上の座標 \( (x,\ y) \) は整数値であることに注意．

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

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

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

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

\[ d_y \P({x - x_1}) - d_x \P({y - y_1}) = 0\]
上述の通り，\( ( x_1 = 0 ,\ y_1 = 0 ) \) として良いんですよー．

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

\[ f(x,\ y) = 2 \P\{{d_y (x - x_1) - d_x (y - y_1)}\} \]

なぜ２倍するのか？ 後述のアルゴリズムの実行中，関数値を常に整数に保つためだ．

座標値は基本的には整数なのだが， 四捨五入のために 1/2 刻みの実数と考える場面もある． しかし，その場面でも，係数２によって， 関数値は１刻みの整数のままにできる．

この関数の値は：

なお，ここではまだスクリーン座標系ではない． Fig.1 のように，左向きが \( +x \)，上向きが \( +y \)， として説明していることに注意．

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

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

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

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

Fig.2.　ブレゼンハムのアルゴリズムによる線分の描画
Fig.2 では，格子点（十文字）が画素の中心点を表わしている． 格子（四角形）が画素ではない．

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

クドいですが，プログラムの実装の際には， 簡単化・効率化のため，直接解法と同様に... \( (x_1 = 0,\ y_1 = 0) \) とみなして... 画素 \( (x+x_1,\ y+y_1) \) を点灯... サンプルファイル内の DDA 等のソースコードを参考にせよ．

本日の課題

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

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

今回のプログラムでは出力デバイスとして，GPUではなく，文字端末を利用しており， プログラム全体に対して出力処理が占めるコストの割合が非常に大きい． したがって，できるだけ純粋にアルゴリズムの計算処理にかかるコストだけを比較するために， 画像出力 off の状態で実行時間を測定すること!!
さらに，当然だが...速度比較の前に， 描画結果が正しいことを確認しておくこと!!
ソースコードのありがちなまちがい
これらは計算コスト的な問題． 特に，ループ内では影響が大きい．小さな無駄でも積み重なると大きな無駄となる．
ループ外なら多少はOK． しかし，メインループから何度も呼び出されるのでやはり...
ループ前に処理を追加（初期投資）することで，ループ内の処理を削減し， 全体的なコストを大幅削減する，という戦略もあり得る．
描画結果のありがちなまちがい
考察方法のアドバイス

性能比較では，単純な差（時間が「○秒早い」とか）ではなく 比率（時間が「○％削減」とか速度が「○倍」とか）を挙げるべきでしょう．

例えば，同じ１秒短縮にしても...

科学的に!!

上級者向け追加課題

（レポートに説明があれば加点対象．）

レポート提出

補足

描画結果のスクリーンショット画像を作るには， 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 のような高性能マシンだと差異が不明確だったり，逆転する場合もある．

(c) 2023, yanagawa@kushiro-ct.ac.jp