CODEWITHSUNDEEP
c#algorithmlinear-algebrasvdalglib
Fat-chunk
Fat-chunk

Reputation: 371

Fitting a plane to a set of points using Singular Value Decomposition

I am trying to fit a plane to a set of points in 3D space. I originally tried an exhaustive least squares fit but this turned out to be way too slow. I read that the most efficient solution would be to perform singular value decompositon.

The maths for this is beyond me, but I have found a bunch of resources to try get this to work.

According to the answer in this post, I need to compute the centroid of the points, subtract the centroid from all of the points, put them into a 3xN matrix and perform SVD. I then take the left singular vector as the normal for the plane.

So far so good.

I found a C# maths library called alglib which has a function for SVD. The definition of the algorithm can be found here. This is where I am having issues, as it requires two more matrices as inputs in addition to the data points matrix, and I don't really understand what to put inside them. I ran this code regardless:

Vector3 centroid = getCentroid(planeVerts);
    double[,] dataMat = substractCentroid(planeVerts, centroid);
    double[] w = new double[3];
    double[,] u = new double[1,1];
    double[,] t = new double[1, 1];

    bool a = alglib.svd.rmatrixsvd(dataMat, 3, planeVerts.Length, 0, 0, 2, ref w, ref u, ref t);

    Vector3 planeNorm = new Vector3((float) w[0], (float) w[1], (float) w[2]);

So in theory I thought "w" would contain my plane normal, but unfortunately it doesn't (I visualised it in Unity3D and it was at the wrong angle). The "u" and "t" matrices are the ones which confound me, and I don't really know what I should be setting them to.

The detailed API for the rmatrixsvd function can be found here.

Are there any maths or algorithm veterans who could share their knowledge on this matter? I need to use C# as my project is in Unity3D. I'll be happy to provide more info if needed.

Upvotes: 2

Views: 3315

Answers (1)

vrume21
vrume21

Reputation: 551

Looking at the documentation, it looks like w will contain your singular values, U will contain the left singular vectors, and V will contain the right singular vectors. Since dataMat is 3xN, U should be 3x3 and V should be NxN. And as you say you need the left singular vector, set UNeeded=1 and just take the first column of U. As you don't need the right singular vectors, you can also set VNeeded=0.

Upvotes: 2

Related Questions