三角形と直線の交差判定


三角形と直線の交差判定
  三角形と直線の交差は、

1.   三角形を通る平面を求める。
2.   その平面と直線との交点を求める。
3.   2.得られた交点を三角形の辺ベクトルの線形結合によって表す。
4.   3.得られた線形結合の係数から、交点が三角形に含まれるかどうかを判定する。

という $4$ 段階を経て判定されうる。(解説を省きたい場合にはまとめへスキップ)
解説
1.   三角形を通る平面を求める。
  問題の記述を簡潔にするため、 三角形 $ABC$ の頂点 $A$ を原点とする座標系を採用し、 点 $A$, $B$, $C$ の位置ベクトルをそれぞれ $\mathbf{a}$, $\mathbf{b}$, $\mathbf{c}$ と表すことにする。 $A$ は原点に置かれているので、
三角形と平面の交点00
である。
三角形と平面の交点の図00
三角形 $ABC$ を通る平面を $P$ とし、 平面の方程式
三角形と平面の交点01
と置く。 ここで、$\mathbf{n}$ は法線ベクトルであり、 $h$ は符号付き距離である。 また、 $\mathbf{x}$ は平面 $P$ 上の任意の位置ベクトルである。
  頂点の位置ベクトル $\mathbf{a}$, $\mathbf{b}$, $\mathbf{c}$ は、 平面 $P$ の上にあるので、
を満たす。 ここで、 $\mathbf{a} = 0$ であることから、 第一式より、
である。 これより、
である。 従って、 法線ベクトル $\mathbf{n}$ は、 $\mathbf{b}$ と $ \mathbf{c}$ の両方と直交するベクトルである。 よって、 $\mathbf{n}$ は $\mathbf{b}$ と $ \mathbf{c}$ の外積の方向を向く (下図) 。
三角形と平面の交点の図01
すなわち、
と表されるベクトルである。 ここで、$C$ はベクトルの大きさを決める定数である。
  以上のように、 法線ベクトル $\mathbf{n}$ と符号付き距離 $h$ が求められたので、 三角形 $ABC$ を通る平面の方程式は、
と表される。
  この式からも分かるように、 $\mathbf{n}$ に付いていた定数 $C$ は、 $0$ でないならばどんな値であっても構わない。 そこで今後は、 $C=1$ とする。 すなわち、
とする。
2.   平面と直線との交点を求める
  判定対象となっている直線を $L$ とし、 $L$ 上の 一点の位置ベクトルを $\mathbf{r}_{0}$、 $L$ の方向ベクトルを $\mathbf{m}$ とすると、 $L$ 上の任意の点 $\mathbf{r}$ は、 パラメータ $t$ によって、
と表される。
  平面 $P$ と直線 $L$ の交点を $I$ とし、 その位置ベクトルを $\mathbf{r}^{I}$ と表す。 $\mathbf{r}^{I}$ は直線 $L$ 上にあり、 なおかつ、 平面 $P$ 上にある点の位置ベクトルである (下図)。
三角形と平面の交点の図02
したがって、 $\mathbf{r}^{I}$ は、
と、
の両方を満たす。 これらより、
が成立する。 よって、
と $t$ が求まる。
  これより、 交点の位置 $\mathbf{r}^{I}$ は、
である。
3.   交点を三角形の辺ベクトルの線形結合によって表す
  ベクトル
と、 法線ベクトル
を合わせた3つのベクトルは、互いに線形独立である (証明は補足を参考)。
  よって、 任意のベクトルは、 これらの線形結合によって表されうる (次元と線形独立なベクトルは基底を成すを参考)。 従って、 交点 $\mathbf{r}^{I}$ を
と表すことが出来る。 ここで現れた係数 $ r_{1}, r_{2}, r_{3}$ の導出するためには、 次のように考察する。
  まず、 基本ベクトル
を定義する。 これらは互いに線形独立であるので、 ベクトル $\mathbf{b}, \mathbf{c}, \mathbf{n}$ の それぞれを
と表すことができる。
  これらを用いると、 交点 $\mathbf{r}^{I} $ を
と表すことができる。 一方、
と表すこともできるので、 上の式と各成分を比較することにより、
の関係が成立することが分かる。 これを行列を用いてまとめると、
となる。 ここで、 行列 $C$ と ベクトル $\mathbf{r}$ を
と定義すると、
と表せる。
  行列 $C$ は、 定義から分かるように ベクトル $\mathbf{b}$、$\mathbf{c}$、$\mathbf{n}$ を列ベクトルに持つ行列である。 すなわち、
である。 ところで、 補足で示されているように、 これらの列ベクトルは互いに線形独立である。 そして、 一般に互いに線形独立な列ベクトルのみを持つ正方行列は逆行列を持つことから、 $C$ には逆行列 $C^{-1}$ が存在する。 そこで、 $(2)$ の両辺に $C^{-1}$ を掛けると、
を得る。
  右辺の行列 $C$ とベクトル $\mathbf{r}^{I}$、$\mathbf{a}$ は、 既に与えられているもの(または求められたもの)であるので、 $(3)$ から $(1)$ の係数 $ r_{1}, r_{2}, r_{3}$ が導出される。
