Why is my ear clipping algorithm doing this with EditableMeshes?

[bhristt (chris)]

Recently made an ear clipping algorithm to fill triangles into my polygon in 2d. There’s other parts of the code that add thickness to the polygon to make it 3d, but currently there’s an issue with my algorithm it seems.

When I move to the right of the polygon and create vertices in the right of the polygon, it does not fill in the polygon correctly. Here’s a visual of what it’s doing:

It seems like it’s trying to make a triangle with one of the first (or last) vertices of the polygon with a vertex in the center of the polygon. However, when I mode to the left of the polygon it works as expected:

I’m not sure what could be going on. Here is a snippet of my code for the algorithm part:

-- creates a polygon using ear clipping method from given vertices
-- given vertices must be in order (connecting the vertices in the given
-- order will create the shape)
function PolyUtil.TriangulatePolygon(vertices: {Vector2}): ({{number}}, {{Vector2}})
	
	-- if we aren't given any vertices to work with,
	-- then return an empty table
	if ( #vertices == 0 ) then
		return {}, {}
	end

	-- the number of triangles will always be 2 less than the number of
	-- vertices in the polygon
	local vertexMap = table.clone(vertices)
	local numGoalTriangles = #vertices - 2
	local triangleVertexIndices, triangles = {}, {}

	for i = 1, numGoalTriangles do
		for i = 1, #vertexMap - 1 do

			local vertexIndex0 = G.cycleWithinRange(i - 1, #vertexMap)
			local vertexIndex1 = i
			local vertexIndex2 = G.cycleWithinRange(i + 1, #vertexMap)

			local v0 = vertexMap[vertexIndex0]
			local v1 = vertexMap[vertexIndex1]
			local v2 = vertexMap[vertexIndex2]
			
			local v1ToV0 = v0 - v1
			local v1ToV2 = v2 - v1
			
			-- check if our current ear is convex
			if (  math.acos(v1ToV0:Dot(v1ToV2)/(v1ToV2.Magnitude*v1ToV2.Magnitude)) > math.pi ) then
				continue
			end

			local possibleTriangle = {v0, v1, v2}
			
			if ( areVerticesInsideTriangleV2(vertexMap, possibleTriangle) ) then
				continue
			end

			local v0Index = table.find(vertices, v0)
			local v1Index = table.find(vertices, v1)
			local v2Index = table.find(vertices, v2)

			table.insert(triangleVertexIndices, {v0Index, v1Index, v2Index})
			table.insert(triangles, possibleTriangle)
			table.remove(vertexMap, vertexIndex1)
			break
		end
	end

	if ( #triangles < numGoalTriangles ) then
		warn(`[PolyUtil]: Unable to fully triangulate given polygon.`)
	end

	return triangleVertexIndices, triangles
end

If anyone has experience in making an ear clipping algorithm, please let me know. I have no idea what’s going on with this. To add on, the circle I made in the middle works perfectly with the ear clipping, but it’s only the paths I make that don’t work for some reason.

[7z99 (cody)]

I believe it has to do with the winding order of your polygon, ear clipping algorithms will only work with a single winding order (in your case, it looks like counter clockwise). You need to flip the order of the vertices in such cases.

I implemented this algorithm to determine the winding order of a polygon:

local function getWindingOrder(points: { Vector3 }): number -- returns the winding order of the polygon
	local sumNow = 0
	for i = 1, #points do
		local point1, point2 = points[i], if points[i + 1] then points[i + 1] else points[1]
		local x1,y1,x2,y2 = point1.X, point1.Z, point2.X, point2.Z

		local x, y = x2 - x1, y2 + y1

		sumNow += x * y
	end
	return math.sign(sumNow)
end

It’s been a while since I implemented this, but it should return 1 if clockwise, -1 if counter clockwise, or 0 if the winding order is invalid. Due to the Z axis being flipped in Roblox, this might be the inverse of what you see visually in the workspace, do some testing to see.

Now, reversing the order of the vertices in these cases is easy enough:

local function reverse <t> (t: { t }): { t } -- reverses a table
	local newTable = {}
	for i = #t, 1, -1 do
		table.insert(newTable, t[i])
	end
	return newTable
end

---

On a side note, I don’t believe the ear clipping algorithm always produces a minimal result, you should probably just check that a valid triangle was found over the first iteration, if it wasn’t found, the polygon is invalid.

[bhristt (chris)]

When I reverse the order it makes the problem change directions. Instead of doing it when I go left, it does it when I go right. Not sure what that means, but I feel like this gets me closer to the solution

[bhristt (chris)]

Got it working. I messed up on the convex check. Instead of using the dot product to calculate an angle ( which will never exceed 180 degrees using this method ), I used the cross product to check for convex angles. If the cross product of both of the vertices from the ear to the adjacent points is negative, it indicates a concave angle. The ear clipping method relies on ignoring the concave angles in the polygon, so that simple change fixed my problem.