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
[go: Go Back, main page]



11/22 嗚呼、憧れの大地よ

 いままでプログラムに入る前の準備として進めてきた国後計画だったのだが、ちと飽きたので、今日は趣向を換えてちょっとした描画アルゴリズムについて考えてみる。



Land scape

     なんだってとにかくだね、アレだよ君。
     3Dゲームといったら地表の表現に尽きるダロ?そうじゃないかね?明智小五郎君。

     古来から、地表は村一番の力持ちたちがその腕を競う格好の場所じゃった。

     地表、メリケンの使う言葉で「ランドスケープ」と言うものは、かなり古くから研究対象になっていたもののひとつである。

     Windows95に於いては、その登場と同時に発売された専用ゲーム「Fury3(フューリー・キューブ)」から登場しているので、知らない人はいないというほどではないだろうか。


     他にも、「アジャイルウォーリアー」や「クレイジー・イワン」などの海外作品にはかなり頻繁に登場し、中でも「アジャイル・ウォーリアー」では爆弾を投下するとその衝撃で地面が窪むなど、かなり効果的に用いられたのが、「高さ(ハイト)フィールド」と呼ばれるポピュラーな手法である。

     「ハイトフィールド」をDirect3Dを使って表現する基本的な方法は、拙著のDirect3D Programming Guidebookに詳しく説明しているので、興味があったらそちらを参照してほしい。

     さて、簡単に紹介すると、この「ハイトフィールド」というのは、その名の通り、高さのフィールドである。これは、碁盤の目のようなものを想像していただくとわかりやすいのだが、碁盤の目にあたる部分にそれぞれ別々の高さを持たせることによって起伏を表現する手法だ。

     もうイヤっつぅほどポピュラーなこのメソッドを、国後に搭載するのも、たぶん最初から皆は分かっていただろうし、いまさらこれをどうするということもない。

     国後は架空の地上戦を再現するゲームなのだし、地上をリアルに表現する方法はこれかボクセル、または水平な地面にボンとなんかでかいものを置くくらいしか方法はない。
     しかし、Direct3Dのハードウェアアクセラレーションが一般化している現在、わざわざボクセルなんつー面妖な代物は当然、使うまでもない。


     


    Optimize for Landscape

     さて、このPrejudiceでこいつを取り上げるからには、やはり最適化はどうしようかという話になるのは、いわば必然である。

     今回、焦点を当てるのはできるだけ素早く「見える範囲」にある頂点だけを割り出すというアルゴリズムである。


     右の図はハイトフィールドの頂点を図示したものだ。青い丸が視点であり、黄色い矢印はそれぞれ視野座標系のベクトルを地面に投影したものであると考えていただきたい(厳密にはまるで違うが)この図の場合、緑色の点が見える頂点、赤色の点が見えない頂点を示している。

     この図で「見えない頂点」になっているものは、このあとのポリゴンやらなんやらで使う、「座標変換」やレンダリングの際には「フレームの描画に無関係な頂点」として処理される。


     この頂点達を求める方法だが、すぐに思い付くのは、黄色い二本のベクトルからなる三角形を想定し、典型的なスキャンコンバージョン法(ポリゴンの塗りつぶしアルゴリズムのひとつだ)を用いて算出する方法である。

     この方法の利点はまず無駄がないこと。なにしろハナから三角形領域しか相手にしないから、無駄も糞もない。
     ただし、なんとなくではあるが、ブレゼンハム法を用いて各々の辺の座標点をはじき出すのは如何なものか。頂点数が多いときは莫大な効果がありそうだが、少ないときは却って遅くなるかもしれない。なにより、すぐにプログラムを組むのは面倒である。

     プログラムを組むことの簡便さからいけば、二つのベクトルを直線とみなして、直線の方程式から頂点をひとつひとつ評価する方法がもっとも簡単と言えるだろう。
     これは、逆に頂点数が少ないほど効果的だと思われる。

     スキャンコンバージョンは処理が複雑すぎて最適化をするのは時間を食いそうなので、とりあえず後者の方法を使ったルーチンをかいてみた。




      
      BOOL groundClip(){
      
      	static struct {
      		double x,y;
      	}vX,vY; // 視野ベクトル
      
      	static double r = 0.0; // 見ている方向(テスト用)
      
      	HDC hdc; D3Z.lpBackBuffer->GetDC(&hdc;); // デバイスコンテキスト取得
      
      	// ブラシなどを初期化
      
      	HBRUSH hRedBrush,hGreenBrush,oldBrush,hBlueBrush;
      	hRedBrush = CreateSolidBrush(RGB(255,80,80));
      	hGreenBrush = CreateSolidBrush(RGB(80,255,80));
      	hBlueBrush = CreateSolidBrush(RGB(80,80,255));
      	oldBrush = SelectObject(hdc,hRedBrush);
      
      
      	// キーボード読み取り
      	char key[256];
      
      	GetKeyboardState((unsigned char*)key);
      
      	if( key[VK_LEFT]  &0xf0) r -= 10.0;
      	if( key[VK_RIGHT] &0xf0) r += 10.0;
      	if( key[VK_ESCAPE] &0xf0) 	DestroyWindow(hwnd);
      
      
      	// テスト用に視野ベクトルを算出
      	double rad = r*3.14159/180;
      
      	vX.x = cos(rad);
      	vX.y = sin(rad);
      
      	vY.x = -sin(rad);
      	vY.y = cos(rad);
      
      	static double ax = 5.0,ay = 5.0;
      
      	// 視点の移動
      	if( key[VK_UP]&0xf0  ) {
      
      		ax += (vX.x + vY.x)/2;
      		ay += (vX.y + vY.y)/2;
      
      	}
      	if( key[VK_DOWN]&0xf0  ) {
      
      		ax -= (vX.x + vY.x)/2;
      		ay -= (vX.y + vY.y)/2;
      
      	}
      
      	mx = ax;
      	my = ay;
      
      	int div;
      	if( vX.x > 0 ){
      		if(vX.y > 0){
      			if(vY.y>0){
      				div = 0;
      			}else{
      				div = 1;
      			}
      		}else{
      			if(vY.y>0){
      				div = 1;
      			}else{
      				div = 2;
      			}
      		}
      	}else{
      		if(vX.y > 0){
      			if(vY.y > 0){
      				div = 0;
      			}else{
      				div = 3;
      			}
      		}else{
      			if(vY.y > 0){
      				div = 3;
      			}else{
      				div = 2;
      			}
      		}
      	}
      	
      	int x1,y1,x2,y2;
      	switch(div){
      		case 0:
      			x1 = mx - VIEWWIDTH/2;
      			y1 = my ;//- VIEWHEIGHT/2;
      			x2 = mx + VIEWWIDTH/2;
      			y2 = my + VIEWHEIGHT/2;
      			break;
      		case 1:
      			x1 = mx;
      			y1 = my - VIEWHEIGHT/2;
      			x2 = mx + VIEWWIDTH/2;
      			y2 = my + VIEWHEIGHT/2 ;
      			break;
      		case 2:
      			x1 = mx - VIEWWIDTH/2;
      			y1 = my - VIEWHEIGHT/2;
      			x2 = mx + VIEWWIDTH/2;
      			y2 = my +1;
      			break;
      		case 3:
      			x1 = mx - VIEWWIDTH/2;
      			y1 = my - VIEWHEIGHT/2;
      			x2 = mx +1;
      			y2 = my + VIEWHEIGHT/2;
      			break;
      	}
      
      
      	int i,j;
      	for(j= y1 ;j < y2;j++)
      		for(i =x1;i < x2;i++){
      		
      		// 点を表示
      		
      		RECT rect;
      
      		int x = i*10;
      		int y = j*10;
      
      		rect .left  = x;
      		rect .top   = y;
      		rect .right = x+5;
      		rect .bottom= y+5;
      
      
      
      		FillRect(hdc,▭,hRedBrush);
      
      		if( (i-mx)*vX.y < (j-my)*vX.x )
      		if( (i-mx)*vY.y > (j-my)*vY.x ){
      			// 見える範囲
      			FillRect(hdc,▭,hGreenBrush);
      		}
      
      		if( ( i == mx ) && (j==my)){
      			// 視点の位置
      
      			FillRect(hdc,▭,hBlueBrush);
      
      			// 視野ベクトル
      			HPEN hPen = CreatePen(PS_SOLID, 1, RGB(255,255,255)),oldPen;
      
      			oldPen = SelectObject(hdc,hPen);
      
      			POINT currentPos;
      			MoveToEx(hdc, x,y ,¤tPos;);
      			LineTo(hdc, x + (vX.x*10) , y + (vX.y*10) );
      
      			HPEN hPen2 = CreatePen(PS_SOLID, 1, RGB(255,255,000));
      
      			SelectObject(hdc,hPen2);
      			
      			MoveToEx(hdc, x,y ,¤tPos;);
      			LineTo(hdc, x + (vY.x*10) , y + (vY.y*10) );
      
      			SelectObject(hdc,oldPen);
      			DeleteObject(hPen2);
      			DeleteObject(hPen);
      		}
      
      	
      	}
      
      	SelectObject(hdc,oldBrush);
      	DeleteObject(hRedBrush);
      	DeleteObject(hBlueBrush);
      	DeleteObject(hGreenBrush);
      
      
      	D3Z.lpBackBuffer->ReleaseDC(hdc);
      
      	return TRUE;
      }
      
      

     でましたヘンな癖。
     もはや、なにもかもが面倒なので、なんとわざわざDirect3Dを使っているのだが、描画はGDIというわけのわからないことになっている。うむ、これこそ環境にやさしいハイブリッド・プログラム!馬鹿ですな。

     まぁ懸命な読者諸氏には、内容についてはわざわざ説明するほどのことはないと思ふ。


     が、まぁ一応補足説明をしておくと、このプログラムでは比較する頂点を少なくするために、「象限」による判定をあらかじめ行っている。

     要するに、(1)視野はかならず直交座標系である。(2)直交座標系は回転したとき、それを構成する二本のベクトルは必ず隣り合う象限に属する。という当たり前の定理を利用しているに過ぎない。

     象限で判定しているのはちょうどdivのあたりだ。

     さて、一通りプログラムを作ってみたわけだが、スキャン・コンバージョン法での実装をしてみる前に少し考えてみたのだが、こういうやり方はどうだろうか。



     もはやこのコーナーでは御馴染みのリスト構造を用いた最適化のアイディアである。
     先ほどの象限による最適化とあわせて、ゲーム中、方向転換はそれほど頻繁にはおこらないという点に着目する。また、起こるにしても、1フレーム差で180度以上旋回するようなことは、いくらコマ落としでも、本来やるべきではない(そんなことをしたら、プレイヤーは酔ってしまう)。

     そこで、頂点のリストというものを作る。最初の一回目は、やはり前述のなんらかの方法で見える頂点と見えない頂点に分けなくてはいけないが、そのとき、同じ象限にありながら、見えた頂点と見えない頂点のリストを二つづつ(直交座標系の場合はかならず二つの象限をまたぐため)作る。


     もっとかみ砕いて言えば、それぞれの象限にとって、視野座標系ベクトルは単に象限を二分するだけの存在でしかない。その、分けた情報を捨てずにとっておくのだ。

     次に、新しいフレーム(画面)を描画するとき、前回分けた頂点情報のうち、視野の回転した方向によって、新しい頂点がどのリストに入っているかは既に自明である。そのため、そのリストの頂点だけを探せばよい。そして、新しい頂点リストをつくるのも簡単で、単に見つけた頂点情報をリンクしなおせば良いのだ(自分で言うのもなんだが、このへんは凄くエレガントだ)。

     依然として、スキャンコンバージョンより無駄が多いのは否めないが、それだけプログラムコードの無駄は少ない。
     ひょっとすると、スキャンコンバージョン法を素直に使うよりも、いい結果が出るかもしれない。
     というのは、結局ゲームなんてのは前フレームとの差分の方が圧倒的なんだと思うわけで、あーこれでもいいかーと思うとスキャンコンバージョンで実装したくなくなるなぁ。
     リスト構造は、これはこれで面倒だが、スキャンコンバージョンより楽だしね。

     といわけでちょっと浮気なPrejudiceでした。