Deprecated: The each() function is deprecated. This message will be suppressed on further calls in /home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php on line 456

11/25 悠久のデジタル積分解析 / 嗚呼、憧れの大地よ[PartII]

　あらすじ・・・とにかく地形を出したくてしようがない清3Zは、可視頂点を求めるよい方法はないじゃろかーと考えはじめた。
　いろいろウダウダかんがえた挙げ句、やっぱりオーソドックスにやるのがいちばんよさそうだという非常につまらない結論に達したのだった。

Scan conVersion method

　前回までの妄想で、とにかくスキャンコンバージョンがやはり予想通り一番効率がよいのではないかという結論(?)に達した。

　そこで、スキャンコンバージョン法を使って可視頂点領域を適切に求めるプログラムを作ってみることにした。

　そもそもスキャンコンバージョン法とは、多角形を縦方向に走査(スキャン)しながら多角形を塗りつぶすための方法である。

　簡単にいえば、多角形を構成するそれぞれの辺とスキャンラインという水平線との交点を求め、その交点同志を結ぶだけの方法である。

　ただこれだけのことなのだが、たとえばこれが窪んだ形の多角形だったりすると、問題は複雑化し、容易にはできなくなる。

　そこで大抵の場合、スキャンコンバージョンされる多角形は凸多角形であるという条件を設ける(この例外はアウトラインフォントを描画するときくらいだ)。そうすると、スキャンライン上の交点は、常に二点以下となり、大変効率化しやすい。

　そして実際のプログラムは、この「交点の算出」を馬鹿正直に方程式を解いて求めたりはしない。そんなことをすれば、画面上のドットとの整合性が失われ、問題をいたずらに複雑化してしまうだろう。
　(たいていの場合はだれでもそうだが)賢明なプログラマは、問題が複雑になることを嫌い、処理時間のかかる浮動小数点を憎む。そのため、もっとも効率の良い「交点」を求めるアルゴリズムをなんとか考え出すのである。

　もっとも、それは計算幾何学という言葉が産まれた頃くらいの大昔からあるよくしられたやり方をほんの少しだけ応用すればよい。
　そう、ブレゼンハム法を使うのだ。

　

　よくできたアルゴリズムほど単純なものだが、ブレゼンハム法もまた原理は単純である。
　通常、直線の方程式は数を連続量として現すのだが、実際に画面に描画するときには、ピクセル単位で現さなくてはならない。つまり必要なのは断続量とでも言うべきものである。

　右の図によく着目すれば、いくつかの大切なことがわかるだろう。

　桝目は画面上の画素(ピクセル)を表している。
　このような線分の場合、X軸方向にいくつか進んだあと、Y軸方向に必ず1ピクセルづつ進んでいる。

　この性質に着目すると、ブレゼンハム法の実態が見えてくる。
　
　まずは問題を単純化するために、必ず傾きが1以下のX軸方向に長い(平べったい)半直線を描くことにしよう。

　原点を始点とし、半直線の傾きをmとすると、List1のような簡単なプログラムでこの直線を描画できる。

List 1


int x,y;
float m,fy;
x = y = 0;
fy = 0; m = [直線の傾き]
while(1){ // 直線を描き続ける
	
	y = (int)(fy+0.5);// fyを四捨五入して整数化
	
	drawPixel( x , y ); // 点を描画
	
	x++;
	fy += m;
	
}

　このプログラムは、あらゆる意味で率直すぎるが、しばしばわかりやすい。

　fyには傾きの値を足し続け、それを四捨五入したものがディスプレイ上でのy座標となる。
　さきほど何故、傾きを１以下に限定したのかという理由は、これでお分かりいただけるだろう。傾きが１よりも大きいと、この場合線が途切れ途切れになってしまうのだ。
　しかし、傾きが１以下の場合と、そうでない場合の違いは、x座標を基準とするかy座標を基準とするかの違いでしかない。
　たとえば傾きが１よりも大きい場合のプログラムは、List1のxとyを単純に入れ替えるだけでよい。

List 2


int x,y;
float m,fx;
x = y = 0;
fx = 0; m = [直線の傾き]
while(1){ // 直線を描き続ける
	
	x = (int)(fx+0.5);// fxを四捨五入して整数化
	
	drawPixel( x , y ); // 点を描画
	
	y++;
	fx += m;
	
}

