Hi guys

I have run into a bit of a problem with my 2D rendering library when filling polygons.

If I draw the polygon as an outline, I have no problems since that is a simple line primitive based triangle generator as can be seen below:

However, if I put it through my ear clipping routine and try to full the triangle list, I get this:

I can sort of understand and see why it is happening based on how the ear clipping formula works. What I am not sure on is how to fix. Ear clipping code below. Based on this:

	std::vector<DXTriIndex> tris;
	while (true)
	{
		int tricount = 0;
		for (int i = clockwise ? int(ptlist.size()) - 1 : 0; (clockwise ? i > -1 : i < int(ptlist.size())); i = (i + (clockwise ? -1 : 1)))
		{
			int _pn = clockwise ? -1 : 1;
			int prev = i - _pn;
			if (prev == ptlist.size())
				prev = 0;
			if (prev < 0)
				prev = ptlist.size() - 1;
			int next = i + _pn;
			if (next == ptlist.size())
				next = 0;
			if (next == -1)
				next = ptlist.size() - 1;
			DXPointF pPrev = ptlist[prev];
			DXPointF pCur = ptlist[i];
			DXPointF pNext = ptlist[next];

			DXPointF pu = DXPointF(pCur.xy[0] - pPrev.xy[0], pCur.xy[1] - pPrev.xy[1]);
			DXPointF pv = DXPointF(pNext.xy[0] - pCur.xy[0], pNext.xy[1] - pCur.xy[1]);

			float lu = sqrt((pu.xy[0] * pu.xy[0]) + (pu.xy[1] * pu.xy[1]));
			float lv = sqrt((pv.xy[0] * pv.xy[0]) + (pv.xy[1] * pv.xy[1]));
			pu.xy[0] /= lu;
			pu.xy[1] /= lu;
			pv.xy[0] /= lv;
			pv.xy[1] /= lv;

			float u = (pu.xy[0] * pv.xy[1]) - (pu.xy[1] * pv.xy[0]);

			if (u <= 0)
				continue;
			else
			{
				DXTriIndex tri = { next, prev, i };
				tris.push_back(tri);
				ptlist.erase(ptlist.begin() + i);
				tricount++;
			}
		}
		if (tricount == 0)
			break;
	}

• Your polygon is nonconvex: you should either decompose it into convex pieces or test whether other vertices lie inside the candidate clipped ear triangle (in which case it must be rejected).
• The clockwise variable is undesirable, being a source of complication, and suspect: your polygon should match the orientation of the individual triangles.
• Your are carelessly iterating through a list you are deleting from. In particular, if incrementing indices, after each vertex deletion the next unprocessed vertex shifts to index i.
• It might be better to iterate through vertices in the same direction every time, to reduce complication, and to refactor extracting a predicate that tells whether three DXPointF are arranged clockwise or counterclockwise and a function that adds a triangle to the clipped ears list and removes a vertex from the original polygon.

21 minutes ago, LorenzoGatti said:

• The clockwise variable is undesirable, being a source of complication, and suspect: your polygon should match the orientation of the individual triangles.

What it is actually doing is attempting to convert a clockwise polygon (if whoever is using the lib happens to make it so) into a CCW polygon. The code doesn't change directions while iterating through the vertices. Always same direction.

28 minutes ago, LorenzoGatti said:

• Your polygon is nonconvex: you should either decompose it into convex pieces or test whether other vertices lie inside the candidate clipped ear triangle (in which case it must be rejected).

I meant to ask this question but somehow it slipped my mind while typing. I have found a number of rather confusing methods to determine if a point is inside the candidate ear. Any suggestions on the most efficient method?

30 minutes ago, LorenzoGatti said:

• Your are carelessly iterating through a list you are deleting from. In particular, if incrementing indices, after each vertex deletion the next unprocessed vertex shifts to index i.

Thanks. Excellent point.

Wow, this is a blast from the past!

In addition to everything Lorenzo said:

1. That algorithm I had written is sorta gross. Double loops? Ew. Here's a slightly different version that does the same thing, assuming the polygon is actually convex

create a list of the vertices in CCW order;
let pCur = the first vertex;

while the list has vertices:
	move pCur cyclicly to the next vertex in the list
	let pPrev = the previous vertex in the list
	let pNext = the next vertex in the list
	if the wedge product of (pPrev - pCur) and (pNext - pCur) <= 0:
		continue;
	if there are any vertices in the polygon inside the triangle made by the current vertex and the two adjacent ones:
		continue;
	create the triangle with the points pPrev, pCur, pNext;
	set pCur to pPrev;
	remove pCur from the list;

2. Testing for points inside of the selected triangle is very important to get the correct results. There's a ton of different ways to do it. You should choose one based on profiling and measurement if you're concerned about speed. People on GDN really get into it here: 

3. A relatively minor point: you don't need to normalize pu and pv in order to do the wedge product. It will be the correct sign regardless of whether or not you normalize. Also, for that block of if's at the top, consider using the modulus operator to make things simpler.

5 hours ago, CulDeVu said:

3. A relatively minor point: you don't need to normalize pu and pv in order to do the wedge product. It will be the correct sign regardless of whether or not you normalize. Also, for that block of if's at the top, consider using the modulus operator to make things simpler.

Thanks a bunch Daniel. Did I at least get the wedge product formula correct, though normalized?

Also, to determine whether a polygon is CW or CCW, do I simply add up the area of the polygon and if it is < 0, it is clockwise?

51 minutes ago, Naruto-kun said:

