三角形の交差判定

交差判定ってめんどくさい

レイトレーサーを作ろうとしてやっぱり避けて通れないのが交差判定　特に三角形。これを適当に説明。

三角形の交差判定
(X, Y, Z)の異なる座標をもつ点A, B, Cで構成される三角形について
D点から始まる視線単位ベクトルVが交差するか判定する方法。
変数はu,v,d

1.三角形と視線の開始点を原点に移す
B’ = B – A
C’ = C – A
D’ = D – A
2.三角形の属する面の関数を作る
f(u, v) = B’u + C’v
3.視線と面の交点を求める方程式を作る
B’u + C’v = D’ + Vd
B’u + C’v – Vd = D’
A=(B’, C’, -V)
x=(u, v, d)
Ax = D’
4.解いて交差するか判定
解くのはクラメールの公式でOK
交差する条件は
u >= 0 かつ
v >= 0　かつ
u + v <= 1
5.交差点と視点からの距離を求める
視点からの距離 = d
交差点 = A – B’u – C’v