床井研究室

参考

[MT97] (Fast, minimum storage ray-triangle intersection) → 安直レイトレーシング入門に反映すること。この論文はレイトレーシングやってる人には基本なんだろうな。

視線と三角形の交差の有無と交差点の位置を調べる

\({\bf O}\) を起点として \({\bf D}\) の方向に向かう視線上の点 \({\bf R}\left(t\right)\) は、以下のように定義されます。

\[ {\bf R}\left(t\right)={\bf O}+t{\bf D} \]

一方、３点 \({\bf V}_0\)、\({\bf V}_1\)、\({\bf V}_2\) を頂点とする三角形上の点 \({\bf S}\left(u, v\right)\) は、以下のように定義されます。

\[ {\bf S}\left(u, v\right)=\left(1-u-v\right){\bf V}_0+u{\bf V}_1+v{\bf V}_2 \]

この \(\left(u, v\right)\) はこの三角形上の重心座標で、これがこの三角形の内部にあるなら \(u \geq 0\)、\(v \geq 0\)、かつ \(u+v \leq 1\) すなわち \(1-u-v \geq 0\) を満たします。なお、この \(\left(u, v\right)\) は頂点色や頂点法線ベクトル、テクスチャ座標などの頂点属性の補間に用いることができます。

視線 \({\bf R}\left(t\right)\) がこの三角形と交差するかどうかを調べるには、\({\bf R}\left(t\right)={\bf S}\left(u, v\right)\) を解きます。

\[ {\bf O}+t{\bf D}=\left(1-u-v\right){\bf V}_0+u{\bf V}_1+v{\bf V}_2 \]

これを次のように行列とベクトルの積の形に変形します。

\[ \begin{pmatrix}-{\bf D}&{\bf V}_1-{\bf V}_0&{\bf V}_2-{\bf V}_0\end{pmatrix}\begin{pmatrix}t\\u\\v\end{pmatrix}={\bf O}-{\bf V}_0 \]

この \({\bf V}_1-{\bf V}_0={\bf E}_1\)、\({\bf V}_2-{\bf V}_0={\bf E}_2\)、\({\bf O}-{\bf V}_0={\bf T}\) とおき、クラメールの公式*1を用いて上式を解きます。

\[ \begin{pmatrix} t\\ u\\ v \end{pmatrix} =\frac{1}{\begin{vmatrix}-{\bf D}&{\bf E_1}&{\bf E}_2\end{vmatrix}} \begin{pmatrix} \begin{vmatrix}{\bf T}&{\bf E}_1&{\bf E}_2\end{vmatrix}\\ \begin{vmatrix}-{\bf D}&{\bf T}&{\bf E}_2\end{vmatrix}\\ \begin{vmatrix}-{\bf D}&{\bf E}_1&{\bf T}\end{vmatrix} \end{pmatrix} \]

\(t\) は視線 \({\bf R}\left(t\right)\) のパラメータですから、これより交点の位置を求めることができます。またスカラー三重積より \(\begin{vmatrix}{\bf A}&{\bf B}&{\bf C}\end{vmatrix}=-\left({\bf A}\times{\bf C}\right)\cdot{\bf B}=-\left({\bf C}\times{\bf B}\right)\cdot{\bf A}\) なので、上式は次のように書き換ええることができます。

\[ \begin{pmatrix} t\\ u\\ v \end{pmatrix} =\frac{1}{\left({\bf D}\times{\bf E}_2\right)\cdot{\bf E}_1} \begin{pmatrix} \left({\bf T}\times{\bf E}_1\right)\cdot{\bf E}_2\\ \left({\bf D}\times{\bf E}_2\right)\cdot{\bf T}\\ \left({\bf T}\times{\bf E}_1\right)\cdot{\bf D} \end{pmatrix} =\frac{1}{{\bf P}\cdot{\bf E}_1} \begin{pmatrix} {\bf Q}\cdot{\bf E}_2\\ {\bf P}\cdot{\bf T}\\ {\bf Q}\cdot{\bf D} \end{pmatrix} \]

ここで \({\bf P}={\bf D}\times{\bf E}_2\) および \({\bf Q}={\bf T}\times{\bf E}_1\) です。

法線ベクトルを使う

考えてみれば \({\bf E}_1\times{\bf E}_2={\bf N}\) はこの三角形の法線ベクトルです。これは陰影付けのときにも使用するので、すべての三角形であらかじめ求めていることも多いように思います。もしこれを利用するなら、上式を次のように書き換えてもいいかもしれません。

\[ \begin{pmatrix} t\\ u\\ v \end{pmatrix} =\frac{-1}{\left({\bf E}_1\times{\bf E}_2\right)\cdot{\bf D}} \begin{pmatrix} \left({\bf E}_1\times{\bf E}_2\right)\cdot{\bf T}\\ \left({\bf T}\times{\bf D}\right)\cdot{\bf E}_2\\ -\left({\bf T}\times{\bf D}\right)\cdot{\bf E}_1 \end{pmatrix} =\frac{-1}{{\bf N}\cdot{\bf D}} \begin{pmatrix} {\bf N}\cdot{\bf T}\\ {\bf M}\cdot{\bf E}_2\\ -{\bf M}\cdot{\bf E}_1 \end{pmatrix} \]

ここで \({\bf M}={\bf T}\times{\bf D}\) です。

ということを考えてみたけど、三角形のデータに法線ベクトルを持たせるときは正規化しちゃうだろうし、SSE やシェーダを使えば外積って簡単に計算できるから、あんまり意味ないなぁ。\({\bf N}\cdot{\bf D}=0\) になるのは視線と三角形が平行のときで、\(t\) の式は視線 \({\bf R}\left(t\right)\) を三角形の平面の方程式に代入した \({\bf N}\cdot{\bf R}\left(t\right)-{\bf N}\cdot{\bf V}_0=0\) を変形して \(t\) を求めたものになるな。当たり前か。

ラスタライザ野郎

ラスタライザを自分で書く私は古くさいラスタライザ野郎なんだろうな。でも、それならレイトレーシングのレンダラを書いている人はサンプリング野郎だよな。