Polygon Triangulation Failure

Eddie Cameron

2 years ago
updated 2 years ago

The ear clipping triangulation fails for this `I` shape. It looks like that at some point while clipping vertices, it ends up with 3 neighbours that are allllmost colinear, and marks them as reflex when they should be convex. If I decrease the fudge value for the reflex calculation it all works fine, but I worry that'll come back to haunt me.

I'm sure it's hard to nail down all these degenerate shapes so I'm going to try find a workaround (all my shapes are of similar scale, so maybe messing with the fudge will be ok) but thought you'd enjoy a "fun" test case.

Points are at the bottom of this debug log:

https://gist.github.com/EddieCameron/0031335ab4a0fb3486511c3865ca4e52

Cheers!

Reporting a bug? please specify Unity version:

2021.2.9

Reporting a bug? please specify Shapes version:

4.2.1

Reporting a bug? please specify Render Pipeline:

URP

Replies 2

Oldest first
Newest first Oldest first

2 years ago

I ended up fixing by scaling the input and converting to integers before running the calculations without any fudging (like ClipperLib: https://github.com/AngusJohnson/Clipper2).

Would be a bit hard to make general since you need to choose an appropriate scale, but good enough for me. Can send code over if you like but it's essentially copypasting the `GenPolygonMesh` function and swapping all the floats for ints/longs

Reply Link

Freya Holmér creator

this specific point set is kind of a surgically precise edge case~

because these three vertices at the top and the bottom happen to be very close to collinear

one thing you can do is to cycle the indices to affect the starting point of the triangulation using the context menu. Most cases triangulate it properly, without changing the points!

As for integer coordinates, I've considered it, but as usual it's a tradeoff between performance and accuracy. Pretty much everyone will want to assign floating point numbers, but ideally I'd use rational vectors, but, it will be hard for people to use >.>

I might be able to tweak the algorithm to make it more stable