algorithm - 3D空間での三角三角交点

Question

私はいくつかの3Dジオメトリを扱っています。三角形と別の三角形の交点を見つける必要があります。

どのアルゴリズムを使用できますか?

Answer 1

多くの人は、2006 年に次の論文 ( PDF へのリンク) で説明されているメソッドの実装 (ソース コードへのリンク)に依存しているようです。

Tropp、Oren、Ayellet Tal、Ilan Shimshoni。「衝突検出のための高速な三角形から三角形への交差テスト。」コンピューター アニメーションと仮想世界 17.5 (2006): 527-535。

ただし、そのコードには問題があります (古いプログラミング スタイルを採用し、型にはまらない表記法を使用し、基礎となる幾何学的解釈を失うことを除いて): 「行列式」は、間違った方法で行われた場合、必ずしも数学をより堅牢にするわけではありません。

Moeller の方法 ( PDF へのリンク) を使用するか、CGAL ライブラリ ( link、「Triangle_3_Triangle_3_do_intersect.h」)に実装されているDelliver の論文 ( PDF へのリンク) を参照することをお勧めします。

例: 上記で実装された交差ルーチンは、三角形 (p0,p1,p2) と (q0,q1,q2) が次の点によって定義されることを示します

p0 = (-21, -72, 63)
p1 = (-78, 99, 40)
p2 = (-19, -78, -83)
q0 = (96, 77, -51)
q1 = (-95, -1, -16)
q2 = (9, 5, -21)

交差していません。三角形の写真は次のとおりです。

コード スニペットは次のとおりです (元のコードに追加)。

#include <iostream>

inline void setPoint(double p[3], const double x, const double y, const double z)
{
    p[0] = x; p[1] = y; p[2] = z;
}

inline void computeEdges(double v0[3], double v1[3], const double p0[3], const double p1[3], const double p2[3])
{
    v0[0] = p1[0]-p0[0];
    v0[1] = p1[1]-p0[1];
    v0[2] = p1[2]-p0[2];
    v1[0] = p2[0]-p0[0];
    v1[1] = p2[1]-p0[1];
    v1[2] = p2[2]-p0[2];
}

void main()
{
    unsigned int numErrors(0), count(0);
    double p0[3], p1[3], p2[3], q0[3], q1[3], q2[3];
    double v0[3], v1[3], w0[3], w1[3];
    bool res, answer;
    int ret;

    std::cout << "Testing the correctness of tr_tri_intersect3D" << std::endl;

    {
        // Non excluding triangles in generic positions, big determinants, intersecting
        ++count;
        setPoint(p0, -21, -72, 63);
        setPoint(p1, -78, 99, 40);
        setPoint(p2, -19, -78, -83);
        setPoint(q0, 96, 77, -51);
        setPoint(q1, -95, -1, -16);
        setPoint(q2, 9, 5, -21);
        answer = true;

        computeEdges(v0, v1, p0, p1, p2);
        computeEdges(w0, w1, q0, q1, q2);
        int ret = tr_tri_intersect3D(p0, v0, v1, q0, w0, w1);
        bool res = ( ret != 0 );

        if( res != answer )
        {
            std::cout << "# wrong answer on test " << count << "!\n";
            ++numErrors;
        }
    }

}

算術演算の数に関する最後の注意: このメソッドは、事前に計算された入力エッジ ベクトルを取り込むため、12 +/- 演算を論文の表 I に追加する必要があります。

大事なことを言い忘れましたが、私が書いていることを自分で確認し、私が何かを誤解していると思われる場合は、フィードバックをお寄せください!

Answer 2

このホワイト ペーパーでは、1 つの実装について説明します。

http://knight.temple.edu/~lakaemper/courses/cis350_2004/etc/moeller_triangle.pdf

交差が発生したポイント/セグメントを知りたいのか、交差が発生したかどうかを知りたいのかによって、さまざまな手法があることに注意してください。このペーパーでは、交点を表す線分を示します。

Answer 3

「Faster Triangle-Triangle Intersection Tests」というタイトルのDevillersらによる優れた論文があります-（はい、Google検索を行いましたが、検索キーワードは重要です...）

とにかく、彼らのポイント (MichaelM の回答の Moeller 論文と比較して) は、選択した 4 つのポイントのグループの決定要因を実行することによって、組み合わせ情報を取得する必要があるということです (論文ではその方法が説明されています)。これにより、問題のある矛盾する可能性があり、おそらく実際にはそれほど速くない中間値の計算が回避されます...

これらの決定要因は、4 つの点によって形成される四面体が右巻き、左巻き、または縮退 (平面) のいずれであるかを判断するものとして見ることができます。この値は、4 つの点のいずれかが他の 3 つの点によって形成される平面の一方の側にあるか他方の側にあるか、および 4 つの点のうちの任意の 2 つによって形成される (有向) 線が平面の一方の側にあるか他方の側にあるかも決定します。他の2人が形成するライン。

簡単に言えば、行列式を実行すると、数学がより堅牢になります。注意を払えば、最初は行列式を実行しなかったアルゴリズムを通常、決定式を実行するアルゴリズムに変換できます。または、紙を読むだけでもかまいません。