二つの三角形が交差するかどうかを検索またはポイントの2セットが与えられていない

Question

（（X1、Y1、Z1）、（X2、Y2、Z2）、（X3、Y3、Z3））と

（ （p1、q1、r1）、（p2、q2、r2）、（p3、q3、r3））である。

これらの三角形が交差しているかどうかをどのように確認しますか？

この問題の1つの明白な解決策は、各三角形によって形成される平面の方程式を見つけることです。平面が平行であれば交差しません。

そうでなければ、これらの面の法線ベクトルを使用して、これらの面の交差によって形成される線の式を見つけます。

ここで、この線が両方の三角形領域にある場合、これらの2つの三角形は交差します。

trianglesIntersect(Triangle T1, Triangle T2) 
{ 
    if(trianglesOnParallelPlanes(T1, T2)) 
    { 
     return false 
    } 
    Line L1 = lineFromPlanes(planeFromTriangle(T1), planeFromTriangle(T2)) 
    if(lineOnTriangle(T1, L1) AND lineOnTriangle(T2, L1)) 
    { 
     return true 
    } 
    return false 
} 

上記の関数を記述する方法を知っているとすれば、triangleIntersectの他の実装を検討する必要がありますか？

この問題を解決するアルゴリズムが高速ですか？

Answer 1

realtimerendering.comの訪問this table of geometric intersection algorithms礼儀は、三角/三角交差点のエントリを見て、クリステルエリクソン、Real-Time Collision Detection、172ページに、たとえば、参照に従ってください（私は非常にお勧めの本。）

基本的な考え方は簡単です。 2つの三角形が交差する場合、一方の三角形の2つの辺が他方の辺に交差するか（下の図の左の配置）、またはそれぞれの三角形の1つの辺が他の三角形と交差します。

だから6線分、三角形の交差テストを実行し、これらの構成のいずれかが見つかったかどうかを確認。

ここで、どのように線分/三角形交差テストを行うのですか？まあ、簡単です。 this table of geometric intersection algorithmsを参照し、線分（光線）/三角形の交差点の項目を見て、参照に従ってください。

（上記の簡単なテストでは、同一平面の三角形は正しく処理されません。これは問題ではありません：たとえば、三角形のメッシュ間の衝突を検出する場合、同一平面の場合はあいまいなので、結果が返されても問題はありませんが、アプリケーションが例外の1つである場合は、特別なケースとして、またはエリクソンで、separating-axis method、またはTomasMöllerのinterval overlap methodのようないくつかの方法で読むことができます。