Programing Note

過去ログ（log1.htm）←過去ログIndex←Programming note←Index

どのようなレイアウトにしようか試行錯誤中。暫定的に日記と同じ形式にします。

1999/06/12	極楽STL
1999/05/11	直線と球の交点
1999/05/06	DrawPrimitiveの連続呼び出し
1999/04/19	高速移動時の当り判定
1999/04/11	当り判定アルゴリズム完成
1999/03/15	３Dの当り判定・その後
1999/03/10	３Dの当り判定

極楽STL

1999/06/12

プログラミングの途中に、任意に拡張ができる配列が欲しくなったりしますよね。その為にnewとdeleteがあるんじゃないかという人もいるかも知れませんが、実装するのは思ったより面倒なものです。しかも、できたプログラムには必ずといって良いほどバグが潜んでいて、バグとりに結構時間を食われたりします。

という訳で、誰かこんなものを作ってくれないかなと思うのが人情というものでしょう。実は、C++ではこれが標準で用意されていたりします。C++を使う人ならば、名前ぐらいは知っているでしょう。そうです、STL(Standerd Template Library)です。

STLといっても色々あるのですが、今回は”後方に拡張可能な配列”であるvectorを使って、STLを少し触ってみましょう。
＊コンパイラはVC++6.0Proを想定しています

まず、vectorを定義しないといけません。#includeでvectorの定義されているヘッダファイルをインクルードします。

#pragma warning (disable : 4786)
#include <vector>
using namespace std;

あれ、ヘッダファイルをインクルードするだけなのに、#include以外の文がありますね。勿論、ちゃんと意味があります。

まず最初に目に付くのは#pragmaディレクティブです。これは何をしているのかというと、4786番の警告は出さなくていいよ、とコンパイラに知らせているのです。これを書き忘れると、デバッグの時鬼のように警告がでてきます。しかも、この警告は無視しても何ら支障はありません。それなら、警告しないようにするのが賢い方法ですね。

次はインクルードしているのがヘッダファイルなのに”vector.h”ではない点ですね。これは、C++の標準化委員会が決めたことです。おとなしく従いましょう(^_^;)。

最後にusing namespace stdなのですが、これもC++標準化委員会で決まったことで、C++の標準ライブラリはすべてネームスペース”std”上に存在しなければならないそうです。ネームスペースについては説明しません。C++の参考書に載っていることだろうと思いますので、そちらを参照してください。

それと、vectorの宣言の方法なのですが、例えばint型のvectorを使いたければvector<int>とします。long型ならばvector<long>です。この表記方法、見たことはありませんか？そうです、C++のtemplateです。STLはtemplateを使うことでどんな型でも扱えるようにしたのです。全く、すばらしいですね。

さて、そろそろSTLを触ってみましょう。以下のプログラムをvectorで置き換えてみます。

get_data関数がfalseを返すまでarrayに挿入するプログラムです。

int size=0;//配列の要素数
int max_size=10;//配列の大きさ
int *array=new int[max_size];
int data;

//get_data関数がfalseを返すまでarrayに挿入
//get_data関数のプロトタイプは"bool get_data(int&)"です。
while(get_data(data)){
if(size>=max_size){
//配列がいっぱいになったので配列を拡張
max_size++;
int tmp=new int[max_size];
for(int n=0;n<size;n++)
tmp[n]=array[n];
delete [] array;
array=tmp;
}
array[size++]=data;
}

次に、お待ちかねのvectorを使ってみましょう。

vector<int> array;
int data;

while(get_data(data)){
array.push_back(data);
}

終わりです。上のようなコードを今まで書いていた方は俺の今までの努力はいったいなんだったんだ！と叫びたくなりそうですね(^_^;)。

更に、vectorにはすばらしい機能が目白押しです。

まず、配列と同じように"int n=array[5];"のようなアクセスが可能です。そして、似たような効果をもつメソッドとしてat()というメソッドがあります。これは、配列の場合、指定した要素が存在しない時やばいことが起きますが、at()を使うとat()内部で範囲チェックを行ってくれて、範囲外の場合はout_of_range例外を投げてくれます。

ほかには、配列を拡張、縮小することもできます。"array.resize(10);"でOKです。この例では、arrayの要素数を１０にします。

