Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

tessTesselate infinite loop #23

Closed
MelvynMay opened this issue Apr 27, 2017 · 5 comments
Closed

tessTesselate infinite loop #23

MelvynMay opened this issue Apr 27, 2017 · 5 comments

Comments

@MelvynMay
Copy link

MelvynMay commented Apr 27, 2017 •
edited

Hi from Unity again! We're seeing the occasional "freeze" reported in libtess2 from the PolygonCollider2D. The following code consistently freezes it it 'tessMeshMergeConvexFaces'. Last report honest!

{
    struct vec2
    {
        vec2(float _x, float _y)
            : x(_x)
            , y(_y)
        {}

        float x;
        float y;
    };
    vec2 points[232] =
    {
        vec2(-0.373205036f, -0.330940127f),
        vec2(-0.0999999940f, -0.0577350110f),
        vec2(0.000000000f, 0.000000000f),
        vec2(0.0999999866f, 0.173205078f),
        vec2(0.199999973f, 0.000000000f),
        vec2(0.399999976f, 0.000000000f),
        vec2(0.600000024f, 0.000000000f),
        vec2(0.700000048f, 0.173205197f),
        vec2(0.800000131f, 0.346410304f),
        vec2(0.700000107f, 0.446410298f),
        vec2(0.563397527f, 0.483012855f),
        vec2(0.600000143f, 0.619615376f),
        vec2(0.700000107f, 0.561880350f),
        vec2(0.800000191f, 0.735085368f),
        vec2(0.600000203f, 0.735085487f),
        vec2(0.600000143f, 0.619615436f),
        vec2(0.463397622f, 0.656218052f),
        vec2(0.500000238f, 0.792820573f),
        vec2(0.463397771f, 0.929423153f),
        vec2(0.600000381f, 0.966025591f),
        vec2(0.600000262f, 0.850555539f),
        vec2(0.800000250f, 0.850555420f),
        vec2(0.700000346f, 1.02376056f),
        vec2(0.600000322f, 0.966025591f),
        vec2(0.563397825f, 1.10262811f),
        vec2(0.700000405f, 1.13923061f),
        vec2(0.800000489f, 1.23923051f),
        vec2(0.900000393f, 1.13923049f),
        vec2(0.800000370f, 1.08149552f),
        vec2(0.900000274f, 0.908290386f),
        vec2(1.00000048f, 1.08149540f),
        vec2(0.900000513f, 1.13923049f),
        vec2(1.10000050f, 1.13923037f),
        vec2(1.20000029f, 0.966025174f),
        vec2(1.10000038f, 1.02376032f),
        vec2(1.00000024f, 0.850555301f),
        vec2(1.20000029f, 0.850555182f),
        vec2(1.20000041f, 0.966025233f),
        vec2(1.30000019f, 0.792820036f),
        vec2(1.20000005f, 0.619615018f),
        vec2(1.20000017f, 0.735085070f),
        vec2(1.00000012f, 0.735085249f),
        vec2(1.09999990f, 0.561880052f),
        vec2(1.19999993f, 0.619614959f),
        vec2(1.23660231f, 0.483012378f),
        vec2(1.09999979f, 0.446410000f),
        vec2(1.00000012f, 0.346410245f),
        vec2(1.20000005f, 0.346410275f),
        vec2(1.10000002f, 0.173205197f),
        vec2(1.30000007f, 0.173205212f),
        vec2(1.20000005f, 0.000000000f),
        vec2(1.09999919f, -0.173204690f),
        vec2(1.30000007f, -0.173204988f),
        vec2(1.20000005f, -0.346410096f),
        vec2(1.40000010f, -0.346410125f),
        vec2(1.30000007f, -0.519615233f),
        vec2(1.40000010f, -0.692820311f),
        vec2(1.50000012f, -0.866025388f),
        vec2(1.40000021f, -1.03922975f),
        vec2(1.60000014f, -1.03923047f),
        vec2(1.50000012f, -1.21243548f),
        vec2(1.40000021f, -1.38564014f),
        vec2(1.30000043f, -1.55884552f),
        vec2(1.40000057f, -1.65884542f),
        vec2(1.50000060f, -1.83205056f),
        vec2(1.40000057f, -1.77431548f),
        vec2(1.30000067f, -1.94752061f),
        vec2(1.50000072f, -1.94752038f),
        vec2(1.50000072f, -1.83205032f),
        vec2(1.60000074f, -2.00525546f),
        vec2(1.50000060f, -2.17846060f),
        vec2(1.50000072f, -2.06299043f),
        vec2(1.30000067f, -2.06299067f),
        vec2(1.40000081f, -2.23619556f),
        vec2(1.50000072f, -2.17846036f),
        vec2(1.40000176f, -2.35166526f),
        vec2(1.30000222f, -2.45166564f),
        vec2(1.20000172f, -2.35166621f),
        vec2(1.30000162f, -2.29393077f),
        vec2(1.20000112f, -2.12072587f),
        vec2(1.10000145f, -2.29393125f),
        vec2(1.20000160f, -2.35166621f),
        vec2(1.10000169f, -2.45166636f),
        vec2(1.00000155f, -2.35166645f),
        vec2(0.963398576f, -2.48826909f),
        vec2(1.00000143f, -2.62487149f),
        vec2(0.863398910f, -2.66147447f),
        vec2(0.863398671f, -2.54600430f),
        vec2(0.663398683f, -2.54600453f),
        vec2(0.763398886f, -2.71920943f),
        vec2(0.863398731f, -2.66147399f),
        vec2(0.900001764f, -2.79807639f),
        vec2(1.00000167f, -2.69807625f),
        vec2(1.10000181f, -2.79807615f),
        vec2(1.00000191f, -2.85581136f),
        vec2(1.10000205f, -3.02901626f),
        vec2(1.20000184f, -2.85581112f),
        vec2(1.10000169f, -2.79807615f),
        vec2(1.20000160f, -2.69807601f),
        vec2(1.30000174f, -2.79807591f),
        vec2(1.33660424f, -2.66147280f),
        vec2(1.30000150f, -2.52487040f),
        vec2(1.43660402f, -2.48826766f),
        vec2(1.43660414f, -2.60373759f),
        vec2(1.63660419f, -2.60373735f),
        vec2(1.53660405f, -2.43053246f),
        vec2(1.43660414f, -2.48826814f),
        vec2(1.40000176f, -2.35166526f),
        vec2(1.53660357f, -2.31506276f),
        vec2(1.73660362f, -2.31506228f),
        vec2(1.63660371f, -2.37279749f),
        vec2(1.73660421f, -2.54600215f),
        vec2(1.83660352f, -2.37279677f),
        vec2(1.73660326f, -2.31506205f),
        vec2(1.93660331f, -2.31506133f),
        vec2(2.03660393f, -2.48826599f),
        vec2(1.93660378f, -2.43053150f),
        vec2(1.83660424f, -2.60373688f),
        vec2(2.03660417f, -2.60373664f),
        vec2(2.03660393f, -2.48826647f),
        vec2(2.17320657f, -2.52486873f),
        vec2(2.13660431f, -2.66147137f),
        vec2(2.17320704f, -2.79807377f),
        vec2(2.03660464f, -2.83467674f),
        vec2(2.03660440f, -2.71920657f),
        vec2(1.83660436f, -2.71920705f),
        vec2(1.93660450f, -2.89241195f),
        vec2(2.03660440f, -2.83467674f),
        vec2(2.07320714f, -2.97127914f),
        vec2(1.93660474f, -3.00788212f),
        vec2(1.83660483f, -3.10788226f),
        vec2(1.73660469f, -3.00788236f),
        vec2(1.83660460f, -2.95014715f),
        vec2(1.73660445f, -2.77694225f),
        vec2(1.63660479f, -2.95014763f),
        vec2(1.73660493f, -3.00788260f),
        vec2(1.63660502f, -3.10788274f),
        vec2(1.53660464f, -3.00788307f),
        vec2(1.50000215f, -3.14448571f),
        vec2(1.53660500f, -3.28108811f),
        vec2(1.40000248f, -3.31769109f),
        vec2(1.40000224f, -3.20222092f),
        vec2(1.20000219f, -3.20222116f),
        vec2(1.30000234f, -3.37542605f),
        vec2(1.40000224f, -3.31769085f),
        vec2(1.43660510f, -3.45429325f),
        vec2(1.30000257f, -3.49089622f),
        vec2(1.20000267f, -3.59089637f),
        vec2(1.10000253f, -3.49089646f),
        vec2(1.20000243f, -3.43316126f),
        vec2(1.10000229f, -3.25995636f),
        vec2(1.00000262f, -3.43316174f),
        vec2(1.10000277f, -3.49089670f),
        vec2(1.00000286f, -3.59089684f),
        vec2(0.900002718f, -3.49089694f),
        vec2(0.763400078f, -3.45429468f),
        vec2(0.800002337f, -3.31769204f),
        vec2(0.900002480f, -3.37542677f),
        vec2(1.00000226f, -3.20222163f),
        vec2(0.800002277f, -3.20222187f),
        vec2(0.800002396f, -3.31769204f),
        vec2(0.663399816f, -3.28108954f),
        vec2(0.700002193f, -3.14448690f),
        vec2(0.663399458f, -3.00788450f),
        vec2(0.800001919f, -2.97128177f),
        vec2(0.800002158f, -3.08675170f),
        vec2(1.00000215f, -3.08675146f),
        vec2(0.900002003f, -2.91354656f),
        vec2(0.800002098f, -2.97128177f),
        vec2(0.763399243f, -2.83467937f),
        vec2(0.663399577f, -2.93467975f),
        vec2(0.563399255f, -2.83468008f),
        vec2(0.663399041f, -2.77694464f),
        vec2(0.563398480f, -2.60373998f),
        vec2(0.463399172f, -2.77694535f),
        vec2(0.563399434f, -2.83467984f),
        vec2(0.463399887f, -2.93468022f),
        vec2(0.363399416f, -2.83468080f),
        vec2(0.226796716f, -2.79807878f),
        vec2(0.263398767f, -2.66147614f),
        vec2(0.363398969f, -2.71921062f),
        vec2(0.463398546f, -2.54600525f),
        vec2(0.263398528f, -2.54600549f),
        vec2(0.263398647f, -2.66147566f),
        vec2(0.126796067f, -2.62487316f),
        vec2(0.163398430f, -2.48827052f),
        vec2(0.126795709f, -2.35166812f),
        vec2(0.263398170f, -2.31506538f),
        vec2(0.263398379f, -2.43053532f),
        vec2(0.463398397f, -2.43053508f),
        vec2(0.363398254f, -2.25733018f),
        vec2(0.263398409f, -2.31506538f),
        vec2(0.226795480f, -2.17846298f),
        vec2(0.363397956f, -2.14186001f),
        vec2(0.463397712f, -2.04185987f),
        vec2(0.563397944f, -2.14185953f),
        vec2(0.463398069f, -2.19959474f),
        vec2(0.563398421f, -2.37279963f),
        vec2(0.663398087f, -2.19959426f),
        vec2(0.563398004f, -2.14185929f),
        vec2(0.663397908f, -2.04185915f),
        vec2(0.763398290f, -2.14185882f),
        vec2(0.800000787f, -2.00525618f),
        vec2(0.763397992f, -1.86865366f),
        vec2(0.900000513f, -1.83205092f),
        vec2(0.900000751f, -1.94752097f),
        vec2(1.10000074f, -1.94752073f),
        vec2(1.00000060f, -1.77431571f),
        vec2(0.900000632f, -1.83205080f),
        vec2(0.863397956f, -1.69544828f),
        vec2(1.00000048f, -1.65884566f),
        vec2(1.10000026f, -1.55884552f),
        vec2(0.900000274f, -1.55884564f),
        vec2(0.800000131f, -1.38564062f),
        vec2(0.700000107f, -1.21243548f),
        vec2(0.500000238f, -1.32790589f),
        vec2(0.426795065f, -1.25470090f),
        vec2(0.400000036f, -1.15470088f),
        vec2(0.499999940f, -1.09696567f),
        vec2(0.399999887f, -1.03923070f),
        vec2(0.399999887f, -0.923760653f),
        vec2(0.499999851f, -0.866025567f),
        vec2(0.599999845f, -0.923760533f),
        vec2(0.699999809f, -0.866025448f),
        vec2(0.799999654f, -0.692820251f),
        vec2(0.899999499f, -0.519615054f),
        vec2(0.799999356f, -0.346410036f),
        vec2(0.699999213f, -0.173205033f),
        vec2(0.500000000f, -0.173205078f),
        vec2(0.299999982f, -0.173205093f),
        vec2(0.0999999866f, -0.173205078f),
        vec2(0.000000000f, -0.230940104f)
    };

    TESStesselator* tess = tessNewTess(NULL);
    tessAddContour(tess, 2, points, sizeof(vec2), 232);
    tessTesselate(tess, TESS_WINDING_ODD, TESS_POLYGONS, 8, 2, NULL);
    tessDeleteTess(tess);
}
@MelvynMay MelvynMay mentioned this issue Apr 27, 2017
Closed
@memononen
Copy link
Owner