　間違ってdrawPixelのパラメータまで入れ替えてしまうとList1とList2の実質的な差異は消滅してしまうので注意が必要だが、これも見たとおりのものである。

　しかし、このプログラムには大いなる無駄がある。

　第一の無駄は、四捨五入だ。

　なぜなら、y座標(list2ではx座標)はあるタイミングで１づつ繰り上がるだけだからである。
　もうひとつ、無駄というよりも、このプログラム自体が持つ深刻な問題は、傾きを浮動小数点として扱うということである。

integer

　浮動小数点とは、物理学などで用いる有効桁数の概念をコンピュータの内部表現として持ち込んだものである。

　たとえばアボガドロ定数は下のように表す。

6.02 x 10

　これと同じことを、コンピュータの二進数で行わせるのである。
　だから、32ビットの浮動小数点表現と、整数表現の直接の互換性は皆無と言ってよい。

　この浮動小数点の扱いかたに関しては、国際組織であるIEEEが制定したIEEE-754が広く用いられている。

　これによれば、32ビット浮動小数点の場合は、十進数にして有効桁は約６桁となる。

List 3


void brezenhamL(int x1,int y1,int x2,int y2,int *buf){

	
	double m,fx,fy;
	int x,y,i,dx,dy,sx=1,sy=1;

	// dx,dyの初期化
	dx = x2-x1;
	if(dx < 0){
		dx = -dx;
		int t;
		t = x1;	x1 = x2;x2 = t;
		t = y1;	y1 = y2;y2 = t;
	}

	dy = y2-y1;
	if(dy < 0){
		dy = -dy;
		sy = -1;
	}
	

	int e,dx2,dy2;

	int mx,my;


	dx2 = dx*2;
	dy2 = dy*2;

	if( dx > dy){
			e = -dx;

			x = x1;y=y1;
			mx = x2; my =y2;


			for( i=0 ; i < (dx/2)+1 ; i++){


				drawPixel(x,y);
				drawPixel(mx,my);

				x ++;
				mx--;
				e+=dy2;
				if( e < =0 ) {
					y += sy;
					my-= sy;
					e -= dx2;

				}


			}

	}else{
			e = -dy;
			x = x1;y=y1;
			mx = x2;my=y2;
			for( i=0 ; i < (dy/2)+1 ; i++){

				drawPixel(x,y);
				drawPixel(mx,my);

				
				buf[y] = x;
				buf[my] = mx;
				
				y += sy;
				my -= sy;
				e += dx2;
				if( e < =0 ){
					x += sx;
					mx -= sx;
					e -= dy2;
				}

			}
	}
}

　これは十分な精度のように感じるかもしれないが、場合によって直線を描画する単純な目的でさえお粗末になる可能性を孕んでいることも注意したい。

　たとえば傾きが1/3の直線を描こうとしたとしよう。果たして正確に1/3という数を「有効桁数６桁」で表現することはできるのか？答えはノーである。

　つまり浮動小数点をこのような形で使用するのはベストとは言えないわけだ。

　ブレゼンハム法を使って、直線を描画する関数は、オーソドックスに書くとList3のようになる。

　リストにしてみると複雑なようだが、たいしたことはやっていない。

　このリストは、スキャンコンバージョンに応用することを考えたりしながら作ったので、いくつか無駄な部分があるが、あまり気にしないでほしい。

　dxとdyは線分のx軸、y軸それぞれの差であり、eは誤差を蓄積するための誤差項であり、x,yおよびmx,myは描画すべきピクセルの座標である。

　ここでは、ブレゼンハム法を最大限に利用するために、線分を両端から描いてループ回数を半数にしている(このテクニックは「X68000マシン語プログラミンググラフィックス編」(村田敏幸・著　ソフトバンク刊))。

　より最適化を推し進めるには、ループカウンタをy座標とする、などの細かい作業が考えられるが、基本的にはこんなところであろう。

　両端から線分上のピクセルを用いるやりかたを最大限に活用するには、コンベックス・ポリゴン(凸多角形)しか扱わないという前提を利用する。

　この前提は、一本のスキャンラインと交差する頂点は、必ず２個以下であるという事実を暗示している。

　フレームバッファは通常、左上から右下へ向かってほぼ連続したアドレスを持つ構造になっている。ということは水平線を描くのは得意なハズである(この前提はスキャンコンバージョン法が有効であるためには欠かせない)。ということは、多角形のそれぞれの辺は必ず左側と右側にそれぞれ分けることができるはずである。

