CAEのメッシュ作成などで、STLデータが直交格子のどこを通るか特定したいことがあります。その際に、直方体と三角形の交差判定が必要となります。交差判定には様々なアルゴリズムがありますが、ここでは「SAT (Separating Axis Theorem：分離軸定理)」による交差判定をご紹介します。
参考文献： Akenine-Möller, Tomas. "Fast 3D triangle-box overlap testing." Acm siggraph 2005 courses. 2005. 8-es.
目次
SAT (Separating Axis Theorem：分離軸定理)
SATによる要素どうしの交差判定は、ある軸に対して交差しているかどうかを判定します。その軸で要素が交差していない（分離している）と判定されると、その軸を分離軸と呼びます。
分かりやすくここでは、２次元平面上にある２つの長方形を考えます。簡単のために長方形の各辺は、X軸・Y軸に平行であるとします。
この場合、判定する軸はX軸・Y軸の２本をとります。どちらか一方の軸に対して、下図のようにその軸に各長方形を投影します。
①は投影した線分が重なっている状態です。線分が重なっていれば「交差」していると判定します。
②は投影した線分が離れています。線分が離れている場合は「分離」と判定できます。
長方形どうしが交差している場合、２本の軸（X軸・Y軸）に投影した線分が、どちらの軸でも必ず交差します。一方で、長方形が交差していない（分離している）場合、２本の分離軸への投影線分のどちらか（もしくは両方）が分離しています。
一般的にSATでは、判定する軸への投影線分が、複数ある判定軸のうちどれか一つでも分離していれば、その要素どうしは交差していない（分離している）と判定できます。
直方体と三角形の交差判定
軸の選び方はその要素の形状によって変わりますが、直方体と三角形の場合は、次の13本の軸で判定を行います。
- 直方体の３軸（X軸、Y軸、Z軸）→ 3本
- 三角形の法線軸 → 1本
- 三角形の各辺と直方体の3軸との外積 → 3×3 = 9本
なお、直方体はX軸、Y軸、Z軸に平行としています（一般的には回転していても構いませんが、下の例では分かりやすく回転は考えていません）。
この13本の軸に投影した線分のうち、どれか一つでも分離していれば、直方体と三角形は交差していない（分離）と判定できます。
Y軸で分離している例
分離の例をあげます。下図のような直方体と三角形があります。図を見れば人間であれば一目で分離しているとわかります。
まず、X軸について判定します。
X軸に投影した線分は交差しているので、この軸では交差と判定されます。
次にY軸について見ていきます。
Y軸に投影した線分は分離しています。この時点で、この直方体と三角形どうしは分離していると判定できます。
三角形の法線軸で分離している例
次に下図のような例を考えます。
これも人間が見ると一目で分離していると分かりますが、理論に従い各軸で判定していきます。
まず、X軸・Y軸・Z軸の3軸について判定します。
この例では、XYZの３軸とも投影線分は交差しています。
次に、三角形の法線を軸として判定を行います。
三角形の法線ベクトル方向の軸をとり、その軸に投影します。投影線分で見ると分離していることが分かります。つまり、これらの要素は分離していると判定できます。
交差（分離）判定
プログラム上は、13本の軸全てで判定を行う必要はなく、順番に見ていき分離と判定された時点で、その要素どうしは交差していないと決定できます。
逆に、要素が交差している場合は分離軸が一つもないので、13本全てで交差と判定された場合に、最終的に交差と判断できます。
以下のページで直方体と三角形の交差判定ができるので、試してみてください。
