Fix triangulator handling of splinters #1205
Conversation
| return true; | ||
| } | ||
| return left->InsideEdge(left->right, epsilon, true); | ||
| return CCW(left->pos, pos, right->pos, epsilon) >= 0; |
There was a problem hiding this comment.
This is interesting - I had been operating under the assumption that I needed to effectively determine a correct perturbation of the epsilon-valid polygon to make it truly valid (non-self-intersecting). This was in fact necessary for my previous triangulator, but since ear clipping proceeds in a naturally manifold way, I tried just letting it clip all degenerate ears. It seems to work great, and vastly simplifies the code. I think the keyholing step may be the only part that's really sensitive to this kind of thing.
Codecov ReportAttention: Patch coverage is
Additional details and impacted files@@ Coverage Diff @@
## master #1205 +/- ##
==========================================
- Coverage 92.23% 92.19% -0.04%
==========================================
Files 31 31
Lines 5988 5985 -3
==========================================
- Hits 5523 5518 -5
- Misses 465 467 +2 ☔ View full report in Codecov by Sentry. 🚀 New features to boost your workflow:
|
| @@ -215,46 +215,47 @@ std::mutex dump_lock; | |||
| * Note that this is not checking for epsilon-validity. | |||
| */ | |||
| bool Manifold::Impl::IsSelfIntersecting() const { | |||
| const double epsilonSq = epsilon_ * epsilon_; | |||
| const double ep = 2 * epsilon_; | |||
There was a problem hiding this comment.
This is the main change to this function - in line with our degenerate checks and such, we increase epsilon to account for error within these checks themselves. The rest of this function is just renames because I was confused by x and y not being directions.
| Manifold result = a + b; | ||
| EXPECT_EQ(result.Status(), Manifold::Error::NoError); | ||
| ManifoldParams().selfIntersectionChecks = selfIntersectionChecks; | ||
| } | ||
|
|
||
| TEST(BooleanComplex, DISABLED_OffsetSelfIntersect) { | ||
| TEST(BooleanComplex, OffsetSelfIntersect) { |
There was a problem hiding this comment.
These disabled tests are now fixed!
| @@ -786,7 +771,8 @@ class EarClip { | |||
| above * CCW(start->pos, vert->pos, connector->pos, epsilon_); | |||
| if (vert->pos.x > start->pos.x - epsilon_ && | |||
| vert->pos.y * above > start->pos.y * above - epsilon_ && | |||
| (inside > 0 || (inside == 0 && vert->pos.x < connector->pos.x)) && | |||
| (inside > 0 || (inside == 0 && vert->pos.x < connector->pos.x && | |||
| vert->pos.y * above < connector->pos.y * above)) && | |||
There was a problem hiding this comment.
Here's the second fix - for the disabled sponge test.
|
Interesting. I think you can try to run the fuzz test. It should report cases that are causing errors in either self-intersection check or triangulation. Let me know if you have trouble running the fuzz test. Btw we don't need to run the script for the fuzz test now, just compile it with fuzzing enabled and run |
|
Got a failure case: will translate it into something readable later... |
|
No, I can't build with the fuzzer - first I needed to change the clang check to I'm going to go ahead and merge this and we can mess with the fuzzer as a follow-on. |
|
@elalish Sounds like we might be able to try removing the interior Status() checks on the SimpleOffset test case now as well? |
|
@starseeker sure - care to make a PR? |
…ad cleared the issue.
) In-loop Status calls were a hacky work-around - see if #1205 had cleared the issue.
Fixes #970
First is just the tests - the polygon is epsilon-valid, but fails to properly triangulate because it doesn't clip the splinters. I also added @pca006132's original test that produced the problem polygon, but that passes on my machine - perhaps simplification changes improved this? I'm pushing it here to see if some other arch has trouble with it.
Okay, I think I have it fixed now, and the algorithm simplified to boot.
And we no longer have any disabled tests!