Ray Cast と三角形交差判定（重心座標と連立方程式）

Ray Cast では、次の問いを解きます。

Ray（半直線）が、三角形の内部に当たっているか？

これは次の2つの点が一致するかどうか、という問題です。

• Ray 上の点
• 三角形上の点

Ray は、次の一次式で表されます。

\[ P(t) = \mathbf{origin} + t\,\mathbf{ray} \]

ここでの意味は次のとおりです。

• $\mathbf{origin}$ ：Ray の開始点（位置ベクトル）
• $\mathbf{ray}$ ：Ray の向き（方向ベクトル）
• $t$ ：Ray 上をどれだけ進んだかを表す実数

Ray は半直線なので、次の条件が付きます。

\[ t \ge 0 \]

三角形の3頂点を次のように置きます。

• $v_0$ ：基準となる頂点
• $v_1$ ：2つ目の頂点
• $v_2$ ：3つ目の頂点

まず、$v_0$ から他の頂点へ向かう辺ベクトルを定義します。

\[ \begin{cases} \mathbf{edge1} = v_1 - v_0 \\ \mathbf{edge2} = v_2 - v_0 \end{cases} \]

この2本のベクトルで、三角形の平面が張られます。

三角形上の任意の点 $Q$ は、次の形で表せます。

\[ Q(u, v) = v_0 + u\,\mathbf{edge1} + v\,\mathbf{edge2} \]

この式は、

• $v_0$ を出発点として
• $\mathbf{edge1}$ 方向に $u$ 倍
• $\mathbf{edge2}$ 方向に $v$ 倍

進んだ点を意味します。

$u, v$ を自由に動かすと、点 $Q$ は次の範囲を動きます。

\[ 0 \le u \le 1, \quad 0 \le v \le 1 \]

この範囲は、三角形ではなく平行四辺形になります。

そこで、次の条件を追加します。

\[ \begin{aligned} u &\ge 0 \\ v &\ge 0 \\ u + v &\le 1 \end{aligned} \]

この条件を満たす点だけが、三角形の内部になります。

Ray と三角形が交わるとき、次の式が成り立ちます。

\[ \mathbf{origin} + t\,\mathbf{ray} = v_0 + u\,\mathbf{edge1} + v\,\mathbf{edge2} \]

これは「Ray 上の点」と「三角形上の点」が同じ位置である、という意味です。

上の式を整理すると、次の形になります。

\[ t\,\mathbf{ray} = (v_0 - \mathbf{origin}) + u\,\mathbf{edge1} + v\,\mathbf{edge2} \]

ここで、次を定義します。

\[ \mathbf{d} = \mathbf{origin} - v_0 \]

未知数は $u, v, t$ の3つです。

$x, y, z$ 成分ごとに書き出すと、次の連立方程式になります。

\[ \begin{cases} u\,\mathbf{edge1}_x + v\,\mathbf{edge2}_x + t(-\mathbf{ray}_x) = d_x \\ u\,\mathbf{edge1}_y + v\,\mathbf{edge2}_y + t(-\mathbf{ray}_y) = d_y \\ u\,\mathbf{edge1}_z + v\,\mathbf{edge2}_z + t(-\mathbf{ray}_z) = d_z \end{cases} \]

この連立方程式を解くことで、次が分かります。

• $u, v$ ：交点が三角形のどの位置か（重心座標）
• $t$ ：Ray の開始点から交点までの距離

Ray が三角形に当たっているためには、次がすべて成り立つ必要があります。

\[ \begin{aligned} t &\ge 0 \\ u &\ge 0 \\ v &\ge 0 \\ u + v &\le 1 \end{aligned} \]

これらは次を意味します。

• $t \ge 0$ ：Ray が前方向に伸びている
• $u, v$ の条件：交点が三角形の外に出ていない

Ray Cast の三角形判定は、

• Ray と三角形を数式で表し
• それらを連立方程式として一致させ
• 解が条件を満たすかを調べる

という、純粋に数学的な問題として解くことができます。

