3

3D環境で三角形と三角形の交差テストを理解して実装するためのチュートリアルまたはガイドがあるかどうかを知りたいです。（交差点が発生した場所を正確に知る必要はありませんが、交差点が発生したことだけを知る必要があります）

私は理論的なpdfに従ってそれを実装するつもりでしたが、私はかなり立ち往生しています

  1. 三角形2の平面方程式を計算します。
  2. 三角形1のすべての点が同じ側にある場合は、取るに足らないものとして拒否します。
  3. 三角形1の平面方程式を計算します。
  4. 三角形2のすべての点が同じ側にある場合は、取るに足らないものとして拒否します。
  5. 交線を計算し、最大軸に投影します。
  6. 各三角形の間隔を計算します。
  7. 間隔を交差させます。

このガイドのポイント5。何を求めているのかよくわかりません（5、6、7すべて）。XD

私は数学の知識があまりないので（まあ、大学でのいくつかの試験で私に与えられたものは知っています（私は生のプログラマーXDです））、できるだけシンプルにしてください。：D（グーグルで検索しようとしましたが、ほとんどのリンクは、私が本当に知りたくない、理解できない数式でいっぱいの4〜5ページを指しています。）

助けてくれてありがとう

4

5 に答える 5

12

あなたが言った：

3D環境で三角形と三角形の交差テストを理解して実装するためのチュートリアルまたはガイドがあるかどうかを知りたいです。

そしてあなたは言った：

ほとんどのリンクは、私が本当に知りたくない数式でいっぱいの4〜5ページを指しています。

これらの2つのステートメントは完全に矛盾していることに注意してください。それで、それはどれですか？三角形と三角形の交差がどのように機能するかを理解したいですか、それとも単に機能する実装が必要なのに理解できませんか？

それらすべてのウェブページが不必要な数学でいっぱいであるというわけではありません。交差アルゴリズムがどのように機能するかを理解するには、すべての計算が必要です。最初から始めて、すべてがどのように機能するかを学びます。

ステップ5、6、7は、単語の意味がわかれば簡単に理解できます。交線は、2つの平面の交点によって作られる線です。各三角形は平面に​​あります。3つのケースがあります：

  • 平面は平行であり、交差していません。三角形は明らかに交差していません。
  • 平面は同じ平面です。三角形が一致する場合と一致しない場合があります。
  • 平面は、線で交わる2つの異なる平面です。三角形が交差する場合、それらは明らかにその線上で交差する必要があります。

3番目のケースにいると仮定します。最初の三角形に含まれる交線のセグメントを計算します。2番目の三角形にある交線のセグメントを計算します。問題は、「これらのセグメントは重複していますか？」です。

セグメントを便利な軸に投影し、その軸の線分が重なっているかどうかを確認することで、これを解決できます。基本的に、これは次のように機能します。線分の影が軸に当たるように、線分に光を当てていると想像してください。軸上の影が交差する場合は、線分が交差する必要があります。軸上の影の間にギャップがある場合は、明らかに線分間にギャップがなければならないため、三角形は交差しません。

これがどのように機能するかを理解したい場合は、これらすべてを理解する必要があるという事実を回避することはできません-平面がどのように交差し、軸への投影がどのように機能するかを理解するすべての代数。それはすべて必要です。そして、それらはすべて基本的な構成要素であり、そこからより複雑な変換や投影などが構築されます。さらに進んでいきたい場合は、基本を完全に理解してください。

于 2009-12-14T21:51:53.337 に答える
2

私の答えは簡単です...この問題は任意の座標系では難しいので、問題を簡単にするものに変更してください。xnaのMatrixクラスには、すべての頂点で有用な変換を作成するために使用できるCreateLookAt関数があります。

