円の描画

前回の線分生成と同様な手法で，円の走査変換をプログラミングしてみよう．

今回も MathJax を利用させていただいております．

問題の設定（円の描画）

次のような設定のもとで， Fig.1 のような円周を描くことにする：

中心点を \( (x_0,\ y_0) \)，半径を \( r \) とする．
中心角 0 〜 45度の 1/8 円弧（太線部分）だけを計算し，残りの 7/8 円弧（破線部分）については円の対称性を利用して補なう．

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

もっとも単純な 1/8 円弧の描画アルゴリズムは次の通り：

座標値 \( y \) を \( y_0 \) から \( \P({y - y_0}) \ge \P({x - x_0}) \) となるまで１ずつ増やしながら繰り返す．
- 円の方程式によって座標値 \( x \) を求める．
  \[ x = x_0 + \sqrt{r^2 - \P({y - y_0})^2} \]
  
  ちなみに円の方程式は：
  \[ \P({x - x_0})^2 + \P({y - y_0})^2 = r^2 \]
- 画素 \( (x,\ y) \) を点灯する．

この方法では，実数演算（平方根）と乗算（自乗）があるので，処理速度的に不利である．

他の単純な方法としては，多角形近似がある．短い線分を組み合わせて，円を表現する．しかし，頂点座標を三角関数（sin，cos）によって算出する必要があり，やはり，処理速度の問題がある．三角関数のルックアップテーブル（事前に算出しておいた数値配列）を利用する方法もあるが，それでも実数の乗算を伴う．

なお，プログラムを実装する際には，前回の線分と同様， 簡単化・効率化のために， \( x_0 = 0 \) ，\( y_0 = 0 \) とみなして計算し，画素 \( \P({x_0 + x,\ y_0 + y}) \) を点灯する．また，この場合には，円の対称性より，次のような８個の画素を点灯すれば 0 〜 360度の円が完成することになる：

\( \P({x_0 + x,\ y_0 + y}) \)
\( \P({x_0 + x,\ y_0 \Red{-} y}) \)
\( \P({x_0 \Red{-} x,\ y_0 + y}) \)
\( \P({x_0 \Red{-} x,\ y_0 - y}) \)
\( \P({x_0 + \Blue{y},\ y_0 + \Red{x}}) \)
\( \P({x_0 + \Blue{y},\ y_0 - \Red{x}}) \)
\( \P({x_0 - \Blue{y},\ y_0 + \Red{x}}) \)
\( \P({x_0 - \Blue{y},\ y_0 - \Red{x}}) \)

ちなみに，\( y \) 座標から \( x \) 座標を求めるための数式のＣ言語コードは：

x = (int)round(sqrt((double)(r*r - y*y)));	// round() は四捨五入の関数

低速アルゴリズムでは，この式を利用することになる．

または：（低速版の多少の高速化）

x = (int)(sqrt((double)(r*r - y*y)) + 0.5);

両者は同じような計算なのに，なぜ処理速度が変わるのか？計算方法に多少の違いがある他，関数の呼出や戻り値の返却の処理にも時間を要するので... 一般に，ループ内での関数呼出は処理速度低下を招く．

ただし今回は，低速版と高速版とを比較したいので，前者の関数 round() を使い，差を明確化しておきましょう．

また，本来なら関数 Plot() も（さらに，その実体である mvaddch() も）ループ内では使いたくないところだが，描画できなくなるのも困るので，これは低速版・高速版ともに気にしないでおこう．

関数 Plot() の８回呼出のコストを軽減するには，こんな関数を利用するとよいだろう：

void Plot8(int x0, int y0, int x, int y, char c)
{
	if (!target) return;

	mvaddch(y0-y, x0-x, c);
	mvaddch(y0-y, x0+x, c);
	mvaddch(y0+y, x0-x, c);
	mvaddch(y0+y, x0+x, c);

	mvaddch(y0-x, x0-y, c);
	mvaddch(y0-x, x0+y, c);
	mvaddch(y0+x, x0-y, c);
	mvaddch(y0+x, x0+y, c);
}

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

前回紹介したブレゼンハムのアルゴリズムを応用すれば，直線だけでなく，円についても，整数のインクリメンタル計算による高速描画が可能である．

円の方程式より次の誤差関数が得られる：（定義式）

\[ f(x,\ y) = 4 \P\{{\P({x - x_0})^2 + \P({y - y_0})^2 - r^2}\} \]

なぜ４倍？前回は２倍だったなー．類推!!