　その時、左側の辺上のピクセルと右側の辺のピクセルを格納するバッファを別々に用意しておき、ブレゼンハム法でそのバッファを満たした後、y軸が最小の位置にある頂点から、y軸が最大となる頂点に向かってスキャンラインをおろしていけば、一気に描画できるハズである。

　この方法の利点は、第一に各々の辺のピクセルを算出するのに、直線描画とほぼ全く同じアルゴリズムで最適化できることである。前出の本に掲載されている「65536倍法」と「ダブルステップブレゼンハム法」を使うこともできる。

　そして、この右辺、左辺のピクセルバッファのサイズを細工し、キャッシュに収まるようにすればかなりの高速化が期待できそうだ。
　左右のバッファはそれほど多くの容量は必要としない。たとえば16ビットでxy座標を表すとして、画面解像度640x480をサポートするバッファは、一つの頂点情報２バイト(16ビット)かけることのＹ座標の最大値480かける、左右一つづつなので２、イコール僅か720バイトである。
　それももったいないというならば、バッファを「普通の大きさのポリゴン用」と「巨大なポリゴン用」の二種類用意し、「普通の～」バッファはポリゴンの大きさを256x256までと限定し、それ以外をより大きな(前述のような)巨大なバッファで扱うようにするとすれば、「普通のポリゴン用」バッファのサイズは１バイト(8ビット)かける256かける2であり、これは512バイトだ。そのポリゴンが巨大であるか普通のものであるかは、簡単な論理積とフラグ系ジャンプで判定できる。言うまでもないが、これは十分キャッシュに入る量である。特殊なキャッシュを持つR3000系のCPUのスクラッチパッドにも十分入るハズだ。

　さらに付け加えるならば、いま扱おうとしているのは、画面に描画するためのポリゴンではなく、可視範囲を策定するために使う擬似的なポリゴンである。だから大きさは256x256もあれば十分お釣がくるハズだ。

flOting point

　浮動小数点について、先ほど少し触れた。
　しかし、この論理展開は多くの論文と同じように作為的であり、決して鵜呑みにしてはならない。

　

List 4


void getPosL2(int x1,int y1,int x2,int y2){
	double m,b;

	if(y2 < y1){
		int t;
		t = y1;
		y1 = y2;
		y2 = t;
		t = x1;
		x1 = x2;
		x2 = t;
	}

	double dx = x2-x1;
	double dy = y2-y1;
	if(dy!=0){
		m = ((dx)/(dy));

		b = x1-(m*y1);

		double fx;
		fx = x1;

		for ( int y=y1; y < y2 ; y++){
			fx += m;
			int x=fx;
			Llinebuf[y] = x;
		}
	}else{ // 垂直線
		for ( int y=y1; y < y2 ; y++){
			Llinebuf[y] = x1;
		}
	}
}

　浮動小数点を利用する演算は、たしかに計算コストがかかる。しかしながら、例には必ず例外があるという金言もあるとおり、この話には例外がある。いや、すでに例外というよりも新しいスタンダードと呼んだ方がよいのかもしれないが、最近のIntel製CPU、つまりIntel社のPentiumシリーズ・プロセッサでは、浮動小数点演算の方が高速だというベンチマーク結果が報告されている(その互換CPUである、Cyrix社製プロセッサは逆に整数演算の方が高速であるらしい)。

　一部のユーザーを除けば、圧倒的にIntel製CPUが普及している現在において、演算の整数化による高速化は、もはや過去の話となっているのかもしれない。

　そこで、参考も兼ねて、敢えてブレゼンハム法を用いず浮動小数点の加算のみを使ったプログラムもかいてみた。
　実際にコードを書いてみると、びっくりするほどアルゴリズムが簡単になるのがわかる。基本的には、直線の傾きを単に初期値に足し込み、整数化して格納しているだけだ。
　ただし、注意しなくてはならないのは、垂直な線を書く場合である。この場合、数学的に行って傾きは求められない(傾いていないからだ)。そのときだけ別に場合分け処理をするようにしている。

　まだベンチマークはしていないが、動かした感じの感想では、描画点が減っていることもあるだろうが、明らかに前回のプログラムよりもググッとスピードアップした感じだ。
　浮動小数点についてのものも含めて、なるべく近日中にベンチマークプログラムとその測定結果を掲載したいと考えている。

　そんなわけで今日のところはさようなら。