Odd crash on sanitized input (c++)
Closed this issue · 8 comments
GoogleCodeExporter commented
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 commented
crash data
Original comment by buckyballreaction
on 24 Oct 2013 at 11:02
Attachments:
GoogleCodeExporter commented
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 commented
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 commented
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 commented
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 commented
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 commented
Original comment by thahlen@gmail.com
on 21 Nov 2013 at 9:21
- Changed state: Invalid
GoogleCodeExporter commented
I added this additional Java check in the JavaScript version
Original comment by remi.tur...@gmail.com
on 25 Nov 2013 at 10:05