Add polygon test showing bad tessellation result + fix #824
Conversation
|
Indeed, this is a valid polygon and a good test case. Turns out a couple of valid ears were being rejected (positive cost) due to verts near their tip. I've improved their neighbor checking to get correct costs, so now everything proceeds properly. |
Codecov ReportAll modified and coverable lines are covered by tests ✅
Additional details and impacted files@@ Coverage Diff @@
## master #824 +/- ##
==========================================
- Coverage 91.84% 89.23% -2.61%
==========================================
Files 37 61 +24
Lines 4976 8482 +3506
Branches 0 932 +932
==========================================
+ Hits 4570 7569 +2999
- Misses 406 913 +507 ☔ View full report in Codecov by Sentry. |
|
Awesome - tested and works perfectly also with extra torture: |
|
@elalish I've got another one. It's a bit time consuming to manually trim polygons to minimal examples. Do you have a good/preferred way of providing data-driven polygon tests? |
|
If you compile with |
|
After a while I figured out it's |
|
Oh, oops - you're right. |
I believe this shows that a relatively complex "branchy" polygon with a single triangular hole causes
Triangulate()to emit some pretty funky triangles.This polygons is a very slimmed down version of the polygon emitted by https://github.com/openscad/openscad/blob/master/examples/Advanced/module_recursion.scad
The polygon itself is a result or a union of a large number of 2D rectangles using Clipper V1.
It's very possible that there is some precision-related issue causing this, but I believe that a robust triangulator should be able to handle this kind of abuse.
PS! validated by emitting the triangles as an OBJ file and rendering that externally: