Odd crash on sanitized input (c++)

[GoogleCodeExporter]

Hi,

After using clipper to sanitize our input, we feed the following points into 
poly2tri (see attached).  There is one outer polyline and one hole.

And here is the stack trace:

0x0000000000a2b770 in p2t::Triangle::GetConstrainedEdgeCW (this=0x0, p=...)
    at /scrubbed/bitfighter/poly2tri/common/shapes.cc:275
275       if (&p == points_[0]) {
(gdb) bt
#0  0x0000000000a2b770 in p2t::Triangle::GetConstrainedEdgeCW (this=0x0, p=...)
    at /scrubbed/bitfighter/poly2tri/common/shapes.cc:275
#1  0x0000000000a2c4cb in p2t::Sweep::FinalizationPolygon (this=0x10889a0, 
tcx=...)
    at /scrubbed/bitfighter/poly2tri/sweep/sweep.cc:66
#2  0x0000000000a2c34f in p2t::Sweep::Triangulate (this=0x10889a0, tcx=...)
    at /scrubbed/bitfighter/poly2tri/sweep/sweep.cc:47
#3  0x0000000000a2bf56 in p2t::CDT::Triangulate (this=0x1605200) at 
/scrubbed/bitfighter/poly2tri/sweep/cdt.cc:52
#4  0x0000000000894fe3 in Zap::Triangulate::processComplex 
(outputTriangles=..., bounds=..., polyTree=..., ignoreFills=true, 
    ignoreHoles=false) at /scrubbed/bitfighter/zap/GeomUtils.cpp:1490

We up-scaled the input to Clipper by a factor of 1000 (since Clipper only uses 
integers).  Down-scaling by 1000 and converting to floats before feeding into 
poly2tri produces the same exact crash.

Also, just for fun, I edited poly2tri to use 64 bit integer (signed long long) 
for x and y in the Point struct.  I altered code everywhere else in the same 
way (except for angle calculations in the sweep code).  Same crash happened, 
with upscaled or downscaled points.

Thank you for any help

Original issue reported on code.google.com by buckyballreaction on 24 Oct 2013 at 11:01

[GoogleCodeExporter]

I get this when I run it in my latest codebase for Java.

Skipping edge: Intersecting Constraints : 
[-3882000.0,7191000.0],[-3875026.0,7153693.0] intersects 
[-3883360.0,7168352.0],[-3876543.0,7172961.0]
Skipping edge: Intersecting Constraints : 
[-3846561.0,7193229.0],[-3840166.0,7189498.0] intersects 
[-3882000.0,7191000.0],[3776000.0,7191000.0]

So my guess is that one constraint(edge) from the hole intersects with the 
polygon hull.

This is a dataset that has been processed by clipper?

To detect these issues in the c++ code add a test here:

void Sweep::FlipEdgeEvent(SweepContext& tcx, Point& ep, Point& eq, Triangle* t, 
Point& p)
{
  Triangle& ot = t->NeighborAcross(p);
  Point& op = *ot.OppositePoint(*t, p);

// My java code
        if( t.getConstrainedEdgeAcross(p) )
        {
            int index = t.index( p );
            throw new TriangulationException( "Intersecting Constraints : "+ 
                                              p +","+ op
                                              +" intersects "+
                                              t.points[(index+1)%3] 
                                              +","+ 
                                              t.points[(index+2)%3]);            
        }

and you will have to add

    public boolean getConstrainedEdgeAcross( final TriangulationPoint p )
    {
        if( p == points[0] )
        {
            return cEdge[0];
        }
        else if( p == points[1] )
        {
            return cEdge[1];
        }
        return cEdge[2];
    }

to Triangle

Original comment by thahlen@gmail.com on 25 Oct 2013 at 10:11

[GoogleCodeExporter]

Just looking at the holes point values I can see that some are outside the 
rectangular polygon hull. So something fishy is going on with the clipping.

Original comment by thahlen@gmail.com on 25 Oct 2013 at 10:23

[GoogleCodeExporter]

crash data

Original comment by buckyballreaction on 24 Oct 2013 at 11:02

Attachments:

• p2t_crash_data.txt

[GoogleCodeExporter]

You are absolutely correct.  We had rare-case in the game where a hole could 
have a point outside of the outer hull.  

This was our code problem.  Thank you very much for that code that detected the 
bad points.  Is that standard in the Java version?  Maybe I should use that 
port for debugging...

Thanks again!

Original comment by buckyballreaction on 25 Oct 2013 at 4:42

[GoogleCodeExporter]

I make an assumption the you wiggled the intersection points? That could 
explain why they end up outside the polygon.

Clipper v6 enforces strictly simple polygons:

http://sourceforge.net/p/polyclipping/discussion/1148419/thread/813a62c8/?limit=
50

Maybe upgrading to it can help?

Original comment by thahlen@gmail.com on 25 Oct 2013 at 10:32

[GoogleCodeExporter]

I realized that this simple test could be made sometime after the inital 
release of Poly2Tri so don't really know if it has been ported to other 
version. It just handle some invalid input a bit more gentle.

But apart from this there shouldn't be many differences in the Java and other 
code bases in the core triangulation classes.

I always try to help if someone get stuck on some invalid data :)

Original comment by thahlen@gmail.com on 25 Oct 2013 at 6:05

[GoogleCodeExporter]

I added this additional Java check in the JavaScript version

Original comment by remi.tur...@gmail.com on 25 Nov 2013 at 10:05

[GoogleCodeExporter]

Original comment by thahlen@gmail.com on 21 Nov 2013 at 9:21

• Changed state: Invalid