wo80 / Triangle

CMake project for Jonathan Shewchuk's Triangle mesh generator.
Other
63 stars 26 forks source link

Crash when two polygons share the same vertex #10

Open reinterpretcat opened 8 years ago

reinterpretcat commented 8 years ago

Triangle lib seems to crash when two polygons share the same vertex, e.g.: { { 0, 0 }, { 10, 0 }, { 10, 10 }, { 0, 10 } } { { 10, 10 }, { 15, 10 }, { 15, 15 }, { 10, 15 } }

I used the following params: pzB

However, .NET port is working in this case.

wo80 commented 8 years ago

Triangle ignores duplicate input vertices. This will cause a problem, if you reference such a vertex in the segmentlist.

The .NET version is doing the same thing. It doesn't crash because the segments reference the vertex instances directly and not by an index array. Still, one of the segments that share the duplicate vertex will reference the ignored vertex, that is not part of the mesh (that means: it's not connected to any triangle and will have vertex type = UndeadVertex). Though this will work fine most of the time, it might lead to subtle bugs and should be documented somewhere, so thanks for bringing up the issue :-)

reinterpretcat commented 8 years ago

Thanks for information. Is there any way to fix the crash and have behavior similar to .NET port? It is much better than crash. Sometimes it is not possible to avoid duplicates by data preprocessing

wo80 commented 8 years ago

It's actually not what I thought. The original Triangle executable works fine with the following poly file:

8 2 0 1
1   0  0 1
2  10  0 1
3  10 10 1
4   0 10 1
5  10 10 2
6  15 10 2
7  15 15 2
8  10 15 2
8 1
1 1 2 1
2 2 3 1
3 3 4 1
4 4 1 1
5 5 6 2
6 6 7 2
7 7 8 2
8 8 5 2
0

So, the problem is in the insertsegment method:

checkvertex = (vertex) NULL;
encodedtri = vertex2tri(endpoint1);
if (encodedtri != (triangle) NULL) {
    decode(encodedtri, searchtri1);
    org(searchtri1, checkvertex);
}

if (checkvertex != endpoint1) {
    ...
}

For the duplicate vertex, you'd expect encodedtri to be NULL, but you get 0xcdcdcdcd.

Don't know when I get some time to look into this. The first thing to do would be:

reinterpretcat commented 8 years ago

According to https://en.wikipedia.org/wiki/Magic_number_(programming), 0xcdcdcdcd is uninitialized heap memory. Just checked: looks like compiling in Win32 release helped, but not in x64.

reinterpretcat commented 8 years ago

In x64 release, I was able to fix it with additional check: if (encodedtri != (triangle)NULL && vertextype(endpoint1) != UNDEADVERTEX)

wo80 commented 8 years ago

Well, it's not really a fix, just a workaround. I think to fix the issue, you should look where UNDEADVERTEX gets set (by setvertextype), and then add

if (b->poly) setvertex2tri(vertex, NULL);

I'm not an expert at C, so please help me to understand: we're getting no crash in release mode just by coincident, the pointer to the triangle could just as well be non-NULL and make insertvertex fail, right?

Anyway, I'll re-open the issue for now.

reinterpretcat commented 8 years ago

I'm not expert in C too. I've just checked your solution and it seems to work too:

f (!b->quiet) {
        printf(
"Warning:  A duplicate vertex at (%.12g, %.12g) appeared and was ignored.\n",
               sortarray[j][0], sortarray[j][1]);
      }
      setvertextype(sortarray[j], UNDEADVERTEX);
      if (b->poly) setvertex2tri(sortarray[j], NULL);
      m->undeads++;

in divconqdelaunay function