Voronoi / Delaunay Graph - Triangle Circumcenter error

Question

I have written a Delaunay Graph script that given a set of points (voronoi cell/region) will generate the Delaunay triangles with their edges. Considering that the Voronoi diagram is complimentary to the Delaunay graph, I can infer the Voronoi regions, edges and corners once the Delaunay graph is complete.

I had previously implemented this in 2D without any troubles and the results were flawless in all of the diagrams I generated. However, I have since tried to implement this in 3D and have now encountered issues.

My implementation of this appears to work fine in 99.9% of cases which leads me to believe that perhaps floating point/rounding errors may be the problem or (more likely) my understanding of the code used to determine the circumcenter is incorrect.

I have based the following implementation on this answer from How do I find the circumcenter of a triangle in 3D?

public static Vector3 Circumcenter(Vector3 a, Vector3 b, Vector3 c)
{
    Vector3 ab = (b - a);
    Vector3 ac = (c - a);

    Vector3 abXac = Vector3.Cross(ab, ac);

    Vector3 i = (ab.sqrMagnitude * ac);
    Vector3 j = (ac.sqrMagnitude * ab);
    Vector3 k = Vector3.Cross((i - j), abXac);

    return (a + (k * (0.5f / abXac.sqrMagnitude)));
}

The screenshots below are of two separate graphs both generated by creating the Voronoi cells/regions in nested for-loop's before attempting to solve the graph. I have tried creating the points randomly, hard coding them, setting different values along the Y-axis or having them all set to a specific constant on the Y-axis, all of which exhibit the same behaviour.

These examples do not use Lloyd relaxation but for the sake of completion, running the solver over several iterations also produces incorrect results.

I have been trying to debug this for weeks now and cannot for the life of me understand why this does not work. My understanding of the math is fairly solid but I really can't begin to narrow this down to resolve the issue.

It would appear that when solving the graph, the circumcenter for three of the nodes is sometimes incorrect (or so i'm lead to believe from the visual output). However, the Delaunay representation appears to be correct which leads to even more confusion on my part.

In the above images, the lines and points represent:

• Red point: Voronio cell/region.
• Black Line: Delaunay Edge.
• Blue point: Voronoi Corner.
• White Line: Voronoi Edge.

The Voronoi graph is determined by creating a Delaunay edge between two nodes and first setting the start point of a Voronoi edge. Once the graph finds another Delaunay triangle along this exact same edge between two nodes, the end point of the Voronoi edge is then set completing this edge entirely.

As you can see in the both images, the Delaunay representation of the graph is correct. However, again in both images, the Voronoi representation has incorrect corners which then leads to incorrect edges.

If anyone can shed any light on this, or point me in the right direction, that would be greatly appreciated.

Answer 1

It's hard to tell without source code but it looks like some triangles are overlapping one another:

I'm guessing another issue is that segment A-B is not always considered the same as segment B-A and you end up with internally 2 different edges sharing the same points.

Because the edge looks twice as thick on your screenshot Red & Blue are probably 2 edges that should be 1, same with Green and Purple:

It could be a bad triangle winding with one edge going backward.

To debug this I recommend printing a log and analyzing it by hand.

First you need to identify the exact edge/vertex indices that are causing issues, then recompile your program to print debug information whenever processing those particular edges/vertices.

You'll be able to gradually narrow down where the error occurs.