Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Crash in Earcut::findHoleBridge #54

Closed
huhtanen opened this issue Oct 14, 2017 · 11 comments · Fixed by #55
Closed

Crash in Earcut::findHoleBridge #54

huhtanen opened this issue Oct 14, 2017 · 11 comments · Fixed by #55
Labels

Comments

@huhtanen
Copy link

Hi,

Earcut::eliminateHoles contains the following loop:

    // process holes from left to right
    for (size_t i = 0; i < queue.size(); i++) {
        eliminateHole(queue[i], outerNode);
        outerNode = filterPoints(outerNode, outerNode->next);
    }

Earcut::filterPoints may return nullptr in case it reduces the polygon into a point, but findHoleBridge called by eliminateHole expects outerNode to be non-null, and crashes if filterPoints returns nullptr before the last iteration of the above for-loop on this line:

if (hy <= p->y && hy >= p->next->y && p->next->y != p->y) {

I've locally fixed/worked around the issue by modifying the loop condition in eliminateHoles as follows:

-    for (size_t i = 0; i < queue.size(); i++) {
+    for (size_t i = 0; i < queue.size() && outerNode; i++) {

and made similar modification to call-site of eliminateHoles to handle the nullptr case.

Is this the correct way around the issue?

@mrgreywater
Copy link
Collaborator

mrgreywater commented Oct 14, 2017

I'll look into the issue, some vertex data to reproduce the crash would be perfect.

This is likely related to mapbox/earcut#87

@mourner
Copy link
Member

mourner commented Oct 14, 2017

Earcut::filterPoints may return nullptr in case it reduces the polygon into a point

Note that it should never return null — in the case of a point, it will return the pointer to that point's node. Also looks related to mapbox/earcut#83

@huhtanen
Copy link
Author

huhtanen commented Oct 14, 2017

Earcut::filterPoints may return nullptr in case it reduces the polygon into a point

Note that it can never return null — in the case of a point, it will return the pointer to that point's node. So the cause must be something else.

Not sure what you mean. As far as I understand it, the code from filterPoints below checks whether the current edge is degenerate, or the two adjacent edges are colinear, and in such case removes the middle node. After this elimination it checks if the current node is same node as next node, and returns nullptr;

If p == p->next, then isn't the polygon just a point?

        if (!p->steiner && (equals(p, p->next) || area(p->prev, p, p->next) == 0)) {
            removeNode(p);
            p = end = p->prev;

            if (p == p->next) return nullptr;
            again = true;

        } else {
            p = p->next;
        }

@huhtanen
Copy link
Author

I'll look into the issue, some vertex data to reproduce the crash would be perfect.
This is likely related to mapbox/earcut#87

Looks like the same issue, I agree!

Below is one example polygon which causes the issue:

0:
    -32, 493
    -32, 444
    0, 440
    6, 487
1:
    -32, 501
    -13, 645
    -32, 648
2:
    -32, 493
    -32, 444
    0, 440
    6, 487
3:
    -32, 501
    -13, 645
    -32, 648
4:
    -32, 493
    -32, 444
    0, 440
    6, 487
5:
    -32, 501
    -13, 645
    -32, 648
6:
    -32, 493
    -32, 444
    0, 440
    6, 487
7:
    -32, 501
    -13, 645
    -32, 648
8:
    -32, 493
    -32, 444
    0, 440
    6, 487
9:
    -32, 501
    -13, 645
    -32, 648
10:
    -32, 493
    -32, 444
    0, 440
    6, 487
11:
    -32, 501
    -13, 645
    -32, 648

@mourner
Copy link
Member

mourner commented Oct 14, 2017

@mrgreywater
Copy link
Collaborator

mrgreywater commented Oct 15, 2017

replacing return nullptr; with break; (or the equivalent return p;) should do the trick, but it's probably better to check the changes with a larger test set than we have hardcoded here.

@huhtanen
Copy link
Author

huhtanen commented Oct 15, 2017

replacing return nullptr; with break; (or the equivalent return p;) should do the trick, but it's probably better to check the changes with a larger test set than we have hardcoded here.

In that case should the below nullptr check be if (ear == ear->next), or should it simply be removed?

template <typename N>
void Earcut<N>::earcutLinked(Node* ear, int pass) {
    if (!ear) return;

eliminateHoles could also early exit by checking every iteration if p == p->next, instead for p == nullptr, but then again, it might not be common enough case to warrant for extra checks.

@mrgreywater
Copy link
Collaborator

mrgreywater commented Oct 15, 2017

@huhtanen Neither. earcutLinked will not do anything if ear == ear->next anyway. But checking for a nullptr is required for code sanity reasons, even if it might never happen.

@mourner
Copy link
Member

mourner commented Oct 17, 2017

@mrgreywater are you looking into a fix? I guess always treating 1-point holes as if they were Steiner points (and never returning null in filterPoints) seems like a good solution.

@mrgreywater
Copy link
Collaborator

I am, but I want to rewrite the test generating script first, to allow additional tests for earcut.hpp that aren't in earcut.js. I don't want to merge the fix without having a testcase that actually confirms it's working.

mrgreywater added a commit to mrgreywater/earcut.hpp that referenced this issue Oct 19, 2017
@mrgreywater
Copy link
Collaborator

So I rewrote the tests to be auto registering, which allows custom (manually written) tests without risking them to be overwritten by the script.
Interestingly after I added the patch, the new test case also gave out some new undefined behaviour warnings which we will have to look into.

/home/travis/build/mrgreywater/earcut.hpp/include/mapbox/earcut.hpp:606:60: runtime error: division by zero
/home/travis/build/mrgreywater/earcut.hpp/include/mapbox/earcut.hpp:606:38: runtime error: value -nan is outside the range of representable values of type 'int'
/home/travis/build/mrgreywater/earcut.hpp/include/mapbox/earcut.hpp:607:60: runtime error: division by zero
/home/travis/build/mrgreywater/earcut.hpp/include/mapbox/earcut.hpp:607:38: runtime error: value -nan is outside the range of representable values of type 'int'
/home/travis/build/mrgreywater/earcut.hpp/include/mapbox/earcut.hpp:609:17: runtime error: left shift of negative value -2147483648
/home/travis/build/mrgreywater/earcut.hpp/include/mapbox/earcut.hpp:614:17: runtime error: left shift of negative value -2147483648

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Development

Successfully merging a pull request may close this issue.

3 participants