Also, to determine whether a polygon is CW or CCW, do I simply add up the area of the polygon and if it is < 0, it is clockwise?

If you are sure the polygon is convex, it's cheaper: any three consecutive vertices will form a clockwise or anticlockwise triangle. In other words edges, treated as oriented links between consecutive vertices, lie all right (clockwise) or all left (counterclockwise) of the previous edge.

The possibly nonconvex but simple case requires a global test because both turning directions are represented: the signed area is probably the most efficient choice, but the sum of external angles (-2pi or +2pi) is another valid option.

If self-intersections between two edges of the polygon are possible you should find the intersections and break the polygon into multiple simple pieces and decide which regions are interior (meant to be triangulated) or exterior.

@CulDeVu Either I am doing something wrong or the code you sent needs a bit of a revamp. With the polygon example from my original post, it is getting stuck in endless loops. Besides, once the list drops down to about 3 or less, there is the potential for no triangles to be made which of course will leave points in the list and cause an endless loop.

14 minutes ago, Naruto-kun said:

Besides, once the list drops down to about 3 or less,

You should keep track of the number of vertices in the polygon, decrementing the count as you clip ears.

• If you have less than 3 vertices at the beginning, it's a malformed polygon. No triangulation necessary.
• When you are down to three vertices, they form the last triangle in the triangulation and you are done.

1 minute ago, LorenzoGatti said:

You should keep track of the number of vertices in the polygon, decrementing the count as you clip ears.

• If you have less than 3 vertices at the beginning, it's a malformed polygon. No triangulation necessary.
• When you are down to three vertices, they form the last triangle in the triangulation and you are done.

 

Yup. Added that, but still getting endless loops with more than 3 verts (without meddling a bit, no triangles even get formed).

Aha! Perfect. Found the solution. In case anyone wants to do the same (and to give back a bit to this incredibly helpful community), here is the entire set of functions:
Note, DXPointF is just a 2 float array, DXPointFT inherits from DXPointF and adds an int for vertex ID, and DXTriIndex is just an array of 3 ints. The triangle output will fit the default D3D11 Rasteriser settings.
 

	float Sign(DXPointF& p1, DXPointF& p2, DXPointF& p3)
	{
		return (p1.xy[0] - p3.xy[0]) * (p2.xy[1] - p3.xy[1]) - (p2.xy[0] - p3.xy[0]) * (p1.xy[1] - p3.xy[1]);
	};

	bool IsPointInTri(DXPointF& pt, DXPointF& v1, DXPointF& v2, DXPointF& v3)
	{
		bool b1, b2, b3;

		b1 = Sign(pt, v1, v2) < 0.0f;
		b2 = Sign(pt, v2, v3) < 0.0f;
		b3 = Sign(pt, v3, v1) < 0.0f;

		return ((b1 == b2) && (b2 == b3));
	}

	float signedArea = 0;
	bool clockwise = false;
	std::vector<DXPointFT> ptlist;
	for (int i = 0; i < count; i++)
	{
		float x1 = points[i].xy[0];
		float y1 = points[i].xy[1];
		float x2 = 0;
		float y2 = 0;
		if (i == (count - 1))
		{
			x2 = points[0].xy[0];
			y2 = points[0].xy[1];
		}
		else
		{
			x2 = points[i + 1].xy[0];
			y2 = points[i + 1].xy[1];
		}
		signedArea += (x1 * y2 - x2 * y1);
	}
	clockwise = signedArea < 0 ? true : false;
	if (!clockwise)
	{
		for (int i = count - 1; i > -1; i--)
		{
			DXPointFT p;
			p.xy[0] = points[i].xy[0];
			p.xy[1] = points[i].xy[1];
			p.id = i;
			ptlist.push_back(p);
		}
	}
	else
	{
		for (int i = 0; i < count; i++)
		{
			DXPointFT p;
			p.xy[0] = points[i].xy[0];
			p.xy[1] = points[i].xy[1];
			p.id = i;
			ptlist.push_back(p);
		}
	}

	std::vector<DXTriIndex> tris;
	int cur = -1;
	while (ptlist.size())
	{
		int _pn = 1;
		cur = (cur + 1) % ptlist.size();
		int prev = cur - _pn;
		if (prev == ptlist.size())
			prev = 0;
		if (prev < 0)
			prev = (int)ptlist.size() - 1;
		int next = cur + _pn;
		if (next == ptlist.size())
			next = 0;
		if (next == -1)
			next = (int)ptlist.size() - 1;

		DXPointFT pPrev = ptlist[prev];
		DXPointFT pCur = ptlist[cur];
		DXPointFT pNext = ptlist[next];

		DXPointF pu = DXPointF(pPrev.xy[0] - pCur.xy[0], pPrev.xy[1] - pCur.xy[1]);
		DXPointF pv = DXPointF(pNext.xy[0] - pCur.xy[0], pNext.xy[1] - pCur.xy[1]);
		
		float u = (pu.xy[0] * pv.xy[1]) - (pu.xy[1] * pv.xy[0]);

		bool inside = false;
		if (ptlist.size() <= 3 && u <= 0)
			break;

		if (u <= 0)
			continue;
		for (int i = 0; i < ptlist.size(); i++)
		{
			if (IsPointInTri(ptlist[i], pPrev, pCur, pNext))
			{
				inside = true;
				break;
			}
		}
		if (inside)
			continue;

		DXTriIndex tri = { pNext.id, pCur.id, pPrev.id };
		tris.push_back(tri);		
		ptlist.erase(ptlist.begin() + cur);
	}