ところで、途中の位置に要素を挿入したい時にはどうすればよいのでしょうか。erase(int n)でｎ個目の要素を削除できてもよさそうなのですが、実はダメなのです。これがSTLの一見面倒そうだけど、実は凄いところです。これについては後ほど。次があるのかどうかは知りませんが(^_^;)

この記事でSTLに興味を持たれた方（いるのかな(^_^;)は、是非本格的に勉強して下さい。恐らくプログラミングがもっと楽になるでしょう。お勧めはεπιδγημη氏著のSTLプログラミングです。STLの本質を理解するだけでなく、リファレンスとしても活用できます。

直線と球の交点

1999/05/11

掲示板にあんなこと（球の軌跡で当り判定ができる）と書いていましたが、見事に挫折してしまいました。詳しくは書きませんが、直線と直線の当り判定の部分です。

という訳で、今回は直線と球の交点です。当り判定は、交点を導き出せないと全く意味がないですからね。（解説しているサイトを見たことないので、ひょっとして一番のりかも(^○^)！？）今回もへぼい画像付きです。勘のいい人は図を見ただけでわかるかもしれません。

image.gif (1886 バイト) 前よりましか！？

判定する球の中心をO、半径をrとします。ベクトルVは直線の方向の単位ベクトルで、Pが直線の開始点です。Hは求める点、つまり球と直線の交点です。Aは説明の都合上書いています。

まず、APの長さを求めます。APの長さとはなんとなく難しそうですが、なんてことはないVとOPの内積で求められます。

次に、OAの長さを求めます。APの長さがすでに求まっているので、三平方の定理で求めることができます。

今度は、AHの長さを求めてみましょう。OHの長さは球の半径になる（Hは球上の点なので当たり前）ので、今求めたOAの長さと合わせてまたまた三平方の定理で求まります。

最後に、HPの長さ（AHの長さーAPの長さ）とベクトルVにかけたものを、Pに足すとHの座標になります。

今回の式は、自力で導き出しました。導き出した時僕って天才？とか思ったりしましたが、よく考えたらそれほど難しい問題ではないですね(^_^;)。

DrawPrimitiveの連続呼び出し

1999/05/06

突然ですが、今、ゲームを作っています。対戦型シューティングゲームを予定していて、折角C++を使っているのだからと、Cマガで読んだデザインパターンを使っています。最初はさくさく進んでいたのですが、思った通りというか、壁にぶつかってしまいました。描画をどうするかです。

最初はオブジェクトごとにRender()メソッドを持っていて、そこに描画コードを書けばいいやと思っていたのですが、DrawPrimitiveの呼び出しは時間がかかるので、できるだけまとめて描画したほうが良いというIM使いの常識を突然思い出して、今悩んでいます。

★。、::。.::・'゜☆。．：：・’゜★。、：：。．：：・’゜★。、::。.::・'゜☆。．：：・’゜★。、：：。．：：・’゜

実際はそんなに時間はかからないのではないかという淡い期待を胸に、DrawPrimitiveを無駄に呼び出してみる実験をしてみました。

実験に使用したプログラムは、うねうねバナナのIMサンプル、”Bend”です。App_Renderの部分をこんなコードに置き換えてみました。

D3DVERTEX *v=g_pvRenderVertices;

for(DWORD d=2;d<g_dwNumVertices;++d){
pd3dDevice->DrawPrimitive( D3DPT_TRIANGLESTRIP, D3DFVF_VERTEX, v, 3, D3DDP_WAIT );
v+=1;
}

考えればごく当然の結果なのですが、元のソースコードの3倍もの時間がかかりました。D3DPT_TRIANGLESTRIPをD3DPT_TRIANGLELISTに変更すると元コードの2倍くらいになりますが、それでも遅すぎる！はっきりいって使い物になりません。

折角VisualC++を立ち上げたので、他のコードも試してみました。

恐らく誰も使っていないであろうBegin()をつかってみます。

D3DVERTEX *v=g_pvRenderVertices;

pd3dDevice->Begin(D3DPT_TRIANGLESTRIP,D3DFVF_VERTEX,D3DDP_WAIT);
for(DWORD d=0;d<g_dwNumVertices;++d){
pd3dDevice->Vertex((LPVOID)(v+d));
}
pd3dDevice->End(0);

