Stack overflow on tens of thousands of points

[GoogleCodeExporter]

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]

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]

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]

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]

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]

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]

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]

changes to SweepContext::MeshClean pushed. thanks!

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

• Changed state: Fixed