二重等高線と二次誤差関数

Question

私は、私の目的のために二重輪郭線が必要であることを知るために、マーチングキューブ、デュアルマーチングキューブ、適応マーチングキューブをC＃で実装しました。 私は二重輪郭線に関するすべての作業を読みましたが、二重輪郭線自体のコアを除いて、二次輪郭関数（QEF）を最小限に抑えています。

今は、その単一の頂点（3〜6辺）を共有するすべてのedgePoint間の平均を見つけるだけで内部ボクセルの頂点位置を計算していますが、それはうまく機能しますが、明らかに内部頂点を作成しません適切な場所。

ここに私が作成しようとしているコードがあります。どんな助けでも非常に高く評価されます

/// <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! 
    } 

Answer 1

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を計算し、最小のものを選択すると、グリッドが細かくなるほど最適な点に近づきます計算時間は長くなります。

Answer 2

私の現在の実装では、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が与えられたintersectoin点の平均である：

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

算術の要約：この関数は、交点と法線によって定義されるすべての平面の交点上にある点を計算します。これには正確な解法がないため、最小自乗近似が計算され、「最も間違っていない」点が見つかる。さらに、交点は、平均点が原点となるように「移動」されます。これは、QEFに対する複数の解が存在する場合、平均点に最も近い解が選択されることを保証する。