CODEWITHSUNDEEP
unity-game-engine3dtriangulation
Marko Taht
Marko Taht

Reputation: 1526

Triangulate set of points on arbitrary plane in 3D space

I have a set of points in 3D space. With maximum error of 10^-5 i can place a plane through them (error is the distance from point to plane).

Is there a way to triangulate these points on this arbitrary plane? I have tried Bowyer-Watson but this only works when the error is 0. Anything else and it wont triangulate or i wont get a good triangulation(overlapping triangles).

Edit

I think i found the problem. At certain angles the bowyer watson algorithm wont work because my calculation of the circumcenter is off. How can i calculate the circumcenter of a triangle in 3D?

Upvotes: 0

Views: 593

Answers (1)

Marko Taht
Marko Taht

Reputation: 1526

Since i know the points on the plane i can calculate a vector. This vector lies on the plane. Next i calculate the center of mass of the points.

Using the vector and center of mass i can create a large triangle on the plane

        Vertex p1 = new Vertex(dir * 3000 + center);
        Vertex p2 = new Vertex(Quaternion.AngleAxis(120, plane.normal) * dir * 3000 + center);
        Vertex p3 = new Vertex(Quaternion.AngleAxis(240, plane.normal) * dir * 3000 + center);

Now that i have the enclosing triangle i can just use Bowyer-Watson. For circumcenter in 3D i use:

Vector3 ac = p3 - p1;
    Vector3 ab = p2 - p1;
    Vector3 abXac = Vector3.Cross(ab, ac);

    circumceter = p1 + (Vector3.Cross(abXac, ab) * ac.sqrMagnitude + Vector3.Cross(ac, abXac) * ab.sqrMagnitude) / (2 * abXac.sqrMagnitude);

And now i have a triangulated set of points on an arbitrary plane in 3D.

Upvotes: 1

Related Questions