Ditto for debugging this one. The merging function has infinite loop, which looks a bit dangerous. Could you try this one instead (have not tested):

int tessMeshMergeConvexFaces( TESSmesh *mesh, int maxVertsPerFace )
{
	TESShalfEdge *e, *eNext, *eSym;
	TESShalfEdge *eHead = &tess->mesh->eHead;
	int curNv, symNv;

	for( e = eHead->next; e != eHead; e = eNext )
	{
		eNext = e->next;
		eSym = eCur->Sym;
		if( !eSym )
			continue;
		
		// Both faces must be inside
		if( !e->Lface || !e->Lface->inside )
			continue;
		if( !eSym->Lface || !eSym->Lface->inside )
			continue;

		curNv = CountFaceVerts( e->Lface );
		symNv = CountFaceVerts( eSym->Lface );
		if( (curNv+symNv-2) > maxVertsPerFace )
			continue;

		// Merge if the resulting poly is convex.
		if( VertCCW( e->Lprev->Org, e->Org, eSym->Lnext->Lnext->Org ) &&
			VertCCW( eSym->Lprev->Org, eSym->Org, e->Lnext->Lnext->Org ) )
		{
			if( e == eNext || e == eNext->Sym ) { eNext = eNext->next; }
			if( !tessMeshDelete( mesh, e ) )
				return 0;
		}
	}

	return 1;
}

