Stack overflow on tens of thousands of points
Closed this issue · 7 comments
GoogleCodeExporter commented
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 commented
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 commented
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 commented
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 commented
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 commented
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 commented
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 commented
changes to SweepContext::MeshClean pushed. thanks!
Original comment by mason.gr...@gmail.com
on 2 May 2013 at 1:24
- Changed state: Fixed