3D衝突編
その21 三角ポリゴンと三角ポリゴン
最も基本的な形である三角ポリゴン。この衝突は、実は結構大変です。三角ポリゴンは「1面・3辺・3頂点」と要素が割とみっしり詰まっています。まともにやると7要素×7要素＝49通りな衝突をチェックしないといけないわけです。ポリゴンのような「閉じた図形」は平面のような開いた図形よりも「無限大」と「陰関数」を使えない分ずっと面倒なんです。
ただ、非常に基本的なプリミティブなので色々研究されています。ここではMollerさんが1997年に発表した論文の衝突判定を噛み砕いてみます。元論文はこちら（A Fast Triangle-Triangle Intersection Test）。
① 頂点が片方に偏っていたら衝突は起こらない
三角ポリゴンが空中にふよふよと浮いている事を想像してみて下さい：
この場合、三角ポリゴンは絶対に平面に接しません。もう一方の三角形がこの平面上にあるならば、もちろんその三角形とも衝突しないわけです。つまり、一方の三角形の頂点がもう一方の三角形を含む平面の片方に偏っていたら、衝突判定をすぐに終了できるわけです。
この判定は両方の三角形でテストする必要があります。もし上の三角形が地面にめり込んでいたとしても、もう一方の三角形がやはり片方に偏っていたら、初めて「衝突の可能性はない」と判断できます：
三角形ポリゴン同士が衝突する可能性があるのは「双方の含有平面にそれぞれがぶすっと刺さっている時」のみです：
この時、2つの平面の交差線上を見れば、衝突しているのか、やっぱり衝突していないかがわかります。上の図の赤丸で囲んだ部分です。結局三角ポリゴン同士の衝突は「双方の三角ポリゴンと交差している線上の交差範囲が重なっているか否か」という問題に帰着します。
この直線を双方の三角ポリゴンは含んでいます。その含まれる範囲を求めるには、含有直線と三角形の辺との交点を求めれば良いんです。
② 直線上の交点を比で求める
含有直線と三角形の辺の交点を求める時、論文ではうまい方法を用いています。下の図を御覧下さい：
平面に三角形がぷすっと刺さっている状態です。平面上の直線を三角形も含んでいます。今、三角形の頂点v1とv2から平面に向かって垂線を下ろし、その距離をd1、d2とします。この時、d1を辺に持つ三角形と、d2を辺に持つ三角形が相似なのは明らかです。と言う事は、赤い線で示した元の三角形の辺をd1対d2に分割する点が、求めたい交点になるわけです。d1もd2も求めるのは簡単ですし、内分点を求めるのも簡単です。
上の平面はもう一方の三角形を含む平面ですから、その法線はもう一方の三角形の頂点座標から、
で求められます。この法線を正規化しておけば、平面上の一点（例えばv21）と宙に浮いているv1（=v11）とのベクトルと法線との内積が距離d1になります：
内分点はv1 + (v2 - v1) * [内分比率]です。この比率は今d1 / (d1 + d2)ですから、求めたい交点p12は、
となります。もう一方（p13）も全く同様に求められます。この2点p12、p13が直線に含まれる三角形の交差領域です。
同じことを反対側の三角形について行うと含有直線上に4つの点（p12、p13、p22、p23）が並ぶことになります。後はp12-p13領域とp22-p23領域が重なっているかを調べるだけです。これはもちろんp12-p13の長さを求めて云々とやっても良いのですが、XYZのどれかの軸に各点を投影してしまったと考えて点の1成分だけで比較しても実は構いません。
p12-p13領域とp22-p23領域が重なっている事がわかれば、2つの三角ポリゴンは衝突していると判定できます。
③ 関数公開
以上のアイデアを組み込んだ関数を公開します。作業用のサブ関数がいくつもありますが、これらはいずれも「2つの三角形が同じ平面にある」という特殊ケースに対応させるために用意しました：
// 三角ポリゴン同士の衝突関連メソッド
float cross2D(const D3DXVECTOR2 &u, const D3DXVECTOR2 &v) {
return u.y * v.x - u.x * v.y;
}
int pointInTriangle2D(const D3DXVECTOR2 &p, const D3DXVECTOR2 &a, const D3DXVECTOR2 &b, const D3DXVECTOR2 &c) {
float pab = cross2D(p - a, b - a);
float pbc = cross2D(p - b, c - b);
if (pab * pbc < 0)
return 0;
float pca = cross2D(p - c, a - c);
if (pab * pca < 0)
return 0;
return 1;
}
float Signed2DTriArea(const D3DXVECTOR2 &a, const D3DXVECTOR2 &b, const D3DXVECTOR2 &c) {
return (a.x - c.x) * (b.y - c.y) - (a.y - c.y) * (b.x - c.x);
}
int test2DSegmentSegment(const D3DXVECTOR2 &a, const D3DXVECTOR2 &b, const D3DXVECTOR2 &c, const D3DXVECTOR2 &d, float &t, D3DXVECTOR2 &p) {
float a1 = Signed2DTriArea(a, b, d);
float a2 = Signed2DTriArea(a, b, c);
if (a1 * a2 < 0.0f) {
float a3 = Signed2DTriArea(c, d, a);
float a4 = a3 + a2 - a1;
if (a3 * a4 < 0.0f) {
t = a3 / (a3 - a4);
p = a + t * (b - a);
return 1;
}
}
return 0;
}
///////////////////////////////////////////
// 三角ポリゴンと三角ポリゴンの衝突判定
//
// t1[3] : 三角ポリゴン1の頂点座標
// t2[3] : 三角ポリゴン2の頂点座標
// 戻り値: 衝突ならtrue
bool intersectTriangleTriangle(const D3DXVECTOR3 t1[3], const D3DXVECTOR3 t2[3]) {
// t1を含む平面とt0の3頂点の距離の符号が同じならば衝突していない
D3DXVECTOR3 N1, N2;
D3DXVec3Cross(&N1, &(t1[1]-t1[0]), &(t1[2]-t1[0]));
D3DXVec3Normalize(&N1, &N1);
D3DXVec3Cross(&N2, &(t2[1]-t2[0]), &(t2[2]-t2[0]));
D3DXVec3Normalize(&N2, &N2);
float d1 = D3DXVec3Dot(&(-N1), &t1[0]);
float d2 = D3DXVec3Dot(&(-N2), &t2[0]);
float dist1[3], dist2[3];
unsigned sign1 = 0, sign2 = 0;
for (unsigned i = 0; i < 3; i++) {
dist1[i] = D3DXVec3Dot(&N2, &t1[i]) + d2;
if (dist1[i] > 0)
sign1 |= (1 << i);
dist2[i] = D3DXVec3Dot(&N1, &t2[i]) + d1;
if (dist2[i] > 0)
sign2 |= (1 << i);
}
if (sign1 == 0 || sign1 == 7 || sign2 == 0 || sign2 == 7) {
// 全dist1 == 0の場合は同一平面衝突の可能性がある
if (fabsf(dist1[0]) >= 0.00001f || fabsf(dist1[1]) >= 0.00001f || fabsf(dist1[2]) >= 0.00001f)
return false;
// 三角ポリゴンの頂点を軸並行平面へ投影
D3DXVECTOR2 t1_2D[3], t2_2D[3];
if (fabsf(N1.x) >= fabsf(N1.y) && fabsf(N1.x) >= fabsf(N1.z)) {
// YZ平面
for (unsigned i = 0; i < 3; i++) {
t1_2D[i].x = t1[i].y; t1_2D[i].y = t1[i].z;
t2_2D[i].x = t2[i].y; t2_2D[i].y = t2[i].z;
}
} else if (fabsf(N1.y) >= fabsf(N1.z)) {
// XZ平面
for (unsigned i = 0; i < 3; i++) {
t1_2D[i].x = t1[i].x; t1_2D[i].y = t1[i].z;
t2_2D[i].x = t2[i].x; t2_2D[i].y = t2[i].z;
}
} else {
// XY平面
for (unsigned i = 0; i < 3; i++) {
t1_2D[i].x = t1[i].x; t1_2D[i].y = t1[i].y;
t2_2D[i].x = t2[i].x; t2_2D[i].y = t2[i].y;
}
}
// 線分間衝突
float t;
D3DXVECTOR2 p;
for (unsigned i = 0; i < 3; i++) {
for (unsigned j = 0; j < 3; j++) {
if (test2DSegmentSegment(t1_2D[i], t1_2D[(i+1)%3], t2_2D[j], t2_2D[(j+1)%3], t, p))
return true;
}
}
// 点含有
for (unsigned i = 0; i < 3; i++) {
if (pointInTriangle2D(t1_2D[i], t2_2D[0], t2_2D[1], t2_2D[2]))
return true;
}
for (unsigned i = 0; i < 3; i++) {
if (pointInTriangle2D(t2_2D[i], t1_2D[0], t1_2D[1], t1_2D[2]))
return true;
}
// 残念・・・
return false;
}
/////////////////////////////////
// 同一平面には無い
////
// 頂点の片側を合わせるためのハッシュテーブル
static struct Hash { int i1, i0, i2; } hash[7] = {
{0, 0, 0},
{0, 1, 2}, // idx0
{1, 0, 2}, // idx1
{2, 0, 1}, // idx2
{2, 0, 1}, // idx2
{1, 0, 2}, // idx1
{0, 1, 2}, // idx0
};
// 2三角形の共通線Lで交わっているか？
D3DXVECTOR3 D;
D3DXVec3Cross(&D, &N1, &N2);
D3DXVec3Normalize(&D, &D);
{
float p1[3] = {
D3DXVec3Dot(&D, &t1[hash[sign1].i0]),
D3DXVec3Dot(&D, &t1[hash[sign1].i1]),
D3DXVec3Dot(&D, &t1[hash[sign1].i2]),
};
float p2[3] = {
D3DXVec3Dot(&D, &t2[hash[sign2].i0]),
D3DXVec3Dot(&D, &t2[hash[sign2].i1]),
D3DXVec3Dot(&D, &t2[hash[sign2].i2]),
};
float d1[3] = {
dist1[hash[sign1].i0],
dist1[hash[sign1].i1],
dist1[hash[sign1].i2],
};
float d2[3] = {
dist2[hash[sign2].i0],
dist2[hash[sign2].i1],
dist2[hash[sign2].i2],
};
float t1_1 = p1[0] + (p1[1] - p1[0]) * d1[0] / (d1[0] - d1[1]);
float t1_2 = p1[2] + (p1[1] - p1[2]) * d1[2] / (d1[2] - d1[1]);
float t2_1 = p2[0] + (p2[1] - p2[0]) * d2[0] / (d2[0] - d2[1]);
float t2_2 = p2[2] + (p2[1] - p2[2]) * d2[2] / (d2[2] - d2[1]);
// t1_1～t1_2の間にある？
if (t1_1 < t1_2) {
if (t2_1 < t2_2) {
if (t2_2 < t1_1 || t1_2 < t2_1)
return false;
} else {
if (t2_1 < t1_1 || t1_2 < t2_2)
return false;
}
} else {
if (t2_1 < t2_2) {
if (t2_2 < t1_2 || t1_1 < t2_1)
return false;
} else {
if (t2_1 < t1_2 || t1_1 < t2_2)
return false;
}
}
}
return true;
}
意外と大変なんですよ～(^-^;。
