Ray Cast では、次の問いを解きます。
Ray（半直線）が、三角形の内部に当たっているか？
これは次の2つの点が一致するかどうか、という問題です。
Ray は、次の一次式で表されます。
\[ P(t) = \mathbf{origin} + t\,\mathbf{ray} \]
ここでの意味は次のとおりです。
Ray は半直線なので、次の条件が付きます。
\[ t \ge 0 \]
三角形の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} \]
この式は、
進んだ点を意味します。
$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} \]
この連立方程式を解くことで、次が分かります。
Ray が三角形に当たっているためには、次がすべて成り立つ必要があります。
\[ \begin{aligned} t &\ge 0 \\ u &\ge 0 \\ v &\ge 0 \\ u + v &\le 1 \end{aligned} \]
これらは次を意味します。
Ray Cast の三角形判定は、
という、純粋に数学的な問題として解くことができます。
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 ????; }