Search code examples
c#unity-game-enginepoint-cloudstriangulation3d-reconstruction

Issues calculating circumcenter of a tetrahedron


I'm trying to calculate the circumcenter of a tetrahedron using C# and I'm using the formula supplied on Wikipedia to accomplish this.

circumcenter formula

Here's what I tried in C#. It seems that the calculated point is always significantly misaligned. I checked my implementation and everything seems to be calculating correctly. circumcenter is a Unity Vector3.

//calculate super tetrahedron
Vector3[] superT = {
    new Vector3(minMaxAvg.x - 2 * deltaMax, minMaxAvg.y - deltaMax    , minMaxAvg.z - deltaMax    ),
    new Vector3(minMaxAvg.x + 2 * deltaMax, minMaxAvg.y - deltaMax    , minMaxAvg.z - deltaMax    ),
    new Vector3(minMaxAvg.x               , minMaxAvg.y + 2 * deltaMax, minMaxAvg.z - deltaMax    ),
    new Vector3(minMaxAvg.x               , minMaxAvg.y               , minMaxAvg.z + 2 * deltaMax)
};

Vector3 v1 = superT[1] - superT[0];
Vector3 v2 = superT[2] - superT[0];
Vector3 v3 = superT[3] - superT[0];
        
Matrix3x3 mA = new Matrix3x3(v1, v2, v3);
float p1Dot = superT[0].Dot(superT[0]);
Vector3 B = new Vector3(superT[1].Dot(superT[1]) - p1Dot, superT[2].Dot(superT[2]) - p1Dot, superT[3].Dot(superT[3]) - p1Dot) * 0.5f;

circumcenter = mA.Invert().MultiplyPoint(B);

I'm using a custom Matrix3x3 class:

public class Matrix3x3 {
    public Vector3 c1, c2, c3;

    public Matrix3x3() {
        c1 = new Vector3();
        c2 = new Vector3();
        c3 = new Vector3();
    }

    public Matrix3x3(Vector3 v1, Vector3 v2, Vector3 v3) {
        this.c1 = v1;
        this.c2 = v2;
        this.c3 = v3;
    }

    public Vector3 MultiplyPoint(Vector3 p) {
        Vector3 res = new Vector3();
        res.x = c1.x * p.x + c2.x * p.y + c3.x * p.z;
        res.y = c1.y * p.x + c2.y * p.y + c3.y * p.z;
        res.z = c1.z * p.x + c2.z * p.y + c3.z * p.z;

        return res;
    }

    public Matrix3x3 Invert() {
        Matrix3x3 res = new Matrix3x3();
        float invdet = 1.0f / Determinant();

        res.Set(0, 0, (Get(1, 1) * Get(2, 2) - Get(2, 1) * Get(1, 2)) * invdet);
        res.Set(0, 1, (Get(0, 2) * Get(2, 1) - Get(0, 1) * Get(2, 2)) * invdet);
        res.Set(0, 2, (Get(0, 1) * Get(1, 2) - Get(0, 2) * Get(1, 1)) * invdet);
        res.Set(1, 0, (Get(1, 2) * Get(2, 0) - Get(1, 0) * Get(2, 2)) * invdet);
        res.Set(1, 1, (Get(0, 0) * Get(2, 2) - Get(0, 2) * Get(2, 0)) * invdet);
        res.Set(1, 2, (Get(1, 0) * Get(0, 2) - Get(0, 0) * Get(1, 2)) * invdet);
        res.Set(2, 0, (Get(1, 0) * Get(2, 1) - Get(2, 0) * Get(1, 1)) * invdet);
        res.Set(2, 1, (Get(2, 0) * Get(0, 1) - Get(0, 0) * Get(2, 1)) * invdet);
        res.Set(2, 2, (Get(0, 0) * Get(1, 1) - Get(1, 0) * Get(0, 1)) * invdet);

        return res;
    }

    public float Determinant() {
        return  Get(0, 0) * (Get(1, 1) * Get(2, 2) - Get(2, 1) * Get(1, 2)) -
                Get(0, 1) * (Get(1, 0) * Get(2, 2) - Get(1, 2) * Get(2, 0)) +
                Get(0, 2) * (Get(1, 0) * Get(2, 1) - Get(1, 1) * Get(2, 0));
    }

And I have a little helper function to calculate the dot product of a Vector3 in Unity:

public static float Dot(this Vector3 v, Vector3 other) {
    return v.x * other.x + v.y * other.y + v.z * other.z;
}

Here's what the result looks like for now:

result

The red dot should have an equal distance to all points of the tetrahedron, but it is clear that this is not the case from the image.

Please can someone point me in the right direction. I've been fighting with this for hours now.


Solution

  • I solved it!

    Took me long enough.

    The solution was to transpose the matrix I made. Or in other words: I inserted the vectors as rows instead of columns.

    This was confusing to me as I thought the formula required the vectors to be inserted as columns, since there's a Transpose symbol in the corner.

    Well. I'm done here.