次の例は最適化されておらず、ソリューションを理解するためだけに書かれています。例外とそれに対応するifステートメントは、いくつかのベクトル変換とともにすべて削除できます。 

    public static bool CheckColision(Vector3 t1a, Vector3 t1b, Vector3 t1c, Vector3 t2a, Vector3 t2b, Vector3 t2c)
    {//rotates each edge of the first triangle to the Z axis and checks the second triangle against it then repeats with the second one against the first, and lastly checks to see if all points of the second triangle are on the same side as the first
        if(! CheckColisionLookAt(t1a, t1b, t1c, t2a, t2b, t2c))
            return false;
        if (!CheckColisionLookAt(t1b, t1c, t1a, t2a, t2b, t2c))
            return false;
        if (!CheckColisionLookAt(t1c, t1a, t1b, t2a, t2b, t2c))
            return false;

        if (!CheckColisionLookAt(t2a, t2b, t2c, t1a, t1b, t1c))
            return false;
        if (!CheckColisionLookAt(t2b, t2c, t2a, t1a, t1b, t1c))
            return false;
        if (!CheckColisionLookAt(t2c, t2a, t2b, t1a, t1b, t1c))
            return false;

        return CheckColisionAllOnOneSide(t1a, t1b, t1c, t2a, t2b, t2c);
    }

    public static bool CheckColisionAllOnOneSide(Vector3 t1a, Vector3 t1b, Vector3 t1c, Vector3 t2a, Vector3 t2b, Vector3 t2c)
    {//simply performs a transformation to check if all points on one triangle are on the same side of the other triangle
        Matrix m = Matrix.CreateLookAt(t1a, t1b, t1c - t1a);
        t2a = Vector3.Transform(t2a, m);
        t2b = Vector3.Transform(t2b, m);
        t2c = Vector3.Transform(t2c, m);
        if (t2a.X < 0 && t2b.X < 0 && t2c.X < 0)
            return false;
        if (0 < t2a.X && 0 < t2b.X && 0 < t2c.X)
            return false;
        return true;
    }

    public static bool CheckColisionLookAt(Vector3 t1a, Vector3 t1b, Vector3 t1c, Vector3 t2a, Vector3 t2b, Vector3 t2c)
    {//performs a transformation and checks if all points of the one triangle are under the other triangle after the transformation

        Matrix m = Matrix.CreateLookAt(t1a, t1b, t1c - t1a);
        t1a = Vector3.Transform(t1a, m);//  (0,     0,      0)
        if ( ZERRO < Math.Abs(t1a.X)|| ZERRO < Math.Abs(t1a.Y) || ZERRO < Math.Abs(t1a.Z))
            throw new Exception();
        t1b = Vector3.Transform(t1b, m);//  (0,     0,      maxZ)
        if (ZERRO < Math.Abs(t1a.X) || ZERRO < Math.Abs(t1a.Y))
            throw new Exception();
        t1c = Vector3.Transform(t1c, m);//  (0,     maxY,   someZ)
        if (ZERRO < Math.Abs(t1a.X))
            throw new Exception();
        t2a = Vector3.Transform(t2a, m);
        t2b = Vector3.Transform(t2b, m);
        t2c = Vector3.Transform(t2c, m);
        if (t2a.Y < 0 && t2b.Y < 0 && t2c.Y < 0)
            return false;
        return true;
    }
于 2011-02-03T20:51:57.770 に答える
1

これは、多くの交差点への参照を含むWebサイトです。

リアルタイムレンダリングオブジェクト/オブジェクト交差ページ

Tri/Triのリストは次のとおりです。

Möllerjgt2（2） ;
jgt 2（4）を開催しました;
GTweb ;
Möller ;
GPG p.393;
GTCG p.539;
TGS ;
RTCD p.155,172;
シェンjgt8（1） ;
Guigue jgt 8（1） ;
SoftSurfer ;
リアルタイムレンダリング、第2版p.590;
リアルタイムレンダリング、第3版p.757

于 2009-12-14T20:32:52.623 に答える
1

三角形の頂点のx、y座標があると思います。例えば。
三角形Aの場合：
1。側面A1：xa1、ya1 2.側面A2：xa2、ya2 3.側面A3：xa3、三角形Bの場合：
1。側面B1：xb1、yb1 2.側面B2：xb2、yb23。サイドB3：xb3、yb3

それらの線の任意の組み合わせが交差する場合、三角形は交差します。A1がB1またはB2またはB3と交差する場合、A2がB1またはB2またはB3と交差する場合、またはA3がB1またはB2またはB3と交差する場合を意味します。

したがって、2本の線が交差するかどうかを検出するアルゴリズムが必要です。これが私が見つけた最も簡単な例です：http：//www.mathopenref.com/coordintersection.html

于 2009-12-14T20:42:31.730 に答える
1

あなたが投稿した方法は、分離軸定理に基づいて、凸多角形が交差するかどうかを検出するために、このアルゴリズムに似たものを使用しているように見えます。理解するのはそれほど難しいことではありません。

分離軸と呼ばれる線が2つのポリゴンの間に描画できる場合、それらは交差しません。各ポリゴンの各エッジは、候補の分離軸です。ポリゴンはその軸に垂直なベクトルに投影され、1D範囲のオーバーラップがテストされます。1Dオーバーラップがない場合、現在のエッジは分離軸であり、2つのポリゴンは交差しません。1Dオーバーラップがある場合、すべての候補エッジがテストされるまで結果は決定的ではありません。テストされた時点で、2つのポリゴンは交差していると結論付けられます。2つのポリゴンがエッジを共有できることに注意してください。

于 2009-12-14T22:03:49.970 に答える