4.   係数を用いて交点が三角形に含まれるかどうかを判定する
  $(3)$ で求められた係数 $ r_{1}, r_{2}, r_{3}$ が如何なる関係性を満たすときに、 直線と三角形が交差したと判定されるのかをここで考察する。
  はじめに $r_{3}=0$ であることを示す。 このことは $(3)$ から直接示すことも出来るが、 次の方法によって示すことも出来る。 まず、 $(1)$ から、
が成立するが、
であるので、
である。 これより、
である。 また、 左辺の $\mathbf{r}^{I}$ は、 平面 $P$ 上の点であるので、
を満たすことから、
が成立する。 ここで、$\left( \mathbf{n}, \hspace{1mm} \mathbf{n} \right) =\| \mathbf{n} \|^2 \neq 0$ であることから、
が得られる。
  さて、 これと $(1)$ から $\mathbf{r}^{I}$ は、
と表される。 ベクトル $\mathbf{r}^{I} $ は、 頂点 $A$ から交点 $I$ に向かうベクトルであるので、 このベクトルが三角形 $ABC$ の中に含まれるための必要十分条件が求まれば、 それが直線 $L$ と三角形 $ABC$ が交差するための必要十分条件になる(下図)。
三角形と平面の交点の図03
そこで、交点 $I$ が三角形 $ABC$ の内部にあると仮定し、 直線 $AI$ と線分 $BC$ の交点を $J$ とする。 $J$ は線分 $BC$ 上の点であるので、 位置ベクトル $\mathbf{r}^{J}$ を
と表すことが出来る(下図)。
三角形と平面の交点の図04
これを用いると、 交点 $I$ が線分 $AJ$ 上の点であることから、 位置ベクトル $\mathbf{r}^{I}$ を
と表すことが出来る。
  これと $(4)$ を比較すると分かるように、
が成立し、 $0 \lt s \lt 1$ かつ $0 \lt \alpha \lt 1$ であることから、
の 3 つの関係が満たされる。 以上から、 交点 $I$ が三角形 $ABC$ の中に入っているならば、 $(5)$ が成立する。
  一方、逆に $(5)$ が成立すると仮定する。 まず、 $ 0 \lt r_{1} +r_{2} \lt 1 $ から
を満たす $\alpha$ が存在することが分かる。 このとき、
が成立するので、
を満たす $s$ が存在することが分かる。 これより、
となるため、 $(4)$ から $\mathbf{r}^{I} $ は、
と表される。
  ここで $ s\mathbf{b} + (1-s) \mathbf{c} $ は、 線分 $BC$ 上にある点の位置ベクトルである。 ゆえに、 $0 \lt \alpha \lt 1$ であることから、 $\mathbf{r}^{I} $ は、 点 $A$ から三角形内部にある点を指す位置ベクトルであることが分かる。
三角形と平面の交点の図05
  以上から、 $(5)$ は、 交点の位置 $\mathbf{r}^{I}$ が三角形 $ABC$ の中に含まれるための必要十分条件である。 ゆえに、 直線 $L$ と三角形 $ABC$ が交差するための必要十分条件である。


まとめ
  点 $\mathbf{r}_{0}$ を通り 方向ベクトルが $\mathbf{m}$ である直線 $L$ が、 頂点が $\mathbf{a}, \mathbf{b}, \mathbf{c}$ である三角形 $ABC$ と交差するための必要十分条件は、 $ABC$ を通る平面 $P$ の法線ベクトル
によって表される交点 $I$ の位置ベクトル
と $3$ 行 $3$ 列の行列
による関係式
から導かれる $\mathbf{r}$ の成分 係数 $r_{1}$ と $r_{2}$ が
を満たすことである。 ただし、$r_{1}$ ( $r_{2}$ ) は頂点 $A$ を原点とし、 $\vec{AB}$ と $\vec{AC}$ と三角形の法線を座標軸とする座標系における $\vec{AB}$ 方向 ( $\vec{AC}$ 方向) の成分である。
補足
  3つのベクトル
が互いに線形独立であることを示す。
三角形と平面の交点の図05
そこで、
と置く。 これより、
が成立する。 内積の線形性によって書き換えると、
と表される。 ここで、 スカラー三重積の循環性を用いると、
であり、 同様に $ (\mathbf{c} , \mathbf{n}) = 0 $ であるので、
が成立する。 $\mathbf{n}\neq 0$ であるので、 $\gamma = 0$ を得る。 よって、
が成立する。 $\mathbf{b} $ と $\mathbf{c} $ は、 三角形の辺ベクトルであるために、互いに平行でない(互いに独立である)。 よって、 上式が成立するためには、 必ず $\alpha=\beta=0$ でなくてはならない。 以上から、$\alpha=\beta=\gamma=0$ が示されたので、 3つのベクトル $\mathbf{b} , \mathbf{c} , \mathbf{n}$ は、互いに線形独立である。
  従って、 任意のベクトルは、これらの線形結合によって表される。