The idea is to walk through all edges (instead of faces), and remove them. It has the same pointer checking as RemoveDegenerateEdges() so changes are that work better in corner cases.

@MelvynMay
Copy link
Author

I modified it slight but that stops the infinite loop, thanks! I'll do some more testing later but appreciate getting back to me so fast!

int tessMeshMergeConvexFaces(TESSmesh *mesh, int maxVertsPerFace)
{
    TESShalfEdge *e, *eNext, *eSym;
    TESShalfEdge *eHead = &mesh->eHead;
    int curNv, symNv;

    for (e = eHead->next; e != eHead; e = eNext)
    {
        eNext = e->next;
        eSym = e->Sym;
        if (!eSym)
            continue;

        // Both faces must be inside
        if (!e->Lface || !e->Lface->inside)
            continue;
        if (!eSym->Lface || !eSym->Lface->inside)
            continue;

        curNv = CountFaceVerts(e->Lface);
        symNv = CountFaceVerts(eSym->Lface);
        if ((curNv + symNv - 2) > maxVertsPerFace)
            continue;

        // Merge if the resulting poly is convex.
        if (VertCCW(e->Lprev->Org, e->Org, eSym->Lnext->Lnext->Org) &&
            VertCCW(eSym->Lprev->Org, eSym->Org, e->Lnext->Lnext->Org))
        {
            if (e == eNext || e == eNext->Sym) { eNext = eNext->next; }
            if (!tessMeshDelete(mesh, e))
                return 0;
        }
    }

    return 1;
}