これは元コードの大体１．３倍の時間がかかりました。これなら許容範囲かも！？

こんどはまたまたマイナーなBeginIndexed()を。

pd3dDevice->BeginIndexed(D3DPT_TRIANGLESTRIP,D3DFVF_VERTEX,
g_pvRenderVertices,g_dwNumVertices,D3DDP_WAIT);
for(DWORD d=0;d<g_dwNumVertices;++d){
pd3dDevice->Index(d);
}
pd3dDevice->End(0);

結果は元コードの１．１倍から１．２倍という、なかなか優秀な成績を残しました。

最後に、一番使用頻度の高いと僕が勝手に思いこんでいるDrawIndexedPrimitive()を。

WORD* id=new WORD[g_dwNumVertices];
for(DWORD d=0;d<g_dwNumVertices;d++)id[d]=d;
pd3dDevice->DrawIndexedPrimitive( D3DPT_TRIANGLESTRIP, D3DFVF_VERTEX,
g_pvRenderVertices, g_dwNumVertices, id, g_dwNumVertices, D3DDP_WAIT );
delete [] id;

驚いたことに、元コードのかかった時間とほぼ同じでした。WORD配列を使うペナルティはあまりないのですね。

面白いことがわかりましたが、結局問題は解決せず。トホホ・・・

高速移動時の当り判定

1999/04/19

3/15日の日記の最後に、”物体が高速で移動していたら貫通する可能性がある”と書きましたが、ありました、解決策が。わかりにくいですが、少し付き合ってください。

物体が高速に移動すると貫通してしまう理由は、物体が一度に当り判定球の半径以上動いてしまうからです。つまり、一度に当り判定球の半径以上動かなければ良いのです。これを実現するにはどうすれば良いかとゆうと、移動前の座標から移動後の座標に直線を引っ張って、その直線上に当り判定球の半径づつ区切りをいれて、この区切りの上に新たな球を配置すればよいのです。さすがに図がないとわかりにくいので、頑張って作ってみました(^_^;)。

test.gif (7326 バイト) なんだこの図は(汗)。３Dで描けという意見は却下(^_^;)

この後、移動前の物体の位置に近い球から普通に当り判定を行います。そして、もし当り判定の処理の結果移動したらその後ろの球（つまり、まだ当り判定を行っていない球）も一緒に移動します。これを最後まで繰り返せば当り判定は終了です。一番最後の球の位置が当り判定終了後の移動後の座標になります。

しかし、この方法は少し問題があります。移動前の座標と移動後の座標があまりにも離れていた場合には、計算量が膨大になってしまいます。そのあたりをよく考えてから使わないといけません。

とても面倒ですね(^_^;)。やはり一番簡単なのは一度に移動する距離を当り判定球の半径以上にしないことでしょう。

当り判定アルゴリズム完成

1999/04/11

一週間もの時間をかけて、ようやく当り判定を行う関数のみ（たった300行）を完成させました。春休み中なのに、これだけ・・・。いやあ、コーディング速度遅すぎですね(-_-;)。

この一週間でわかったことは、優れたプログラマはデバッグがうまい、ということでしょうか。もし僕のデバッグ能力が高かったら、このていどなら1時間程度ですんでいたのに・・・

殆ど方針も決まっているので楽勝だろうと思っていたのですが、意外な落とし穴にはまってしまいました。floatの精度の問題です。誤差といっても小数点以下の誤差なんて問題にならないだろう、と思っていたのですが、まさか0.0001が-0.0001になるとは思ってもいませんでした。三角形の内部かどうかの判定に符号によって条件分岐していたので、0.0002の誤差でも致命的です。このバグを取り除くのにこんな膨大な時間を費やした訳です。わかってみるとアホくさい話です(-_-;)。

//テストプログラム公開はまだまだ先の話・・・

