ポリゴンに対する内外

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
Ute

ポリゴンに対する内外

#1

投稿記事 by Ute » 8年前

Dxlibでmqoファイルを読み込みポリゴンとの接地判定を行うプログラムをバトーキン島の作者様のコード(http://www.nicovideo.jp/watch/sm8387469)で学習中です。
しかしこの方のプログラムのSetGroundPolygon関数のアルゴリズムが上手く理解できません。
ポリゴン内部に次フレームでの移動点が存在するかどうかを判定していること、何やら外積を使っていそうなことぐらいは理解できるのですが、atan2をどう用いているのか、回転角の総和と6.2fを比べる行為に何の意味があるのかわかりません。
お手数ですが是非ご回答下さい。

あわせて、3Dプログラミングにアルゴリズム等を紹介してくれる良いサイトなど御座いましたら是非教えて下さい。

コード:




// 接地ポリゴン情報をセット
int SetGroundPolygon( void )
{
	int i,ResultFlag;
	float TotalRad, ResultY;
	VECTOR Position[3];
	HITRESULT_LINE HitResult;

	ResultY = Pc.NextPosition.y - PC_MAX_VERTICAL;
	ResultFlag = 0;
	for( i = 0 ; i < MapPoly.PolygonNum ; i++ ){
		if( MapPoly.Polygons[ i ].MinPosition.x <= Pc.NextPosition.x && MapPoly.Polygons[ i ].MinPosition.z <= Pc.NextPosition.z &&
			MapPoly.Polygons[ i ].MaxPosition.x >= Pc.NextPosition.x && MapPoly.Polygons[ i ].MaxPosition.z >= Pc.NextPosition.z){

			Position[0] = MapPoly.Vertexs[ MapPoly.Polygons[ i ].VIndex[ 0 ] ].Position ;
			Position[1] = MapPoly.Vertexs[ MapPoly.Polygons[ i ].VIndex[ 1 ] ].Position ;
			Position[2] = MapPoly.Vertexs[ MapPoly.Polygons[ i ].VIndex[ 2 ] ].Position ;

			// ポリゴンに座標が含まれているか
			TotalRad = atan2(
				(Position[0].x - Pc.NextPosition.x) * (Position[1].z - Pc.NextPosition.z) - (Position[0].z - Pc.NextPosition.z) * (Position[1].x - Pc.NextPosition.x),
				(Position[0].x - Pc.NextPosition.x) * (Position[1].x - Pc.NextPosition.x) + (Position[0].z - Pc.NextPosition.z) * (Position[1].z - Pc.NextPosition.z)
				) ;
			TotalRad += atan2(
				(Position[1].x - Pc.NextPosition.x) * (Position[2].z - Pc.NextPosition.z) - (Position[1].z - Pc.NextPosition.z) * (Position[2].x - Pc.NextPosition.x),
				(Position[1].x - Pc.NextPosition.x) * (Position[2].x - Pc.NextPosition.x) + (Position[1].z - Pc.NextPosition.z) * (Position[2].z - Pc.NextPosition.z)
				) ;
			TotalRad += atan2(
				(Position[2].x - Pc.NextPosition.x) * (Position[0].z - Pc.NextPosition.z) - (Position[2].z - Pc.NextPosition.z) * (Position[0].x - Pc.NextPosition.x),
				(Position[2].x - Pc.NextPosition.x) * (Position[0].x - Pc.NextPosition.x) + (Position[2].z - Pc.NextPosition.z) * (Position[0].z - Pc.NextPosition.z)
				) ;
			if( abs(TotalRad) >= 6.2f ){

				HitResult = HitCheck_Line_Triangle(
					VGet( Pc.NextPosition.x, (Pc.NextPosition.y + PC_PASSAGE_BUMP), Pc.NextPosition.z ),
					VGet( Pc.NextPosition.x, (Pc.NextPosition.y - PC_MAX_VERTICAL), Pc.NextPosition.z ),
					Position[0], Position[1], Position[2]
					) ;
				if( (HitResult.Position.y <= Pc.Position.y + PC_PASSAGE_BUMP) && (HitResult.Position.y > ResultY) )
				{
					memcpy(Pc.GroundPolygon, Position, sizeof(Pc.GroundPolygon));
					memcpy(Pc.GroundIndex  , MapPoly.Polygons[ i ].VIndex, sizeof(Pc.GroundIndex));
					Pc.GroundPoint = HitResult;
					ResultY = HitResult.Position.y;
					ResultFlag = 1;
				}
			}
		}
	}

	return ResultFlag;
}


Ute

Re: ポリゴンに対する内外

#2

投稿記事 by Ute » 8年前

また、このプログラムだと次のポリゴンが三角形であることが前提になっている(三頂点で比較しているので)と思うんですが、このプログラムのmqoデータには三角形以外にも勿論四角形ポリゴンが含まれていて、なぜこのプログラムで判定できるかがわからないのです…。

djann
記事: 27
登録日時: 11年前

Re: ポリゴンに対する内外

#3

投稿記事 by djann » 8年前

コード:

// まず軸に沿ったXZ平面で中に入っているかを簡易的にチェック(軽量化処理)
if (
	(MapPoly.Polygons[ i ].MinPosition.x <= Pc.NextPosition.x 
&&  MapPoly.Polygons[ i ].MaxPosition.x >= Pc.NextPosition.x)
&&  (MapPoly.Polygons[ i ].MinPosition.z <= Pc.NextPosition.z
&&  MapPoly.Polygons[ i ].MaxPosition.z >= Pc.NextPosition.z)
){

// 1つの面を構成する各頂点の座標取り出し - 書きやすくするだけ.
Position[ 0 ] = MapPoly.Vertexs[ MapPoly.Polygons[ i ].VIndex[ 0 ] ].Position;
Position[ 1 ] = MapPoly.Vertexs[ MapPoly.Polygons[ i ].VIndex[ 1 ] ].Position;
Position[ 2 ] = MapPoly.Vertexs[ MapPoly.Polygons[ i ].VIndex[ 2 ] ].Position;

// ポリゴンに座標が含まれているか
// 単純に
// Pc.NextPositionからPosition[ 0 ]へのベクトル1
// Pc.NextPositionからPosition[ 1 ]へのベクトル2
// 以上の二つの二次元ベクトル間の角度を求めている。
TotalRad = atan2(
	(Position[ 0 ].x - Pc.NextPosition.x) * (Position[ 1 ].z - Pc.NextPosition.z) - (Position[ 0 ].z - Pc.NextPosition.z) * (Position[ 1 ].x - Pc.NextPosition.x),
	(Position[ 0 ].x - Pc.NextPosition.x) * (Position[ 1 ].x - Pc.NextPosition.x) + (Position[ 0 ].z - Pc.NextPosition.z) * (Position[ 1 ].z - Pc.NextPosition.z)
);
// 扱う頂点が違うだけで同じ。それを足している.
TotalRad += atan2(
	(Position[ 1 ].x - Pc.NextPosition.x) * (Position[ 2 ].z - Pc.NextPosition.z) - (Position[ 1 ].z - Pc.NextPosition.z) * (Position[ 2 ].x - Pc.NextPosition.x),
	(Position[ 1 ].x - Pc.NextPosition.x) * (Position[ 2 ].x - Pc.NextPosition.x) + (Position[ 1 ].z - Pc.NextPosition.z) * (Position[ 2 ].z - Pc.NextPosition.z)
);
// 同様に扱う頂点が違うだけでry.
TotalRad += atan2(
	(Position[ 2 ].x - Pc.NextPosition.x) * (Position[ 0 ].z - Pc.NextPosition.z) - (Position[ 2 ].z - Pc.NextPosition.z) * (Position[ 0 ].x - Pc.NextPosition.x),
	(Position[ 2 ].x - Pc.NextPosition.x) * (Position[ 0 ].x - Pc.NextPosition.x) + (Position[ 2 ].z - Pc.NextPosition.z) * (Position[ 0 ].z - Pc.NextPosition.z)
);


// Pc.NextPositionが3頂点から成る面の中にあるのであれば
// atan2()を3回行っているところで求められた角度は「大体360度くらい」になるでしょう
// 弧度法では3.14159265...が180度に値するし、その倍である数値近く以上なら入ってる可能性が高い
// または明確に入っている!を意図したのかもしれない
if ( abs( TotalRad ) >= 6.2f ){
	// 素晴らしいチェックを行ってくれるであろう関数の呼び出しだと思われる。
	// 先ほどまでのチェックはXZ平面だったので、今度はYの検出なのかなー.
	HitResult = HitCheck_Line_Triangle(
		VGet( Pc.NextPosition.x, (Pc.NextPosition.y + PC_PASSAGE_BUMP), Pc.NextPosition.z ),
		VGet( Pc.NextPosition.x, (Pc.NextPosition.y - PC_MAX_VERTICAL), Pc.NextPosition.z ),
		Position[ 0 ], Position[ 1 ], Position[ 2 ]
	);
	// 多分当たったと思われる結果になる条件式なのだろう。
	if ( (HitResult.Position.y <= Pc.Position.y + PC_PASSAGE_BUMP) && (HitResult.Position.y > ResultY) )
	{
		// そういえばこれはクラスメンバなんですかね?とりあえず当たったポリゴン(1面のことかな?)やら
		// やら当たった場所やらを格納してそれが出力結果になるのですね。
		memcpy( Pc.GroundPolygon, Position, sizeof( Pc.GroundPolygon ) );
		memcpy( Pc.GroundIndex, MapPoly.Polygons[ i ].VIndex, sizeof( Pc.GroundIndex ) );
		Pc.GroundPoint = HitResult;
		ResultY = HitResult.Position.y;
		ResultFlag = 1;
	}
}
atan2()に渡しているのはそれぞれ外積と内積であり、つまりそれぞれのベクトルのノルムが掛けられたsinとcosです。
sinとcosって、直角三角形で言えば斜辺の部分の長さが1だったらそれぞれsin == 高さ、cos == 幅になるじゃないですか?だから

20行では「2つのベクトルから思い浮かべられる直角三角形の高さ」
21行ではその幅

をatan2に渡している、つまりはPc.NextPositionから2頂点へ引いた線がなす角度を取得している。という感じになり、コメントに書いた通り「内側にあるのであれば、それを各頂点に行った結果は360度」になります。
Ute さんが書きました:また、このプログラムだと次のポリゴンが三角形であることが前提になっている(三頂点で比較しているので)と思うんですが、このプログラムのmqoデータには三角形以外にも勿論四角形ポリゴンが含まれていて、なぜこのプログラムで判定できるかがわからないのです…。
だいたい4頂点からなる面は、プログラムに読み込む時等に3頂点に変換すると思いますよ。
なのでプログラムの内部的には3頂点からなる面二つで四角形が構成されているのではないかと思います。
Ute さんが書きました:あわせて、3Dプログラミングにアルゴリズム等を紹介してくれる良いサイトなど御座いましたら是非教えて下さい。
ゲームつくろー!さんなんてよろしいのではないでしょうか?
調べて覗いた感じだと、数式を出すというよりは「この公式はこのような意味を持っている」というのを、ゲーム作りに即した形でかつイメージ的に書いてくださっているようですので、参考になるかと。

Ute

Re: ポリゴンに対する内外

#4

投稿記事 by Ute » 8年前

返答に気がつくのが遅れてしまいました…ありがとうございます。
内積・外積が単にノルムにsin、cosを掛けた物、という考えは基本的ながら、すっかり失念しておりました…。
6.2fで制限する処理も明確にポリゴンの内外を判定する為に意図的に狭めている、と考えると確かにすっきり通ります。
また、四角形ポリゴンが三角形に自動で変換されているとは驚きました…てっきりメタセコで見た通りのポリゴンが渡されているのだとばかり…
ご紹介頂いたゲームつくろー!さん等で学習を進めてみようと思います。
コードへのご丁寧な解説、及び簡潔な説明、感謝いたします!

閉鎖

“C言語何でも質問掲示板” へ戻る