凸体と線分の交差 - ゲームプログラミングというゲームを攻略するWIKI

問題を定義する

• a*x + b*y + c*z + d = 0 で表される平面（法線ベクトル側を外とする）

が複数あるとして

• (x1, y1, z1) から (x1 + dx, y1 + dy, z1 + dz) への線分

が、全ての平面に入るときの t と いずれかの平面から出るときの t を求める。

問題を整理する

平面の法線ベクトル (a, b, c) と、線分のベクトル (dx, dy, dz) の内積が

• 正ならば線分は内から外に向けて平面を通る。
• 負ならば線分は外から内に向けて平面を通る。

通るタイミングは平面と線分の交点。

例外的な状況

線分が平面と平行な場合

• 始点 (x1, y1, z1) が平面の外側にあるなら、交差しない。（tが無限大のとき入って、tがマイナス無限大のとき出るとも考えられる）
• 始点 (x1, y1, z1) が平面の内側にあるなら、tがマイナス無限大のとき入って、tが無限大のとき出ると考えられる。
• 始点 (x1, y1, z1) が平面上にあるなら、どちらとも考えられる。

実装

線分が平面上にある場合は交差している状態とみなすと、以下のようなコードになる。

void intersection(float a, float b, float c, float d, float x, float y, float z, float dx, float dy, float dz, float & ti, float & to)
{
	float dot =  a * dx + b * dy + c * dz;
	if (dot == 0)
	{
		// parallel
		float dis = distance(a, b, c, d, x, y, z);
		if (0 < dis)
		{
			// always outside
			ti = INFINITY;
			to = - INFINITY;
		}
	}
	else
	{
		float t = (- a * x - b * y - c * z - d) / dot;
		if (dot < 0)
		{
			if (ti < t)
			{
				ti = t;
			}
		}
		else
		{
			assert(0 < dot);
			if (t < to)
			{
				to = t;
			}
		}
	}
}