99/04/13訂正：大幅に手抜きをしてテストプログラムを完成させました。手を抜こうと思ったらとことん抜けるものですね(^^ゞ。

３Dの当り判定・その後

1999/03/15

Webを巡っていたら、ありました、当り判定(-_-;)。今までの苦労は一体何？って感じですね。はっはっは（泣）

まあ、過去のことは忘れたことにしておきましょう。前予告した通り球体で判定して、三角形は動きません。

球体の中心点と三角形を含む平面との距離を求める。これで距離が球体の半径以下なら第一条件クリア。

三角形を含む平面の方程式は、当然事前に計算して置きます。あとは中心点から平面へ垂線を引っ張って、その足の座標と中心点との距離を出せば良いわけです。おっと、そこの人、垂線の足の座標は捨てたら駄目ですよ。後で使いますから。

次に、球体の中心点から三角形を含む平面に下ろした垂線の足が、三角形の内部にあるかどうか調べる。　内部にあれば当っている

この判定をかなりの間悩みました。僕は三角形の頂点と垂線の足をXZ平面（あるいはXY、YZ平面）に投影して、２D的に求めようとしていたのですが、外積を使って判定する方法があるようですね。自分でもまだ解釈していない(^_^;;;;ので、書くのはまだお預けにしておきます。

内部に無い場合、次は三角形の一辺を含む直線と球体の中心点との距離を求める。（当然３回行う）この距離が球体の半径以下ならば、当っている可能性あり。次の処理へ

まだ可能性だけです。中心点から直線へ垂線を引っ張って、その足と中心点の距離を求めるのですが、ここでも計算結果を捨ててはいけません。

その辺を作っている頂点から直方体を作り、前の処理で求めた垂線の足がこの直方体内部にあるかどうか判定。もし内部にあった場合、当っている。

なんか長方形を作るって辺りが訳わからないですが、ようするに頂点座標の原点に近い方をx1,y1,z1、遠い方をx2,y2,z2、垂線の足の座標をX,Y,Zと置くと、
x1<=X<=x2 , y1<=Y<=y2 , z1<=Z<=z2になっているかどうかということです。これを満たせば垂線の足は三角形の辺上にあるということになります。

これでようやく衝突判定は終わったので、今度は事後処理をしなければなりません（めり込んだままじゃカッコ悪いですからね）。移動をキャンセルして以前の座標に戻す方法もありますが、折角垂線の足の座標が手もとにあるので、これを使って壁に沿って移動させましょう。どうやってするのかというと、垂線の座標から球体の中心点の方へ向かって、距離が球体の半径分になる様にずらせばよいのです。って、説明読んだらますます訳がわかりませんね（自爆）。やっぱり画像は必要だなあ（特に、僕みたいに文章力の無い人間は）

冒頭にもあった通り、これはWebの情報を自分なりに解釈して書いています。（元ネタBio_100%さんの 3D Fellows BBS）。よって、独りよがりになっていたり、うそを書いているかもしれません（！）ので、鵜呑みにしない様に(^^ゞ。で、書いていて気付いたのですが、物体が高速で移動していたら貫通する可能性がありますね。どうしましょう(^_^;)。当っているだけなら判定方法はすぐ思いつきますが、壁に沿って移動となると・・・。うーん、思いつきません。これはゲームを作るときに貫通するような移動はさせない様にするしかないですね。

３Dの当り判定

1999/03/10

今、３D空間を歩き回るゲームを作成してみようかなと思っているのですが、当り判定で悩んでいます。三角形と移動するオブジェクトの当り判定です。２Dだとたいして悩む必要の無い当り判定ですが、３Dとなると・・・(泣）。今思いついているのはこのような方法です。（かなり大雑把＆わかりにくいですが、どうせ没案ですから、ご容赦を）

前提条件

三角形は移動しない。
オブジェクトの当り判定領域は、直方体とする

移動前の直方体と移動後の直方体の対応する頂点を結んで、直線を作る。（直方体なので八本できる）
　
その直線と、三角形との交点を求める。
　
その交点が、三角形の内部の点なのかどうかを求める。
　
もし内部の点ならば、当っている

とまあ、こんな感じなのですが、この方法、問題大有りです。見ての通り、直線と三角形の交点を無駄に８回も求めないと駄目なので、とてつもなく重いのです。特に、当り判定は一回更新するごとに何回も行わなければならないので、リアルタイムで動かすとなると致命的です。まだ問題はあるのですが、この案は没にしている案なのでもうこれ以上書きません。次は、オブジェクトの当り判定領域を球でやってみようと思います。球体を表すには、中心の座標と半径だけでよいので、少なくても直方体よりは簡単に出来るはずです。多分(-_-;)