CDT: stack overflow in insertEdges()

For few not so trivial cases (actually pretty extreme ones), I’m getting stack overflow exception from insertEdge() call. There are many many CDT::Triangulation<double,CDT::LocatorKDTree<double,32,32,32>>::triangulatePseudopolygon calls on the stack causing this. That would be great if refactoring this recursion into a pseudo-recursion loop would be possible. I’m on Win10, VS22. Problem should be reproducible with something like:

#include <random>
#include "CDT.h"

#define POINTS 1000000
#define EDGES 10000
std::random_device rd{};
std::mt19937_64 gen{rd()};
std::gamma_distribution<double> d(0.1,2.0);
std::vector<CDT::V2d<double>> verts;
for (int i = 0; i < POINTS; i++)
{
  CDT::V2d<double> v;
  v.x = d(gen) - 5.0;
  v.y = d(gen) - 5.0;
  verts.push_back(v);
}

std::vector<CDT::Edge> edges;
for (int c = 0; c < EDGES; c++)
{
  int from = rand()%POINTS;
  int to = (from + 1 + rand() % (POINTS - 1)) % POINTS;
  CDT::Edge e{ (size_t)from, (size_t)to };
  edges.push_back(e);
}

CDT::RemoveDuplicatesAndRemapEdges(verts,edges);

CDT::Triangulation<double> cdt;
cdt.insertVertices(verts);
cdt.insertEdges(edges);  // here it occurs
cdt.eraseSuperTriangle();

EDIT: Enlarging stack reserve size in linker (from a default of 1MB) to 10MB resolves the issue (for 1M verts and 10K edges).

About this issue

Original URL
State: closed
Created 2 years ago
Comments: 23 (13 by maintainers)

Commits related to this issue

#84 #86 Performance and API improvments - Don't re-calculate triangles by vertex when finalizing triangulation (don't pay for what you don't use) - If needed calculating triangles by vertex can be ... — committed to artem-ogre/CDT by artem-ogre 2 years ago
#84 #86 Performance and API improvments - Don't re-calculate triangles by vertex when finalizing triangulation (don't pay for what you don't use) - If needed calculating triangles by vertex can be ... — committed to artem-ogre/CDT by artem-ogre 2 years ago
#84 #86 Performance and API improvments - Don't re-calculate triangles by vertex when finalizing triangulation (don't pay for what you don't use) - If needed calculating triangles by vertex can be ... — committed to artem-ogre/CDT by artem-ogre 2 years ago
#86 Convert from recursion to iteration - triangulating pseudo-polygon - inserting edges - conforming to edges — committed to artem-ogre/CDT by artem-ogre 2 years ago
#86 Convert from recursion to iteration - triangulating pseudo-polygon - inserting edges - conforming to edges — committed to artem-ogre/CDT by artem-ogre 2 years ago

Most upvoted comments

It is totally fine, it is your free time and I really appreciate it. Thank you!

artem-ogre on Aug 19, 2022

Hey @artem-ogre , that was a long weekend :p Actually I was quite busy with my own stuff, so please accept my apologies for such delay!

I’ve confirmed, no more stack overflows occurs in insertEdges(), I didn’t test conforming edges as it is currently outside my scope, but probably it is also fine (I’ve reviewed sources while bench marking). I’ve noticed a tiny performance drop, about 5% when compared with stack based implementation but I still prefer stability over speed so thanks for changing it!

msokalski on Aug 18, 2022

Yes, sure. Ill check it on Monday, I’m away for weekend. Thanks.

msokalski on Aug 12, 2022

You should not call insertEdges after eraseSuperTriangle: after eraseSuperTriangle super-triangle vertices are erased, but +3 adjustment will still be applied inside insertEdges. Generally, one should think of eraseXXX methods as a final ‘bake-the-final-data’ step.

This is not a great API design and especially not very newcomer-friendly.

@msokalski I have changed the code so that it would detect if erase... was called (see new Triangulation::isFinalized method) and would throw an exception when trying to add new vertices or edges. This should make the API more error-proof.

artem-ogre on Jul 7, 2022

FYI, trying to add an edge over many colinear vertices which are already edge connected (like in the test case for https://github.com/artem-ogre/CDT/issues/84) can easily overflow stack in the following recursion: https://github.com/artem-ogre/CDT/blob/21cdbb249e58e5628a61ac1a0a1753ee0ec5d437/CDT/include/CDT.hpp#L469

I can see there are many commits made since I pulled, so this may be outdated 😃

msokalski on Jul 6, 2022

You should not call insertEdges after eraseSuperTriangle: after eraseSuperTriangle super-triangle vertices are erased, but +3 adjustment will still be applied inside insertEdges. Generally, one should think of eraseXXX methods as a final ‘bake-the-final-data’ step.

artem-ogre on Jul 5, 2022

Edge-edge overlapping and edge overlapping multiple vertices are supported. And there is quite some internal complexity involved to correctly handle such corner cases 😃 There is also a branch that implements automatically resolving crossing edges intersection points (not 100% numerically robust as intersection points are subject to rounding errors but works in most practical cases).

Surviving crossing edges is not a big deal, the problem is that there are no guarantees that the output is correct.

artem-ogre on Jul 1, 2022

Hi @artem-ogre , No it is not the input problem, in the given example it is pre-filtered using RemoveDuplicatesAndRemapEdges. Also this is not CDT bug, but only refactoring suggestion. CDT is easily able to solve this particular input but it requires changing linking parameters.

Currently insertEdges() makes use of recursive pseudo-polygon algorithm. It is elegant and is fast but it is fragile if too small stack size is given at the compile/link time for executable.

Of course, one could increase executable stack size if scale of the problem can be predicted at the compile time, but usually it is not possible.

One way to resolve this uncomfortable situation is replacing recursive calls to ‘triangulatePseudopolygon’ with a loop emulating call stack (arguments, local variables) on the heap rather on stack.

I hope this time I’m more clear 😃

msokalski on Jul 1, 2022