ポリゴンと線分の当たり判定

先日のジムノ氏の注文により作成。何気に結構面白かったです（^^;　変数メチャ多くてちょい困ったけど。

早速ですが考え方を。まずはポリゴンを含む平面と線分の当たり判定を考える。これは割りと簡単で、線分の両端がそれぞれ平面の反対側にいればよい。ということは、平面状の適当な点から線分の端の点へのベクトルと、平面の法線ベクトルの内積が正か負かで平面のどちらかにいるかが判定できる。法線ベクトルはポリゴンの１点を支点として残りの２点をそれぞれのベクトルとして外積をとればよい。また線分の端の点のベクトルの支点としては先程の点を取ればよいので、これで内積をとればよい。さてここで気がつくのは、３つのベクトルは全部支点が同じで、そのうちの２つを外積をとってその結果ともう一つを内積をとっている。つまりこれはスカラー３重積。だからどうなんだと言われても別に何かあるわけじゃないんだけど（^^;　スカラー３重積はその３つのベクトルが作る平行６面体の体積になるが、じゃあ何で負になったりするんだという。簡単にいえば３重積の３つのベクトルが右回りか左回りかで正か負になる。今回もある意味それを利用している。まあ脱線はこのくらいにして、これらを式で表すと、ポリゴンの３点をそれぞれP1(p1x,p1y),P2(p2x,p2y),P3(p3x,p3y)、線分の両端をL1(l1x,l1y),L2(l2x,l2y)とすると、
( P1P2×P1P3・P1L1 )・( P1P2×P1P3・P1L2 ) <= 0
というわけで平面と線分はこれＯＫ。あとは交点がちゃんとポリゴン内にあるかどうか。これは少々厄介だったり。考え方はいろいろあるだろうけど私が考えたのは、交点がポリゴンの各辺からみて全部右側or左側だとOKだという判定。これは先ほどのスカラー３重積の符号が３つのベクトルの回り方(何)で決定することが利用できる。図なしでの説明は結構つらそうなので割愛すると（ぉぃ
( ( P1L1×P1L2・P1P2 ) <= 0 ∩ ( P2L1×P1L2・P2P3 ) <= 0 ∩ ( P3L1×P3L2・P3P1 ) <= 0 )
∪
( ( P1L1×P1L2・P1P2 ) >= 0 ∩ ( P2L1×P1L2・P2P3 ) >= 0 ∩ ( P3L1×P3L2・P3P1 ) >= 0 )
まあ、とりあえずなんとなくわかってくれ（ぉ
というわけでこれをソースに起こすと

bool LineAndPolygon( float P1[3], float P2[3], float P3[3], float L1[3], float L2[3] ){
	{
		//条件１　ポリゴンを含む平面と線分が交わる条件
		const float P1P2[3] = { P2[0] - P1[0], P2[1] - P1[1], P2[2] - P1[2] };
		const float P1P3[3] = { P3[0] - P1[0], P3[1] - P1[1], P3[2] - P1[2] };
		const float P1L1[3] = { L1[0] - P1[0], L1[1] - P1[1], L1[2] - P1[2] };
		const float P1L2[3] = { L2[0] - P1[0], L2[1] - P1[1], L2[2] - P1[2] };
		
		const float P1P2__P1P3[3] = {
			P1P2[1] * P1P3[2] - P1P2[2] * P1P3[1],
			P1P2[2] * P1P3[0] - P1P2[0] * P1P3[2],
			P1P2[0] * P1P3[1] - P1P2[1] * P1P3[0] };
		
		const float P1P2_P1P3_P1L1 = P1P2__P1P3[0] * P1L1[0] + P1P2__P1P3[1] * P1L1[1] + P1P2__P1P3[2] * P1L1[2];
		const float P1P2_P1P3_P1L2 = P1P2__P1P3[0] * P1L2[0] + P1P2__P1P3[1] * P1L2[1] + P1P2__P1P3[2] * P1L2[2];
		if( ( P1P2_P1P3_P1L1 < 0 ) == ( P1P2_P1P3_P1L2 < 0 ) ){
			return false;
		}
	}
	{
		//条件２　交点がポリゴン内にある条件
		bool sign[3];

		const float* P[3] = { P1, P2, P3 };
		for( int i = 0; i < 3; ++i ){
			const int j = ( i + 1 ) % 3;
			const float PP[3] = { P[j][0] - P[i][0], P[j][1] - P[i][1], P[j][2] - P[i][2] };
			const float PL1[3] = { L1[0] - P[i][0], L1[1] - P[i][1], L1[2] - P[i][2] };
			const float PL2[3] = { L2[0] - P[i][0], L2[1] - P[i][1], L2[2] - P[i][2] };

			const float fp = PP[0] * PL1[1] * PL2[2] + PP[1] * PL1[2] * PL2[0] + PP[2] * PL1[0] * PL2[1];
			const float fm = PP[2] * PL1[1] * PL2[0] + PP[0] * PL1[2] * PL2[1] + PP[1] * PL1[0] * PL2[2];
			sign[i] = ( fp > fm );
		}
		if( ( sign[0] != sign[1] ) || ( sign[1] != sign[2] ) || ( sign[2] != sign[0] ) ){
			return false;
		}
	}
	return true;
}

多分うまくいっていると思うけど十分なテストはしてないので御利用する場合(いるんけそんな奴？)は自己責任にてよろしくです（^^;