godot: Delaunay2D fails when trying to triangulate certain set of points
Godot version
3.5.1
System information
Windows10, Ryzen 5600
Issue description
Self expalnatory, calling Delaunay2D on a set of points fails to return a triangulation. This triangulation can exist in matlab, so most likely godot bug.
Steps to reproduce
Make an array of the points ill show below, calling the Geometry.Delaunay2D(list) returns an empty int array.
Minimal reproduction project
List<Vector2> testList = new List<Vector2>();
testList.Add(new Vector2(0,0));
testList.Add(new Vector2(-13.3f,0));
testList.Add(new Vector2(-6.5f,-0.15f));
testList.Add(new Vector2(-6.8f,-0.15f));
GD.Print(Geometry.TriangulateDelaunay2d(testList.ToArray()).Count());
Use this or the equivalent in GDScript and you get 0 printed
About this issue
- Original URL
- State: open
- Created a year ago
- Reactions: 1
- Comments: 24 (22 by maintainers)
So the issue seems to be the algorithm itself, it’s not guaranteed to returna a proper Delaunay triangulation for the given set of
Npoints. Currently used algorithm starts with an arbitrarily choosen bounding triangle and keeps subdividing until a proper triangulation is found for such set ofN + 3points (originalNpoints and3bounding vertices). At the end all triangles including at least 1 bounding vertex are discarded from the final result. The issue is: the remaining triangles are not guaranteed to form a valid triangulation of the original set of N points. At worst no triangles will be left, like in the MRP (before the removal algorithm ends with 9 triangles but all of them are discarded).Possibly it fails only for cocircular points (all lying on the same circle), like the 4 points from the MRP. But not sure about it.
Anyway, the algorithm needs tweaking/rewrite. I’ll look into it.
Further evidence to indicate that the problem is with a bounding triangle that is too small. The circle at the top is the circumcircle of three of the points provided by @Kemikal1 [(0,0), (-6.5,0.15), (-13.3,0)]. The blue triangle is the bounding triangle created by the algorithm. Notice that the vertex of the bounding triangle is found within the circumcircle of the points. I believe this is why the algorithm is breaking down.
As noted by @AThousandShips , if the y-values are positive, the Delaunay triangulation does work, but I think this is because it effectively flips the circumcircle (circle in red) which then no longer contains any bounding triangle vertices.
See the Desmos graph.
I’m still not sure the best way to fix this algorithm. In the stack exchange forum post I mentioned above, it looks like you can theoretically set the bounding triangle to an infinite size, but I’m pretty sure it would involve some more maths to handle situations when some circumcircles are consequently infinite. I’m surprised I don’t see more details about this problem with the Bowyer Watson algorithm other places online.
I’m also wondering if we could add a check prior to the circumcircle check on line 116, such that if all three points of the considered triangle are non-bounding-triangle vertices, and if the current point i is, then continue. I haven’t had a chance to test this hypothesis yet.
I’ll set it to 4.3 as a reminder for you, @kleonc 😛 But if this is not a priority, we should probably put it in 4.x, or remove it entirely until the fix becomes available.
I just created a pull request for a bug I initially assumed to be the same as the one discussed here. But after trying the problematic example provided in this issue, I realized that my bug was actually different. In some further testing, it looks like the Bowyer Watson algorithm has problems with nearly colinear points, and thus the bounding triangle needs to potentially be infinite to handle these scenarios. This is because the circumscribed circle grows rapidly as the points approach a line. Thus, the bounding triangle technically needs to be large enough to avoid having one of its vertices enclosed by that circle.
I tried increasing the multiplier when creating the bounding triangle from 16 to 100, and I believe I was able to reduce the non-zero y-coordinates in the example in this issue down to -0.045 while still getting valid results. I’m running out of time to work on this right now, but I’m planning on creating a graphic in desmos later tonight to show the problem in more detail.
I don’t have the time to investigate this but my blind guess would be that this is either an unsolved bug in Godot 3 cause the Delaunay code in Godot 4 is slightly different, or this is just another precision issues as there are a lot of float ops in the Delaunay function. Also a lot of length_squared() and distance_squared_to() checks which are fast but not anywhere as precise as e.g. MathLab.
This isx how it looks in matlab
@Kemikal1 The fact you can triangulate this in another Delaunay implementation is relevant and should be up there in the OP
Creating an infinite super triangle will most definitely fix this issue. I encountered this same issue while implementing Bowyer-Watson in C++. You might fix this specific case by scaling the super triangle more, but you’ll just find more cases where this breaks down as 3 points approach collinearity.
Not sure if it is frowned upon to link my own code, but for reference you can see how I dealt with the edge cases introduced by an infinite super triangle here. Mostly it involves detecting whether a new point is inside a half-plane or not, but this will incur some performance hit due to more branching.
Assigned myself to this issue to not forget about it again (I remember getting into it after https://github.com/godotengine/godot/issues/77279#issuecomment-1560147702 but I guess I focused on something else later and forgot about this issue). I’m not getting straight into it right now so if anyone else wants to do so - feel free to do so. Setting milestone to 4.2 as a kinda deadline/reminder for myself.
Note that this doesn’t happen if the y-values are positive for this specific case, indicating this is a strange edge case
Be aware that in Godot y values go the other way, so the plot is upside down, and also auto scaled meaning it ignores the significantly stretched shape, reason I’m pointing this out is that this plot doesn’t give a proper idea of how the shape actually looks
Then that is a bug likely, sorry didn’t know you had verified it was correct