1

GJKアルゴリズムを実装しようとしていますが、すぐに行き詰まりました。

問題は、O（n ^ 2）ではないサポート関数を実装することです。

現在、ミンコフスキーの完全な差を計算しているので、GJKアルゴリズムを実行しても意味がありません。（またはそれは？）

サポート関数とは、指定された方向に最も遠いミンコフスキー差の点を返す関数です。私の現在の実装のように、これはO（n ^ 2）であってはならないと思います。

4

2 に答える 2

5

最も単純なサポート関数は 0(n) です。つまり、ある方向に最適な内積を見つけます。

    public Vector3 MaxPointAlongDirection(Vector3 directionToMove)
    {
        float max = float.NegativeInfinity;
        int index = 0;
        for (int i = 0; i < vertices.Length; i++)
        {
            float dot = Vector3.Dot(vertices[i], directionToMove);
            if (dot > max)
            {
                max = dot;
                index = i;
            }
        }
        return vertices[index];
    }

三角形化された凸包のもう 1 つの高速なアプローチは、ヒル クライミングです。1 すべてのポイントの隣接情報を計算します。2 任意の点から始めて、隣接するすべての点の最適な内積を見つけます。3 この新しい点を現在の点にします ステップ 2 を繰り返します

または Dobkin-Kirkpatrick 階層。

オブジェクトが回転している場合、directionToMove ベクトルは、回転したオブジェクトを基準にして変換できます (まだ作業中です)。したがって、すべてのポイントを回転する必要はありません。

于 2010-05-04T21:43:08.743 に答える
3

GJK は、原点に最も近いミンコフスキー和の点を示します。他に何も動かなければ、ミンコフスキー和は同じになり、最近点も同じになります。

通常、人々は体が自由に動いたり回転したりできると思い込んでいます。その場合、結果は常に変化します。

翻訳の場合、ミンコフスキーの違いを再利用できるはずです。ローテーションの場合は、再計算する必要があります。これは、多くのリアルタイム アプリケーションにとって問題となります。

アルゴリズムがミンコフスキー差をサポート関数によって暗黙的に使用する場合、何も再計算する必要はありません。それが支援機能を利用するメリットの一つです。

一部の形状は、サポート機能が非常に簡単な形状をしています。その場合、何も計算する必要はありません。それはもう一つの利点です。最後に、サポート関数を追加して、ミンコフスキー和のサポート関数を作成できます。プリミティブを使用して形状のファミリを形成し、GJK にそれらを処理させることができるため、優れたプロパティです。

平面上に n 点の凸包がある場合、サポート関数は、包ポリゴンのエッジを見つけて法線ベクトルの角度をソートすることで事前に計算できます。ハルのすべての頂点には 2 つの法線があります。順番に進み、方向がこれらの法線ベクトルの間にあるかどうかを確認してください。それはあなたにO（n）を与えるでしょう。

比較順序を変更して O(log(n)) にすることもできます。

于 2010-03-16T21:31:38.897 に答える