Colinear triangle when convex contour has colinear points on vertical right side

[bsupnik]

Hi,

I'm not sure if this is a bug or design limitation, but: the tesselator appears to create a colinear triangle (e.g. a triangle where all 3 vertices are colinear) if the input is a single contour with colinear vertices on a vertical right side.

Here's my test program.

static void test()
{
	float v[10] = {
		-20.0, 	5.00,
		0.00,		5.00,
		0.00,		15.00,
		0.00,		 25.00,
		-20.0,		 25.00
	};
	
	TESStesselator * t = tessNewTess(nullptr);
	
	tessAddContour(t, 2, v, 2 * sizeof(float), 5);

	float nrm[3] = { 0, 0, 1 };

	int ok = tessTesselate(t, TESS_WINDING_POSITIVE, TESS_POLYGONS, 3, 2, nrm);
	
	if(ok)
	{
		const float * v = tessGetVertices(t);
		int ic = tessGetElementCount(t);
		const int * idx = tessGetElements(t);

		while(ic--)
		{
			int i1 = *idx++;
			int i2 = *idx++;
			int i3 = *idx++;
			printf("Tri: (%.2f,%.2f) (%.2f,%.2f) (%.2f,%.2f)\n",
				v[i1*2],v[i1*2+1],
				v[i2*2],v[i2*2+1],
				v[i3*2],v[i3*2+1]);
		}
	}
	tessDeleteTess(t);
}

The output is:

Tri: (-20.00,25.00) (0.00,5.00) (0.00,25.00)
Tri: (0.00,5.00) (-20.00,25.00) (-20.00,5.00)```
My expectation is that the 3 right-most colinear vertical vertices would not be organized into a single triangle.

Note that if the data is rotated 180 so that the left side has the colinear vertices, the colinear triangle does not occur.  Changing the vertex table to

```	float v[10] = {
		20.0, 		-5.00,
		0.00,		-5.00,
		0.00,		-15.00,
		0.00,		 -25.00,
		20.0,		 -25.00
	};

gives us

Tri: (0.00,-5.00) (20.00,-25.00) (20.00,-5.00)
Tri: (0.00,-15.00) (20.00,-25.00) (0.00,-5.00)
Tri: (20.00,-25.00) (0.00,-15.00) (0.00,-25.00)

where each triangle is non-colinear.

[bsupnik]

One random thought: if the algorithm sweeps mono regions from left to right, is this an artifact of not closing off the end of the sweep properly when there are multiple right-side edges?

[memononen]

I've seen the algorithm to generate bunch of zero area triangles before, but not missing a triangle. I think you are right that the problem is due to monotone triangulation.

I did not write the triangulation code, it is based on the GLU tessellator, I once understood it really well, but a lot of that is forgotten.

I try to find some time in coming week to see if I can figure out what is causing it. I'm super short on time, so if you have the patience to step through the case in debugger that'd be great help.

[bsupnik]

@memononen Thanks - if I find any more details (or specific or confirmed details), I'll be sure to post them here. I've had experience with sweep-line algorithms before but I haven't taken the time to pull this one apart yet.

This isn't at the top of my Q because the colinear triangle does generate an (I guess?) mesh that is manifold and thus doesn't break OpenGL's mesh cracking rules, but it's a case that would be nice to fix because our input data is all axis-aligned, and the next stage for the triangulation algorithm is another algorithm that doesn't cope with degeneracies well. If I spot something I'll let you know.

[memononen]

The incremental delaunay pass that was added recently removes the degenerates quite well. But does not solve the specific case you found.

[bsupnik]

I've found the source of the colinear triangle (or at least, the code path that causes it). The very beginning of tessMessTessellateMonoRegion is producing the colinear triangle in its very first triangulation step.

The algorithm works by blocking off sub-regions of the monotone polygon and fan-triangulating them. In the first iteration the top right side is "lo" and the top is "up". No triangles are built because the algorithm never 'ears off' lo and up; lo is walked backward to the bottom right side.

On pass 2 "Lo's" org forms the beginning of a colinear vertical section, hitting the EdgeSign <= 0 case (our edge sign is exactly 0). We form a triangle from lo->Lnext->Dst to lo->org.

Since we have explicitly allowed for this edge sign to be 0, this step seems weird to me...it explicitly allows us to build a colinear triangle.

I did experiment with making the Edgesign tests < 0 and > 0 and it does seem to fix my case - the algorithm walks "lo" past the colinear vertices on the right side and starts fanning from the upper left corner.

[memononen]

Does that EdgeSign <= 0 case happen to be this one:
955761f

I wish I had documented the fix better. It's not that long ago and I cannot remember all my reasoning. I think there was mismatch between the assert and the code. It has taken me days to swap in those comparisons and equalities a few times in the past :)

[bsupnik]

No, fortunately (maybe?) that's a different code site.