@memononen
Copy link
Owner

good! this version could be a bit more understandable:

int tessMeshMergeConvexFaces( TESSmesh *mesh, int maxVertsPerFace )
{
	TESShalfEdge *e, *eNext, *eSym;
	TESShalfEdge *eHead = &tess->mesh->eHead;
	int leftNv, rightNv;
	TESSvertex *va, *vb, *vc, *vd, *ve, *vf;

	for( e = eHead->next; e != eHead; e = eNext )
	{
		eNext = e->next;
		
		// Both faces must be inside
		if( !e->Lface || !e->Lface->inside )
			continue;
		if( !e->Rface || !e->Rface->inside )
			continue;

		leftNv = CountFaceVerts( e->Lface );
		rightNv = CountFaceVerts( e->Rface );
		if( (leftNv+leftNv-2) > maxVertsPerFace )
			continue;

		// Merge if the resulting poly is convex.
		//
		//      vf--ve--vd
		//          ^|
		// left   e ||   right
		//          |v
		//      va--vb--vc

		va = e->Lprev->Org;
		vb = e->Org;
		vc = e->Sym->Lnext->Dst;

		vd = e->Sym->Lprev->Org;
		ve = e->Sym->Org;
		vf = e->Lnext->Dst;

		if( VertCCW( va, vb, vc ) && VertCCW( vd, ve, vf ) )
		{
			if( e == eNext || e == eNext->Sym ) { eNext = eNext->next; }
			if( !tessMeshDelete( mesh, e ) )
				return 0;
		}
	}

	return 1;
}