float Math::Det(XMFLOAT3 a, XMFLOAT3 b, XMFLOAT3 c) {
// 3x3 行列の行列式 
// | a.x a.y a.z | 
// | b.x b.y b.z | 
// | c.x c.y c.z |
return  /* TODO: 1つ目の + 項 */     
      + /* TODO: 2つ目の + 項 */ 
      + /* TODO: 3つ目の + 項 */
      - /* TODO: 1つ目の - 項 */
      - /* TODO: 2つ目の - 項 */
      - /* TODO: 3つ目の - 項 */;
}

 bool Math::Intersect( XMFLOAT3 origin, XMFLOAT3 ray, XMFLOAT3 v0, XMFLOAT3 v1, XMFLOAT3 v2) { // ---- ベクトルの準備 ----
// Ray の始点・方向、三角形の頂点を XMVECTOR に変換
// （DirectXMath で計算するため）
XMVECTOR vOrigin = XMLoadFloat3(&origin); // Ray の開始点 O
XMVECTOR vRay    = XMLoadFloat3(&ray);    // Ray の方向ベクトル
XMVECTOR vV0     = XMLoadFloat3(&v0);     // 三角形の頂点 v0
XMVECTOR vV1     = XMLoadFloat3(&v1);     // 三角形の頂点 v1
XMVECTOR vV2     = XMLoadFloat3(&v2);     // 三角形の頂点 v2
 
 
//--------------------------------------
// 三角形の 2 本の辺ベクトルを作る
//--------------------------------------
// edge1 = v1 - v0  （三角形の一辺）
// edge2 = v2 - v0  （三角形のもう一辺）
XMVECTOR vEdge1 = ;
XMVECTOR vEdge2 = ;
 
// 行列式計算のため、XMFLOAT3 に戻す
XMFLOAT3 edge1;
XMFLOAT3 edge2;
XMStoreFloat3(&edge1, vEdge1);
XMStoreFloat3(&edge2, vEdge2);
 
 
//--------------------------------------
// d = origin - v0
//--------------------------------------
// 三角形の基準点 v0 から、Ray の開始点 origin へのベクトル
// 連立方程式
//   t*ray = (v0 - origin) + u*edge1 + v*edge2
// を作るための準備
XMFLOAT3 d;
XMStoreFloat3(&d, );
 
 
//--------------------------------------
// ray を反転（-ray）
//--------------------------------------
// 連立方程式を
//   u*edge1 + v*edge2 + t*(-ray) = d
// の形にそろえるため、ray に -1 を掛ける
ray = {
    ray.x * -1.0f,
    ray.y * -1.0f,
    ray.z * -1.0f
};
 
 
//--------------------------------------
// 連立方程式の分母（行列式）
//--------------------------------------
// denom = det(edge1, edge2, -ray)
// → 3 本のベクトルが作る行列の行列式
// → 0 なら、平面と Ray が平行で交点を持たない
float denom = Det();
 
 
// 平行（解なし）の判定
if (denom <= 0.0f)
{
    // Ray が三角形の平面と交差しない
    return false;
}
 
 
//--------------------------------------
// クラメルの公式で u, v, t を求める
//--------------------------------------
 
// u = det(d, edge2, -ray) / denom
// → 交点が edge1 方向にどれだけ進んだか（重心座標 u）
float u = Det() / denom;
 
// v = det(edge1, d, -ray) / denom
// → 交点が edge2 方向にどれだけ進んだか（重心座標 v）
float v = Det() / denom;
 
// t = det(edge1, edge2, d) / denom
// → Ray の開始点から交点までの距離
float t = Det() / denom;
 
 
//--------------------------------------
// 三角形内部 ＋ Ray の向き 判定
//--------------------------------------
// t >= 0  : Ray の前方向に交点がある
// u >= 0  : v0 → v1 方向に外れていない
// v >= 0  : v0 → v2 方向に外れていない
// u + v <= 1 : 三角形の内部に入っている
if (/*複合条件*/)
{
    // Ray が三角形の内部にヒット
    return ????;
}
 
// 条件を満たさない → 当たっていない
return ????;
 
}