この関数の値は：

円周上では \( f = 0 \)
円外では \( f \gt 0 \)
円内では \( f \lt 0 \)

アルゴリズムについては，Fig.2 の説明図および前回の高速アルゴリズム（ブレゼンハムの線分生成アルゴリズム）を参考にして考えてみよう．

なお，アルゴリズム中で利用される計算式は次の通り：（漸化式）

判定点× での誤差：
\[ f(x-1/2,\ y+1) = f(x,\ y) + 5 - 4 \P({x - x_0}) + 8 \P({y - y_0}) \]
判定点が円内だった場合，次に点灯する画素（円外）での誤差：
\[ f(x,\ y+1) = f(x-1/2,\ y+1) - 1 + 4 \P({x - x_0}) \]
判定点が円外（または円周上）だった場合，次に点灯する画素（円内）での誤差：
\[ f(x-1,\ y+1) = f(x-1/2,\ y+1) + 3 - 4 \P({x - x_0}) \]

これで，元々は２乗を含んでいた誤差関数を，簡単な整数の足し算とシフト演算（ \( 2^n \) 倍）だけで計算できるようになった．

前回同様，コンピュータには，定義式では計算させない． 漸化式で計算させる．

右辺の関数値 \( f \) の部分には，既に計算済みの変数値を使う．ループ内で関数 \( f \) を定義式通りに何度も再計算してしまうのは非効率．

なお，このアルゴリズムでも，実装上は， \( x_0 = y_0 = 0 \) として計算し，画素 \( \P({x_0 + x,\ y_0 + y}) \) 等を点灯する方が簡単．

本日の課題

前回作成したプログラム line.cを元にして，ディジタル円を生成するための関数の低速版 SlowDrawCircle() および高速版 FastDrawCircle() を定義し，実行速度を比較せよ：

void SlowDrawCircle(int x0, int y0, int r, char c)
{
	...
}

void FastDrawCircle(int x0, int y0, int r, char c)
{
	...
}

高速版では，無駄な計算を極力排除するよう，工夫すること．前回の注意事項も参考にしよう．

まずは，円を正しく描画できることを確認すること．その後で速度計測だ．

前回の線分描画では効果を実感できなかったかもしれないが，今回はかなりの高速化が期待できるだろう．

上級者向け追加課題

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

円を高速に塗り潰すための関数 FastPaintCircle() も定義してみよう．
いろいろなアルゴリズムが考えられる：
- 円周上の位置を求めてから，対称軸（ \( y \) 軸）から円周まで水平線を描く．（基本的にはBAと同じ．Plot()を差し替える．）
- 円内にいることをチェックしながら，対称軸から水平線を徐々に延ばしてゆく．（BAとは異なる．円内かどうかをインクリメンタル計算によりチェック．）
- ...
どれが速い？
楕円を高速に生成するための関数 SlowDrawOval() および FastDrawOval() も定義してみよう．
楕円の方程式：
\[ \P({\F{x - x_0}{r_x}})^2 + \P({\F{y - y_0}{r_y}})^2 = 1 \]
多分，1/8領域ではなく1/4領域を単位として，高速アルゴリズムが考えられる：
- 1/4領域をさらに，\( x \) から \( y \) を求める部分と \( y \) から \( x \) を求める部分とに分け，それぞれの部分に対して BA を適用する．
- 次に点灯すべき画素の候補を３点 \( (x-1,\ y) \) ， \( (x-1,\ y+1) \) ， \( (x,\ y+1) \) とし，選択基準を２点 \( (x-1/2,\ y+1) \) および \( (x-1,\ y+1/2) \) とする．
どちらも，楕円の輪郭線が途切れて点線にならないようにするための措置ね．隣接画素が離れてしまわないように注意しよう．

レポート提出

提出方法：電子メール
- 宛先：yanagawa@kushiro-ct.ac.jp
- 件名：cg-1108
提出期限：11月20日（水）17:00
提出内容（本文）：
- 学年・分野，出席番号，氏名
- 定義した関数（２個以上）のソースコード
- 処理時間（図形表示なし）の測定・比較結果（３回程度の平均値や代表値，授業用PC以外で実験した場合には実行環境も明記）
- （工夫事項・問題点・改善案の説明など）
提出内容（添付）：
- 描画結果（図形表示あり）のスクリーンショット画像

おまけ

円と三角形の塗り潰しのアルゴリズムについて，参考資料（2007年度の課題）に説明がある．