be sure to check that you get other than triangles as output too :) if it works equally good, i would appreciate a PR :)

now to change some diapers...

@MelvynMay
Copy link
Author

This follow on one seems to cause a separate crash for some reason.

The change I made to it was "&tess->mesh->eHead;" -> "&mesh->eHead;"

memononen added a commit that referenced this issue Apr 16, 2018
@memononen
Fix for #23
1952b91 
- rewrote tessMeshMergeConvexFaces() to avoid infinite loops
@memononen
Copy link
Owner

Thanks for the repro. I finally go around adding for for this, sorry it took so long.

sakamura added a commit to sakamura/libtess3 that referenced this issue Jul 7, 2018
@sakamura
Merge commit '56d5c87b596bfe792f79b2e41fde83b769f6406d' into original
daa091b 
* commit '56d5c87b596bfe792f79b2e41fde83b769f6406d':
  Fix for memononen#30
  Spaces --> tabs
  Replace calcAngle() with inCircle() to avoid expensive trigonometry
  Spaces --> tabs
  Fix issues
  Add TESS_REVERSE_CONTOURS to TessOption
  Add a reversed flag to tessAddContour()
  Fix for memononen#14
  Fix for memononen#23
  Fix for memononen#22
  Updated link to license
  Small tweaks to CDT

# Conflicts:
#	Example/example.c
#	Source/sweep.c
#	Source/tess.c
#	Source/tess.h
sakamura pushed a commit to sakamura/libtess3 that referenced this issue Jul 9, 2018
@ak-mdonais
Merge remote-tracking branch 'origin/original'
1c53e88 
* origin/original:
  Fix for memononen#30
  Spaces --> tabs
  Replace calcAngle() with inCircle() to avoid expensive trigonometry
  Spaces --> tabs
  Fix issues
  Add TESS_REVERSE_CONTOURS to TessOption
  Add a reversed flag to tessAddContour()
  Fix for memononen#14
  Fix for memononen#23
  Fix for memononen#22
  Updated link to license
  Small tweaks to CDT

# Conflicts:
#	Include/tesselator.h
#	Source/geom.c
#	Source/mesh.c
#	Source/sweep.c
#	Source/tess.c
#	Source/tess.h
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
2 participants
@MelvynMay @memononen