7

マーチング キューブ、デュアル マーチング キューブ、適応型マーチング キューブを C# で実装しましたが、目的のためにデュアル コンターリングが必要であることがわかりました。二重輪郭に関するすべての作品を読み、二重輪郭自体の核心である二次誤差関数 (QEF) の最小化以外はすべて理解しました。

現在、その単一の頂点 (3 ～ 6 エッジ) を共有するすべての edgePoints 間の平均を見つけるだけで、内部ボクセルの頂点位置を計算していますが、うまく機能しますが、適切な場所に内部頂点が作成されないことは明らかです。

これが私が作成しようとしているコードです。どんな助けでも大歓迎です

/// <summary>
    /// ORIGINAL WORK: Dual Contouring of Hermite Data by Tao Ju (remember me of a MechCommander 2 character)
    /// 2.3 Representing and minimizing QEFs
    /// The function E[x] can be expressed as the inner
    /// product (Ax-b)T (Ax-b) where A is a matrix whose rows are the
    /// normals ni and b is a vector whose entries are ni*pi.  <------------ (dot product?)>
    /// Typically, the quadratic function E[x] is expanded into the form
    /// E[x] = xT AT Ax - 2xT AT b + bT b (2)
    /// where the matrix AT A is a symmetric 3x3 matrix, AT b is a column
    /// vector of length three and bT b is a scalar. The advantage of this expansion
    /// is that only the matrices AT A, AT b and bT b need be stored
    /// (10 floats), as opposed to storing the matrices A and b. Furthermore,
    /// a minimizing value ˆ x for E[x] can be computed by solving
    /// the normal equations AT Aˆ x = AT b.
    /// </summary>
    public Vector3 GetMinimumError(Vector3 p0, Vector3 p1, Vector3 p2, Vector3 n0, Vector3 n1, Vector3 n2)
    {
        //so, here we are. I'm creating a vector to store the final value.
        Vector3 position = Vector3.Zero;

        //Values of b are supposed to b (:P) three floats. The only way i know to find a float value
        //by multiplying 2 vectors is to use dot product.
        Vector3 b = new Vector3(
               Vector3.Dot(p0, n0),
               Vector3.Dot(p1, n1),
               Vector3.Dot(p2, n2));

        //What the transpose of a vector is supposed to be?
        //I don't know, but i think should be the vector itself :)
        float bTb = Vector3.Dot(b, b); 

        //i create a square matrix 3x3, so i can use c# matrix transformation libraries.
        //i know i will probably have to build bigger matrix later on, but it should fit for now
        Matrix A = new Matrix(
            n0.X, n0.Y, n0.Z, 0,
            n1.X, n1.Y, n1.Z, 0,
            n2.X, n2.Y, n2.Z, 0,
            0, 0, 0, 0);

        //easy
        Matrix AT = Matrix.Transpose(A);

        //EASY
        Matrix ATA = Matrix.Multiply(AT, A);

        //Another intuition. Hope makes sense...
        Vector3 ATb = Vector3.Transform(b, AT);

        //...
        // some cool stuff about solving
        // the normal equations AT Aˆ x = AT b
        //...

        return position; //profit!
    }
4

2 に答える 2

8

QEF を理解するのはかなり難しいです。うまくいけば、私は助けることができます. 二重輪郭法は、各交点で「エルミート」データを計算します。つまり、ボクセルのエッジに作成された各点で、サーフェスの法線が既知です。点と法線を使用して、平面の方程式を計算できます。

QEF は、ボクセルの内部点からボクセルに関連付けられた各平面までの距離の 2 乗の合計です。以下は、QEF を計算するための疑似コードです。

double get_QEF(Point3d point, Voxel3d voxel) 
{ 
    double QEF = 0.0; 
    foreach(plane in voxel.planes) 
    { 
        double dist_to_plane = plane.distance(point); 
        QEF += dist_to_plane*dist_to_plane; 
    } 
    return(QEF); 
}

目標は、QEF を最小化するボクセル内のポイントを選択することです。文献では、Grahm-Schmidt プロセスを使用して最適なポイントを見つけることを提案していますが、これは複雑になる可能性があり、ボクセルの外側にあるポイントになる可能性もあります。

別のオプション (ハックっぽい) は、ボクセル内にポイントのグリッドを作成し、それぞれの QEF を計算し、最も低いものを選択することです。グリッドが細かいほど、最適なポイントに近づきますが、計算。

于 2015-03-13T18:24:10.767 に答える
3

私の現在のデュアルコンターリングの実装では、QEF を解決するための非常に簡単な方法を使用しています。QEF は本質的に最小二乗近似であるため、QEF を計算する最も簡単な方法は疑似逆数を計算することであることがわかりました。この擬似逆行列は、言語の代数ライブラリを使用して計算できます。

これは私が使用しているコードです:

    public static Vector<float> CalculateCubeQEF(Vector3[] normals, Vector3[] positions, Vector3 meanPoint)
    {
        var A = DenseMatrix.OfRowArrays(normals.Select(e => new[] { e.X, e.Y, e.Z }).ToArray());
        var b = DenseVector.OfArray(normals.Zip(positions.Select(p => p - meanPoint), Vector3.Dot).ToArray());

        var pseudo = PseudoInverse(A);
        var leastsquares = pseudo.Multiply(b);

        return leastsquares + DenseVector.OfArray(new[] { meanPoint.X, meanPoint.Y, meanPoint.Z });
    }

関数の入力は交点と法線であり、meanPoint は指定された交点の平均です。

数学の要約: この関数は、交点と法線によって定義されるすべての平面の交点にある点を計算します。これには正確な解がないため、最小二乗近似が計算され、「最も間違っていない」点が検出されます。さらに、平均点が原点になるように交点が「移動」されます。これにより、QEF に複数の解がある場合に、平均点に最も近い解が選択されるようになります。

于 2015-07-02T15:08:39.343 に答える