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

Jump to bottom

Stack overflow on tens of thousands of points #65

Closed
GoogleCodeExporter opened this issue Mar 16, 2015 · 7 comments
Closed

Stack overflow on tens of thousands of points #65

GoogleCodeExporter opened this issue Mar 16, 2015 · 7 comments
Labels
auto-migrated Priority-Medium Type-Defect

Comments

@GoogleCodeExporter
Copy link 

Hello,

I think this is the same as issue 57. I get a stack overflow on big sets of 
points, like over 10000. Recursion in SweepContext::MeshClean is the cause.

The guy in issue 57 gives a fix using std::deque, but I heard that can be slow. 
Here's a simple replacement of SweepContext::MeshClean which is faster and 
fixes the error:

void SweepContext::MeshClean(Triangle& triangle)
{
  std::vector<Triangle *> triangles;
  triangles.push_back(&triangle);

  while(!triangles.empty()){
    Triangle *t = triangles.back();
    triangles.pop_back();

    if (t != NULL && !t->IsInterior()) {
      t->IsInterior(true);
      triangles_.push_back(t);
      for (int i = 0; i < 3; i++) {
        if (!t->constrained_edge[i])
          triangles.push_back(t->GetNeighbor(i));
      }
    }
  }
}

As you can see, the recursion is replaced with a while loop. I recommend 
std::vector instead of std::stack since you can reserve if you can guess the 
size (maybe you can, I can't).

I can provide a dataset which produces the crash on Win 7 x64, if interested. 
Thanks for the great library by the way!

Original issue reported on code.google.com by nonbasketless on 25 Feb 2013 at 6:04
@GoogleCodeExporter
Copy link
Author 

Thanks for your suggestion. I'll forward this to mason since he maintains that 
branch and might not have seen this issue yet. 

This issue comes up now and again it would be nice to have it fixed in the 
current branch.

Original comment by thahlen@gmail.com on 14 Mar 2013 at 7:44

  • Changed state: Accepted

@GoogleCodeExporter
Copy link
Author 

I implemented this fix for the JavaScript version : I am interested in the 
dataset producing the crash.

Original comment by remi.tur...@gmail.com on 21 Mar 2013 at 10:40

@GoogleCodeExporter
Copy link
Author 

You could probably create one easily by just using a unit square polygon and 
add a big number of steiner points inside.

The recursive mesh clean breaks the recursion when hitting a constrained edge. 
Few edges and big number of steiner points will cause the recursive mesh clean 
to go very deep. Causing the stack overflow.

Original comment by thahlen@gmail.com on 21 Mar 2013 at 10:55

@GoogleCodeExporter
Copy link
Author 

Ah, thanks ! I had trouble reproducing the problems using a contour with many 
edges. But many steiner points does the trick.

Original comment by remi.tur...@gmail.com on 21 Mar 2013 at 12:51

@GoogleCodeExporter
Copy link
Author 

I checked this a couple days after posting and feared this project might be 
dead, very happy that it isn't :->

It looks like you've managed to reproduce it, let me know if you still want 
data. A commit for the default branch would be very nice!


I've been using this extensively at work for some high performance 3D work 
(meshing 2D pieces), by the way. It covers pretty much everything, what a great 
library!

Original comment by nonbasketless on 10 Apr 2013 at 11:54

@GoogleCodeExporter
Copy link
Author 

Great to hear you like it :)

Mason said he would push this to the default branch when he got time. Might 
have forgotten it. I'll remind him again since this issue shows up now and 
then.

Original comment by thahlen@gmail.com on 11 Apr 2013 at 2:08

@GoogleCodeExporter
Copy link
Author 

changes to SweepContext::MeshClean pushed. thanks!

Original comment by mason.gr...@gmail.com on 2 May 2013 at 1:24

  • Changed state: Fixed

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
auto-migrated Priority-Medium Type-Defect
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
1 participant
@GoogleCodeExporter